Changeset f1240b0

Timestamp:

Apr 16, 2019, 3:51:40 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:

a786586

Parents:

397848f5

git-author:

Aaron Moss <a3moss@…> (04/16/19 15:50:52)

git-committer:

Aaron Moss <a3moss@…> (04/16/19 15:51:40)

Message:

thesis: strip CFA-DCA results, add speedup graph

Location:

doc/theses/aaron_moss_PhD/phd

Files:

• evaluation/cfa-plots.gp (modified) (2 diffs)
• experiments.tex (modified) (4 diffs)
• macros.tex (modified) (1 diff)

doc/theses/aaron_moss_PhD/phd/evaluation/cfa-plots.gp

@@ -11 +11 @@
 set key outside
 
-plot for [i=2:6] 'evaluation/cfa-time.tsv' using 2:i title columnheader
+plot for [i=2:5] 'evaluation/cfa-time.tsv' using 2:i title columnheader
 
 # MEMORY #
@@ -18 +18 @@
 set ylabel "peak memory (MB)"
 
-plot for [i=2:6] 'evaluation/cfa-mem-by-time.tsv' using 7:(column(i)/1000) title columnheader
+plot for [i=2:5] 'evaluation/cfa-mem-by-time.tsv' using 7:(column(i)/1000) title columnheader
+
+# SPEEDUP #
+set output BUILD."cfa-speedup.tex"
+
+set ylabel "speedup w.r.t. baseline"
+unset logscale y
+
+plot 'evaluation/cfa-time.tsv' using 2:(column(2)/column(2)) title 'baseline', \
+     '' using 2:(column(2)/column(3)) title columnheader, \
+         '' using 2:(column(3)/column(4)) title 'inter-round', \
+         '' using 2:(column(4)/column(5)) title columnheader
 
 # # RUNTIME SPEEDUP #

doc/theses/aaron_moss_PhD/phd/experiments.tex

@@ -210 +210 @@
 \section{\CFA{} Results} \label{cfa-results-sec}
 
-I have integrated most of the algorithmic techniques discussed in this chapter into \CFACC{}. 
+I have integrated a number of the algorithmic techniques discussed in this chapter into \CFACC{}. 
 This integration took place over a period of months while \CFACC{} was under active development on a number of other fronts, so it is not possible to completely isolate the effects of the algorithmic changes, but I believe the algorithmic changes to have had the most-significant effects on performance over the study period. 
 To generate this data, representative commits from the \texttt{git} history of the project were checked out and compiled, then run on the same machine used for the resolver prototype experiments discussed in Section~\ref{proto-exp-sec}. 
@@ -217 +217 @@
 I performed two rounds of modification to \CFACC{}; the first round moved from Bilson's original combined-bottom-up algorithm to an un-combined bottom-up algorithm, denoted \textsc{cfa-co} and \textsc{cfa-bu}, respectively. 
 A top-down algorithm was not attempted in \CFACC{} due to its poor performance in the prototype.
-The second round of modifications addressed assertion satisfaction, taking Bilson's original \textsc{cfa-imm} algorithm, and iteratively modifying it, first to use the deferred approach \textsc{cfa-def}, then caching those results in the \textsc{cfa-dca} algorithm. 
+The second round of modifications addressed assertion satisfaction, taking Bilson's original \textsc{cfa-imm} algorithm and modifying it to use the deferred approach \textsc{cfa-def}. 
+Due to time constraints a deferred-cached assertion satisfaction algorithm for \CFACC{} could not be completed, but both preliminary results from this effort and the averaged prototype results from Section~\ref{proto-exp-sec} indicate that assertion satisfaction caching is not likely to be a fruitful optimization for \CFACC{}. 
 The new environment data structures discussed in Section~\ref{proto-exp-sec} have not been successfully merged into \CFACC{} due to their dependencies on the garbage-collection framework in the prototype; I spent several months modifying \CFACC{} to use similar garbage collection, but due to \CFACC{} not being designed to use such memory management the performance of the modified compiler was non-viable. 
 It is possible that the persistent union-find environment could be modified to use a reference-counted pointer internally without changing the entire memory-management framework of \CFACC{}, but such an attempt is left to future work.
 
-As can be seen in Figures~\ref{cfa-time-fig} and~\ref{cfa-mem-fig}, the time and peak memory results for these five versions of \CFACC{} show that assertion resolution dominates total resolution cost, with the \textsc{cfa-def} and \textsc{cfa-dca} variants running consistently faster than the others on more expensive test cases; no difference can be seen between these two algorithms' performance, but which agrees with the prototype experiments in Section~\ref{proto-exp-sec}. 
-The results from \CFACC{} for \textsc{cfa-co} \textit{vs.}\ \textsc{cfa-bu} do not mirror those from the prototype; I conjecture this is mostly due to the different memory-management schemes and sorts of data required to run type unification and assertion satisfaction calculations, as \CFACC{} performance has proven to be particularly sensitive to the amount of heap allocation performed. 
-This data also shows a noticeable regression in compiler performance in the eleven months between \textsc{cfa-bu} and \textsc{cfa-imm}, which use the same resolution algorithms; this regression is not due to expression resolution, as no integration work happened in this time, but I am unable to ascertain its actual cause.
+As can be seen in Figures~\ref{cfa-time-fig}--\ref{cfa-mem-fig}, the time and peak memory results for these five versions of \CFACC{} show that assertion resolution dominates total resolution cost, with the \textsc{cfa-def} variant running consistently faster than the others on more expensive test cases, and the speedup from the deferred approach increasing with the difficulty of the test case. 
+The results from \CFACC{} for \textsc{cfa-co} \vs{} \textsc{cfa-bu} do not mirror those from the prototype; I conjecture this is mostly due to the different memory-management schemes and sorts of data required to run type unification and assertion satisfaction calculations, as \CFACC{} performance has proven to be particularly sensitive to the amount of heap allocation performed. 
+This data also shows a noticeable regression in compiler performance in the eleven months between \textsc{cfa-bu} and \textsc{cfa-imm}, which use the same resolution algorithms; this approximate doubling in runtime is not due to expression resolution, as no integration work happened in this time, but I am unable to ascertain its actual cause. 
+To isolate the effects of the algorithmic changes from this unrelated performance regression, the speedup results in Figure~\ref{cfa-speedup-fig} are shown with respect to the start of each modification round, \textsc{cfa-bu} \vs{} \textsc{cfa-co} and \textsc{cfa-def} \vs{} \textsc{cfa-imm}.
 It should also be noted with regard to the peak memory results in Figure~\ref{cfa-mem-fig} that the peak memory usage does not always occur during the resolution phase of the compiler. 
 
@@ -230 +232 @@
 \input{cfa-time}
 \caption[\CFACC{} runtime against \textsc{cfa-co} baseline.]{\CFACC{} runtime against \textsc{cfa-co} baseline. Note log scales on both axes.} \label{cfa-time-fig}
+\end{figure}
+
+\begin{figure}
+\centering
+\input{cfa-speedup}
+\caption[\CFACC{} speedup.]{\CFACC{} speedup against against \textsc{cfa-co} baseline runtime. To isolate the effect of algorithmic changes, \textsc{cfa-bu} speedup is \vs{} \textsc{cfa-co} while \textsc{cfa-def} speedup is \vs{} \textsc{cfa-imm}. The `inter-round' series shows slowdown between \textsc{cfa-bu} and \textsc{cfa-imm}.} \label{cfa-speedup-fig}
 \end{figure}
 
@@ -246 +254 @@
 % some data you collected personally for imm vs. def vs. dca variants in resolv-proto/logs/rp-bu-tec_vs_cfacc.ods
 
-% look back at Resolution Algorithms section for threads to tie up "does the algorithm look like this?"
-
 \section{Conclusion}
 

doc/theses/aaron_moss_PhD/phd/macros.tex

@@ -19 +19 @@
 \newcommand{\etc}{\textit{etc.}\@}
 \newcommand{\etal}{\textit{et~al.}\@}
+\newcommand{\vs}{\textit{vs.}\@}
 
 \newcommand{\myset}[1]{\left\{#1\right\}}