Array append performance

JAnderson ask at me.com
Mon Aug 25 08:21:42 PDT 2008


Lionello Lunesu wrote:
> Nevermind. None of that explained why bearophile's program is so slow. 
> This does:
> 
> int[] ~= int is using _d_arrayappendcT (from internal/gc/gc.d), which 
> appends an int by appending its four bytes! Blasphemy! Now we have great 
> super-duper-efficient array operations using SSEx but a simple append of 
> an int to an int[] is using a "rep movs" to append 4 bytes. X-(
> 
> Also, the append code first checks whether the array should be resized, 
> and if not, jumps to the actual append code. The common case should not 
> be branching: { if (too small) goto resize; append: ... return; resize: 
> ... goto append; }
> 
> The use of _d_arrayappendcT is hardcoded in the D compiler (e2ir.c) so I 
> don't know how to create different code paths for different primitive 
> (sizes) other than to add many ifs to _d_arrayappendcT. IIRC, TypeInfo 
> contained a pointer to a method for fast array comparisons. Shouldn't a 
> similar thing be added for array appends?
> 
> BTW, the capacity look-up was indeed using the cached values. Meaning, 
> it's not "capacity" we should be focussing on, but the general append 
> code. However, if you were to append to two different arrays in a 
> similar loop, the performance would be terrible, since each array would 
> overwrite the cache with its own ptr/size, resulting in the slow O(m+n) 
> for each capacity look-up.
> 
> L.

Great stuff!

-Joel



More information about the Digitalmars-d mailing list