Feature Request: Linked Arrays

[janderson]

janderson wrote:
> downs wrote:
>> janderson wrote:
>>> Robert Fraser wrote:
>>>> I'd rather ask the GC to expose a canExpand() method and have it
>>>> implemented in the library.
>>> I agree.
>>
>> So do I, actually. That would be best.
>>> BTW, to state the obvious:
>>>
>>> "Linked arrays" have several dis-advantages when compared to arrays.
>>> Namely after a while of lots of insertions deletions they become very
>>> fragmented and performance slows down.
>>
>> I don't see how that could happen, if you're only appending at the end.
>>
>>> 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.
>>
>> I don't have the benchs to demonstrate that though. Sorry.
>>
>>> One think what would help, is if you could get the next free aligned
>>> block in memory from the previous block.  That way the array would be
>>> slightly more cache friendly.
>>>
>>
>> I don't understand.
>>
>>> I'm not saying this sort of data struct doesn't have it's uses,
>>> sometimes its useful for minimizing Memory Manager fragmentation.  In
>>> fact if you have a huge array, sometimes the only way to get around
>>> fragmentation is to spit it up.
>>
>> That's the idea :) Currently, appending to an array is almost 
>> embarassingly slow. This forces the use of preallocating, which is 
>> unintuitive.
>>
>> Imnsho :)
>>
>>> -Joel
>>
>>  --downs
> 
> 
> This may help:
> 
> http://video.google.com/videosearch?hl=en&safe=off&pwst=1&resnum=0&q=herb%20sutter&um=1&ie=UTF-8&sa=N&tab=wv 
> 
> 
> Note that smallest cache lines could be as small as 64bit.
> 
> -Joel


Also you should be aware of this trick:

array.length = 100;
array.length = 0;

Will preallocate memory for you.

-Joel