Array append performance (Was: Re: Lisp like lists and a problem with TANGO fromStringz)

[Bjoern]

Oskar Linde schrieb:
> bearophile wrote:
>> To: Newsgroups: digitalmars.D
>> Subject: Re: Lisp like lists and a problem with TANGO fromStringz
>>
>> Oskar Linde>Here is a way to reserve space for arrays:<
>>
>> I did try a function equal to that one, but have you timed it? My 
>> timing results don't show any advantage of using such reserve.
> 
> There are more advantages to do it than speed. Memory fragmentation and 
> wastage for example.
> 
> <snip>
> 
>> OUTPUT TIMINGS:
>>
>> DMD 1.026, N = 12_000_000:
>>   append:            3.3 s
>>   reserve + append:  3.3 s
>>   allocate + assign: 1.0 s
> 
> 
> It is hard to draw too many conclusions from such a simple test. For one 
> thing, the DMD GC will on array appends try to grow the allocated GC 
> chunk without reallocating. In an application such as this (with 
> virtually no memory fragmentation), there is a good chance that it is 
> able to do that almost all the time.
> 
> DMD/GDC also seems unable to inline the _d_arrayappendcTp call which 
> would be one reason for the rather poor performance overall.
> 
> There are cases where the reallocation helps though, even though the 
> performance overall is embarrassing compared to not appending.
> 
> GDC 0.24, N = 120_000_000:
>    append:            9.3 s
>    reserve + append:  5.3 s
>    allocate + assign: 1.3 s
> 
> (Also note that append in this case wastes 168 MB memory compared to 
> reserve+append (*))
> 
> It is also slightly faster for small arrays, where the GC bucket 
> limitation prevents in place growing from happening:
> 
> GDC 0.24, N = 512:
>    append:            26  µs
>    reserve + append:  23  µs
>    allocate + assign: 1.7 µs
> 
> ----
> 
> *) There seems to be a bug (or it might be by design) that the GC on 
> appending to an array sometimes allocates up to 3x the required memory 
> (to me, it seems anything above 2x is seriously overkill). The line in 
> question is in internal/gc/gc.d in Phobos, where the correct line is 
> commented out:
> 
> //long mult = 100 + (1000L * size) / (6 * log2plus1(newcap));
> long mult = 100 + (1000L * size) / (log2plus1(newcap));
> 
> So, for example, appending one int to a 1MB int[] array, could result in 
> an array with 3MB reserved space. Or appending a single int to a 74MB 
> array results in a 184 MB array. Something to look out for.
> 

Gentleman,
somebody out there remembering the topic ?   ... :
Bjoern -< OOPS wrong planet.