Changeset 278516c


Ignore:
Timestamp:
Apr 25, 2017, 11:59:02 AM (8 years ago)
Author:
Thierry Delisle <tdelisle@…>
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:
592b9fa, cf67057
Parents:
026a0f5 (diff), 89a9be2 (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:
10 edited

Legend:

Unmodified
Added
Removed

  • doc/generic_types/evaluation/Makefile

    r026a0f5 r278516c  
     1CC = gcc
    12CFA = cfa
    23DEPFLAGS = -MMD -MP
    … …  
    67endif
    78CXXFLAGS = $(CFLAGS) --std=c++14
     9MAKEFILE_NAME = ${firstword ${MAKEFILE_LIST}}
    810
    9 .PHONY: all clean distclean run-c run-cpp run-cfa run
     11.PHONY : all clean run-c run-cpp run-cfa run
    1012
    11 all: c-bench cpp-bench cfa-bench cpp-vbench
     13all : c-bench cpp-bench cpp-vbench cfa-bench
    1214
    1315# rewrite object generation to auto-determine deps
    … …  
    1719
    1820c-%.o : c-%.c
    19 c-%.o : c-%.c c-%.d
    2021        $(COMPILE.c) $(OUTPUT_OPTION) -c $<
    2122
    2223cpp-%.o : cpp-%.cpp
    23 cpp-%.o : cpp-%.cpp cpp-%.d
    2424        $(COMPILE.cpp) $(OUTPUT_OPTION) -c $<
    2525
    2626cfa-%.o : cfa-%.c
    27 cfa-%.o : cfa-%.c cfa-%.d
    2827        $(COMPILE.cfa) $(OUTPUT_OPTION) -c $<
    2928
    30 COBJS = c-stack.o c-pair.o c-print.o
    31 CPPOBJS =
    32 CPPVOBJS = cpp-vstack.o
    33 CFAOBJS = cfa-stack.o cfa-pair.o cfa-print.o
     29COBJS = c-stack.o c-pair.o c-print.o c-bench.o
     30CPPOBJS = cpp-bench.o
     31CPPVOBJS = cpp-vstack.o cpp-vbench.o
     32CFAOBJS = cfa-stack.o cfa-pair.o cfa-print.o cfa-bench.o
    3433
    35 CFILES = c-bench.c bench.h $(COBJS:.o=.h) $(COBJS:.o=.c)
    36 CPPFILES = cpp-bench.cpp bench.hpp cpp-stack.hpp cpp-pair.hpp cpp-print.hpp
    37 CPPVFILES = cpp-vbench.cpp bench.hpp object.hpp $(CPPVOBJS:.o=.hpp) $(CPPVOBJS:.o=.cpp) cpp-vprint.hpp
    38 CFAFILES = cfa-bench.c bench.h $(CFAOBJS:.o=.h) $(CFAOBJS:.o=.c)
     34${COBJS} ${CPPOBJS} ${CPPVOBJS} ${CFAOBJS} : ${MAKEFILE_NAME}
    3935
    40 c-bench: c-bench.c c-bench.d $(COBJS)
    41         $(COMPILE.c) -o $@ $< $(COBJS) $(LDFLAGS)
     36CFILES = bench.h $(patsubst c-bench.h,,$(COBJS:.o=.h)) $(COBJS:.o=.c)
     37CPPFILES = bench.hpp cpp-stack.hpp cpp-pair.hpp cpp-print.hpp $(CPPOBJS:.o=.cpp)
     38CPPVFILES = bench.hpp object.hpp cpp-vprint.hpp $(patsubst cpp-vbench.hpp,,$(CPPVOBJS:.o=.hpp)) $(CPPVOBJS:.o=.cpp)
     39CFAFILES = bench.h $(patsubst cfa-bench.h,,$(CFAOBJS:.o=.h)) $(CFAOBJS:.o=.c)
    4240
    43 cpp-bench: cpp-bench.cpp cpp-bench.d $(CPPOBJS)
    44         $(COMPILE.cpp) -o $@ $< $(CPPOBJS) $(LDFLAGS)
     41c-bench : $(COBJS) c-bench.o
     42        $(COMPILE.c) $(LDFLAGS) $^ -o $@
    4543
    46 cpp-vbench: cpp-vbench.cpp cpp-vbench.d $(CPPVOBJS)
    47         $(COMPILE.cpp) -o $@ $< $(CPPVOBJS) $(LDFLAGS)
     44cpp-bench : $(CPPOBJS) cpp-bench.o
     45        $(COMPILE.cpp) $(LDFLAGS) $^ -o $@
    4846
    49 cfa-bench: cfa-bench.c cfa-bench.d $(CFAOBJS)
    50         $(COMPILE.cfa) -o $@ $< $(CFAOBJS) $(LDFLAGS)
     47cpp-vbench : $(CPPVOBJS) cpp-vbench.o
     48        $(COMPILE.cpp) $(LDFLAGS) $^ -o $@
    5149
    52 clean:
    53         -rm $(COBJS) c-bench
    54         -rm $(CPPOBJS) cpp-bench
    55         -rm $(CPPVOBJS) cpp-vbench
    56         -rm $(CFAOBJS) cfa-bench
     50cfa-bench : $(CFAOBJS) cfa-bench.o
     51        $(COMPILE.cfa) $(LDFLAGS) $^ -o $@
    5752
    58 distclean: clean
    59         -rm $(COBJS:.o=.d) c-bench.d
    60         -rm $(CPPOBJS:.o=.d) cpp-bench.d
    61         -rm $(CPPVOBJS:.o=.d) cpp-vbench.d
    62         -rm $(CFAOBJS:.o=.d) cfa-bench.d
     53# include dependency files
     54-include $(COBJS:.o=.d)
     55-include $(CPPOBJS:.o=.d)
     56-include $(CPPVOBJS:.o=.d)
     57-include $(CFAOBJS:.o=.d)
    6358
    64 run-c: c-bench
     59clean :
     60        rm -f $(COBJS) $(COBJS:.o=.d) c-bench
     61        rm -f $(CPPOBJS) $(CPPOBJS:.o=.d) cpp-bench
     62        rm -f $(CPPVOBJS) $(CPPVOBJS:.o=.d) cpp-vbench
     63        rm -f $(CFAOBJS) $(CFAOBJS:.o=.d) cfa-bench
     64
     65run-c : c-bench
    6566        @echo
    6667        @echo '## C ##'
    67         @/usr/bin/time -f 'max_memory:\t%M kilobytes' ./c-bench
     68        @/usr/bin/time -f 'max_memory:\t%M kilobytes' ./$<
    6869        @printf 'source_size:\t%8d lines\n' `cat $(CFILES) | wc -l`
    6970        @printf 'redundant_type_annotations:%8d lines\n' `cat $(CFILES) | fgrep '/***/' -c`
    70         @printf 'binary_size:\t%8d bytes\n' `stat -c %s c-bench`
     71        @printf 'binary_size:\t%8d bytes\n' `stat -c %s $<`
    7172
    72 run-cfa: cfa-bench
     73run-cpp : cpp-bench
     74        @echo
     75        @echo '## C++ ##'
     76        @/usr/bin/time -f 'max_memory:\t %M kilobytes' ./$<
     77        @printf 'source_size:\t%8d lines\n' `cat $(CPPFILES) | wc -l`
     78        @printf 'redundant_type_annotations:%8d lines\n' `cat $(CPPFILES) | fgrep '/***/' -c`
     79        @printf 'binary_size:\t%8d bytes\n' `stat -c %s $<`
     80
     81run-cppv : cpp-vbench
     82        @echo
     83        @echo '## C++obj ##'
     84        @/usr/bin/time -f 'max_memory:\t%M kilobytes' ./$<
     85        @printf 'source_size:\t%8d lines\n' `cat $(CPPVFILES) | wc -l`
     86        @printf 'redundant_type_annotations:%8d lines\n' `cat $(CPPVFILES) | fgrep '/***/' -c`
     87        @printf 'binary_size:\t%8d bytes\n' `stat -c %s $<`
     88
     89run-cfa : cfa-bench
    7390        @echo
    7491        @echo '## Cforall ##'
    75         @/usr/bin/time -f 'max_memory:\t %M kilobytes' ./cfa-bench
     92        @/usr/bin/time -f 'max_memory:\t %M kilobytes' ./$<
    7693        @printf 'source_size:\t%8d lines\n' `cat $(CFAFILES) | wc -l`
    7794        @printf 'redundant_type_annotations:%8d lines\n' `cat $(CFAFILES) | fgrep '/***/' -c`
    78         @printf 'binary_size:\t%8d bytes\n' `stat -c %s cfa-bench`
     95        @printf 'binary_size:\t%8d bytes\n' `stat -c %s $<`
    7996
    80 run-cpp: cpp-bench
    81         @echo
    82         @echo '## C++ ##'
    83         @/usr/bin/time -f 'max_memory:\t %M kilobytes' ./cpp-bench
    84         @printf 'source_size:\t%8d lines\n' `cat $(CPPFILES) | wc -l`
    85         @printf 'redundant_type_annotations:%8d lines\n' `cat $(CPPFILES) | fgrep '/***/' -c`
    86         @printf 'binary_size:\t%8d bytes\n' `stat -c %s cpp-bench`
    87 
    88 run-cppv: cpp-vbench
    89         @echo
    90         @echo '## C++obj ##'
    91         @/usr/bin/time -f 'max_memory:\t%M kilobytes' ./cpp-vbench
    92         @printf 'source_size:\t%8d lines\n' `cat $(CPPVFILES) | wc -l`
    93         @printf 'redundant_type_annotations:%8d lines\n' `cat $(CPPVFILES) | fgrep '/***/' -c`
    94         @printf 'binary_size:\t%8d bytes\n' `stat -c %s cpp-vbench`
    95 
    96 run: run-c run-cfa run-cpp run-cppv
    97 
    98 # so make doesn't fail without dependency files
    99 %.d: ;
    100 
    101 # so make won't delete dependency files
    102 .PRECIOUS: %.d
    103 
    104 # include dependency files
    105 -include: $(COBJS:.o=.d)
    106 -include: $(CPPOBJS:.o=.d)
    107 -include: $(CFAOBJS:.o=.d)
    108 -include: c-bench.d
    109 -include: cpp-bench.d
    110 -include: cfa-bench.d
     97run : run-c run-cfa run-cpp run-cppv

  • doc/generic_types/evaluation/c-bench.c

    r026a0f5 r278516c  
    3939
    4040int main(int argc, char** argv) {
    41         FILE * out = fopen("c-out.txt", "w");
     41        FILE * out = fopen("/dev/null", "w");
    4242        int maxi = 0, vali = 42;
    4343        struct stack si = new_stack(), ti;

  • doc/generic_types/evaluation/c-stack.c

    r026a0f5 r278516c  
    1111void copy_stack(struct stack* s, const struct stack* t, void* (*copy)(const void*)) {
    1212        struct stack_node** crnt = &s->head;
    13         struct stack_node* next = t->head;
    14         while ( next ) {
     13        for ( struct stack_node* next = t->head; next; next = next->next ) {
    1514                *crnt = malloc(sizeof(struct stack_node)); /***/
    1615                **crnt = (struct stack_node){ copy(next->value) }; /***/
    1716                crnt = &(*crnt)->next;
    18                 next = next->next;
    1917        }
    2018        *crnt = 0;
    … …  
    2220
    2321void clear_stack(struct stack* s, void (*free_el)(void*)) {
    24         struct stack_node* next = s->head;
    25         while ( next ) {
     22    for ( struct stack_node* next = s->head; next; ) {
    2623                struct stack_node* crnt = next;
    2724                next = crnt->next;

  • doc/generic_types/evaluation/cfa-bench.c

    r026a0f5 r278516c  
    66
    77int main( int argc, char *argv[] ) {
    8         FILE * out = fopen( "cfa-out.txt", "w" );
     8        FILE * out = fopen( "/dev/null", "w" );
    99        int maxi = 0, vali = 42;
    1010        stack(int) si, ti;

  • doc/generic_types/evaluation/cfa-stack.c

    r026a0f5 r278516c  
    1111forall(otype T) void ?{}(stack(T)* s, stack(T) t) {
    1212        stack_node(T)** crnt = &s->head;
    13         stack_node(T)* next = t.head;
    14         while ( next ) {
     13        for ( stack_node(T)* next = t.head; next; next = next->next ) {
    1514                *crnt = ((stack_node(T)*)malloc()){ next->value }; /***/
    1615                stack_node(T)* acrnt = *crnt;
    1716                crnt = &acrnt->next;
    18                 next = next->next;
    1917        }
    2018        *crnt = 0;
    … …  
    4644
    4745forall(otype T) void clear(stack(T)* s) {
    48         stack_node(T)* next = s->head;
    49         while ( next ) {
     46    for ( stack_node(T)* next = s->head; next; ) {
    5047                stack_node(T)* crnt = next;
    5148                next = crnt->next;

  • doc/generic_types/evaluation/cpp-bench.cpp

    r026a0f5 r278516c  
    77
    88int main(int argc, char** argv) {
    9         std::ofstream out{"cpp-out.txt"};
     9        std::ofstream out{"/dev/null"};
    1010        int maxi = 0, vali = 42;
    1111        stack<int> si, ti;

  • doc/generic_types/evaluation/cpp-stack.hpp

    r026a0f5 r278516c  
    1313        void copy(const stack<T>& o) {
    1414                node** crnt = &head;
    15                 node* next = o.head;
    16                 while ( next ) {
     15                for ( node* next = o.head; next; next = next->next ) {
    1716                        *crnt = new node{ next->value }; /***/
    1817                        crnt = &(*crnt)->next;
    19                         next = next->next;
    2018                }
    2119                *crnt = nullptr;
    … …  
    2321public:
    2422        void clear() {
    25                 node* next = head;
    26                 while ( next ) {
     23            for ( node* next = head; next; ) {
    2724                        node* crnt = next;
    2825                        next = crnt->next;

  • doc/generic_types/evaluation/cpp-vbench.cpp

    r026a0f5 r278516c  
    77
    88int main(int argc, char** argv) {
    9         std::ofstream out{"cpp-vout.txt"};
     9        std::ofstream out{"/dev/null"};
    1010        integer maxi{ 0 }, vali{ 42 };
    1111        stack si, ti;

  • doc/generic_types/evaluation/cpp-vstack.cpp

    r026a0f5 r278516c  
    66void stack::copy(const stack& o) {
    77        node** crnt = &head;
    8         node* next = o.head;
    9         while ( next ) {
     8        for ( node* next = o.head; next; next = next->next ) {
    109                *crnt = new node{ *next->value };
    1110                crnt = &(*crnt)->next;
    12                 next = next->next;
    1311        }
    1412        *crnt = nullptr;
    … …  
    3533
    3634void stack::clear() {
    37         node* next = head;
    38         while ( next ) {
     35    for ( node* next = head; next; ) {
    3936                node* crnt = next;
    4037                next = crnt->next;

  • doc/generic_types/generic_types.tex

    r026a0f5 r278516c  
    232232int comp( const void * t1, const void * t2 ) { return *(double *)t1 < *(double *)t2 ? -1 :
    233233                                *(double *)t2 < *(double *)t1 ? 1 : 0; }
    234 double key = 5.0, vals[10] = { /* 10 floating-point values */ };
     234double key = 5.0, vals[10] = { /* 10 sorted floating-point values */ };
    235235double * val = (double *)bsearch( &key, vals, 10, sizeof(vals[0]), comp );      $\C{// search sorted array}$
    236236\end{lstlisting}
    … …  
    354354One of the known shortcomings of standard C is that it does not provide reusable type-safe abstractions for generic data structures and algorithms.
    355355Broadly speaking, there are three approaches to implement abstract data-structures in C.
    356 One approach is to write bespoke data structures for each context in which they are needed.
     356One approach is to write bespoke data-structures for each context in which they are needed.
    357357While this approach is flexible and supports integration with the C type-checker and tooling, it is also tedious and error-prone, especially for more complex data structures.
    358358A second approach is to use @void *@--based polymorphism, \eg the C standard-library functions @bsearch@ and @qsort@; an approach which does allow reuse of code for common functionality.
    … …  
    542542\end{lstlisting}
    543543where the tuple variable-name serves the same purpose as the parameter name(s).
    544 Tuple variables can be composed of any types, except for array types, since array sizes are generally unknown.
     544Tuple variables can be composed of any types, except for array types, since array sizes are generally unknown in C.
    545545
    546546One way to access the tuple-variable components is with assignment or composition:
    … …  
    552552\begin{lstlisting}
    553553[int, int] * p = &qr;                                           $\C{// tuple pointer}$
    554 int rem = qr.1;                                                         $\C{// access remainder}$
    555 int quo = div( 13, 5 ).0;                                       $\C{// access quotient}$
    556 p->0 = 5;                                                                       $\C{// change quotient}$
    557 bar( qr.1, qr );                                                        $\C{// pass remainder and quotient/remainder}$
    558 rem = [42, div( 13, 5 )].0.1;                           $\C{// access 2nd component of 1st component of tuple expression}$
     554int rem = qr`.1`;                                                       $\C{// access remainder}$
     555int quo = div( 13, 5 )`.0`;                                     $\C{// access quotient}$
     556p`->0` = 5;                                                                     $\C{// change quotient}$
     557bar( qr`.1`, qr );                                                      $\C{// pass remainder and quotient/remainder}$
     558rem = [42, div( 13, 5 )]`.0.1`;                         $\C{// access 2nd component of 1st component of tuple expression}$
    559559\end{lstlisting}
    560560
    … …  
    616616This semantics means mass assignment differs from C cascading assignment (\eg @a = b = c@) in that conversions are applied in each individual assignment, which prevents data loss from the chain of conversions that can happen during a cascading assignment.
    617617For example, @[y, x] = 3.14@ performs the assignments @y = 3.14@ and @x = 3.14@, yielding @y == 3.14@ and @x == 3@;
    618 whereas C cascading assignment @y = x = 3.14@ performs the assignments @x = 3.14@ and @y = x@, yielding @3@ in @y@ and @x@.
     618whereas, C cascading assignment @y = x = 3.14@ performs the assignments @x = 3.14@ and @y = x@, yielding @3@ in @y@ and @x@.
    619619Finally, tuple assignment is an expression where the result type is the type of the left-hand side of the assignment, just like all other assignment expressions in C.
    620620This example shows mass, multiple, and cascading assignment used in one expression:
    … …  
    742742\end{lstlisting}
    743743Hence, function parameter and return lists are flattened for the purposes of type unification allowing the example to pass expression resolution.
    744 This relaxation is possible by extending the thunk scheme described by \citet{Bilson03}.
     744This relaxation is possible by extending the thunk scheme described by~\citet{Bilson03}.
    745745Whenever a candidate's parameter structure does not exactly match the formal parameter's structure, a thunk is generated to specialize calls to the actual function:
    746746\begin{lstlisting}
    … …  
    748748\end{lstlisting}
    749749so the thunk provides flattening and structuring conversions to inferred functions, improving the compatibility of tuples and polymorphism.
    750 These thunks take advantage of GCC C nested-functions to produce closures that have the usual function pointer signature.
     750These thunks take advantage of GCC C nested-functions to produce closures that have the usual function-pointer signature.
    751751
    752752
    … …  
    829829\subsection{Implementation}
    830830
    831 Tuples are implemented in the \CFA translator via a transformation into generic types.
     831Tuples are implemented in the \CFA translator via a transformation into \emph{generic types}.
    832832For each $N$, the first time an $N$-tuple is seen in a scope a generic type with $N$ type parameters is generated, \eg:
    833833\begin{lstlisting}
    … …  
    10861086Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is practically applicable.
    10871087
    1088 There is ongoing work on a wide range of \CFA feature extensions, including reference types, exceptions, concurrent primitives and modules.
     1088There is ongoing work on a wide range of \CFA feature extensions, including reference types, arrays with size, exceptions, concurrent primitives and modules.
    10891089(While all examples in the paper compile and run, a public beta-release of \CFA will take another 8--12 months to finalize these additional extensions.)
    10901090In addition, there are interesting future directions for the polymorphism design.
    … …  
    10921092\CFA polymorphic functions use dynamic virtual-dispatch;
    10931093the runtime overhead of this approach is low, but not as low as inlining, and it may be beneficial to provide a mechanism for performance-sensitive code.
    1094 Two promising approaches are an @inline@ annotation at polymorphic function call sites to create a template-specialization of the function (provided the code is visible) or placing an @inline@ annotation on polymorphic function-definitions to instantiate a specialized version for some set of types.
     1094Two promising approaches are an @inline@ annotation at polymorphic function call sites to create a template-specialization of the function (provided the code is visible) or placing an @inline@ annotation on polymorphic function-definitions to instantiate a specialized version for some set of types (\CC template specialization).
    10951095These approaches are not mutually exclusive and allow performance optimizations to be applied only when necessary, without suffering global code-bloat.
    10961096In general, we believe separate compilation, producing smaller code, works well with loaded hardware-caches, which may offset the benefit of larger inlined-code.
    … …  
    11171117Throughout, @/***/@ designates a counted redundant type annotation.
    11181118
    1119 \medskip\noindent
     1119\smallskip\noindent
    11201120\CFA
    11211121\begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
Note: See TracChangeset for help on using the changeset viewer.