Skip to content

Instantly share code, notes, and snippets.

@MartinNowak
Last active September 26, 2017 05:03
Show Gist options
  • Save MartinNowak/6f0bb8fe04410d12fdfa7ac8f7646563 to your computer and use it in GitHub Desktop.
Save MartinNowak/6f0bb8fe04410d12fdfa7ac8f7646563 to your computer and use it in GitHub Desktop.
Benchmark realloc growth strategies
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)
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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment