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

[Andrei Alexandrescu]

d-bugm...@puremagic.com wrote:
http://d.puremagic.com/issues/show_bug.cgi?id=4412

bearophile_h...@eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bearophile_h...@eml.cc


--- Comment #4 from bearophile_h...@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.

...when it is actually being move. Per my previous message - you may 
want to evaluate and print the ratio only when the array is effectively 
relocated.

Andrei