[Issue 4412] Array capacity growth spikey and the ratio approaches 1.0

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=4412


bearophile_hugs at eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bearophile_hugs at eml.cc


--- Comment #4 from bearophile_hugs at eml.cc 2010-07-02 09:31:02 PDT ---
This is a simplified version of that code:


import std.stdio: writeln;
void main() {
    int[] array;
    size_t oldCapacity;

    foreach (i; 0 .. 20_000) {
        array ~= i;
        size_t newCapacity = array.capacity();
        if (newCapacity != oldCapacity) {
            writeln(cast(double)newCapacity / oldCapacity);
            oldCapacity = newCapacity;
        }
    }
}


It prints:

inf
2.33333
2.14286
2.06667
2.03226
2.01587
2.00787
1.99608
2.00589
2.00294
1.50073
1.33366
1.25018
1.20012
1.16675
1.14292
1.12505
1.11115
1.10003
1.09093
1.08335
1.07694
1.07144
1.06668
1.06251
1.05883
1.05556
1.05264

This output shows that there is a bug: to allow an O(1) amortized append the
size of the array has to grow geometrically.

So I suggest to use a geometric growth factor of 2 until the memory block is
"large enough", something like 200MB or 300MB. And after such absolute memory
limit then use a smaller geometric growth factor, like 1.3, to avoid wasting
too much memory.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------