On Thursday, 14 August 2014 at 17:16:42 UTC, Philippe Sigaud
wrote:
From time to time, I try to speed up some array-heavy code by
using std.array.Appender, reserving some capacity and so on.
It never works. Never. It gives me executables that are maybe
30-50% slower than bog-standard array code.
I don't do anything fancy: I just replace the types, use
clear() instead of = null...
Do people here get good results from Appender? And if yes, how
are you using it?
Quick test...
----------------
import std.array;
import std.datetime;
import std.stdio;
enum size = 1000;
void test1()
{
auto arr = appender!(int[])();
foreach(n; 0 .. size)
arr.put(n);
}
void test2()
{
int[] arr;
foreach(n; 0 .. size)
arr ~= n;
}
void test3()
{
auto arr = new int[](size);
foreach(n; 0 .. size)
arr[n] = n;
}
void test4()
{
auto arr = uninitializedArray!(int[])(size);
foreach(n; 0 .. size)
arr[n] = n;
}
void main()
{
auto result = benchmark!(test1, test2, test3, test4)(10_000);
writeln(cast(Duration)result[0]);
writeln(cast(Duration)result[1]);
writeln(cast(Duration)result[2]);
writeln(cast(Duration)result[3]);
}
----------------
With size being 1000, I get
178 ms, 229 μs, and 4 hnsecs
321 ms, 272 μs, and 8 hnsecs
27 ms, 138 μs, and 7 hnsecs
24 ms, 970 μs, and 9 hnsecs
With size being 100,000, I get
15 secs, 731 ms, 499 μs, and 1 hnsec
29 secs, 339 ms, 553 μs, and 8 hnsecs
2 secs, 602 ms, 385 μs, and 2 hnsecs
2 secs, 409 ms, 448 μs, and 9 hnsecs
So, it looks like using Appender to create an array of ints is
about twice as fast as appending to the array directly, and
unsurprisingly, creating the array at the correct size up front
and filling in the values is far faster than either, whether the
array's elements are default-initialized or not. And the numbers
are about the same if it's an array of char rather than an array
of int.
Also, curiously, if I add a test which is the same as test2 (so
it's just appending to the array) except that it calls reserve on
the array with size, the result is almost the same as not
reserving. It's a smidgeon faster but probably not enough to
matter. So, it looks like reserve doesn't buy you much for some
reason. Maybe the extra work for checking whether it needs to
reallocate or whatever fancy logic it has to do in ~= dwarfs the
extra cost of the reallocations? That certainly seems odd to me,
but bizarrely, the evidence does seem to say that reserving
doesn't help much. That should probably be looked into.
In any case, from what I can see, if all you're doing is creating
an array and then throwing away the Appender, it's faster to use
Appender than to directly append to the array. Maybe that changes
with structs? I don't know. It would be interesting to know
what's different about your code that's causing Appender to be
slower, but from what I can see, it's definitely faster to use
Appender unless you know the target size of the array up front.
- Jonathan M Davis
