From: Mark Wooding Date: Wed, 18 Sep 2024 18:57:55 +0000 (+0100) Subject: much stuff X-Git-Url: https://www.chiark.greenend.org.uk/ucgi/~mdw/git/wordchain/commitdiff_plain/ed71412555b7ef3b16544e33f21fbd521b21b9ae?ds=inline much stuff --- diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..51f1cd9 --- /dev/null +++ b/.gitignore @@ -0,0 +1,10 @@ +*.d +*.o +/REF.* +/massif.* +/time.* +/chain.c++-* +/chain.libavl-* +/chain.qptrie-* +/chain.sgt-* +/chain.xyla-* diff --git a/DICT.huge b/DICT.huge new file mode 120000 index 0000000..651259b --- /dev/null +++ b/DICT.huge @@ -0,0 +1 @@ +/usr/share/dict/british-english-huge \ No newline at end of file diff --git a/DICT.insane b/DICT.insane new file mode 120000 index 0000000..3db7864 --- /dev/null +++ b/DICT.insane @@ -0,0 +1 @@ +/usr/share/dict/british-english-insane \ No newline at end of file diff --git a/DICT.large b/DICT.large new file mode 120000 index 0000000..66f7d8b --- /dev/null +++ b/DICT.large @@ -0,0 +1 @@ +/usr/share/dict/british-english-large \ No newline at end of file diff --git a/DICT.medium b/DICT.medium new file mode 120000 index 0000000..fd66f18 --- /dev/null +++ b/DICT.medium @@ -0,0 +1 @@ +/usr/share/dict/british-english \ No newline at end of file diff --git a/DICT.small b/DICT.small new file mode 120000 index 0000000..7592c5f --- /dev/null +++ b/DICT.small @@ -0,0 +1 @@ +/usr/share/dict/british-english-small \ No newline at end of file diff --git a/format-data b/format-data new file mode 100755 index 0000000..327157b --- /dev/null +++ b/format-data @@ -0,0 +1,84 @@ +#! /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"; diff --git a/get-timing-data b/get-timing-data new file mode 100755 index 0000000..2b3d5b6 --- /dev/null +++ b/get-timing-data @@ -0,0 +1,310 @@ +#! /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]))) diff --git a/graphs.tex b/graphs.tex new file mode 100644 index 0000000..7ccf62f --- /dev/null +++ b/graphs.tex @@ -0,0 +1,110 @@ +\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} diff --git a/run-massif b/run-massif new file mode 100755 index 0000000..05ee019 --- /dev/null +++ b/run-massif @@ -0,0 +1,29 @@ +#! /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 diff --git a/summarize b/summarize new file mode 100755 index 0000000..b51a430 --- /dev/null +++ b/summarize @@ -0,0 +1,157 @@ +#! /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}; + } +}