why does array appending add a page size instead of doubling ?

[Ali Çehreli]

On 02/02/2013 08:37 PM, Ali Çehreli wrote:
 > On 02/02/2013 06:22 PM, timotheecour wrote:
 >  > What's the rationale behind array appending adding a page size to
 >  > capacity
 >
 > It is not always the case. The page is added only if the next page
 > conveniently free. There is no cost for that "allocation".

I have tested this for D and C++ with the following programs. They count 
the number of times the underlying buffer gets reallocated and the 
number of elements that get moved as a result of that.

Here is the C++ program:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
     for (size_t maxElements = 1; maxElements <= 0x4000000; maxElements 
*= 2) {
         vector<int> s;
         size_t totalElementsMoved = 0;
         size_t totalAllocations = 0;

         for (size_t i = 0; i < maxElements; ++i) {
             int *oldPtr = s.empty() ? NULL : &s[0];
             s.push_back(0);

             if (&s[0] != oldPtr) {
                 totalElementsMoved += (s.size() - 1);
                 ++totalAllocations;
             }
         }

         cout << "Elements: " << maxElements
              << " Allocations: " << totalAllocations
              << " Moved: " << totalElementsMoved
              << '\n';
     }
}

It indeed shows amortized constant growth. The total number of elements 
that get moved is always one less than the eventual size of the array 
and the number of times of the allocations is predictable:

Elements: 1 Allocations: 1 Moved: 0
Elements: 2 Allocations: 2 Moved: 1
Elements: 4 Allocations: 3 Moved: 3
Elements: 8 Allocations: 4 Moved: 7
Elements: 16 Allocations: 5 Moved: 15
Elements: 32 Allocations: 6 Moved: 31
Elements: 64 Allocations: 7 Moved: 63
Elements: 128 Allocations: 8 Moved: 127
Elements: 256 Allocations: 9 Moved: 255
Elements: 512 Allocations: 10 Moved: 511
Elements: 1024 Allocations: 11 Moved: 1023
Elements: 2048 Allocations: 12 Moved: 2047
Elements: 4096 Allocations: 13 Moved: 4095
Elements: 8192 Allocations: 14 Moved: 8191
Elements: 16384 Allocations: 15 Moved: 16383
Elements: 32768 Allocations: 16 Moved: 32767
Elements: 65536 Allocations: 17 Moved: 65535
Elements: 131072 Allocations: 18 Moved: 131071
Elements: 262144 Allocations: 19 Moved: 262143
Elements: 524288 Allocations: 20 Moved: 524287
Elements: 1048576 Allocations: 21 Moved: 1048575
Elements: 2097152 Allocations: 22 Moved: 2097151
Elements: 4194304 Allocations: 23 Moved: 4194303
Elements: 8388608 Allocations: 24 Moved: 8388607
Elements: 16777216 Allocations: 25 Moved: 16777215
Elements: 33554432 Allocations: 26 Moved: 33554431
Elements: 67108864 Allocations: 27 Moved: 67108863

Here is the D program:

import std.stdio;

void main()
{
     for (auto maxElements = 1; maxElements <= 0x400_0000; maxElements 
*= 2) {
         int[] s;
         auto totalElementsMoved = 0;
         auto totalAllocations = 0;

         foreach (i; 0 .. maxElements) {
             auto oldPtr = s.ptr;
             s ~= 0;

             if (s.ptr != oldPtr) {
                 totalElementsMoved += (s.length - 1);
                 ++totalAllocations;
             }
         }

         writefln("Elements: %s, Allocations: %s, Moved: %s",
                  maxElements, totalAllocations, totalElementsMoved);
     }
}

Its output is different in that the number of allocations is less than 
C++ but the total number of elements that get moved are more:

Elements: 1, Allocations: 1, Moved: 0
Elements: 2, Allocations: 1, Moved: 0
Elements: 4, Allocations: 2, Moved: 3
Elements: 8, Allocations: 3, Moved: 10
Elements: 16, Allocations: 4, Moved: 25
Elements: 32, Allocations: 5, Moved: 56
Elements: 64, Allocations: 6, Moved: 119
Elements: 128, Allocations: 7, Moved: 246
Elements: 256, Allocations: 8, Moved: 501
Elements: 512, Allocations: 9, Moved: 1012
Elements: 1024, Allocations: 9, Moved: 1012
Elements: 2048, Allocations: 9, Moved: 1012
Elements: 4096, Allocations: 9, Moved: 1012
Elements: 8192, Allocations: 9, Moved: 1012
Elements: 16384, Allocations: 9, Moved: 1012
Elements: 32768, Allocations: 9, Moved: 1012
Elements: 65536, Allocations: 9, Moved: 1012
Elements: 131072, Allocations: 10, Moved: 28655
Elements: 262144, Allocations: 9, Moved: 1012
Elements: 524288, Allocations: 12, Moved: 435173
Elements: 1048576, Allocations: 13, Moved: 1431520
Elements: 2097152, Allocations: 11, Moved: 1993706
Elements: 4194304, Allocations: 13, Moved: 5877728
Elements: 8388608, Allocations: 14, Moved: 14838747
Elements: 16777216, Allocations: 12, Moved: 30438373
Elements: 33554432, Allocations: 12, Moved: 59881445
Elements: 67108864, Allocations: 12, Moved: 109627365

Ali