Feature Request: Linked Arrays

[downs]

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