D array expansion and non-deterministic re-allocation

[dsimcha]

== Quote from Andrei Alexandrescu (SeeWebsiteForEmail at erdani.org)'s article
> Bartosz Milewski wrote:
> > Andrei Alexandrescu Wrote:
> >
> >
> >>> 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.
> >> I don't think a conforming implementation is allowed to do that. The
> >> functioning of many algorithms assumes constant-time append. If D can't
> >> guarantee that, those algorithms won't work.
> >>
> >> I've been deliberately vague in the book because I wasn't sure we can
> >> offer a guarantee if the cache is filled. Now I know we can: if a memory
> >> block stores the requested size in addition to today's effective
> >> capacity, then the allocator can overallocate growing arrays and then
> >> detect and correctly handle in-place reallocation requests, even when
> >> the MRU cache capacity is exceeded. There would be a larger cost for
> >> that (acquiring a lock), but it's still a constant amortized per-element
> >> cost.
> >
> > I wish we had some performance numbers to support this optimization. There's
always a break-even point between O(1) and O(N) and I wonder at what N it happens.
Also, how often does it happen that the cache is full--whether it's normal state
or an exception. Hitting the cache and the heap lock on every extension will also
break locality. There are so many factors...
> Very true. It would be great if you or someone else interested could
> find the time to run a few tests. I am committed way over the top and
> simply cannot look into this.
> Andrei

But one of my biggest gripes about the current appending implementation, far more
important from a practical perspective than any theoretical safety guarantees, is
that it doesn't scale to multiple threads.  I've experienced this in a real-world
program that I translated from someone else's C++ code that used
vector::push_back() quite liberally inside core algorithms.  (The reason is that
it was written more for simplicity/readability than performance, so the person who
wrote it never thought to optimize this kind of stuff.)  When I did a literal
translation of this to D, everything was completely serialized.  It didn't even
scale to two cores.  I had to rewrite significant portions of the code in a way
that did not use appending to get it to scale at all.

D is supposed to be a language that is geared toward multi-threading.  If
something as simple as array appending is a threading bottleneck (and it was for
me in a real-world program), I don't care if it is O(1) because effectively it has
a constant the size of Jupiter.