D array expansion and non-deterministic re-allocation

[Andrei Alexandrescu]

dsimcha wrote:
> == Quote from Bartosz Milewski (bartosz-nospam at relisoft.com)'s article
>> dsimcha Wrote:
>>> The one thing that I think has been missing from this discussion is, what would be
>>> the alternative if we didn't have this "non-deterministic" reallocation?  How else
>>> could you **efficiently** implement dynamic arrays?
>> In the long run (D3), I proposed using the "unique" type modifier. If an array
> is unique, the compiler knows that there are no slices to worry about, and it can
> use in-place reallocation to its heart content. That pretty much solves the
> performance problem.
>> In the short run (D2), I would suggest sticking to "reallocate on every
> extension" semantics (especially in SafeD) and provide a library solution (a la
> C++ std::vector) where the performance of appending is an issue.
> 
> Probably not a bad idea, since:
> 
> 1.  I've concluded that appending to slices simply can't be made both efficient
> and safe.
> 
> 2.  We'll probably get a std.collections anyhow.
> 
> 3.  If you **really** care about performance, you should only append when you
> don't know the length in advance.  If you know the length, you should always
> pre-allocate.

We will have collections and all those good things, but I don't see how 
the proposal follows from the feedback. My perception is that this is a 
group of people who use D. Bartosz' concern didn't cause quite a riot, 
so as far as I can tell there is no big issue at stake. (Add to that the 
fact that today's arrays are even _more_ potentially puzzling because, 
without the MRU cache, expanding slices may trample over other slices.)

In contrast, slowness of ~= comes time and again to haunt this 
newsgroup. Want it or not, people will want to use T[] and ~= to manage 
arrays. We could remove the ~= operator and require use of a library 
type for appends, but the aforementioned facts suggest that that might 
not be the best decision.

One thing that Bartosz didn't mention is that "this unique" is different 
than "the other unique", which I think reveals the half-bakedness of the 
proposal. "The other unique" that was intensively discussed before is 
transitive, meaning that the root reference points to a graph of objects 
having no other connection to the outer world. "This unique" is very 
different because it's shallow - only the array chunk is unaliased, but 
the members of the array don't need to be. This is a very important 
distinction.


Andrei