Spikes in array capacity

[Steven Schveighoffer]

On Thu, 01 Jul 2010 12:46:27 -0400, Ali Çehreli <acehreli at yahoo.com> wrote:

> There is something strange in the array capacity algorithm.
>
> import std.stdio;
> import std.array;
>
> void main()
> {
>      int[] a;
>      size_t oldCapacity;
>
>      foreach (i; 0 .. 100_000_000) {
>          a ~= i;
>
>          if (a.capacity != oldCapacity) {
>              writeln("length: ", a.length,
>                      " capacity: ", capacity(a),
>                      " ratio: ", cast(double)capacity(a) / oldCapacity);
>              oldCapacity = capacity(a);
>          }
>      }
> }
>
> Produces:
>
> length: 1 capacity: 3 ratio: inf        please ignore this one ;)
> length: 4 capacity: 7 ratio: 2.33333
> length: 8 capacity: 15 ratio: 2.14286
> length: 16 capacity: 31 ratio: 2.06667
> length: 32 capacity: 63 ratio: 2.03226
> length: 64 capacity: 127 ratio: 2.01587
> length: 128 capacity: 255 ratio: 2.00787
> length: 256 capacity: 509 ratio: 1.99608
> length: 512 capacity: 1021 ratio: 2.00589
> length: 1022 capacity: 2045 ratio: 2.00294
> length: 2046 capacity: 3069 ratio: 1.50073
> length: 3070 capacity: 4093 ratio: 1.33366
> length: 4094 capacity: 5117 ratio: 1.25018
> ...
> length: 1153022 capacity: 1154045 ratio: 1.00089
> length: 1154046 capacity: 1155069 ratio: 1.00089
> length: 1155070 capacity: 3153917 ratio: 2.7305    <-- spike
> length: 3153918 capacity: 3154941 ratio: 1.00032
> length: 3154942 capacity: 3155965 ratio: 1.00032
> ...
> length: 4741118 capacity: 4742141 ratio: 1.00022
> length: 4742142 capacity: 4743165 ratio: 1.00022
> length: 4743166 capacity: 12333053 ratio: 2.60017  <-- spike
> length: 12333054 capacity: 12334077 ratio: 1.00008
> length: 12334078 capacity: 12335101 ratio: 1.00008
> ... (there are more spikes later on)
>
> Is that intended?
>
> Ali

No, that is not intended.  Please file a bugzilla against druntime.

-Steve