Bill Baxter wrote:
On Mon, Nov 23, 2009 at 2:09 PM, Steven Schveighoffer
<schvei...@yahoo.com> wrote:
On Mon, 23 Nov 2009 16:33:42 -0500, dsimcha <dsim...@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
