Array concatenation vs. Appender

[Steven Schveighoffer]

On Sat, 02 Feb 2013 10:47:39 -0500, FG <home at fgda.pl> wrote:

> On 2013-02-02 13:50, Era Scarecrow wrote:
>> On Saturday, 2 February 2013 at 11:33:07 UTC, Namespace wrote:
>>> I'm was quite surprised as I had heard the first time of these  
>>> 'appender'.
>>> Therefore I'm asking me:
>>> Why is the 'appender' method so much more efficient?
>>
>>   Because concatenation likely will end up relocating the memory over  
>> and over
>> again (possibly lots of abandoned slices too) whereas the appender will
>> allocated & reuse the same buffer. On the other hand you might be  
>> better off
>> (depending on the need) with just reserving a lot more memory (close to  
>> what you
>> need or slightly larger) and then concatenation will perform much  
>> better. But if
>> it need to reallocate then you've still got the same problem with  
>> slices where
>> with the appender you probably won't.
>
> Yeah but let us move reallocation out of the equation.
> Reserving space limits the amount of RAM used and can avoid  
> reallocations all together but in a little test it came out that still  
> appender is 2.5-4 times faster than tab ~= str, where tab is char[]  
> (same when it is ubyte[]). Why is that?
>
> Let's say we have this code:
>
>      char[] tab;
>      string fill = "1234";
>      uint loops = 100_000_000;
>      tab.reserve(loops * fill.length);
>      foreach (i; 0..loops) tab ~= fill;
>
> Using Appender changes the above loop into something like this:
>
>      size_t capacity = tab.capacity;
>      foreach (i; 0..loops) {
>          size_t flen = fill.length;
>          size_t len = tab.length;
>          if (len + flen > capacity) {
>              ...
>              // use GC.extend or GC.qalloc & memcpy
>              // update capacity and assign tab = memory_block[0..len]
>          }
>          tab = tab.ptr[0..len+flen];
>          tab.ptr[len..len+flen] = fill[];
>      }
>
> Why cannot tab ~= fill achieve similar performance as this code?
> Am I missing something important?

Appender is built for appending and has higher up-front costs, and higher  
memory costs.

Normal arrays can be used for appending, but also can be used for so many  
other things.

In other words, Appender cannot have the features that standard arrays  
have in order to make appending as fast as possible.

-Steve