D array expansion and non-deterministic re-allocation

[Steven Schveighoffer]

On Mon, 23 Nov 2009 16:33:42 -0500, dsimcha <dsimcha at yahoo.com> wrote:

> 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.

It's hard to say that your example is a good fit for the arrays of D.   
What you need is a library type that does not require a global lock for  
appending.  Such is not the case for every example of appending in D, and  
the existence of the current D arrays does not prevent you from adding  
more specialized types.  There are other costs to using such types besides  
the global lock, such as storing the capacity, and if you are slicing,  
locally storing the slice extents.

-Steve