Benchmark realloc growth strategies

plot.R

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

data <- read.csv('capacities.csv')
data <- ddply(data, .(growth_factor), mutate, step = seq_along(capacity))
data$growth_factor <- factor(data$growth_factor)

p <- ggplot(data, aes(x=step, y=capacity, color=growth_factor)) + geom_step() + geom_point(size = 0.5)
ggsave("capacity_steps.png", p)

data <- read.csv('realloc_times.csv')
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)

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)
    {
        ptr = realloc.reserve(ptr, len + 1);
        ptr[len++] = t;
    }

    ~this()
    {
        free(ptr);
    }

    @disable this(this);

    T* ptr;
    size_t len;
    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);
        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);
        }
        if (print) writeln(num * 1.0 / 10, ",", (cast(Duration) sw.peek).total!"usecs");
    }
}

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