www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Array Appending and DRuntime

reply dsimcha <dsimcha yahoo.com> writes:
For a while now, I've had a suspicion that the builtin array appending has
gotten slower lately.  The talk about array appenders here lately has brought
that to a head, so I decided to test it and find out.  Here's the test program
I used:

import std.stdio, std.perf;

void main() {
    scope pc = new PerformanceCounter;
    pc.start;
    uint[] foo;
    foreach(i; 0..1_000_000) {
        foo ~= i;
    }
    pc.stop;
    writeln(pc.milliseconds);
}

Results:

DMD 2.019 (Last release before druntime):  42 milliseconds.
DMD 2.020 (First release with druntime):  ~1000 milliseconds.
DMD 2.029 (Current version):  ~1000 milliseconds.
DMD 2.029 (Replacing ~= with the Appender struct):  18 milliseconds.
DMD 2.029 (Replacing builtin array with rangeextra.TNew):  19 milliseconds.

I think it's abundantly clear that I wasn't just going crazy and something
changed between 2.019 and 2.020 that made the builtin ~= about 25x slower.  It
probably is related to druntime because this was the only major change between
2.019 and 2.020.  If we could put this back to the way it was in 2.019, this
would drastically reduce the need for more complicated solutions.  Here's some
speculation about what might have happened:

1.  Since Appender and TNew both use the builtin array's reallocation scheme,
it's not a reallocation scheme issue.
2.  gcx.d appears to cache the last block size query.  This means that
repeatedly querying the same block in a single threaded program (where
thread_needLock() returns false and no lock is necessary) is very fast.  This
is true in both the old Phobos GC and the druntime GC.  I wonder if this was
somehow bypassed by the ~= operator when druntime was integrated with DMD in
its early days.
Apr 25 2009
next sibling parent dsimcha <dsimcha yahoo.com> writes:
== Quote from dsimcha (dsimcha yahoo.com)'s article

 2.  gcx.d appears to cache the last block size query.  This means that
 repeatedly querying the same block in a single threaded program (where
 thread_needLock() returns false and no lock is necessary) is very fast.  This
 is true in both the old Phobos GC and the druntime GC.  I wonder if this was
 somehow bypassed by the ~= operator when druntime was integrated with DMD in
 its early days.


On further examination, this is clearly somehow related to caching.  Here is a
very similar test program, that appends to tow arrays instead of one:

import std.stdio, std.perf;

void main() {
    scope pc = new PerformanceCounter;
    pc.start;
    uint[] foo, bar;
    foreach(i; 0..1_000_000) {
        foo ~= i;
		bar ~= i;
    }
    pc.stop;
    writeln(pc.milliseconds);
}

Timings:
DMD 2.019:  ~1800 ms
DMD 2.029:  ~2300 ms (Note:  Still slower but not by as much even in absolute
terms)
DMD 2.029 (Using Appender instead of ~=):  49 ms

By appending to two arrays, we screw up the caching scheme, hence much poorer
performance.  However most use cases probably involve appending to only one
array
at a time.  Since this is a clear regression, I'll file a bug report.
Apr 25 2009
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
dsimcha:

 DMD 2.019 (Last release before druntime):  42 milliseconds.
 DMD 2.020 (First release with druntime):  ~1000 milliseconds.
 DMD 2.029 (Current version):  ~1000 milliseconds.
 DMD 2.029 (Replacing ~= with the Appender struct):  18 milliseconds.
 DMD 2.029 (Replacing builtin array with rangeextra.TNew):  19 milliseconds.


I have done some more timings:

Timings, appending 100_000_000 uints, seconds:
  DMD 1.042:                 7.51
  DMD 1.042, ArrayBuilder:   1.81
  DMD 2.029:                 a lot
  DMD 2.029, Appender:      22.83

I don't like the user interface of Appender.

---------------

The code I have used:

void main() {
    uint[] foo;
    for (int i; i < 100_000_000; i++)
        foo ~= i;
}

---------------

import d.builders: ArrayBuilder;
void main() {
    ArrayBuilder!(uint) b;
    for (int i; i < 100_000_000; i++)
        b ~= i;
    uint[] arr = b.toarray;
}

---------------

import std.array: appender;
void main() {
    char[] arr;
    auto app = appender(&arr);
    for (int i; i < 100_000_000; i++)
        app.put(i);
    auto result = app.data;
}

Bye,
bearophile
Apr 25 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
bearophile wrote:

 dsimcha:

 DMD 2.019 (Last release before druntime):  42 milliseconds.
 DMD 2.020 (First release with druntime):  ~1000 milliseconds.
 DMD 2.029 (Current version):  ~1000 milliseconds.
 DMD 2.029 (Replacing ~= with the Appender struct):  18 milliseconds.
 DMD 2.029 (Replacing builtin array with rangeextra.TNew):  19 milliseconds.


 
 I have done some more timings:
 
 Timings, appending 100_000_000 uints, seconds:
   DMD 1.042:                 7.51
   DMD 1.042, ArrayBuilder:   1.81
   DMD 2.029:                 a lot
   DMD 2.029, Appender:      22.83


I'm not sure on what machine you test, but on my (crappy old) laptop, 
your Appender example completes in 4.95 seconds. Are you sure you are 
measuring the right thing?

Andrei
Apr 25 2009
parent reply bearophile <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:

 I'm not sure on what machine you test, but on my (crappy old) laptop, 
 your Appender example completes in 4.95 seconds. Are you sure you are 
 measuring the right thing?


My purpose is to have a good standard library and a good language.
Errors of mine are always possible. Benchmarks are tricky things.

I have redone the tests, the CPU is unloaded, no computation is going on, the
system is WinXP with 2 GB RAM, 2 GHz Core 2.

New timings give no less than 22.6 seconds, repeated. As running time I use a
timing command similar to the "time" of Linux, that gives the total running
time of the program (final deallocations too).

I think Appender can be improved some. You can also try DMD1, to compare
timings, it's not a fully dead language yet.

Bye,
bearophile
Apr 25 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
bearophile wrote:

 Andrei Alexandrescu:

 I'm not sure on what machine you test, but on my (crappy old)
 laptop, your Appender example completes in 4.95 seconds. Are you
 sure you are measuring the right thing?


 
 My purpose is to have a good standard library and a good language. 
 Errors of mine are always possible. Benchmarks are tricky things.
 
 I have redone the tests, the CPU is unloaded, no computation is going
 on, the system is WinXP with 2 GB RAM, 2 GHz Core 2.
 
 New timings give no less than 22.6 seconds, repeated. As running time
 I use a timing command similar to the "time" of Linux, that gives the
 total running time of the program (final deallocations too).
 
 I think Appender can be improved some.


I can't improve what I can't measure. On my system, liberally loaded 
with a variety of programs, weaker than yours (1.8GHz/512MB laptop) I 
get 4.8s with -O and 5.3s without. The major difference is the OS 
(Ubuntu on my laptop), but I am puzzled as Appender doesn't assume a lot 
about the OS. I time with Unix time. I copied the code straight from 
your post. Please advise.

Andrei
Apr 25 2009
parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article

 bearophile wrote:

 Andrei Alexandrescu:

 I'm not sure on what machine you test, but on my (crappy old)
 laptop, your Appender example completes in 4.95 seconds. Are you
 sure you are measuring the right thing?


 My purpose is to have a good standard library and a good language.
 Errors of mine are always possible. Benchmarks are tricky things.

 I have redone the tests, the CPU is unloaded, no computation is going
 on, the system is WinXP with 2 GB RAM, 2 GHz Core 2.

 New timings give no less than 22.6 seconds, repeated. As running time
 I use a timing command similar to the "time" of Linux, that gives the
 total running time of the program (final deallocations too).

 I think Appender can be improved some.


 I can't improve what I can't measure. On my system, liberally loaded
 with a variety of programs, weaker than yours (1.8GHz/512MB laptop) I
 get 4.8s with -O and 5.3s without. The major difference is the OS
 (Ubuntu on my laptop), but I am puzzled as Appender doesn't assume a lot
 about the OS. I time with Unix time. I copied the code straight from
 your post. Please advise.
 Andrei


I think I can actually explain this.  For some reason (I don't know why) the
Linux
GC is less susceptible to false pointers than the Windows GC.  You can prove
this
by playing with associative arrays and seeing how big an associative array has
to
get before there is a high probability that the GC won't free it.  (See bugzilla
2105.)

I get timings more similar to Bearophile on my WinXP box.  If blocks of memory
keep getting hit with false pointers on reallocation (which they do when arrays
get this big, at least on Windows), and you have to allocate more memory from
the
OS, etc., of course it's going to be slower.

As for why the Linux GC is less susceptible to false pointers, I really don't
know.  It's just an empirical observation.  I would guess that maybe Linux
allocates from the top of the address space, where false pointers are less
frequent.

Other than that, I would suggest only using 1,000,000 or so elements both
because
100,000,000 is just plain unrealistic in most real-world use cases and because
you
avoid false pointer issues that way.
Apr 25 2009