Reserving/Preallocating associative array?

[thedeemon]

On Thursday, 26 December 2013 at 14:09:29 UTC, bearophile wrote:

> A question for people that know something about the D garbage 
> collector: can it be added some logic to the GC to detect the 
> situations where you have to allocate many times very 
> frequently, and disable or rarefy the collection frequency, to 
> increase the code performance a lot? (I think "recently" the 
> Python garbage collector has added such optimization). This way 
> that enabling and disabling the GC becomes not needed any more.

I think it's possible. During the sweep phase where GC returns 
unmarked memory blocks (garbage) to the free lists, it can 
calculate total amount of freed memory at this stage. Probably 
this stat is already being calculated. It also knows total size 
of its heap, so after a collection it can know how much % of the 
heap was freed. When the program is in a state where it mostly 
allocates, this % will be very low compared to usual case. When 
GC sees it's so low it can increase the effective threshold for 
the next collection, making collections less often. I think 
actual parameter will be the size of pool allocated from system 
memory. AFAIR, currently GC is triggered when there are not 
enough free blocks in the current pool, and if after collection 
there is still not enough free space a new pool gets allocated. 
Its size is currently constant, making long allocating loops run 
in O(n^2) but if the pool size will grow in cases where % of 
collected memory is low and shrink back when % of freed space is 
bigger again, then GC will adapt to allocation rate and such 
scenarios will work faster.