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

[Andrei Alexandrescu]

d-bugmail at puremagic.com wrote:
> 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.

...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