Kernel LISP - how low down can it go?

[BRIAN SPILSBURY]

> I don't think he was suggesting that you make _every_ immutable list
> into a vector; only that some immutable lists might profit from such
> a thing.

Right
 
> Actually, for the most part I wouldn't advise making most immutable
> cons cells into vectors, since one still has to worry about recursing
> down a list with CDR's, so it would be nice if this were reasonably
> efficient.

Yeah, I wasn't thikning of a normal vector, but rather leaving out the
cdr reference, once the list had been rearranged to be linear, with
a special case to catch falling off the end. Then you could have cdr/car
work normally on elements of the list.

At the least for reasonable length lists this would save around

#-#-#-#-#-#-#-#-| (16 references)
| | | | | | | |
a b c d e f g h

becomes

abcdefgh| (9 references)

and we get a saving of almost half. A magic termination symbol may be
necessary, but that's not a huge deal.

As for speed, I suspect it will be slightly faster.
Another advantage is that it reduces fragmentation.

I haven't tested this yet, so I guess its speculative. :)

Brian