Array append performance

[bearophile]

Lionello Lunesu:
>However, if you were to append to two different arrays in a similar loop, the performance would be terrible, since each array would overwrite the cache with its own ptr/size, resulting in the slow O(m+n) for each capacity look-up.<

Yes, there's something that deserves some improvements, probably at various levels. I have modified the benchmarks in the way you have explained (see below), with n = 4 millions the running time of the C++ version is barely testable (0.04 s), the D version takes 32.2 s (I have had not enough patience to see it finish with n = 10 millions).

Bye,
bearophile

------------------
C++:

#include "stdio.h"
#include <vector>

using namespace std;

int main(int argc, char **argv) {
    int n = argc >= 2 ? atoi(argv[1]) : 1000;

    vector<int> a1;
    a1.reserve(n);
    vector<int> a2;
    a2.reserve(n);
    for (int i = 0; i < n; ++i) {
        a1.push_back(i);
        a2.push_back(i);
    }

    printf("%d %d\n", a1[n - 1], a2[n - 1]);
    return 0;
}

------------------
C++:

import std.conv: toInt;
import std.gc: malloc, hasNoPointers;

int main(string[] args) {
    int n = args.length >= 2 ? toInt(args[1]) : 1000;

    int* aux_ptr1 = cast(int*)malloc(n * int.sizeof);
    hasNoPointers(aux_ptr1);
    int[] a1 = aux_ptr1[0 .. 0];

    int* aux_ptr2 = cast(int*)malloc(n * int.sizeof);
    hasNoPointers(aux_ptr2);
    int[] a2 = aux_ptr2[0 .. 0];

    for (int i; i < n; i++) {
        a1 ~= i;
        a2 ~= i;
    }

    printf("%d %d\n", a1[n - 1], a2[n - 1]);
    return 0;
}