Ignore:
Timestamp:
Feb 12, 2019, 10:40:29 PM (5 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

File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/aaron_moss_PhD/phd/experiments.tex

    r0f78f3c7 r9e43aff  
    1515Since 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.
    1616
    17 \section{Resolver Prototype Features}
     17\section{Resolver Prototype Features} \label{rp-features-sec}
    1818
    1919The resolver prototype can express most of the \CFA{} features described in Chapter~\ref{cfa-chap}.
    … …  
    6868\TODO{test performance; shouldn't be too hard to change \texttt{resolveAssertions} to use unification}
    6969
    70 \section{Experimental Results}
     70\section{Prototype Experiments}
     71
     72The 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}.
     73The 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.
     74The 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
     97To 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.
     98Terminal 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.
     99The 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.
     100The 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
     102As a matter of experimental practicality, test runs which exceeded 8~GB of peak resident memory usage were excluded from the data set.
     103This 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.
     104The \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.
     105However, 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.
     106Full results for tests completed by algorithm variant are presented in Figure~\TODO{}.
     107
     108\section{Instance Difficulty}
     109
     110\section{\CFA{} Results}
    71111
    72112% use Jenkins daily build logs to rebuild speedup graph with more data
Note: See TracChangeset for help on using the changeset viewer.