Changeset 4c41b17 for doc/theses/aaron_moss_PhD

Timestamp:

Feb 15, 2019, 6:55:02 PM (6 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

060b12d

Parents:

7c6eb64

Message:

thesis: Add per-problem histogram

Location:

doc/theses/aaron_moss_PhD/phd

Files:

• Makefile (modified) (2 diffs)
• evaluation/data.xlsx (modified) (previous)
• evaluation/per-prob.gp (added)
• evaluation/per-prob.tsv (added)
• experiments.tex (modified) (2 diffs)
• resolution-heuristics.tex (modified) (1 diff)

doc/theses/aaron_moss_PhD/phd/Makefile

@@ -39 +39 @@
 generic-timing \
 tests-completed \
+per-prob-histo \
 }
 
@@ -69 +70 @@
         gnuplot -e BUILD="'${BUILD}/'" ${EVALDIR}/algo-summary.gp
 
+per-prob-histo.tex : per-prob.gp per-prob.tsv ${BUILD}
+        gnuplot -e BUILD="'${BUILD}/'" ${EVALDIR}/per-prob.gp
+
 ${BUILD}: 
         mkdir -p ${BUILD}

doc/theses/aaron_moss_PhD/phd/experiments.tex

@@ -98 +98 @@
 Terminal output was suppressed for all tests to avoid confounding factors in the timing results, and all tests were run three times in series, with the median result reported in all cases.
 The medians are representative data points; considering test cases that took at least 0.2~s to run, the average run was within 2\% of the reported median runtime, and no run diverged by more than 20\% of median runtime or 5.5~s. 
-The memory results are even more consistent, with no run exceeding 2\% difference from median in peak resident set size, and 93\% of tests not recording any difference within the 1~KB granularity of the measurement software.
+The memory results are even more consistent, with no run exceeding 2\% difference from median in peak resident set size, and 93\% of tests not recording any difference within the 1~KB granularity of the measurement software. 
+All tests were run on a machine with 128~GB of RAM and 64 cores running at 2.2~GHz.
 
 As a matter of experimental practicality, test runs which exceeded 8~GB of peak resident memory usage were excluded from the data set. 
@@ -156 +157 @@
 \section{Instance Difficulty}
 
+To characterize the difficulty of expression resolution problem instances, the test suites must be explored at a finer granuarity. 
+As discussed in Section~\ref{resn-analysis-sec}, a single top-level expression is the fundamental problem instance for resolution, yet the test inputs discussed above are composed of thousands of top-level expressions, like the actual source code they are derived from. 
+To pull out the effects of these individual problems, I instrumented the resolver prototype to time resolution for each expression, and also report some relevant properties of the expression. 
+This instrumented resolver was then run on a set of difficult test instances; to limit the data collection task, these runs were limited to the best-performing \textsc{bu-dca-per} algorithm and test inputs which that algorithm took more than 1~s to complete. 
+
+The 13 test inputs thus selected contain 20632 top-level expressions between them, which are separated into order-of-magnitude bins by runtime in Figure~\ref{per-prob-histo-fig}.
+As can be seen from this figure, overall runtime is dominated by a few particularly difficult problem instances --- the 60\% of expressions which resolve in under 0.1~ms collectively take less time to resolve than any of the 0.2\% of expressions which take at least 100~ms to resolve. 
+On the other hand, the 46 expressions in that 0.2\% take 38\% of the overall time in this difficult test suite, while the 201 expressions that take between 10 and 100~ms to resolve consume another 30\%. 
+
+\begin{figure}
+        \centering
+        \input{per-prob-histo}
+        \caption[Histogram of top-level expressions]{Histogram of top-level expression resolution runtime, binned by order-of-magnitude. The left series counts the expressions in each bin according to the left axis, while the right series reports the summed runtime of resolution for all expressions in that bin. Note that both y-axes are log-scaled.} \label{per-prob-histo-fig}
+\end{figure}
+
+Since the top centile of expression resolution instances requires approximately two-thirds of the resolver's time, optimizing the resolver for specific hard problem instances has proven to be an effective technique for reducing overall runtime. 
+\TODO{Discuss metrics of difficulty.}
+
 % TODO: look at overloads
 % TODO: histogram of hard cases

doc/theses/aaron_moss_PhD/phd/resolution-heuristics.tex

@@ -197 +197 @@
 
 To resolve the outermost !wrap!, the resolver must check that !pair(pair(int))! unifies with itself, but at three levels of nesting, !pair(pair(int))! is more complex than either !pair(T)! or !T!, the types in the declaration of !wrap!. 
-Accordingly, the cost of a single argument-parameter unification is $O(d)$, where !d! is the depth of the expression tree, and the cost of argument-parameter unification for a single candidate for a given function call expression is $O(pd)$, where $p$ is the number of parameters. 
+Accordingly, the cost of a single argument-parameter unification is $O(d)$, where $d$ is the depth of the expression tree, and the cost of argument-parameter unification for a single candidate for a given function call expression is $O(pd)$, where $p$ is the number of parameters. 
 
 Implicit conversions are also checked in argument-parameter matching, but the cost of checking for the existence of an implicit conversion is again proportional to the complexity of the type, $O(d)$.