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](https://tinyurl.com/2nr25ytt)
The comment says:
```d
/**
* 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 :
```d
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](https://github.com/dlang/phobos/blob/master/std/array.d),
in particular the code for put() line 3460, it's obviously more
complex:
```d
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
