why does array appending add a page size instead of doubling ?

[Steven Schveighoffer]

On Sun, 03 Feb 2013 03:53:10 -0500, timotheecour  
<thelastmammoth at gmail.com> wrote:

>> Note that dynamic arrays are generic containers, so they aren't exactly  
>> optimized for anything. You could try that test with the "made for  
>> appending" std.array.appender: It always tries to extend without  
>> reallocating, and only relocates when the current memory segment is  
>> 100% full.
>>
>> Furthermore, when it *does* relocate, it use D-style memmove without  
>> calling postblit. Independent of language, and with the requirement of  
>> contiguous memory, I can't really think of a scheme that could be  
>> better than that...?
>
>
> modified a bit (see below) to include timing etc. I'm on OSX (16GB ram,  
> core i7 2.3GHz).
> dmd is slow even with optimizations so I used ldc:
>
> ldmd2 -inline -O -release -noboundscheck  (similar results with ldc2 -O3  
> -release)
> for C++: g++ -O2
>
> It seems that:
> * the number of moves is up to 2x (resp. 1.8x) as the C++ version for  
> T[] (resp. appender)
> * the C++ version is 7x (resp 1.8x) times faster .
> * it seems even the appender version grows super-linearly whereas C++  
> version stays roughly linear in that regime in terms of time.
>
> Based on this, I'm curious whether the current growing scheme could be  
> improved, or be closer to the simple doubling scheme used in C++.

The performance increase is due to a) using malloc instead of GC  
allocation, which would run quite a few collection cycles while  
allocating.  If you profile the D code, you will see this.  b) vector is  
FREEING its previously used array space, D array appending is relying on  
the GC to free that space.  The consumed D space will grow more rapidly.

You are essentially comparing apples to oranges here.

-Steve