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. Pros: 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? _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
