Benchmark realloc growth strategies

plot.R

library(ggplot2)
library(plyr)
library(dplyr)

data <- read.csv('realloc_bench.csv')[ ,c('growth_factor', 'time_in_us')]
data$growth_factor <- factor(data$growth_factor)
p <- ggplot(data, aes(x=growth_factor, y=time_in_us, fill=growth_factor)) + geom_boxplot()
ggsave("grow_timings.png", p)

data <- read.csv('realloc_bench.csv')[ ,c('growth_factor', 'reloc_ratio')]
data$growth_factor <- factor(data$growth_factor)
p <- ggplot(data, aes(x=growth_factor, y=reloc_ratio, fill=growth_factor)) + geom_boxplot()
ggsave("grow_relocr.png", p)

data <- read.csv('realloc_bench.csv')[ ,c('growth_factor', 'total_reloc')]
data$growth_factor <- factor(data$growth_factor)
p <- ggplot(data, aes(x=growth_factor, y=total_reloc, fill=growth_factor)) + geom_boxplot()
ggsave("grow_treloc.png", p)

realloc_bench.d

import core.checkedint : mulu;
import core.stdc.stdlib;
import std.datetime : AutoStart, Duration, StopWatch;
import std.meta;
import std.numeric : gcd;
import std.random;
import std.stdio;

struct Array(T, alias ReallocPolicy)
{
    void push(T t)
    {
        auto oldptr = ptr;
        ptr = realloc.reserve(ptr, len + 1);
        if (ptr != oldptr)
            relocs += len;
        ptr[len++] = t;
    }

    ~this()
    {
        free(ptr);
    }

    @disable this(this);

    T* ptr;
    size_t len;
    size_t relocs;
    ReallocPolicy!T realloc;
}


template ExpGrowth(size_t ExpNum, size_t ExpDen) if (ExpNum > ExpDen)
{
    enum Div = gcd(ExpNum, ExpDen);
    enum Num = ExpNum / Div;
    enum Den = ExpDen / Div;

    struct ExpGrowth(T)
    {
        T* reserve(T* ptr, size_t nlen)
        {
            return nlen > cap ? grow(ptr, nlen) : ptr;
        }

    private:
        T* grow(T* ptr, size_t nlen)
        {
            bool overflow;
            cap = mulu(cap, Num / Den, overflow) + mulu(cap, Num % Den, overflow) / Den;
            if (overflow)
                assert(0, "capacity computation overflowed");
            if (cap < nlen)
                cap = nlen;
            cap += -cap & 15;
            return cast(T*) realloc(ptr, cap * T.sizeof);
        }

        size_t cap;
    }
}

struct ReallocInternalGrowth(T)
{
    T* reserve(T* ptr, size_t nlen)
    {
        bool overflow;
        immutable sz = mulu(nlen, T.sizeof, overflow);
        if (overflow)
            assert(0, "capacity computation overflowed");
        return cast(T*) realloc(ptr, sz);
    }
}

struct Dummy
{
    ubyte[32] payload;
}

void runLoop(bool print)
{
    foreach (num; AliasSeq!(11, 12, 13, 14, 15, 16, 17, 18, 19, 20))
    {
        auto rng = Random(1234);
        auto sw = StopWatch(AutoStart.yes);
        double reloc_ratio = 0.0;
        ulong total_reloc;
version(all)
{
        foreach (i; 0 .. 8)
        {
            immutable N = uniform(1024, 8 *1024 * 1024, rng);
            Array!(Dummy, ExpGrowth!(num, 10)) ary;
            foreach (j; 0 .. N)
                ary.push(Dummy.init);
            total_reloc += ary.relocs;
            reloc_ratio += ary.relocs / double(N);
        }
        reloc_ratio /= 8;
}
else
{
        foreach (i; 0 .. 1_000)
        {
            immutable N = uniform(0, 64 * 1024, rng);
            Array!(Dummy, ExpGrowth!(num, 10)) ary;
            foreach (j; 0 .. N)
                ary.push(Dummy.init);
            total_reloc += ary.relocs;
            reloc_ratio += ary.relocs / double(N);
        }
        reloc_ratio /= 1_000;
}
        if (print)
            writeln(num * 1.0 / 10, ",", (cast(Duration) sw.peek).total!"usecs",
                    ",", reloc_ratio,",", total_reloc);
    }
}

void main()
{
    writeln("growth_factor,time_in_us,reloc_ratio,total_reloc");
    runLoop(false); // warmup
    foreach (_; 0 .. 16)
        runLoop(true);
}