Changeset 308880c


Ignore:
Timestamp:
Apr 15, 2017, 2:55:09 PM (7 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:
a381b46
Parents:
67e8e192
Message:

Finish Aaron's editorial pass on paper

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/generic_types/generic_types.tex

    r67e8e192 r308880c  
    957957The experiment uses element types @int@ and @pair( _Bool, char)@, and push $N=40M$ elements on a generic stack, copy the stack, clear one of the stacks, find the maximum value in the other stack, and print $N$ constant values.
    958958
    959 The structure of each benchmark implemented is: C with @void *@-based polymorphism, \CFA with the different presented features, \CC with templates, and \CC using only class inheritance for polymorphism, called \CCV.
     959The 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.
    960960The \CCV variant illustrates an alternative object-oriented idiom where all objects inherit from a base @object@ class, mimicking a Java-like interface;
    961961hence runtime checks are necessary to safely down-cast objects.
    962 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}.
    963 % The 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.
    964 For the print benchmark, idiomatic printing is used: the C and \CFA variants used @cstdio.h@, while the \CC and \CCV variants used @iostream@.
    965 Preliminary tests show the difference has little runtime effect.
    966 %Finally, the C @rand@ function is used generate random numbers.
     962The 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.
     963For the print benchmark, idiomatic printing is used: the C and \CFA variants used @cstdio.h@, while the \CC and \CCV variants used @iostream@; preliminary tests show this distinction has little runtime impact.
    967964
    968965\begin{figure}
     
    10141011\end{table}
    10151012
    1016 Figure~\ref{fig:eval} and Table~\ref{tab:eval} show the benchmark results.
    1017 Each data point is the time for $N = 40M$ function calls or loop iterations, as appropriate.
    1018 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$ 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.
    1019 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@.
    1020 \TODO{} The data shown is the median of 5 consecutive runs of each program, with an initial warm-up run omitted.
     1013Figure~\ref{fig:eval} and Table~\ref{tab:eval} show the results of running the benchmark in Figure~\ref{fig:MicroBenchmark} and its C, \CC, and \CCV equivalents.
     1014The data shown is the median of 5 consecutive runs of each program, with an initial warm-up run omitted.
    10211015All code was compiled at \texttt{-O2} by GCC or G++ 6.2.0, with all \CC code compiled as \CCfourteen.
    10221016The 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.
     
    10241018By 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.
    10251019
    1026 \CC performs best because it uses header-only inlined libraries (i.e., no separate compilation).
     1020\CC performs best because it uses header-only inlined libraries (\ie no separate compilation).
    10271021\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.
    10281022The 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.
     
    10381032\subsection{Polymorphism}
    10391033
    1040 \CC is closest language to \CFA;
    1041 both are extensions to C with source and runtime backwards compatibility, and incremental extensions to C.
     1034\CC is the most similar language to \CFA;
     1035both are extensions to C with source and runtime backwards compatibility.
    10421036The fundamental difference is in their engineering approach to C compatibility and programmer expectation.
    10431037While \CC provides good backwards compatibility with C, it has a steep learning curve for many of its extensions.
    10441038For example, polymorphism is provided via three disjoint mechanisms: overloading, inheritance, and templates.
    10451039The overloading is restricted because resolution does not using the return type, inheritance requires learning object-oriented programming and coping with a restricted nominal-inheritance hierarchy, templates cannot be separately compiled resulting in compilation/code bloat and poor error messages, and determining how these mechanisms interact and which to use is confusing.
    1046 In contrast, \CFA has a single facility for polymorphic code supporting type-safe separate-compilation of polymorphic functions and generic (opaque) types, which uniformly leveraging the C procedural paradigm.
     1040In contrast, \CFA has a single facility for polymorphic code supporting type-safe separate-compilation of polymorphic functions and generic (opaque) types, which uniformly leverage the C procedural paradigm.
    10471041The key mechanism to support separate compilation is \CFA's \emph{explicit} use of assumed properties for a type.
    10481042Until \CC concepts~\citep{C++Concepts} are standardized (anticipated for \CCtwenty), \CC provides no way to specify the requirements of a generic function in code beyond compilation errors during template expansion;
     
    10551049While the Cyclone design provides the efficiency benefits discussed in Section~\ref{sec:generic-apps} for dtype-static polymorphism, it is more restrictive than \CFA's general model.
    10561050
    1057 Objective-C~\citep{obj-c-book} is an industrially successful extensions to C.
     1051Objective-C~\citep{obj-c-book} is an industrially successful extension to C.
    10581052However, Objective-C is a radical departure from C, using an object-oriented model with message-passing.
    10591053Objective-C did not support type-checked generics until recently~\citep{xcode7}, historically using less-efficient and more error-prone runtime checking of object types.
     
    10671061
    10681062D~\citep{D}, Go~\citep{Go}, and Rust~\citep{Rust} are modern, compiled languages with abstraction features similar to \CFA traits, \emph{interfaces} in D and Go and \emph{traits} in Rust.
    1069 However, each language represents significant departures from C in terms of language model, and none has the same level of compatibility with C as \CFA.
     1063However, each language represents a significant departure from C in terms of language model, and none has the same level of compatibility with C as \CFA.
    10701064D and Go are garbage-collected languages, imposing the associated runtime overhead.
    10711065The necessity of accounting for data transfer between managed runtimes and the unmanaged C runtime complicates foreign-function interfaces to C.
     
    10991093\section{Conclusion \& Future Work}
    11001094
    1101 The \CFA goal is to provide an evolutionary pathway for large C development-environments to be more productive and safer, while respecting the talent and skill of C programmers.
     1095The goal of \CFA is to provide an evolutionary pathway for large C development-environments to be more productive and safer, while respecting the talent and skill of C programmers.
    11021096While other programming languages purport to be a better C, they are in fact new and interesting languages in their own right, but not C extensions.
    1103 The purpose of this paper is to introduce \CFA, and showcase two language features that illustrate the \CFA type-system and approaches taken to achieve the evolutionary goal.
     1097The purpose of this paper is to introduce \CFA, and showcase two language features that illustrate the \CFA type-system and approaches taken to achieve the goal of evolutionary C extension.
    11041098The contributions are a powerful type-system using parametric polymorphism and overloading, generic types, and tuples, which all have complex interactions.
    11051099The work is a challenging design, engineering, and implementation exercise.
     
    11071101However, every \CFA feature is different than its \CC counterpart, often with extended functionality, better integration with C and its programmers, and always supporting separate compilation.
    11081102All of these new features are being used by the \CFA development-team to build the \CFA runtime system.
    1109 Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is competitive.
     1103Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is practically applicable.
    11101104
    11111105There is ongoing work on a wide range of \CFA feature extensions, including reference types, exceptions, and concurrent programming primitives.
     
    11201114
    11211115\begin{acks}
    1122 The authors would like to thank Magnus Madsen for valuable editorial feedback.
     1116The authors would like to recognize the design assitance of Glen Ditchfield, Richard Bilson, and Thierry Delisle on the features described in this paper. They also thank Magnus Madsen and three anonymous reviewers for valuable editorial feedback.
    11231117
    11241118This work is supported in part by a corporate partnership with \grantsponsor{Huawei}{Huawei Ltd.}{http://www.huawei.com}\ and the first author's \grantsponsor{NSERC-PGS}{NSERC PGS D}{http://www.nserc-crsng.gc.ca/Students-Etudiants/PG-CS/BellandPostgrad-BelletSuperieures_eng.asp} scholarship.
Note: See TracChangeset for help on using the changeset viewer.