Changeset 9e43aff for doc/theses/aaron_moss_PhD

Timestamp:

Feb 12, 2019, 10:40:29 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:

72b20c9

Parents:

0f78f3c7

Message:

thesis: introduce experimental results from prototype

Location:

doc/theses/aaron_moss_PhD/phd

Files:

• evaluation/data.xlsx (modified) (previous)
• experiments.tex (modified) (2 diffs)
• resolution-heuristics.tex (modified) (2 diffs)
• type-environment.tex (modified) (2 diffs)

doc/theses/aaron_moss_PhD/phd/experiments.tex

@@ -15 +15 @@
 Since at this juncture all development in \CFA{} is done by our research team, I have tested the prototype system on all \CFA{} code currently extant, primarily the standard library and compiler test suite.
 
-\section{Resolver Prototype Features}
+\section{Resolver Prototype Features} \label{rp-features-sec}
 
 The resolver prototype can express most of the \CFA{} features described in Chapter~\ref{cfa-chap}. 
@@ -68 +68 @@
 \TODO{test performance; shouldn't be too hard to change \texttt{resolveAssertions} to use unification}
 
-\section{Experimental Results}
+\section{Prototype Experiments}
+
+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}. 
+The prototype was compiled in 24 variants over 3 variables, with variants identified by the hyphen-separated concatenation of their short codes, \eg{} \textsc{bu-imm-bas} for bottom-up traversal, immediate assertion satisfaction, basic type environment. 
+The variables and their values are as follows:
+
+\begin{description}
+        \item[Traversal direction] The order in which arguments are matched with parameters, as discussed in Section~\ref{arg-parm-matching-sec}.
+        \begin{description}
+                \item[Bottom-up] (\textsc{bu}) Baker-style bottom-up pass, searching for function candidates based on the available argument interpretations.
+                \item[Combined] (\textsc{co}) Bilson-style bottom-up pass, where argument interpretations are combined into a single combination interpretation.
+                \item[Top-down] (\textsc{td}) Cormack-style top-down pass, searching for argument interpretations based on function candidate parameter types. The \textsc{td-*} variants of the resolver prototype implement a caching system to avoid recomputation of the same argument interpretation with the same type.
+        \end{description}
+        \item[Assertion satisfaction] The algorithm for finding satisfying declarations for type assertions, as discussed in Section~\ref{assn-sat-sec}.
+        \begin{description}
+                \item[Immediate] (\textsc{imm}) All assertions are checked for satisfaction immediately upon generating a candidate interpretation. The techniques discussed in Section~\ref{assn-sat-sec} for environment combination and level-by-level consideration of recursive assertions are applied here.
+                \item[Deferred] (\textsc{def}) As in \textsc{-imm-}, but waits to check assertions until a top-level interpretation has been generated.
+                \item[Cached] (\textsc{dca}) As in \textsc{-def-}, but uses the caching optimization discussed in Section~\ref{assn-sat-sec}.
+        \end{description}
+        \item[Type Environment] The type environment data structure used, as discussed in Chapter~\ref{env-chap}.
+        \begin{description}
+                \item[Basic] (\textsc{bas}) Bilson-style type environment with hash-based equivalence class storage, as discussed in Section~\ref{naive-env-sec}.
+                \item[Incremental Inheritance] (\textsc{inc}) Incremental inheritance variant sharing unmodified common parent information between environments, as discussed in Section~\ref{inc-env-sec}.
+                \item[Persistent union-find] (\textsc{per}) Union-find-based environment, using the persistent variant discussed in Section~\ref{env-persistent-union-find} for backtracking and combination. The requirement of this type environment for common root environments for combination is incompatible with the caching used in the top-down traversal direction, and thus no \textsc{td-*-per} algorithms are tested.
+        \end{description}
+\end{description}
+
+To test the various algorithms, the resolver prototype was compiled with each of the 24 valid combinations of variables\footnote{Namely, all combinations except \textsc{td-*-per}.}, and then timed running each of the \CFA{}-derived test inputs. 
+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.
+
+As a matter of experimental practicality, test runs which exceeded 8~GB of peak resident memory usage were excluded from the data set. 
+This is a reasonable real-world restriction, as a compiler which is merely slow may be accommodated with patience, but one which uses in excess of 8~GB of RAM may be impossible to run on many currently deployed computer systems.
+The \textsc{bu-dca-bas} and \textsc{bu-dca-per} variants were able to run all 131 test inputs to completion under this restriction, with maximum memory usage of 70~MB and 78~MB, respectively, which validates its selection as an error threshold. 
+However, this threshold did eliminate a significant number of algorithm-test variants, with the worst-performing variant, \textsc{td-imm-inc}, only completing 62 test inputs within the memory bound. 
+Full results for tests completed by algorithm variant are presented in Figure~\TODO{}.
+
+\section{Instance Difficulty}
+
+\section{\CFA{} Results}
 
 % use Jenkins daily build logs to rebuild speedup graph with more data

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

@@ -226 +226 @@
 % also, unification of two classes is not particularly cheap ... the bounds above may be optimistic
 
-\subsection{Argument-Parameter Matching}
+\subsection{Argument-Parameter Matching} \label{arg-parm-matching-sec}
 
 Pruning possible interpretations as early as possible is one way to reduce the real-world cost of expression resolution, provided that a sufficient proportion of interpretations are pruned to pay for the cost of the pruning algorithm. 
@@ -273 +273 @@
 This thesis closes that gap in the literature by performing performance comparisons of both top-down and bottom-up expression resolution algorithms.
 
-\subsection{Assertion Satisfaction}
+\subsection{Assertion Satisfaction} \label{assn-sat-sec}
 
 The assertion satisfaction algorithm designed by Bilson~\cite{Bilson03} for the original \CFACC{} is the most-relevant prior work to this project. 

doc/theses/aaron_moss_PhD/phd/type-environment.tex

@@ -68 +68 @@
 \section{Approaches}
 
-\subsection{Na\"{\i}ve}
+\subsection{Na\"{\i}ve} \label{naive-env-sec}
 
 The type environment data structure used in Bilson's~\cite{Bilson03} original implementation of \CFACC{} is a straightforward translation of the definitions in Section~\ref{env-defn-sec} to \CC{} code; a !TypeEnvironment! contains a list of !EqvClass! type equivalence classes, each of which contains the type bound information and a tree-based sorted set of type variables. 
@@ -75 +75 @@
 These improvements do not change the fundamental issues with this data structure, however.
 
-\subsection{Incremental Inheritance}
+\subsection{Incremental Inheritance} \label{inc-env-sec}
 
 One more invasive modification to this data structure which I investigated is to support swifter combinations of closely-related environments in the backtracking tree by storing a reference to a \emph{parent} environment within each environment, and having that environment only store type classes which have been modified with respect to the parent.