[racket] Should immutable lists be implemented as over-allocated arrays?

From: Greg Hendershott (greghendershott at gmail.com)
Date: Tue Aug 2 14:54:20 EDT 2011

Should immutable lists be implemented as over-allocated arrays,
instead of as linked lists?

Seems like immutable lists don't need the pointer-like, linked-list
semantics of mutable lists.

1. Contiguous items means better locality of reference (for various
levels of cache, from CPU on up to OS virtual memory).
2. Requires less memory. (See also 1. The happy case of speed and
space, not speed vs. space.)
3. Nearly all operations will be as fast (e.g. `car', `cdr') or faster
(e.g. `length', `list-ref').

Cons: (pun warning)
1. One operation should be slower: `cons'. But `cons' simply prepends
an element to the front of the array. The array could be
over-allocated so only every N `cons' ops actually expand the array
space. (This is a simplified case of a
keep-the-gap-near-the-insertion-point array, but where the "gap" is
always on the front, and there are no memcpy shifts at all.)

This:                       is:
(list 1 2 3 4 5)            [___gap____12345]
(cons 0 (list 1 2 3 4 5))   [___gap___012345]

But I'm assuming that the array holds objects themselves. If instead
the array must contain pointers to objects, then goodbye locality of
reference and this wouldn't be as big a win after all.

The more I think about it, Racket vectors need to be of pointers to
things, not the things themselves. And so would need to be an array
implementation of mutable lists. Hmm.

I'm guessing only flvector is a simple array of things (floats) themselves?

Posted on the users mailing list.