Feature Request: Linked Arrays

[downs]

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