Appender is ... slow

[Jonathan M Davis via Digitalmars-d-learn]

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