Array concatenation vs. Appender

FG home at fgda.pl
Sat Feb 2 07:47:39 PST 2013


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?




More information about the Digitalmars-d-learn mailing list