Changeset 72b20c9 for doc/theses

Timestamp:

Feb 13, 2019, 3:16:08 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:

96bf5781

Parents:

9e43aff

Message:

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

Location:

doc/theses/aaron_moss_PhD/phd

Files:

• Makefile (modified) (2 diffs)
• evaluation/algo-summary.dat (added)
• evaluation/algo-summary.gp (added)
• evaluation/bu-summary.dat (added)
• evaluation/generic-timing.dat (modified) (1 diff)
• experiments.tex (modified) (1 diff)
• generic-types.tex (modified) (1 diff)

doc/theses/aaron_moss_PhD/phd/Makefile

@@ -38 +38 @@
 GRAPHS = ${addsuffix .tex, \
 generic-timing \
+tests-completed \
 }
 
@@ -62 +63 @@
         ${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

@@ -8 +8 @@
 "clear\npair"   2840    773     748     3511
 "pop\npair"     3025    5414    813     23867
-

doc/theses/aaron_moss_PhD/phd/experiments.tex

@@ -104 +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. 
 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

@@ -449 +449 @@
 \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}