Changeset 1504536


Ignore:
Timestamp:
Apr 14, 2017, 5:03:43 PM (4 years ago)
Author:
Peter A. Buhr <pabuhr@…>
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:
952d201
Parents:
bbe856c (diff), 3fb7f5e (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 plg2:software/cfa/cfa-cc

Location:
doc/generic_types
Files:
18 edited

Legend:

Unmodified
Added
Removed
  • doc/generic_types/evaluation/Makefile

    rbbe856c r1504536  
    3333CFAOBJS = cfa-stack.o cfa-pair.o cfa-print.o
    3434
     35CFILES = c-bench.c bench.h $(COBJS:.o=.h) $(COBJS:.o=.c)
     36CPPFILES = cpp-bench.cpp bench.hpp cpp-stack.hpp cpp-print.hpp
     37CPPVFILES = cpp-vbench.cpp bench.hpp object.hpp $(CPPVOBJS:.o=.hpp) $(CPPVOBJS:.o=.cpp) cpp-vprint.hpp
     38CFAFILES = cfa-bench.c bench.h cfa-stack.h cfa-print.h cfa-stack.c cfa-print.c
     39
    3540c-bench: c-bench.c c-bench.d $(COBJS)
    3641        $(COMPILE.c) -o $@ $< $(COBJS) $(LDFLAGS)
     
    6166        @echo '## C ##'
    6267        @/usr/bin/time -f 'max_memory:\t%M kilobytes' ./c-bench
    63         @printf 'source_size:\t%8d lines\n' `cat c-bench.c bench.h c-stack.{h,c} c-pair.{h,c} c-print.{h,c} | wc -l`
     68        @printf 'source_size:\t%8d lines\n' `cat $(CFILES) | wc -l`
     69        @printf 'redundant_type_annotations:%8d count\n' `cat $(CFILES) | fgrep '/***/' -c`
    6470        @printf 'binary_size:\t%8d bytes\n' `stat -c %s c-bench`
    6571
     
    6874        @echo '## Cforall ##'
    6975        @/usr/bin/time -f 'max_memory:\t %M kilobytes' ./cfa-bench
    70         @printf 'source_size:\t%8d lines\n' `cat cfa-bench.c bench.h cfa-stack.h cfa-stack.c cfa-print.h cfa-print.c | wc -l`
     76        @printf 'source_size:\t%8d lines\n' `cat $(CFAFILES) | wc -l`
     77        @printf 'redundant_type_annotations:%8d count\n' `cat $(CFAFILES) | fgrep '/***/' -c`
    7178        @printf 'binary_size:\t%8d bytes\n' `stat -c %s cfa-bench`
    7279
     
    7582        @echo '## C++ ##'
    7683        @/usr/bin/time -f 'max_memory:\t %M kilobytes' ./cpp-bench
    77         @printf 'source_size:\t%8d lines\n' `cat cpp-bench.cpp bench.hpp cpp-stack.hpp cpp-print.hpp | wc -l`
     84        @printf 'source_size:\t%8d lines\n' `cat $(CPPFILES) | wc -l`
     85        @printf 'redundant_type_annotations:%8d count\n' `cat $(CPPFILES) | fgrep '/***/' -c`
    7886        @printf 'binary_size:\t%8d bytes\n' `stat -c %s cpp-bench`
    7987
     
    8290        @echo '## C++ virtual ##'
    8391        @/usr/bin/time -f 'max_memory:\t%M kilobytes' ./cpp-vbench
    84         @printf 'source_size:\t%8d lines\n' `cat cpp-vbench.cpp bench.hpp object.hpp cpp-vstack.{hpp,cpp} cpp-vprint.hpp | wc -l`
     92        @printf 'source_size:\t%8d lines\n' `cat $(CPPVFILES) | wc -l`
     93        @printf 'redundant_type_annotations:%8d count\n' `cat $(CPPVFILES) | fgrep '/***/' -c`
    8594        @printf 'binary_size:\t%8d bytes\n' `stat -c %s cpp-vbench`
    8695
  • doc/generic_types/evaluation/bench.h

    rbbe856c r1504536  
    2020}
    2121
    22 #define REPEAT_TIMED(name, code) TIMED( name, for (int _i = 0; _i < N; ++_i) { code } )
     22#define REPEAT_N_TIMED(name, n, code) TIMED( name, for (int _i = 0; _i < n; ++_i) { code } )
     23
     24#define REPEAT_TIMED(name, code) REPEAT_N_TIMED(name, N, code)
  • doc/generic_types/evaluation/bench.hpp

    rbbe856c r1504536  
    2121}
    2222
    23 #define REPEAT_TIMED(name, code) TIMED( name, for (int _i = 0; _i < N; ++_i) { code } )
     23#define REPEAT_N_TIMED(name, n, code) TIMED( name, for (int _i = 0; _i < n; ++_i) { code } )
     24
     25#define REPEAT_TIMED(name, code) REPEAT_N_TIMED(name, N, code)
  • doc/generic_types/evaluation/c-bench.c

    rbbe856c r1504536  
    77
    88_Bool* new_bool( _Bool b ) {
    9         _Bool* q = malloc(sizeof(_Bool));
     9        _Bool* q = malloc(sizeof(_Bool)); /***/
    1010        *q = b;
    1111        return q;
     
    1313
    1414char* new_char( char c ) {
    15         char* q = malloc(sizeof(char));
     15        char* q = malloc(sizeof(char)); /***/
    1616        *q = c;
    1717        return q;
     
    1919
    2020int* new_int( int i ) {
    21         int* q = malloc(sizeof(int));
     21        int* q = malloc(sizeof(int)); /***/
    2222        *q = i;
    2323        return q;
    2424}
    2525
    26 void* copy_bool( const void* p ) { return new_bool( *(const _Bool*)p ); }
     26void* copy_bool( const void* p ) { return new_bool( *(const _Bool*)p ); } /***/
    2727
    28 void* copy_char( const void* p ) { return new_char( *(const char*)p ); }
     28void* copy_char( const void* p ) { return new_char( *(const char*)p ); } /***/
    2929
    30 void* copy_int( const void* p ) { return new_int( *(const int*)p ); }
     30void* copy_int( const void* p ) { return new_int( *(const int*)p ); } /***/
    3131
    32 void* copy_pair_bool_char( const void* p ) { return copy_pair( p, copy_bool, copy_char ); }
     32void* copy_pair_bool_char( const void* p ) { return copy_pair( p, copy_bool, copy_char ); } /***/
    3333
    34 void free_pair_bool_char( void* p ) { free_pair( p, free, free ); }
     34void free_pair_bool_char( void* p ) { free_pair( p, free, free ); } /***/
    3535
    3636int cmp_bool( const void* a, const void* b ) {
    37         return *(const _Bool*)a == *(const _Bool*)b ? 0 : *(const _Bool*)a < *(const _Bool*)b ? -1 : 1;
     37        return *(const _Bool*)a == *(const _Bool*)b ? 0 : *(const _Bool*)a < *(const _Bool*)b ? -1 : 1; /***/
    3838}
    3939
    4040int cmp_char( const void* a, const void* b ) {
    41         return *(const char*)a == *(const char*)b ? 0 : *(const char*)a < *(const char*)b ? -1 : 1;
     41        return *(const char*)a == *(const char*)b ? 0 : *(const char*)a < *(const char*)b ? -1 : 1; /***/
    4242}
    4343
    4444int main(int argc, char** argv) {
     45        FILE* out = fopen("c-out.txt", "w");
    4546        srand(20171025);
    4647
     
    5253        struct stack t;
    5354        TIMED( "copy_int",
    54                 copy_stack(&t, &s, copy_int);
     55                copy_stack(&t, &s, copy_int); /***/
    5556        )
    5657
    5758        TIMED( "clear_int",
    58                 clear_stack(&s, free);
     59                clear_stack(&s, free); /***/
    5960        )
    6061
    6162        int max = 0;
    6263        REPEAT_TIMED( "pop_int",
    63                 int* x = pop_stack(&t);
     64                int* x = pop_stack(&t); /***/
    6465                if ( *x > max ) { max = *x; }
    6566                free(x);
     67        )
     68        print( out, "d", max, "\n" ); /***/
     69
     70        REPEAT_N_TIMED( "print_int", N/2,
     71                print( out, "dsds", rand(), ":", rand(), "\n" ); /***/
    6672        )
    6773
     
    7379        struct stack t2;
    7480        TIMED( "copy_bool_char",
    75                 copy_stack(&t2, &s2, copy_pair_bool_char);
     81                copy_stack(&t2, &s2, copy_pair_bool_char); /***/
    7682        )
    7783
    7884        TIMED( "clear_bool_char",
    79                 clear_stack(&s2, free_pair_bool_char);
     85                clear_stack(&s2, free_pair_bool_char); /***/
    8086        )
    8187
    8288        struct pair* max2 = new_pair( new_bool(0), new_char('\0') );
    8389        REPEAT_TIMED( "pop_bool_char",
    84                 struct pair* x = pop_stack(&t2);
    85                 if ( cmp_pair( x, max2, cmp_bool, cmp_char ) > 0 ) {
    86                         free_pair_bool_char( max2 );
     90                struct pair* x = pop_stack(&t2); /***/
     91                if ( cmp_pair( x, max2, cmp_bool, cmp_char ) > 0 ) { /***/
     92                        free_pair_bool_char( max2 ); /***/
    8793                        max2 = x;
    8894                } else {
    89                         free_pair_bool_char( x );
     95                        free_pair_bool_char( x ); /***/
    9096                }
    9197        )
    92         free_pair_bool_char( max2 );
     98        print( out, "pbc", *max2, "\n" ); /***/
     99        free_pair_bool_char( max2 ); /***/
    93100
    94         FILE* out = fopen("c-out.txt", "w");
    95         REPEAT_TIMED( "print_int",
    96                 print( out, "dsds", rand(), ":", rand(), "\n" );
     101        REPEAT_N_TIMED( "print_pair", N/2,
     102                struct pair p1 = ((struct pair){ new_bool(rand() & 0x1), new_char(rand() & 0x7F) }); /***/
     103                struct pair p2 = ((struct pair){ new_bool(rand() & 0x1), new_char(rand() & 0x7F) }); /***/
     104                print( out, "pbcspbcs", p1, ":", p2, "\n" ); /***/
     105                free(p1.first); free(p1.second); /***/
     106                free(p2.first); free(p2.second); /***/
    97107        )
    98 
    99         REPEAT_TIMED( "print_pair",
    100                 struct pair p1 = ((struct pair){ new_bool(rand() & 0x1), new_char(rand() & 0x7F) });
    101                 struct pair p2 = ((struct pair){ new_bool(rand() & 0x1), new_char(rand() & 0x7F) });
    102                 print( out, "pbcspbcs", p1, ":", p2, "\n" );
    103                 free(p1.first); free(p1.second);
    104                 free(p2.first); free(p2.second);
    105         )
     108       
    106109        fclose(out);
    107110}
  • doc/generic_types/evaluation/c-pair.c

    rbbe856c r1504536  
    33
    44struct pair* new_pair(void* first, void* second) {
    5         struct pair* p = malloc(sizeof(struct pair));
    6         *p = (struct pair){ first, second };
     5        struct pair* p = malloc(sizeof(struct pair)); /***/
     6        *p = (struct pair){ first, second }; /***/
    77        return p;
    88}
  • doc/generic_types/evaluation/c-print.c

    rbbe856c r1504536  
    1717void print_fmt(FILE* out, char fmt, void* p) {
    1818        switch( fmt ) {
    19         case 's': print_string(out, (const char*)p); break;
    20         case 'b': print_bool(out, *(_Bool*)p); break;
    21         case 'c': print_char(out, *(char*)p); break;
    22         case 'd': print_int(out, *(int*)p); break;
     19        case 's': print_string(out, (const char*)p); break; /***/
     20        case 'b': print_bool(out, *(_Bool*)p); break; /***/
     21        case 'c': print_char(out, *(char*)p); break; /***/
     22        case 'd': print_int(out, *(int*)p); break; /***/
    2323        }
    2424}
     
    2929        for (const char* it = fmt; *it; ++it) {
    3030                switch( *it ) {
    31                 case 's': print_string(out, va_arg(args, const char*)); break;
    32                 case 'b': print_bool(out, va_arg(args, int)); break;
    33                 case 'c': print_char(out, va_arg(args, int)); break;
    34                 case 'd': print_int(out, va_arg(args, int)); break;
     31                case 's': print_string(out, va_arg(args, const char*)); break; /***/
     32                case 'b': print_bool(out, va_arg(args, int)); break; /***/
     33                case 'c': print_char(out, va_arg(args, int)); break; /***/
     34                case 'd': print_int(out, va_arg(args, int)); break; /***/
    3535                case 'p': {
    36                         const struct pair x = va_arg(args, const struct pair);
     36                        const struct pair x = va_arg(args, const struct pair); /***/
    3737                        fprintf(out, "[");
    38                         print_fmt(out, *++it, x.first);
     38                        print_fmt(out, *++it, x.first); /***/
    3939                        fprintf(out, ", ");
    40                         print_fmt(out, *++it, x.second);
     40                        print_fmt(out, *++it, x.second); /***/
    4141                        fprintf(out, "]");
    4242                        break;
  • doc/generic_types/evaluation/c-stack.c

    rbbe856c r1504536  
    88
    99struct stack new_stack() {
    10         return (struct stack){ NULL };
     10        return (struct stack){ NULL }; /***/
    1111}
    1212
     
    1515        struct stack_node* next = t->head;
    1616        while ( next ) {
    17                 *crnt = malloc(sizeof(struct stack_node));
    18                 **crnt = (struct stack_node){ copy(next->value) };
     17                *crnt = malloc(sizeof(struct stack_node)); /***/
     18                **crnt = (struct stack_node){ copy(next->value) }; /***/
    1919                crnt = &(*crnt)->next;
    2020                next = next->next;
     
    3939
    4040void push_stack(struct stack* s, void* value) {
    41         struct stack_node* n = malloc(sizeof(struct stack_node));
    42         *n = (struct stack_node){ value, s->head };
     41        struct stack_node* n = malloc(sizeof(struct stack_node)); /***/
     42        *n = (struct stack_node){ value, s->head }; /***/
    4343        s->head = n;
    4444}
  • doc/generic_types/evaluation/cfa-bench.c

    rbbe856c r1504536  
    88
    99int main(int argc, char** argv) {
     10        FILE* out = fopen("cfa-out.txt", "w");
    1011        srand(20171025);
    1112
     
    2829                max = max( max, pop( &t ) );
    2930        )
     31        print( out, max, "\n" );
     32
     33        REPEAT_N_TIMED( "print_int", N/2,
     34                print( out, rand(), ":", rand(), "\n" );
     35        )
    3036
    3137        stack(pair(_Bool, char)) s2;
     
    4753                max2 = max( max2, pop( &t2 ) );
    4854        )
     55        print( out, max2, "\n" );
    4956
    50         FILE* out = fopen("cfa-out.txt", "w");
    51         REPEAT_TIMED( "print_int",
    52                 print( out, rand(), ":", rand(), "\n" );
    53         )
    54 
    55         REPEAT_TIMED( "print_pair",
     57        REPEAT_N_TIMED( "print_pair", N/2,
    5658                print( out, (pair(_Bool, char)){ rand() & 0x1, rand() & 0x7F }, ":",
    5759                                (pair(_Bool, char)){ rand() & 0x1, rand() & 0x7F }, "\n" );
  • doc/generic_types/evaluation/cfa-stack.c

    rbbe856c r1504536  
    1515        stack_node(T)* next = t->head;
    1616        while ( next ) {
    17                 *crnt = ((stack_node(T)*)malloc()){ next->value };
     17                *crnt = ((stack_node(T)*)malloc()){ next->value }; /***/
    1818                stack_node(T)* acrnt = *crnt;
    1919                crnt = &acrnt->next;
     
    2727        stack_node(T)* next = t.head;
    2828        while ( next ) {
    29                 *crnt = ((stack_node(T)*)malloc()){ next->value };
     29                *crnt = ((stack_node(T)*)malloc()){ next->value }; /***/
    3030                stack_node(T)* acrnt = *crnt;
    3131                crnt = &acrnt->next;
     
    5151
    5252forall(otype T) void push(stack(T)* s, T value) {
    53         s->head = ((stack_node(T)*)malloc()){ value, s->head };
     53        s->head = ((stack_node(T)*)malloc()){ value, s->head }; /***/
    5454}
    5555
  • doc/generic_types/evaluation/cpp-bench.cpp

    rbbe856c r1504536  
    88
    99int main(int argc, char** argv) {
     10        std::ofstream out{"cpp-out.txt"};
    1011        srand(20171025);
    1112
     
    2829                max = std::max( max, t.pop() );
    2930        )
     31        print( out, max, "\n" );
     32
     33        REPEAT_N_TIMED( "print_int", N/2,
     34                print( out, rand(), ":", rand(), "\n" );
     35        )
    3036
    3137        stack<std::pair<bool, char>> s2;
     
    4753                max2 = std::max( max2, t2.pop() );
    4854        )
     55        print( out, max2, "\n" );
    4956
    50         std::ofstream out{"cpp-out.txt"};
    51         REPEAT_TIMED( "print_int",
    52                 print( out, rand(), ":", rand(), "\n" );
    53         )
    54 
    55         REPEAT_TIMED( "print_pair",
     57        REPEAT_N_TIMED( "print_pair", N/2,
    5658                print( out, std::pair<bool, char>{ rand() & 0x1, rand() & 0x7F }, ":",
    5759                                std::pair<bool, char>{ rand() & 0x1, rand() & 0x7F }, "\n" );
  • doc/generic_types/evaluation/cpp-stack.hpp

    rbbe856c r1504536  
    1818                node* next = o.head;
    1919                while ( next ) {
    20                         *crnt = new node{ next->value };
     20                        *crnt = new node{ next->value }; /***/
    2121                        crnt = &(*crnt)->next;
    2222                        next = next->next;
     
    6363
    6464        void push(T&& value) {
    65                 head = new node{ std::move(value), head };
     65                head = new node{ std::move(value), head };  /***/
    6666        }
    6767
  • doc/generic_types/evaluation/cpp-vbench.cpp

    rbbe856c r1504536  
    88
    99int main(int argc, char** argv) {
     10        std::ofstream out{"cpp-vout.txt"};
    1011        srand(20171025);
    1112
     
    2627        integer max;
    2728        REPEAT_TIMED( "pop_int",
    28                 max = std::max( max, t.pop()->as<integer>() );
     29                max = std::max( max, t.pop()->as<integer>() ); /***/
     30        )
     31        print( out, max, c_string{"\n"} );
     32
     33        REPEAT_N_TIMED( "print_int", N/2,
     34                print( out, integer{rand()}, c_string{":"}, integer{rand()}, c_string{"\n"} );
    2935        )
    3036
     
    4753                std::make_unique<character>('\0') );
    4854        REPEAT_TIMED( "pop_bool_char",
    49                 std::unique_ptr<pair> x = as_ptr<pair>( t2.pop() );
     55                std::unique_ptr<pair> x = as_ptr<pair>( t2.pop() ); /***/
    5056                if ( *x > *max2 ) { max2 = std::move(x); }
    5157        )
     58        print( out, *max2, c_string{"\n"} );
    5259
    53         std::ofstream out{"cpp-vout.txt"};
    54         REPEAT_TIMED( "print_int",
    55                 print( out, integer{rand()}, c_string{":"}, integer{rand()}, c_string{"\n"} );
    56         )
    57 
    58         REPEAT_TIMED( "print_pair",
     60        REPEAT_N_TIMED( "print_pair", N/2,
    5961                print( out, pair{ std::make_unique<boolean>( rand() & 0x1 ),
    6062                        std::make_unique<character>( rand() & 0x7F ) }, c_string{":"},
  • doc/generic_types/evaluation/cpp-vstack.cpp

    rbbe856c r1504536  
    5555
    5656void stack::push(std::unique_ptr<object>&& value) {
    57         head = new node{ std::move(value), head };
     57        head = new node{ std::move(value), head }; /***/
    5858}
    5959
  • doc/generic_types/evaluation/object.hpp

    rbbe856c r1504536  
    9696        }
    9797
    98         object& operator= (const object& that) override { return *this = that.as<boolean>(); }
     98        object& operator= (const object& that) override { return *this = that.as<boolean>(); } /***/
    9999
    100100        ~boolean() override = default;
     
    102102        int cmp(const boolean& that) const { return x == that.x ? 0 : x == false ? -1 : 1; }
    103103
    104         int cmp(const ordered& that) const override { return cmp( that.as<boolean>() ); }
     104        int cmp(const ordered& that) const override { return cmp( that.as<boolean>() ); } /***/
    105105
    106106        void print(std::ostream& out) const override { out << (x ? "true" : "false"); }
     
    124124        }
    125125
    126         object& operator= (const object& that) override { return *this = that.as<character>(); }
     126        object& operator= (const object& that) override { return *this = that.as<character>(); } /***/
    127127
    128128        ~character() override = default;
     
    130130        int cmp(const character& that) const { return x == that.x ? 0 : x < that.x ? -1 : 1; }
    131131
    132         int cmp(const ordered& that) const override { return cmp( that.as<character>() ); }
     132        int cmp(const ordered& that) const override { return cmp( that.as<character>() ); } /***/
    133133
    134134        void print(std::ostream& out) const override {
     
    155155        }
    156156
    157         object& operator= (const object& that) override { return *this = that.as<integer>(); }
     157        object& operator= (const object& that) override { return *this = that.as<integer>(); } /***/
    158158
    159159        ~integer() override = default;
     
    161161        int cmp(const integer& that) const { return x == that.x ? 0 : x < that.x ? -1 : 1; }
    162162
    163         int cmp(const ordered& that) const override { return cmp( that.as<integer>() ); }
     163        int cmp(const ordered& that) const override { return cmp( that.as<integer>() ); } /***/
    164164
    165165        void print(std::ostream& out) const override { out << x; }
     
    183183        }
    184184
    185         object& operator= (const object& that) override { return *this = that.as<c_string>(); }
     185        object& operator= (const object& that) override { return *this = that.as<c_string>(); } /***/
    186186
    187187        ~c_string() override = default;
     
    212212        }
    213213
    214         object& operator= (const object& that) override { return *this = that.as<pair>(); }
     214        object& operator= (const object& that) override { return *this = that.as<pair>(); } /***/
    215215
    216216        ~pair() override = default;
    217217
    218218        int cmp(const pair& that) const {
    219                 int c = x->as<ordered>().cmp( that.x->as<ordered>() );
     219                int c = x->as<ordered>().cmp( that.x->as<ordered>() ); /***/
    220220                if ( c != 0 ) return c;
    221                 return y->as<ordered>().cmp( that.y->as<ordered>() );
     221                return y->as<ordered>().cmp( that.y->as<ordered>() ); /***/
    222222        }
    223223
     
    226226        void print(std::ostream& out) const override {
    227227                out << "[";
    228                 x->as<printable>().print(out);
     228                x->as<printable>().print(out); /***/
    229229                out << ", ";
    230                 y->as<printable>().print(out);
     230                y->as<printable>().print(out); /***/
    231231                out << "]";
    232232        }
  • doc/generic_types/evaluation/timing.csv

    rbbe856c r1504536  
    1 "400 million repetitions","C","\\CFA{}","\\CC{}","\\CC{obj}","units"
    2 "push\nint",3379,2616,1928,3527,"ms"
    3 "copy\nint",3036,2268,1564,3182,"ms"
    4 "clear\nint",1389,834,751,1502,"ms"
    5 "pop\nint",1421,2728,738,5245,"ms"
    6 "push\npair",4598,3708,1776,7302,"ms"
    7 "copy\npair",6367,1920,1009,6982,"ms"
    8 "clear\npair",2906,875,732,3387,"ms"
    9 "pop\npair",3136,8283,861,21669,"ms"
    10 "print\nint",17373,17157,9779,10051,"ms"
    11 "print\npair",24862,27693,20599,42533,"ms"
     1"400 million repetitions","C","\\CFA{}","\\CC{}","\\CC{obj}"
     2"push\nint",3358,2616,1929,3559
     3"copy\nint",2966,2268,1534,3097
     4"clear\nint",1343,834,708,1487
     5"pop\nint",1385,2728,711,5122
     6"print\nint",6609,17157,5006,5023
     7"push\npair",4930,3708,1795,7136
     8"copy\npair",6203,1920,996,7043
     9"clear\npair",2811,875,712,3393
     10"pop\npair",3054,8283,883,21262
     11"print\npair",12364,27693,10448,21468
     12
  • doc/generic_types/evaluation/timing.gp

    rbbe856c r1504536  
    1212set boxwidth 0.8
    1313
    14 set ylabel "seconds"
     14set ylabel "milliseconds"
    1515set key top left reverse Left
    1616
  • doc/generic_types/generic_types.tex

    rbbe856c r1504536  
    969969The \CCV variant illustrates an alternative object-oriented idiom where all objects inherit from a base @object@ class, mimicking a Java-like interface;
    970970hence runtime checks are necessary to safely down-cast objects.
    971 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}.
    972 For the print benchmark, idiomatic printing is used: the C and \CFA variants used @cstdio.h@, while the \CC and \CCV variants used @iostream@.
    973 Preliminary tests show the difference has little runtime effect.
     971The 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.
     972For the print benchmark, idiomatic printing is used: the C and \CFA variants use @stdio.h@, while the \CC and \CCV variants use @iostream@.
     973Preliminary tests show this difference has little runtime effect.
    974974Finally, the C @rand@ function is used generate random numbers.
    975975
     
    10141014\newcommand{\CT}[1]{\multicolumn{1}{c}{#1}}
    10151015\begin{tabular}{r|rrrr}
    1016                                                         & \CT{C}        & \CT{\CFA}     & \CT{\CC}      &       \CT{\CCV}       \\ \hline
    1017 maximum memory usage (MB)       & 10001         & 2501          & 2503          &       11253           \\
    1018 source code size (lines)        & 301           & 224           & 188           &       437                     \\
    1019 binary size (KB)                        & 18            & 234           & 18            &       42                      \\
     1016                                                                        & \CT{C}        & \CT{\CFA}     & \CT{\CC}      &       \CT{\CCV}       \\ \hline
     1017maximum memory usage (MB)                       & 10001         & 2501          & 2503          &       11253           \\
     1018source code size (lines)                        & 301           & 224           & 188           &       437                     \\
     1019redundant type annotations (lines)      & 46            & 3                     & 2                     &       15                      \\
     1020binary size (KB)                                        & 18            & 234           & 18            &       42                      \\
    10201021\end{tabular}
    10211022\end{table}
    10221023
    10231024Figure~\ref{fig:eval} and Table~\ref{tab:eval} show the benchmark results.
    1024 Each data point is the time for 40M function call, repeated times where appropriate.
    1025 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/2$ variadic @print@ calls each containing two constant strings and two stack elements \TODO{right now $N$ fresh elements: FIX}, and $N$ stack pops, keeping a running record of the maximum element to ensure that the object copies are not optimized out.
     1025Each data point is the time for $N = 40M$ function calls or loop iterations, as appropriate.
     1026The 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.
    10261027These five functions are run first for a stack of integers, and second for a stack of generic pairs of a boolean and a @char@.
    10271028\TODO{} The data shown is the median of 5 consecutive runs of each program, with an initial warm-up run omitted.
     
    10321033
    10331034\CC performs best because it uses header-only inlined libraries (i.e., no separate compilation).
    1034 \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. {\color{red} Why?}
    1035 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 and with their omission the \CCV line count is similar to C;
    1036 we justify the given line count by the fact that many object-oriented languages do not allow implementing new interfaces on library types without subclassing or boilerplate-filled wrapper types, which may be similarly verbose.
     1035\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.
     1036The 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.
     1037We justify the given line count by noting that many object-oriented languages do not allow implementing new interfaces on library types without subclassing or boilerplate-filled wrapper types, which may be similarly verbose.
     1038
    10371039Raw line-count, however, is a fairly rough measure of code complexity;
    10381040another important factor is how much type information the programmer must manually specify, especially where that information is not checked by the compiler.
    1039 Such un-checked type information produces a heavier documentation burden and increased potential for runtime bugs, and is much less common in \CFA than C, with its manually specified function pointers arguments and format codes, or \CCV, with its extensive use of un-type-checked downcasts (\eg @object@ to @integer@ when popping a stack, or @object@ to @printable@ when printing the elements of a @pair@) \TODO{Actually calculate this; I want to put a distinctive comment in the source code and grep for it}.
    1040 
     1041Such un-checked type information produces a heavier documentation burden and increased potential for runtime bugs, and is much less common in \CFA than C, with its manually specified function pointers arguments and format codes, or \CCV, with its extensive use of un-type-checked downcasts (\eg @object@ to @integer@ when popping a stack, or @object@ to @printable@ when printing the elements of a @pair@). To quantify this, the ``redundant type annotations'' line in Table~\ref{tab:eval} counts the number of lines on which the type of a known variable is re-specified, either as a format specifier, explicit downcast, type-specific function, or by name in a @sizeof@, struct literal, or @new@ expression. The \CC benchmark uses two redundant type annotations to create a new stack nodes, while the C and \CCV benchmarks have several such annotations spread throughout their code. The three instances in which the \CFA benchmark still uses redundant type specifiers are to cast the result of a polymorphic @malloc@ call (the @sizeof@ argument is inferred by the compiler). These uses are similar to the @new@ expressions in \CC, though ongoing work on the \CFA compiler's type resolver should shortly render even these type casts superfluous.
    10411042
    10421043\section{Related Work}
     
    11271128\appendix
    11281129
    1129 
    11301130\section{BenchMarks}
    11311131\label{sec:BenchMarks}
Note: See TracChangeset for help on using the changeset viewer.