Index: doc/generic_types/generic_types.tex =================================================================== --- doc/generic_types/generic_types.tex (revision 67e8e192e166bc9a4f26b93a49b9bc8047bb10ad) +++ doc/generic_types/generic_types.tex (revision 308880c62efc9d218aa37bd1cccefca934608e56) @@ -957,12 +957,9 @@ The 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. -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. +The 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. The \CCV variant illustrates an alternative object-oriented idiom where all objects inherit from a base @object@ class, mimicking a Java-like interface; hence runtime checks are necessary to safely down-cast objects. -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}. -% 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. -For 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 the difference has little runtime effect. -%Finally, the C @rand@ function is used generate random numbers. +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. +For 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. \begin{figure} @@ -1014,9 +1011,6 @@ \end{table} -Figure~\ref{fig:eval} and Table~\ref{tab:eval} show the benchmark results. -Each data point is the time for $N = 40M$ function calls or loop iterations, as 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$ 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. -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. +Figure~\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. +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. @@ -1024,5 +1018,5 @@ 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. -\CC performs best because it uses header-only inlined libraries (i.e., no separate compilation). +\CC performs best because it uses header-only inlined libraries (\ie no separate compilation). \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. 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; with their omission the \CCV line count is similar to C. @@ -1038,11 +1032,11 @@ \subsection{Polymorphism} -\CC is closest language to \CFA; -both are extensions to C with source and runtime backwards compatibility, and incremental extensions to C. +\CC is the most similar language to \CFA; +both are extensions to C with source and runtime backwards compatibility. The fundamental difference is in their engineering approach to C compatibility and programmer expectation. While \CC provides good backwards compatibility with C, it has a steep learning curve for many of its extensions. For example, polymorphism is provided via three disjoint mechanisms: overloading, inheritance, and templates. The 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. -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. +In 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. The key mechanism to support separate compilation is \CFA's \emph{explicit} use of assumed properties for a type. Until \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; @@ -1055,5 +1049,5 @@ While 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. -Objective-C~\citep{obj-c-book} is an industrially successful extensions to C. +Objective-C~\citep{obj-c-book} is an industrially successful extension to C. However, Objective-C is a radical departure from C, using an object-oriented model with message-passing. Objective-C did not support type-checked generics until recently~\citep{xcode7}, historically using less-efficient and more error-prone runtime checking of object types. @@ -1067,5 +1061,5 @@ D~\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. -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. +However, 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. D and Go are garbage-collected languages, imposing the associated runtime overhead. The necessity of accounting for data transfer between managed runtimes and the unmanaged C runtime complicates foreign-function interfaces to C. @@ -1099,7 +1093,7 @@ \section{Conclusion \& Future Work} -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. +The 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. While 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. -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. +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 goal of evolutionary C extension. The contributions are a powerful type-system using parametric polymorphism and overloading, generic types, and tuples, which all have complex interactions. The work is a challenging design, engineering, and implementation exercise. @@ -1107,5 +1101,5 @@ However, 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. All of these new features are being used by the \CFA development-team to build the \CFA runtime system. -Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is competitive. +Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is practically applicable. There is ongoing work on a wide range of \CFA feature extensions, including reference types, exceptions, and concurrent programming primitives. @@ -1120,5 +1114,5 @@ \begin{acks} -The authors would like to thank Magnus Madsen for valuable editorial feedback. +The 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. This 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.