Feature Request: Linked Arrays

[Robert Fraser]

downs wrote:
> Since one of D's weaknesses is bad speed when appending to dynamic arrays, I've been thinking about a way to fix this.
> 
> Linked arrays are a hybrid between flat arrays and linked list: a single linked list of array chunks.
> 
> Basically, a linked array (syntax: T[>], new T[50>]) looks like this:
> 
> struct LinkedArray {
>   void* start;
>   size_t my_length;
>   size_t length();
>   LinkedArray* nextBlock, lastBlock;
> }
> 
> When appending to a LinkedArray, it is first checked if the current block can be grown to accomodate the new member(s) *without* reallocating.
> 
> If it can't, instead of reallocating and copying, a new LinkedArray is tacked on the end.
> 
> Because of this, there is never redundancy as with current arrays, and the load on the GC can be vastly reduced.
> 
> Appending is also much closer to linear than with current arrays. This makes Linked Arrays highly suitable for queues and buffers.
> 
> On the other hand, they're completely incompatible with C libraries, don't expose a .ptr property (not flat), and because of the complexities of their layout, all slices have to be constant (value, not reference).
> 
> But these disadvantages are, imho, more than made up by the benefits they'd offer as an alternative to current arrays.
> 
> Also, they don't need new keywords :)
> 
> Whaddya think?
> 
>  --downs

I'd rather ask the GC to expose a canExpand() method and have it 
implemented in the library.