Changeset cceab8a for doc


Ignore:
Timestamp:
Apr 13, 2017, 4:54:38 PM (8 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
Children:
c87eb50
Parents:
3fe98b7
Message:

Initial checkin of evaluation section

Location:
doc/generic_types
Files:
3 added
2 edited

Legend:

Unmodified
Added
Removed

  • doc/generic_types/generic_types.tex

    r3fe98b7 rcceab8a  
    66\usepackage{upquote}                                                                    % switch curled `'" to straight
    77\usepackage{listings}                                                                   % format program code
     8\usepackage{graphicx}
    89
    910\makeatletter
    … …  
    5455\newcommand{\CCseventeen}{\rm C\kern-.1em\hbox{+\kern-.25em+}17\xspace} % C++17 symbolic name
    5556\newcommand{\CCtwenty}{\rm C\kern-.1em\hbox{+\kern-.25em+}20\xspace} % C++20 symbolic name
     57\newcommand{\CCV}{\rm C\kern-.1em\hbox{+\kern-.25em+}obj\xspace} % C++ virtual symbolic name
    5658\newcommand{\CS}{C\raisebox{-0.7ex}{\Large$^\sharp$}\xspace}
    5759\newcommand{\Textbf}[1]{{\color{red}\textbf{#1}}}
    … …  
    765767
    766768\subsection{Variadic Tuples}
     769\label{sec:variadic-tuples}
    767770
    768771To define variadic functions, \CFA adds a new kind of type parameter, @ttype@ (tuple type).
    … …  
    929932\section{Evaluation}
    930933
    931 \TODO{Magnus suggests we need some graphs, it's kind of a done thing that the reviewers will be looking for. Also, we've made some unsubstantiated claims about the runtime performance of \CFA, which some micro-benchmarks could help with. I'm thinking a simple stack push and pop, with an idiomatic \lstinline@void*@, \CFA, \CC template and \CC virtual inheritance versions (the void* and virtual inheritance versions likely need to be linked lists, or clumsy in their API -- possibly both versions) to test generics, and variadic print to test tuples. We measure SLOC, runtime performance, executable size (making sure to include benchmarks for multiple types in the executable), and possibly manually count the number of places where the programmer must provide un-type-checked type information. Appendices don't count against our page limit, so we might want to include the source code for the benchmarks (or at least the relevant implementation details) in one.}
    932 
     934Though \CFA provides significant added functionality over C, these added features do not impose a significant runtime penalty. In fact, \CFA's features for generic programming can enable runtime execution that is faster than idiomatic @void*@-based C code. We have produced a set of generic-code-based micro-benchmarks to demonstrate these claims, source code for which may be found in \TODO{Appendix A}. These benchmarks test a generic stack based on a singly-linked-list, a generic pair data structure, and a variadic @print@ routine similar to that shown in Section~\ref{sec:variadic-tuples}. Each benchmark has been implemented in C with @void*@-based polymorphism, \CFA with the features discussed in this paper, \CC with templates, and \CC using only class inheritance for polymorphism (``\CCV''). The intention of these benchmarks is to represent the costs of idiomatic use of each language's features, rather than the strict maximal performance obtainable by code written in each language -- as all the languages considered have a shared subset comprising most of standard C, a set of maximal-performance benchmarks would presumably show very little runtime variance, and would differ primarily in length and clarity of source code. Particularly, in the \CCV variant of the benchmark all objects inherit from a base @object@ class, explicitly implement interfaces defined as abstract base classes, and must do runtime checks in generic code to safely down-cast objects; this is not an idiomatic programming pattern for \CC, but is meant to represent the design of a simple object-oriented programming language. The most notable difference between the implementations is  memory layout; the \CFA and \CC variants inline the stack and pair elements into their corresponding list and pair nodes, while the C and \CCV versions are forced by their lack of a generic type capability to store generic objects via pointers to separately-allocated objects. For more idiomatic language use, the C and \CFA variants used \texttt{cstdio.h} for printing, while the \CC and \CCV variants used \texttt{iostream}, though preliminary experiments showed this distinction to make little runtime difference. For consistency in testing, all implementations used the C @rand()@ function for random number generation.
     935
     936\begin{figure}
     937\centering
     938\includegraphics{evaluation/timing}
     939\caption{Timing Results for benchmarks}
     940\label{fig:eval}
     941\end{figure}
     942
     943\begin{table}
     944\caption{Properties of benchmark code}
     945\label{tab:eval}
     946\begin{tabular}{lrrrr}
     947                                                        &       C               &       \CFA    &       \CC             &       \CCV    \\ \hline
     948maximum memory usage (MB)       &       10001   &       2501    &       2503    &       11253   \\
     949source code size (lines)        &       301             &       224             &       188             &       437             \\
     950binary size (KB)                        &       18.46   &       234.22  &       18.42   &       42.10   \\
     951\end{tabular}
     952\end{table}
     953
     954The results of running the benchmarks can be seen in Figure~\ref{fig:eval} and Table~\ref{tab:eval}; each result records the time taken by a single function call, repeated $N = 40,000,000$ times where appropriate. 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. These five functions are run first for a stack of integers, and second for a stack of generic pairs of a boolean and a @char@. \TODO{} The data shown is the median of 5 consecutive runs of each program, with an initial warm-up run omitted. All code was compiled at \texttt{-O2} by GCC or G++ 6.2.0, with all \CC code compiled as \CCfourteen. The benchmarks were 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. The C and \CCV variants are generally the slowest and most memory-hungry, due to their less-efficient memory layout and the pointer-indirection necessary to implement generic types in these languages; this problem is exacerbated by the second level of generic types in the pair-based benchmarks. By contrast, the \CFA and \CC variants run in roughly equivalent time for both the integer and pair of boolean and char tests, which makes sense given that an integer is actually larger than the pair in both languages.
     955
     956The \CC code is the shortest largely due to its use of header-only libraries, as template code cannot be separately compiled, the \CFA line count would shrink to \TODO{} if it used a header-only approach instead of the more idiomatic separate compilation. \CFA and \CC also have the advantage of a more extensive standard library; as part of the standard library neither language's generic @pair@ type is included in the line count, while this type must be written by the user programmer in both C and \CCV. 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; 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. Raw line-count, however, is a fairly rough measure of code complexity; another important factor is how much type information the programmer must manually specify, especially where that information is not checked by the compiler. 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}.
    933957
    934958\section{Related Work}
Note: See TracChangeset for help on using the changeset viewer.