Index: doc/theses/aaron_moss_PhD/phd/Makefile =================================================================== --- doc/theses/aaron_moss_PhD/phd/Makefile (revision a72b2409258fb1475c94ea127e47443a40261a83) +++ doc/theses/aaron_moss_PhD/phd/Makefile (revision 6cb935d44eac9fc5a0d5681d4222864aa38d730f) @@ -1,4 +1,5 @@ BUILD = build BIBDIR = ../../../bibliography +EVALDIR = evaluation TEXLIB = .:${BUILD}:${BIBDIR}: @@ -6,4 +7,6 @@ LATEX = TEXINPUTS=${TEXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${BUILD} BIBTEX = BIBINPUTS=${TEXLIB} && export BIBINPUTS && bibtex + +VPATH = ${EVALDIR} BASE = thesis @@ -24,4 +27,8 @@ } +GRAPHS = ${addsuffix .tex, \ +generic-timing \ +} + .PHONY : all rebuild-refs clean wc @@ -40,5 +47,5 @@ dvips ${BUILD}/$< -o ${BUILD}/$@ -${BASE}.dvi : Makefile ${SOURCES} ${BIBFILE} ${BUILD} +${BASE}.dvi : Makefile ${SOURCES} ${GRAPHS} ${BIBFILE} ${BUILD} ${LATEX} ${BASE} ${BIBTEX} ${BUILD}/${BASE} @@ -46,13 +53,6 @@ ${LATEX} ${BASE} -# ${DOCUMENT} : Makefile ${SOURCES} ${BUILD} -# ${LATEX} ${BASE} -# ${LATEX} ${BASE} - -# rebuild-refs : Makefile ${SOURCES} ${BIBFILE} ${BUILD} -# ${LATEX} ${BASE} -# ${BIBTEX} ${BUILD}/${BASE} -# ${LATEX} ${BASE} -# ${LATEX} ${BASE} +${GRAPHS} : generic-timing.gp generic-timing.dat ${BUILD} + gnuplot -e BUILD="'${BUILD}/'" ${EVALDIR}/generic-timing.gp ${BUILD}: Index: doc/theses/aaron_moss_PhD/phd/evaluation/generic-timing.dat =================================================================== --- doc/theses/aaron_moss_PhD/phd/evaluation/generic-timing.dat (revision 6cb935d44eac9fc5a0d5681d4222864aa38d730f) +++ doc/theses/aaron_moss_PhD/phd/evaluation/generic-timing.dat (revision 6cb935d44eac9fc5a0d5681d4222864aa38d730f) @@ -0,0 +1,10 @@ +"400 million repetitions" "C" "\\CFA{}" "\\CC{}" "\\CCV{}" +"push\nint" 2911 2034 1504 3246 +"copy\nint" 2953 1622 1526 3075 +"clear\nint" 1397 754 753 1452 +"pop\nint" 1446 1203 760 5016 +"push\npair" 3673 2297 955 6971 +"copy\npair" 6027 1183 998 7204 +"clear\npair" 2840 773 748 3511 +"pop\npair" 3025 5414 813 23867 + Index: doc/theses/aaron_moss_PhD/phd/evaluation/generic-timing.gp =================================================================== --- doc/theses/aaron_moss_PhD/phd/evaluation/generic-timing.gp (revision 6cb935d44eac9fc5a0d5681d4222864aa38d730f) +++ doc/theses/aaron_moss_PhD/phd/evaluation/generic-timing.gp (revision 6cb935d44eac9fc5a0d5681d4222864aa38d730f) @@ -0,0 +1,29 @@ +# set terminal pdfcairo linewidth 3 size 6,3 +# set output "timing.pdf" +set terminal pslatex size 6.25,2.125 color solid +set output BUILD."generic-timing.tex" + +set pointsize 2.0 +set grid linetype 0 +set style data histogram +set style histogram cluster gap 2 +set style fill solid border -1 +set offset -0.5,-0.35 +set boxwidth 0.8 + +set key top left reverse Left + +set style fill solid noborder +set linetype 1 lc rgb 'black' +set linetype 2 lc rgb 'red' +set linetype 3 lc rgb 'blue' +set linetype 4 lc rgb 'green' + +SCALE=1000 +set ylabel "seconds" +set yrange [0:10] + +set label "23.9" at 7.125,10.5 +set style fill pattern 4 border lt -1 +# set datafile separator "," +plot for [COL=2:5] 'evaluation/generic-timing.dat' using (column(COL)/SCALE):xticlabels(1) title columnheader Index: doc/theses/aaron_moss_PhD/phd/generic-types.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/generic-types.tex (revision a72b2409258fb1475c94ea127e47443a40261a83) +++ doc/theses/aaron_moss_PhD/phd/generic-types.tex (revision 6cb935d44eac9fc5a0d5681d4222864aa38d730f) @@ -135,5 +135,5 @@ \CC{}, Java, and other languages use \emph{generic types} to produce type-safe abstract data types. -Design and implementation of generic types for \CFA{} is the first major contribution of this thesis, a summary of which is published in \cite{Moss18}. +Design and implementation of generic types for \CFA{} is the first major contribution of this thesis, a summary of which is published in \cite{Moss18} and from which this chapter is closely based. \CFA{} generic types integrate efficiently and naturally with the existing polymorphic functions in \CFA{}, while retaining backward compatibility with C in layout and support for separate compilation. A generic type can be declared in \CFA{} by placing a !forall! specifier on a !struct! or !union! declaration, and instantiated using a parenthesized list of types after the generic name. @@ -408,5 +408,80 @@ \section{Performance Experiments} \label{generic-performance-sec} -\TODO{pull benchmarks from Moss et al.} +To validate the practicality of this generic type design I have conducted microbenchmark-based tests against a number of comparable code designs in C and \CC{}, first published in \cite{Moss18}. +Since all these languages are compiled with the same compiler backend and share a subset essentially comprising standard C, maximal-performance benchmarks should show little runtime variance, differing only in length and clarity of source code. +A more illustrative comparison measures the costs of idiomatic usage of each language's features. +The code below shows the \CFA{} benchmark tests for a generic stack based on a singly-linked list; the test suite is equivalent for the other other languages. +The experiment uses element types !int! and !pair(short, char)! and pushes $N = 40M$ elements on a generic stack, copies the stack, clears one of the stacks, and finds the maximum value in the other stack. + +\begin{cfa} +int main() { + int max = 0, val = 42; + stack( int ) si, ti; + + REPEAT_TIMED( "push_int", N, push( si, val ); ) + TIMED( "copy_int", ti{ si }; ) + TIMED( "clear_int", clear( si ); ) + REPEAT_TIMED( "pop_int", N, int x = pop( ti ); if ( x > max ) max = x; ) + + pair( short, char ) max = { 0h, '\0' }, val = { 42h, 'a' }; + stack( pair( short, char ) ) sp, tp; + + REPEAT_TIMED( "push_pair", N, push( sp, val ); ) + TIMED( "copy_pair", tp{ sp }; ) + TIMED( "clear_pair", clear( sp ); ) + REPEAT_TIMED( "pop_pair", N, pair(short, char) x = pop( tp ); + if ( x > max ) max = x; ) +} +\end{cfa} + +The four versions of the benchmark implemented are C with !void*!-based polymorphism, \CFA{} with parameteric polymorphism, \CC{} with templates, and \CC{} using only class inheritance for polymorphism, denoted \CCV{}. +The \CCV{} variant illustrates an alternative object-oriented idiom where all objects inherit from a base !object! class, mimicking a Java-like interface; in particular, runtime checks are necessary to safely downcast objects. +The most notable difference among the implementations is the memory layout of generic types: \CFA{} and \CC{} inline the stack and pair elements into corresponding list and pair nodes, while C and \CCV{} lack such capability and, instead, must store generic objects via pointers to separately allocated objects. +Note that the C benchmark uses unchecked casts as C has no runtime mechanism to perform such checks, whereas \CFA{} and \CC{} provide type safety statically. + +Figure~\ref{generic-eval-fig} and Table~\ref{generic-eval-table} show the results of running the described benchmark. +The graph plots the median of five consecutive runs of each program, with an initial warm-up run omitted. +All code is compiled at \texttt{-O2} by gcc or g++ 6.4.0, with all \CC{} code compiled as \CCfourteen{}. +The benchmarks are run on an Ubuntu 16.04 workstation with 16 GB of RAM and a 6-core AMD FX-6300 CPU with 3.5 GHz maximum clock frequency. +I conjecture that these results scale across most uses of generic types, given the constant underlying polymorphism implementation. + +\begin{figure} +\centering +\input{generic-timing} +\caption{Benchmark timing results (smaller is better)} \label{generic-eval-fig} +\end{figure} + +\begin{table} +\caption{Properties of benchmark code} \label{generic-eval-table} +\centering +\newcommand{\CT}[1]{\multicolumn{1}{c}{#1}} +\begin{tabular}{lrrrr} + & \CT{C} & \CT{\CFA} & \CT{\CC} & \CT{\CCV} \\ +maximum memory usage (MB) & 10\,001 & 2\,502 & 2\,503 & 11\,253 \\ +source code size (lines) & 201 & 191 & 125 & 294 \\ +redundant type annotations (lines) & 27 & 0 & 2 & 16 \\ +binary size (KB) & 14 & 257 & 14 & 37 \\ +\end{tabular} +\end{table} + +The C and \CCV{} variants are generally the slowest and have the largest memory footprint, due to their less-efficient memory layout and the pointer indirection necessary to implement generic types in those languages; this inefficiency is exacerbated by the second level of generic types in the pair benchmarks. +By contrast, the \CFA{} and \CC{} variants run in roughly equivalent time for both the integer and pair because of the equivalent storage layout, with the inlined libraries (\ie{} no separate compilation) and greater maturity of the \CC{} compiler contributing to its lead. +\CCV{} is slower than C largely due to the cost of runtime type checking of downcasts (implemented with !dynamic_cast!); the outlier for \CFA{}, pop !pair!, results from the complexity of the generated-C polymorphic code. +The gcc compiler is unable to optimize some dead code and condense nested calls; a compiler designed for \CFA{} could more easily perform these optimizations. +Finally, the binary size for \CFA{} is larger because of static linking with \CFA{} libraries. + +\CFA{} is also competitive in terms of source code size, measured as a proxy for programmer effort. +The line counts in Table~\ref{generic-eval-table} include implementations of !pair! and !stack! types for all four languages for purposes of direct comparison, although it should be noted that \CFA{} and \CC{} have prewritten data structures in their standard libraries that programmers would generally use instead. +Use of these standard library types has minimal impact on the performance benchmarks, but shrinks the \CFA{} and \CC{} code to 39 and 42 lines, respectively. +The difference between the \CFA{} and \CC{} line counts is primarily declaration duplication to implement separate compilation; a header-only \CFA{} library is similar in length to the \CC{} version. +On the other hand, due to the language shortcomings mentioned at the beginning of the chapter, C does not have a generic collections library in its standard distribution, resulting in frequent reimplementation of such collection types by C programmers. +\CCV{} does not use the \CC{} standard template library by construction, and, in fact, includes the definition of !object! and wrapper classes for !char!, !short!, and !int! in its line count, which inflates this count somewhat, as an actual object-oriented language would include these in the standard library. +I justify the given line count by noting that many object-oriented languages do not allow implementing new interfaces on library types without subclassing or wrapper types, which may be similarly verbose. + +Line count is a fairly rough measure of code complexity; another important factor is how much type information the programmer must specify manually, especially where that information is not type-checked. +Such unchecked type information produces a heavier documentation burden and increased potential for runtime bugs and is much less common in \CFA{} than C, with its manually specified function pointer arguments and format codes, or \CCV{}, with its extensive use of un-type-checked downcasts, \eg{} !object! to !integer! when popping a stack. +To quantify this manual typing, the ``redundant type annotations'' line in Table~\ref{generic-eval-table} counts the number of lines on which the known type of a variable is respecified, either as a format specifier, explicit downcast, type-specific function, or by name in a !sizeof!, !struct! literal, or !new! expression. +The \CC{} benchmark uses two redundant type annotations to create new stack nodes, whereas the C and \CCV{} benchmarks have several such annotations spread throughout their code. +The \CFA{} benchmark is able to eliminate \emph{all} redundant type annotations through use of the return-type polymorphic !alloc! function in the \CFA{} standard library. \section{Future Work} Index: doc/theses/aaron_moss_PhD/phd/macros.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/macros.tex (revision a72b2409258fb1475c94ea127e47443a40261a83) +++ doc/theses/aaron_moss_PhD/phd/macros.tex (revision 6cb935d44eac9fc5a0d5681d4222864aa38d730f) @@ -12,4 +12,5 @@ \newcommand{\CCseventeen}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}17} % C++17 symbolic name \newcommand{\CCtwenty}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}20} % C++20 symbolic name +\newcommand{\CCV}{\rm C\kern-.1em\hbox{+\kern-.25em+}obj} % C++ virtual symbolic name \newcommand{\Csharp}{C\raisebox{-0.7ex}{\Large$^\sharp$}} % C# symbolic name