D array expansion and non-deterministic re-allocation

[Steven Schveighoffer]

On Sun, 22 Nov 2009 21:19:15 -0500, Bartosz Milewski  
<bartosz-nospam at relisoft.com> wrote:

> Andrei Alexandrescu Wrote:
>
>> I'm not sure I figure what the issue is, and I'd appreciate a rehash of
>> the few other issues brought up. (I thought they had been responded to.)
>
> Some of the points are in my message from Sat, 05:19 pm. Especially this  
> point: Can a conforming implementation simply re-allocate on every  
> expansion? You make it sound like that would violate some performance  
> guarantees but there are no specifics.

My view is that a conforming implementation could reallocate on every  
expansion.  That translates to an MRU cache size of zero.

But the MRU cache is just one way to solve the problem, and does not need  
to be in the language spec.  It's an implementation detail.

BTW, the more disturbing case than those being discussed, one which  
violates more than just your expectations is:

string x = "hello".idup;
auto y = x[0..1];
y ~= "appy";

We must have a solution to this problem, to keep the promise of  
immutability intact.  The other problem of sometimes sharing data is not  
as important IMO.

Basically, we have 2 options for the spec:

A. Once you append to an array, you cannot change the data through that  
array for any other alias to the original array, so x ~= y is equivalent  
to x = x ~ y.
B. Appending to an array may reallocate, so appending to x may allow x to  
share it's prefix bytes with another array.

Whatever implementation satisfies the choice is correct, however optimized  
you want to make it.

For instance, you could use an MRU cache for immutable data only, and  
still satisfy rule A.

I also agree that there should be an array building mechanism, because  
these rules may not satisfy all usages.

-Steve