Kernel LISP - how low down can it go?
Thu, 22 May 1997 11:38:57 -0700
>Subject: Re: Kernel LISP - how low down can it go?
>Date: Thu, 22 May 1997 12:15:48 -0400 (EDT)
>From: BRIAN SPILSBURY <email@example.com>
>> 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. :)
This already has been done and it even has a name. It's called