D array expansion and non-deterministic re-allocation

[Andrei Alexandrescu]

Bill Baxter wrote:
> On Mon, Nov 23, 2009 at 2:09 PM, Steven Schveighoffer
> <schveiguy at yahoo.com> wrote:
>> 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.
> 
> That's likely to be far too big a limitation for the upcoming world of
> parallelism everywhere.
> But the single-threaded GC is the real culprit.  Fix that and arrays
> shouldn't be a problem either.

I agree. Overall, our eyes should be at this point focused on principle 
matters rather than matters of optimizations that can be done but 
haven't been done yet.

Without being 100% sure, I conjecture that array primitives can be 
implemented efficiently if we give the implementation the freedom to end 
sharing for ~=. Also I am not ruling out the possibility that we can 
guarantee a ~= that never keeps sharing with existing arrays. (One idea 
I discussed with Walter was encoding uniqueness of arrays in a bit 
stored with the array limits.)


Andrei