Permalink
Reply
Hi fellow Dlangers,
I am working on an old codebase, and found a re-implementation of standard dynamic arrays as a struct called ArrayBuilder, visible on my github
The comment says:
/**
* Behaves the same as built-in arrays, except about 6x faster with concatenation at the expense of the base pointer being 4 system words instead of two (16 instead of 8 bytes on a 32-bit system).
*/
So I wrote a unittest to verify that claim, using for benchmark 10_000_000 concatenations :
trace("*** ArrayBuilder Concatenation benchmark ***");
import std.datetime.stopwatch : benchmark, Duration;
import std.array : appender;
void concat_withStd()
{
int[] array;
for (int j = 0; j < 1000; j++)
array ~= j;
}
void concat_withStdReserve()
{
int[] array;
array.reserve(1000);
for (int j = 0; j < 1000; j++)
array ~= j;
}
void concat_withStdLength()
{
int[] array;
array.length = 1000;
for (int j = 0; j < 1000; j++)
array[j] = j;
}
void concat_withAppenderReserve()
{
auto array = appender!(int[]);
//trace ("array is ", array);
array.reserve(1000);
for (int j = 0; j < 1000; j++)
array ~= j;
}
void concat_withArrayBuilder()
{
ArrayBuilder!(int) array;
for (int j = 0; j < 1000; j++)
array ~= j;
}
auto r = benchmark!(concat_withStd,
(...)//stuff
concat_withArrayBuilder)(10_000);
tracef("with std: %s", bench1);
tracef("with stdReserve: %s", bench2);
tracef("with stdLength: %s", bench3);
tracef("with AppenderReserve: %s", bench4);
tracef("with Arraybuilder: %s \n", bench5);
The results are below (you can also git clone the repo + dub test):
| Concatenation method | benchmark in ms |
|---|---|
| with std: | 385 ms |
| with stdReserve: | 327 ms |
| with stdLength: | 29 ms |
| with AppenderReserve: | 256 ms |
| with Arraybuilder: | 118 ms |
-
The use of reserve does not seem to improve much the standard concatenation performance. Would you know why?
-
Increasing the length of the array before-hand is by far the best solution, as expected.
-
AppenderReserve outperforms a basic concatenation, but the gain is not completely obvious, even with a call to reserve. Is it expected behavior?
-
ArrayBuilder is 3 times faster than standard concatenation, and twice as fast as AppenderReserve! Which explanation would you give? I looked at the ArrayBuilder struct, it's a very basic code with no magic trick. I also looked at the phobos Appender code on github, in particular the code for put() line 3460, it's obviously more complex:
import core.internal.lifetime : emplaceRef;
ensureAddable(1);
immutable len = _data.arr.length;
auto bigData = (() @trusted => _data.arr.ptr[0 .. len + 1])();
emplaceRef!(Unqual!T)(bigData[len], cast() item);
//We do this at the end, in case of exceptions
_data.arr = bigData;
There are some functions calls... Maybe the drag comes from there. I am really out of my league here, any help appreciated. I am not even sure which part of the Appender code is activated.
cheers
