Changeset 9e43aff for doc/theses/aaron_moss_PhD/phd/experiments.tex
- Timestamp:
- Feb 12, 2019, 10:40:29 PM (6 years ago)
- 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
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/aaron_moss_PhD/phd/experiments.tex
r0f78f3c7 r9e43aff 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. 16 16 17 \section{Resolver Prototype Features} 17 \section{Resolver Prototype Features} \label{rp-features-sec} 18 18 19 19 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} 69 69 70 \section{Experimental Results} 70 \section{Prototype Experiments} 71 72 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}. 73 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. 74 The variables and their values are as follows: 75 76 \begin{description} 77 \item[Traversal direction] The order in which arguments are matched with parameters, as discussed in Section~\ref{arg-parm-matching-sec}. 78 \begin{description} 79 \item[Bottom-up] (\textsc{bu}) Baker-style bottom-up pass, searching for function candidates based on the available argument interpretations. 80 \item[Combined] (\textsc{co}) Bilson-style bottom-up pass, where argument interpretations are combined into a single combination interpretation. 81 \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. 82 \end{description} 83 \item[Assertion satisfaction] The algorithm for finding satisfying declarations for type assertions, as discussed in Section~\ref{assn-sat-sec}. 84 \begin{description} 85 \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. 86 \item[Deferred] (\textsc{def}) As in \textsc{-imm-}, but waits to check assertions until a top-level interpretation has been generated. 87 \item[Cached] (\textsc{dca}) As in \textsc{-def-}, but uses the caching optimization discussed in Section~\ref{assn-sat-sec}. 88 \end{description} 89 \item[Type Environment] The type environment data structure used, as discussed in Chapter~\ref{env-chap}. 90 \begin{description} 91 \item[Basic] (\textsc{bas}) Bilson-style type environment with hash-based equivalence class storage, as discussed in Section~\ref{naive-env-sec}. 92 \item[Incremental Inheritance] (\textsc{inc}) Incremental inheritance variant sharing unmodified common parent information between environments, as discussed in Section~\ref{inc-env-sec}. 93 \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. 94 \end{description} 95 \end{description} 96 97 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. 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. 99 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. 100 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. 101 102 As a matter of experimental practicality, test runs which exceeded 8~GB of peak resident memory usage were excluded from the data set. 103 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. 104 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. 105 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. 106 Full results for tests completed by algorithm variant are presented in Figure~\TODO{}. 107 108 \section{Instance Difficulty} 109 110 \section{\CFA{} Results} 71 111 72 112 % use Jenkins daily build logs to rebuild speedup graph with more data
Note: See TracChangeset
for help on using the changeset viewer.