[plt-scheme] PLT4 expectations

On Mar 11, Matthew Flatt wrote:
> At Tue, 11 Mar 2008 13:59:33 -0400, Doug Orleans wrote:
> > 
> > How about "length" and "last"?  Or would those be too expensive in
> > space?
> 
> Yes, I think that would be too expensive.

Here's a cute idea: make a second type `xcons' for extended cons cells
with a place for a (fixnum) count, allocate cons cells as usual,
except that once in a while (at random, or once every N allocations)
you allocate an xcons instead.  Then, when `length' is used the code
iterates down the list as usual -- except when it runs into an xcons:
in that case it either uses the cached length or set it if it's
missing (ignoring further xconses so it's still an iteration).

... But my guess is that this is too heavy and that `length' is not a
big bottleneck.  (Esp. if the GC can get good locality.)

-- 
          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                  http://www.barzilay.org/                 Maze is Life!