Changeset 2b8a897


Ignore:
Timestamp:
Apr 17, 2017, 6:12:58 PM (4 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-env, no_list, persistent-indexer, resolv-new, with_gc
Children:
7aa78b4
Parents:
ab16fc5
Message:

Final tweaks to the evaluation section from Aaron

Location:
doc/generic_types
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/generic_types/generic_types.tex

    rab16fc5 r2b8a897  
    949949In fact, \CFA's features for generic programming can enable faster runtime execution than idiomatic @void *@-based C code.
    950950This claim is demonstrated through a set of generic-code-based micro-benchmarks in C, \CFA, and \CC (see stack implementations in Appendix~\ref{sec:BenchmarkStackImplementation}).
    951 Since all these languages share a subset comprising standard C, maximal-performance benchmarks would show little runtime variance, other than in length and clarity of source code.
    952 A more illustrative benchmark is the idiomatic costs of each language's features covering common usage.
     951Since all these languages share a subset essentially comprising standard C, maximal-performance benchmarks would show little runtime variance, other than in length and clarity of source code.
     952A more illustrative benchmark measures the costs of idiomatic usage of each language's features.
    953953Figure~\ref{fig:BenchmarkTest} shows the \CFA benchmark tests for a generic stack based on a singly linked-list, a generic pair-data-structure, and a variadic @print@ routine similar to that in Section~\ref{sec:variadic-tuples}.
    954954The benchmark test is similar for C and \CC.
    955 The experiment uses element types @int@ and @pair(_Bool, char)@, and pushes $N=40M$ elements on a generic stack, copies the stack, clears one of the stacks, finds the maximum value in the other stack, and prints $N/2$ (to reduce graph height) constants.
     955The experiment uses element types @int@ and @pair(_Bool, char)@, and pushes $N=40M$ elements on a generic stack, copies the stack, clears one of the stacks, finds the maximum value in the other stack, and prints $N$ values of each type (2 per @print@ call).
    956956
    957957The structure of each benchmark implemented is: C with @void *@-based polymorphism, \CFA with the presented features, \CC with templates, and \CC using only class inheritance for polymorphism, called \CCV.
     
    959959hence runtime checks are necessary to safely down-cast objects.
    960960The 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 instead must store generic objects via pointers to separately-allocated objects.
    961 For the print benchmark, idiomatic printing is used: the C and \CFA variants used @stdio.h@, while the \CC and \CCV variants used @iostream@; preliminary tests show this distinction has little runtime impact.
     961For the print benchmark, idiomatic printing is used: the C and \CFA variants used @stdio.h@, while the \CC and \CCV variants used @iostream@; preliminary tests show this distinction has negligible runtime impact.
    962962Note, the C benchmark uses unchecked casts as there is no runtime mechanism to perform such checks, while \CFA and \CC provide type-safety statically.
    963963
     
    10111011                                                                        & \CT{C}        & \CT{\CFA}     & \CT{\CC}      & \CT{\CCV}             \\ \hline
    10121012maximum memory usage (MB)                       & 10001         & 2502          & 2503          & 11253                 \\
    1013 source code size (lines)                        & 247           & 223           & 165           & 339                   \\
     1013source code size (lines)                        & 247           & 222           & 165           & 339                   \\
    10141014redundant type annotations (lines)      & 39            & 2                     & 2                     & 15                    \\
    10151015binary size (KB)                                        & 14            & 229           & 18            & 38                    \\
     
    10191019The C and \CCV variants are generally the slowest with the largest memory footprint, because of their less-efficient memory layout and the pointer-indirection necessary to implement generic types;
    10201020this inefficiency is exacerbated by the second level of generic types in the pair-based benchmarks.
    1021 By contrast, the \CFA and \CC variants run in roughly equivalent time for both the integer and pair of @_Bool@ and @char@ because the storage layout is equivalent.
     1021By contrast, the \CFA and \CC variants run in roughly equivalent time for both the integer and pair of @_Bool@ and @char@ because the storage layout is equivalent, with the inlined libraries (\ie no separate compilation) and greater maturity of the \CC compiler contributing to its lead.
    10221022\CCV is slower than C largely due to the cost of runtime type-checking of down-casts (implemented with @dynamic_cast@);
    10231023There are two outliers in the graph for \CFA: all prints and pop of @pair@.
    10241024Both of these cases result from the complexity of the C-generated polymorphic code, so that the GCC compiler is unable to optimize some dead code and condense nested calls.
    1025 A compiler for \CFA could easily perform these optimizations.
     1025A compiler designed for \CFA could easily perform these optimizations.
    10261026Finally, the binary size for \CFA is larger because of static linking with the \CFA libraries.
    10271027
    1028 \CC performs best because it uses header-only inlined libraries (\ie no separate compilation).
    1029 \CFA and \CC have the advantage of a pre-written generic @pair@ and @stack@ 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 and \CCV does not use the \CC standard template library by construction.
    1030 For \CCV, the definition of @object@ and wrapper classes for @bool@, @char@, @int@, and @const char *@ are included in the line count, which inflates its line count, as an actual object-oriented language would include these in the standard library;
     1028\CFA is also competitive in terms of source code size, measured as a proxy for programmer effort. The line counts in Table~\ref{tab:eval} include implementations of @pair@ and @stack@ types for all four languages for purposes of direct comparison, though it should be noted that \CFA and \CC have pre-written 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 benchmarks to 73 and 54 lines, respectively.
     1029On the other hand, C does not have a generic collections-library in its standard distribution, resulting in frequent reimplementation of such collection types by C programmers.
     1030\CCV does not use the \CC standard template library by construction, and in fact includes the definition of @object@ and wrapper classes for @bool@, @char@, @int@, and @const char *@ in its line count, which inflates this count somewhat, as an actual object-oriented language would include these in the standard library;
    10311031with their omission the \CCV line count is similar to C.
    10321032We 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.
Note: See TracChangeset for help on using the changeset viewer.