Feature Request: Linked Arrays

[Steven Schveighoffer]

"downs" wrote
> janderson wrote:
>> The main thing you have to
>> watch out for is traversal. Often I've seen code slow down because
>> people write a data structure to speed up insertion, not realizing that
>> most of the time was spent in traversal.  By using links the work of the
>> pre-fetcher, code optimizer and cache is increased.
>
> It depends on the size of the elements.
>
> If it's, say, an int[>], about 1k of them could fit into a single page of 
> memory. At that point, and especially if the next array pointer is stored 
> at the _end_ of the memory range, and considering that linear traversal 
> can easily be enhanced with prefetch instructions, I think the traversal 
> speed difference to flat arrays shrinks considerably.

If each array chunk is the same size, you could store the array in an array 
of arrays.  Then lookup time becomes O(1), and appending data is not going 
to cause a copy of the other array chunks that you already have allocated.

If you add a huge piece that is bigger than one chunk, just allocate that 
piece, then slice the piece up into chunks.

It could actually be an array of pointers, assuming all your chunks are the 
same size.

I'd prefer that to a linked list of arrays, where traversal is O(n) (with a 
small constant)

-Steve