Changeset 4570131


Ignore:
Timestamp:
Apr 14, 2017, 6:12:31 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:
79b8dc3
Parents:
e3de500 (diff), 952d201 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:
doc/generic_types
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/generic_types/evaluation/timing.gp

    re3de500 r4570131  
    1212set boxwidth 0.8
    1313
    14 set ylabel "milliseconds"
    1514set key top left reverse Left
    1615
     
    2120set linetype 4 lc rgb 'green'
    2221
     22set ylabel "milli-seconds"
     23set yrange [0:*] ;
     24
    2325set datafile separator ","
    2426plot for [COL=2:5] 'evaluation/timing.csv' using COL:xticlabels(1) title columnheader
  • doc/generic_types/generic_types.tex

    re3de500 r4570131  
    954954Since all these languages share a subset comprising most of standard C, maximal-performance benchmarks would show little runtime variance, other than in length and clarity of source code.
    955955Instead, the presented benchmarks show the costs of idiomatic use of each language's features to examine common usage.
    956 The benchmarks test 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}.
     956Figure~\ref{fig:MicroBenchmark} 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}.
     957The tests are similar for C and \CC.
     958The first two experiments use element types @int@ and @pair( _Bool, char)@, and push $N=40M$ elements on a generic stack, copy the stack, clear one of the stacks, and find the maximum value in the other stack.
     959The last experiment creates a file and prints $N=40M$ elements of type @int@ and @pair( _Bool, char)@ using a variadic print.
     960
    957961The structure of each 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.
    958962The \CCV variant illustrates an alternative object-oriented idiom where all objects inherit from a base @object@ class, mimicking a Java-like interface;
    959963hence runtime checks are necessary to safely down-cast objects.
    960 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 store generic objects via pointers to separately-allocated objects instead.
    961 For the print benchmark, idiomatic printing is used: the C and \CFA variants use @stdio.h@, while the \CC and \CCV variants use @iostream@.
    962 Preliminary tests show this difference has little runtime effect.
     964The 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}.
     965For the print benchmark, idiomatic printing is used: the C and \CFA variants used @cstdio.h@, while the \CC and \CCV variants used @iostream@.
     966Preliminary tests show the difference has little runtime effect.
    963967Finally, the C @rand@ function is used generate random numbers.
     968
     969\begin{figure}
     970\begin{lstlisting}[xleftmargin=3\parindentlnth,aboveskip=0pt,belowskip=0pt,numbers=left,numberstyle=\tt\small,numberblanklines=false]
     971int main( int argc, char *argv[] ) {
     972        int max = 0;
     973        stack(int) s, t;
     974        REPEAT_TIMED( "push_int", push( &s, 42 ); )
     975        TIMED( "copy_int", t = s; )
     976        TIMED( "clear_int", clear( &s ); )
     977        REPEAT_TIMED( "pop_int", max = max( max, pop( &t ) ); )
     978
     979        stack(pair(_Bool, char)) s1, t1;
     980        pair(_Bool, char) max = { (_Bool)0, '\0' };
     981        REPEAT_TIMED( "push_pair", push( &s1, (pair(_Bool, char)){ (_Bool)0, 'a' } ); )
     982        TIMED( "copy_pair", t1 = s1; )
     983        TIMED( "clear_pair", clear( &s1 ); )
     984        REPEAT_TIMED( "pop_pair", max = max( max, pop( &t1 ) ); )
     985
     986        FILE * out = fopen( "cfa-out.txt", "w" );
     987        REPEAT_TIMED( "print_int", print( out, 42, ":", 42, "\n" ); )
     988        REPEAT_TIMED( "print_pair", print( out, (pair(_Bool, char)){ (_Bool)0, 'a' }, ":",
     989                                                         (pair(_Bool, char)){ (_Bool)0, 'a' }, "\n" ); )
     990        fclose(out);
     991}
     992\end{lstlisting}
     993\caption{Micro-Benchmark}
     994\label{fig:MicroBenchmark}
     995\end{figure}
    964996
    965997\begin{figure}
     
    9751007\newcommand{\CT}[1]{\multicolumn{1}{c}{#1}}
    9761008\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                     \\
     1009                                                        & \CT{C}        & \CT{\CFA}     & \CT{\CC}      &       \CT{\CCV}       \\ \hline
     1010maximum memory usage (MB)       & 10001         & 2501          & 2503          &       11253           \\
     1011source code size (lines)        & 301           & 224           & 188           &       437                     \\
    9801012redundant type annotations (lines)      & 46            & 3                     & 2                     &       15                      \\
    981 binary size (KB)                                        & 18            & 234           & 18            &       42                      \\
     1013binary size (KB)                        & 18            & 234           & 18            &       42                      \\
    9821014\end{tabular}
    9831015\end{table}
     
    10511083SETL~\cite{SETL} is a high-level mathematical programming language, with tuples being one of the primary data types.
    10521084Tuples in SETL allow subscripting, dynamic expansion, and multiple assignment.
    1053 C provides variadic functions through @va_list@ objects, but the programmer is responsible for managing the number of arguments and their types.
     1085C provides variadic functions through @va_list@ objects, but the programmer is responsible for managing the number of arguments and their types, so the mechanism is not type-safe.
    10541086KW-C~\cite{Buhr94a}, a predecessor of \CFA, introduced tuples to C as an extension of the C syntax, taking much of its inspiration from SETL.
    10551087The main contributions of that work were adding MRVF, tuple mass and multiple assignment, and record-field access.
     
    10871119
    10881120
     1121\bibliographystyle{ACM-Reference-Format}
     1122\bibliography{cfa}
     1123
     1124
    10891125\appendix
     1126
    10901127
    10911128\section{BenchMarks}
     
    10931130
    10941131TODO
    1095 
    1096 
    1097 \bibliographystyle{ACM-Reference-Format}
    1098 \bibliography{cfa}
    10991132
    11001133\end{document}
Note: See TracChangeset for help on using the changeset viewer.