Feature Request: Linked Arrays

[janderson]

Steven Schveighoffer wrote:
> "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 
> 
> 

Yes this is often better, although it depends on what you are doing.

-Joel