Spikes in array capacity

[Andrei Alexandrescu]

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.


Andrei