Kernel LISP - how low down can it go?
Thu, 22 May 1997 12:15:48 -0400 (EDT)
> 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.
> 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
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
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. :)