# Spikes in array capacity

Ali Çehreli acehreli at yahoo.com
Fri Jul 2 10:01:41 PDT 2010

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