D array expansion and non-deterministic re-allocation

Bartosz Milewski bartosz-nospam at relisoft.com
Sat Nov 21 14:19:08 PST 2009


> int[] a = [0];
> auto b = a;
> a ~= 1;
> b ~= 2;
> What is a[1]?
>
> Is this considered "stomping" and requiring a re-allocation?

Can this question be answered without the recourse to implementation, and the MRU cache in particular? 

I thought about an abstract definition of "stomping".Something like that: The expanded part of the array is never implicitly shared with any other array. But I'm not sure about this case:

int[] a = [1, 2, 3];
int[] b = a[0..1];
b ~= 4;
what is a[1]?

By my definition, this would be considered stomping, but I couldn't find this example in TDPL. 

I'm also not sure what to make of this statement: "client code is guaranteed to benefit of good average performance over a large number of appends to the same array". Since "good" is open to interpretation, such a guarantee is meaningless. If it is meant as "amortized O(1)", it's impossible to fulfill, unless the MRU cache is infinite and a lookup is O(1).

Then there is the problem of multithreading. A global MRU cache would require potentially expensive synchronization. A thread-local cache, on the other hand, makes thread creation even more heavy-weight than it is right now. My prediction is that D will be evolving towards user-level threads and fine granularity concurrency, which requires very small thread footprint. 



More information about the Digitalmars-d mailing list