Changeset f728971 for doc/theses/aaron_moss_PhD/phd/experiments.tex

Timestamp:

Feb 20, 2019, 2:00:37 PM (7 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, stuck-waitfor-destruct

Children:

a2971cc

Parents:

95c0ebe (diff), 7e9fa47 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'aaron-thesis' of plg.uwaterloo.ca:software/cfa/cfa-cc into aaron-thesis

File:

• doc/theses/aaron_moss_PhD/phd/experiments.tex (modified) (4 diffs)

doc/theses/aaron_moss_PhD/phd/experiments.tex

@@ -68 +68 @@
 \TODO{test performance; shouldn't be too hard to change \texttt{resolveAssertions} to use unification}
 
-\section{Prototype Experiments}
+\section{Prototype Experiments} \label{proto-exp-sec}
 
 The primary performance experiments for this thesis were conducted using the resolver prototype on problem instances generated from actual \CFA{} code using the method described in Section~\ref{rp-features-sec}. 
@@ -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}
 
-\section{\CFA{} Results}
+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. 
+The data below indicates that number of assertions necessary to resolve has the greatest effect on runtime, as seen in 
+Figure~\ref{per-prob-assns-fig}. 
+However, since the number of assertions required is only known once resolution is finished, the most-promising pre-resolution metric of difficulty is the nesting depth of the expression; as seen in Figure~\ref{per-prob-depth-fig}, expressions of depth $> 10$ in this dataset are uniformly difficult. 
+Figure~\ref{per-prob-subs-fig} presents a similar pattern for number of subexpressions, though given that the expensive tail of problem instances occurs at approximately twice the depth values, it is reasonable to believe that the difficult expressions in question are deeply-nested invocations of binary functions rather than wider but shallowly-nested expressions.
+
+% TODO statistics to tease out difficulty? Is ANOVA the right keyword?
+% TODO maybe metrics to sum number of poly-overloads invoked
+
+\begin{figure}
+\centering
+\input{per-prob-assns}
+\caption[Top-level expression resolution time by number of assertions resolved.]{Top-level expression resolution time by number of assertions resolved. Note log scales on both axes.} \label{per-prob-assns-fig}
+\end{figure}
+
+\begin{figure}
+\centering
+\input{per-prob-depth}
+\caption[Top-level expression resolution time by maximum nesting depth of expression.]{Top-level expression resolution time by maximum nesting depth of expression. Note log scales on both axes.} \label{per-prob-depth-fig}
+\end{figure}
+
+\begin{figure}
+\centering
+\input{per-prob-subs}
+\caption[Top-level expression resolution time by number of subexpressions.]{Top-level expression resolution time by number of subexpressions. Note log scales on both axes.} \label{per-prob-subs-fig}
+\end{figure}
+        
+
+\section{\CFA{} Results} \label{cfa-results-sec}
+
+I have integrated most of the algorithmic techniques discussed in this chapter into \CFACC{}. 
+This integration took place over a period of months while \CFACC{} was under active development on a number of other fronts, so it is not possible to completely isolate the effects of the algorithmic changes, but I have generated some data. 
+To generate this data, representative commits from the \texttt{git} history of the project were checked out and compiled, then run on the same machine used for the resolver prototype experiments discussed in Section~\ref{proto-exp-sec}. 
+To negate the effects of changes to the \CFA{} standard library on the timing results, 55 test files from the test suite of the oldest \CFA{} variant were compiled with the \texttt{-E} flag to inline their library dependencies, and these inlined files were used to test the remaining \CFACC{} versions. 
+
+I performed two rounds of modification to \CFACC{}; the first round moved from Bilson's original combined-bottom-up algorithm to an un-combined bottom-up algorithm, denoted \textsc{cfa-co} and \textsc{cfa-bu}, respectively. 
+A top-down algorithm was not attempted in \CFACC{} due to its poor performance in the prototype.
+The second round of modifications addressed assertion satisfaction, taking Bilson's original \textsc{cfa-imm} algorithm, and iteratively modifying it, first to use the deferred approach \textsc{cfa-def}, then caching those results in the \text{cfa-dca} algorithm. 
+The new environment data structures discussed in Section~\ref{proto-exp-sec} have not been successfully merged into \CFACC{} due to their dependencies on the garbage-collection framework in the prototype; I spent several months modifiying \CFACC{} to use similar garbage collection, but due to \CFACC{} not being designed to use such memory management the performance of the modified compiler was non-viable. 
+It is possible that the persistent union-find environment could be modified to use a reference-counted pointer internally without changing the entire memory-management framework of \CFACC{}, but such an attempt is left to future work.
+
+As can be seen in Figures~\ref{cfa-time-fig} and~\ref{cfa-mem-fig}, which show the time and peak memory results for these five versions of \CFACC{} on the same test suite, assertion resolution dominates total resolution cost, with the \textsc{cfa-def} and \textsc{cfa-dca} variants running consistently faster than the others on more expensive test cases. 
+The results from \CFACC{} do not exactly mirror those from the prototype; I conjecture this is mostly due to the different memory-management schemes and sorts of data required to run type unification and assertion satisfaction calculations, as \CFACC{} performance has proven to be particularly sensitive to the amount of heap allocation performed. 
+This data also shows a noticable regression in compiler performance in the eleven months between \textsc{cfa-bu} and \textsc{cfa-imm}; this regression is not due to expression resolution, as no integration work happened in this time, but I am unable to ascertain its actual cause.
+It should also be noted with regard to the peak memory results in Figure~\ref{cfa-mem-fig} that the peak memory usage does not always occur during the resolution phase of the compiler. 
+
+\begin{figure}
+\centering
+\input{cfa-time}
+\caption[\CFACC{} runtime against \textsc{cfa-co} baseline.]{\CFACC{} runtime against \textsc{cfa-co} baseline. Note log scales on both axes.} \label{cfa-time-fig}
+\end{figure}
+
+\begin{figure}
+\centering
+\input{cfa-mem}
+\caption[\CFACC{} peak memory usage against \textsc{cfa-co} baseline runtime.]{\CFACC{} peak memory usage against \textsc{cfa-co} baseline runtime. Note log scales on both axes.} \label{cfa-mem-fig}
+\end{figure}
 
 % use Jenkins daily build logs to rebuild speedup graph with more data
@@ -167 +239 @@
 
 % look back at Resolution Algorithms section for threads to tie up "does the algorithm look like this?"
+
+\section{Conclusion}
+
+As can be seen from the prototype results, per-expression benchmarks, and \CFACC{}, the dominant factor in the cost of \CFA{} expression resolution is assertion satisfaction. 
+Reducing the number of total number of assertion satisfaction problems solved, as in the deferred satisfaction algorithm, is consistently effective at reducing runtime, and caching results of these satisfaction problems has shown promise in the prototype system. 
+The results presented here also demonstrate that a bottom-up approach to expression resolution is superior to top-down, settling an open question from Baker~\cite{Baker82}.
+The persistent union-find type environment introduced in Chapter~\ref{env-chap} has also been demonstrated to be a modest performance improvement on the na\"{\i}ve approach.
+
+Given the consistently strong performance of the \textsc{bu-dca-imm} and \textsc{bu-dca-per} variants of the resolver prototype, the results in this chapter demonstrate that it is possible to develop a \CFA{} compiler with acceptable runtime performance for widespread use, an important and previously unaddressed consideration for the practical viability of the language. 
+However, the less-marked improvement in Section~\ref{cfa-results-sec} from retrofitting these algorithmic changes onto the existing compiler leave the actual development of a performant \CFA{} compiler to future work. 
+Characterization and elimination of the performance deficits in the existing \CFACC{} has proven difficult, though runtime is generally dominated by the expression resolution phase; as such, building a new \CFA{} compiler based on the resolver prototype contributed by this work may prove to be an effective strategy.