Changeset 5a40e4e


Ignore:
Timestamp:
Sep 9, 2021, 3:56:32 PM (8 months ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
enum, forall-pointer-decay, master
Children:
d0b9247
Parents:
dd1cc02 (diff), d8d512e (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

Files:
43 added
95 edited
13 moved

Legend:

Unmodified
Added
Removed
  • benchmark/Makefile.am

    rdd1cc02 r5a40e4e  
    197197        $(srcdir)/fixcsv.sh $@
    198198
     199# use --no-print-directory to generate csv appropriately
     200mutexStmt.csv:
     201        echo "building $@"
     202        echo "1-lock,2-lock,4-lock,8-lock,1-no-stmt-lock,2-no-stmt-lock,4-no-stmt-lock,8-no-stmt-lock,1-monitor,2-monitor,4-monitor" > $@
     203        +make mutexStmt-lock1.runquiet >> $@ && echo -n ',' >> $@
     204        +make mutexStmt-lock2.runquiet >> $@ && echo -n ',' >> $@
     205        +make mutexStmt-lock4.runquiet >> $@ && echo -n ',' >> $@
     206        +make mutexStmt-lock8.runquiet >> $@ && echo -n ',' >> $@
     207        +make mutexStmt-no-stmt-lock1.runquiet >> $@ && echo -n ',' >> $@
     208        +make mutexStmt-no-stmt-lock2.runquiet >> $@ && echo -n ',' >> $@
     209        +make mutexStmt-no-stmt-lock4.runquiet >> $@ && echo -n ',' >> $@
     210        +make mutexStmt-no-stmt-lock8.runquiet >> $@ && echo -n ',' >> $@
     211        +make mutexStmt-monitor1.runquiet >> $@ && echo -n ',' >> $@
     212        +make mutexStmt-monitor2.runquiet >> $@ && echo -n ',' >> $@
     213        +make mutexStmt-monitor4.runquiet >> $@
     214        $(srcdir)/fixcsv.sh $@
     215
    199216schedint.csv:
    200217        echo "building $@"
     
    355372        chmod a+x a.out
    356373
     374mutexStmt$(EXEEXT) :                \
     375        mutexStmt-lock1.run                 \
     376        mutexStmt-lock2.run                 \
     377        mutexStmt-lock4.run                 \
     378        mutexStmt-lock8.run                 \
     379        mutexStmt-no-stmt-lock1.run \
     380        mutexStmt-no-stmt-lock2.run \
     381        mutexStmt-no-stmt-lock4.run \
     382        mutexStmt-no-stmt-lock8.run \
     383        mutexStmt-monitor1.run      \
     384        mutexStmt-monitor2.run      \
     385        mutexStmt-monitor4.run
     386
     387mutexStmt-lock1$(EXEEXT):
     388        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/lock1.cfa
     389
     390mutexStmt-lock2$(EXEEXT):
     391        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/lock2.cfa
     392
     393mutexStmt-lock4$(EXEEXT):
     394        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/lock4.cfa
     395
     396mutexStmt-lock8$(EXEEXT):
     397        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/lock8.cfa
     398
     399mutexStmt-monitor1$(EXEEXT):
     400        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/monitor1.cfa
     401
     402mutexStmt-monitor2$(EXEEXT):
     403        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/monitor2.cfa
     404
     405mutexStmt-monitor4$(EXEEXT):
     406        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/monitor4.cfa
     407
     408mutexStmt-no-stmt-lock1$(EXEEXT):
     409        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/no_stmt_lock1.cfa
     410
     411mutexStmt-no-stmt-lock2$(EXEEXT):
     412        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/no_stmt_lock2.cfa
     413
     414mutexStmt-no-stmt-lock4$(EXEEXT):
     415        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/no_stmt_lock4.cfa
     416
     417mutexStmt-no-stmt-lock8$(EXEEXT):
     418        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/no_stmt_lock8.cfa
     419
    357420## =========================================================================================================
    358421
  • doc/theses/andrew_beach_MMath/code/CondCatch.java

    rdd1cc02 r5a40e4e  
    66        static boolean should_catch = false;
    77
    8         static void throw_exception() throws EmptyException {
    9                 throw new EmptyException();
    10         }
    11 
    12         static void cond_catch() throws EmptyException {
    13                 try {
    14                         throw_exception();
    15                 } catch (EmptyException exc) {
    16                         if (!should_catch) {
    17                                 throw exc;
    18                         }
    19                 }
    20         }
    21 
    228        private static long loop(int times) {
    239                long startTime = System.nanoTime();
    2410                for (int count = 0 ; count < times ; ++count) {
    2511                        try {
    26                                 cond_catch();
     12                                try {
     13                                        throw new EmptyException();
     14                                } catch (EmptyException exc) {
     15                                        if (!should_catch) {
     16                                                throw exc;
     17                                        }
     18                                }
    2719                        } catch (EmptyException exc) {
    2820                                // ...
     
    4638
    4739                long time = loop(times);
    48                 System.out.println("Run-Time (ns): " + time);
     40                System.out.format("Run-Time (s): %.1f%n", time / 1_000_000_000.);
    4941        }
    5042}
  • doc/theses/andrew_beach_MMath/code/ThrowEmpty.java

    rdd1cc02 r5a40e4e  
    3939
    4040                long time = loop(times, total_frames);
    41                 System.out.println("Run-Time (ns): " + time);
     41                System.out.format("Run-Time (s): %.1f%n", time / 1_000_000_000.);
    4242        }
    4343}
  • doc/theses/andrew_beach_MMath/code/ThrowFinally.java

    rdd1cc02 r5a40e4e  
    4444
    4545                long time = loop(times, total_frames);
    46                 System.out.println("Run-Time (ns): " + time);
     46                System.out.format("Run-Time (s): %.1f%n", time / 1_000_000_000.);
    4747        }
    4848}
  • doc/theses/andrew_beach_MMath/code/ThrowOther.java

    rdd1cc02 r5a40e4e  
    5252
    5353                long time = loop(times, total_frames);
    54                 System.out.println("Run-Time (ns): " + time);
     54                System.out.format("Run-Time (s): %.1f%n", time / 1_000_000_000.);
    5555        }
    5656}
  • doc/theses/andrew_beach_MMath/code/TryCatch.java

    rdd1cc02 r5a40e4e  
    33class NotRaisedException extends Exception {}
    44
    5 public class CrossCatch {
     5public class TryCatch {
    66        private static boolean shouldThrow = false;
    77
     
    3131
    3232                long time = loop(times);
    33                 System.out.println("Run-Time (ns): " + time);
     33                System.out.format("Run-Time (s): %.1f%n", time / 1_000_000_000.);
    3434        }
    3535}
  • doc/theses/andrew_beach_MMath/code/TryFinally.java

    rdd1cc02 r5a40e4e  
    1 // Cross a Try Statement with a Finally Clause
     1// Enter and Leave a Try Statement with a Finally Handler
    22
    3 public class CrossFinally {
     3public class TryFinally {
    44        private static boolean shouldThrow = false;
    55
     
    2727
    2828                long time = loop(times);
    29                 System.out.println("Run-Time (ns): " + time);
     29                System.out.format("Run-Time (s): %.1f%n", time / 1_000_000_000.);
    3030        }
    3131}
  • doc/theses/andrew_beach_MMath/code/cond-catch.cfa

    rdd1cc02 r5a40e4e  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.h>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(empty_exception)();
    8 
    9 EHM_VIRTUAL_TABLE(empty_exception, empty_vt);
     7exception empty_exception;
     8vtable(empty_exception) empty_vt;
    109
    1110bool should_catch = false;
    12 
    13 void throw_exception() {
    14         throw (empty_exception){&empty_vt};
    15 }
    16 
    17 void cond_catch() {
    18         try {
    19                 throw_exception();
    20         } catch (empty_exception * exc ; should_catch) {
    21                 asm volatile ("# catch block (conditional)");
    22         }
    23 }
    2411
    2512int main(int argc, char * argv[]) {
    2613        unsigned int times = 1;
    2714        if (1 < argc) {
    28                 times = strtol(argv[1], 0p, 10);
     15                times = strto(argv[1], 0p, 10);
    2916        }
    3017        if (2 < argc) {
    31                 should_catch = strtol(argv[2], 0p, 10);
     18                should_catch = (unsigned int)strto(argv[2], 0p, 2);
    3219        }
    3320
     
    3522        for (unsigned int count = 0 ; count < times ; ++count) {
    3623                try {
    37                         cond_catch();
     24                        throw (empty_exception){&empty_vt};
     25                } catch (empty_exception * exc ; should_catch) {
     26                        asm volatile ("# catch block (conditional)");
    3827                } catch (empty_exception * exc) {
    3928                        asm volatile ("# catch block (unconditional)");
     
    4130        }
    4231        Time end_time = timeHiRes();
    43         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     32        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    4433}
  • doc/theses/andrew_beach_MMath/code/cond-catch.cpp

    rdd1cc02 r5a40e4e  
    44#include <exception>
    55#include <iostream>
     6#include <iomanip>
    67
     8using namespace std;
    79using namespace std::chrono;
    810
     
    1012
    1113bool should_catch = false;
    12 
    13 void throw_exception() {
    14         throw EmptyException();
    15 }
    16 
    17 void cond_catch() {
    18         try {
    19                 throw_exception();
    20         } catch (EmptyException & exc) {
    21                 if (!should_catch) {
    22                         throw;
    23                 }
    24                 asm volatile ("# catch block (conditional)");
    25         }
    26 }
    2714
    2815int main(int argc, char * argv[]) {
     
    3825    for (unsigned int count = 0 ; count < times ; ++count) {
    3926        try {
    40                         cond_catch();
     27                        try {
     28                                throw EmptyException();
     29                        } catch (EmptyException & exc) {
     30                                if (!should_catch) {
     31                                        throw;
     32                                }
     33                                asm volatile ("# catch block (conditional)");
     34                        }
    4135                } catch (EmptyException &) {
    4236                        asm volatile ("# catch block (unconditional)");
     
    4539        time_point<steady_clock> end_time = steady_clock::now();
    4640        nanoseconds duration = duration_cast<nanoseconds>(end_time - start_time);
    47         std::cout << "Run-Time (ns): " << duration.count() << std::endl;
     41        cout << "Run-Time (s): " << fixed << setprecision(1) << duration.count() / 1'000'000'000. << endl;
    4842}
  • doc/theses/andrew_beach_MMath/code/cond-catch.py

    rdd1cc02 r5a40e4e  
    1313
    1414
    15 def throw_exception():
    16     raise EmptyException()
    17 
    18 
    19 def cond_catch():
    20     try:
    21         throw_exception()
    22     except EmptyException as exc:
    23         if not should_catch:
    24             raise
    25 
    26 
    2715def main(argv):
    2816    times = 1
     
    3523    for count in range(times):
    3624        try:
    37             cond_catch();
     25            try:
     26                raise EmptyException()
     27            except EmptyException as exc:
     28                if not should_catch:
     29                    raise
    3830        except EmptyException:
    3931            pass
    4032
    4133    end_time = thread_time_ns()
    42     print('Run-Time (ns):', end_time - start_time)
     34    print('Run-Time (s): {:.1f}'.format((end_time - start_time) / 1_000_000_000.))
    4335
    4436
  • doc/theses/andrew_beach_MMath/code/cond-fixup.cfa

    rdd1cc02 r5a40e4e  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.hfa>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(empty_exception)();
    8 
    9 EHM_VIRTUAL_TABLE(empty_exception, empty_vt);
     7exception empty_exception;
     8vtable(empty_exception) empty_vt;
    109
    1110bool should_catch = false;
    12 
    13 void throw_exception() {
    14         throwResume (empty_exception){&empty_vt};
    15 }
    16 
    17 void cond_catch() {
    18         try {
    19                 throw_exception();
    20         } catchResume (empty_exception * exc ; should_catch) {
    21                 asm volatile ("# fixup block (conditional)");
    22         }
    23 }
    2411
    2512int main(int argc, char * argv[]) {
    2613        unsigned int times = 1;
    2714        if (1 < argc) {
    28                 times = strtol(argv[1], 0p, 10);
     15                times = strto(argv[1], 0p, 10);
    2916        }
    3017        if (2 < argc) {
    31                 should_catch = strtol(argv[2], 0p, 10);
     18                should_catch = (unsigned int)strto(argv[2], 0p, 2);
    3219        }
    3320
     
    3522        for (unsigned int count = 0 ; count < times ; ++count) {
    3623                try {
    37                         cond_catch();
     24                        throwResume (empty_exception){&empty_vt};
     25                } catchResume (empty_exception * exc ; should_catch) {
     26                        asm volatile ("# fixup block (conditional)");
    3827                } catchResume (empty_exception * exc) {
    3928                        asm volatile ("# fixup block (unconditional)");
     
    4130        }
    4231        Time end_time = timeHiRes();
    43         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     32        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    4433}
  • doc/theses/andrew_beach_MMath/code/resume-detor.cfa

    rdd1cc02 r5a40e4e  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.hfa>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(empty_exception)();
    8 
    9 EHM_VIRTUAL_TABLE(empty_exception, empty_vt);
     7exception empty_exception;
     8vtable(empty_exception) empty_vt;
    109
    1110struct WithDestructor {};
     
    1716void unwind_destructor(unsigned int frames) {
    1817        if (frames) {
    19 
    2018                WithDestructor object;
    2119                unwind_destructor(frames - 1);
     
    2927        unsigned int total_frames = 1;
    3028        if (1 < argc) {
    31                 times = strtol(argv[1], 0p, 10);
     29                times = strto(argv[1], 0p, 10);
    3230        }
    3331        if (2 < argc) {
    34                 total_frames = strtol(argv[2], 0p, 10);
     32                total_frames = strto(argv[2], 0p, 10);
    3533        }
    3634
     
    4442        }
    4543        Time end_time = timeHiRes();
    46         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     44        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    4745}
  • doc/theses/andrew_beach_MMath/code/resume-empty.cfa

    rdd1cc02 r5a40e4e  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.hfa>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(empty_exception)();
     7exception empty_exception;
     8vtable(empty_exception) empty_vt;
    89
    9 EHM_VIRTUAL_TABLE(empty_exception, empty_vt);
    10 
    11 void unwind_empty(unsigned int frames) {
     10void nounwind_empty(unsigned int frames) {
    1211        if (frames) {
    13                 unwind_empty(frames - 1);
     12                nounwind_empty(frames - 1);
     13                if ( frames == -1 ) printf( "42" );                             // prevent recursion optimizations
    1414        } else {
    1515                throwResume (empty_exception){&empty_vt};
     
    2121        unsigned int total_frames = 1;
    2222        if (1 < argc) {
    23                 times = strtol(argv[1], 0p, 10);
     23                times = strto(argv[1], 0p, 10);
    2424        }
    2525        if (2 < argc) {
    26                 total_frames = strtol(argv[2], 0p, 10);
     26                total_frames = strto(argv[2], 0p, 10);
    2727        }
    2828
    2929        Time start_time = timeHiRes();
    30         for (int count = 0 ; count < times ; ++count) {
     30        for (unsigned int count = 0 ; count < times ; ++count) {
    3131                try {
    32                         unwind_empty(total_frames);
     32                        nounwind_empty(total_frames);
    3333                } catchResume (empty_exception *) {
    3434                        asm volatile ("# fixup block");
     
    3636        }
    3737        Time end_time = timeHiRes();
    38         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     38        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    3939}
  • doc/theses/andrew_beach_MMath/code/resume-finally.cfa

    rdd1cc02 r5a40e4e  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.hfa>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(empty_exception)();
    8 
    9 EHM_VIRTUAL_TABLE(empty_exception, empty_vt);
     7exception empty_exception;
     8vtable(empty_exception) empty_vt;
    109
    1110void unwind_finally(unsigned int frames) {
     
    2524        unsigned int total_frames = 1;
    2625        if (1 < argc) {
    27                 times = strtol(argv[1], 0p, 10);
     26                times = strto(argv[1], 0p, 10);
    2827        }
    2928        if (2 < argc) {
    30                 total_frames = strtol(argv[2], 0p, 10);
     29                total_frames = strto(argv[2], 0p, 10);
    3130        }
    3231
     
    4039        }
    4140        Time end_time = timeHiRes();
    42         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     41        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    4342}
  • doc/theses/andrew_beach_MMath/code/resume-other.cfa

    rdd1cc02 r5a40e4e  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.hfa>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(empty_exception)();
     7exception empty_exception;
     8vtable(empty_exception) empty_vt;
     9exception not_raised_exception;
    810
    9 EHM_VIRTUAL_TABLE(empty_exception, empty_vt);
    10 
    11 EHM_EXCEPTION(not_raised_exception)();
    12 
    13 void unwind_other(unsigned int frames) {
     11void nounwind_other(unsigned int frames) {
    1412        if (frames) {
    1513                try {
    16                         unwind_other(frames - 1);
     14                        nounwind_other(frames - 1);
    1715                } catchResume (not_raised_exception *) {
    1816                        asm volatile ("# fixup block (stack)");
     
    2725        unsigned int total_frames = 1;
    2826        if (1 < argc) {
    29                 times = strtol(argv[1], 0p, 10);
     27                times = strto(argv[1], 0p, 10);
    3028        }
    3129        if (2 < argc) {
    32                 total_frames = strtol(argv[2], 0p, 10);
     30                total_frames = strto(argv[2], 0p, 10);
    3331        }
    3432
     
    3634        for (int count = 0 ; count < times ; ++count) {
    3735                try {
    38                         unwind_other(total_frames);
     36                        nounwind_other(total_frames);
    3937                } catchResume (empty_exception *) {
    4038                        asm volatile ("# fixup block (base)");
     
    4240        }
    4341        Time end_time = timeHiRes();
    44         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     42        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    4543}
  • doc/theses/andrew_beach_MMath/code/run.sh

    rdd1cc02 r5a40e4e  
    11#!/usr/bin/env bash
    22
    3 readonly ALL_TESTS=(cond-match-{all,none} cross-{catch,finally} \
    4                 raise-{detor,empty,finally,other})
     3readonly ALL_TESTS=(raise-{empty,detor,finally,other} try-{catch,finally} \
     4                        cond-match-{all,none} fixup-{empty,other})
    55
    66gen-file-name() (
     
    1818)
    1919
    20 readonly N=${1:-5}
     20readonly N=${1:-1}
    2121readonly OUT_FILE=$(gen-file-name ${2:-run-%-$N})
    2222
  • doc/theses/andrew_beach_MMath/code/test.sh

    rdd1cc02 r5a40e4e  
    44# test.sh LANGUAGE TEST
    55#   Run the TEST in LANGUAGE.
     6# test.sh -a
     7#   Build all tests.
    68# test.sh -b SOURCE_FILE...
    79#   Build a test from SOURCE_FILE(s).
     10# test.sh -c
     11#   Clean all executables.
    812# test.sh -v LANGUAGE TEST FILE
    913#   View the result from TEST in LANGUAGE stored in FILE.
    1014
    11 readonly ITERATIONS=1000000 # 1 000 000, one million
     15readonly DIR=$(dirname "$(readlink -f "$0")")
     16cd $DIR
     17
     18readonly MIL=000000
     19# Various preset values used as arguments.
     20readonly ITERS_1M=1$MIL
     21readonly ITERS_10M=10$MIL
     22readonly ITERS_100M=100$MIL
     23readonly ITERS_1000M=1000$MIL
    1224readonly STACK_HEIGHT=100
    1325
     
    2335        case "$1" in
    2436        *.cfa)
    25                 # Requires a symbolic link.
    26                 mmake "${1%.cfa}" "$1" ./cfa -DNDEBUG -nodebug -O3 "$1" -o "${1%.cfa}"
     37                # A symbolic link/local copy can be used as an override.
     38                cmd=./cfa
     39                if [ ! -x $cmd ]; then
     40                        cmd=cfa
     41                fi
     42                mmake "${1%.cfa}" "$1" $cmd -DNDEBUG -nodebug -O3 "$1" -o "${1%.cfa}"
    2743                ;;
    2844        *.cpp)
    29                 mmake "${1%.cpp}-cpp" "$1" g++ -DNDEBUG -O3 "$1" -o "${1%.cpp}-cpp"
     45                mmake "${1%.cpp}-cpp" "$1" g++-10 -DNDEBUG -O3 "$1" -o "${1%.cpp}-cpp"
    3046                ;;
    3147        *.java)
     
    3955)
    4056
    41 if [ "-b" = "$1" ]; then
     57if [ "-a" = "$1" ]; then
     58        for file in *.cfa *.cpp *.java; do
     59                build $file
     60        done
     61        exit 0
     62elif [ "-b" = "$1" ]; then
    4263        for file in "${@:2}"; do
    4364                build $file
    4465        done
    4566        exit 0
     67elif [ "-c" = "$1" ]; then
     68        rm $(basename -s ".cfa" -a *.cfa)
     69        rm $(basename -s ".cpp" -a *.cpp)
     70        rm *-cpp
     71        rm *.class
     72        exit 0
    4673elif [ "-v" = "$1" -a 4 = "$#" ]; then
    47     TEST_LANG="$2"
    48     TEST_CASE="$3"
    49     VIEW_FILE="$4"
     74        TEST_LANG="$2"
     75        TEST_CASE="$3"
     76        VIEW_FILE="$4"
    5077elif [ 2 -eq "$#" ]; then
    5178        TEST_LANG="$1"
     
    6390
    6491case "$TEST_CASE" in
    65 cond-match-all)
    66         CFAT="./cond-catch $ITERATIONS 1"
    67         CFAR="./cond-fixup $ITERATIONS 1"
    68         CPP="./cond-catch-cpp $ITERATIONS 1"
    69         JAVA="java CondCatch $ITERATIONS 1"
    70         PYTHON="./cond_catch.py $ITERATIONS 1"
    71         ;;
    72 cond-match-none)
    73         CFAT="./cond-catch $ITERATIONS 0"
    74         CFAR="./cond-fixup $ITERATIONS 0"
    75         CPP="./cond-catch-cpp $ITERATIONS 0"
    76         JAVA="java CondCatch $ITERATIONS 0"
    77         PYTHON="./cond_catch.py $ITERATIONS 0"
    78         ;;
    79 cross-catch)
    80         CFAT="./cross-catch $ITERATIONS"
    81         CFAR="./cross-resume $ITERATIONS"
    82         CPP="./cross-catch-cpp $ITERATIONS"
    83         JAVA="java CrossCatch $ITERATIONS"
    84         PYTHON="./cross_catch.py $ITERATIONS"
    85         ;;
    86 cross-finally)
    87         CFAT="./cross-finally $ITERATIONS"
    88         CFAR=unsupported
    89         CPP=unsupported
    90         JAVA="java CrossFinally $ITERATIONS"
    91         PYTHON="./cross_finally.py $ITERATIONS"
     92raise-empty)
     93        CFAT="./throw-empty $ITERS_1M $STACK_HEIGHT"
     94        CFAR="./resume-empty $ITERS_10M $STACK_HEIGHT"
     95        CPP="./throw-empty-cpp $ITERS_1M $STACK_HEIGHT"
     96        JAVA="java ThrowEmpty $ITERS_1M $STACK_HEIGHT"
     97        PYTHON="./throw-empty.py $ITERS_1M $STACK_HEIGHT"
    9298        ;;
    9399raise-detor)
    94         CFAT="./throw-detor $ITERATIONS $STACK_HEIGHT"
    95         CFAR="./resume-detor $ITERATIONS $STACK_HEIGHT"
    96         CPP="./throw-detor-cpp $ITERATIONS $STACK_HEIGHT"
     100        CFAT="./throw-detor $ITERS_1M $STACK_HEIGHT"
     101        CFAR="./resume-detor $ITERS_10M $STACK_HEIGHT"
     102        CPP="./throw-detor-cpp $ITERS_1M $STACK_HEIGHT"
    97103        JAVA=unsupported
    98104        PYTHON=unsupported
    99105        ;;
    100 raise-empty)
    101         CFAT="./throw-empty $ITERATIONS $STACK_HEIGHT"
    102         CFAR="./resume-empty $ITERATIONS $STACK_HEIGHT"
    103         CPP="./throw-empty-cpp $ITERATIONS $STACK_HEIGHT"
    104         JAVA="java ThrowEmpty $ITERATIONS $STACK_HEIGHT"
    105         PYTHON="./throw_empty.py $ITERATIONS $STACK_HEIGHT"
    106         ;;
    107106raise-finally)
    108         CFAT="./throw-finally $ITERATIONS $STACK_HEIGHT"
    109         CFAR="./resume-finally $ITERATIONS $STACK_HEIGHT"
     107        CFAT="./throw-finally $ITERS_1M $STACK_HEIGHT"
     108        CFAR="./resume-finally $ITERS_10M $STACK_HEIGHT"
    110109        CPP=unsupported
    111         JAVA="java ThrowFinally $ITERATIONS $STACK_HEIGHT"
    112         PYTHON="./throw_finally.py $ITERATIONS $STACK_HEIGHT"
     110        JAVA="java ThrowFinally $ITERS_1M $STACK_HEIGHT"
     111        PYTHON="./throw-finally.py $ITERS_1M $STACK_HEIGHT"
    113112        ;;
    114113raise-other)
    115         CFAT="./throw-other $ITERATIONS $STACK_HEIGHT"
    116         CFAR="./resume-other $ITERATIONS $STACK_HEIGHT"
    117         CPP="./throw-other-cpp $ITERATIONS $STACK_HEIGHT"
    118         JAVA="java ThrowOther $ITERATIONS $STACK_HEIGHT"
    119         PYTHON="./throw_other.py $ITERATIONS $STACK_HEIGHT"
     114        CFAT="./throw-other $ITERS_1M $STACK_HEIGHT"
     115        CFAR="./resume-other $ITERS_10M $STACK_HEIGHT"
     116        CPP="./throw-other-cpp $ITERS_1M $STACK_HEIGHT"
     117        JAVA="java ThrowOther $ITERS_1M $STACK_HEIGHT"
     118        PYTHON="./throw-other.py $ITERS_1M $STACK_HEIGHT"
     119        ;;
     120try-catch)
     121        CFAT="./try-catch $ITERS_1000M"
     122        CFAR="./try-resume $ITERS_1000M"
     123        CPP="./try-catch-cpp $ITERS_1000M"
     124        JAVA="java TryCatch $ITERS_1000M"
     125        PYTHON="./try-catch.py $ITERS_1000M"
     126        ;;
     127try-finally)
     128        CFAT="./try-finally $ITERS_1000M"
     129        CFAR=unsupported
     130        CPP=unsupported
     131        JAVA="java TryFinally $ITERS_1000M"
     132        PYTHON="./try-finally.py $ITERS_1000M"
     133        ;;
     134cond-match-all)
     135        CFAT="./cond-catch $ITERS_10M 1"
     136        CFAR="./cond-fixup $ITERS_100M 1"
     137        CPP="./cond-catch-cpp $ITERS_10M 1"
     138        JAVA="java CondCatch $ITERS_10M 1"
     139        PYTHON="./cond-catch.py $ITERS_10M 1"
     140        ;;
     141cond-match-none)
     142        CFAT="./cond-catch $ITERS_10M 0"
     143        CFAR="./cond-fixup $ITERS_100M 0"
     144        CPP="./cond-catch-cpp $ITERS_10M 0"
     145        JAVA="java CondCatch $ITERS_10M 0"
     146        PYTHON="./cond-catch.py $ITERS_10M 0"
     147        ;;
     148fixup-empty)
     149        CFAT="./fixup-empty-f $ITERS_10M $STACK_HEIGHT"
     150        CFAR="./fixup-empty-r $ITERS_10M $STACK_HEIGHT"
     151        CPP="./fixup-empty-cpp $ITERS_10M $STACK_HEIGHT"
     152        JAVA="java FixupEmpty $ITERS_10M $STACK_HEIGHT"
     153        PYTHON="./fixup-empty.py $ITERS_10M $STACK_HEIGHT"
     154        ;;
     155fixup-other)
     156        CFAT="./fixup-other-f $ITERS_10M $STACK_HEIGHT"
     157        CFAR="./fixup-other-r $ITERS_10M $STACK_HEIGHT"
     158        CPP="./fixup-other-cpp $ITERS_10M $STACK_HEIGHT"
     159        JAVA="java FixupOther $ITERS_10M $STACK_HEIGHT"
     160        PYTHON="./fixup-other.py $ITERS_10M $STACK_HEIGHT"
    120161        ;;
    121162*)
     
    140181
    141182if [ -n "$VIEW_FILE" ]; then
    142     grep -A 1 -B 0 "$CALL" "$VIEW_FILE" | sed -n -e 's!Run-Time (ns): !!;T;p'
    143     exit
     183        grep -A 1 -B 0 "$CALL" "$VIEW_FILE" | sed -n -e 's!Run-Time (ns): !!;T;p'
     184        exit
    144185fi
    145186
  • doc/theses/andrew_beach_MMath/code/throw-detor.cfa

    rdd1cc02 r5a40e4e  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.hfa>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(empty_exception)();
    8 
    9 EHM_VIRTUAL_TABLE(empty_exception, empty_vt);
     7exception empty_exception;
     8vtable(empty_exception) empty_vt;
    109
    1110struct WithDestructor {};
     
    2827        unsigned int total_frames = 1;
    2928        if (1 < argc) {
    30                 times = strtol(argv[1], 0p, 10);
     29                times = strto(argv[1], 0p, 10);
    3130        }
    3231        if (2 < argc) {
    33                 total_frames = strtol(argv[2], 0p, 10);
     32                total_frames = strto(argv[2], 0p, 10);
    3433        }
    3534
     
    4342        }
    4443        Time end_time = timeHiRes();
    45         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     44        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    4645}
  • doc/theses/andrew_beach_MMath/code/throw-detor.cpp

    rdd1cc02 r5a40e4e  
    44#include <exception>
    55#include <iostream>
     6#include <iomanip>
    67
     8using namespace std;
    79using namespace std::chrono;
    810
     
    4446        time_point<steady_clock> end_time = steady_clock::now();
    4547        nanoseconds duration = duration_cast<nanoseconds>(end_time - start_time);
    46         std::cout << "Run-Time (ns): " << duration.count() << std::endl;
     48        cout << "Run-Time (s): " << fixed << setprecision(1) << duration.count() / 1'000'000'000. << endl;
    4749}
  • doc/theses/andrew_beach_MMath/code/throw-empty.cfa

    rdd1cc02 r5a40e4e  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.hfa>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(empty_exception)();
    8 
    9 EHM_VIRTUAL_TABLE(empty_exception, empty_vt);
     7exception empty_exception;
     8vtable(empty_exception) empty_vt;
    109
    1110void unwind_empty(unsigned int frames) {
     
    2120        unsigned int total_frames = 1;
    2221        if (1 < argc) {
    23                 times = strtol(argv[1], 0p, 10);
     22                times = strto(argv[1], 0p, 10);
    2423        }
    2524        if (2 < argc) {
    26                 total_frames = strtol(argv[2], 0p, 10);
     25                total_frames = strto(argv[2], 0p, 10);
    2726        }
    2827
     
    3635        }
    3736        Time end_time = timeHiRes();
    38         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     37        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    3938}
  • doc/theses/andrew_beach_MMath/code/throw-empty.cpp

    rdd1cc02 r5a40e4e  
    11// Throw Across Empty Function
    22#include <chrono>
     3#include <cstdio>
    34#include <cstdlib>
    45#include <exception>
    56#include <iostream>
     7#include <iomanip>
    68
     9using namespace std;
    710using namespace std::chrono;
    811
     
    1215        if (frames) {
    1316                unwind_empty(frames - 1);
     17                if (-1 == frames) printf("~");
    1418        } else {
    1519                throw (EmptyException){};
     
    3741        time_point<steady_clock> end_time = steady_clock::now();
    3842        nanoseconds duration = duration_cast<nanoseconds>(end_time - start_time);
    39         std::cout << "Run-Time (ns): " << duration.count() << std::endl;
     43        cout << "Run-Time (s): " << fixed << setprecision(1) << duration.count() / 1'000'000'000. << endl;
    4044}
  • doc/theses/andrew_beach_MMath/code/throw-empty.py

    rdd1cc02 r5a40e4e  
    3333
    3434    end_time = thread_time_ns()
    35     print('Run-Time (ns):', end_time - start_time)
     35    print('Run-Time (s): {:.1f}'.format((end_time - start_time) / 1_000_000_000.))
    3636
    3737
  • doc/theses/andrew_beach_MMath/code/throw-finally.cfa

    rdd1cc02 r5a40e4e  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.hfa>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(empty_exception)();
     7exception empty_exception;
     8vtable(empty_exception) empty_vt;
    89
    9 EHM_VIRTUAL_TABLE(empty_exception, empty_vt);
     10unsigned int frames;                                                                    // use global because of gcc thunk problem
    1011
    11 void unwind_finally(unsigned int frames) {
     12void unwind_finally(unsigned int dummy) {
    1213        if (frames) {
     14                frames -= 1;
    1315                try {
    14                         unwind_finally(frames - 1);
     16                        unwind_finally(42);
    1517                } finally {
    1618                        asm volatile ("# finally block");
    1719                }
    1820        } else {
     21                dummy = 42;
    1922                throw (empty_exception){&empty_vt};
    2023        }
     
    2528        unsigned int total_frames = 1;
    2629        if (1 < argc) {
    27                 times = strtol(argv[1], 0p, 10);
     30                times = strto(argv[1], 0p, 10);
    2831        }
    2932        if (2 < argc) {
    30                 total_frames = strtol(argv[2], 0p, 10);
     33                total_frames = strto(argv[2], 0p, 10);
    3134        }
     35        frames = total_frames;
    3236
    3337        Time start_time = timeHiRes();
    3438        for (int count = 0 ; count < times ; ++count) {
    3539                try {
    36                         unwind_finally(total_frames);
     40                        unwind_finally(42);
    3741                } catch (empty_exception *) {
    3842                        asm volatile ("# catch block");
     
    4044        }
    4145        Time end_time = timeHiRes();
    42         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     46        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    4347}
  • doc/theses/andrew_beach_MMath/code/throw-finally.py

    rdd1cc02 r5a40e4e  
    3636
    3737    end_time = thread_time_ns()
    38     print('Run-Time (ns):', end_time - start_time)
     38    print('Run-Time (s): {:.1f}'.format((end_time - start_time) / 1_000_000_000.))
    3939
    4040
  • doc/theses/andrew_beach_MMath/code/throw-other.cfa

    rdd1cc02 r5a40e4e  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.hfa>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(empty_exception)();
     7exception empty_exception;
     8vtable(empty_exception) empty_vt;
     9exception not_raised_exception;
    810
    9 EHM_VIRTUAL_TABLE(empty_exception, empty_vt);
     11unsigned int frames;                                                                    // use global because of gcc thunk problem
    1012
    11 EHM_EXCEPTION(not_raised_exception)();
    12 
    13 void unwind_other(unsigned int frames) {
     13void unwind_other(unsigned int dummy) {
    1414        if (frames) {
     15                frames -= 1;
    1516                try {
    16                         unwind_other(frames - 1);
     17                        unwind_other(42);
    1718                } catch (not_raised_exception *) {
    1819                        asm volatile ("# catch block (stack)");
    1920                }
    2021        } else {
     22                dummy = 42;
    2123                throw (empty_exception){&empty_vt};
    2224        }
     
    2729        unsigned int total_frames = 1;
    2830        if (1 < argc) {
    29                 times = strtol(argv[1], 0p, 10);
     31                times = strto(argv[1], 0p, 10);
    3032        }
    3133        if (2 < argc) {
    32                 total_frames = strtol(argv[2], 0p, 10);
     34                total_frames = strto(argv[2], 0p, 10);
    3335        }
     36        frames = total_frames;
    3437
    3538        Time start_time = timeHiRes();
    3639        for (int count = 0 ; count < times ; ++count) {
    3740                try {
    38                         unwind_other(total_frames);
     41                        unwind_other(42);
    3942                } catch (empty_exception *) {
    4043                        asm volatile ("# catch block (base)");
     
    4245        }
    4346        Time end_time = timeHiRes();
    44         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     47        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    4548}
  • doc/theses/andrew_beach_MMath/code/throw-other.cpp

    rdd1cc02 r5a40e4e  
    44#include <exception>
    55#include <iostream>
     6#include <iomanip>
    67
     8using namespace std;
    79using namespace std::chrono;
    810
     
    4345        time_point<steady_clock> end_time = steady_clock::now();
    4446        nanoseconds duration = duration_cast<nanoseconds>(end_time - start_time);
    45         std::cout << "Run-Time (ns): " << duration.count() << std::endl;
     47        cout << "Run-Time (s): " << fixed << setprecision(1) << duration.count() / 1'000'000'000. << endl;
    4648}
  • doc/theses/andrew_beach_MMath/code/throw-other.py

    rdd1cc02 r5a40e4e  
    4040
    4141    end_time = thread_time_ns()
    42     print('Run-Time (ns):', end_time - start_time)
     42    print('Run-Time (s): {:.1f}'.format((end_time - start_time) / 1_000_000_000.))
    4343
    4444
  • doc/theses/andrew_beach_MMath/code/throw-with.py

    rdd1cc02 r5a40e4e  
    4343
    4444    end_time = thread_time_ns()
    45     print('Run-Time (ns):', end_time - start_time)
     45    print('Run-Time (s): {:.1f}'.format((end_time - start_time) / 1_000_000_000.))
    4646
    4747
  • doc/theses/andrew_beach_MMath/code/try-catch.cfa

    rdd1cc02 r5a40e4e  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.hfa>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(not_raised_exception)();
    8 
    9 EHM_VIRTUAL_TABLE(not_raised_exception, not_vt);
     7exception not_raised_exception;
     8vtable(not_raised_exception) not_vt;
    109
    1110int main(int argc, char * argv[]) {
     
    1312        volatile bool should_throw = false;
    1413        if (1 < argc) {
    15                 times = strtol(argv[1], 0p, 10);
     14                times = strto(argv[1], 0p, 10);
    1615        }
    1716
     
    2827        }
    2928        Time end_time = timeHiRes();
    30         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     29        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    3130}
  • doc/theses/andrew_beach_MMath/code/try-catch.cpp

    rdd1cc02 r5a40e4e  
    44#include <exception>
    55#include <iostream>
     6#include <iomanip>
    67
     8using namespace std;
    79using namespace std::chrono;
    810
     
    2931        time_point<steady_clock> end_time = steady_clock::now();
    3032        nanoseconds duration = duration_cast<nanoseconds>(end_time - start_time);
    31         std::cout << "Run-Time (ns): " << duration.count() << std::endl;
     33        cout << "Run-Time (s): " << fixed << setprecision(1) << duration.count() / 1'000'000'000. << endl;
    3234}
  • doc/theses/andrew_beach_MMath/code/try-catch.py

    rdd1cc02 r5a40e4e  
    2323
    2424    end_time = thread_time_ns()
    25     print('Run-Time (ns):', end_time - start_time)
     25    print('Run-Time (s): {:.1f}'.format((end_time - start_time) / 1_000_000_000.))
    2626
    2727
  • doc/theses/andrew_beach_MMath/code/try-finally.cfa

    rdd1cc02 r5a40e4e  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.hfa>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(not_raised_exception)();
    8 
    9 EHM_VIRTUAL_TABLE(not_raised_exception, not_vt);
     7exception not_raised_exception;
     8vtable(not_raised_exception) not_vt;
    109
    1110int main(int argc, char * argv[]) {
     
    1312        volatile bool should_throw = false;
    1413        if (1 < argc) {
    15                 times = strtol(argv[1], 0p, 10);
     14                times = strto(argv[1], 0p, 10);
    1615        }
    1716
     
    2827        }
    2928        Time end_time = timeHiRes();
    30         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     29        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    3130}
  • doc/theses/andrew_beach_MMath/code/try-finally.py

    rdd1cc02 r5a40e4e  
    2222
    2323    end_time = thread_time_ns()
    24     print('Run-Time (ns):', end_time - start_time)
     24    print('Run-Time (s): {:.1f}'.format((end_time - start_time) / 1_000_000_000.))
    2525
    2626
  • doc/theses/andrew_beach_MMath/code/try-resume.cfa

    rdd1cc02 r5a40e4e  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.hfa>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(not_raised_exception)();
     7exception not_raised_exception;
    88
    99int main(int argc, char * argv[]) {
     
    1111        unsigned int total_frames = 1;
    1212        if (1 < argc) {
    13                 times = strtol(argv[1], 0p, 10);
     13                times = strto(argv[1], 0p, 10);
    1414        }
    1515        if (2 < argc) {
    16                 total_frames = strtol(argv[2], 0p, 10);
     16                total_frames = strto(argv[2], 0p, 10);
    1717        }
    1818
     
    2626        }
    2727        Time end_time = timeHiRes();
    28         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     28        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    2929}
  • doc/theses/andrew_beach_MMath/conclusion.tex

    rdd1cc02 r5a40e4e  
    11\chapter{Conclusion}
     2\label{c:conclusion}
    23% Just a little knot to tie the paper together.
    34
    45In the previous chapters this thesis presents the design and implementation
    56of \CFA's exception handling mechanism (EHM).
    6 Both the design and implementation are based off of tools and techniques
    7 developed for other programming languages but they were adapted to better fit
    8 \CFA's feature set.
     7Both the design and implementation are based off of tools and
     8techniques developed for other programming languages but they were adapted to
     9better fit \CFA's feature set and add a few features that do not exist in
     10other EHMs;
     11including conditional matching, default handlers for unhandled exceptions
     12and cancellation though coroutines and threads back to the program main stack.
    913
    1014The resulting features cover all of the major use cases of the most popular
    1115termination EHMs of today, along with reintroducing resumption exceptions and
    12 creating some new features that fix with \CFA's larger programming patterns.
     16creating some new features that fit with \CFA's larger programming patterns,
     17such as virtuals independent of traditional objects.
    1318
    14 The implementation has been tested and compared to other implementations.
     19The \CFA project's test suite has been expanded to test the EHM.
     20The implementation's performance has also been
     21compared to other implementations with a small set of targeted
     22micro-benchmarks.
    1523The results, while not cutting edge, are good enough for prototyping, which
    16 is \CFA's stage of development.
     24is \CFA's current stage of development.
    1725
    18 This is a valuable new feature for \CFA in its own right but also serves
    19 as a tool (and motivation) for other developments in the language.
     26This initial EHM will bring valuable new features to \CFA in its own right
     27but also serves as a tool and motivation for other developments in the
     28language.
  • doc/theses/andrew_beach_MMath/exception-layout.fig

    rdd1cc02 r5a40e4e  
    2828        0 0 1.00 240.00 240.00
    2929         360 405 360 2070
    30 4 0 0 50 -1 0 12 0.0000 4 135 1080 2700 585 Fixed Header\001
    31 4 0 0 50 -1 0 12 0.0000 4 135 1710 540 990 Cforall Information\001
    32 4 0 0 50 -1 0 12 0.0000 4 165 1530 540 585 _Unwind_Exception\001
    33 4 0 0 50 -1 0 12 0.0000 4 165 1260 540 1530 User Exception\001
    34 4 0 0 50 -1 0 12 0.0000 4 165 1170 2655 1530 Variable Body\001
    35 4 0 0 50 -1 0 12 0.0000 4 165 1260 2655 1215 (Fixed Offset)\001
     304 0 0 50 -1 0 12 0.0000 0 135 1080 2700 585 Fixed Header\001
     314 0 0 50 -1 0 12 0.0000 0 135 1575 540 990 Cforall Information\001
     324 0 0 50 -1 0 12 0.0000 0 180 1695 540 585 _Unwind_Exception\001
     334 0 0 50 -1 0 12 0.0000 0 180 1245 540 1530 User Exception\001
     344 0 0 50 -1 0 12 0.0000 0 180 1185 2655 1530 Variable Body\001
     354 0 0 50 -1 0 12 0.0000 0 165 1110 2655 1215 (Fixed Offset)\001
  • doc/theses/andrew_beach_MMath/existing.tex

    rdd1cc02 r5a40e4e  
    1010
    1111Only those \CFA features pertaining to this thesis are discussed.
    12 % Also, only new features of \CFA will be discussed,
    1312A familiarity with
    1413C or C-like languages is assumed.
     
    1716\CFA has extensive overloading, allowing multiple definitions of the same name
    1817to be defined~\cite{Moss18}.
    19 \begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
    20 char @i@; int @i@; double @i@;
    21 int @f@(); double @f@();
    22 void @g@( int ); void @g@( double );
    23 \end{lstlisting}
     18\begin{cfa}
     19char i; int i; double i;
     20int f(); double f();
     21void g( int ); void g( double );
     22\end{cfa}
    2423This feature requires name mangling so the assembly symbols are unique for
    2524different overloads. For compatibility with names in C, there is also a syntax
     
    6362int && rri = ri;
    6463rri = 3;
    65 &ri = &j; // rebindable
     64&ri = &j;
    6665ri = 5;
    6766\end{cfa}
     
    7978\end{minipage}
    8079
    81 References are intended for pointer situations where dereferencing is the common usage,
    82 \ie the value is more important than the pointer.
     80References are intended to be used when the indirection of a pointer is
     81required, but the address is not as important as the value and dereferencing
     82is the common usage.
    8383Mutable references may be assigned to by converting them to a pointer
    84 with a @&@ and then assigning a pointer to them, as in @&ri = &j;@ above
     84with a @&@ and then assigning a pointer to them, as in @&ri = &j;@ above.
     85% ???
    8586
    8687\section{Operators}
    8788
    8889\CFA implements operator overloading by providing special names, where
    89 operator usages are translated into function calls using these names.
     90operator expressions are translated into function calls using these names.
    9091An operator name is created by taking the operator symbols and joining them with
    9192@?@s to show where the arguments go.
     
    9495This syntax make it easy to tell the difference between prefix operations
    9596(such as @++?@) and post-fix operations (@?++@).
    96 For example, plus and equality operators are defined for a point type.
     97
     98As an example, here are the addition and equality operators for a point type.
    9799\begin{cfa}
    98100point ?+?(point a, point b) { return point{a.x + b.x, a.y + b.y}; }
     
    102104}
    103105\end{cfa}
    104 Note these special names are not limited to builtin
    105 operators, and hence, may be used with arbitrary types.
    106 \begin{cfa}
    107 double ?+?( int x, point y ); // arbitrary types
    108 \end{cfa}
    109 % Some ``near misses", that are that do not match an operator form but looks like
    110 % it may have been supposed to, will generate warning but otherwise they are
    111 % left alone.
    112 Because operators are never part of the type definition they may be added
    113 at any time, including on built-in types.
     106Note that this syntax works effectively but a textual transformation,
     107the compiler converts all operators into functions and then resolves them
     108normally. This means any combination of types may be used,
     109although nonsensical ones (like @double ?==?(point, int);@) are discouraged.
     110This feature is also used for all builtin operators as well,
     111although those are implicitly provided by the language.
    114112
    115113%\subsection{Constructors and Destructors}
    116 
    117 \CFA also provides constructors and destructors as operators, which means they
    118 are functions with special operator names rather than type names in \Cpp.
    119 While constructors and destructions are normally called implicitly by the compiler,
    120 the special operator names, allow explicit calls.
    121 
    122 % Placement new means that this is actually equivalent to C++.
     114In \CFA, constructors and destructors are operators, which means they are
     115functions with special operator names rather than type names in \Cpp.
     116Both constructors and destructors can be implicity called by the compiler,
     117however the operator names allow explicit calls.
     118% Placement new means that this is actually equivant to C++.
    123119
    124120The special name for a constructor is @?{}@, which comes from the
     
    129125struct Example { ... };
    130126void ?{}(Example & this) { ... }
     127{
     128        Example a;
     129        Example b = {};
     130}
    131131void ?{}(Example & this, char first, int num) { ... }
    132 Example a;              // implicit constructor calls
    133 Example b = {};
    134 Example c = {'a', 2};
    135 \end{cfa}
    136 Both @a@ and @b@ are initialized with the first constructor,
    137 while @c@ is initialized with the second.
    138 Constructor calls can be replaced with C initialization using special operator \lstinline{@=}.
    139 \begin{cfa}
    140 Example d @= {42};
    141 \end{cfa}
     132{
     133        Example c = {'a', 2};
     134}
     135\end{cfa}
     136Both @a@ and @b@ will be initalized with the first constructor,
     137@b@ because of the explicit call and @a@ implicitly.
     138@c@ will be initalized with the second constructor.
     139Currently, there is no general way to skip initialation.
     140% I don't use @= anywhere in the thesis.
     141
    142142% I don't like the \^{} symbol but $^\wedge$ isn't better.
    143143Similarly, destructors use the special name @^?{}@ (the @^@ has no special
    144144meaning).
    145 % These are a normally called implicitly called on a variable when it goes out
    146 % of scope. They can be called explicitly as well.
    147145\begin{cfa}
    148146void ^?{}(Example & this) { ... }
    149147{
    150         Example e;      // implicit constructor call
    151         ^?{}(e);                // explicit destructor call
    152         ?{}(e);         // explicit constructor call
    153 } // implicit destructor call
     148        Example d;
     149        ^?{}(d);
     150
     151        Example e;
     152} // Implicit call of ^?{}(e);
    154153\end{cfa}
    155154
     
    225224The global definition of @do_once@ is ignored, however if quadruple took a
    226225@double@ argument, then the global definition would be used instead as it
    227 is a better match.
    228 % Aaron's thesis might be a good reference here.
    229 
    230 To avoid typing long lists of assertions, constraints can be collect into
    231 convenient package called a @trait@, which can then be used in an assertion
     226would then be a better match.\cite{Moss19}
     227
     228To avoid typing long lists of assertions, constraints can be collected into
     229convenient a package called a @trait@, which can then be used in an assertion
    232230instead of the individual constraints.
    233231\begin{cfa}
     
    253251        node(T) * next;
    254252        T * data;
    255 }
     253};
    256254node(int) inode;
    257255\end{cfa}
     
    293291};
    294292CountUp countup;
    295 for (10) sout | resume(countup).next; // print 10 values
    296293\end{cfa}
    297294Each coroutine has a @main@ function, which takes a reference to a coroutine
    298295object and returns @void@.
    299296%[numbers=left] Why numbers on this one?
    300 \begin{cfa}[numbers=left,numberstyle=\scriptsize\sf]
     297\begin{cfa}
    301298void main(CountUp & this) {
    302         for (unsigned int up = 0;; ++up) {
    303                 this.next = up;
     299        for (unsigned int next = 0 ; true ; ++next) {
     300                this.next = next;
    304301                suspend;$\label{suspend}$
    305302        }
     
    307304\end{cfa}
    308305In this function, or functions called by this function (helper functions), the
    309 @suspend@ statement is used to return execution to the coroutine's resumer
    310 without terminating the coroutine's function(s).
     306@suspend@ statement is used to return execution to the coroutine's caller
     307without terminating the coroutine's function.
    311308
    312309A coroutine is resumed by calling the @resume@ function, \eg @resume(countup)@.
    313310The first resume calls the @main@ function at the top. Thereafter, resume calls
    314311continue a coroutine in the last suspended function after the @suspend@
    315 statement, in this case @main@ line~\ref{suspend}.  The @resume@ function takes
    316 a reference to the coroutine structure and returns the same reference. The
    317 return value allows easy access to communication variables defined in the
    318 coroutine object. For example, the @next@ value for coroutine object @countup@
    319 is both generated and collected in the single expression:
    320 @resume(countup).next@.
     312statement. In this case there is only one and, hence, the difference between
     313subsequent calls is the state of variables inside the function and the
     314coroutine object.
     315The return value of @resume@ is a reference to the coroutine, to make it
     316convent to access fields of the coroutine in the same expression.
     317Here is a simple example in a helper function:
     318\begin{cfa}
     319unsigned int get_next(CountUp & this) {
     320        return resume(this).next;
     321}
     322\end{cfa}
     323
     324When the main function returns the coroutine halts and can no longer be
     325resumed.
    321326
    322327\subsection{Monitor and Mutex Parameter}
     
    330335exclusion on a monitor object by qualifying an object reference parameter with
    331336@mutex@.
    332 \begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
    333 void example(MonitorA & @mutex@ argA, MonitorB & @mutex@ argB);
    334 \end{lstlisting}
     337\begin{cfa}
     338void example(MonitorA & mutex argA, MonitorB & mutex argB);
     339\end{cfa}
    335340When the function is called, it implicitly acquires the monitor lock for all of
    336341the mutex parameters without deadlock.  This semantics means all functions with
     
    362367{
    363368        StringWorker stringworker; // fork thread running in "main"
    364 } // implicitly join with thread / wait for completion
     369} // Implicit call to join(stringworker), waits for completion.
    365370\end{cfa}
    366371The thread main is where a new thread starts execution after a fork operation
  • doc/theses/andrew_beach_MMath/features.tex

    rdd1cc02 r5a40e4e  
    1919
    2020\paragraph{Raise}
    21 The raise is the starting point for exception handling
     21The raise is the starting point for exception handling,
    2222by raising an exception, which passes it to
    2323the EHM.
     
    3030\paragraph{Handle}
    3131The primary purpose of an EHM is to run some user code to handle a raised
    32 exception. This code is given, with some other information, in a handler.
     32exception. This code is given, along with some other information,
     33in a handler.
    3334
    3435A handler has three common features: the previously mentioned user code, a
    35 region of code it guards, and an exception label/condition that matches
    36 the raised exception.
     36region of code it guards and an exception label/condition that matches
     37against the raised exception.
    3738Only raises inside the guarded region and raising exceptions that match the
    3839label can be handled by a given handler.
     
    4142
    4243The @try@ statements of \Cpp, Java and Python are common examples. All three
    43 show the common features of guarded region, raise, matching and handler.
    44 \begin{cfa}
    45 try {                           // guarded region
    46         ...     
    47         throw exception;        // raise
    48         ...     
    49 } catch( exception ) {  // matching condition, with exception label
    50         ...                             // handler code
    51 }
    52 \end{cfa}
     44also show another common feature of handlers, they are grouped by the guarded
     45region.
    5346
    5447\subsection{Propagation}
    5548After an exception is raised comes what is usually the biggest step for the
    56 EHM: finding and setting up the handler for execution. The propagation from raise to
     49EHM: finding and setting up the handler for execution.
     50The propagation from raise to
    5751handler can be broken up into three different tasks: searching for a handler,
    5852matching against the handler and installing the handler.
     
    6054\paragraph{Searching}
    6155The EHM begins by searching for handlers that might be used to handle
    62 the exception. The search is restricted to
    63 handlers that have the raise site in their guarded
     56the exception.
     57The search will find handlers that have the raise site in their guarded
    6458region.
    6559The search includes handlers in the current function, as well as any in
     
    6761
    6862\paragraph{Matching}
    69 Each handler found is matched with the raised exception. The exception
     63Each handler found is with the raised exception. The exception
    7064label defines a condition that is used with the exception and decides if
    7165there is a match or not.
     66%
    7267In languages where the first match is used, this step is intertwined with
    7368searching; a match check is performed immediately after the search finds
     
    8479different course of action for this case.
    8580This situation only occurs with unchecked exceptions as checked exceptions
    86 (such as in Java) are guaranteed to find a matching handler.
     81(such as in Java) can make the guarantee.
    8782The unhandled action is usually very general, such as aborting the program.
    8883
     
    9893A handler labeled with any given exception can handle exceptions of that
    9994type or any child type of that exception. The root of the exception hierarchy
    100 (here \code{C}{exception}) acts as a catch-all, leaf types catch single types,
     95(here \code{C}{exception}) acts as a catch-all, leaf types catch single types
    10196and the exceptions in the middle can be used to catch different groups of
    10297related exceptions.
    10398
    10499This system has some notable advantages, such as multiple levels of grouping,
    105 the ability for libraries to add new exception types, and the isolation
     100the ability for libraries to add new exception types and the isolation
    106101between different sub-hierarchies.
    107102This design is used in \CFA even though it is not a object-orientated
     
    123118For effective exception handling, additional information is often passed
    124119from the raise to the handler and back again.
    125 So far, only communication of the exception's identity is covered.
    126 A common communication method for passing more information is putting fields into the exception instance
     120So far, only communication of the exceptions' identity is covered.
     121A common communication method for adding information to an exception
     122is putting fields into the exception instance
    127123and giving the handler access to them.
    128 Using reference fields pointing to data at the raise location allows data to be
    129 passed in both directions.
     124% You can either have pointers/references in the exception, or have p/rs to
     125% the exception when it doesn't have to be copied.
     126Passing references or pointers allows data at the raise location to be
     127updated, passing information in both directions.
    130128
    131129\section{Virtuals}
     130\label{s:virtuals}
    132131Virtual types and casts are not part of \CFA's EHM nor are they required for
    133132an EHM.
    134133However, one of the best ways to support an exception hierarchy
    135134is via a virtual hierarchy and dispatch system.
    136 
    137 Ideally, the virtual system should have been part of \CFA before the work
     135Ideally, the virtual system would have been part of \CFA before the work
    138136on exception handling began, but unfortunately it was not.
    139137Hence, only the features and framework needed for the EHM were
    140 designed and implemented for this thesis. Other features were considered to ensure that
     138designed and implemented for this thesis.
     139Other features were considered to ensure that
    141140the structure could accommodate other desirable features in the future
    142141but are not implemented.
    143142The rest of this section only discusses the implemented subset of the
    144 virtual-system design.
     143virtual system design.
    145144
    146145The virtual system supports multiple ``trees" of types. Each tree is
     
    149148number of children.
    150149Any type that belongs to any of these trees is called a virtual type.
    151 
    152150% A type's ancestors are its parent and its parent's ancestors.
    153151% The root type has no ancestors.
    154152% A type's descendants are its children and its children's descendants.
    155153
    156 Every virtual type also has a list of virtual members. Children inherit
    157 their parent's list of virtual members but may add new members to it.
    158 It is important to note that these are virtual members, not virtual methods
    159 of object-orientated programming, and can be of any type.
    160 
    161 \PAB{Need to look at these when done.
    162 
    163 \CFA still supports virtual methods as a special case of virtual members.
    164 Function pointers that take a pointer to the virtual type are modified
    165 with each level of inheritance so that refers to the new type.
    166 This means an object can always be passed to a function in its virtual table
    167 as if it were a method.
    168 \todo{Clarify (with an example) virtual methods.}
    169 
    170 Each virtual type has a unique id.
    171 This id and all the virtual members are combined
    172 into a virtual table type. Each virtual type has a pointer to a virtual table
    173 as a hidden field.
    174 \todo{Might need a diagram for virtual structure.}
    175 }%
     154For the purposes of illustration, a proposed -- but unimplemented syntax --
     155will be used. Each virtual type is represented by a trait with an annotation
     156that makes it a virtual type. This annotation is empty for a root type, which
     157creates a new tree:
     158\begin{cfa}
     159trait root_type(T) virtual() {}
     160\end{cfa}
     161The annotation may also refer to any existing virtual type to make this new
     162type a child of that type and part of the same tree. The parent may itself
     163be a child or a root type and may have any number of existing children.
     164
     165% OK, for some reason the b and t positioning options are reversed here.
     166\begin{minipage}[b]{0.6\textwidth}
     167\begin{cfa}
     168trait child_a(T) virtual(root_type) {}
     169trait grandchild(T) virtual(child_a) {}
     170trait child_b(T) virtual(root_type) {}
     171\end{cfa}
     172\end{minipage}
     173\begin{minipage}{0.4\textwidth}
     174\begin{center}
     175\input{virtual-tree}
     176\end{center}
     177\end{minipage}
     178
     179Every virtual type also has a list of virtual members and a unique id,
     180both are stored in a virtual table.
     181Every instance of a virtual type also has a pointer to a virtual table stored
     182in it, although there is no per-type virtual table as in many other languages.
     183
     184The list of virtual members is built up down the tree. Every virtual type
     185inherits the list of virtual members from its parent and may add more
     186virtual members to the end of the list which are passed on to its children.
     187Again, using the unimplemented syntax this might look like:
     188\begin{cfa}
     189trait root_type(T) virtual() {
     190        const char * to_string(T const & this);
     191        unsigned int size;
     192}
     193
     194trait child_type(T) virtual(root_type) {
     195        char * irrelevant_function(int, char);
     196}
     197\end{cfa}
     198% Consider adding a diagram, but we might be good with the explanation.
     199
     200As @child_type@ is a child of @root_type@ it has the virtual members of
     201@root_type@ (@to_string@ and @size@) as well as the one it declared
     202(@irrelevant_function@).
     203
     204It is important to note that these are virtual members, and may contain   
     205arbitrary fields, functions or otherwise.
     206The names ``size" and ``align" are reserved for the size and alignment of the
     207virtual type, and are always automatically initialized as such.
     208The other special case are uses of the trait's polymorphic argument
     209(@T@ in the example), which are always updated to refer to the current
     210virtual type. This allows functions that refer to to polymorphic argument
     211to act as traditional virtual methods (@to_string@ in the example), as the
     212object can always be passed to a virtual method in its virtual table.
    176213
    177214Up until this point the virtual system is similar to ones found in
    178 object-orientated languages but this is where \CFA diverges. Objects encapsulate a
    179 single set of methods in each type, universally across the entire program,
    180 and indeed all programs that use that type definition. Even if a type inherits and adds methods, it still encapsulate a
    181 single set of methods. In this sense,
    182 object-oriented types are ``closed" and cannot be altered.
    183 
    184 In \CFA, types do not encapsulate any code. Traits are local for each function and
    185 types can satisfy a local trait, stop satisfying it or, satisfy the same
    186 trait in a different way at any lexical location in the program where a function is call.
    187 In this sense, the set of functions/variables that satisfy a trait for a type is ``open" as the set can change at every call site.
     215object-oriented languages but this is where \CFA diverges.
     216Objects encapsulate a single set of methods in each type,
     217universally across the entire program,
     218and indeed all programs that use that type definition.
     219The only way to change any method is to inherit and define a new type with
     220its own universal implementation. In this sense,
     221these object-oriented types are ``closed" and cannot be altered.
     222% Because really they are class oriented.
     223
     224In \CFA, types do not encapsulate any code.
     225Whether or not satisfies any given assertion, and hence any trait, is
     226context sensitive. Types can begin to satisfy a trait, stop satisfying it or
     227satisfy the same trait at any lexical location in the program.
     228In this sense, an type's implementation in the set of functions and variables
     229that allow it to satisfy a trait is ``open" and can change
     230throughout the program.
    188231This capability means it is impossible to pick a single set of functions
    189232that represent a type's implementation across a program.
     
    192235type. A user can define virtual tables that are filled in at their
    193236declaration and given a name. Anywhere that name is visible, even if it is
    194 defined locally inside a function \PAB{What does this mean? (although that means it does not have a
    195 static lifetime)}, it can be used.
     237defined locally inside a function (although in this case the user must ensure
     238it outlives any objects that use it), it can be used.
    196239Specifically, a virtual type is ``bound" to a virtual table that
    197240sets the virtual members for that object. The virtual members can be accessed
    198241through the object.
     242
     243This means virtual tables are declared and named in \CFA.
     244They are declared as variables, using the type
     245@vtable(VIRTUAL_TYPE)@ and any valid name. For example:
     246\begin{cfa}
     247vtable(virtual_type_name) table_name;
     248\end{cfa}
     249
     250Like any variable they may be forward declared with the @extern@ keyword.
     251Forward declaring virtual tables is relatively common.
     252Many virtual types have an ``obvious" implementation that works in most
     253cases.
     254A pattern that has appeared in the early work using virtuals is to
     255implement a virtual table with the the obvious definition and place a forward
     256declaration of it in the header beside the definition of the virtual type.
     257
     258Even on the full declaration, no initializer should be used.
     259Initialization is automatic.
     260The type id and special virtual members ``size" and ``align" only depend on
     261the virtual type, which is fixed given the type of the virtual table and
     262so the compiler fills in a fixed value.
     263The other virtual members are resolved, using the best match to the member's
     264name and type, in the same context as the virtual table is declared using
     265\CFA's normal resolution rules.
    199266
    200267While much of the virtual infrastructure is created, it is currently only used
     
    212279@EXPRESSION@ object, otherwise it returns @0p@ (null pointer).
    213280
    214 \section{Exception}
    215 % Leaving until later, hopefully it can talk about actual syntax instead
    216 % of my many strange macros. Syntax aside I will also have to talk about the
    217 % features all exceptions support.
    218 
    219 Exceptions are defined by the trait system; there are a series of traits, and
    220 if a type satisfies them, then it can be used as an exception. The following
     281\section{Exceptions}
     282
     283The syntax for declaring an exception is the same as declaring a structure
     284except the keyword that is swapped out:
     285\begin{cfa}
     286exception TYPE_NAME {
     287        FIELDS
     288};
     289\end{cfa}
     290
     291Fields are filled in the same way as a structure as well. However an extra
     292field is added that contains the pointer to the virtual table.
     293It must be explicitly initialized by the user when the exception is
     294constructed.
     295
     296Here is an example of declaring an exception type along with a virtual table,
     297assuming the exception has an ``obvious" implementation and a default
     298virtual table makes sense.
     299
     300\begin{minipage}[t]{0.4\textwidth}
     301Header:
     302\begin{cfa}
     303exception Example {
     304        int data;
     305};
     306
     307extern vtable(Example)
     308        example_base_vtable;
     309\end{cfa}
     310\end{minipage}
     311\begin{minipage}[t]{0.6\textwidth}
     312Source:
     313\begin{cfa}
     314vtable(Example) example_base_vtable
     315\end{cfa}
     316\vfil
     317\end{minipage}
     318
     319%\subsection{Exception Details}
     320This is the only interface needed when raising and handling exceptions.
     321However it is actually a short hand for a more complex
     322trait based interface.
     323
     324The language views exceptions through a series of traits.
     325If a type satisfies them, then it can be used as an exception. The following
    221326is the base trait all exceptions need to match.
    222327\begin{cfa}
     
    225330};
    226331\end{cfa}
    227 The trait is defined over two types, the exception type and the virtual table
     332The trait is defined over two types: the exception type and the virtual table
    228333type. Each exception type should have a single virtual table type.
    229334There are no actual assertions in this trait because the trait system
     
    231336completing the virtual system). The imaginary assertions would probably come
    232337from a trait defined by the virtual system, and state that the exception type
    233 is a virtual type, is a descendant of @exception_t@ (the base exception type),
    234 and note its virtual table type.
     338is a virtual type, is a descendant of @exception_t@ (the base exception type)
     339and allow the user to find the virtual table type.
    235340
    236341% I did have a note about how it is the programmer's responsibility to make
     
    250355};
    251356\end{cfa}
    252 Both traits ensure a pair of types are an exception type, its virtual table
    253 type,
     357Both traits ensure a pair of types is an exception type, its virtual table
     358type
    254359and defines one of the two default handlers. The default handlers are used
    255360as fallbacks and are discussed in detail in \vref{s:ExceptionHandling}.
     
    260365facing way. So these three macros are provided to wrap these traits to
    261366simplify referring to the names:
    262 @IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@, and @IS_RESUMPTION_EXCEPTION@.
     367@IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@ and @IS_RESUMPTION_EXCEPTION@.
    263368
    264369All three take one or two arguments. The first argument is the name of the
     
    283388These twin operations are the core of \CFA's exception handling mechanism.
    284389This section covers the general patterns shared by the two operations and
    285 then goes on to cover the details of each individual operation.
     390then goes on to cover the details each individual operation.
    286391
    287392Both operations follow the same set of steps.
    288393First, a user raises an exception.
    289 Second, the exception propagates up the stack.
     394Second, the exception propagates up the stack, searching for a handler.
    290395Third, if a handler is found, the exception is caught and the handler is run.
    291396After that control continues at a raise-dependent location.
    292 Fourth, if a handler is not found, a default handler is run and, if it returns, then control
     397As an alternate to the third step,
     398if a handler is not found, a default handler is run and, if it returns,
     399then control
    293400continues after the raise.
    294401
    295 %This general description covers what the two kinds have in common.
    296 The differences in the two operations include how propagation is performed, where execution continues
    297 after an exception is caught and handled, and which default handler is run.
     402The differences between the two operations include how propagation is
     403performed, where execution continues after an exception is handled
     404and which default handler is run.
    298405
    299406\subsection{Termination}
    300407\label{s:Termination}
    301 Termination handling is the familiar EHM and used in most programming
     408Termination handling is the familiar kind of handling
     409and used in most programming
    302410languages with exception handling.
    303411It is a dynamic, non-local goto. If the raised exception is matched and
     
    331439Then propagation starts with the search. \CFA uses a ``first match" rule so
    332440matching is performed with the copied exception as the search key.
    333 It starts from the raise in the throwing function and proceeds towards the base of the stack,
     441It starts from the raise site and proceeds towards base of the stack,
    334442from callee to caller.
    335443At each stack frame, a check is made for termination handlers defined by the
     
    345453\end{cfa}
    346454When viewed on its own, a try statement simply executes the statements
    347 in the \snake{GUARDED_BLOCK}, and when those are finished,
     455in the \snake{GUARDED_BLOCK} and when those are finished,
    348456the try statement finishes.
    349457
     
    371479termination exception types.
    372480The global default termination handler performs a cancellation
    373 (see \vref{s:Cancellation} for the justification) on the current stack with the copied exception.
    374 Since it is so general, a more specific handler is usually
    375 defined, possibly with a detailed message, and used for specific exception type, effectively overriding the default handler.
     481(as described in \vref{s:Cancellation})
     482on the current stack with the copied exception.
     483Since it is so general, a more specific handler can be defined,
     484overriding the default behaviour for the specific exception types.
    376485
    377486\subsection{Resumption}
    378487\label{s:Resumption}
    379488
    380 Resumption exception handling is the less familar EHM, but is
     489Resumption exception handling is less familar form of exception handling,
     490but is
    381491just as old~\cite{Goodenough75} and is simpler in many ways.
    382492It is a dynamic, non-local function call. If the raised exception is
     
    387497function once the error is corrected, and
    388498ignorable events, such as logging where nothing needs to happen and control
    389 should always continue from the raise point.
     499should always continue from the raise site.
     500
     501Except for the changes to fit into that pattern, resumption exception
     502handling is symmetric with termination exception handling, by design
     503(see \autoref{s:Termination}).
    390504
    391505A resumption raise is started with the @throwResume@ statement:
     
    393507throwResume EXPRESSION;
    394508\end{cfa}
    395 \todo{Decide on a final set of keywords and use them everywhere.}
    396 It works much the same way as the termination throw.
    397 The expression must return a reference to a resumption exception,
    398 where the resumption exception is any type that satisfies the trait
    399 @is_resumption_exception@ at the call site.
    400 The assertions from this trait are available to
    401 the exception system while handling the exception.
    402 
    403 At run-time, no exception copy is made, since
     509% The new keywords are currently ``experimental" and not used in this work.
     510It works much the same way as the termination raise, except the
     511type must satisfy the \snake{is_resumption_exception} that uses the
     512default handler: \defaultResumptionHandler.
     513This can be specialized for particular exception types.
     514
     515At run-time, no exception copy is made. Since
    404516resumption does not unwind the stack nor otherwise remove values from the
    405 current scope, so there is no need to manage memory to keep the exception in scope.
    406 
    407 Then propagation starts with the search. It starts from the raise in the
    408 resuming function and proceeds towards the base of the stack,
    409 from callee to caller.
    410 At each stack frame, a check is made for resumption handlers defined by the
    411 @catchResume@ clauses of a @try@ statement.
     517current scope, there is no need to manage memory to keep the exception
     518allocated.
     519
     520Then propagation starts with the search,
     521following the same search path as termination,
     522from the raise site to the base of stack and top of try statement to bottom.
     523However, the handlers on try statements are defined by @catchResume@ clauses.
    412524\begin{cfa}
    413525try {
     
    419531}
    420532\end{cfa}
    421 % PAB, you say this above.
    422 % When a try statement is executed, it simply executes the statements in the
    423 % @GUARDED_BLOCK@ and then finishes.
    424 %
    425 % However, while the guarded statements are being executed, including any
    426 % invoked functions, all the handlers in these statements are included in the
    427 % search path.
    428 % Hence, if a resumption exception is raised, these handlers may be matched
    429 % against the exception and may handle it.
    430 %
    431 % Exception matching checks the handler in each catch clause in the order
    432 % they appear, top to bottom. If the representation of the raised exception type
    433 % is the same or a descendant of @EXCEPTION_TYPE@$_i$, then @NAME@$_i$
    434 % (if provided) is bound to a pointer to the exception and the statements in
    435 % @HANDLER_BLOCK@$_i$ are executed.
    436 % If control reaches the end of the handler, execution continues after the
    437 % the raise statement that raised the handled exception.
    438 %
    439 % Like termination, if no resumption handler is found during the search,
    440 % then the default handler (\defaultResumptionHandler) visible at the raise
    441 % statement is called. It will use the best match at the raise sight according
    442 % to \CFA's overloading rules. The default handler is
    443 % passed the exception given to the raise. When the default handler finishes
    444 % execution continues after the raise statement.
    445 %
    446 % There is a global @defaultResumptionHandler{} is polymorphic over all
    447 % resumption exceptions and performs a termination throw on the exception.
    448 % The \defaultTerminationHandler{} can be overridden by providing a new
    449 % function that is a better match.
    450 
    451 The @GUARDED_BLOCK@ and its associated nested guarded statements work the same
    452 for resumption as for termination, as does exception matching at each
    453 @catchResume@. Similarly, if no resumption handler is found during the search,
    454 then the currently visible default handler (\defaultResumptionHandler) is
    455 called and control continues after the raise statement if it returns. Finally,
    456 there is also a global @defaultResumptionHandler@, which can be overridden,
    457 that is polymorphic over all resumption exceptions but performs a termination
    458 throw on the exception rather than a cancellation.
    459 
    460 Throwing the exception in @defaultResumptionHandler@ has the positive effect of
    461 walking the stack a second time for a recovery handler. Hence, a programmer has
    462 two chances for help with a problem, fixup or recovery, should either kind of
    463 handler appear on the stack. However, this dual stack walk leads to following
    464 apparent anomaly:
    465 \begin{cfa}
    466 try {
    467         throwResume E;
    468 } catch (E) {
    469         // this handler runs
    470 }
    471 \end{cfa}
    472 because the @catch@ appears to handle a @throwResume@, but a @throwResume@ only
    473 matches with @catchResume@. The anomaly results because the unmatched
    474 @catchResuem@, calls @defaultResumptionHandler@, which in turn throws @E@.
    475 
    476 % I wonder if there would be some good central place for this.
    477 Note, termination and resumption handlers may be used together
     533Note that termination handlers and resumption handlers may be used together
    478534in a single try statement, intermixing @catch@ and @catchResume@ freely.
    479535Each type of handler only interacts with exceptions from the matching
    480536kind of raise.
     537Like @catch@ clauses, @catchResume@ clauses have no effect if an exception
     538is not raised.
     539
     540The matching rules are exactly the same as well.
     541The first major difference here is that after
     542@EXCEPTION_TYPE@$_i$ is matched and @NAME@$_i$ is bound to the exception,
     543@HANDLER_BLOCK@$_i$ is executed right away without first unwinding the stack.
     544After the block has finished running control jumps to the raise site, where
     545the just handled exception came from, and continues executing after it,
     546not after the try statement.
    481547
    482548\subsubsection{Resumption Marking}
     
    486552and run, its try block (the guarded statements) and every try statement
    487553searched before it are still on the stack. There presence can lead to
    488 the \emph{recursive resumption problem}.
     554the recursive resumption problem.\cite{Buhr00a}
     555% Other possible citation is MacLaren77, but the form is different.
    489556
    490557The recursive resumption problem is any situation where a resumption handler
     
    500567When this code is executed, the guarded @throwResume@ starts a
    501568search and matches the handler in the @catchResume@ clause. This
    502 call is placed on the stack above the try-block. Now the second raise in the handler
    503 searches the same try block, matches, and puts another instance of the
     569call is placed on the stack above the try-block.
     570Now the second raise in the handler searches the same try block,
     571matches again and then puts another instance of the
    504572same handler on the stack leading to infinite recursion.
    505573
    506 While this situation is trivial and easy to avoid, much more complex cycles can
    507 form with multiple handlers and different exception types.  The key point is
    508 that the programmer's intuition expects every raise in a handler to start
    509 searching \emph{below} the @try@ statement, making it difficult to understand
    510 and fix the problem.
    511 
     574While this situation is trivial and easy to avoid, much more complex cycles
     575can form with multiple handlers and different exception types.
    512576To prevent all of these cases, each try statement is ``marked" from the
    513 time the exception search reaches it to either when a matching handler
    514 completes or when the search reaches the base
     577time the exception search reaches it to either when a handler completes
     578handling that exception or when the search reaches the base
    515579of the stack.
    516580While a try statement is marked, its handlers are never matched, effectively
     
    524588for instance, marking just the handlers that caught the exception,
    525589would also prevent recursive resumption.
    526 However, the rule selected mirrors what happens with termination,
    527 and hence, matches programmer intuition that a raise searches below a try.
    528 
    529 In detail, the marked try statements are the ones that would be removed from
     590However, the rules selected mirrors what happens with termination,
     591so this reduces the amount of rules and patterns a programmer has to know.
     592
     593The marked try statements are the ones that would be removed from
    530594the stack for a termination exception, \ie those on the stack
    531595between the handler and the raise statement.
     
    593657
    594658\subsection{Comparison with Reraising}
    595 Without conditional catch, the only approach to match in more detail is to reraise
    596 the exception after it has been caught, if it could not be handled.
     659In languages without conditional catch, that is no ability to match an
     660exception based on something other than its type, it can be mimicked
     661by matching all exceptions of the right type, checking any additional
     662conditions inside the handler and re-raising the exception if it does not
     663match those.
     664
     665Here is a minimal example comparing both patterns, using @throw;@
     666(no argument) to start a re-raise.
    597667\begin{center}
    598 \begin{tabular}{l|l}
     668\begin{tabular}{l r}
    599669\begin{cfa}
    600670try {
    601         do_work_may_throw();
    602 } catch(excep_t * ex; can_handle(ex)) {
    603 
    604         handle(ex);
    605 
    606 
    607 
    608 }
     671    do_work_may_throw();
     672} catch(exception_t * exc ;
     673                can_handle(exc)) {
     674    handle(exc);
     675}
     676
     677
     678
    609679\end{cfa}
    610680&
    611681\begin{cfa}
    612682try {
    613         do_work_may_throw();
    614 } catch(excep_t * ex) {
    615         if (can_handle(ex)) {
    616                 handle(ex);
     683    do_work_may_throw();
     684} catch(exception_t * exc) {
     685    if (can_handle(exc)) {
     686        handle(exc);
     687    } else {
     688        throw;
     689    }
     690}
     691\end{cfa}
     692\end{tabular}
     693\end{center}
     694At first glance catch-and-reraise may appear to just be a quality of life
     695feature, but there are some significant differences between the two
     696stratagies.
     697
     698A simple difference that is more important for \CFA than many other languages
     699is that the raise site changes, with a re-raise but does not with a
     700conditional catch.
     701This is important in \CFA because control returns to the raise site to run
     702the per-site default handler. Because of this only a conditional catch can
     703allow the original raise to continue.
     704
     705The more complex issue comes from the difference in how conditional
     706catches and re-raises handle multiple handlers attached to a single try
     707statement. A conditional catch will continue checking later handlers while
     708a re-raise will skip them.
     709If the different handlers could handle some of the same exceptions,
     710translating a try statement that uses one to use the other can quickly
     711become non-trivial:
     712
     713\noindent
     714Original, with conditional catch:
     715\begin{cfa}
     716...
     717} catch (an_exception * e ; check_a(e)) {
     718        handle_a(e);
     719} catch (exception_t * e ; check_b(e)) {
     720        handle_b(e);
     721}
     722\end{cfa}
     723Translated, with re-raise:
     724\begin{cfa}
     725...
     726} catch (exception_t * e) {
     727        an_exception * an_e = (virtual an_exception *)e;
     728        if (an_e && check_a(an_e)) {
     729                handle_a(an_e);
     730        } else if (check_b(e)) {
     731                handle_b(e);
    617732        } else {
    618733                throw;
     
    620735}
    621736\end{cfa}
    622 \end{tabular}
    623 \end{center}
    624 Notice catch-and-reraise increases complexity by adding additional data and
    625 code to the exception process. Nevertheless, catch-and-reraise can simulate
    626 conditional catch straightforwardly, when exceptions are disjoint, \ie no
    627 inheritance.
    628 
    629 However, catch-and-reraise simulation becomes unusable for exception inheritance.
    630 \begin{flushleft}
    631 \begin{cfa}[xleftmargin=6pt]
    632 exception E1;
    633 exception E2(E1); // inheritance
    634 \end{cfa}
    635 \begin{tabular}{l|l}
    636 \begin{cfa}
    637 try {
    638         ... foo(); ... // raise E1/E2
    639         ... bar(); ... // raise E1/E2
    640 } catch( E2 e; e.rtn == foo ) {
    641         ...
    642 } catch( E1 e; e.rtn == foo ) {
    643         ...
    644 } catch( E1 e; e.rtn == bar ) {
    645         ...
    646 }
    647 
    648 \end{cfa}
    649 &
    650 \begin{cfa}
    651 try {
    652         ... foo(); ...
    653         ... bar(); ...
    654 } catch( E2 e ) {
    655         if ( e.rtn == foo ) { ...
    656         } else throw; // reraise
    657 } catch( E1 e ) {
    658         if (e.rtn == foo) { ...
    659         } else if (e.rtn == bar) { ...
    660         else throw; // reraise
    661 }
    662 \end{cfa}
    663 \end{tabular}
    664 \end{flushleft}
    665 The derived exception @E2@ must be ordered first in the catch list, otherwise
    666 the base exception @E1@ catches both exceptions. In the catch-and-reraise code
    667 (right), the @E2@ handler catches exceptions from both @foo@ and
    668 @bar@. However, the reraise misses the following catch clause. To fix this
    669 problem, an enclosing @try@ statement is need to catch @E2@ for @bar@ from the
    670 reraise, and its handler must duplicate the inner handler code for @bar@. To
    671 generalize, this fix for any amount of inheritance and complexity of try
    672 statement requires a technique called \emph{try-block
    673 splitting}~\cite{Krischer02}, which is not discussed in this thesis. It is
    674 sufficient to state that conditional catch is more expressive than
    675 catch-and-reraise in terms of complexity.
    676 
    677 \begin{comment}
    678 That is, they have the same behaviour in isolation.
    679 Two things can expose differences between these cases.
    680 
    681 One is the existence of multiple handlers on a single try statement.
    682 A reraise skips all later handlers for a try statement but a conditional
    683 catch does not.
    684 % Hence, if an earlier handler contains a reraise later handlers are
    685 % implicitly skipped, with a conditional catch they are not.
    686 Still, they are equivalently powerful,
    687 both can be used two mimic the behaviour of the other,
    688 as reraise can pack arbitrary code in the handler and conditional catches
    689 can put arbitrary code in the predicate.
    690 % I was struggling with a long explanation about some simple solutions,
    691 % like repeating a condition on later handlers, and the general solution of
    692 % merging everything together. I don't think it is useful though unless its
    693 % for a proof.
    694 % https://en.cppreference.com/w/cpp/language/throw
    695 
    696 The question then becomes ``Which is a better default?"
    697 We believe that not skipping possibly useful handlers is a better default.
    698 If a handler can handle an exception it should and if the handler can not
    699 handle the exception then it is probably safer to have that explicitly
    700 described in the handler itself instead of implicitly described by its
    701 ordering with other handlers.
    702 % Or you could just alter the semantics of the throw statement. The handler
    703 % index is in the exception so you could use it to know where to start
    704 % searching from in the current try statement.
    705 % No place for the `goto else;` metaphor.
    706 
    707 The other issue is all of the discussion above assumes that the only
    708 way to tell apart two raises is the exception being raised and the remaining
    709 search path.
    710 This is not true generally, the current state of the stack can matter in
    711 a number of cases, even only for a stack trace after an program abort.
    712 But \CFA has a much more significant need of the rest of the stack, the
    713 default handlers for both termination and resumption.
    714 
    715 % For resumption it turns out it is possible continue a raise after the
    716 % exception has been caught, as if it hadn't been caught in the first place.
    717 This becomes a problem combined with the stack unwinding used in termination
    718 exception handling.
    719 The stack is unwound before the handler is installed, and hence before any
    720 reraises can run. So if a reraise happens the previous stack is gone,
    721 the place on the stack where the default handler was supposed to run is gone,
    722 if the default handler was a local function it may have been unwound too.
    723 There is no reasonable way to restore that information, so the reraise has
    724 to be considered as a new raise.
    725 This is the strongest advantage conditional catches have over reraising,
    726 they happen before stack unwinding and avoid this problem.
    727 
    728 % The one possible disadvantage of conditional catch is that it runs user
    729 % code during the exception search. While this is a new place that user code
    730 % can be run destructors and finally clauses are already run during the stack
    731 % unwinding.
     737(There is a simpler solution if @handle_a@ never raises exceptions,
     738using nested try statements.)
     739
     740% } catch (an_exception * e ; check_a(e)) {
     741%     handle_a(e);
     742% } catch (exception_t * e ; !(virtual an_exception *)e && check_b(e)) {
     743%     handle_b(e);
     744% }
    732745%
    733 % https://www.cplusplus.com/reference/exception/current_exception/
    734 %   `exception_ptr current_exception() noexcept;`
    735 % https://www.python.org/dev/peps/pep-0343/
    736 \end{comment}
     746% } catch (an_exception * e)
     747%   if (check_a(e)) {
     748%     handle_a(e);
     749%   } else throw;
     750% } catch (exception_t * e)
     751%   if (check_b(e)) {
     752%     handle_b(e);
     753%   } else throw;
     754% }
     755In similar simple examples translating from re-raise to conditional catch
     756takes less code but it does not have a general trivial solution either.
     757
     758So, given that the two patterns do not trivially translate into each other,
     759it becomes a matter of which on should be encouraged and made the default.
     760From the premise that if a handler that could handle an exception then it
     761should, it follows that checking as many handlers as possible is preferred.
     762So conditional catch and checking later handlers is a good default.
    737763
    738764\section{Finally Clauses}
     
    750776The @FINALLY_BLOCK@ is executed when the try statement is removed from the
    751777stack, including when the @GUARDED_BLOCK@ finishes, any termination handler
    752 finishes, or during an unwind.
     778finishes or during an unwind.
    753779The only time the block is not executed is if the program is exited before
    754780the stack is unwound.
     
    770796they have their own strengths, similar to top-level function and lambda
    771797functions with closures.
    772 Destructors take more work for their creation, but if there is clean-up code
     798Destructors take more work to create, but if there is clean-up code
    773799that needs to be run every time a type is used, they are much easier
    774 to set-up.
     800to set-up for each use. % It's automatic.
    775801On the other hand finally clauses capture the local context, so is easy to
    776802use when the clean-up is not dependent on the type of a variable or requires
     
    788814raise, this exception is not used in matching only to pass information about
    789815the cause of the cancellation.
    790 Finaly, since a cancellation only unwinds and forwards, there is no default handler.
     816Finally, as no handler is provided, there is no default handler.
    791817
    792818After @cancel_stack@ is called the exception is copied into the EHM's memory
     
    799825After the main stack is unwound there is a program-level abort.
    800826
    801 The reasons for this semantics in a sequential program is that there is no more code to execute.
    802 This semantics also applies to concurrent programs, too, even if threads are running.
    803 That is, if any threads starts a cancellation, it implies all threads terminate.
    804 Keeping the same behaviour in sequential and concurrent programs is simple.
    805 Also, even in concurrent programs there may not currently be any other stacks
    806 and even if other stacks do exist, main has no way to know where they are.
     827The first reason for this behaviour is for sequential programs where there
     828is only one stack, and hence to stack to pass information to.
     829Second, even in concurrent programs, the main stack has no dependency
     830on another stack and no reliable way to find another living stack.
     831Finally, keeping the same behaviour in both sequential and concurrent
     832programs is simple and easy to understand.
    807833
    808834\paragraph{Thread Stack}
     
    834860
    835861With explicit join and a default handler that triggers a cancellation, it is
    836 possible to cascade an error across any number of threads, cleaning up each
     862possible to cascade an error across any number of threads,
     863alternating between the resumption (possibly termination) and cancellation,
     864cleaning up each
    837865in turn, until the error is handled or the main thread is reached.
    838866
     
    847875caller's context and passes it to the internal report.
    848876
    849 A coroutine only knows of two other coroutines, its starter and its last resumer.
     877A coroutine only knows of two other coroutines,
     878its starter and its last resumer.
    850879The starter has a much more distant connection, while the last resumer just
    851880(in terms of coroutine state) called resume on this coroutine, so the message
     
    853882
    854883With a default handler that triggers a cancellation, it is possible to
    855 cascade an error across any number of coroutines, cleaning up each in turn,
     884cascade an error across any number of coroutines,
     885alternating between the resumption (possibly termination) and cancellation,
     886cleaning up each in turn,
    856887until the error is handled or a thread stack is reached.
    857 
    858 \PAB{Part of this I do not understand. A cancellation cannot be caught. But you
    859 talk about handling a cancellation in the last sentence. Which is correct?}
  • doc/theses/andrew_beach_MMath/future.tex

    rdd1cc02 r5a40e4e  
    22\label{c:future}
    33
     4The following discussion covers both possible interesting research
     5that could follow from this work as long as simple implementation
     6improvements.
     7
    48\section{Language Improvements}
    5 \todo{Future/Language Improvements seems to have gotten mixed up. It is
    6 presented as ``waiting on language improvements" but really its more
    7 non-research based impovements.}
     9
    810\CFA is a developing programming language. As such, there are partially or
    9 unimplemented features of the language (including several broken components)
    10 that I had to workaround while building an exception handling system largely in
    11 the \CFA language (some C components).  The following are a few of these
    12 issues, and once implemented/fixed, how they would affect the exception system.
     11unimplemented features (including several broken components)
     12that I had to workaround while building the EHM largely in
     13the \CFA language (some C components). Below are a few of these issues
     14and how implementing/fixing them would affect the EHM.
     15In addition there are some simple improvements that had no interesting
     16research attached to them but would make using the language easier.
    1317\begin{itemize}
    14 \item
    15 The implementation of termination is not portable because it includes
    16 hand-crafted assembly statements.
    17 The existing compilers cannot translate that for other platforms and those
    18 sections must be ported by hand to
    19 support more hardware architectures, such as the ARM processor.
    2018\item
    2119Due to a type-system problem, the catch clause cannot bind the exception to a
     
    2422result in little or no change in the exception system but simplify usage.
    2523\item
     24The @copy@ function in the exception virtual table is an adapter to address
     25some limitations in the \CFA copy constructor. If the copy constructor is
     26improved it can be used directly without the adapter.
     27\item
    2628Termination handlers cannot use local control-flow transfers, \eg by @break@,
    2729@return@, \etc. The reason is that current code generation hoists a handler
    2830into a nested function for convenience (versus assemble-code generation at the
    29 @try@ statement). Hence, when the handler runs, its code is not in the lexical
    30 scope of the @try@ statement, where the local control-flow transfers are
    31 meaningful.
     31try statement). Hence, when the handler runs, it can still access local
     32variables in the lexical scope of the try statement. Still, it does mean
     33that seemingly local control flow is not in fact local and crosses a function
     34boundary.
     35Making the termination handlers code within the surrounding
     36function would remove this limitation.
     37% Try blocks are much more difficult to do practically (requires our own
     38% assembly) and resumption handlers have some theoretical complexity.
    3239\item
    3340There is no detection of colliding unwinds. It is possible for clean-up code
    3441run during an unwind to trigger another unwind that escapes the clean-up code
    3542itself; such as a termination exception caught further down the stack or a
    36 cancellation. There do exist ways to handle this but currently they are not
    37 even detected and the first unwind will simply be forgotten, often leaving
     43cancellation. There do exist ways to handle this case, but currently there is
     44no detection and the first unwind will simply be forgotten, often leaving
    3845it in a bad state.
    3946\item
    40 Also the exception system did not have a lot of time to be tried and tested.
    41 So just letting people use the exception system more will reveal new
    42 quality of life upgrades that can be made with time.
     47Finally, the exception system has not had a lot of programmer testing.
     48More time with encouraged usage will reveal new
     49quality of life upgrades that can be made.
    4350\end{itemize}
    4451
     
    4754project, but was thrust upon it to do exception inheritance; hence, only
    4855minimal work is done. A draft for a complete virtual system is available but
    49 it is not finalized. A future \CFA project is to complete that work and then
     56not finalized. A future \CFA project is to complete that work and then
    5057update the exception system that uses the current version.
    5158
     
    5360exception traits. The most important one is an assertion to check one virtual
    5461type is a child of another. This check precisely captures many of the
    55 correctness requirements.
     62current ad-hoc correctness requirements.
     63
     64Other features of the virtual system could also remove some of the
     65special cases around exception virtual tables, such as the generation
     66of the @msg@ function, could be removed.
    5667
    5768The full virtual system might also include other improvement like associated
    5869types to allow traits to refer to types not listed in their header. This
    5970feature allows exception traits to not refer to the virtual-table type
    60 explicitly, removing the need for the current interface macros.
     71explicitly, removing the need for the current interface macros,
     72such as @EHM_IS_EXCEPTION@.
    6173
    6274\section{Additional Raises}
     
    7486Non-local/concurrent raise requires more
    7587coordination between the concurrency system
    76 and the exception system. Many of the interesting design decisions centre
     88and the exception system. Many of the interesting design decisions center
    7789around masking, \ie controlling which exceptions may be thrown at a stack. It
    7890would likely require more of the virtual system and would also effect how
     
    93105Checked exceptions make exceptions part of a function's type by adding an
    94106exception signature. An exception signature must declare all checked
    95 exceptions that could propagate from the function (either because they were
    96 raised inside the function or came from a sub-function). This improves safety
     107exceptions that could propagate from the function, either because they were
     108raised inside the function or came from a sub-function. This improves safety
    97109by making sure every checked exception is either handled or consciously
    98110passed on.
    99111
    100112However checked exceptions were never seriously considered for this project
    101 because they have significant trade-offs in usablity and code reuse in
     113because they have significant trade-offs in usability and code reuse in
    102114exchange for the increased safety.
    103115These trade-offs are most problematic when trying to pass exceptions through
     
    129141not support a successful-exiting stack-search without doing an unwind.
    130142Workarounds are possible but awkward. Ideally an extension to libunwind could
    131 be made, but that would either require separate maintenance or gain enough
    132 support to have it folded into the standard.
     143be made, but that would either require separate maintenance or gaining enough
     144support to have it folded into the official library itself.
    133145
    134146Also new techniques to skip previously searched parts of the stack need to be
     
    158170to leave the handler.
    159171Currently, mimicking this behaviour in \CFA is possible by throwing a
    160 termination inside a resumption handler.
     172termination exception inside a resumption handler.
    161173
    162174% Maybe talk about the escape; and escape CONTROL_STMT; statements or how
  • doc/theses/andrew_beach_MMath/implement.tex

    rdd1cc02 r5a40e4e  
    1414\label{s:VirtualSystem}
    1515% Virtual table rules. Virtual tables, the pointer to them and the cast.
    16 While the \CFA virtual system currently has only one public feature, virtual
    17 cast (see the virtual cast feature \vpageref{p:VirtualCast}),
    18 substantial structure is required to support it,
     16While the \CFA virtual system currently has only one public features, virtual
     17cast and virtual tables,
     18% ??? refs (see the virtual cast feature \vpageref{p:VirtualCast}),
     19substantial structure is required to support them,
    1920and provide features for exception handling and the standard library.
    2021
    2122\subsection{Virtual Type}
    22 Virtual types only have one change to their structure: the addition of a
    23 pointer to the virtual table, which is called the \emph{virtual-table pointer}.
    24 Internally, the field is called \snake{virtual_table}.
    25 The field is fixed after construction. It is always the first field in the
     23A virtual type~(see \autoref{s:virtuals}) has a pointer to a virtual table,
     24called the \emph{virtual-table pointer},
     25which binds each instance of a virtual type to a virtual table.
     26Internally, the field is called \snake{virtual_table}
     27and is fixed after construction.
     28This pointer is also the table's id and how the system accesses the
     29virtual table and the virtual members there.
     30It is always the first field in the
    2631structure so that its location is always known.
    27 \todo{Talk about constructors for virtual types (after they are working).}
    28 
    29 The virtual table pointer binds an instance of a virtual type
    30 to a virtual table.
    31 The pointer is also the table's id and how the system accesses the
    32 virtual table and the virtual members there.
     32
     33% We have no special rules for these constructors.
     34Virtual table pointers are passed to the constructors of virtual types
     35as part of field-by-field construction.
    3336
    3437\subsection{Type Id}
    3538Every virtual type has a unique id.
    36 Type ids can be compared for equality,
    37 which checks if the types reperented are the same,
    38 or used to access the type's type information.
     39These are used in type equality, to check if the representation of two values
     40are the same, and to access the type's type information.
     41This uniqueness means across a program composed of multiple translation
     42units (TU), not uniqueness across all programs or even across multiple
     43processes on the same machine.
     44
     45Our approach for program uniqueness is using a static declaration for each
     46type id, where the run-time storage address of that variable is guaranteed to
     47be unique during program execution.
     48The type id storage can also be used for other purposes,
     49and is used for type information.
     50
     51The problem is that a type id may appear in multiple TUs that compose a
     52program (see \autoref{ss:VirtualTable}); so the initial solution would seem
     53to be make it external in each translation unit. Hovever, the type id must
     54have a declaration in (exactly) one of the TUs to create the storage.
     55No other declaration related to the virtual type has this property, so doing
     56this through standard C declarations would require the user to do it manually.
     57
     58Instead the linker is used to handle this problem.
     59% I did not base anything off of C++17; they are solving the same problem.
     60A new feature has been added to \CFA for this purpose, the special attribute
     61\snake{cfa_linkonce}, which uses the special section @.gnu.linkonce@.
     62When used as a prefix (\eg @.gnu.linkonce.example@) the linker does
     63not combine these sections, but instead discards all but one with the same
     64full name.
     65
     66So each type id must be given a unique section name with the linkonce
     67prefix. Luckily \CFA already has a way to get unique names, the name mangler.
     68For example, this could be written directly in \CFA:
     69\begin{cfa}
     70__attribute__((cfa_linkonce)) void f() {}
     71\end{cfa}
     72This is translated to:
     73\begin{cfa}
     74__attribute__((section(".gnu.linkonce._X1fFv___1"))) void _X1fFv___1() {}
     75\end{cfa}
     76This is done internally to access the name manglers.
     77This attribute is useful for other purposes, any other place a unique
     78instance required, and should eventually be made part of a public and
     79stable feature in \CFA.
     80
     81\subsection{Type Information}
     82
     83There is data stored at the type id's declaration, the type information.
    3984The type information currently is only the parent's type id or, if the
    4085type has no parent, the null pointer.
    41 
    42 The id's are implemented as pointers to the type's type information instance.
    43 Dereferencing the pointer gets the type information.
    4486The ancestors of a virtual type are found by traversing type ids through
    4587the type information.
    46 The information pushes the issue of creating a unique value (for
    47 the type id) to the problem of creating a unique instance (for type
    48 information), which the linker can solve.
    49 
    50 The advanced linker support is used here to avoid having to create
    51 a new declaration to attach this data to.
    52 With C/\CFA's header/implementation file divide for something to appear
    53 exactly once it must come from a declaration that appears in exactly one
    54 implementation file; the declarations in header files may exist only once
    55 they can be included in many different translation units.
    56 Therefore, structure's declaration will not work.
    57 Neither will attaching the type information to the virtual table -- although
    58 a vtable declarations are in implemention files they are not unique, see
    59 \autoref{ss:VirtualTable}.
    60 Instead the same type information is generated multiple times and then
    61 the new attribute \snake{cfa_linkone} is used to removed duplicates.
     88An example using helper macros looks like:
     89\begin{cfa}
     90struct INFO_TYPE(TYPE) {
     91        INFO_TYPE(PARENT) const * parent;
     92};
     93
     94__attribute__((cfa_linkonce))
     95INFO_TYPE(TYPE) const INFO_NAME(TYPE) = {
     96        &INFO_NAME(PARENT),
     97};
     98\end{cfa}
    6299
    63100Type information is constructed as follows:
    64 \begin{enumerate}
     101\begin{enumerate}[nosep]
    65102\item
    66 Use the type's name to generate a name for the type information structure.
    67 This is saved so it may be reused.
     103Use the type's name to generate a name for the type information structure,
     104which is saved so it can be reused.
    68105\item
    69106Generate a new structure definition to store the type
    70107information. The layout is the same in each case, just the parent's type id,
    71108but the types used change from instance to instance.
    72 The generated name is used for both this structure and, if relivant, the
     109The generated name is used for both this structure and, if relevant, the
    73110parent pointer.
    74111If the virtual type is polymorphic then the type information structure is
    75112polymorphic as well, with the same polymorphic arguments.
    76113\item
    77 A seperate name for instances is generated from the type's name.
     114A separate name for instances is generated from the type's name.
    78115\item
    79 The definition is generated and initialised.
     116The definition is generated and initialized.
    80117The parent id is set to the null pointer or to the address of the parent's
    81118type information instance. Name resolution handles the rest.
    82119\item
    83120\CFA's name mangler does its regular name mangling encoding the type of
    84 the declaration into the instance name. This gives a completely unique name
     121the declaration into the instance name.
     122This process gives a completely unique name
    85123including different instances of the same polymorphic type.
    86124\end{enumerate}
    87 \todo{The list is making me realise, some of this isn't ordered.}
    88125
    89126Writing that code manually, with helper macros for the early name mangling,
     
    100137\end{cfa}
    101138
     139\begin{comment}
    102140\subsubsection{\lstinline{cfa\_linkonce} Attribute}
    103 % I just realised: This is an extension of the inline keyword.
     141% I just realized: This is an extension of the inline keyword.
    104142% An extension of C's at least, it is very similar to C++'s.
    105143Another feature added to \CFA is a new attribute: \texttt{cfa\_linkonce}.
     
    126164everything that comes after the special prefix, then only one is used
    127165and the other is discarded.
     166\end{comment}
    128167
    129168\subsection{Virtual Table}
     
    136175below.
    137176
    138 The layout always comes in three parts.
    139 \todo{Add labels to the virtual table layout figure.}
     177The layout always comes in three parts (see \autoref{f:VirtualTableLayout}).
    140178The first section is just the type id at the head of the table. It is always
    141179there to ensure that it can be found even when the accessing code does not
     
    143181The second section are all the virtual members of the parent, in the same
    144182order as they appear in the parent's virtual table. Note that the type may
    145 change slightly as references to the ``this" will change. This is limited to
     183change slightly as references to the ``this" change. This is limited to
    146184inside pointers/references and via function pointers so that the size (and
    147185hence the offsets) are the same.
     
    150188
    151189\begin{figure}
     190\begin{center}
    152191\input{vtable-layout}
     192\end{center}
    153193\caption{Virtual Table Layout}
    154194\label{f:VirtualTableLayout}
    155 \todo*{Improve the Virtual Table Layout diagram.}
    156195\end{figure}
    157196
     
    176215type's alignment, is set using an @alignof@ expression.
    177216
    178 \subsubsection{Concurrency Integration}
     217Most of these tools are already inside the compiler. Using simple
     218code transformations early on in compilation, allows most of that work to be
     219handed off to the existing tools. \autoref{f:VirtualTableTransformation}
     220shows an example transformation, this example shows an exception virtual table.
     221It also shows the transformation on the full declaration.
     222For a forward declaration, the @extern@ keyword is preserved and the
     223initializer is not added.
     224
     225\begin{figure}[htb]
     226\begin{cfa}
     227vtable(example_type) example_name;
     228\end{cfa}
     229\transformline
     230% Check mangling.
     231\begin{cfa}
     232const struct example_type_vtable example_name = {
     233        .__cfavir_typeid : &__cfatid_example_type,
     234        .size : sizeof(example_type),
     235        .copy : copy,
     236        .^?{} : ^?{},
     237        .msg : msg,
     238};
     239\end{cfa}
     240\caption{Virtual Table Transformation}
     241\label{f:VirtualTableTransformation}
     242\end{figure}
     243
     244\subsection{Concurrency Integration}
    179245Coroutines and threads need instances of @CoroutineCancelled@ and
    180246@ThreadCancelled@ respectively to use all of their functionality. When a new
     
    183249at the definition of the main function.
    184250
    185 This is showned through code re-writing in
    186 \autoref{f:ConcurrencyTypeTransformation} and
    187 \autoref{f:ConcurrencyMainTransformation}.
    188 In both cases the original declaration is not modified,
     251These transformations are shown through code re-writing in
     252\autoref{f:CoroutineTypeTransformation} and
     253\autoref{f:CoroutineMainTransformation}.
     254Threads use the same pattern, with some names and types changed.
     255In both cases, the original declaration is not modified,
    189256only new ones are added.
    190257
    191 \begin{figure}
     258\begin{figure}[htb]
    192259\begin{cfa}
    193260coroutine Example {
     
    207274extern CoroutineCancelled_vtable & _default_vtable;
    208275\end{cfa}
    209 \caption{Concurrency Type Transformation}
    210 \label{f:ConcurrencyTypeTransformation}
     276\caption{Coroutine Type Transformation}
     277\label{f:CoroutineTypeTransformation}
    211278\end{figure}
    212279
    213 \begin{figure}
     280\begin{figure}[htb]
    214281\begin{cfa}
    215282void main(Example & this) {
     
    229296        &_default_vtable_object_declaration;
    230297\end{cfa}
    231 \caption{Concurrency Main Transformation}
    232 \label{f:ConcurrencyMainTransformation}
     298\caption{Coroutine Main Transformation}
     299\label{f:CoroutineMainTransformation}
    233300\end{figure}
    234301
     
    242309\begin{cfa}
    243310void * __cfa__virtual_cast(
    244         struct __cfavir_type_td parent,
    245         struct __cfavir_type_id const * child );
    246 \end{cfa}
    247 The type id of target type of the virtual cast is passed in as @parent@ and
     311        struct __cfavir_type_id * parent,
     312        struct __cfavir_type_id * const * child );
     313\end{cfa}
     314The type id for the target type of the virtual cast is passed in as
     315@parent@ and
    248316the cast target is passed in as @child@.
    249 
    250 For generated C code wraps both arguments and the result with type casts.
     317The generated C code wraps both arguments and the result with type casts.
    251318There is also an internal check inside the compiler to make sure that the
    252319target type is a virtual type.
     
    260327
    261328\section{Exceptions}
    262 % Anything about exception construction.
     329% The implementation of exception types.
     330
     331Creating exceptions can roughly divided into two parts,
     332the exceptions themselves and the virtual system interactions.
     333
     334Creating an exception type is just a matter of prepending the field 
     335with the virtual table pointer to the list of the fields
     336(see \autoref{f:ExceptionTypeTransformation}).
     337
     338\begin{figure}[htb]
     339\begin{cfa}
     340exception new_exception {
     341        // EXISTING FIELDS
     342};
     343\end{cfa}
     344\transformline
     345\begin{cfa}
     346struct new_exception {
     347        struct new_exception_vtable const * virtual_table;
     348        // EXISTING FIELDS
     349};
     350\end{cfa}
     351\caption{Exception Type Transformation}
     352\label{f:ExceptionTypeTransformation}
     353\end{figure}
     354
     355The integration between exceptions and the virtual system is a bit more
     356complex simply because of the nature of the virtual system prototype.
     357The primary issue is that the virtual system has no way to detect when it
     358should generate any of its internal types and data. This is handled by
     359the exception code, which tells the virtual system when to generate
     360its components.
     361
     362All types associated with a virtual type,
     363the types of the virtual table and the type id,
     364are generated when the virtual type (the exception) is first found.
     365The type id (the instance) is generated with the exception, if it is
     366a monomorphic type.
     367However, if the exception is polymorphic, then a different type id has to
     368be generated for every instance. In this case, generation is delayed
     369until a virtual table is created.
     370% There are actually some problems with this, which is why it is not used
     371% for monomorphic types.
     372When a virtual table is created and initialized, two functions are created
     373to fill in the list of virtual members.
     374The first is a copy function that adapts the exception's copy constructor
     375to work with pointers, avoiding some issues with the current copy constructor
     376interface.
     377Second is the msg function that returns a C-string with the type's name,
     378including any polymorphic parameters.
    263379
    264380\section{Unwinding}
     
    274390stack. On function entry and return, unwinding is handled directly by the
    275391call/return code embedded in the function.
    276 In many cases, the position of the instruction pointer (relative to parameter
    277 and local declarations) is enough to know the current size of the stack
    278 frame.
    279 
     392
     393% Discussing normal stack unwinding:
    280394Usually, the stack-frame size is known statically based on parameter and
    281 local variable declarations. Even with dynamic stack-size, the information
     395local variable declarations. Even for a dynamic stack-size, the information
    282396to determine how much of the stack has to be removed is still contained
    283397within the function.
     
    285399bumping the hardware stack-pointer up or down as needed.
    286400Constructing/destructing values within a stack frame has
    287 a similar complexity but can add additional work and take longer.
    288 
     401a similar complexity but larger constants.
     402
     403% Discussing multiple frame stack unwinding:
    289404Unwinding across multiple stack frames is more complex because that
    290405information is no longer contained within the current function.
    291 With seperate compilation a function has no way of knowing what its callers
    292 are so it can't know how large those frames are.
    293 Without altering the main code path it is also hard to pass that work off
    294 to the caller.
     406With separate compilation,
     407a function does not know its callers nor their frame layout.
     408Even using the return address, that information is encoded in terms of
     409actions in code, intermixed with the actions required finish the function.
     410Without changing the main code path it is impossible to select one of those
     411two groups of actions at the return site.
    295412
    296413The traditional unwinding mechanism for C is implemented by saving a snap-shot
     
    302419This approach is fragile and requires extra work in the surrounding code.
    303420
    304 With respect to the extra work in the surounding code,
     421With respect to the extra work in the surrounding code,
    305422many languages define clean-up actions that must be taken when certain
    306423sections of the stack are removed. Such as when the storage for a variable
    307 is removed from the stack or when a try statement with a finally clause is
     424is removed from the stack, possibly requiring a destructor call,
     425or when a try statement with a finally clause is
    308426(conceptually) popped from the stack.
    309 None of these should be handled by the user --- that would contradict the
     427None of these cases should be handled by the user --- that would contradict the
    310428intention of these features --- so they need to be handled automatically.
    311429
     
    348466In plain C (which \CFA currently compiles down to) this
    349467flag only handles the cleanup attribute:
     468%\label{code:cleanup}
    350469\begin{cfa}
    351470void clean_up( int * var ) { ... }
     
    355474in this case @clean_up@, run when the variable goes out of scope.
    356475This feature is enough to mimic destructors,
    357 but not try statements which can effect
     476but not try statements that affect
    358477the unwinding.
    359478
    360479To get full unwinding support, all of these features must be handled directly
    361 in assembly and assembler directives; partiularly the cfi directives
     480in assembly and assembler directives; particularly the cfi directives
    362481\snake{.cfi_lsda} and \snake{.cfi_personality}.
    363482
     
    399518@_UA_FORCE_UNWIND@ specifies a forced unwind call. Forced unwind only performs
    400519the cleanup phase and uses a different means to decide when to stop
    401 (see \vref{s:ForcedUnwind}).
     520(see \autoref{s:ForcedUnwind}).
    402521\end{enumerate}
    403522
    404523The @exception_class@ argument is a copy of the
    405524\code{C}{exception}'s @exception_class@ field,
    406 which is a number that identifies the exception handling mechanism
     525which is a number that identifies the EHM
    407526that created the exception.
    408527
     
    494613needs its own exception context.
    495614
    496 The exception context should be retrieved by calling the function
     615The current exception context should be retrieved by calling the function
    497616\snake{this_exception_context}.
    498617For sequential execution, this function is defined as
     
    519638The first step of a termination raise is to copy the exception into memory
    520639managed by the exception system. Currently, the system uses @malloc@, rather
    521 than reserved memory or the stack top. The exception handling mechanism manages
     640than reserved memory or the stack top. The EHM manages
    522641memory for the exception as well as memory for libunwind and the system's own
    523642per-exception storage.
     
    554673\newsavebox{\stackBox}
    555674\begin{lrbox}{\codeBox}
    556 \begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
     675\begin{cfa}
    557676unsigned num_exceptions = 0;
    558677void throws() {
     
    573692    throws();
    574693}
    575 \end{lstlisting}
     694\end{cfa}
    576695\end{lrbox}
    577696
    578697\begin{lrbox}{\stackBox}
    579698\begin{lstlisting}
    580 | try-finally
    581 | try-catch (Example)
     699| finally block (Example)
     700| try block
    582701throws()
    583 | try-finally
    584 | try-catch (Example)
     702| finally block (Example)
     703| try block
    585704throws()
    586 | try-finally
    587 | try-catch (Example)
     705| finally block (Example)
     706| try block
    588707throws()
    589708main()
     
    598717\label{f:MultipleExceptions}
    599718\end{figure}
    600 \todo*{Work on multiple exceptions code sample.}
    601719
    602720All exceptions are stored in nodes, which are then linked together in lists
     
    618736\subsection{Try Statements and Catch Clauses}
    619737The try statement with termination handlers is complex because it must
    620 compensate for the C code-generation versus
     738compensate for the C code-generation versus proper
    621739assembly-code generated from \CFA. Libunwind
    622740requires an LSDA and personality function for control to unwind across a
    623741function. The LSDA in particular is hard to mimic in generated C code.
    624742
    625 The workaround is a function called @__cfaehm_try_terminate@ in the standard
    626 library. The contents of a try block and the termination handlers are converted
    627 into functions. These are then passed to the try terminate function and it
    628 calls them.
     743The workaround is a function called \snake{__cfaehm_try_terminate} in the
     744standard \CFA library. The contents of a try block and the termination
     745handlers are converted into nested functions. These are then passed to the
     746try terminate function and it calls them, appropriately.
    629747Because this function is known and fixed (and not an arbitrary function that
    630 happens to contain a try statement), the LSDA can be generated ahead
     748happens to contain a try statement), its LSDA can be generated ahead
    631749of time.
    632750
    633 Both the LSDA and the personality function are set ahead of time using
     751Both the LSDA and the personality function for \snake{__cfaehm_try_terminate}
     752are set ahead of time using
    634753embedded assembly. This assembly code is handcrafted using C @asm@ statements
    635754and contains
    636 enough information for a single try statement the function repersents.
     755enough information for the single try statement the function represents.
    637756
    638757The three functions passed to try terminate are:
     
    646765decides if a catch clause matches the termination exception. It is constructed
    647766from the conditional part of each handler and runs each check, top to bottom,
    648 in turn, first checking to see if the exception type matches and then if the
    649 condition is true. It takes a pointer to the exception and returns 0 if the
     767in turn, to see if the exception matches this handler.
     768The match is performed in two steps, first a virtual cast is used to check
     769if the raised exception is an instance of the declared exception type or
     770one of its descendant types, and then the condition is evaluated, if
     771present.
     772The match function takes a pointer to the exception and returns 0 if the
    650773exception is not handled here. Otherwise the return value is the id of the
    651774handler that matches the exception.
     
    660783All three functions are created with GCC nested functions. GCC nested functions
    661784can be used to create closures,
    662 in other words functions that can refer to the state of other
    663 functions on the stack. This approach allows the functions to refer to all the
     785in other words,
     786functions that can refer to variables in their lexical scope even
     787those variables are part of a different function.
     788This approach allows the functions to refer to all the
    664789variables in scope for the function containing the @try@ statement. These
    665790nested functions and all other functions besides @__cfaehm_try_terminate@ in
     
    669794
    670795\autoref{f:TerminationTransformation} shows the pattern used to transform
    671 a \CFA try statement with catch clauses into the approprate C functions.
    672 \todo{Explain the Termination Transformation figure.}
     796a \CFA try statement with catch clauses into the appropriate C functions.
    673797
    674798\begin{figure}
     
    728852\caption{Termination Transformation}
    729853\label{f:TerminationTransformation}
    730 \todo*{Improve (compress?) Termination Transformations.}
    731854\end{figure}
    732855
     
    738861Instead of storing the data in a special area using assembly,
    739862there is just a linked list of possible handlers for each stack,
    740 with each node on the list reperenting a try statement on the stack.
     863with each node on the list representing a try statement on the stack.
    741864
    742865The head of the list is stored in the exception context.
     
    744867to the head of the list.
    745868Instead of traversing the stack, resumption handling traverses the list.
    746 At each node, the EHM checks to see if the try statement the node repersents
     869At each node, the EHM checks to see if the try statement the node represents
    747870can handle the exception. If it can, then the exception is handled and
    748871the operation finishes, otherwise the search continues to the next node.
    749872If the search reaches the end of the list without finding a try statement
    750 that can handle the exception, the default handler is executed and the
    751 operation finishes.
     873with a handler clause
     874that can handle the exception, the default handler is executed.
     875If the default handler returns, control continues after the raise statement.
    752876
    753877Each node has a handler function that does most of the work.
    754878The handler function is passed the raised exception and returns true
    755879if the exception is handled and false otherwise.
    756 
    757880The handler function checks each of its internal handlers in order,
    758881top-to-bottom, until it funds a match. If a match is found that handler is
     
    760883If no match is found the function returns false.
    761884The match is performed in two steps, first a virtual cast is used to see
    762 if the thrown exception is an instance of the declared exception or one of
    763 its descendant type, then check to see if passes the custom predicate if one
    764 is defined. This ordering gives the type guarantee used in the predicate.
     885if the raised exception is an instance of the declared exception type or one
     886of its descendant types, if so then it is passed to the custom predicate
     887if one is defined.
     888% You need to make sure the type is correct before running the predicate
     889% because the predicate can depend on that.
    765890
    766891\autoref{f:ResumptionTransformation} shows the pattern used to transform
    767 a \CFA try statement with catch clauses into the approprate C functions.
    768 \todo{Explain the Resumption Transformation figure.}
     892a \CFA try statement with catchResume clauses into the appropriate
     893C functions.
    769894
    770895\begin{figure}
     
    807932\caption{Resumption Transformation}
    808933\label{f:ResumptionTransformation}
    809 \todo*{Improve (compress?) Resumption Transformations.}
    810934\end{figure}
    811935
     
    814938(see \vpageref{s:ResumptionMarking}), which ignores parts of
    815939the stack
    816 already examined, is accomplished by updating the front of the list as the
    817 search continues. Before the handler at a node is called, the head of the list
     940already examined, and is accomplished by updating the front of the list as
     941the search continues.
     942Before the handler is called at a matching node, the head of the list
    818943is updated to the next node of the current node. After the search is complete,
    819944successful or not, the head of the list is reset.
     
    822947been checked are not on the list while a handler is run. If a resumption is
    823948thrown during the handling of another resumption, the active handlers and all
    824 the other handler checked up to this point are not checked again.
     949the other handlers checked up to this point are not checked again.
    825950% No paragraph?
    826951This structure also supports new handlers added while the resumption is being
     
    830955
    831956\begin{figure}
     957\centering
    832958\input{resumption-marking}
    833959\caption{Resumption Marking}
    834960\label{f:ResumptionMarking}
    835 \todo*{Label Resumption Marking to aid clarity.}
    836961\end{figure}
    837962
     
    851976\section{Finally}
    852977% Uses destructors and GCC nested functions.
    853 A finally clause is placed into a GCC nested-function with a unique name,
    854 and no arguments or return values.
    855 This nested function is then set as the cleanup
    856 function of an empty object that is declared at the beginning of a block placed
    857 around the context of the associated @try@ statement.
    858 
    859 The rest is handled by GCC. The try block and all handlers are inside this
    860 block. At completion, control exits the block and the empty object is cleaned
     978
     979%\autoref{code:cleanup}
     980A finally clause is handled by converting it into a once-off destructor.
     981The code inside the clause is placed into GCC nested-function
     982with a unique name, and no arguments or return values.
     983This nested function is
     984then set as the cleanup function of an empty object that is declared at the
     985beginning of a block placed around the context of the associated try
     986statement (see \autoref{f:FinallyTransformation}).
     987
     988\begin{figure}
     989\begin{cfa}
     990try {
     991        // TRY BLOCK
     992} finally {
     993        // FINALLY BLOCK
     994}
     995\end{cfa}
     996
     997\transformline
     998
     999\begin{cfa}
     1000{
     1001        void finally(void *__hook){
     1002                // FINALLY BLOCK
     1003        }
     1004        __attribute__ ((cleanup(finally)))
     1005        struct __cfaehm_cleanup_hook __finally_hook;
     1006        {
     1007                // TRY BLOCK
     1008        }
     1009}
     1010\end{cfa}
     1011
     1012\caption{Finally Transformation}
     1013\label{f:FinallyTransformation}
     1014\end{figure}
     1015
     1016The rest is handled by GCC.
     1017The TRY BLOCK
     1018contains the try block itself as well as all code generated for handlers.
     1019Once that code has completed,
     1020control exits the block and the empty object is cleaned
    8611021up, which runs the function that contains the finally code.
    8621022
     
    8871047passed to the forced-unwind function. The general pattern of all three stop
    8881048functions is the same: continue unwinding until the end of stack and
    889 then preform the appropriate transfer.
     1049then perform the appropriate transfer.
    8901050
    8911051For main stack cancellation, the transfer is just a program abort.
  • doc/theses/andrew_beach_MMath/intro.tex

    rdd1cc02 r5a40e4e  
    1111
    1212% Now take a step back and explain what exceptions are generally.
     13Exception handling provides dynamic inter-function control flow.
    1314A language's EHM is a combination of language syntax and run-time
    14 components that are used to construct, raise, and handle exceptions,
    15 including all control flow.
    16 Exceptions are an active mechanism for replacing passive error/return codes and return unions (Go and Rust).
    17 Exception handling provides dynamic inter-function control flow.
     15components that construct, raise, propagate and handle exceptions,
     16to provide all of that control flow.
    1817There are two forms of exception handling covered in this thesis:
    1918termination, which acts as a multi-level return,
    2019and resumption, which is a dynamic function call.
    21 % PAB: Maybe this sentence was suppose to be deleted?
    22 Termination handling is much more common,
    23 to the extent that it is often seen as the only form of handling.
    24 % PAB: I like this sentence better than the next sentence.
    25 % This separation is uncommon because termination exception handling is so
    26 % much more common that it is often assumed.
    27 % WHY: Mention other forms of continuation and \cite{CommonLisp} here?
    28 
    29 Exception handling relies on the concept of nested functions to create handlers that deal with exceptions.
    30 \begin{center}
    31 \begin{tabular}[t]{ll}
    32 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt,language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
    33 void f( void (*hp)() ) {
    34         hp();
    35 }
    36 void g( void (*hp)() ) {
    37         f( hp );
    38 }
    39 void h( int @i@, void (*hp)() ) {
    40         void @handler@() { // nested
    41                 printf( "%d\n", @i@ );
    42         }
    43         if ( i == 1 ) hp = handler;
    44         if ( i > 0 ) h( i - 1, hp );
    45         else g( hp );
    46 }
    47 h( 2, 0 );
    48 \end{lstlisting}
    49 &
    50 \raisebox{-0.5\totalheight}{\input{handler}}
    51 \end{tabular}
    52 \end{center}
    53 The nested function @handler@ in the second stack frame is explicitly passed to function @f@.
    54 When this handler is called in @f@, it uses the parameter @i@ in the second stack frame, which is accessible by an implicit lexical-link pointer.
    55 Setting @hp@ in @h@ at different points in the recursion, results in invoking a different handler.
    56 Exception handling extends this idea by eliminating explicit handler passing, and instead, performing a stack search for a handler that matches some criteria (conditional dynamic call), and calls the handler at the top of the stack.
    57 It is the runtime search $O(N)$ that differentiates an EHM call (raise) from normal dynamic call $O(1)$ via a function or virtual-member pointer.
    58 
    59 Termination exception handling searches the stack for a handler, unwinds the stack to the frame containing the matching handler, and calling the handler at the top of the stack.
     20% About other works:
     21Often, when this separation is not made, termination exceptions are assumed
     22as they are more common and may be the only form of handling provided in
     23a language.
     24
     25All types of exception handling link a raise with a handler.
     26Both operations are usually language primitives, although raises can be
     27treated as a primitive function that takes an exception argument.
     28Handlers are more complex as they are added to and removed from the stack
     29during execution, must specify what they can handle and give the code to
     30handle the exception.
     31
     32Exceptions work with different execution models but for the descriptions
     33that follow a simple call stack, with functions added and removed in a
     34first-in-last-out order, is assumed.
     35
     36Termination exception handling searches the stack for the handler, then
     37unwinds the stack to where the handler was found before calling it.
     38The handler is run inside the function that defined it and when it finishes
     39it returns control to that function.
    6040\begin{center}
    6141\input{termination}
    6242\end{center}
    63 Note, since the handler can reference variables in @h@, @h@ must remain on the stack for the handler call.
    64 After the handler returns, control continues after the lexical location of the handler in @h@ (static return)~\cite[p.~108]{Tennent77}.
    65 Unwinding allows recover to any previous
    66 function on the stack, skipping any functions between it and the
    67 function containing the matching handler.
    68 
    69 Resumption exception handling searches the stack for a handler, does \emph{not} unwind the stack to the frame containing the matching handler, and calls the handler at the top of the stack.
     43
     44Resumption exception handling searches the stack for a handler and then calls
     45it without removing any other stack frames.
     46The handler is run on top of the existing stack, often as a new function or
     47closure capturing the context in which the handler was defined.
     48After the handler has finished running it returns control to the function
     49that preformed the raise, usually starting after the raise.
    7050\begin{center}
    7151\input{resumption}
    7252\end{center}
    73 After the handler returns, control continues after the resume in @f@ (dynamic return).
    74 Not unwinding allows fix up of the problem in @f@ by any previous function on the stack, without disrupting the current set of stack frames.
    7553
    7654Although a powerful feature, exception handling tends to be complex to set up
    7755and expensive to use
    7856so it is often limited to unusual or ``exceptional" cases.
    79 The classic example is error handling, where exceptions are used to
    80 remove error handling logic from the main execution path, while paying
     57The classic example is error handling, exceptions can be used to
     58remove error handling logic from the main execution path, and pay
    8159most of the cost only when the error actually occurs.
    8260
     
    8866some of the underlying tools used to implement and express exception handling
    8967in other languages are absent in \CFA.
    90 Still the resulting basic syntax resembles that of other languages:
    91 \begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
    92 @try@ {
     68Still the resulting syntax resembles that of other languages:
     69\begin{cfa}
     70try {
    9371        ...
    9472        T * object = malloc(request_size);
    9573        if (!object) {
    96                 @throw@ OutOfMemory{fixed_allocation, request_size};
     74                throw OutOfMemory{fixed_allocation, request_size};
    9775        }
    9876        ...
    99 } @catch@ (OutOfMemory * error) {
     77} catch (OutOfMemory * error) {
    10078        ...
    10179}
    102 \end{lstlisting}
     80\end{cfa}
    10381% A note that yes, that was a very fast overview.
    10482The design and implementation of all of \CFA's EHM's features are
     
    10785
    10886% The current state of the project and what it contributes.
    109 The majority of the \CFA EHM is implemented in \CFA, except for a small amount of assembler code.
    110 In addition,
    111 a suite of tests and performance benchmarks were created as part of this project.
    112 The \CFA implementation techniques are generally applicable in other programming
     87All of these features have been implemented in \CFA,
     88covering both changes to the compiler and the run-time.
     89In addition, a suite of test cases and performance benchmarks were created
     90along side the implementation.
     91The implementation techniques are generally applicable in other programming
    11392languages and much of the design is as well.
    114 Some parts of the EHM use features unique to \CFA, and hence,
    115 are harder to replicate in other programming languages.
    116 % Talk about other programming languages.
    117 Three well known programming languages with EHMs, %/exception handling
    118 C++, Java and Python are examined in the performance work. However, these languages focus on termination
    119 exceptions, so there is no comparison with resumption.
     93Some parts of the EHM use other features unique to \CFA and would be
     94harder to replicate in other programming languages.
    12095
    12196The contributions of this work are:
    12297\begin{enumerate}
    12398\item Designing \CFA's exception handling mechanism, adapting designs from
    124 other programming languages, and creating new features.
    125 \item Implementing stack unwinding for the \CFA EHM, including updating
    126 the \CFA compiler and run-time environment to generate and execute the EHM code.
    127 \item Designing and implementing a prototype virtual system.
     99other programming languages and creating new features.
     100\item Implementing stack unwinding and the \CFA EHM, including updating
     101the \CFA compiler and the run-time environment.
     102\item Designed and implemented a prototype virtual system.
    128103% I think the virtual system and per-call site default handlers are the only
    129104% "new" features, everything else is a matter of implementation.
    130 \item Creating tests and performance benchmarks to compare with EHM's in other languages.
     105\item Creating tests to check the behaviour of the EHM.
     106\item Creating benchmarks to check the performances of the EHM,
     107as compared to other languages.
    131108\end{enumerate}
    132109
    133 %\todo{I can't figure out a good lead-in to the roadmap.}
    134 The thesis is organization as follows.
    135 The next section and parts of \autoref{c:existing} cover existing EHMs.
    136 New \CFA EHM features are introduced in \autoref{c:features},
     110The rest of this thesis is organized as follows.
     111The current state of exceptions is covered in \autoref{s:background}.
     112The existing state of \CFA is also covered in \autoref{c:existing}.
     113New EHM features are introduced in \autoref{c:features},
    137114covering their usage and design.
    138115That is followed by the implementation of these features in
    139116\autoref{c:implement}.
    140 Performance results are presented in \autoref{c:performance}.
    141 Summing up and possibilities for extending this project are discussed in \autoref{c:future}.
     117Performance results are examined in \autoref{c:performance}.
     118Possibilities to extend this project are discussed in \autoref{c:future}.
     119Finally, the project is summarized in \autoref{c:conclusion}.
    142120
    143121\section{Background}
    144122\label{s:background}
    145123
    146 Exception handling is a well examined area in programming languages,
    147 with papers on the subject dating back the 70s~\cite{Goodenough75}.
     124Exception handling has been examined before in programming languages,
     125with papers on the subject dating back 70s.\cite{Goodenough75}
    148126Early exceptions were often treated as signals, which carried no information
    149 except their identity. Ada~\cite{Ada} still uses this system.
     127except their identity.
     128Ada originally used this system\cite{Ada}, but now allows for a string
     129message as a payload\cite{Ada12}.
    150130
    151131The modern flag-ship for termination exceptions is \Cpp,
    152132which added them in its first major wave of non-object-orientated features
    153 in 1990.
    154 % https://en.cppreference.com/w/cpp/language/history
    155 While many EHMs have special exception types,
    156 \Cpp has the ability to use any type as an exception.
    157 However, this generality is not particularly useful, and has been pushed aside for classes, with a convention of inheriting from
     133in 1990.\cite{CppHistory}
     134Many EHMs have special exception types,
     135however \Cpp has the ability to use any type as an exception.
     136These were found to be not very useful and have been pushed aside for classes
     137inheriting from
    158138\code{C++}{std::exception}.
    159 While \Cpp has a special catch-all syntax @catch(...)@, there is no way to discriminate its exception type, so nothing can
    160 be done with the caught value because nothing is known about it.
    161 Instead the base exception-type \code{C++}{std::exception} is defined with common functionality (such as
    162 the ability to print a message when the exception is raised but not caught) and all
     139Although there is a special catch-all syntax (@catch(...)@) there are no
     140operations that can be performed on the caught value, not even type inspection.
     141Instead the base exception-type \code{C++}{std::exception} defines common
     142functionality (such as
     143the ability to describe the reason the exception was raised) and all
    163144exceptions have this functionality.
    164 Having a root exception-type seems to be the standard now, as the guaranteed functionality is worth
    165 any lost in flexibility from limiting exceptions types to classes.
    166 
    167 Java~\cite{Java} was the next popular language to use exceptions.
    168 Its exception system largely reflects that of \Cpp, except it requires
    169 exceptions to be a subtype of \code{Java}{java.lang.Throwable}
     145That trade-off, restricting usable types to gain guaranteed functionality,
     146is almost universal now, as without some common functionality it is almost
     147impossible to actually handle any errors.
     148
     149Java was the next popular language to use exceptions.\cite{Java8}
     150Its exception system largely reflects that of \Cpp, except that requires
     151you throw a child type of \code{Java}{java.lang.Throwable}
    170152and it uses checked exceptions.
    171 Checked exceptions are part of a function's interface defining all exceptions it or its called functions raise.
    172 Using this information, it is possible to statically verify if a handler exists for all raised exception, \ie no uncaught exceptions.
    173 Making exception information explicit, improves clarity and
    174 safety, but can slow down programming.
    175 For example, programming complexity increases when dealing with high-order methods or an overly specified
    176 throws clause. However some of the issues are more
    177 programming annoyances, such as writing/updating many exception signatures after adding or remove calls.
    178 Java programmers have developed multiple programming ``hacks'' to circumvent checked exceptions negating the robustness it is suppose to provide.
    179 For example, the ``catch-and-ignore" pattern, where the handler is empty because the exception does not appear relevant to the programmer versus
    180 repairing or recovering from the exception.
     153Checked exceptions are part of a function's interface,
     154the exception signature of the function.
     155Every function that could be raised from a function, either directly or
     156because it is not handled from a called function, is given.
     157Using this information, it is possible to statically verify if any given
     158exception is handled and guarantee that no exception will go unhandled.
     159Making exception information explicit improves clarity and safety,
     160but can slow down or restrict programming.
     161For example, programming high-order functions becomes much more complex
     162if the argument functions could raise exceptions.
     163However, as odd it may seem, the worst problems are rooted in the simple
     164inconvenience of writing and updating exception signatures.
     165This has caused Java programmers to develop multiple programming ``hacks''
     166to circumvent checked exceptions, negating their advantages.
     167One particularly problematic example is the ``catch-and-ignore'' pattern,
     168where an empty handler is used to handle an exception without doing any
     169recovery or repair. In theory that could be good enough to properly handle
     170the exception, but more often is used to ignore an exception that the       
     171programmer does not feel is worth the effort of handling it, for instance if
     172they do not believe it will ever be raised.
     173If they are incorrect the exception will be silenced, while in a similar
     174situation with unchecked exceptions the exception would at least activate   
     175the language's unhandled exception code (usually program abort with an 
     176error message).
    181177
    182178%\subsection
    183179Resumption exceptions are less popular,
    184 although resumption is as old as termination;
    185 hence, few
     180although resumption is as old as termination; hence, few
    186181programming languages have implemented them.
    187182% http://bitsavers.informatik.uni-stuttgart.de/pdf/xerox/parc/techReports/
    188183%   CSL-79-3_Mesa_Language_Manual_Version_5.0.pdf
    189 Mesa~\cite{Mesa} is one programming languages that did. Experience with Mesa
    190 is quoted as being one of the reasons resumptions are not
     184Mesa is one programming language that did.\cite{Mesa} Experience with Mesa
     185is quoted as being one of the reasons resumptions were not
    191186included in the \Cpp standard.
    192187% https://en.wikipedia.org/wiki/Exception_handling
    193 As a result, resumption has ignored in main-stream programming languages.
    194 However, ``what goes around comes around'' and resumption is being revisited now (like user-level threading).
    195 While rejecting resumption might have been the right decision in the past, there are decades
    196 of developments in computer science that have changed the situation.
    197 Some of these developments, such as functional programming's resumption
    198 equivalent, algebraic effects\cite{Zhang19}, are enjoying significant success.
    199 A complete reexamination of resumptions is beyond this thesis, but their re-emergence is
    200 enough to try them in \CFA.
     188Since then resumptions have been ignored in main-stream programming languages.
     189However, resumption is being revisited in the context of decades of other
     190developments in programming languages.
     191While rejecting resumption may have been the right decision in the past,
     192the situation has changed since then.
     193Some developments, such as the function programming equivalent to resumptions,
     194algebraic effects\cite{Zhang19}, are enjoying success.
     195A complete reexamination of resumptions is beyond this thesis,
     196but there reemergence is enough to try them in \CFA.
    201197% Especially considering how much easier they are to implement than
    202 % termination exceptions.
    203 
    204 %\subsection
    205 Functional languages tend to use other solutions for their primary EHM,
    206 but exception-like constructs still appear.
    207 Termination appears in error construct, which marks the result of an
    208 expression as an error; thereafter, the result of any expression that tries to use it is also an
    209 error, and so on until an appropriate handler is reached.
     198% termination exceptions and how much Peter likes them.
     199
     200%\subsection
     201Functional languages tend to use other solutions for their primary error
     202handling mechanism, but exception-like constructs still appear.
     203Termination appears in the error construct, which marks the result of an
     204expression as an error; then the result of any expression that tries to use
     205it also results in an error, and so on until an appropriate handler is reached.
    210206Resumption appears in algebraic effects, where a function dispatches its
    211207side-effects to its caller for handling.
    212208
    213209%\subsection
    214 Some programming languages have moved to a restricted kind of EHM
    215 called ``panic".
    216 In Rust~\cite{Rust}, a panic is just a program level abort that may be implemented by
    217 unwinding the stack like in termination exception handling.
    218 % https://doc.rust-lang.org/std/panic/fn.catch_unwind.html
    219 In Go~\cite{Go}, a panic is very similar to a termination, except it only supports
     210More recently exceptions seem to be vanishing from newer programming
     211languages, replaced by ``panic".
     212In Rust, a panic is just a program level abort that may be implemented by
     213unwinding the stack like in termination exception
     214handling.\cite{RustPanicMacro}\cite{RustPanicModule}
     215Go's panic through is very similar to a termination, except it only supports
    220216a catch-all by calling \code{Go}{recover()}, simplifying the interface at
    221 the cost of flexibility.
     217the cost of flexibility.\cite{Go:2021}
    222218
    223219%\subsection
    224220While exception handling's most common use cases are in error handling,
    225 here are other ways to handle errors with comparisons to exceptions.
     221here are some other ways to handle errors with comparisons with exceptions.
    226222\begin{itemize}
    227223\item\emph{Error Codes}:
    228 This pattern has a function return an enumeration (or just a set of fixed values) to indicate
    229 if an error occurred and possibly which error it was.
    230 
    231 Error codes mix exceptional and normal values, artificially enlarging the type and/or value range.
    232 Some languages address this issue by returning multiple values or a tuple, separating the error code from the function result.
    233 However, the main issue with error codes is forgetting to checking them,
     224This pattern has a function return an enumeration (or just a set of fixed
     225values) to indicate if an error has occurred and possibly which error it was.
     226
     227Error codes mix exceptional/error and normal values, enlarging the range of
     228possible return values. This can be addressed with multiple return values
     229(or a tuple) or a tagged union.
     230However, the main issue with error codes is forgetting to check them,
    234231which leads to an error being quietly and implicitly ignored.
    235 Some new languages have tools that issue warnings, if the error code is
    236 discarded to avoid this problem.
    237 Checking error codes also results in bloating the main execution path, especially if an error is not dealt with locally and has to be cascaded down the call stack to a higher-level function..
     232Some new languages and tools will try to issue warnings when an error code
     233is discarded to avoid this problem.
     234Checking error codes also bloats the main execution path,
     235especially if the error is not handled immediately hand has to be passed
     236through multiple functions before it is addressed.
    238237
    239238\item\emph{Special Return with Global Store}:
    240 Some functions only return a boolean indicating success or failure
    241 and store the exact reason for the error in a fixed global location.
    242 For example, many C routines return non-zero or -1, indicating success or failure,
    243 and write error details into the C standard variable @errno@.
    244 
    245 This approach avoids the multiple results issue encountered with straight error codes
    246 but otherwise has many (if not more) of the disadvantages.
    247 For example, everything that uses the global location must agree on all possible errors and global variable are unsafe with concurrency.
     239Similar to the error codes pattern but the function itself only returns
     240that there was an error
     241and store the reason for the error in a fixed global location.
     242For example many routines in the C standard library will only return some
     243error value (such as -1 or a null pointer) and the error code is written into
     244the standard variable @errno@.
     245
     246This approach avoids the multiple results issue encountered with straight
     247error codes but otherwise has the same disadvantages and more.
     248Every function that reads or writes to the global store must agree on all
     249possible errors and managing it becomes more complex with concurrency.
    248250
    249251\item\emph{Return Union}:
     
    254256so that one type can be used everywhere in error handling code.
    255257
    256 This pattern is very popular in functional or any semi-functional language with
    257 primitive support for tagged unions (or algebraic data types).
    258 % We need listing Rust/rust to format code snipits from it.
     258This pattern is very popular in any functional or semi-functional language
     259with primitive support for tagged unions (or algebraic data types).
     260% We need listing Rust/rust to format code snippets from it.
    259261% Rust's \code{rust}{Result<T, E>}
    260 The main advantage is providing for more information about an
    261 error, other than one of a fix-set of ids.
    262 While some languages use checked union access to force error-code checking,
    263 it is still possible to bypass the checking.
    264 The main disadvantage is again significant error code on the main execution path and cascading through called functions.
     262The main advantage is that an arbitrary object can be used to represent an
     263error so it can include a lot more information than a simple error code.
     264The disadvantages include that the it does have to be checked along the main
     265execution and if there aren't primitive tagged unions proper usage can be
     266hard to enforce.
    265267
    266268\item\emph{Handler Functions}:
    267 This pattern implicitly associates functions with errors.
    268 On error, the function that produced the error implicitly calls another function to
     269This pattern associates errors with functions.
     270On error, the function that produced the error calls another function to
    269271handle it.
    270272The handler function can be provided locally (passed in as an argument,
    271273either directly as as a field of a structure/object) or globally (a global
    272274variable).
    273 C++ uses this approach as its fallback system if exception handling fails, \eg
    274 \snake{std::terminate_handler} and for a time \snake{std::unexpected_handler}
    275 
    276 Handler functions work a lot like resumption exceptions, without the dynamic handler search.
    277 Therefore, setting setting up the handler can be more complex/expensive, especially if the handle must be passed through multiple function calls, but cheaper to call $O(1)$, and hence,
    278 are more suited to frequent exceptional situations.
    279 % The exception being global handlers if they are rarely change as the time
    280 % in both cases shrinks towards zero.
     275C++ uses this approach as its fallback system if exception handling fails,
     276such as \snake{std::terminate_handler} and, for a time,
     277\snake{std::unexpected_handler}.
     278
     279Handler functions work a lot like resumption exceptions,
     280but without the dynamic search for a handler.
     281Since setting up the handler can be more complex/expensive,
     282especially when the handler has to be passed through multiple layers of
     283function calls, but cheaper (constant time) to call,
     284they are more suited to more frequent (less exceptional) situations.
    281285\end{itemize}
    282286
    283287%\subsection
    284288Because of their cost, exceptions are rarely used for hot paths of execution.
    285 Therefore, there is an element of self-fulfilling prophecy for implementation
    286 techniques to make exceptions cheap to set-up at the cost
    287 of expensive usage.
    288 This cost differential is less important in higher-level scripting languages, where use of exceptions for other tasks is more common.
    289 An iconic example is Python's @StopIteration@ exception that is thrown by
    290 an iterator to indicate that it is exhausted, especially when combined with Python's heavy
    291 use of the iterator-based for-loop.
    292 % https://docs.python.org/3/library/exceptions.html#StopIteration
     289Hence, there is an element of self-fulfilling prophecy as implementation
     290techniques have been focused on making them cheap to set-up,
     291happily making them expensive to use in exchange.
     292This difference is less important in higher-level scripting languages,
     293where using exception for other tasks is more common.
     294An iconic example is Python's
     295\code{Python}{StopIteration}\cite{PythonExceptions} exception that
     296is thrown by an iterator to indicate that it is exhausted.
     297When paired with Python's iterator-based for-loop this will be thrown every
     298time the end of the loop is reached.\cite{PythonForLoop}
  • doc/theses/andrew_beach_MMath/performance.tex

    rdd1cc02 r5a40e4e  
    22\label{c:performance}
    33
    4 Performance has been of secondary importance for most of this project.
    5 Instead, the focus has been to get the features working. The only performance
    6 requirements is to ensure the tests for correctness run in a reasonable
    7 amount of time.
     4Performance is of secondary importance for most of this project.
     5Instead, the focus was to get the features working. The only performance
     6requirement is to ensure the tests for correctness run in a reasonable
     7amount of time. Hence, a few basic performance tests were performed to
     8check this requirement.
    89
    910\section{Test Set-Up}
    10 Tests will be run in \CFA, C++, Java and Python.
     11Tests were run in \CFA, C++, Java and Python.
    1112In addition there are two sets of tests for \CFA,
    12 one for termination exceptions and once with resumption exceptions.
     13one with termination and one with resumption.
    1314
    1415C++ is the most comparable language because both it and \CFA use the same
    1516framework, libunwind.
    16 In fact, the comparison is almost entirely a quality of implementation
    17 comparison. \CFA's EHM has had significantly less time to be optimized and
     17In fact, the comparison is almost entirely in quality of implementation.
     18Specifically, \CFA's EHM has had significantly less time to be optimized and
    1819does not generate its own assembly. It does have a slight advantage in that
    19 there are some features it does not handle, through utility functions,
    20 but otherwise \Cpp has a significant advantage.
    21 
    22 Java is another very popular language with similar termination semantics.
    23 It is implemented in a very different environment, a virtual machine with
     20\Cpp has to do some extra bookkeeping to support its utility functions,
     21but otherwise \Cpp should have a significant advantage.
     22
     23Java, a popular language with similar termination semantics,
     24is implemented in a very different environment, a virtual machine with
    2425garbage collection.
    2526It also implements the finally clause on try blocks allowing for a direct
    2627feature-to-feature comparison.
    27 As with \Cpp, Java's implementation is more mature, has more optimizations
    28 and more extra features.
    29 
    30 Python was used as a point of comparison because of the \CFA EHM's
    31 current performance goals, which is not be prohibitively slow while the
     28As with \Cpp, Java's implementation is mature, has more optimizations
     29and extra features as compared to \CFA.
     30
     31Python is used as an alternative comparison because of the \CFA EHM's
     32current performance goals, which is to not be prohibitively slow while the
    3233features are designed and examined. Python has similar performance goals for
    3334creating quick scripts and its wide use suggests it has achieved those goals.
    3435
    35 Unfortunately there are no notable modern programming languages with
    36 resumption exceptions. Even the older programming languages with resumptions
    37 seem to be notable only for having resumptions.
    38 So instead resumptions are compared to a less similar but much more familiar
    39 feature, termination exceptions.
    40 
    41 All tests are run inside a main loop which will perform the test
    42 repeatedly. This is to avoids start-up or tear-down time from
     36Unfortunately, there are no notable modern programming languages with
     37resumption exceptions. Even the older programming languages with resumption
     38seem to be notable only for having resumption.
     39Instead, resumption is compared to its simulation in other programming
     40languages: fixup functions that are explicitly passed into a function.
     41
     42All tests are run inside a main loop that repeatedly performs a test.
     43This approach avoids start-up or tear-down time from
    4344affecting the timing results.
    44 Tests ran their main loop a million times.
    45 The Java versions of the test also run this loop an extra 1000 times before
    46 beginning to time the results to ``warm-up" the JVM.
     45The number of times the loop is run is configurable from the command line;
     46the number used in the timing runs is given with the results per test.
     47The Java tests run the main loop 1000 times before
     48beginning the actual test to ``warm-up" the JVM.
     49% All other languages are precompiled or interpreted.
    4750
    4851Timing is done internally, with time measured immediately before and
    49 immediately after the test loop. The difference is calculated and printed.
    50 
     52after the test loop. The difference is calculated and printed.
    5153The loop structure and internal timing means it is impossible to test
    5254unhandled exceptions in \Cpp and Java as that would cause the process to
     
    5557critical.
    5658
    57 The exceptions used in these tests will always be a exception based off of
    58 the base exception. This requirement minimizes performance differences based
    59 on the object model used to repersent the exception.
    60 
    61 All tests were designed to be as minimal as possible while still preventing
    62 exessive optimizations.
     59The exceptions used in these tests are always based off of
     60the base exception for the language.
     61This requirement minimizes performance differences based
     62on the object model used to represent the exception.
     63
     64All tests are designed to be as minimal as possible, while still preventing
     65excessive optimizations.
    6366For example, empty inline assembly blocks are used in \CFA and \Cpp to
    6467prevent excessive optimizations while adding no actual work.
     
    6871% \code{C++}{catch(...)}).
    6972
     73When collecting data, each test is run eleven times. The top three and bottom
     74three results are discarded and the remaining five values are averaged.
     75The test are run with the latest (still pre-release) \CFA compiler,
     76using gcc-10 10.3.0 as a backend.
     77g++-10 10.3.0 is used for \Cpp.
     78Java tests are complied and run with version 11.0.11.
     79Python used version 3.8.10.
     80The machines used to run the tests are:
     81\begin{itemize}[nosep]
     82\item ARM 2280 Kunpeng 920 48-core 2$\times$socket
     83      \lstinline{@} 2.6 GHz running Linux v5.11.0-25
     84\item AMD 6380 Abu Dhabi 16-core 4$\times$socket
     85      \lstinline{@} 2.5 GHz running Linux v5.11.0-25
     86\end{itemize}
     87Representing the two major families of hardware architecture.
     88
    7089\section{Tests}
    7190The following tests were selected to test the performance of different
    7291components of the exception system.
    73 The should provide a guide as to where the EHM's costs can be found.
    74 
    75 \paragraph{Raise and Handle}
    76 The first group of tests involve setting up
    77 So there is three layers to the test. The first is set up and a loop, which
    78 configures the test and then runs it repeatedly to reduce the impact of
    79 start-up and shutdown on the results.
    80 Each iteration of the main loop
     92They should provide a guide as to where the EHM's costs are found.
     93
     94\paragraph{Stack Traversal}
     95This group measures the cost of traversing the stack,
     96(and in termination, unwinding it).
     97Inside the main loop is a call to a recursive function.
     98This function calls itself F times before raising an exception.
     99F is configurable from the command line, but is usually 100.
     100This builds up many stack frames, and any contents they may have,
     101before the raise.
     102The exception is always handled at the base of the stack.
     103For example the Empty test for \CFA resumption looks like:
     104\begin{cfa}
     105void unwind_empty(unsigned int frames) {
     106        if (frames) {
     107                unwind_empty(frames - 1);
     108        } else {
     109                throwResume (empty_exception){&empty_vt};
     110        }
     111}
     112\end{cfa}
     113Other test cases have additional code around the recursive call adding
     114something besides simple stack frames to the stack.
     115Note that both termination and resumption have to traverse over
     116the stack but only termination has to unwind it.
    81117\begin{itemize}[nosep]
    82 \item Empty Function:
     118% \item None:
     119% Reuses the empty test code (see below) except that the number of frames
     120% is set to 0 (this is the only test for which the number of frames is not
     121% 100). This isolates the start-up and shut-down time of a throw.
     122\item Empty:
    83123The repeating function is empty except for the necessary control code.
     124As other traversal tests add to this, it is the baseline for the group
     125as the cost comes from traversing over and unwinding a stack frame
     126that has no other interactions with the exception system.
    84127\item Destructor:
    85128The repeating function creates an object with a destructor before calling
    86129itself.
     130Comparing this to the empty test gives the time to traverse over and
     131unwind a destructor.
    87132\item Finally:
    88133The repeating function calls itself inside a try block with a finally clause
    89134attached.
     135Comparing this to the empty test gives the time to traverse over and
     136unwind a finally clause.
    90137\item Other Handler:
    91138The repeating function calls itself inside a try block with a handler that
    92 will not match the raised exception. (But is of the same kind of handler.)
     139does not match the raised exception, but is of the same kind of handler.
     140This means that the EHM has to check each handler, and continue
     141over all of them until it reaches the base of the stack.
     142Comparing this to the empty test gives the time to traverse over and
     143unwind a handler.
    93144\end{itemize}
    94145
    95146\paragraph{Cross Try Statement}
    96 The next group measures the cost of a try statement when no exceptions are
    97 raised. The test is set-up, then there is a loop to reduce the impact of
    98 start-up and shutdown on the results.
    99 In each iteration, a try statement is executed. Entering and leaving a loop
    100 is all the test wants to do.
     147This group of tests measures the cost for setting up exception handling,
     148if it is
     149not used (because the exceptional case did not occur).
     150Tests repeatedly cross (enter, execute and leave) a try statement but never
     151perform a raise.
    101152\begin{itemize}[nosep]
    102153\item Handler:
    103 The try statement has a handler (of the matching kind).
     154The try statement has a handler (of the appropriate kind).
    104155\item Finally:
    105156The try statement has a finally clause.
     
    107158
    108159\paragraph{Conditional Matching}
    109 This group of tests checks the cost of conditional matching.
     160This group measures the cost of conditional matching.
    110161Only \CFA implements the language level conditional match,
    111 the other languages must mimic with an ``unconditional" match (it still
    112 checks the exception's type) and conditional re-raise if it was not supposed
     162the other languages mimic it with an ``unconditional" match (it still
     163checks the exception's type) and conditional re-raise if it is not supposed
    113164to handle that exception.
     165
     166Here is the pattern shown in \CFA and \Cpp. Java and Python use the same
     167pattern as \Cpp, but with their own syntax.
     168
     169\begin{minipage}{0.45\textwidth}
     170\begin{cfa}
     171try {
     172        ...
     173} catch (exception_t * e ;
     174                should_catch(e)) {
     175        ...
     176}
     177\end{cfa}
     178\end{minipage}
     179\begin{minipage}{0.55\textwidth}
     180\begin{lstlisting}[language=C++]
     181try {
     182        ...
     183} catch (std::exception & e) {
     184        if (!should_catch(e)) throw;
     185        ...
     186}
     187\end{lstlisting}
     188\end{minipage}
    114189\begin{itemize}[nosep]
    115190\item Match All:
     
    118193The condition is always false. (Never matches or always re-raises.)
    119194\end{itemize}
     195
     196\paragraph{Resumption Simulation}
     197A slightly altered version of the Empty Traversal test is used when comparing
     198resumption to fix-up routines.
     199The handler, the actual resumption handler or the fix-up routine,
     200always captures a variable at the base of the loop,
     201and receives a reference to a variable at the raise site, either as a
     202field on the exception or an argument to the fix-up routine.
     203% I don't actually know why that is here but not anywhere else.
    120204
    121205%\section{Cost in Size}
     
    130214
    131215\section{Results}
    132 Each test was run eleven times. The top three and bottom three results were
    133 discarded and the remaining five values are averaged.
    134 
    135 In cases where a feature is not supported by a language the test is skipped
    136 for that language. Similarly, if a test is does not change between resumption
    137 and termination in \CFA, then only one test is written and the result
    138 was put into the termination column.
    139 
    140 % Raw Data:
    141 % run-algol-a.sat
    142 % ---------------
    143 % Raise Empty   &  82687046678 &  291616256 &   3252824847 & 15422937623 & 14736271114 \\
    144 % Raise D'tor   & 219933199603 &  297897792 & 223602799362 &         N/A &         N/A \\
    145 % Raise Finally & 219703078448 &  298391745 &          N/A &         ... & 18923060958 \\
    146 % Raise Other   & 296744104920 & 2854342084 & 112981255103 & 15475924808 & 21293137454 \\
    147 % Cross Handler &      9256648 &   13518430 &       769328 &     3486252 &    31790804 \\
    148 % Cross Finally &       769319 &        N/A &          N/A &     2272831 &    37491962 \\
    149 % Match All     &   3654278402 &   47518560 &   3218907794 &  1296748192 &   624071886 \\
    150 % Match None    &   4788861754 &   58418952 &   9458936430 &  1318065020 &   625200906 \\
    151 %
    152 % run-algol-thr-c
    153 % ---------------
    154 % Raise Empty   &   3757606400 &   36472972 &   3257803337 & 15439375452 & 14717808642 \\
    155 % Raise D'tor   &  64546302019 &  102148375 & 223648121635 &         N/A &         N/A \\
    156 % Raise Finally &  64671359172 &  103285005 &          N/A & 15442729458 & 18927008844 \\
    157 % Raise Other   & 294143497130 & 2630130385 & 112969055576 & 15448220154 & 21279953424 \\
    158 % Cross Handler &      9646462 &   11955668 &       769328 &     3453707 &    31864074 \\
    159 % Cross Finally &       773412 &        N/A &          N/A &     2253825 &    37266476 \\
    160 % Match All     &   3719462155 &   43294042 &   3223004977 &  1286054154 &   623887874 \\
    161 % Match None    &   4971630929 &   55311709 &   9481225467 &  1310251289 &   623752624 \\
    162 \begin{tabular}{|l|c c c c c|}
    163 \hline
    164               & \CFA (Terminate) & \CFA (Resume) & \Cpp & Java & Python \\
    165 \hline
    166 Raise Empty   & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
    167 Raise D'tor   & 0.0 & 0.0 & 0.0 & N/A & N/A \\
    168 Raise Finally & 0.0 & 0.0 & N/A & 0.0 & 0.0 \\
    169 Raise Other   & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
    170 Cross Handler & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
    171 Cross Finally & 0.0 & N/A & N/A & 0.0 & 0.0 \\
    172 Match All     & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
    173 Match None    & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
     216% First, introduce the tables.
     217\autoref{t:PerformanceTermination},
     218\autoref{t:PerformanceResumption}
     219and~\autoref{t:PerformanceFixupRoutines}
     220show the test results.
     221In cases where a feature is not supported by a language, the test is skipped
     222for that language and the result is marked N/A.
     223There are also cases where the feature is supported but measuring its
     224cost is impossible. This happened with Java, which uses a JIT that optimize
     225away the tests and it cannot be stopped.\cite{Dice21}
     226These tests are marked N/C.
     227To get results in a consistent range (1 second to 1 minute is ideal,
     228going higher is better than going low) N, the number of iterations of the
     229main loop in each test, is varied between tests. It is also given in the
     230results and has a value in the millions.
     231
     232An anomaly in some results came from \CFA's use of gcc nested functions.
     233These nested functions are used to create closures that can access stack
     234variables in their lexical scope.
     235However, if they do so, then they can cause the benchmark's run-time to
     236increase by an order of magnitude.
     237The simplest solution is to make those values global variables instead
     238of function local variables.
     239% Do we know if editing a global inside nested function is a problem?
     240Tests that had to be modified to avoid this problem have been marked
     241with a ``*'' in the results.
     242
     243% Now come the tables themselves:
     244% You might need a wider window for this.
     245
     246\begin{table}[htb]
     247\centering
     248\caption{Termination Performance Results (sec)}
     249\label{t:PerformanceTermination}
     250\begin{tabular}{|r|*{2}{|r r r r|}}
     251\hline
     252                       & \multicolumn{4}{c||}{AMD}         & \multicolumn{4}{c|}{ARM}  \\
     253\cline{2-9}
     254N\hspace{8pt}          & \multicolumn{1}{c}{\CFA} & \multicolumn{1}{c}{\Cpp} & \multicolumn{1}{c}{Java} & \multicolumn{1}{c||}{Python} &
     255                         \multicolumn{1}{c}{\CFA} & \multicolumn{1}{c}{\Cpp} & \multicolumn{1}{c}{Java} & \multicolumn{1}{c|}{Python} \\
     256\hline
     257Empty Traversal (1M)   & 3.4   & 2.8   & 18.3  & 23.4      & 3.7   & 3.2   & 15.5  & 14.8  \\
     258D'tor Traversal (1M)   & 48.4  & 23.6  & N/A   & N/A       & 64.2  & 29.0  & N/A   & N/A   \\
     259Finally Traversal (1M) & 3.4*  & N/A   & 17.9  & 29.0      & 4.1*  & N/A   & 15.6  & 19.0  \\
     260Other Traversal (1M)   & 3.6*  & 23.2  & 18.2  & 32.7      & 4.0*  & 24.5  & 15.5  & 21.4  \\
     261Cross Handler (1B)     & 6.0   & 0.9   & N/C   & 37.4      & 10.0  & 0.8   & N/C   & 32.2  \\
     262Cross Finally (1B)     & 0.9   & N/A   & N/C   & 44.1      & 0.8   & N/A   & N/C   & 37.3  \\
     263Match All (10M)        & 32.9  & 20.7  & 13.4  & 4.9       & 36.2  & 24.5  & 12.0  & 3.1   \\
     264Match None (10M)       & 32.7  & 50.3  & 11.0  & 5.1       & 36.3  & 71.9  & 12.3  & 4.2   \\
    174265\hline
    175266\end{tabular}
    176 
    177 % run-plg7a-a.sat
    178 % ---------------
    179 % Raise Empty   &  57169011329 &  296612564 &   2788557155 & 17511466039 & 23324548496 \\
    180 % Raise D'tor   & 150599858014 &  318443709 & 149651693682 &         N/A &         N/A \\
    181 % Raise Finally & 148223145000 &  373325807 &          N/A &         ... & 29074552998 \\
    182 % Raise Other   & 189463708732 & 3017109322 &  85819281694 & 17584295487 & 32602686679 \\
    183 % Cross Handler &      8001654 &   13584858 &      1555995 &     6626775 &    41927358 \\
    184 % Cross Finally &      1002473 &        N/A &          N/A &     4554344 &    51114381 \\
    185 % Match All     &   3162460860 &   37315018 &   2649464591 &  1523205769 &   742374509 \\
    186 % Match None    &   4054773797 &   47052659 &   7759229131 &  1555373654 &   744656403 \\
    187 %
    188 % run-plg7a-thr-a
    189 % ---------------
    190 % Raise Empty   &   3604235388 &   29829965 &   2786931833 & 17576506385 & 23352975105 \\
    191 % Raise D'tor   &  46552380948 &  178709605 & 149834207219 &         N/A &         N/A \\
    192 % Raise Finally &  46265157775 &  177906320 &          N/A & 17493045092 & 29170962959 \\
    193 % Raise Other   & 195659245764 & 2376968982 &  86070431924 & 17552979675 & 32501882918 \\
    194 % Cross Handler &    397031776 &   12503552 &      1451225 &     6658628 &    42304965 \\
    195 % Cross Finally &      1136746 &        N/A &          N/A &     4468799 &    46155817 \\
    196 % Match All     &   3189512499 &   39124453 &   2667795989 &  1525889031 &   733785613 \\
    197 % Match None    &   4094675477 &   48749857 &   7850618572 &  1566713577 &   733478963 \\
    198 
    199 % PLG7A (in seconds)
    200 \begin{tabular}{|l|c c c c c|}
    201 \hline
    202               & \CFA (Terminate) & \CFA (Resume) & \Cpp & Java & Python \\
    203 \hline
    204 % Raise Empty   & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
    205 % Raise D'tor   & 0.0 & 0.0 & 0.0 & N/A & N/A \\
    206 % Raise Finally & 0.0 & 0.0 & N/A & 0.0 & 0.0 \\
    207 % Raise Other   & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
    208 % Cross Handler & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
    209 % Cross Finally & 0.0 & N/A & N/A & 0.0 & 0.0 \\
    210 % Match All     & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
    211 % Match None    & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
    212 Raise Empty   & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
    213 Raise D'tor   & 0.0 & 0.0 & 0.0 & N/A & N/A \\
    214 Raise Finally & 0.0 & 0.0 & N/A & 0.0 & 0.0 \\
    215 Raise Other   & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
    216 Cross Handler & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
    217 Cross Finally & 0.0 & N/A & N/A & 0.0 & 0.0 \\
    218 Match All     & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
    219 Match None    & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
     267\end{table}
     268
     269\begin{table}[htb]
     270\centering
     271\caption{Resumption Performance Results (sec)}
     272\label{t:PerformanceResumption}
     273\begin{tabular}{|r||r||r|}
     274\hline
     275N\hspace{8pt}
     276                        & AMD     & ARM  \\
     277\hline
     278Empty Traversal (10M)   & 0.2     & 0.3  \\
     279D'tor Traversal (10M)   & 1.8     & 1.0  \\
     280Finally Traversal (10M) & 1.7     & 1.0  \\
     281Other Traversal (10M)   & 22.6    & 25.9 \\
     282Cross Handler (1B)      & 8.4     & 11.9 \\
     283Match All (100M)        & 2.3     & 3.2  \\
     284Match None (100M)       & 2.9     & 3.9  \\
    220285\hline
    221286\end{tabular}
    222 
    223 One result that is not directly related to \CFA but is important to keep in
    224 mind is that in exceptions the standard intuitions about which languages
    225 should go faster often do not hold. There are cases where Python out-preforms
    226 \Cpp and Java. The most likely explination is that, since exceptions are
    227 rarely considered to be the common case, the more optimized langages have
    228 optimized at their expence. In addition languages with high level           
    229 repersentations have a much easier time scanning the stack as there is less
    230 to decode.
    231 
    232 This means that while \CFA does not actually keep up with Python in every
    233 case it is no worse than roughly half the speed of \Cpp. This is good
    234 enough for the prototyping purposes of the project.
    235 
    236 One difference not shown is that optimizations in \CFA is very fragile.
    237 The \CFA compiler uses gcc as part of its complation process and the version
    238 of gcc could change the speed of some of the benchmarks by 10 times or more.
    239 Similar changes to g++ for the \Cpp benchmarks had no significant changes.
    240 Because of the connection between gcc and g++; this suggests it is not the
    241 optimizations that are changing but how the optimizer is detecting if the
    242 optimizations can be applied. So the optimizations are always applied in
    243 g++, but only newer versions of gcc can detect that they can be applied in
    244 the more complex \CFA code.
    245 
    246 Resumption exception handling is also incredibly fast. Often an order of
    247 magnitude or two better than the best termination speed.
    248 There is a simple explination for this; traversing a linked list is much   
    249 faster than examining and unwinding the stack. When resumption does not do as
    250 well its when more try statements are used per raise. Updating the interal
    251 linked list is not very expencive but it does add up.
    252 
    253 The relative speed of the Match All and Match None tests (within each
    254 language) can also show the effectiveness conditional matching as compared
    255 to catch and rethrow.
    256 \begin{itemize}[nosep]
    257 \item
    258 Java and Python get similar values in both tests.
    259 Between the interperated code, a higher level repersentation of the call
    260 stack and exception reuse it it is possible the cost for a second
    261 throw can be folded into the first.
    262 % Is this due to optimization?
    263 \item
    264 Both types of \CFA are slighly slower if there is not a match.
    265 For termination this likely comes from unwinding a bit more stack through
    266 libunwind instead of executing the code normally.
    267 For resumption there is extra work in traversing more of the list and running
    268 more checks for a matching exceptions.
    269 % Resumption is a bit high for that but this is my best theory.
    270 \item
    271 Then there is \Cpp, which takes 2--3 times longer to catch and rethrow vs.
    272 just the catch. This is very high, but it does have to repeat the same
    273 process of unwinding the stack and may have to parse the LSDA of the function
    274 with the catch and rethrow twice, once before the catch and once after the
    275 rethrow.
    276 % I spent a long time thinking of what could push it over twice, this is all
    277 % I have to explain it.
    278 \end{itemize}
    279 The difference in relative performance does show that there are savings to
    280 be made by performing the check without catching the exception.
     287\end{table}
     288
     289\begin{table}[htb]
     290\centering
     291\small
     292\caption{Resumption/Fixup Routine Comparison (sec)}
     293\label{t:PerformanceFixupRoutines}
     294\setlength{\tabcolsep}{5pt}
     295\begin{tabular}{|r|*{2}{|r r r r r|}}
     296\hline
     297            & \multicolumn{5}{c||}{AMD}     & \multicolumn{5}{c|}{ARM}  \\
     298\cline{2-11}
     299N\hspace{8pt}       & \multicolumn{1}{c}{Raise} & \multicolumn{1}{c}{\CFA} & \multicolumn{1}{c}{\Cpp} & \multicolumn{1}{c}{Java} & \multicolumn{1}{c||}{Python} &
     300              \multicolumn{1}{c}{Raise} & \multicolumn{1}{c}{\CFA} & \multicolumn{1}{c}{\Cpp} & \multicolumn{1}{c}{Java} & \multicolumn{1}{c|}{Python} \\
     301\hline
     302Resume Empty (10M)  & 1.5 & 1.5 & 14.7 & 2.3 & 176.1  & 1.0 & 1.4 & 8.9 & 1.2 & 119.9 \\
     303\hline
     304\end{tabular}
     305\end{table}
     306
     307% Now discuss the results in the tables.
     308One result not directly related to \CFA but important to keep in mind is that,
     309for exceptions, the standard intuition about which languages should go
     310faster often does not hold.
     311For example, there are a few cases where Python out-performs
     312\CFA, \Cpp and Java.
     313% To be exact, the Match All and Match None cases.
     314The most likely explanation is that, since exceptions
     315are rarely considered to be the common case, the more optimized languages
     316make that case expensive to improve other cases.
     317In addition, languages with high-level representations have a much
     318easier time scanning the stack as there is less to decode.
     319
     320As stated,
     321the performance tests are not attempting to show \CFA has a new competitive
     322way of implementing exception handling.
     323The only performance requirement is to insure the \CFA EHM has reasonable
     324performance for prototyping.
     325Although that may be hard to exactly quantify, I believe it has succeeded
     326in that regard.
     327Details on the different test cases follow.
     328
     329\subsection{Termination \texorpdfstring{(\autoref{t:PerformanceTermination})}{}}
     330
     331\begin{description}
     332\item[Empty Traversal]
     333\CFA is slower than \Cpp, but is still faster than the other languages
     334and closer to \Cpp than other languages.
     335This result is to be expected,
     336as \CFA is closer to \Cpp than the other languages.
     337
     338\item[D'tor Traversal]
     339Running destructors causes a huge slowdown in the two languages that support
     340them. \CFA has a higher proportionate slowdown but it is similar to \Cpp's.
     341Considering the amount of work done in destructors is effectively zero
     342(an assembly comment), the cost
     343must come from the change of context required to run the destructor.
     344
     345\item[Finally Traversal]
     346Performance is similar to Empty Traversal in all languages that support finally
     347clauses. Only Python seems to have a larger than random noise change in
     348its run-time and it is still not large.
     349Despite the similarity between finally clauses and destructors,
     350finally clauses seem to avoid the spike that run-time destructors have.
     351Possibly some optimization removes the cost of changing contexts.
     352
     353\item[Other Traversal]
     354For \Cpp, stopping to check if a handler applies seems to be about as
     355expensive as stopping to run a destructor.
     356This results in a significant jump.
     357
     358Other languages experience a small increase in run-time.
     359The small increase likely comes from running the checks,
     360but they could avoid the spike by not having the same kind of overhead for
     361switching to the check's context.
     362
     363\item[Cross Handler]
     364Here \CFA falls behind \Cpp by a much more significant margin.
     365This is likely due to the fact \CFA has to insert two extra function
     366calls, while \Cpp does not have to do execute any other instructions.
     367Python is much further behind.
     368
     369\item[Cross Finally]
     370\CFA's performance now matches \Cpp's from Cross Handler.
     371If the code from the finally clause is being inlined,
     372which is just an asm comment, than there are no additional instructions
     373to execute again when exiting the try statement normally.
     374
     375\item[Conditional Match]
     376Both of the conditional matching tests can be considered on their own.
     377However for evaluating the value of conditional matching itself, the
     378comparison of the two sets of results is useful.
     379Consider the massive jump in run-time for \Cpp going from match all to match
     380none, which none of the other languages have.
     381Some strange interaction is causing run-time to more than double for doing
     382twice as many raises.
     383Java and Python avoid this problem and have similar run-time for both tests,
     384possibly through resource reuse or their program representation.
     385However \CFA is built like \Cpp and avoids the problem as well, this matches
     386the pattern of the conditional match, which makes the two execution paths
     387very similar.
     388
     389\end{description}
     390
     391\subsection{Resumption \texorpdfstring{(\autoref{t:PerformanceResumption})}{}}
     392
     393Moving on to resumption, there is one general note,
     394resumption is \textit{fast}. The only test where it fell
     395behind termination is Cross Handler.
     396In every other case, the number of iterations had to be increased by a
     397factor of 10 to get the run-time in an appropriate range
     398and in some cases resumption still took less time.
     399
     400% I tried \paragraph and \subparagraph, maybe if I could adjust spacing
     401% between paragraphs those would work.
     402\begin{description}
     403\item[Empty Traversal]
     404See above for the general speed-up notes.
     405This result is not surprising as resumption's linked-list approach
     406means that traversing over stack frames without a resumption handler is
     407$O(1)$.
     408
     409\item[D'tor Traversal]
     410Resumption does have the same spike in run-time that termination has.
     411The run-time is actually very similar to Finally Traversal.
     412As resumption does not unwind the stack, both destructors and finally
     413clauses are run while walking down the stack during the recursive returns.
     414So it follows their performance is similar.
     415
     416\item[Finally Traversal]
     417Same as D'tor Traversal,
     418except termination did not have a spike in run-time on this test case.
     419
     420\item[Other Traversal]
     421Traversing across handlers reduces resumption's advantage as it actually
     422has to stop and check each one.
     423Resumption still came out ahead (adjusting for iterations) but by much less
     424than the other cases.
     425
     426\item[Cross Handler]
     427The only test case where resumption could not keep up with termination,
     428although the difference is not as significant as many other cases.
     429It is simply a matter of where the costs come from,
     430both termination and resumption have some work to set-up or tear-down a
     431handler. It just so happens that resumption's work is slightly slower.
     432
     433\item[Conditional Match]
     434Resumption shows a slight slowdown if the exception is not matched
     435by the first handler, which follows from the fact the second handler now has
     436to be checked. However the difference is not large.
     437
     438\end{description}
     439
     440\subsection{Resumption/Fixup \texorpdfstring{(\autoref{t:PerformanceFixupRoutines})}{}}
     441
     442Finally are the results of the resumption/fixup routine comparison.
     443These results are surprisingly varied. It is possible that creating a closure
     444has more to do with performance than passing the argument through layers of
     445calls.
     446At 100 stack frames, resumption and manual fixup routines have similar
     447performance in \CFA.
     448More experiments could try to tease out the exact trade-offs,
     449but the prototype's only performance goal is to be reasonable.
     450It has already in that range, and \CFA's fixup routine simulation is
     451one of the faster simulations as well.
     452Plus exceptions add features and remove syntactic overhead,
     453so even at similar performance resumptions have advantages
     454over fixup routines.
  • doc/theses/andrew_beach_MMath/resumption-marking.fig

    rdd1cc02 r5a40e4e  
    88-2
    991200 2
    10 6 5985 1530 6165 3105
    11 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 6075 1620 90 90 6075 1620 6075 1710
    12 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 6075 2340 90 90 6075 2340 6075 2430
    13 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 6075 3015 90 90 6075 3015 6075 3105
    14 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    15         1 1 1.00 60.00 120.00
    16          6075 1755 6075 2205
    17 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    18         1 1 1.00 60.00 120.00
    19          6075 2475 6075 2925
    20 -6
    21 6 3465 1530 3645 3105
    22 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3555 1620 90 90 3555 1620 3555 1710
    23 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3555 2340 90 90 3555 2340 3555 2430
    24 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3555 3015 90 90 3555 3015 3555 3105
    25 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    26         1 1 1.00 60.00 120.00
    27          3555 1755 3555 2205
    28 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    29         1 1 1.00 60.00 120.00
    30          3555 2475 3555 2925
    31 -6
    32 6 2115 1530 2295 3105
    33 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2205 1620 90 90 2205 1620 2205 1710
    34 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2205 2340 90 90 2205 2340 2205 2430
    35 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2205 3015 90 90 2205 3015 2205 3105
    36 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    37         1 1 1.00 60.00 120.00
    38          2205 1755 2205 2205
    39 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    40         1 1 1.00 60.00 120.00
    41          2205 2475 2205 2925
    42 -6
    43101 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 4905 1620 90 90 4905 1620 4905 1710
    44 1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 4905 3015 90 90 4905 3015 4905 3105
    45111 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 4905 945 90 90 4905 945 4905 1035
    46121 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 4905 2340 90 90 4905 2340 4905 2430
    47 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    48         1 1 1.00 60.00 120.00
    49          2790 1620 2430 1620
    50 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    51         1 1 1.00 60.00 120.00
    52          4095 2340 3735 2340
    53 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    54         1 1 1.00 60.00 120.00
    55          6660 1620 6300 1620
    56 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    57         1 1 1.00 60.00 120.00
    58          5490 945 5130 945
     131 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 1665 1620 90 90 1665 1620 1665 1710
     141 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 1665 2340 90 90 1665 2340 1665 2430
     151 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 1665 3060 90 90 1665 3060 1665 3150
     161 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3195 1620 90 90 3195 1620 3195 1710
     171 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3195 2340 90 90 3195 2340 3195 2430
     181 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3195 3060 90 90 3195 3060 3195 3150
     191 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 6525 1620 90 90 6525 1620 6525 1710
     201 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 6525 2340 90 90 6525 2340 6525 2430
     211 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 4905 3060 90 90 4905 3060 4905 3150
     221 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 6525 3060 90 90 6525 3060 6525 3150
    59232 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    6024        1 1 1.00 60.00 120.00
     
    6630        1 1 1.00 60.00 120.00
    6731         4770 1080 4590 1260 4590 2070 4770 2250
    68 4 0 0 50 -1 0 12 0.0000 4 135 1170 1980 3375 Initial State\001
    69 4 0 0 50 -1 0 12 0.0000 4 135 1170 3420 3375 Found Handler\001
    70 4 0 0 50 -1 0 12 0.0000 4 165 810 4770 3375 Try block\001
    71 4 0 0 50 -1 0 12 0.0000 4 135 900 4770 3555 in Handler\001
    72 4 0 0 50 -1 0 12 0.0000 4 165 1530 5940 3375 Handling Complete\001
     322 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
     33        1 1 1.00 60.00 120.00
     34         1665 1755 1665 2205
     352 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
     36        1 1 1.00 60.00 120.00
     37         1665 2475 1665 2925
     382 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
     39        1 1 1.00 60.00 120.00
     40         3195 1755 3195 2205
     412 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
     42        1 1 1.00 60.00 120.00
     43         3195 2475 3195 2925
     442 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
     45        1 1 1.00 60.00 120.00
     46         6525 1755 6525 2205
     472 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
     48        1 1 1.00 60.00 120.00
     49         6525 2475 6525 2925
     502 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
     51        1 1 1.00 60.00 120.00
     52         1260 1620 1485 1620
     532 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
     54        1 1 1.00 60.00 120.00
     55         1980 1440 1755 1440
     562 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
     57        1 1 1.00 60.00 120.00
     58         2790 2340 3015 2340
     592 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
     60        1 1 1.00 60.00 120.00
     61         3600 1620 3375 1620
     622 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
     63        1 1 1.00 60.00 120.00
     64         4500 945 4725 945
     652 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
     66        1 1 1.00 60.00 120.00
     67         5265 765 5040 765
     682 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
     69        1 1 1.00 60.00 120.00
     70         6120 1620 6345 1620
     712 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
     72        1 1 1.00 60.00 120.00
     73         6840 1440 6615 1440
     744 1 0 50 -1 0 12 0.0000 0 135 1170 1665 3375 Initial State\001
     754 1 0 50 -1 0 12 0.0000 0 135 1170 3195 3375 Found Handler\001
     764 1 0 50 -1 0 12 0.0000 0 165 1530 6570 3375 Handling Complete\001
     774 2 0 50 -1 0 12 0.0000 0 135 720 1485 2385 handlers\001
     784 1 0 50 -1 0 12 0.0000 0 135 900 4905 3375 Handler in\001
     794 1 0 50 -1 0 12 0.0000 0 165 810 4905 3600 Try block\001
     804 0 0 50 -1 0 12 0.0000 0 135 360 855 1665 head\001
     814 0 0 50 -1 0 12 0.0000 4 120 810 2025 1485 execution\001
     824 0 0 50 -1 0 12 0.0000 0 135 360 2385 2385 head\001
     834 0 0 50 -1 0 12 0.0000 4 120 810 3645 1665 execution\001
     844 0 0 50 -1 0 12 0.0000 0 135 360 4095 990 head\001
     854 0 0 50 -1 0 12 0.0000 4 120 810 5310 810 execution\001
     864 0 0 50 -1 0 12 0.0000 0 135 360 5715 1665 head\001
     874 0 0 50 -1 0 12 0.0000 4 120 810 6885 1485 execution\001
  • doc/theses/andrew_beach_MMath/uw-ethesis-frontpgs.tex

    rdd1cc02 r5a40e4e  
    129129\begin{center}\textbf{Abstract}\end{center}
    130130
    131 This is the abstract.
     131The \CFA (Cforall) programming language is an evolutionary refinement of
     132the C programming language, adding modern programming features without
     133changing the programming paradigms of C.
     134One of these modern programming features is more powerful error handling
     135through the addition of an exception handling mechanism (EHM).
     136
     137This thesis covers the design and implementation of the \CFA EHM,
     138along with a review of the other required \CFA features.
     139The EHM includes common features of termination exception handling and
     140similar support for resumption exception handling.
     141The design of both has been adapted to utilize other tools \CFA provides,
     142as well as fit with the assertion based interfaces of the language.
     143
     144The EHM has been implemented into the \CFA compiler and run-time environment.
     145Although it has not yet been optimized, performance testing has shown it has
     146comparable performance to other EHM's,
     147which is sufficient for use in current \CFA programs.
    132148
    133149\cleardoublepage
     
    138154\begin{center}\textbf{Acknowledgements}\end{center}
    139155
    140 I would like to thank all the little people who made this thesis possible.
     156I would like to thank all the people who made this thesis possible.
     157(I'm waiting until who is involved is finalized.)
     158
    141159\cleardoublepage
    142160
  • doc/theses/andrew_beach_MMath/uw-ethesis.bib

    rdd1cc02 r5a40e4e  
    11% Bibliography of key references for "LaTeX for Thesis and Large Documents"
    22% For use with BibTeX
     3% The online reference does not seem to be supported here.
    34
    4 @book{goossens.book,
    5         author =        "Michel Goossens and Frank Mittelbach and
    6                          Alexander Samarin",
    7         title =         "The \LaTeX\ Companion",
    8         year =          "1994",
    9         publisher =     "Addison-Wesley",
    10         address =       "Reading, Massachusetts"
     5@misc{Dice21,
     6    author      = {Dave Dice},
     7    year        = 2021,
     8    month       = aug,
     9    howpublished= {personal communication}
    1110}
    1211
    13 @book{knuth.book,
    14         author =        "Donald Knuth",
    15         title =         "The \TeX book",
    16         year =          "1986",
    17         publisher =     "Addison-Wesley",
    18         address =       "Reading, Massachusetts"
     12@misc{CforallExceptionBenchmarks,
     13    contributer = {pabuhr@plg},
     14    key         = {Cforall Exception Benchmarks},
     15    author      = {{\textsf{C}{$\mathbf{\forall}$} Exception Benchmarks}},
     16    howpublished= {\href{https://github.com/cforall/ExceptionBenchmarks_SPE20}{https://\-github.com/\-cforall/\-ExceptionBenchmarks\_SPE20}},
    1917}
    2018
    21 @book{lamport.book,
    22         author =        "Leslie Lamport",
    23         title =         "\LaTeX\ --- A Document Preparation System",
    24         edition =       "Second",
    25         year =          "1994",
    26         publisher =     "Addison-Wesley",
    27         address =       "Reading, Massachusetts"
     19% Could not get `#the-for-statement` to work.
     20@misc{PythonForLoop,
     21    author={Python Software Foundation},
     22    key={Python Compound Statements},
     23    howpublished={\href{https://docs.python.org/3/reference/compound_stmts.html}{https://\-docs.python.org/\-3/\-reference/\-compound\_stmts.html}},
     24    addendum={Accessed 2021-08-30},
    2825}
     26
     27% Again, I would like this to have `#StopIteration`.
     28@misc{PythonExceptions,
     29    author={Python Software Foundation},
     30    key={Python Exceptions},
     31    howpublished={\href{https://docs.python.org/3/library/exceptions.html}{https://\-docs.python.org/\-3/\-library/\-exceptions.html}},
     32    addendum={Accessed 2021-08-30},
     33}
     34
     35@misc{CppHistory,
     36    author={C++ Community},
     37    key={Cpp Reference History},
     38    howpublished={\href{https://en.cppreference.com/w/cpp/language/history}{https://\-en.cppreference.com/\-w/\-cpp/\-language/\-history}},
     39    addendum={Accessed 2021-08-30},
     40}
     41
     42@misc{RustPanicMacro,
     43    author={The Rust Team},
     44    key={Rust Panic Macro},
     45    howpublished={\href{https://doc.rust-lang.org/std/panic/index.html}{https://\-doc.rust-lang.org/\-std/\-panic/\-index.html}},
     46    addendum={Accessed 2021-08-31},
     47}
     48
     49@misc{RustPanicModule,
     50    author={The Rust Team},
     51    key={Rust Panic Module},
     52    howpublished={\href{https://doc.rust-lang.org/std/panic/index.html}{https://\-doc.rust-lang.org/\-std/\-panic/\-index.html}},
     53    addendum={Accessed 2021-08-31},
     54}
     55
     56@manual{Go:2021,
     57    keywords={Go programming language},
     58    author={Robert Griesemer and Rob Pike and Ken Thompson},
     59    title={{Go} Programming Language},
     60    organization={Google},
     61    year=2021,
     62    note={\href{http://golang.org/ref/spec}{http://\-golang.org/\-ref/\-spec}},
     63    addendum={Accessed 2021-08-31},
     64}
  • doc/theses/andrew_beach_MMath/uw-ethesis.tex

    rdd1cc02 r5a40e4e  
    210210\lstMakeShortInline@
    211211\lstset{language=CFA,style=cfacommon,basicstyle=\linespread{0.9}\tt}
    212 % PAB causes problems with inline @=
    213 %\lstset{moredelim=**[is][\protect\color{red}]{@}{@}}
    214212% Annotations from Peter:
    215213\newcommand{\PAB}[1]{{\color{blue}PAB: #1}}
  • doc/theses/andrew_beach_MMath/vtable-layout.fig

    rdd1cc02 r5a40e4e  
    88-2
    991200 2
    10 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 1
    11          1620 1665
    12102 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
    1311         3510 1890 3645 1755
     
    16142 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
    1715         3645 1305 3645 1755
     162 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
     17         2115 1935 2250 1935
     182 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 4
     19         2250 1170 2115 1170 2115 2475 2250 2475
     202 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
     21         2250 1350 2115 1350
    18224 0 0 50 -1 0 12 0.0000 4 165 630 2295 1305 type_id\001
    19234 0 0 50 -1 0 12 0.0000 4 165 1170 2295 1500 parent_field0\001
  • libcfa/prelude/builtins.c

    rdd1cc02 r5a40e4e  
    1010// Created On       : Fri Jul 21 16:21:03 2017
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Wed Jul 21 13:31:34 2021
    13 // Update Count     : 129
     12// Last Modified On : Sat Aug 14 08:45:54 2021
     13// Update Count     : 133
    1414//
    1515
     
    107107#endif // __SIZEOF_INT128__
    108108
     109// for-control index constraints
     110// forall( T | { void ?{}( T &, zero_t ); void ?{}( T &, one_t ); T ?+=?( T &, T ); T ?-=?( T &, T ); int ?<?( T, T ); } )
     111// static inline T __for_control_index_constraints__( T t ) { return t; }
     112
    109113// exponentiation operator implementation
    110114
  • libcfa/src/Makefile.am

    rdd1cc02 r5a40e4e  
    4848        math.hfa \
    4949        time_t.hfa \
     50        bits/algorithm.hfa \
    5051        bits/align.hfa \
    5152        bits/containers.hfa \
     
    7778        memory.hfa \
    7879        parseargs.hfa \
     80        parseconfig.hfa \
    7981        rational.hfa \
    8082        stdlib.hfa \
     
    8587        containers/pair.hfa \
    8688        containers/result.hfa \
     89        containers/string.hfa \
     90        containers/string_res.hfa \
    8791        containers/vector.hfa \
    8892        device/cpu.hfa
     
    9094libsrc = ${inst_headers_src} ${inst_headers_src:.hfa=.cfa} \
    9195        assert.cfa \
    92         bits/algorithm.hfa \
    9396        bits/debug.cfa \
    9497        exception.c \
     
    106109        concurrency/invoke.h \
    107110        concurrency/future.hfa \
    108         concurrency/kernel/fwd.hfa
     111        concurrency/kernel/fwd.hfa \
     112        concurrency/mutex_stmt.hfa
    109113
    110114inst_thread_headers_src = \
  • libcfa/src/concurrency/kernel/startup.cfa

    rdd1cc02 r5a40e4e  
    235235
    236236        register_tls( mainProcessor );
     237        mainThread->last_cpu = __kernel_getcpu();
    237238
    238239        //initialize the global state variables
     
    478479        state = Start;
    479480        self_cor{ info };
    480         last_cpu = __kernel_getcpu();
    481481        curr_cor = &self_cor;
    482482        curr_cluster = mainCluster;
  • libcfa/src/concurrency/locks.hfa

    rdd1cc02 r5a40e4e  
    324324        }
    325325
    326         // linear backoff bounded by spin_count
    327         spin = spin_start;
    328         int spin_counter = 0;
    329         int yield_counter = 0;
    330         for ( ;; ) {
    331                 if(try_lock_contention(this)) return true;
    332                 if(spin_counter < spin_count) {
    333                         for (int i = 0; i < spin; i++) Pause();
    334                         if (spin < spin_end) spin += spin;
    335                         else spin_counter++;
    336                 } else if (yield_counter < yield_count) {
    337                         // after linear backoff yield yield_count times
    338                         yield_counter++;
    339                         yield();
    340                 } else { break; }
    341         }
    342 
    343         // block until signalled
    344         while (block(this)) if(try_lock_contention(this)) return true;
    345 
    346         // this should never be reached as block(this) always returns true
    347         return false;
    348 }
    349 
    350 static inline bool lock_improved(linear_backoff_then_block_lock & this) with(this) {
    351         // if owner just return
    352         if (active_thread() == owner) return true;
    353         size_t compare_val = 0;
    354         int spin = spin_start;
    355         // linear backoff
    356         for( ;; ) {
    357                 compare_val = 0;
    358                 if (internal_try_lock(this, compare_val)) return true;
    359                 if (2 == compare_val) break;
    360                 for (int i = 0; i < spin; i++) Pause();
    361                 if (spin >= spin_end) break;
    362                 spin += spin;
    363         }
    364 
    365         // linear backoff bounded by spin_count
    366         spin = spin_start;
    367         int spin_counter = 0;
    368         int yield_counter = 0;
    369         for ( ;; ) {
    370                 compare_val = 0;
    371                 if(internal_try_lock(this, compare_val)) return true;
    372                 if (2 == compare_val) break;
    373                 if(spin_counter < spin_count) {
    374                         for (int i = 0; i < spin; i++) Pause();
    375                         if (spin < spin_end) spin += spin;
    376                         else spin_counter++;
    377                 } else if (yield_counter < yield_count) {
    378                         // after linear backoff yield yield_count times
    379                         yield_counter++;
    380                         yield();
    381                 } else { break; }
    382         }
    383 
    384326        if(2 != compare_val && try_lock_contention(this)) return true;
    385327        // block until signalled
     
    402344static inline void on_notify(linear_backoff_then_block_lock & this, struct thread$ * t ) { unpark(t); }
    403345static inline size_t on_wait(linear_backoff_then_block_lock & this) { unlock(this); return 0; }
    404 static inline void on_wakeup(linear_backoff_then_block_lock & this, size_t recursion ) { lock_improved(this); }
     346static inline void on_wakeup(linear_backoff_then_block_lock & this, size_t recursion ) { lock(this); }
    405347
    406348//-----------------------------------------------------------------------------
  • libcfa/src/concurrency/monitor.cfa

    rdd1cc02 r5a40e4e  
    367367
    368368        // __cfaabi_dbg_print_safe( "MGUARD : entered\n" );
     369}
     370
     371void ?{}( monitor_guard_t & this, monitor$ * m [], __lock_size_t count ) {
     372        this{ m, count, 0p };
    369373}
    370374
     
    986990}
    987991
     992//-----------------------------------------------------------------------------
     993// Enter routine for mutex stmt
     994// Can't be accepted since a mutex stmt is effectively an anonymous routine
     995// Thus we do not need a monitor group
     996void lock( monitor$ * this ) {
     997        thread$ * thrd = active_thread();
     998
     999        // Lock the monitor spinlock
     1000        lock( this->lock __cfaabi_dbg_ctx2 );
     1001
     1002        __cfaabi_dbg_print_safe( "Kernel : %10p Entering mon %p (%p)\n", thrd, this, this->owner);
     1003
     1004        if( unlikely(0 != (0x1 & (uintptr_t)this->owner)) ) {
     1005                abort( "Attempt by thread \"%.256s\" (%p) to access joined monitor %p.", thrd->self_cor.name, thrd, this );
     1006        }
     1007        else if( !this->owner ) {
     1008                // No one has the monitor, just take it
     1009                __set_owner( this, thrd );
     1010
     1011                __cfaabi_dbg_print_safe( "Kernel :  mon is free \n" );
     1012        }
     1013        else if( this->owner == thrd) {
     1014                // We already have the monitor, just note how many times we took it
     1015                this->recursion += 1;
     1016
     1017                __cfaabi_dbg_print_safe( "Kernel :  mon already owned \n" );
     1018        }
     1019        else {
     1020                __cfaabi_dbg_print_safe( "Kernel :  blocking \n" );
     1021
     1022                // Some one else has the monitor, wait in line for it
     1023                /* paranoid */ verify( thrd->link.next == 0p );
     1024                append( this->entry_queue, thrd );
     1025                /* paranoid */ verify( thrd->link.next == 1p );
     1026
     1027                unlock( this->lock );
     1028                park();
     1029
     1030                __cfaabi_dbg_print_safe( "Kernel : %10p Entered  mon %p\n", thrd, this);
     1031
     1032                /* paranoid */ verifyf( active_thread() == this->owner, "Expected owner to be %p, got %p (r: %i, m: %p)", active_thread(), this->owner, this->recursion, this );
     1033                return;
     1034        }
     1035
     1036        __cfaabi_dbg_print_safe( "Kernel : %10p Entered  mon %p\n", thrd, this);
     1037
     1038        /* paranoid */ verifyf( active_thread() == this->owner, "Expected owner to be %p, got %p (r: %i, m: %p)", active_thread(), this->owner, this->recursion, this );
     1039        /* paranoid */ verify( this->lock.lock );
     1040
     1041        // Release the lock and leave
     1042        unlock( this->lock );
     1043        return;
     1044}
     1045
     1046// Leave routine for mutex stmt
     1047// Is just a wrapper around __leave for the is_lock trait to see
     1048void unlock( monitor$ * this ) { __leave( this ); }
     1049
    9881050// Local Variables: //
    9891051// mode: c //
  • libcfa/src/concurrency/monitor.hfa

    rdd1cc02 r5a40e4e  
    4848
    4949void ?{}( monitor_guard_t & this, monitor$ ** m, __lock_size_t count, void (*func)() );
     50void ?{}( monitor_guard_t & this, monitor$ ** m, __lock_size_t count );
    5051void ^?{}( monitor_guard_t & this );
    5152
     
    148149void __waitfor_internal( const __waitfor_mask_t & mask, int duration );
    149150
     151// lock and unlock routines for mutex statements to use
     152void lock( monitor$ * this );
     153void unlock( monitor$ * this );
     154
    150155// Local Variables: //
    151156// mode: c //
  • libcfa/src/concurrency/thread.cfa

    rdd1cc02 r5a40e4e  
    3434        preempted = __NO_PREEMPTION;
    3535        corctx_flag = false;
     36        disable_interrupts();
    3637        last_cpu = __kernel_getcpu();
     38        enable_interrupts();
    3739        curr_cor = &self_cor;
    3840        self_mon.owner = &this;
  • libcfa/src/fstream.cfa

    rdd1cc02 r5a40e4e  
    124124void open( ofstream & os, const char name[], const char mode[] ) {
    125125        FILE * file = fopen( name, mode );
    126         #ifdef __CFA_DEBUG__
     126        // #ifdef __CFA_DEBUG__
    127127        if ( file == 0p ) {
    128128                throw (Open_Failure){ os };
    129129                // abort | IO_MSG "open output file \"" | name | "\"" | nl | strerror( errno );
    130130        } // if
    131         #endif // __CFA_DEBUG__
     131        // #endif // __CFA_DEBUG__
    132132        (os){ file };
    133133} // open
     
    262262void open( ifstream & is, const char name[], const char mode[] ) {
    263263        FILE * file = fopen( name, mode );
    264         #ifdef __CFA_DEBUG__
     264        // #ifdef __CFA_DEBUG__
    265265        if ( file == 0p ) {
    266266                throw (Open_Failure){ is };
    267267                // abort | IO_MSG "open input file \"" | name | "\"" | nl | strerror( errno );
    268268        } // if
    269         #endif // __CFA_DEBUG__
     269        // #endif // __CFA_DEBUG__
    270270        is.file$ = file;
    271271} // open
  • libcfa/src/heap.cfa

    rdd1cc02 r5a40e4e  
    1010// Created On       : Tue Dec 19 21:58:35 2017
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sat May 22 08:46:39 2021
    13 // Update Count     : 1036
     12// Last Modified On : Mon Aug  9 19:03:02 2021
     13// Update Count     : 1040
    1414//
    1515
     
    102102} // prtUnfreed
    103103
     104extern int cfa_main_returned;                                                   // from bootloader.cf
    104105extern "C" {
    105106        void heapAppStart() {                                                           // called by __cfaabi_appready_startup
     
    109110        void heapAppStop() {                                                            // called by __cfaabi_appready_startdown
    110111                fclose( stdin ); fclose( stdout );
    111                 prtUnfreed();
     112                if ( cfa_main_returned ) prtUnfreed();                  // do not check unfreed storage if exit called
    112113        } // heapAppStop
    113114} // extern "C"
  • libcfa/src/memory.cfa

    rdd1cc02 r5a40e4e  
    155155
    156156forall(T &)
     157T * release(unique_ptr(T) & this) {
     158        T * data = this.data;
     159        this.data = 0p;
     160        return data;
     161}
     162
     163forall(T &)
    157164int ?==?(unique_ptr(T) const & this, unique_ptr(T) const & that) {
    158165        return this.data == that.data;
  • libcfa/src/memory.hfa

    rdd1cc02 r5a40e4e  
    9494
    9595forall(T &)
     96T * release(unique_ptr(T) & this);
     97
     98forall(T &)
    9699int ?==?(unique_ptr(T) const & this, unique_ptr(T) const & that);
    97100forall(T &)
  • src/AST/Convert.cpp

    rdd1cc02 r5a40e4e  
    606606        }
    607607
     608        const ast::Stmt * visit( const ast::MutexStmt * node ) override final {
     609                if ( inCache( node ) ) return nullptr;
     610                 auto stmt = new MutexStmt(
     611                        get<Statement>().accept1( node->stmt ),
     612                        get<Expression>().acceptL( node->mutexObjs )
     613                );
     614                return stmtPostamble( stmt, node );
     615        }
     616
    608617        TypeSubstitution * convertTypeSubstitution(const ast::TypeSubstitution * src) {
    609618
     
    21242133        }
    21252134
     2135        virtual void visit( const MutexStmt * old ) override final {
     2136                if ( inCache( old ) ) return;
     2137                this->node = new ast::MutexStmt(
     2138                        old->location,
     2139                        GET_ACCEPT_1(stmt, Stmt),
     2140                        GET_ACCEPT_V(mutexObjs, Expr)
     2141                );
     2142                cache.emplace( old, this->node );
     2143        }
     2144
    21262145        // TypeSubstitution shouldn't exist yet in old.
    21272146        ast::TypeSubstitution * convertTypeSubstitution(const TypeSubstitution * old) {
  • src/AST/Fwd.hpp

    rdd1cc02 r5a40e4e  
    6060class NullStmt;
    6161class ImplicitCtorDtorStmt;
     62class MutexStmt;
    6263
    6364class Expr;
  • src/AST/Node.cpp

    rdd1cc02 r5a40e4e  
    176176template class ast::ptr_base< ast::ImplicitCtorDtorStmt, ast::Node::ref_type::weak >;
    177177</