Spikes in array capacity

[Ali Çehreli]

Andrei Alexandrescu wrote:
 > Ali Çehreli wrote:
 > [snip]
 >> Now the spikes are gone, and the allocations asymptote at
 >> once-per-1024 elements for an int array:
 >>
 >> length: 1 capacity: 3 ratio: inf reserve: 2
 >> length: 4 capacity: 7 ratio: 2.33333 reserve: 3
 >> length: 8 capacity: 15 ratio: 2.14286 reserve: 7
 >> length: 16 capacity: 31 ratio: 2.06667 reserve: 15
 >> length: 32 capacity: 63 ratio: 2.03226 reserve: 31
 >> length: 64 capacity: 127 ratio: 2.01587 reserve: 63
 >> length: 128 capacity: 255 ratio: 2.00787 reserve: 127
 >> length: 256 capacity: 509 ratio: 1.99608 reserve: 253
 >> length: 512 capacity: 1021 ratio: 2.00589 reserve: 509
 >> length: 1022 capacity: 2045 ratio: 2.00294 reserve: 1023
 >> length: 2046 capacity: 3069 ratio: 1.50073 reserve: 1023
 >> length: 3070 capacity: 4093 ratio: 1.33366 reserve: 1023
 >> ....
 >>
 >> In the long run, there is one allocation per 1024 elements. That still
 >> feels like amortized constant, but considering that relocation times
 >> would be O(N), I think reserve should still grow with N, but maybe not
 >> too much. (I am not sure about this last point at all.)
 >
 > You may want to also print the pointer to the first element of the
 > array. That provides you information about how often the array is
 > actually moved.

Good point. :) Yes, spikes are only when the array is moved.

I've also discovered that a basic array invariant is violated at size 
509 as well:

import std.string;
import std.array;

void main()
{
     int[] a;
     a.length = 509;
     a ~= 0;

     assert(a.capacity >= a.length,
            format("capacity: %s length: %s", a.capacity, a.length));
}

Outputs

core.exception.AssertError at deneme.d(17444): capacity: 509 length: 510

I will update the bug with these.

Ali