Ignore:
Timestamp:
Apr 14, 2017, 4:51:13 PM (5 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, resolv-new, with_gc
Children:
1504536, e3de500
Parents:
3895b8b5
Message:

Update benchmarks, cleanup edits to the evaluation section

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/generic_types/generic_types.tex

    r3895b8b5 r3fb7f5e  
    958958The \CCV variant illustrates an alternative object-oriented idiom where all objects inherit from a base @object@ class, mimicking a Java-like interface;
    959959hence runtime checks are necessary to safely down-cast objects.
    960 The most notable difference among the implementations is in optimizations: \CFA and \CC inline the stack and pair elements into corresponding list and pair nodes, while the C and \CCV lack generic-type capability {\color{red}(AWKWARD) to store generic objects via pointers to separately-allocated objects}.
    961 For the print benchmark, idiomatic printing is used: the C and \CFA variants used @cstdio.h@, while the \CC and \CCV variants used @iostream@.
    962 Preliminary tests show the difference has little runtime effect.
     960The most notable difference among the implementations is in 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 a capability and store generic objects via pointers to separately-allocated objects instead.
     961For the print benchmark, idiomatic printing is used: the C and \CFA variants use @stdio.h@, while the \CC and \CCV variants use @iostream@.
     962Preliminary tests show this difference has little runtime effect.
    963963Finally, the C @rand@ function is used generate random numbers.
    964964
     
    975975\newcommand{\CT}[1]{\multicolumn{1}{c}{#1}}
    976976\begin{tabular}{r|rrrr}
    977                                                         & \CT{C}        & \CT{\CFA}     & \CT{\CC}      &       \CT{\CCV}       \\ \hline
    978 maximum memory usage (MB)       & 10001         & 2501          & 2503          &       11253           \\
    979 source code size (lines)        & 301           & 224           & 188           &       437                     \\
    980 binary size (KB)                        & 18            & 234           & 18            &       42                      \\
     977                                                                        & \CT{C}        & \CT{\CFA}     & \CT{\CC}      &       \CT{\CCV}       \\ \hline
     978maximum memory usage (MB)                       & 10001         & 2501          & 2503          &       11253           \\
     979source code size (lines)                        & 301           & 224           & 188           &       437                     \\
     980redundant type annotations (lines)      & 46            & 3                     & 2                     &       15                      \\
     981binary size (KB)                                        & 18            & 234           & 18            &       42                      \\
    981982\end{tabular}
    982983\end{table}
    983984
    984985Figure~\ref{fig:eval} and Table~\ref{tab:eval} show the benchmark results.
    985 Each data point is the time for 40M function call, repeated times where appropriate.
    986 The five functions are $N$ stack pushes of randomly generated elements, deep copy of an $N$ element stack, clearing all nodes of an $N$ element stack, $N/2$ variadic @print@ calls each containing two constant strings and two stack elements \TODO{right now $N$ fresh elements: FIX}, and $N$ stack pops, keeping a running record of the maximum element to ensure that the object copies are not optimized out.
     986Each data point is the time for $N = 40M$ function calls or loop iterations, as appropriate.
     987The five functions are $N$ stack pushes of randomly generated elements, deep copy of an $N$ element stack, clearing all nodes of an $N$ element stack, $N$ stack pops (keeping a running record of the maximum element to ensure that the object copies are not optimized out), and $N/2$ variadic @print@ calls each containing two constant strings and two stack elements.
    987988These five functions are run first for a stack of integers, and second for a stack of generic pairs of a boolean and a @char@.
    988989\TODO{} The data shown is the median of 5 consecutive runs of each program, with an initial warm-up run omitted.
     
    993994
    994995\CC performs best because it uses header-only inlined libraries (i.e., no separate compilation).
    995 \CFA and \CC have the advantage of a pre-written generic @pair@ type to reduce line count, while C and \CCV require it to written by the programmer. {\color{red} Why?}
    996 The definition of @object@ and wrapper classes for @bool@, @char@, @int@, and @const char *@ are included in the line count for \CCV, which somewhat inflates its line count, as an actual object-oriented language would include these in the standard library and with their omission the \CCV line count is similar to C;
    997 we justify the given line count by the fact that many object-oriented languages do not allow implementing new interfaces on library types without subclassing or boilerplate-filled wrapper types, which may be similarly verbose.
     996\CFA and \CC have the advantage of a pre-written generic @pair@ type to reduce line count, while C and \CCV require it to written by the programmer, as C does not have a generic collections library in its standard distribution and \CCV does not use the \CC standard template library by construction.
     997The definition of @object@ and wrapper classes for @bool@, @char@, @int@, and @const char *@ are included in the line count for \CCV, which somewhat inflates its line count, as an actual object-oriented language would include these in the standard library; with their omission the \CCV line count is similar to C.
     998We justify the given line count by noting that many object-oriented languages do not allow implementing new interfaces on library types without subclassing or boilerplate-filled wrapper types, which may be similarly verbose.
     999
    9981000Raw line-count, however, is a fairly rough measure of code complexity;
    9991001another important factor is how much type information the programmer must manually specify, especially where that information is not checked by the compiler.
    1000 Such un-checked 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 pointers arguments and format codes, or \CCV, with its extensive use of un-type-checked downcasts (\eg @object@ to @integer@ when popping a stack, or @object@ to @printable@ when printing the elements of a @pair@) \TODO{Actually calculate this; I want to put a distinctive comment in the source code and grep for it}.
    1001 
     1002Such un-checked 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 pointers arguments and format codes, or \CCV, with its extensive use of un-type-checked downcasts (\eg @object@ to @integer@ when popping a stack, or @object@ to @printable@ when printing the elements of a @pair@). To quantify this, the ``redundant type annotations'' line in Table~\ref{tab:eval} counts the number of lines on which the type of a known variable is re-specified, 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 a new stack nodes, while the C and \CCV benchmarks have several such annotations spread throughout their code. The three instances in which the \CFA benchmark still uses redundant type specifiers are to cast the result of a polymorphic @malloc@ call (the @sizeof@ argument is inferred by the compiler). These uses are similar to the @new@ expressions in \CC, though ongoing work on the \CFA compiler's type resolver should shortly render even these type casts superfluous.
    10021003
    10031004\section{Related Work}
     
    10881089\appendix
    10891090
    1090 
    10911091\section{BenchMarks}
    10921092\label{sec:BenchMarks}
Note: See TracChangeset for help on using the changeset viewer.