Oct 4, 2018, 5:31:37 PM (4 years ago)
Aaron Moss <a3moss@…>
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, no_list, persistent-indexer

Added benchmark results to generic chapter of thesis

1 edited


  • doc/theses/aaron_moss_PhD/phd/generic-types.tex

    ra72b240 r6cb935d  
    136136\CC{}, Java, and other languages use \emph{generic types} to produce type-safe abstract data types.
    137 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}.
     137Design 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.
    138138\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.
    139139A 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.
    408408\section{Performance Experiments} \label{generic-performance-sec}
    410 \TODO{pull benchmarks from Moss et al.}
     410To 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}.
     411Since 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.
     412A more illustrative comparison measures the costs of idiomatic usage of each language's features.
     413The 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.
     414The 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.
     417int main() {
     418        int max = 0, val = 42;
     419        stack( int ) si, ti;
     421        REPEAT_TIMED( "push_int", N, push( si, val ); )
     422        TIMED( "copy_int", ti{ si }; )
     423        TIMED( "clear_int", clear( si ); )
     424        REPEAT_TIMED( "pop_int", N, int x = pop( ti ); if ( x > max ) max = x; )
     426        pair( short, char ) max = { 0h, '\0' }, val = { 42h, 'a' };
     427        stack( pair( short, char ) ) sp, tp;
     429        REPEAT_TIMED( "push_pair", N, push( sp, val ); )
     430        TIMED( "copy_pair", tp{ sp }; )
     431        TIMED( "clear_pair", clear( sp ); )
     432        REPEAT_TIMED( "pop_pair", N, pair(short, char) x = pop( tp );
     433                if ( x > max ) max = x; )
     437The 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{}.
     438The \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.
     439The 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.
     440Note 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.
     442Figure~\ref{generic-eval-fig} and Table~\ref{generic-eval-table} show the results of running the described benchmark.
     443The graph plots the median of five consecutive runs of each program, with an initial warm-up run omitted.
     444All code is compiled at \texttt{-O2} by gcc or g++ 6.4.0, with all \CC{} code compiled as \CCfourteen{}.
     445The 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.
     446I conjecture that these results scale across most uses of generic types, given the constant underlying polymorphism implementation.
     451\caption{Benchmark timing results (smaller is better)} \label{generic-eval-fig}
     455\caption{Properties of benchmark code} \label{generic-eval-table}
     459                                                                        & \CT{C}        & \CT{\CFA}     & \CT{\CC}      & \CT{\CCV}             \\
     460maximum memory usage (MB)                       & 10\,001       & 2\,502        & 2\,503        & 11\,253               \\
     461source code size (lines)                        & 201           & 191           & 125           & 294                   \\
     462redundant type annotations (lines)      & 27            & 0                     & 2                     & 16                    \\
     463binary size (KB)                                        & 14            & 257           & 14            & 37                    \\
     467The 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.
     468By 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.
     469\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.
     470The gcc compiler is unable to optimize some dead code and condense nested calls; a compiler designed for \CFA{} could more easily perform these optimizations.
     471Finally, the binary size for \CFA{} is larger because of static linking with \CFA{} libraries.
     473\CFA{} is also competitive in terms of source code size, measured as a proxy for programmer effort.
     474The 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.
     475Use 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.
     476The 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.
     477On 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.
     478\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.
     479I 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.
     481Line 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.
     482Such 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.
     483To 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.
     484The \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.
     485The \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.
    412487\section{Future Work}
Note: See TracChangeset for help on using the changeset viewer.