# Changeset 72b20c9

Ignore:
Timestamp:
Feb 13, 2019, 3:16:08 PM (3 years ago)
Branches:
aaron-thesis, arm-eh, cleanup-dtors, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr
Children:
96bf5781
Parents:
9e43aff
Message:

thesis: Add charts and discussion of summary results for different algorithms

Location:
doc/theses/aaron_moss_PhD/phd
Files:
4 edited

Unmodified
Removed
• ## doc/theses/aaron_moss_PhD/phd/Makefile

 r9e43aff GRAPHS = ${addsuffix .tex, \ generic-timing \ tests-completed \ }${LATEX} ${BASE}${GRAPHS} : generic-timing.gp generic-timing.dat ${BUILD} generic-timing.tex : generic-timing.gp generic-timing.dat${BUILD} gnuplot -e BUILD="'${BUILD}/'"${EVALDIR}/generic-timing.gp tests-completed.tex : algo-summary.gp algo-summary.dat bu-summary.dat ${BUILD} gnuplot -e BUILD="'${BUILD}/'" ${EVALDIR}/algo-summary.gp${BUILD}:
• ## doc/theses/aaron_moss_PhD/phd/evaluation/generic-timing.dat

 r9e43aff "clear\npair"   2840    773     748     3511 "pop\npair"     3025    5414    813     23867
• ## doc/theses/aaron_moss_PhD/phd/experiments.tex

 r9e43aff 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{}. Full results for tests completed by algorithm variant are presented in Figure~\ref{tests-completed-fig}. \begin{figure} \centering \input{tests-completed} \caption[Tests completed for each algorithmic variant]{Number of tests completed for each algorithmic variant} \label{tests-completed-fig} \end{figure} As can be seen from these results, traversal direction is clearly the dominant variable in memory usage, with the \textsc{bu-*} variants performing better than the \textsc{co-} variants, which in turn out-perform the \textsc{td-} variants. It can also be seen that the incremental inheritance (\textsc{inc}) type environment consistently under-performs the other two environment data structures tested. To provide a more holistic view of performance, I have considerered the results from the 56 test inputs which all algorithms are able to complete within the memory bound. Limiting consideration to these algorithms provides an apples-to-apples comparison between algorithms, as the excluded inputs are harder instances which take more time and memory for the algorithms which are able to solve them. Figures~\ref{avg-peak-mem-fig} and~\ref{avg-runtime-fig} show the mean peak memory and runtime, respectively, of each algorithm over the inputs in this data set. These averages are not themselves meaningful, but do enable an overall comparison of relative performance of the different variants. Selecting only these 56 easy'' test inputs does bias the average values downward, but has little effect on the relative trends; similar trends can be seen in the graphs of the \textsc{bu-*} algorithms over the 124 (of 131) test inputs which all complete, omitted to save space. \begin{figure} \centering \input{avg-peak-mem} \caption[Average peak memory for each algorithmic variant]{Average peak resident set size for each algorithmic variant over the 56 test inputs all variants complete.} \label{avg-peak-mem-fig} \end{figure} \begin{figure} \centering \input{avg-runtime} \caption[Average runtime for each algorithmic variant]{Average runtime for each algorithmic variant over the 56 test inputs all variants complete.} \label{avg-runtime-fig} \end{figure} % \begin{figure} % \centering % \input{bu-peak-mem} % \caption[Average peak memory for each \textsc{bu-*} variant]{Average peak resident set size for each \textsc{bu-*} variant over the 124 test inputs all \textsc{bu-*} variants complete.} \label{bu-peak-mem-fig} % \end{figure} % \begin{figure} % \centering % \input{bu-runtime} % \caption[Average runtime for each \textsc{bu-*} variant]{Average runtime for each \textsc{bu-*} variant over the 124 test inputs all \textsc{bu-*} variants complete.} \label{bu-runtime-fig} % \end{figure} It can be seen from these results that that top-down immediate-assertion-satisfaction (\textsc{td-imm-*}) are particularly un-performant, as they check a significant number of assertions without filtering to determine if the arguments can be made to fit. It is clear that the bottom-up (\textsc{bu-*}) traversal order is better than both top-down and the Bilson-style bottom-up-combined orders. With regard to assertion satisfaction, immediate (\textsc{*-imm-*}) satisfaction is an inferior solution, though there is little performance difference between deferred (\textsc{*-def-*}) and deferred-cached (\textsc{*-dca-*}) for instances which they can both complete. Since the \textsc{dca} algorithm can solve some particularly hard instances which \textsc{def} cannot, it is the recommended approach. The \textsc{inc} type environment also often uses upwards of double the memory required by the other variants, in addition to being consistently slower on these easy tests; aside from \textsc{bu-imm-bas} performing worse than \textsc{bu-imm-inc} on average when larger tests are considered, these results hold for the other variants. Aside from that, the persistent union-find (\textsc{per}) type environment generally performs better than the basic (\textsc{bas}) environment, with similar peak memory usage and an average speedup factor of nearly 2, though the requirements of the \textsc{per} environment for automatic garbage collection and a shared history for combination make retrofitting it into older code difficult. \section{Instance Difficulty}
• ## doc/theses/aaron_moss_PhD/phd/generic-types.tex

 r9e43aff \centering \input{generic-timing} \caption{Benchmark timing results (smaller is better)} \label{generic-eval-fig} \caption[Benchmark timing results]{Benchmark timing results (smaller is better)} \label{generic-eval-fig} \end{figure}
Note: See TracChangeset for help on using the changeset viewer.