--- /dev/null
+*.d
+*.o
+/REF.*
+/massif.*
+/time.*
+/chain.c++-*
+/chain.libavl-*
+/chain.qptrie-*
+/chain.sgt-*
+/chain.xyla-*
--- /dev/null
+/usr/share/dict/british-english-huge
\ No newline at end of file
--- /dev/null
+/usr/share/dict/british-english-insane
\ No newline at end of file
--- /dev/null
+/usr/share/dict/british-english-large
\ No newline at end of file
--- /dev/null
+/usr/share/dict/british-english
\ No newline at end of file
--- /dev/null
+/usr/share/dict/british-english-small
\ No newline at end of file
--- /dev/null
+#! /usr/bin/perl -w
+
+use autodie;
+use strict;
+
+our %MAP =
+ ("c++-map" => 'GNU \textsf{libstdc++} \textsf{std::map}',
+ "c++-uomap" => 'GNU \textsf{libstdc++} \textsf{std::unordered\_map}',
+ "golang" => 'Golang \textsf{map}',
+ "libavl-avl" => 'GNU \textsf{libavl} plain AVL trees',
+ "libavl-pavl" => 'GNU \textsf{libavl} AVL trees, parent pointers',
+ "libavl-rtavl" => 'GNU \textsf{libavl} AVL trees, right threaded',
+ "libavl-tavl" => 'GNU \textsf{libavl} AVL trees, threaded',
+ "libavl-rb" => 'GNU \textsf{libavl} plain red-black trees',
+ "libavl-prb" => 'GNU \textsf{libavl} red-black trees, parent pointers',
+ "libavl-rtrb" => 'GNU \textsf{libavl} red-black trees, right threaded',
+ "libavl-trb" => 'GNU \textsf{libavl} red-black trees, threaded',
+ "lisp-ccl" => 'Common Lisp (Clozure CL)',
+ "lisp-clisp" => 'Common Lisp (GNU CLisp)',
+ "lisp-cmucl" => 'Common Lisp (CMU CL)',
+ "lisp-ecl" => 'Common Lisp (ECL)',
+ "lisp-sbcl" => 'Common Lisp (SBCL)',
+ "mLib-sym" => 'mLib, \textsf{sym} hash table',
+ "perl" => 'Perl hash',
+ "python" => 'Python \textsf{dict}',
+ "qptrie-qp-fanf" => 'Four-bit QP-trie, recursive \textsf{Tnextl}',
+ "qptrie-qp-mdw" => 'Four-bit QP-trie, iterative \textsf{Tnextl}',
+ "qptrie-qp-list" => 'Four-bit QP-trie, linked list',
+ "qptrie-fn-fanf" => 'Five-bit QP-trie, recursive \textsf{Tnextl}',
+ "qptrie-fn-mdw" => 'Five-bit QP-trie, iterative \textsf{Tnextl}',
+ "qptrie-fn-list" => 'Five-bit QP-trie, linked list',
+ "rust-btree" => 'Rust \textsf{std::collections::BTreeMap}',
+ "rust-hash" => 'Rust \textsf{std::collections::HashMap}',
+ "sgt-tree234" => "Simon Tatham's 2-3-4 tree",
+ "xyla-avl" => 'Xyla AVL tree',
+ "xyla-rb" => 'Xyla red-black tree',
+ "xyla-splay" => 'Xyla splay tree',
+ "xyla-treap" => 'Xyla treap');
+
+our @STAT = ("lower whisker",
+ "lower quartile",
+ "median",
+ "average",
+ "upper quartile",
+ "upper whisker");
+
+my @X;
+while (<>) {
+ my ($impl, $data, $stat) = m{ ^ (\S+)
+ ((?: \s+ [0-9.]+)*) \s* \;
+ ((?: \s+ [0-9.]+){6}) \s* $ }x
+ or die "bad line";
+ my @data = map { $_ + 0.0 } split ' ', $data;
+ my @stat = map { $_ + 0.0 } split ' ', $stat;
+ my ($wlo, undef, undef, undef, undef, $whi) = @stat;
+ my @out = grep { $_ < $wlo || $_ > $whi } @data;
+ push @X, [$impl, \@stat, \@out];
+}
+
+print "\\begin{axis}\n";
+printf " [ytick = {%s},\n", join(", ", 1 .. @X);
+print " yticklabels =\n";
+for (my $i = 0; $i < @X; $i++) {
+ my $x = $X[$i];
+ printf " %s{%s}%s\n",
+ $i ? " " : "{",
+ "\\textsf{$x->[0]}",
+ $i == @X - 1 ? "}]" : ",";
+}
+for my $x (@X) {
+ print " \\addplot+\n";
+ print " [boxplot prepared =\n";
+ my ($impl, $stat, $out) = $x->@*;
+ STAT: for (my $j = 0; $j < @STAT; $j++) {
+ next STAT unless defined $stat->[$j];
+ printf " %s%s = %.3f%s\n",
+ $j ? " " : "{",
+ $STAT[$j], $stat->[$j],
+ $j == @STAT - 1 ? "}]" : ",";
+ }
+ printf " coordinates {%s};\n",
+ join(" ", map { sprintf "(0, %.3f)", $_ } $out->@*);
+}
+print "\\end{axis}\n";
--- /dev/null
+#! /usr/bin/python3
+
+import bisect as BS
+import curses as CU
+import optparse as OP
+import os as OS
+import random as RND
+import resource as RSC
+import subprocess as SUB
+import sys as SYS
+
+op = OP.OptionParser\
+ (usage = "%prog [-t] [-d FILE] [-j JOBS] [-n SAMPLES] [-r REF] VAR ...")
+op.disable_interspersed_args()
+for short, long, kw in \
+ [("-d", "--dictionary",
+ dict(type = "string", metavar = "DICT",
+ dest = "dict", default = "/usr/share/dict/words",
+ help = "word list to process")),
+ ("-j", "--jobs",
+ dict(type = "int", metavar = "JOBS",
+ dest = "njobs", default = 1,
+ help = "number of jobs to run concurrently")),
+ ("-n", "--samples",
+ dict(type = "int", metavar = "SAMPLES",
+ dest = "nsamples", default = 5,
+ help = "number of samples for each variant")),
+ ("-r", "--reference",
+ dict(type = "string", metavar = "REF",
+ dest = "ref", default = None,
+ help = "reference output data expected")),
+ ("-t", "--terminal",
+ dict(action = "store_true", dest = "terminal", default = None,
+ help = "show progress display"))]:
+ op.add_option(short, long, **kw)
+OPTS, ARGS = op.parse_args()
+
+REF = OPTS.ref
+if REF is None:
+ REF = "REF.%s" % OS.path.basename(OPTS.dict)
+ if not OS.path.exists(REF): REF = None
+
+IDLE = 0
+LIVE = 1
+DONE = 2
+
+class BasicVariant (object):
+
+ def __init__(me, name, row):
+ me.name = name
+ me.samples = []
+ me.row = row
+ me._prog = "./chain.%s" % name
+ me.state = IDLE
+
+ @property
+ def n(me):
+ return len(me.samples)
+
+ def start(me, out):
+ SYS.stdin.close()
+ fd = OS.open(OPTS.dict, OS.O_RDONLY)
+ if fd != 0: OS.dup2(fd, 0); OS.close(fd)
+ SYS.stdout.close()
+ fd = OS.open(out, OS.O_WRONLY | OS.O_CREAT | OS.O_TRUNC, 0o666)
+ if fd != 1: OS.dup2(fd, 1); OS.close(fd)
+ OS.execv(me._prog, [me._prog])
+
+ def end(me, time):
+ me.samples.append(time)
+ return time
+
+class LispVariant (BasicVariant):
+ def __init__(me, name, *args, **kw):
+ super(LispVariant, me).__init__(name, *args, **kw)
+ me._time = "time.%s" % name
+ me._lisp = name[5:]
+ me._prog = "chain.lisp"
+
+ def start(me, out):
+ SYS.stdout.close()
+ fd = OS.open(out, OS.O_WRONLY | OS.O_CREAT | OS.O_TRUNC, 0o666)
+ if fd != 1: OS.dup2(fd, 1); OS.close(fd)
+ OS.execvp("runlisp", ["runlisp", "-L%s" % me._lisp,
+ me._prog, "-T%s" % me._time, OPTS.dict])
+
+ def end(me, time):
+ #with open(me._time) as f: time = 1000*float(f.read())
+ OS.unlink(me._time)
+ me.samples.append(time)
+ return time
+
+def strwait(st):
+ if OS.WIFEXITED(st): return "rc = %d" % OS.WEXITSTATUS(st)
+ elif OS.WIFSIGNALED(st): return "signal = %d" % OS.WTERMSIG(st)
+ else: return "?st = %d" % st
+
+class State (object):
+
+ def __init__(me):
+ me.vars = []
+ me.idle = []
+ me.done = []
+ me.live = {}
+ me.bad = False
+
+ me._nextrow = 0
+ me._dpy = None
+
+ def _setdpy(me, dpy):
+ me._dpy = dpy
+
+ def addvar(me, var):
+ if arg.startswith("lisp-"): var = LispVariant(arg, me._nextrow)
+ else: var = BasicVariant(arg, me._nextrow)
+ me.vars.append(var); me.idle.append(var); me._nextrow += 1
+
+ def cycle(me):
+ if me.idle and not me.bad and len(me.live) < OPTS.njobs:
+ n = len(me.idle)
+ k = RND.randrange(n); pick = me.idle[k]; assert pick.state == IDLE
+ me.idle[k] = me.idle[n - 1]; me.idle.pop()
+ kid = OS.fork()
+ if not kid: pick.start("chain.%s.out" % pick.name)
+ #me._dpy.msg(";; start %s\n" % pick.name)
+ me.live[kid] = pick; pick.state = LIVE
+ me._dpy.paint_var(pick)
+ return True
+ elif me.live:
+ kid, st, ru = OS.wait3(0)
+ try: var = me.live.pop(kid)
+ except KeyError:
+ me._dpy.msg("ignoring unexpected child %d (%s)" %
+ (kid, strwait(st)))
+ return True
+ assert var.state == LIVE
+ if not (OS.WIFEXITED(st) and OS.WEXITSTATUS(st) == 0):
+ me._dpy.msg("chain.%s failed (%s)" % (var.name, strwait(st)))
+ me.bad = True
+ return True
+ out = "chain.%s.out" % var.name
+ if REF is not None:
+ if SUB.call(["./chkref", out, REF]):
+ me._dpy.msg("chain.%s produced incorrect output" % var.name)
+ me.bad = True
+ return True
+ OS.unlink(out)
+ time = var.end(1000*(ru.ru_utime + ru.ru_stime))
+ #me._dpy.msg(";; end %s, time = %.3f s" % (var.name, time))
+ if var.n < OPTS.nsamples:
+ me.idle.append(var); var.state = IDLE
+ else:
+ me.done.append(var); var.state = DONE
+ #me._dpy.msg(";; done %s\n" % var.name)
+ me._dpy.paint_var(var)
+ return True
+ else:
+ return False
+
+if OPTS.terminal or SYS.stdout.isatty():
+
+ class Display (object):
+
+ def __init__(me, state):
+ me._st = state
+ me._st._setdpy(me)
+ namewd = 16
+ for var in me._st.vars:
+ if len(var.name) >= namewd: namewd = len(var.name) + 1
+ me._a_idle = CU.A_NORMAL
+ me._a_live = CU.A_BOLD
+ me._namewd = namewd
+ me._msgs = []
+
+ def __enter__(me):
+
+ if not SYS.stdout.isatty():
+ ttyfd = OS.open("/dev/tty", OS.O_RDWR)
+ SYS.stdout = OS.fdopen(OS.dup(1), "w")
+ OS.dup2(ttyfd, 1)
+ OS.close(ttyfd)
+
+ me._scr = CU.initscr()
+ me._resize()
+ CU.start_color()
+ CU.use_default_colors()
+ if CU.COLORS and CU.COLOR_PAIRS >= 3:
+ CU.init_pair(1, CU.COLOR_GREEN, -1)
+ me._a_done = CU.color_pair(1)
+ CU.init_pair(2, CU.COLOR_BLACK, CU.COLOR_GREEN)
+ CU.init_pair(3, CU.COLOR_BLACK, CU.COLOR_YELLOW)
+ me._a_bar_left = CU.color_pair(2)
+ me._a_bar_right = CU.color_pair(3)
+ else:
+ me._a_live = CU.A_DIM
+ me._a_bar_left = CU.A_REVERSE
+ me._a_bar_right = None
+ me._msgrow = min(len(me._st.vars) + 1, me._ht - 1)
+ me._nmsgs = me._ht - me._msgrow
+ me._scr.setscrreg(me._msgrow, me._ht - 1)
+ me._scr.scrollok(True)
+ me._repaint()
+
+ def __exit__(me, exval, exty, tb):
+ CU.endwin()
+ for m in me._msgs: SYS.stderr.write(m + "\n")
+
+ def _resize(me):
+ me._ht, me._wd = me._scr.getmaxyx()
+ barwd = me._wd - me._namewd
+ if OPTS.nsamples <= barwd: me._barsc = 1
+ else: me._barsc = float(barwd)/OPTS.nsamples
+
+ def paint_var(me, var, refresh = True):
+ if var.row >= me._ht - 2: return
+ rbar = int(me._barsc*OPTS.nsamples + 0.5)
+ if var.state == LIVE: attr = me._a_live
+ elif var.state == DONE: attr = me._a_done
+ else: attr = me._a_idle
+ me._scr.addstr(var.row, 0, var.name, attr)
+ mbar = int(me._barsc*len(var.samples))
+ me._scr.attrset(me._a_bar_left)
+ me._scr.hline(var.row, me._namewd, " ", mbar)
+ if me._a_bar_right is not None:
+ me._scr.attrset(me._a_bar_right)
+ me._scr.hline(var.row, me._namewd + mbar, " ", rbar - mbar)
+ me._scr.move(var.row, me._namewd + rbar)
+ else:
+ me._scr.move(var.row, me._namewd + mbar)
+ me._scr.attrset(0)
+ if var.samples:
+ avg = "%.3f ms" % (sum(var.samples)/len(var.samples))
+ if me._wd - (me._namewd + rbar) > len(avg):
+ me._scr.addstr(var.row, me._namewd + rbar + 1, avg)
+ me._scr.clrtoeol()
+ if refresh: me._scr.refresh()
+
+ def msg(me, msg):
+ n = len(me._msgs)
+ if n >= me._nmsgs:
+ me._scr.scroll(1)
+ me._scr.addstr(min(me._msgrow + n, me._ht - 1), 0, msg)
+ me._msgs.append(msg)
+ me._scr.refresh()
+
+ def _repaint(me):
+ me._scr.erase()
+ for var in me._st.vars: me.paint_var(var, refresh = False)
+ n = len(me._msgs); y = me._msgrow
+ for i in range(max(0, n - me._nmsgs), n):
+ me._scr.addstr(y, 0, me._msg[i]); y += 1
+ me._scr.refresh()
+
+else:
+
+ class Display (object):
+
+ def __init__(me, state):
+ me._st = state
+ me._st._setdpy(me)
+
+ def __enter__(me):
+ pass
+ def __exit__(me, exval, exty, tb):
+ pass
+
+ def paint_var(me, var):
+ if var.state == IDLE:
+ SYS.stderr.write(";; end %s, time = %.3f ms\n" %
+ (var.name, var.samples[-1]))
+ elif var.state == LIVE:
+ SYS.stderr.write(";; start %s\n" % var.name)
+ elif var.state == DONE:
+ SYS.stderr.write(";; %s all done\n" % var.name)
+
+ def msg(me, msg):
+ SYS.stderr.write("%s\n" % msg)
+
+RND.seed()
+STATE = State()
+for arg in ARGS: STATE.addvar(arg)
+with Display(STATE):
+ while STATE.cycle(): pass
+if STATE.bad: SYS.exit(2)
+
+def quartile(i, x):
+ n = len(x)
+ k = i*n
+ j = k//4
+ if not k%4: return x[j]
+ else: return (x[j] + x[j + 1])/2
+
+def stats(x):
+ q1, mid, q3 = quartile(1, x), quartile(2, x), quartile(3, x)
+ iqr = q3 - q1
+ locut = BS.bisect_left(x, q1 - 1.5*iqr); lo = x[locut]
+ hicut = BS.bisect_right(x, q3 + 1.5*iqr); hi = x[hicut - 1]
+ avg = sum(x)/len(x)
+ return lo, q1, mid, avg, q3, hi
+
+done = STATE.vars
+done.sort(key = lambda var: var.name)
+n = OPTS.nsamples - 1
+for var in done:
+ x = [xi for xi in var.samples]; x.sort()
+ lo, q1, mid, avg, q3, hi = stats(x)
+ print("%-16s %s; %s" %
+ (var.name,
+ " ".join("%.3f" % xi for xi in var.samples),
+ " ".join("%.3f" % xi for xi in [lo, q1, mid, avg, q3, hi])))
--- /dev/null
+\documentclass{strayman}
+
+\usepackage[T1]{fontenc}
+\usepackage[palatino, helvetica, courier, maths = palatino]{mdwfonts}
+\usepackage{mdwtab}
+\usepackage{dcolumn}
+
+\usepackage{tikz}
+\usepackage{pgfplots}
+ \usepgfplotslibrary{statistics}
+
+\pgfplotsset{compat = 1.16, width = 0.8\textwidth}
+
+\errorcontextlines=\maxdimen
+
+\begin{document}
+
+%%\begin{figure}
+%% \centering
+%% \begin{tikzpicture}
+%% \pgfplotsset
+%% {xmin = 0, y dir = reverse, height = 160mm,
+%% typeset ticklabels with strut,
+%% enlarge y limits = 0.02,
+%% cycle list = {},
+%% \input{t.tex}
+%% \end{tikzpicture}
+%%\end{figure}
+
+\begin{figure}
+ \centering
+ \begin{tikzpicture}
+ \begin{axis}
+ [xlabel = Implementation,
+ xtick = data,
+ x tick label style =
+ { rotate = 60, anchor = north east, font = \sffamily },
+ enlarge x limits = 0.02,
+ ylabel = Time (ns/word),
+ ymin = 0, yticklabel style = {/pgf/number format/.cd, 1000 sep = \,},
+ legend cell align = left,
+ width = 0.95 \textwidth,
+ height = 0.60 \textheight,
+ symbolic x coords =
+ {c++-map, c++-uomap,
+ golang,
+ libavl-avl, libavl-pavl, libavl-rtavl, libavl-tavl,
+ libavl-rb, libavl-prb, libavl-rtrb, libavl-trb,
+ %lisp-ccl, lisp-clisp, lisp-cmucl, lisp-ecl,
+ lisp-sbcl,
+ mLib-sym,
+ %perl,python,%
+ qptrie-qp-fanf, qptrie-qp-mdw, qptrie-qp-list,
+ qptrie-fn-fanf, qptrie-fn-mdw, qptrie-fn-list,
+ rust-btree, rust-hash,
+ sgt-tree234,
+ xyla-avl, xyla-rb, xyla-splay, xyla-treap}]
+ \addplot+[sharp plot]
+ table[x = impl, y = small] from {summary.dat};
+ \addlegendentry{\textsf{small}}
+ \addplot+[sharp plot]
+ table[x = impl, y = medium] from {summary.dat};
+ \addlegendentry{\textsf{medium}}
+ \addplot+[sharp plot]
+ table[x = impl, y = large] from {summary.dat};
+ \addlegendentry{\textsf{large}}
+ \addplot+[sharp plot]
+ table[x = impl, y = huge] from {summary.dat};
+ \addlegendentry{\textsf{huge}}
+ \addplot+[sharp plot]
+ table[x = impl, y = insane] from {summary.dat};
+ \addlegendentry{\textsf{insane}}
+ \end{axis}
+ \end{tikzpicture}
+
+ \caption{Performance of various associative mapping implementations}
+ \label{fig:perf}
+\end{figure}
+
+\begin{table}
+ \begin{tabular}[C]{llrr} \hlx*{hv}
+ \textbf{Dictionary}
+ & \textbf{Filename}
+ & \multicolumn{1}{c}{\textbf{Words}}
+ & \multicolumn{1}{c}{\textbf{Bytes}} \\ \hlx{vhv}
+ \textsf{small} & \texttt{british-english-small}
+ & 50\,792 & 465\,516 \\
+ \textsf{medium} & \texttt{british-english}
+ & 101\,921 & 968\,222 \\
+ \textsf{large} & \texttt{british-english-large}
+ & 166\,747 & 1\,635\,703 \\
+ \textsf{huge} & \texttt{british-english-huge}
+ & 344\,817 & 3\,532\,576 \\
+ \textsf{insane} & \texttt{british-english-insane}
+ & 654\,276 & 6\,875\,495 \\ \hlx*{vh}
+ \end{tabular}
+
+ \caption{Dictionaries used in this experieent}
+ \label{tab:dict}
+\end{table}
+
+\begin{table}
+ \input{sumtab.tex}
+ \caption{Performance of various associative mapping implementations.
+ Entries show times in nanoseconds per word, followed by ranking in
+ parentheses.}
+ \label{tab:perf}
+\end{table}
+
+\end{document}
--- /dev/null
+#! /bin/sh -e
+
+run_massif () {
+ out=$1; shift
+ valgrind --tool=massif --massif-out-file=$out \
+ --peak-inaccuracy=0 --pages-as-heap=yes \
+ "$@"
+}
+
+run_wordchain () {
+ out=$1 impl=$2 dict=$3
+
+ case $impl in
+ lisp-*)
+ run_massif $out runlisp -L${impl#lisp-} ./chain.lisp $dict
+ ;;
+ *)
+ run_massif $out ./chain.$impl <$dict
+ ;;
+ esac
+}
+
+make -s list | while read i; do
+ run_wordchain massif.$i.baseline $i /dev/null
+ for d in DICT.*; do
+ d=${d#DICT.}
+ run_wordchain massif.$i.$d $i DICT.$d
+ done
+done
--- /dev/null
+#! /usr/bin/perl -w
+
+use autodie;
+use strict;
+
+our %IMPL =
+ ("c++" => ["map", "uomap"],
+ "golang" => undef,
+ "libavl" => ["avl", "pavl", "rtavl", "tavl",
+ "rb", "prb", "rtrb", "trb"],
+ "lisp" => ["ccl", "clisp", "cmucl", "ecl", "sbcl"],
+ "mLib" => ["sym"],
+ "perl" => undef,
+ "python" => undef,
+ "qptrie" => ["qp-fanf", "qp-mdw", "qp-list",
+ "fn-fanf", "fn-mdw", "fn-list"],
+ "rust" => ["btree", "hash"],
+ "sgt" => ["tree234"],
+ "xyla" => ["avl", "rb", "splay", "treap"]);
+our @IMPL;
+for my $base (sort keys %IMPL) {
+ if (!defined $IMPL{$base}) { push @IMPL, $base; }
+ else { for my $var ($IMPL{$base}->@*) { push @IMPL, "$base-$var"; } }
+}
+
+our @DICT = ("small", "medium", "large", "huge", "insane");
+
+our %WC;
+our %BYTES;
+for my $dict (@DICT) {
+ open my $f, "<", "DICT.$dict";
+ my $wc = 0; my $bytes = 0;
+ while (<$f>) { chomp; $wc++; $bytes += length; }
+ $WC{$dict} = $wc; $BYTES{$dict} = $bytes;
+ close $f;
+}
+
+sub closeish ($$) {
+ my ($x, $y) = @_;
+
+ return abs($x - $y) < 1e-3;
+}
+
+our %DATA;
+our %SLOW;
+for my $dict (@DICT) {
+ open my $f, "<", "DATA.$dict";
+ my %seen = map { $_ => 0 } @IMPL;
+ my $wc = $WC{$dict};
+ while (<$f>) {
+ my ($impl, $data, $stat) = m{ ^ (\S+)
+ ((?: \s+ [0-9.]+)*) \s* \;
+ ((?: \s+ [0-9.]+){6}) \s* $ }x
+ or die "bad line";
+ my @data = sort { $a <=> $b } map { $_ + 0.0 } split ' ', $data;
+ my @stat = map { $_ + 0.0 } split ' ', $stat;
+ my $i = @data/2;
+ my $mid = @data%2 ? ($data[$i] + $data[$i + 1])/2 : $data[$i];
+ my $sum = 0; for my $x (@data) { $sum += $x; }
+ my $avg = $sum/@data;
+ closeish($mid, $stat[2]) && closeish($avg, $stat[3])
+ or die "stat miscalculation";
+ if ($seen{$impl}) { die "duplicate entry for `$impl'"; }
+ elsif (exists $seen{$impl}) { $seen{$impl} = 1; }
+ else { die "unknown implementation `$impl'" }
+ my $unit = 1000000*$mid/$wc;
+ if ($unit >= 1200) { $SLOW{$impl} = 1; }
+ push $DATA{$impl}->@*, $mid/$wc;
+ }
+ close $f;
+ for my $impl (@IMPL)
+ { die "missing implementation `$impl'" unless $seen{$impl}; }
+}
+
+{ open my $f, ">summary.dat";
+ printf $f "%-15s ", "impl";
+ for my $dict (@DICT) { printf $f " %7s", $dict }
+ print $f "\n";
+
+ IMPL: for my $impl (@IMPL) {
+ next IMPL if $SLOW{$impl};
+ printf $f "%-15s ", $impl;
+ for my $t ($DATA{$impl}->@*) { printf $f " %7.2f", 1e6*$t; }
+ print $f "\n";
+ }
+ close $f;
+}
+
+our %RANK;
+for (my $i = 0; $i < @DICT; $i++) {
+ my @pairs;
+ for my $impl (keys %DATA) { push @pairs, [$impl, $DATA{$impl}->[$i]]; }
+ my $k = 0;
+ for my $pair (sort { $a->[1] <=> $b->[1] } @pairs)
+ { push $RANK{$pair->[0]}->@*, ++$k; }
+}
+
+{ open my $f, ">sumtab.tex";
+ printf $f "\\begin{tabular}[C]{l*%d{r\@{ }r}} \\hlx*{hv}\n",
+ scalar @DICT;
+ print $f " \\textbf{Impl}\n";
+ for my $dict (@DICT) {
+ print $f " & \\multicolumn{2}{c}{\\textbf{\\textsf{$dict}}}\n";
+ }
+ print $f " \\\\\n";
+
+ sub row ($) {
+ my ($impl) = @_;
+ print $f " \\textsf{$impl}\n";
+ for (my $i = 0; $i < @DICT; $i++) {
+ printf $f " & %.0f & (%d)\n",
+ 1e6*$DATA{$impl}->[$i],
+ $RANK{$impl}->[$i];
+ }
+ print $f " \\\\\n";
+ }
+
+ for my $base (sort keys %IMPL) {
+ print $f " \\hlx{vhv}\n";
+ if (!defined $IMPL{$base}) { row $base; }
+ else { for my $var ($IMPL{$base}->@*) { row "$base-$var"; } }
+ }
+ print $f " \\hlx*{vh}\n";
+ print $f "\\end{tabular}\n";
+ close $f;
+}
+
+for my $dict (@DICT) {
+ printf "%-7s %d %d\n", $dict, $WC{$dict}, $BYTES{$dict};
+}
+
+IMPL: for my $impl (@IMPL) {
+ DICT: for my $dict (@DICT) {
+ -e "massif.$impl.$dict" or next IMPL;
+ my $peak_alloc; my $peak_waste;
+
+ open my $f, "<", "massif.$impl.$dict";
+ my $alloc; my $waste; my $snap = "unset";
+ while (<$f>) {
+ chomp;
+ if (/^snapshot=/) {
+ if ($snap eq "peak") { $peak_alloc = $alloc; $peak_waste = $waste; }
+ $alloc = $waste = $snap = undef;
+ } elsif (/^mem_heap_B=(\d+)$/) { $alloc = $1; }
+ elsif (/^mem_heap_extra_B=(\d+)$/) { $waste = $1; }
+ elsif (/^heap_tree=(\w+)$/) { $snap = $1; }
+ }
+ if ($snap eq "peak") { $peak_alloc = $alloc; $peak_waste = $waste; }
+ close $f;
+ defined $peak_alloc or next DICT;
+
+ printf "%-15s %-7s %.3f %.3f\n",
+ $impl, $dict,
+ ($peak_alloc - $BYTES{$dict})/$WC{$dict},
+ $peak_waste/$WC{$dict};
+ }
+}
~mdw / wordchain / commitdiff