Changeset eaeca5f


Ignore:
Timestamp:
Aug 29, 2021, 11:46:13 AM (5 months ago)
Author:
Andrew Beach <ajbeach@…>
Branches:
jacob/cs343-translation, master
Children:
75f8e04
Parents:
1d402be (diff), cfbab07 (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 'andrew-mmath' into 'master', latest round of updates to the thesis.

Location:
doc/theses/andrew_beach_MMath
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/andrew_beach_MMath/conclusion.tex

    r1d402be reaeca5f  
    11\chapter{Conclusion}
     2\label{c:conclusion}
    23% Just a little knot to tie the paper together.
    34
    4 In the previous chapters this thesis presents the design and implementation of
    5 \CFA's EHM.  Both the design and implementation are based off of tools and
     5In the previous chapters this thesis presents the design and implementation
     6of \CFA's exception handling mechanism (EHM).
     7Both the design and implementation are based off of tools and
    68techniques developed for other programming languages but they were adapted to
    7 better fit \CFA's feature set and add a few features that do not exist in other
    8 EHMs, like conditional catch, default handlers, implicitly changing resumption
    9 into termination in the resumption default handler, and cancellation through
    10 coroutines and threads back to program main.
     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.
    1113
    1214The resulting features cover all of the major use cases of the most popular
     
    1517such as virtuals independent of traditional objects.
    1618
    17 The implementation has been tested through a set of small but interesting micro-benchmarks
    18 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.
    1923The results, while not cutting edge, are good enough for prototyping, which
    2024is \CFA's current stage of development.
    2125
    22 This initial EHM is a valuable new feature for \CFA in its own right but also serves
    23 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/existing.tex

    r1d402be reaeca5f  
    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.
     227\todo{cite Aaron's thesis (maybe)}
     228
     229To avoid typing long lists of assertions, constraints can be collected into
     230convenient a package called a @trait@, which can then be used in an assertion
    232231instead of the individual constraints.
    233232\begin{cfa}
     
    253252        node(T) * next;
    254253        T * data;
    255 }
     254};
    256255node(int) inode;
    257256\end{cfa}
     
    293292};
    294293CountUp countup;
    295 for (10) sout | resume(countup).next; // print 10 values
    296294\end{cfa}
    297295Each coroutine has a @main@ function, which takes a reference to a coroutine
    298296object and returns @void@.
    299297%[numbers=left] Why numbers on this one?
    300 \begin{cfa}[numbers=left,numberstyle=\scriptsize\sf]
     298\begin{cfa}
    301299void main(CountUp & this) {
    302         for (unsigned int up = 0;; ++up) {
    303                 this.next = up;
     300        for (unsigned int next = 0 ; true ; ++next) {
     301                this.next = next;
    304302                suspend;$\label{suspend}$
    305303        }
     
    307305\end{cfa}
    308306In 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).
     307@suspend@ statement is used to return execution to the coroutine's caller
     308without terminating the coroutine's function.
    311309
    312310A coroutine is resumed by calling the @resume@ function, \eg @resume(countup)@.
    313311The first resume calls the @main@ function at the top. Thereafter, resume calls
    314312continue 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@.
     313statement. In this case there is only one and, hence, the difference between
     314subsequent calls is the state of variables inside the function and the
     315coroutine object.
     316The return value of @resume@ is a reference to the coroutine, to make it
     317convent to access fields of the coroutine in the same expression.
     318Here is a simple example in a helper function:
     319\begin{cfa}
     320unsigned int get_next(CountUp & this) {
     321        return resume(this).next;
     322}
     323\end{cfa}
     324
     325When the main function returns the coroutine halts and can no longer be
     326resumed.
    321327
    322328\subsection{Monitor and Mutex Parameter}
     
    330336exclusion on a monitor object by qualifying an object reference parameter with
    331337@mutex@.
    332 \begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
    333 void example(MonitorA & @mutex@ argA, MonitorB & @mutex@ argB);
    334 \end{lstlisting}
     338\begin{cfa}
     339void example(MonitorA & mutex argA, MonitorB & mutex argB);
     340\end{cfa}
    335341When the function is called, it implicitly acquires the monitor lock for all of
    336342the mutex parameters without deadlock.  This semantics means all functions with
     
    362368{
    363369        StringWorker stringworker; // fork thread running in "main"
    364 } // implicitly join with thread / wait for completion
     370} // Implicit call to join(stringworker), waits for completion.
    365371\end{cfa}
    366372The thread main is where a new thread starts execution after a fork operation
  • doc/theses/andrew_beach_MMath/features.tex

    r1d402be reaeca5f  
    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}
    132 \label{s:Virtuals}
     130\label{s:virtuals}
    133131Virtual types and casts are not part of \CFA's EHM nor are they required for
    134132an EHM.
    135133However, one of the best ways to support an exception hierarchy
    136134is via a virtual hierarchy and dispatch system.
    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 For example, the following hypothetical syntax creates two virtual-type trees.
    152 \begin{flushleft}
    153 \lstDeleteShortInline@
    154 \begin{tabular}{@{\hspace{20pt}}l@{\hspace{20pt}}l}
    155 \begin{cfa}
    156 vtype V0, V1(V0), V2(V0);
    157 vtype W0, W1(W0), W2(W1);
    158 \end{cfa}
    159 &
    160 \raisebox{-0.6\totalheight}{\input{vtable}}
    161 \end{tabular}
    162 \lstMakeShortInline@
    163 \end{flushleft}
    164150% A type's ancestors are its parent and its parent's ancestors.
    165151% The root type has no ancestors.
    166152% A type's descendants are its children and its children's descendants.
    167 Every virtual type (tree node) has a pointer to a virtual table with a unique
    168 @Id@ and a list of virtual members (see \autoref{s:VirtualSystem} for
    169 details). Children inherit their parent's list of virtual members but may add
    170 and/or replace members.  For example,
    171 \begin{cfa}
    172 vtable W0 | { int ?<?( int, int ); int ?+?( int, int ); }
    173 vtable W1 | { int ?+?( int, int ); int w, int ?-?( int, int ); }
    174 \end{cfa}
    175 creates a virtual table for @W0@ initialized with the matching @<@ and @+@
    176 operations visible at this declaration context.  Similarly, @W1@ is initialized
    177 with @<@ from inheritance with @W0@, @+@ is replaced, and @-@ is added, where
    178 both operations are matched at this declaration context. It is important to
    179 note that these are virtual members, not virtual methods of object-orientated
    180 programming, and can be of any type. Finally, trait names can be used to
    181 specify the list of virtual members.
    182 
    183 \PAB{Need to look at these when done.
    184 
    185 \CFA still supports virtual methods as a special case of virtual members.
    186 Function pointers that take a pointer to the virtual type are modified
    187 with each level of inheritance so that refers to the new type.
    188 This means an object can always be passed to a function in its virtual table
    189 as if it were a method.
    190 \todo{Clarify (with an example) virtual methods.}
    191 }%
     153
     154For the purposes of illistration, a proposed -- but unimplemented syntax --
     155will be used. Each virtual type is repersented 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\begin{cfa}
     165trait child_a(T) virtual(root_type) {}
     166trait grandchild(T) virtual(child_a) {}
     167trait child_b(T) virtual(root_type) {}
     168\end{cfa}
     169\todo{Update the diagram in vtable.fig to show the new type tree.}
     170
     171Every virtual type also has a list of virtual members and a unique id,
     172both are stored in a virtual table.
     173Every instance of a virtual type also has a pointer to a virtual table stored
     174in it, although there is no per-type virtual table as in many other languages.
     175
     176The list of virtual members is built up down the tree. Every virtual type
     177inherits the list of virtual members from its parent and may add more
     178virtual members to the end of the list which are passed on to its children.
     179Again, using the unimplemented syntax this might look like:
     180\begin{cfa}
     181trait root_type(T) virtual() {
     182        const char * to_string(T const & this);
     183        unsigned int size;
     184}
     185
     186trait child_type(T) virtual(root_type) {
     187        char * irrelevant_function(int, char);
     188}
     189\end{cfa}
     190% Consider adding a diagram, but we might be good with the explanation.
     191
     192As @child_type@ is a child of @root_type@ it has the virtual members of
     193@root_type@ (@to_string@ and @size@) as well as the one it declared
     194(@irrelivant_function@).
     195
     196It is important to note that these are virtual members, and may contain   
     197arbitrary fields, functions or otherwise.
     198The names ``size" and ``align" are reserved for the size and alignment of the
     199virtual type, and are always automatically initialized as such.
     200The other special case are uses of the trait's polymorphic argument
     201(@T@ in the example), which are always updated to refer to the current
     202virtual type. This allows functions that refer to to polymorphic argument
     203to act as traditional virtual methods (@to_string@ in the example), as the
     204object can always be passed to a virtual method in its virtual table.
    192205
    193206Up until this point the virtual system is similar to ones found in
    194 object-orientated languages but this is where \CFA diverges. Objects encapsulate a
    195 single set of methods in each type, universally across the entire program,
    196 and indeed all programs that use that type definition. Even if a type inherits and adds methods, it still encapsulate a
    197 single set of methods. In this sense,
    198 object-oriented types are ``closed" and cannot be altered.
    199 
    200 In \CFA, types do not encapsulate any code. Traits are local for each function and
    201 types can satisfy a local trait, stop satisfying it or, satisfy the same
    202 trait in a different way at any lexical location in the program where a function is call.
    203 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.
     207object-oriented languages but this is where \CFA diverges.
     208Objects encapsulate a single set of methods in each type,
     209universally across the entire program,
     210and indeed all programs that use that type definition.
     211The only way to change any method is to inherit and define a new type with
     212its own universal implementation. In this sense,
     213these object-oriented types are ``closed" and cannot be altered.
     214% Because really they are class oriented.
     215
     216In \CFA, types do not encapsulate any code.
     217Whether or not satisfies any given assertion, and hence any trait, is
     218context sensitive. Types can begin to satisfy a trait, stop satisfying it or
     219satisfy the same trait at any lexical location in the program.
     220In this sense, an type's implementation in the set of functions and variables
     221that allow it to satisfy a trait is ``open" and can change
     222throughout the program.
    204223This capability means it is impossible to pick a single set of functions
    205224that represent a type's implementation across a program.
     
    208227type. A user can define virtual tables that are filled in at their
    209228declaration and given a name. Anywhere that name is visible, even if it is
    210 defined locally inside a function \PAB{What does this mean? (although that means it does not have a
    211 static lifetime)}, it can be used.
     229defined locally inside a function (although in this case the user must ensure
     230it outlives any objects that use it), it can be used.
    212231Specifically, a virtual type is ``bound" to a virtual table that
    213232sets the virtual members for that object. The virtual members can be accessed
    214233through the object.
     234
     235This means virtual tables are declared and named in \CFA.
     236They are declared as variables, using the type
     237@vtable(VIRTUAL_TYPE)@ and any valid name. For example:
     238\begin{cfa}
     239vtable(virtual_type_name) table_name;
     240\end{cfa}
     241
     242Like any variable they may be forward declared with the @extern@ keyword.
     243Forward declaring virtual tables is relatively common.
     244Many virtual types have an ``obvious" implementation that works in most
     245cases.
     246A pattern that has appeared in the early work using virtuals is to
     247implement a virtual table with the the obvious definition and place a forward
     248declaration of it in the header beside the definition of the virtual type.
     249
     250Even on the full declaration, no initializer should be used.
     251Initialization is automatic.
     252The type id and special virtual members ``size" and ``align" only depend on
     253the virtual type, which is fixed given the type of the virtual table and
     254so the compiler fills in a fixed value.
     255The other virtual members are resolved, using the best match to the member's
     256name and type, in the same context as the virtual table is declared using
     257\CFA's normal resolution rules.
    215258
    216259While much of the virtual infrastructure is created, it is currently only used
     
    228271@EXPRESSION@ object, otherwise it returns @0p@ (null pointer).
    229272
    230 \section{Exception}
    231 % Leaving until later, hopefully it can talk about actual syntax instead
    232 % of my many strange macros. Syntax aside I will also have to talk about the
    233 % features all exceptions support.
    234 
    235 Exceptions are defined by the trait system; there are a series of traits, and
     273\section{Exceptions}
     274
     275The syntax for declaring an exception is the same as declaring a structure
     276except the keyword that is swapped out:
     277\begin{cfa}
     278exception TYPE_NAME {
     279        FIELDS
     280};
     281\end{cfa}
     282
     283Fields are filled in the same way as a structure as well. However an extra
     284field is added, this field contains the pointer to the virtual table.
     285It must be explicitly initialised by the user when the exception is
     286constructed.
     287
     288Here is an example of declaring an exception type along with a virtual table,
     289assuming the exception has an ``obvious" implementation and a default
     290virtual table makes sense.
     291
     292\begin{minipage}[t]{0.4\textwidth}
     293Header:
     294\begin{cfa}
     295exception Example {
     296        int data;
     297};
     298
     299extern vtable(Example)
     300        example_base_vtable;
     301\end{cfa}
     302\end{minipage}
     303\begin{minipage}[t]{0.6\textwidth}
     304Source:
     305\begin{cfa}
     306vtable(Example) example_base_vtable
     307\end{cfa}
     308\vfil
     309\end{minipage}
     310
     311%\subsection{Exception Details}
     312If one is only raising and handling exceptions, that is the only interface
     313that is needed. However it is actually a short hand for a more complex
     314trait based interface.
     315
     316The language views exceptions through a series of traits,
    236317if a type satisfies them, then it can be used as an exception. The following
    237318is the base trait all exceptions need to match.
     
    247328completing the virtual system). The imaginary assertions would probably come
    248329from a trait defined by the virtual system, and state that the exception type
    249 is a virtual type, is a descendant of @exception_t@ (the base exception type),
    250 and note its virtual table type.
     330is a virtual type, is a descendant of @exception_t@ (the base exception type)
     331and allow the user to find the virtual table type.
    251332
    252333% I did have a note about how it is the programmer's responsibility to make
     
    267348\end{cfa}
    268349Both traits ensure a pair of types are an exception type, its virtual table
    269 type,
     350type
    270351and defines one of the two default handlers. The default handlers are used
    271352as fallbacks and are discussed in detail in \vref{s:ExceptionHandling}.
     
    276357facing way. So these three macros are provided to wrap these traits to
    277358simplify referring to the names:
    278 @IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@, and @IS_RESUMPTION_EXCEPTION@.
     359@IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@ and @IS_RESUMPTION_EXCEPTION@.
    279360
    280361All three take one or two arguments. The first argument is the name of the
     
    299380These twin operations are the core of \CFA's exception handling mechanism.
    300381This section covers the general patterns shared by the two operations and
    301 then goes on to cover the details of each individual operation.
     382then goes on to cover the details each individual operation.
    302383
    303384Both operations follow the same set of steps.
    304385First, a user raises an exception.
    305 Second, the exception propagates up the stack.
     386Second, the exception propagates up the stack, searching for a handler.
    306387Third, if a handler is found, the exception is caught and the handler is run.
    307388After that control continues at a raise-dependent location.
    308 Fourth, if a handler is not found, a default handler is run and, if it returns, then control
     389As an alternate to the third step,
     390if a handler is not found, a default handler is run and, if it returns,
     391then control
    309392continues after the raise.
    310393
    311 %This general description covers what the two kinds have in common.
    312 The differences in the two operations include how propagation is performed, where execution continues
    313 after an exception is caught and handled, and which default handler is run.
     394The differences between the two operations include how propagation is
     395performed, where excecution after an exception is handler
     396and which default handler is run.
    314397
    315398\subsection{Termination}
    316399\label{s:Termination}
    317 Termination handling is the familiar EHM and used in most programming
     400Termination handling is the familiar kind of handling
     401and used in most programming
    318402languages with exception handling.
    319403It is a dynamic, non-local goto. If the raised exception is matched and
     
    347431Then propagation starts with the search. \CFA uses a ``first match" rule so
    348432matching is performed with the copied exception as the search key.
    349 It starts from the raise in the throwing function and proceeds towards the base of the stack,
     433It starts from the raise site and proceeds towards base of the stack,
    350434from callee to caller.
    351435At each stack frame, a check is made for termination handlers defined by the
     
    361445\end{cfa}
    362446When viewed on its own, a try statement simply executes the statements
    363 in the \snake{GUARDED_BLOCK}, and when those are finished,
     447in the \snake{GUARDED_BLOCK} and when those are finished,
    364448the try statement finishes.
    365449
     
    387471termination exception types.
    388472The global default termination handler performs a cancellation
    389 (see \vref{s:Cancellation} for the justification) on the current stack with the copied exception.
    390 Since it is so general, a more specific handler is usually
    391 defined, possibly with a detailed message, and used for specific exception type, effectively overriding the default handler.
     473(as described in \vref{s:Cancellation})
     474on the current stack with the copied exception.
     475Since it is so general, a more specific handler can be defined,
     476overriding the default behaviour for the specific exception types.
    392477
    393478\subsection{Resumption}
    394479\label{s:Resumption}
    395480
    396 Resumption exception handling is the less familar EHM, but is
     481Resumption exception handling is less familar form of exception handling,
     482but is
    397483just as old~\cite{Goodenough75} and is simpler in many ways.
    398484It is a dynamic, non-local function call. If the raised exception is
     
    403489function once the error is corrected, and
    404490ignorable events, such as logging where nothing needs to happen and control
    405 should always continue from the raise point.
     491should always continue from the raise site.
     492
     493Except for the changes to fit into that pattern, resumption exception
     494handling is symmetric with termination exception handling, by design
     495(see \autoref{s:Termination}).
    406496
    407497A resumption raise is started with the @throwResume@ statement:
     
    410500\end{cfa}
    411501\todo{Decide on a final set of keywords and use them everywhere.}
    412 It works much the same way as the termination throw.
    413 The expression must return a reference to a resumption exception,
    414 where the resumption exception is any type that satisfies the trait
    415 @is_resumption_exception@ at the call site.
    416 The assertions from this trait are available to
    417 the exception system while handling the exception.
    418 
    419 At run-time, no exception copy is made, since
     502It works much the same way as the termination raise, except the
     503type must satisfy the \snake{is_resumption_exception} that uses the
     504default handler: \defaultResumptionHandler.
     505This can be specialized for particular exception types.
     506
     507At run-time, no exception copy is made. Since
    420508resumption does not unwind the stack nor otherwise remove values from the
    421 current scope, so there is no need to manage memory to keep the exception in scope.
    422 
    423 Then propagation starts with the search. It starts from the raise in the
    424 resuming function and proceeds towards the base of the stack,
    425 from callee to caller.
    426 At each stack frame, a check is made for resumption handlers defined by the
    427 @catchResume@ clauses of a @try@ statement.
     509current scope, there is no need to manage memory to keep the exception
     510allocated.
     511
     512Then propagation starts with the search,
     513following the same search path as termination,
     514from the raise site to the base of stack and top of try statement to bottom.
     515However, the handlers on try statements are defined by @catchResume@ clauses.
    428516\begin{cfa}
    429517try {
     
    435523}
    436524\end{cfa}
    437 % PAB, you say this above.
    438 % When a try statement is executed, it simply executes the statements in the
    439 % @GUARDED_BLOCK@ and then finishes.
    440 %
    441 % However, while the guarded statements are being executed, including any
    442 % invoked functions, all the handlers in these statements are included in the
    443 % search path.
    444 % Hence, if a resumption exception is raised, these handlers may be matched
    445 % against the exception and may handle it.
    446 %
    447 % Exception matching checks the handler in each catch clause in the order
    448 % they appear, top to bottom. If the representation of the raised exception type
    449 % is the same or a descendant of @EXCEPTION_TYPE@$_i$, then @NAME@$_i$
    450 % (if provided) is bound to a pointer to the exception and the statements in
    451 % @HANDLER_BLOCK@$_i$ are executed.
    452 % If control reaches the end of the handler, execution continues after the
    453 % the raise statement that raised the handled exception.
    454 %
    455 % Like termination, if no resumption handler is found during the search,
    456 % then the default handler (\defaultResumptionHandler) visible at the raise
    457 % statement is called. It will use the best match at the raise sight according
    458 % to \CFA's overloading rules. The default handler is
    459 % passed the exception given to the raise. When the default handler finishes
    460 % execution continues after the raise statement.
    461 %
    462 % There is a global @defaultResumptionHandler{} is polymorphic over all
    463 % resumption exceptions and performs a termination throw on the exception.
    464 % The \defaultTerminationHandler{} can be overridden by providing a new
    465 % function that is a better match.
    466 
    467 The @GUARDED_BLOCK@ and its associated nested guarded statements work the same
    468 for resumption as for termination, as does exception matching at each
    469 @catchResume@. Similarly, if no resumption handler is found during the search,
    470 then the currently visible default handler (\defaultResumptionHandler) is
    471 called and control continues after the raise statement if it returns. Finally,
    472 there is also a global @defaultResumptionHandler@, which can be overridden,
    473 that is polymorphic over all resumption exceptions but performs a termination
    474 throw on the exception rather than a cancellation.
    475 
    476 Throwing the exception in @defaultResumptionHandler@ has the positive effect of
    477 walking the stack a second time for a recovery handler. Hence, a programmer has
    478 two chances for help with a problem, fixup or recovery, should either kind of
    479 handler appear on the stack. However, this dual stack walk leads to following
    480 apparent anomaly:
    481 \begin{cfa}
    482 try {
    483         throwResume E;
    484 } catch (E) {
    485         // this handler runs
    486 }
    487 \end{cfa}
    488 because the @catch@ appears to handle a @throwResume@, but a @throwResume@ only
    489 matches with @catchResume@. The anomaly results because the unmatched
    490 @catchResuem@, calls @defaultResumptionHandler@, which in turn throws @E@.
    491 
    492 % I wonder if there would be some good central place for this.
    493 Note, termination and resumption handlers may be used together
     525Note that termination handlers and resumption handlers may be used together
    494526in a single try statement, intermixing @catch@ and @catchResume@ freely.
    495527Each type of handler only interacts with exceptions from the matching
    496528kind of raise.
     529Like @catch@ clauses, @catchResume@ clauses have no effect if an exception
     530is not raised.
     531
     532The matching rules are exactly the same as well.
     533The first major difference here is that after
     534@EXCEPTION_TYPE@$_i$ is matched and @NAME@$_i$ is bound to the exception,
     535@HANDLER_BLOCK@$_i$ is executed right away without first unwinding the stack.
     536After the block has finished running control jumps to the raise site, where
     537the just handled exception came from, and continues executing after it,
     538not after the try statement.
    497539
    498540\subsubsection{Resumption Marking}
     
    502544and run, its try block (the guarded statements) and every try statement
    503545searched before it are still on the stack. There presence can lead to
    504 the \emph{recursive resumption problem}.
     546the recursive resumption problem.
     547\todo{Is there a citation for the recursive resumption problem?}
    505548
    506549The recursive resumption problem is any situation where a resumption handler
     
    516559When this code is executed, the guarded @throwResume@ starts a
    517560search and matches the handler in the @catchResume@ clause. This
    518 call is placed on the stack above the try-block. Now the second raise in the handler
    519 searches the same try block, matches, and puts another instance of the
     561call is placed on the stack above the try-block.
     562Now the second raise in the handler searches the same try block,
     563matches again and then puts another instance of the
    520564same handler on the stack leading to infinite recursion.
    521565
    522 While this situation is trivial and easy to avoid, much more complex cycles can
    523 form with multiple handlers and different exception types.  The key point is
    524 that the programmer's intuition expects every raise in a handler to start
    525 searching \emph{below} the @try@ statement, making it difficult to understand
    526 and fix the problem.
    527 
     566While this situation is trivial and easy to avoid, much more complex cycles
     567can form with multiple handlers and different exception types.
    528568To prevent all of these cases, each try statement is ``marked" from the
    529 time the exception search reaches it to either when a matching handler
    530 completes or when the search reaches the base
     569time the exception search reaches it to either when a handler completes
     570handling that exception or when the search reaches the base
    531571of the stack.
    532572While a try statement is marked, its handlers are never matched, effectively
     
    540580for instance, marking just the handlers that caught the exception,
    541581would also prevent recursive resumption.
    542 However, the rule selected mirrors what happens with termination,
    543 and hence, matches programmer intuition that a raise searches below a try.
    544 
    545 In detail, the marked try statements are the ones that would be removed from
     582However, the rules selected mirrors what happens with termination,
     583so this reduces the amount of rules and patterns a programmer has to know.
     584
     585The marked try statements are the ones that would be removed from
    546586the stack for a termination exception, \ie those on the stack
    547587between the handler and the raise statement.
     
    609649
    610650\subsection{Comparison with Reraising}
    611 Without conditional catch, the only approach to match in more detail is to reraise
    612 the exception after it has been caught, if it could not be handled.
     651In languages without conditional catch, that is no ability to match an
     652exception based on something other than its type, it can be mimicked
     653by matching all exceptions of the right type, checking any additional
     654conditions inside the handler and re-raising the exception if it does not
     655match those.
     656
     657Here is a minimal example comparing both patterns, using @throw;@
     658(no argument) to start a re-raise.
    613659\begin{center}
    614 \begin{tabular}{l|l}
     660\begin{tabular}{l r}
    615661\begin{cfa}
    616662try {
    617         do_work_may_throw();
    618 } catch(excep_t * ex; can_handle(ex)) {
    619 
    620         handle(ex);
    621 
    622 
    623 
    624 }
     663    do_work_may_throw();
     664} catch(exception_t * exc ;
     665                can_handle(exc)) {
     666    handle(exc);
     667}
     668
     669
     670
    625671\end{cfa}
    626672&
    627673\begin{cfa}
    628674try {
    629         do_work_may_throw();
    630 } catch(excep_t * ex) {
    631         if (can_handle(ex)) {
    632                 handle(ex);
     675    do_work_may_throw();
     676} catch(exception_t * exc) {
     677    if (can_handle(exc)) {
     678        handle(exc);
     679    } else {
     680        throw;
     681    }
     682}
     683\end{cfa}
     684\end{tabular}
     685\end{center}
     686At first glance catch-and-reraise may appear to just be a quality of life
     687feature, but there are some significant differences between the two
     688stratagies.
     689
     690A simple difference that is more important for \CFA than many other languages
     691is that the raise site changes, with a re-raise but does not with a
     692conditional catch.
     693This is important in \CFA because control returns to the raise site to run
     694the per-site default handler. Because of this only a conditional catch can
     695allow the original raise to continue.
     696
     697The more complex issue comes from the difference in how conditional
     698catches and re-raises handle multiple handlers attached to a single try
     699statement. A conditional catch will continue checking later handlers while
     700a re-raise will skip them.
     701If the different handlers could handle some of the same exceptions,
     702translating a try statement that uses one to use the other can quickly
     703become non-trivial:
     704
     705\noindent
     706Original, with conditional catch:
     707\begin{cfa}
     708...
     709} catch (an_exception * e ; check_a(e)) {
     710        handle_a(e);
     711} catch (exception_t * e ; check_b(e)) {
     712        handle_b(e);
     713}
     714\end{cfa}
     715Translated, with re-raise:
     716\begin{cfa}
     717...
     718} catch (exception_t * e) {
     719        an_exception * an_e = (virtual an_exception *)e;
     720        if (an_e && check_a(an_e)) {
     721                handle_a(an_e);
     722        } else if (check_b(e)) {
     723                handle_b(e);
    633724        } else {
    634725                throw;
     
    636727}
    637728\end{cfa}
    638 \end{tabular}
    639 \end{center}
    640 Notice catch-and-reraise increases complexity by adding additional data and
    641 code to the exception process. Nevertheless, catch-and-reraise can simulate
    642 conditional catch straightforwardly, when exceptions are disjoint, \ie no
    643 inheritance.
    644 
    645 However, catch-and-reraise simulation becomes unusable for exception inheritance.
    646 \begin{flushleft}
    647 \begin{cfa}[xleftmargin=6pt]
    648 exception E1;
    649 exception E2(E1); // inheritance
    650 \end{cfa}
    651 \begin{tabular}{l|l}
    652 \begin{cfa}
    653 try {
    654         ... foo(); ... // raise E1/E2
    655         ... bar(); ... // raise E1/E2
    656 } catch( E2 e; e.rtn == foo ) {
    657         ...
    658 } catch( E1 e; e.rtn == foo ) {
    659         ...
    660 } catch( E1 e; e.rtn == bar ) {
    661         ...
    662 }
    663 
    664 \end{cfa}
    665 &
    666 \begin{cfa}
    667 try {
    668         ... foo(); ...
    669         ... bar(); ...
    670 } catch( E2 e ) {
    671         if ( e.rtn == foo ) { ...
    672         } else throw; // reraise
    673 } catch( E1 e ) {
    674         if (e.rtn == foo) { ...
    675         } else if (e.rtn == bar) { ...
    676         else throw; // reraise
    677 }
    678 \end{cfa}
    679 \end{tabular}
    680 \end{flushleft}
    681 The derived exception @E2@ must be ordered first in the catch list, otherwise
    682 the base exception @E1@ catches both exceptions. In the catch-and-reraise code
    683 (right), the @E2@ handler catches exceptions from both @foo@ and
    684 @bar@. However, the reraise misses the following catch clause. To fix this
    685 problem, an enclosing @try@ statement is need to catch @E2@ for @bar@ from the
    686 reraise, and its handler must duplicate the inner handler code for @bar@. To
    687 generalize, this fix for any amount of inheritance and complexity of try
    688 statement requires a technique called \emph{try-block
    689 splitting}~\cite{Krischer02}, which is not discussed in this thesis. It is
    690 sufficient to state that conditional catch is more expressive than
    691 catch-and-reraise in terms of complexity.
    692 
    693 \begin{comment}
    694 That is, they have the same behaviour in isolation.
    695 Two things can expose differences between these cases.
    696 
    697 One is the existence of multiple handlers on a single try statement.
    698 A reraise skips all later handlers for a try statement but a conditional
    699 catch does not.
    700 % Hence, if an earlier handler contains a reraise later handlers are
    701 % implicitly skipped, with a conditional catch they are not.
    702 Still, they are equivalently powerful,
    703 both can be used two mimic the behaviour of the other,
    704 as reraise can pack arbitrary code in the handler and conditional catches
    705 can put arbitrary code in the predicate.
    706 % I was struggling with a long explanation about some simple solutions,
    707 % like repeating a condition on later handlers, and the general solution of
    708 % merging everything together. I don't think it is useful though unless its
    709 % for a proof.
    710 % https://en.cppreference.com/w/cpp/language/throw
    711 
    712 The question then becomes ``Which is a better default?"
    713 We believe that not skipping possibly useful handlers is a better default.
    714 If a handler can handle an exception it should and if the handler can not
    715 handle the exception then it is probably safer to have that explicitly
    716 described in the handler itself instead of implicitly described by its
    717 ordering with other handlers.
    718 % Or you could just alter the semantics of the throw statement. The handler
    719 % index is in the exception so you could use it to know where to start
    720 % searching from in the current try statement.
    721 % No place for the `goto else;` metaphor.
    722 
    723 The other issue is all of the discussion above assumes that the only
    724 way to tell apart two raises is the exception being raised and the remaining
    725 search path.
    726 This is not true generally, the current state of the stack can matter in
    727 a number of cases, even only for a stack trace after an program abort.
    728 But \CFA has a much more significant need of the rest of the stack, the
    729 default handlers for both termination and resumption.
    730 
    731 % For resumption it turns out it is possible continue a raise after the
    732 % exception has been caught, as if it hadn't been caught in the first place.
    733 This becomes a problem combined with the stack unwinding used in termination
    734 exception handling.
    735 The stack is unwound before the handler is installed, and hence before any
    736 reraises can run. So if a reraise happens the previous stack is gone,
    737 the place on the stack where the default handler was supposed to run is gone,
    738 if the default handler was a local function it may have been unwound too.
    739 There is no reasonable way to restore that information, so the reraise has
    740 to be considered as a new raise.
    741 This is the strongest advantage conditional catches have over reraising,
    742 they happen before stack unwinding and avoid this problem.
    743 
    744 % The one possible disadvantage of conditional catch is that it runs user
    745 % code during the exception search. While this is a new place that user code
    746 % can be run destructors and finally clauses are already run during the stack
    747 % unwinding.
     729(There is a simpler solution if @handle_a@ never raises exceptions,
     730using nested try statements.)
     731
     732% } catch (an_exception * e ; check_a(e)) {
     733%     handle_a(e);
     734% } catch (exception_t * e ; !(virtual an_exception *)e && check_b(e)) {
     735%     handle_b(e);
     736% }
    748737%
    749 % https://www.cplusplus.com/reference/exception/current_exception/
    750 %   `exception_ptr current_exception() noexcept;`
    751 % https://www.python.org/dev/peps/pep-0343/
    752 \end{comment}
     738% } catch (an_exception * e)
     739%   if (check_a(e)) {
     740%     handle_a(e);
     741%   } else throw;
     742% } catch (exception_t * e)
     743%   if (check_b(e)) {
     744%     handle_b(e);
     745%   } else throw;
     746% }
     747In similar simple examples translating from re-raise to conditional catch
     748takes less code but it does not have a general trivial solution either.
     749
     750So, given that the two patterns do not trivially translate into each other,
     751it becomes a matter of which on should be encouraged and made the default.
     752From the premise that if a handler that could handle an exception then it
     753should, it follows that checking as many handlers as possible is preferred.
     754So conditional catch and checking later handlers is a good default.
    753755
    754756\section{Finally Clauses}
     
    766768The @FINALLY_BLOCK@ is executed when the try statement is removed from the
    767769stack, including when the @GUARDED_BLOCK@ finishes, any termination handler
    768 finishes, or during an unwind.
     770finishes or during an unwind.
    769771The only time the block is not executed is if the program is exited before
    770772the stack is unwound.
     
    786788they have their own strengths, similar to top-level function and lambda
    787789functions with closures.
    788 Destructors take more work for their creation, but if there is clean-up code
     790Destructors take more work to create, but if there is clean-up code
    789791that needs to be run every time a type is used, they are much easier
    790 to set-up.
     792to set-up for each use. % It's automatic.
    791793On the other hand finally clauses capture the local context, so is easy to
    792794use when the clean-up is not dependent on the type of a variable or requires
     
    804806raise, this exception is not used in matching only to pass information about
    805807the cause of the cancellation.
    806 Finaly, since a cancellation only unwinds and forwards, there is no default handler.
     808Finally, as no handler is provided, there is no default handler.
    807809
    808810After @cancel_stack@ is called the exception is copied into the EHM's memory
     
    815817After the main stack is unwound there is a program-level abort.
    816818
    817 The reasons for this semantics in a sequential program is that there is no more code to execute.
    818 This semantics also applies to concurrent programs, too, even if threads are running.
    819 That is, if any threads starts a cancellation, it implies all threads terminate.
    820 Keeping the same behaviour in sequential and concurrent programs is simple.
    821 Also, even in concurrent programs there may not currently be any other stacks
    822 and even if other stacks do exist, main has no way to know where they are.
     819The first reason for this behaviour is for sequential programs where there
     820is only one stack, and hence to stack to pass information to.
     821Second, even in concurrent programs, the main stack has no dependency
     822on another stack and no reliable way to find another living stack.
     823Finally, keeping the same behaviour in both sequential and concurrent
     824programs is simple and easy to understand.
    823825
    824826\paragraph{Thread Stack}
     
    850852
    851853With explicit join and a default handler that triggers a cancellation, it is
    852 possible to cascade an error across any number of threads, cleaning up each
     854possible to cascade an error across any number of threads,
     855alternating between the resumption (possibly termination) and cancellation,
     856cleaning up each
    853857in turn, until the error is handled or the main thread is reached.
    854858
     
    863867caller's context and passes it to the internal report.
    864868
    865 A coroutine only knows of two other coroutines, its starter and its last resumer.
     869A coroutine only knows of two other coroutines,
     870its starter and its last resumer.
    866871The starter has a much more distant connection, while the last resumer just
    867872(in terms of coroutine state) called resume on this coroutine, so the message
     
    869874
    870875With a default handler that triggers a cancellation, it is possible to
    871 cascade an error across any number of coroutines, cleaning up each in turn,
     876cascade an error across any number of coroutines,
     877alternating between the resumption (possibly termination) and cancellation,
     878cleaning up each in turn,
    872879until the error is handled or a thread stack is reached.
    873 
    874 \PAB{Part of this I do not understand. A cancellation cannot be caught. But you
    875 talk about handling a cancellation in the last sentence. Which is correct?}
  • doc/theses/andrew_beach_MMath/future.tex

    r1d402be reaeca5f  
    22\label{c:future}
    33
    4 The following discussion covers both missing language features that affected my
    5 work and research based improvements.
     4The following discussion covers both possible interesting research
     5that could follow from this work as long as simple implementation
     6improvements.
    67
    78\section{Language Improvements}
     
    910\CFA is a developing programming language. As such, there are partially or
    1011unimplemented features (including several broken components)
    11 that I had to workaround while building an EHM largely in
    12 the \CFA language (some C components).  The following are a few of these
    13 issues, and once implemented/fixed, how they would affect the exception system.
     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.
    1417\begin{itemize}
    15 \item
    16 The implementation of termination is not portable because it includes
    17 hand-crafted assembly statements for each architecture, where the
    18 ARM processor was just added.
    19 % The existing compilers cannot translate that for other platforms and those
    20 % sections must be ported by hand to
    21 Supporting more hardware architectures in a general way is important.
    2218\item
    2319Due to a type-system problem, the catch clause cannot bind the exception to a
     
    2925@return@, \etc. The reason is that current code generation hoists a handler
    3026into a nested function for convenience (versus assemble-code generation at the
    31 @try@ statement). Hence, when the handler runs, its can access local variable
    32 in the lexical scope of the @try@ statement, but the closure does not capture
    33 local control-flow points so it cannot perform non-local transfers in the
    34 hoisted function.
     27try statement). Hence, when the handler runs, it can still access local
     28variables in the lexical scope of the try statement. Still, it does mean
     29that seemingly local control flow is not in fact local and crosses a function
     30boundary.
     31Making the termination handlers code within the surrounding
     32function would remove this limitation.
     33% Try blocks are much more difficult to do practically (requires our own
     34% assembly) and resumption handlers have some theoretical complexity.
    3535\item
    3636There is no detection of colliding unwinds. It is possible for clean-up code
    3737run during an unwind to trigger another unwind that escapes the clean-up code
    3838itself; such as a termination exception caught further down the stack or a
    39 cancellation. There do exist ways to handle this case, but currently there is no
    40 detection and the first unwind is simply forgotten, often leaving
     39cancellation. There do exist ways to handle this case, but currently there is
     40no detection and the first unwind will simply be forgotten, often leaving
    4141it in a bad state.
    4242\item
    43 Finally, the exception system has not have a lot programmer testing.
     43Finally, the exception system has not had a lot of programmer testing.
    4444More time with encouraged usage will reveal new
    4545quality of life upgrades that can be made.
     
    5050project, but was thrust upon it to do exception inheritance; hence, only
    5151minimal work is done. A draft for a complete virtual system is available but
    52 not finalized.  A future \CFA project is to complete that work and then
     52not finalized. A future \CFA project is to complete that work and then
    5353update the exception system that uses the current version.
    5454
     
    6161types to allow traits to refer to types not listed in their header. This
    6262feature allows exception traits to not refer to the virtual-table type
    63 explicitly. %, removing the need for the current interface macros.
     63explicitly, removing the need for the current interface macros,
     64such as @EHM_IS_EXCEPTION@.
    6465
    6566\section{Additional Raises}
     
    7778Non-local/concurrent raise requires more
    7879coordination between the concurrency system
    79 and the exception system. Many of the interesting design decisions centre
     80and the exception system. Many of the interesting design decisions center
    8081around masking, \ie controlling which exceptions may be thrown at a stack. It
    8182would likely require more of the virtual system and would also effect how
     
    9798exception signature. An exception signature must declare all checked
    9899exceptions that could propagate from the function, either because they were
    99 raised inside the function or a call to a sub-function. This improves safety
     100raised inside the function or came from a sub-function. This improves safety
    100101by making sure every checked exception is either handled or consciously
    101102passed on.
     
    133134Workarounds are possible but awkward. Ideally an extension to libunwind could
    134135be made, but that would either require separate maintenance or gaining enough
    135 support to have it folded into the code base.
     136support to have it folded into the official library itself.
    136137
    137138Also new techniques to skip previously searched parts of the stack need to be
  • doc/theses/andrew_beach_MMath/implement.tex

    r1d402be reaeca5f  
    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 A virtual type~(see \autoref{s:Virtuals}) has a pointer to a virtual table,
    23 called the \emph{virtual-table pointer}, which binds an instance of a virtual
    24 type to a virtual table.  Internally, the field is called \snake{virtual_table}
    25 and is fixed after construction.  This pointer is also the table's id and how
    26 the system accesses the virtual table and the virtual members there. It is
    27 always the first field in the structure so that its location is always known.
    28 \todo{Talk about constructors for virtual types (after they are working).}
     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
     31structure so that its location is always known.
     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.
    2936
    3037\subsection{Type Id}
    31 Every virtual type needs a unique id, so that type ids can be compared for
    32 equality, which checks if the types representation are the same, or used to
    33 access the type's type information.  Here, uniqueness means within a program
    34 composed of multiple translation units (TU), not uniqueness across all
    35 programs.
    36 
    37 One approach for program uniqueness is declaring a static declaration for each
    38 type id, where the runtime storage address of that variable is guaranteed to be
    39 unique during program execution. The type id storage can also be used for other
    40 purposes.
     38Every virtual type has a unique id.
     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.
    4150
    4251The problem is that a type id may appear in multiple TUs that compose a
    43 program, see \autoref{ss:VirtualTable}; hence in each TU, it must be declared
    44 as external to prevent multiple definitions. However, the type id must actually
    45 be declared in one of the TUs so the linker creates the storage.  Hence, the
    46 problem becomes designating one TU to insert an actual type-id declaration. But
    47 the \CFA compiler does not know the set of the translation units that compose a
    48 program, because TUs can be compile separately, followed by a separate link
    49 step.
    50 
    51 The solution is to mimic a \CFA feature in \Cpp{17}, @inline@ variables and
    52 function:
    53 \begin{quote}
    54 There may be more than one definition of an inline function or variable (since
    55 \Cpp{17} in the program as long as each definition appears in a different
    56 translation unit and (for non-static inline functions and variables (since
    57 \Cpp{17})) all definitions are identical. For example, an inline function or an
    58 inline variable (since \Cpp{17}) may be defined in a header file that is
    59 @#include@'d in multiple source files.~\cite{C++17}
    60 \end{quote}
    61 The underlying mechanism to provide this capability is attribute
    62 \begin{cfa}
    63 section(".gnu.linkonce.NAME")
    64 \end{cfa}
    65 where @NAME@ is the variable/function name duplicated in each TU.  The linker than
    66 provides the service of generating a single declaration (instance) across all
    67 TUs, even if a program is linked incrementally.
    68 
    69 C does not support this feature for @inline@, and hence, neither does \CFA.
    70 Again, rather than implement a new @inline@ extension for \CFA, a temporary
    71 solution for the exception handling is to add the following in \CFA.
    72 \begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
    73 @__attribute__((cfa_linkonce))@ void f() {}
    74 \end{lstlisting}
    75 which becomes
    76 \begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
    77 __attribute__((section(".gnu.linkonce._X1fFv___1"))) void @_X1fFv___1@(){}
    78 \end{lstlisting}
    79 where @NAME@ from above is the \CFA mangled variable/function name.  Note,
    80 adding this feature is necessary because, when using macros, the mangled name
    81 is unavailable.  This attribute is useful for purposes other than exception
    82 handling, and should eventually be rolled into @inline@ processing in \CFA.
    83 
    84 Finally, a type id's data implements a pointers to the type's type information
    85 instance.  Dereferencing the pointer gets the type information.
    86 
    87 \subsection{Implementation}
    88 
     52program (see \autoref{ss:VirtualTable}); so the initial solution would seem
     53to be make it external in each translation unit. Honever, 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.
    8984The type information currently is only the parent's type id or, if the
    9085type has no parent, the null pointer.
     
    10398\end{cfa}
    10499
    105 The type information is constructed as follows:
     100Type information is constructed as follows:
    106101\begin{enumerate}
    107102\item
     
    124119\item
    125120\CFA's name mangler does its regular name mangling encoding the type of
    126 the declaration into the instance name. This process gives a program unique name
     121the declaration into the instance name.
     122This process gives a completely unique name
    127123including different instances of the same polymorphic type.
    128124\end{enumerate}
    129125\todo{The list is making me realize, some of this isn't ordered.}
    130126
     127Writing that code manually, with helper macros for the early name mangling,
     128would look like this:
     129\begin{cfa}
     130struct INFO_TYPE(TYPE) {
     131        INFO_TYPE(PARENT) const * parent;
     132};
     133
     134__attribute__((cfa_linkonce))
     135INFO_TYPE(TYPE) const INFO_NAME(TYPE) = {
     136        &INFO_NAME(PARENT),
     137};
     138\end{cfa}
    131139
    132140\begin{comment}
     
    158166and the other is discarded.
    159167\end{comment}
    160 
    161168
    162169\subsection{Virtual Table}
     
    191198The first and second sections together mean that every virtual table has a
    192199prefix that has the same layout and types as its parent virtual table.
    193 This, combined with the fixed offset to the virtual-table pointer, means that
     200This, combined with the fixed offset to the virtual table pointer, means that
    194201for any virtual type, it is always safe to access its virtual table and,
    195202from there, it is safe to check the type id to identify the exact type of the
     
    209216type's alignment, is set using an @alignof@ expression.
    210217
     218Most of these tools are already inside the compiler. Using the is a simple
     219code transformation early on in compilation allows most of that work to be
     220handed off to the existing tools. \autoref{f:VirtualTableTransformation}
     221shows an example transformation, this example shows an exception virtual table.
     222It also shows the transformation on the full declaration,
     223for a forward declaration the @extern@ keyword is preserved and the
     224initializer is not added.
     225
     226\begin{figure}[htb]
     227\begin{cfa}
     228vtable(example_type) example_name;
     229\end{cfa}
     230\transformline
     231% Check mangling.
     232\begin{cfa}
     233const struct example_type_vtable example_name = {
     234        .__cfavir_typeid : &__cfatid_example_type,
     235        .size : sizeof(example_type),
     236        .copy : copy,
     237        .^?{} : ^?{},
     238        .msg : msg,
     239};
     240\end{cfa}
     241\caption{Virtual Table Transformation}
     242\label{f:VirtualTableTransformation}
     243\end{figure}
     244
    211245\subsection{Concurrency Integration}
    212246Coroutines and threads need instances of @CoroutineCancelled@ and
     
    218252These transformations are shown through code re-writing in
    219253\autoref{f:CoroutineTypeTransformation} and
    220 \autoref{f:CoroutineMainTransformation} for a coroutine and a thread is similar.
    221 In both cases, the original declaration is not modified, only new ones are
    222 added.
    223 
    224 \begin{figure}
     254\autoref{f:CoroutineMainTransformation}.
     255Threads use the same pattern, with some names and types changed.
     256In both cases, the original declaration is not modified,
     257only new ones are added.
     258
     259\begin{figure}[htb]
    225260\begin{cfa}
    226261coroutine Example {
     
    242277\caption{Coroutine Type Transformation}
    243278\label{f:CoroutineTypeTransformation}
    244 %\end{figure}
    245 
    246 \bigskip
    247 
    248 %\begin{figure}
     279\end{figure}
     280
     281\begin{figure}[htb]
    249282\begin{cfa}
    250283void main(Example & this) {
     
    277310\begin{cfa}
    278311void * __cfa__virtual_cast(
    279         struct __cfavir_type_td parent,
    280         struct __cfavir_type_id const * child );
    281 \end{cfa}
    282 The type id for the target type of the virtual cast is passed in as @parent@ and
     312        struct __cfavir_type_id * parent,
     313        struct __cfavir_type_id * const * child );
     314\end{cfa}
     315The type id for the target type of the virtual cast is passed in as
     316@parent@ and
    283317the cast target is passed in as @child@.
    284318The generated C code wraps both arguments and the result with type casts.
     
    294328
    295329\section{Exceptions}
    296 \todo{Anything about exception construction.}
     330% The implementation of exception types.
     331
     332Creating exceptions can roughly divided into two parts,
     333the exceptions themselves and the virtual system interactions.
     334
     335Creating an exception type is just a matter of preppending the field 
     336with the virtual table pointer to the list of the fields
     337(see \autoref{f:ExceptionTypeTransformation}).
     338
     339\begin{figure}[htb]
     340\begin{cfa}
     341exception new_exception {
     342        // EXISTING FIELDS
     343};
     344\end{cfa}
     345\transformline
     346\begin{cfa}
     347struct new_exception {
     348        struct new_exception_vtable const * virtual_table;
     349        // EXISTING FIELDS
     350};
     351\end{cfa}
     352\caption{Exception Type Transformation}
     353\label{f:ExceptionTypeTransformation}
     354\end{figure}
     355
     356The integration between exceptions and the virtual system is a bit more
     357complex simply because of the nature of the virtual system prototype.
     358The primary issue is that the virtual system has no way to detect when it
     359should generate any of its internal types and data. This is handled by
     360the exception code, which tells the virtual system when to generate
     361its components.
     362
     363All types associated with a virtual type,
     364the types of the virtual table and the type id,
     365are generated when the virtual type (the exception) is first found.
     366The type id (the instance) is generated with the exception if it is
     367a monomorphic type.
     368However if the exception is polymorphic then a different type id has to
     369be generated for every instance. In this case generation is delayed
     370until a virtual table is created.
     371% There are actually some problems with this, which is why it is not used
     372% for monomorphic types.
     373When a virtual table is created and initialized two functions are created
     374to fill in the list of virtual members.
     375The first is a copy function which adapts the exception's copy constructor
     376to work with pointers, avoiding some issues with the current copy constructor
     377interface.
     378Second is the msg function, which returns a C-string with the type's name,
     379including any polymorphic parameters.
    297380
    298381\section{Unwinding}
     
    308391stack. On function entry and return, unwinding is handled directly by the
    309392call/return code embedded in the function.
    310 \PAB{Meaning: In many cases, the position of the instruction pointer (relative to parameter
    311 and local declarations) is enough to know the current size of the stack
    312 frame.}
    313 
     393
     394% Discussing normal stack unwinding:
    314395Usually, the stack-frame size is known statically based on parameter and
    315396local variable declarations. Even for a dynamic stack-size, the information
     
    319400bumping the hardware stack-pointer up or down as needed.
    320401Constructing/destructing values within a stack frame has
    321 a similar complexity but larger constants, which takes longer.
    322 
     402a similar complexity but larger constants.
     403
     404% Discussing multiple frame stack unwinding:
    323405Unwinding across multiple stack frames is more complex because that
    324406information is no longer contained within the current function.
    325 With separate compilation a function does not know its callers nor their frame size.
    326 In general, the caller's frame size is embedded only at the functions entry (push
    327 stack) and exit (pop stack).
    328 Without altering the main code path it is also hard to pass that work off
    329 to the caller.
     407With seperate compilation,
     408a function does not know its callers nor their frame layout.
     409Even using the return address, that information is encoded in terms of
     410actions in code, intermixed with the actions required finish the function.
     411Without changing the main code path it is impossible to select one of those
     412two groups of actions at the return site.
    330413
    331414The traditional unwinding mechanism for C is implemented by saving a snap-shot
     
    340423many languages define clean-up actions that must be taken when certain
    341424sections of the stack are removed. Such as when the storage for a variable
    342 is removed from the stack (destructor call) or when a try statement with a finally clause is
     425is removed from the stack, possibly requiring a destructor call,
     426or when a try statement with a finally clause is
    343427(conceptually) popped from the stack.
    344428None of these cases should be handled by the user --- that would contradict the
     
    383467In plain C (which \CFA currently compiles down to) this
    384468flag only handles the cleanup attribute:
     469%\label{code:cleanup}
    385470\begin{cfa}
    386471void clean_up( int * var ) { ... }
     
    394479
    395480To get full unwinding support, all of these features must be handled directly
    396 in assembly and assembler directives; particularly the cfi directives
     481in assembly and assembler directives; partiularly the cfi directives
    397482\snake{.cfi_lsda} and \snake{.cfi_personality}.
    398483
     
    529614needs its own exception context.
    530615
    531 An exception context is retrieved by calling the function
     616The current exception context should be retrieved by calling the function
    532617\snake{this_exception_context}.
    533618For sequential execution, this function is defined as
     
    658743function. The LSDA in particular is hard to mimic in generated C code.
    659744
    660 The workaround is a function called @__cfaehm_try_terminate@ in the standard
    661 \CFA library. The contents of a try block and the termination handlers are converted
    662 into nested functions. These are then passed to the try terminate function and it
    663 calls them, appropriately.
     745The workaround is a function called \snake{__cfaehm_try_terminate} in the
     746standard \CFA library. The contents of a try block and the termination
     747handlers are converted into nested functions. These are then passed to the
     748try terminate function and it calls them, appropriately.
    664749Because this function is known and fixed (and not an arbitrary function that
    665750happens to contain a try statement), its LSDA can be generated ahead
    666751of time.
    667752
    668 Both the LSDA and the personality function for @__cfaehm_try_terminate@ are set ahead of time using
     753Both the LSDA and the personality function for \snake{__cfaehm_try_terminate}
     754are set ahead of time using
    669755embedded assembly. This assembly code is handcrafted using C @asm@ statements
    670756and contains
    671 enough information for a single try statement the function represents.
     757enough information for the single try statement the function represents.
    672758
    673759The three functions passed to try terminate are:
     
    681767decides if a catch clause matches the termination exception. It is constructed
    682768from the conditional part of each handler and runs each check, top to bottom,
    683 in turn, first checking to see if the exception type matches.
    684 The match is performed in two steps, first a virtual cast is used to see
    685 if the raised exception is an instance of the declared exception or one of
    686 its descendant type, and then is the condition true, if present.
    687 It takes a pointer to the exception and returns 0 if the
     769in turn, to see if the exception matches this handler.
     770The match is performed in two steps, first a virtual cast is used to check
     771if the raised exception is an instance of the declared exception type or
     772one of its descendant types, and then the condition is evaluated, if
     773present.
     774The match function takes a pointer to the exception and returns 0 if the
    688775exception is not handled here. Otherwise the return value is the id of the
    689776handler that matches the exception.
     
    698785All three functions are created with GCC nested functions. GCC nested functions
    699786can be used to create closures,
    700 in other words, functions that can refer to their lexical scope in other
    701 functions on the stack when called. This approach allows the functions to refer to all the
     787in other words,
     788functions that can refer to variables in their lexical scope even
     789those variables are part of a different function.
     790This approach allows the functions to refer to all the
    702791variables in scope for the function containing the @try@ statement. These
    703792nested functions and all other functions besides @__cfaehm_try_terminate@ in
     
    786875the operation finishes, otherwise the search continues to the next node.
    787876If the search reaches the end of the list without finding a try statement
    788 that can handle the exception, the default handler is executed and the
    789 operation finishes, unless it throws an exception.
     877with a handler clause
     878that can handle the exception, the default handler is executed.
     879If the default handler returns, control continues after the raise statement.
    790880
    791881Each node has a handler function that does most of the work.
     
    797887If no match is found the function returns false.
    798888The match is performed in two steps, first a virtual cast is used to see
    799 if the raised exception is an instance of the declared exception or one of
    800 its descendant type, and then is the condition true, if present.
    801 \PAB{I don't understand this sentence.
    802 This ordering gives the type guarantee used in the predicate.}
     889if the raised exception is an instance of the declared exception type or one
     890of its descendant types, if so then it is passed to the custom predicate
     891if one is defined.
     892% You need to make sure the type is correct before running the predicate
     893% because the predicate can depend on that.
    803894
    804895\autoref{f:ResumptionTransformation} shows the pattern used to transform
    805 a \CFA try statement with catch clauses into the appropriate C functions.
     896a \CFA try statement with catch clauses into the approprate C functions.
    806897\todo{Explain the Resumption Transformation figure.}
    807898
     
    852943(see \vpageref{s:ResumptionMarking}), which ignores parts of
    853944the stack
    854 already examined, and is accomplished by updating the front of the list as the
    855 search continues. Before the handler is called at a matching node, the head of the list
     945already examined, and is accomplished by updating the front of the list as
     946the search continues.
     947Before the handler is called at a matching node, the head of the list
    856948is updated to the next node of the current node. After the search is complete,
    857949successful or not, the head of the list is reset.
     
    890982\section{Finally}
    891983% Uses destructors and GCC nested functions.
    892 \autoref{f:FinallyTransformation} shows the pattern used to transform a \CFA
    893 try statement with finally clause into the appropriate C functions.
    894 The finally clause is placed into a GCC nested-function
    895 with a unique name, and no arguments or return values.  This nested function is
     984
     985%\autoref{code:cleanup}
     986A finally clause is handled by converting it into a once-off destructor.
     987The code inside the clause is placed into GCC nested-function
     988with a unique name, and no arguments or return values.
     989This nested function is
    896990then set as the cleanup function of an empty object that is declared at the
    897 beginning of a block placed around the context of the associated @try@
    898 statement.
     991beginning of a block placed around the context of the associated try
     992statement (see \autoref{f:FinallyTransformation}).
    899993
    900994\begin{figure}
     
    9191013                // TRY BLOCK
    9201014        }
    921 
    9221015}
    9231016\end{cfa}
     
    9271020\end{figure}
    9281021
    929 The rest is handled by GCC. The try block and all handlers are inside this
    930 block. At completion, control exits the block and the empty object is cleaned
     1022The rest is handled by GCC.
     1023The TRY BLOCK
     1024contains the try block itself as well as all code generated for handlers.
     1025Once that code has completed,
     1026control exits the block and the empty object is cleaned
    9311027up, which runs the function that contains the finally code.
    9321028
     
    9391035
    9401036The first step of cancellation is to find the cancelled stack and its type:
    941 coroutine, thread, or main thread.
     1037coroutine, thread or main thread.
    9421038In \CFA, a thread (the construct the user works with) is a user-level thread
    9431039(point of execution) paired with a coroutine, the thread's main coroutine.
    9441040The thread library also stores pointers to the main thread and the current
    945 coroutine.
     1041thread.
    9461042If the current thread's main and current coroutines are the same then the
    9471043current stack is a thread stack, otherwise it is a coroutine stack.
  • doc/theses/andrew_beach_MMath/intro.tex

    r1d402be reaeca5f  
    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.
     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.
    3040\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}
     41\input{callreturn}
    5242\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.
    60 \begin{center}
    61 \input{termination}
    62 \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. Ada still uses this system.\todo{cite Ada}
    150128
    151129The modern flag-ship for termination exceptions is \Cpp,
    152130which added them in its first major wave of non-object-orientated features
    153131in 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
     132\todo{cite https://en.cppreference.com/w/cpp/language/history}
     133Many EHMs have special exception types,
     134however \Cpp has the ability to use any type as an exception.
     135These were found to be not very useful and have been pushed aside for classes
     136inheriting from
    158137\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
     138Although there is a special catch-all syntax (@catch(...)@) there are no
     139operations that can be performed on the caught value, not even type inspection.
     140Instead the base exception-type \code{C++}{std::exception} defines common
     141functionality (such as
     142the ability to describe the reason the exception was raised) and all
    163143exceptions 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}
     144That trade-off, restricting usable types to gain guaranteed functionality,
     145is almost universal now, as without some common functionality it is almost
     146impossible to actually handle any errors.
     147
     148Java was the next popular language to use exceptions. \todo{cite Java}
     149Its exception system largely reflects that of \Cpp, except that requires
     150you throw a child type of \code{Java}{java.lang.Throwable}
    170151and 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.
     152Checked exceptions are part of a function's interface,
     153the exception signature of the function.
     154Every function that could be raised from a function, either directly or
     155because it is not handled from a called function, is given.
     156Using this information, it is possible to statically verify if any given
     157exception is handled and guarantee that no exception will go unhandled.
     158Making exception information explicit improves clarity and safety,
     159but can slow down or restrict programming.
     160For example, programming high-order functions becomes much more complex
     161if the argument functions could raise exceptions.
     162However, as odd it may seem, the worst problems are rooted in the simple
     163inconvenience of writing and updating exception signatures.
     164This has caused Java programmers to develop multiple programming ``hacks''
     165to circumvent checked exceptions, negating their advantages.
     166One particularly problematic example is the ``catch-and-ignore'' pattern,
     167where an empty handler is used to handle an exception without doing any
     168recovery or repair. In theory that could be good enough to properly handle
     169the exception, but more often is used to ignore an exception that the       
     170programmer does not feel is worth the effort of handling it, for instance if
     171they do not believe it will ever be raised.
     172If they are incorrect the exception will be silenced, while in a similar
     173situation with unchecked exceptions the exception would at least activate   
     174the language's unhandled exception code (usually program abort with an 
     175error message).
    181176
    182177%\subsection
    183178Resumption exceptions are less popular,
    184 although resumption is as old as termination;
    185 hence, few
     179although resumption is as old as termination; hence, few
    186180programming languages have implemented them.
    187181% http://bitsavers.informatik.uni-stuttgart.de/pdf/xerox/parc/techReports/
    188182%   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
     183Mesa is one programming language that did.\todo{cite Mesa} Experience with Mesa
     184is quoted as being one of the reasons resumptions were not
    191185included in the \Cpp standard.
    192186% 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.
     187Since then resumptions have been ignored in main-stream programming languages.
     188However, resumption is being revisited in the context of decades of other
     189developments in programming languages.
     190While rejecting resumption may have been the right decision in the past,
     191the situation has changed since then.
     192Some developments, such as the function programming equivalent to resumptions,
     193algebraic effects\cite{Zhang19}, are enjoying success.
     194A complete reexamination of resumptions is beyond this thesis,
     195but there reemergence is enough to try them in \CFA.
    201196% 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.
     197% termination exceptions and how much Peter likes them.
     198
     199%\subsection
     200Functional languages tend to use other solutions for their primary error
     201handling mechanism, but exception-like constructs still appear.
     202Termination appears in the error construct, which marks the result of an
     203expression as an error; then the result of any expression that tries to use
     204it also results in an error, and so on until an appropriate handler is reached.
    210205Resumption appears in algebraic effects, where a function dispatches its
    211206side-effects to its caller for handling.
    212207
    213208%\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.
     209More recently exceptions seem to be vanishing from newer programming
     210languages, replaced by ``panic".
     211In Rust, a panic is just a program level abort that may be implemented by
     212unwinding the stack like in termination exception handling.\todo{cite Rust}
    218213% 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
     214Go's panic through is very similar to a termination, except it only supports
    220215a catch-all by calling \code{Go}{recover()}, simplifying the interface at
    221 the cost of flexibility.
     216the cost of flexibility.\todo{cite Go}
    222217
    223218%\subsection
    224219While exception handling's most common use cases are in error handling,
    225 here are other ways to handle errors with comparisons to exceptions.
     220here are some other ways to handle errors with comparisons with exceptions.
    226221\begin{itemize}
    227222\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,
     223This pattern has a function return an enumeration (or just a set of fixed
     224values) to indicate if an error has occurred and possibly which error it was.
     225
     226Error codes mix exceptional/error and normal values, enlarging the range of
     227possible return values. This can be addressed with multiple return values
     228(or a tuple) or a tagged union.
     229However, the main issue with error codes is forgetting to check them,
    234230which 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..
     231Some new languages and tools will try to issue warnings when an error code
     232is discarded to avoid this problem.
     233Checking error codes also bloats the main execution path,
     234especially if the error is not handled immediately hand has to be passed
     235through multiple functions before it is addressed.
    238236
    239237\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.
     238Similar to the error codes pattern but the function itself only returns
     239that there was an error
     240and store the reason for the error in a fixed global location.
     241For example many routines in the C standard library will only return some
     242error value (such as -1 or a null pointer) and the error code is written into
     243the standard variable @errno@.
     244
     245This approach avoids the multiple results issue encountered with straight
     246error codes but otherwise has the same disadvantages and more.
     247Every function that reads or writes to the global store must agree on all
     248possible errors and managing it becomes more complex with concurrency.
    248249
    249250\item\emph{Return Union}:
     
    254255so that one type can be used everywhere in error handling code.
    255256
    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.
     257This pattern is very popular in any functional or semi-functional language
     258with primitive support for tagged unions (or algebraic data types).
     259% We need listing Rust/rust to format code snippets from it.
    259260% 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.
     261The main advantage is that an arbitrary object can be used to represent an
     262error so it can include a lot more information than a simple error code.
     263The disadvantages include that the it does have to be checked along the main
     264execution and if there aren't primitive tagged unions proper usage can be
     265hard to enforce.
    265266
    266267\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
     268This pattern associates errors with functions.
     269On error, the function that produced the error calls another function to
    269270handle it.
    270271The handler function can be provided locally (passed in as an argument,
    271272either directly as as a field of a structure/object) or globally (a global
    272273variable).
    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.
     274C++ uses this approach as its fallback system if exception handling fails,
     275such as \snake{std::terminate_handler} and, for a time,
     276\snake{std::unexpected_handler}.
     277
     278Handler functions work a lot like resumption exceptions,
     279but without the dynamic search for a handler.
     280Since setting up the handler can be more complex/expensive,
     281especially when the handler has to be passed through multiple layers of
     282function calls, but cheaper (constant time) to call,
     283they are more suited to more frequent (less exceptional) situations.
    281284\end{itemize}
    282285
    283286%\subsection
    284287Because 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.
     288Hence, there is an element of self-fulfilling prophecy as implementation
     289techniques have been focused on making them cheap to set-up,
     290happily making them expensive to use in exchange.
     291This difference is less important in higher-level scripting languages,
     292where using exception for other tasks is more common.
     293An iconic example is Python's \code{Python}{StopIteration} exception that
     294is thrown by an iterator to indicate that it is exhausted.
     295When paired with Python's iterator-based for-loop this will be thrown every
     296time the end of the loop is reached.
     297\todo{Cite Python StopIteration and for-each loop.}
    292298% https://docs.python.org/3/library/exceptions.html#StopIteration
  • doc/theses/andrew_beach_MMath/performance.tex

    r1d402be reaeca5f  
    1111Tests were run in \CFA, C++, Java and Python.
    1212In addition there are two sets of tests for \CFA,
    13 one for termination and one for resumption exceptions.
     13one for termination and once with resumption.
    1414
    1515C++ is the most comparable language because both it and \CFA use the same
    1616framework, libunwind.
    17 In fact, the comparison is almost entirely a quality of implementation.
     17In fact, the comparison is almost entirely in quality of implementation.
    1818Specifically, \CFA's EHM has had significantly less time to be optimized and
    1919does not generate its own assembly. It does have a slight advantage in that
    20 there are some features it handles directly instead of through utility functions,
     20\Cpp has to do some extra bookkeeping to support its utility functions,
    2121but otherwise \Cpp should have a significant advantage.
    2222
    23 Java is a popular language with similar termination semantics, but
     23Java a popular language with similar termination semantics, but
    2424it is implemented in a very different environment, a virtual machine with
    2525garbage collection.
    26 It also implements the @finally@ clause on @try@ blocks allowing for a direct
     26It also implements the finally clause on try blocks allowing for a direct
    2727feature-to-feature comparison.
    28 As with \Cpp, Java's implementation is mature, optimized
    29 and has extra features.
     28As with \Cpp, Java's implementation is mature, has more optimizations
     29and extra features as compared to \CFA.
    3030
    3131Python is used as an alternative comparison because of the \CFA EHM's
    32 current performance goals, which is not to be prohibitively slow while the
     32current performance goals, which is to not be prohibitively slow while the
    3333features are designed and examined. Python has similar performance goals for
    3434creating quick scripts and its wide use suggests it has achieved those goals.
     
    3737resumption exceptions. Even the older programming languages with resumption
    3838seem to be notable only for having resumption.
    39 So instead, resumption is compared to its simulation in other programming
    40 languages using fixup functions that are explicitly passed for correction or
    41 logging purposes.
    42 % So instead, resumption is compared to a less similar but much more familiar
    43 %feature, termination exceptions.
     39Instead, resumption is compared to its simulation in other programming
     40languages: fixup functions that are explicity passed into a function.
    4441
    4542All tests are run inside a main loop that repeatedly performs a test.
    4643This approach avoids start-up or tear-down time from
    4744affecting the timing results.
    48 Each test is run a N times (configurable from the command line).
     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.
     47Tests ran their main loop a million times.
    4948The Java tests runs the main loop 1000 times before
    5049beginning the actual test to ``warm-up" the JVM.
     50% All other languages are precompiled or interpreted.
    5151
    5252Timing is done internally, with time measured immediately before and
     
    5959
    6060The exceptions used in these tests are always based off of
    61 a base exception. This requirement minimizes performance differences based
     61the base exception for the language.
     62This requirement minimizes performance differences based
    6263on the object model used to represent the exception.
    6364
     
    6667For example, empty inline assembly blocks are used in \CFA and \Cpp to
    6768prevent excessive optimizations while adding no actual work.
    68 Each test was run eleven times. The top three and bottom three results were
    69 discarded and the remaining five values are averaged.
    70 
    71 The tests are compiled with gcc-10 for \CFA and g++-10 for \Cpp. Java is
    72 compiled with version 11.0.11. Python with version 3.8. The tests were run on:
    73 \begin{itemize}[nosep]
    74 \item
    75 ARM 2280 Kunpeng 920 48-core 2$\times$socket \lstinline{@} 2.6 GHz running Linux v5.11.0-25
    76 \item
    77 AMD 6380 Abu Dhabi 16-core 4$\times$socket \lstinline{@} 2.5 GHz running Linux v5.11.0-25
    78 \end{itemize}
    79 Two kinds of hardware architecture allows discriminating any implementation and
    80 architectural effects.
    81 
    8269
    8370% We don't use catch-alls but if we did:
    8471% Catch-alls are done by catching the root exception type (not using \Cpp's
    8572% \code{C++}{catch(...)}).
     73
     74When collecting data each test is run eleven times. The top three and bottom
     75three results are discarded and the remaining five values are averaged.
     76The test are run with the latest (still pre-release) \CFA compiler was used,
     77using gcc-10 as a backend.
     78g++-10 is used for \Cpp.
     79Java tests are complied and run with version 11.0.11.
     80Python used version 3.8.
     81The machines used to run the tests are:
     82\todo{Get patch versions for python, gcc and g++.}
     83\begin{itemize}[nosep]
     84\item ARM 2280 Kunpeng 920 48-core 2$\times$socket
     85      \lstinline{@} 2.6 GHz running Linux v5.11.0-25
     86\item AMD 6380 Abu Dhabi 16-core 4$\times$socket
     87      \lstinline{@} 2.5 GHz running Linux v5.11.0-25
     88\end{itemize}
     89Representing the two major families of hardware architecture.
    8690
    8791\section{Tests}
     
    9094They should provide a guide as to where the EHM's costs are found.
    9195
    92 \paragraph{Raise and Handle}
    93 This group measures the cost of a try statement when exceptions are raised and
    94 the stack is unwound (termination) or not unwound (resumption).  Each test has
    95 has a repeating function like the following
    96 \begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
     96\paragraph{Stack Traversal}
     97This group measures the cost of traversing the stack,
     98(and in termination, unwinding it).
     99Inside the main loop is a call to a recursive function.
     100This function calls itself F times before raising an exception.
     101F is configurable from the command line, but is usually 100.
     102This builds up many stack frames, and any contents they may have,
     103before the raise.
     104The exception is always handled at the base of the stack.
     105For example the Empty test for \CFA resumption looks like:
     106\begin{cfa}
    97107void unwind_empty(unsigned int frames) {
    98108        if (frames) {
    99                 @unwind_empty(frames - 1);@ // AUGMENTED IN OTHER EXPERIMENTS
    100         } else throw (empty_exception){&empty_vt};
    101 }
    102 \end{lstlisting}
    103 which is called N times, where each call recurses to a depth of R (configurable from the command line), an
    104 exception is raised, the stack is a unwound, and the exception caught.
    105 \begin{itemize}[nosep]
    106 \item Empty:
    107 For termination, this test measures the cost of raising (stack walking) an
    108 exception through empty stack frames from the bottom of the recursion to an
    109 empty handler, and unwinding the stack. (see above code)
    110 
    111 \medskip
    112 For resumption, this test measures the same raising cost but does not unwind
    113 the stack. For languages without resumption, a fixup function is to the bottom
    114 of the recursion and called to simulate a fixup operation at that point.
    115 \begin{cfa}
    116 void nounwind_fixup(unsigned int frames, void (*raised_rtn)(int &)) {
    117         if (frames) {
    118                 nounwind_fixup(frames - 1, raised_rtn);
     109                unwind_empty(frames - 1);
    119110        } else {
    120                 int fixup = 17;
    121                 raised_rtn(fixup);
     111                throwResume (empty_exception){&empty_vt};
    122112        }
    123113}
    124114\end{cfa}
    125 where the passed fixup function is:
    126 \begin{cfa}
    127 void raised(int & fixup) {
    128         fixup = 42;
    129 }
    130 \end{cfa}
    131 For comparison, a \CFA version passing a function is also included.
     115Other test cases have additional code around the recursive call add
     116something besides simple stack frames to the stack.
     117Note that both termination and resumption will have to traverse over
     118the stack but only termination has to unwind it.
     119\begin{itemize}[nosep]
     120% \item None:
     121% Reuses the empty test code (see below) except that the number of frames
     122% is set to 0 (this is the only test for which the number of frames is not
     123% 100). This isolates the start-up and shut-down time of a throw.
     124\item Empty:
     125The repeating function is empty except for the necessary control code.
     126As other traversal tests add to this, so it is the baseline for the group
     127as the cost comes from traversing over and unwinding a stack frame
     128that has no other interactions with the exception system.
    132129\item Destructor:
    133 This test measures the cost of raising an exception through non-empty frames,
    134 where each frame has an object requiring destruction, from the bottom of the
    135 recursion to an empty handler. Hence, there are N destructor calls during
    136 unwinding.
    137 
    138 \medskip
    139 This test is not meaningful for resumption because the stack is only unwound as
    140 the recursion returns.
    141 \begin{cfa}
    142         WithDestructor object;
    143         unwind_destructor(frames - 1);
    144 \end{cfa}
     130The repeating function creates an object with a destructor before calling
     131itself.
     132Comparing this to the empty test gives the time to traverse over and/or
     133unwind a destructor.
    145134\item Finally:
    146 This test measures the cost of establishing a try block with an empty finally
    147 clause on the front side of the recursion and running the empty finally clauses
    148 during stack unwinding from the bottom of the recursion to an empty handler.
    149 \begin{cfa}
    150         try {
    151                 unwind_finally(frames - 1);
    152         } finally {}
    153 \end{cfa}
    154 
    155 \medskip
    156 This test is not meaningful for resumption because the stack is only unwound as
    157 the recursion returns.
     135The repeating function calls itself inside a try block with a finally clause
     136attached.
     137Comparing this to the empty test gives the time to traverse over and/or
     138unwind a finally clause.
    158139\item Other Handler:
    159 For termination, this test is like the finally test but the try block has a
    160 catch clause for an exception that is not raised, so catch matching is executed
    161 during stack unwinding but the match never successes until the catch at the
    162 bottom of the recursion.
    163 \begin{cfa}
    164         try {
    165                 unwind_other(frames - 1);
    166         } catch (not_raised_exception *) {}
    167 \end{cfa}
    168 
    169 \medskip
    170 For resumption, this test measures the same raising cost but does not unwind
    171 the stack. For languages without resumption, the same fixup function is passed
    172 and called.
     140The repeating function calls itself inside a try block with a handler that
     141will not match the raised exception, but is of the same kind of handler.
     142This means that the EHM will have to check each handler, but will continue
     143over all of the until it reaches the base of the stack.
     144Comparing this to the empty test gives the time to traverse over and/or
     145unwind a handler.
    173146\end{itemize}
    174147
    175 \paragraph{Try/Handle/Finally Statement}
    176 This group measures just the cost of executing a try statement so
    177 \emph{there is no stack unwinding}.  Hence, the program main loops N times
    178 around:
    179 \begin{cfa}
    180 try {
    181 } catch (not_raised_exception *) {}
    182 \end{cfa}
     148\paragraph{Cross Try Statement}
     149This group of tests measures the cost setting up exception handling if it is
     150not used (because the exceptional case did not occur).
     151Tests repeatedly cross (enter and leave, execute) a try statement but never
     152preform a raise.
    183153\begin{itemize}[nosep]
    184154\item Handler:
    185 The try statement has a handler (catch/resume).
     155The try statement has a handler (of the appropriate kind).
    186156\item Finally:
    187157The try statement has a finally clause.
     
    191161This group measures the cost of conditional matching.
    192162Only \CFA implements the language level conditional match,
    193 the other languages mimic with an ``unconditional" match (it still
    194 checks the exception's type) and conditional re-raise if it is not suppose
     163the other languages mimic it with an ``unconditional" match (it still
     164checks the exception's type) and conditional re-raise if it is not supposed
    195165to handle that exception.
    196 \begin{center}
    197 \begin{tabular}{ll}
    198 \multicolumn{1}{c}{\CFA} & \multicolumn{1}{c}{\Cpp, Java, Python} \\
     166
     167There is the pattern shown in \CFA and \Cpp. Java and Python use the same
     168pattern as \Cpp, but with their own syntax.
     169
     170\begin{minipage}{0.45\textwidth}
    199171\begin{cfa}
    200172try {
    201         throw_exception();
    202 } catch (empty_exception * exc;
    203                  should_catch) {
     173        ...
     174} catch (exception_t * e ;
     175                should_catch(e)) {
     176        ...
    204177}
    205178\end{cfa}
    206 &
    207 \begin{cfa}
     179\end{minipage}
     180\begin{minipage}{0.55\textwidth}
     181\begin{lstlisting}[language=C++]
    208182try {
    209         throw_exception();
    210 } catch (EmptyException & exc) {
    211         if (!should_catch) throw;
     183        ...
     184} catch (std::exception & e) {
     185        if (!should_catch(e)) throw;
     186        ...
    212187}
    213 \end{cfa}
    214 \end{tabular}
    215 \end{center}
     188\end{lstlisting}
     189\end{minipage}
    216190\begin{itemize}[nosep]
    217191\item Match All:
     
    221195\end{itemize}
    222196
    223 \medskip
    224 \noindent
    225 All omitted test code for other languages is functionally identical to the \CFA
    226 tests or simulated, and available online~\cite{CforallExceptionBenchmarks}.
     197\paragraph{Resumption Simulation}
     198A slightly altered version of the Empty Traversal test is used when comparing
     199resumption to fix-up routines.
     200The handler, the actual resumption handler or the fix-up routine,
     201always captures a variable at the base of the loop,
     202and receives a reference to a variable at the raise site, either as a
     203field on the exception or an argument to the fix-up routine.
     204% I don't actually know why that is here but not anywhere else.
    227205
    228206%\section{Cost in Size}
     
    237215
    238216\section{Results}
    239 One result not directly related to \CFA but important to keep in
    240 mind is that, for exceptions, the standard intuition about which languages
    241 should go faster often does not hold. For example, there are a few cases where Python out-performs
    242 \CFA, \Cpp and Java. The most likely explanation is that, since exceptions are
    243 rarely considered to be the common case, the more optimized languages
    244 make that case expense. In addition, languages with high-level
    245 representations have a much easier time scanning the stack as there is less
    246 to decode.
    247 
    248 Tables~\ref{t:PerformanceTermination} and~\ref{t:PerformanceResumption} show
    249 the test results for termination and resumption, respectively.  In cases where
    250 a feature is not supported by a language, the test is skipped for that language
    251 (marked N/A).  For some Java experiments it was impossible to measure certain
    252 effects because the JIT corrupted the test (marked N/C). No workaround was
    253 possible~\cite{Dice21}.  To get experiments in the range of 1--100 seconds, the
    254 number of times an experiment is run (N) is varied (N is marked beside each
    255 experiment, e.g., 1M $\Rightarrow$ 1 million test iterations).
    256 
    257 An anomaly exists with gcc nested functions used as thunks for implementing
    258 much of the \CFA EHM. If a nested-function closure captures local variables in
    259 its lexical scope, performance dropped by a factor of 10.  Specifically, in try
    260 statements of the form:
    261 \begin{cfa}
    262         try {
    263                 unwind_other(frames - 1);
    264         } catch (not_raised_exception *) {}
    265 \end{cfa}
    266 the try block is hoisted into a nested function and the variable @frames@ is
    267 the local parameter to the recursive function, which triggers the anomaly. The
    268 workaround is to remove the recursion parameter and make it a global variable
    269 that is explicitly decremented outside of the try block (marked with a ``*''):
    270 \begin{cfa}
    271         frames -= 1;
    272         try {
    273                 unwind_other();
    274         } catch (not_raised_exception *) {}
    275 \end{cfa}
    276 To make comparisons fair, a dummy parameter is added and the dummy value passed
    277 in the recursion. Note, nested functions in gcc are rarely used (if not
    278 completely unknown) and must follow the C calling convention, unlike \Cpp
    279 lambdas, so it is not surprising if there are performance issues efficiently
    280 capturing closures.
    281 
    282 % Similarly, if a test does not change between resumption
    283 % and termination in \CFA, then only one test is written and the result
    284 % was put into the termination column.
    285 
    286 % Raw Data:
    287 % run-algol-a.sat
    288 % ---------------
    289 % Raise Empty   &  82687046678 &  291616256 &   3252824847 & 15422937623 & 14736271114 \\
    290 % Raise D'tor   & 219933199603 &  297897792 & 223602799362 &         N/A &         N/A \\
    291 % Raise Finally & 219703078448 &  298391745 &          N/A &         ... & 18923060958 \\
    292 % Raise Other   & 296744104920 & 2854342084 & 112981255103 & 15475924808 & 21293137454 \\
    293 % Cross Handler &      9256648 &   13518430 &       769328 &     3486252 &    31790804 \\
    294 % Cross Finally &       769319 &        N/A &          N/A &     2272831 &    37491962 \\
    295 % Match All     &   3654278402 &   47518560 &   3218907794 &  1296748192 &   624071886 \\
    296 % Match None    &   4788861754 &   58418952 &   9458936430 &  1318065020 &   625200906 \\
    297 %
    298 % run-algol-thr-c
    299 % ---------------
    300 % Raise Empty   &   3757606400 &   36472972 &   3257803337 & 15439375452 & 14717808642 \\
    301 % Raise D'tor   &  64546302019 &  102148375 & 223648121635 &         N/A &         N/A \\
    302 % Raise Finally &  64671359172 &  103285005 &          N/A & 15442729458 & 18927008844 \\
    303 % Raise Other   & 294143497130 & 2630130385 & 112969055576 & 15448220154 & 21279953424 \\
    304 % Cross Handler &      9646462 &   11955668 &       769328 &     3453707 &    31864074 \\
    305 % Cross Finally &       773412 &        N/A &          N/A &     2253825 &    37266476 \\
    306 % Match All     &   3719462155 &   43294042 &   3223004977 &  1286054154 &   623887874 \\
    307 % Match None    &   4971630929 &   55311709 &   9481225467 &  1310251289 &   623752624 \\
    308 %
    309 % run-algol-04-a
    310 % --------------
    311 % Raise Empty   & 0.0 & 0.0 &  3250260945 & 0.0 & 0.0 \\
    312 % Raise D'tor   & 0.0 & 0.0 & 29017675113 & N/A & N/A \\
    313 % Raise Finally & 0.0 & 0.0 &         N/A & 0.0 & 0.0 \\
    314 % Raise Other   & 0.0 & 0.0 & 24411823773 & 0.0 & 0.0 \\
    315 % Cross Handler & 0.0 & 0.0 &      769334 & 0.0 & 0.0 \\
    316 % Cross Finally & 0.0 & N/A &         N/A & 0.0 & 0.0 \\
    317 % Match All     & 0.0 & 0.0 &  3254283504 & 0.0 & 0.0 \\
    318 % Match None    & 0.0 & 0.0 &  9476060146 & 0.0 & 0.0 \\
    319 
    320 % run-plg7a-a.sat
    321 % ---------------
    322 % Raise Empty   &  57169011329 &  296612564 &   2788557155 & 17511466039 & 23324548496 \\
    323 % Raise D'tor   & 150599858014 &  318443709 & 149651693682 &         N/A &         N/A \\
    324 % Raise Finally & 148223145000 &  373325807 &          N/A &         ... & 29074552998 \\
    325 % Raise Other   & 189463708732 & 3017109322 &  85819281694 & 17584295487 & 32602686679 \\
    326 % Cross Handler &      8001654 &   13584858 &      1555995 &     6626775 &    41927358 \\
    327 % Cross Finally &      1002473 &        N/A &          N/A &     4554344 &    51114381 \\
    328 % Match All     &   3162460860 &   37315018 &   2649464591 &  1523205769 &   742374509 \\
    329 % Match None    &   4054773797 &   47052659 &   7759229131 &  1555373654 &   744656403 \\
    330 %
    331 % run-plg7a-thr-a
    332 % ---------------
    333 % Raise Empty   &   3604235388 &   29829965 &   2786931833 & 17576506385 & 23352975105 \\
    334 % Raise D'tor   &  46552380948 &  178709605 & 149834207219 &         N/A &         N/A \\
    335 % Raise Finally &  46265157775 &  177906320 &          N/A & 17493045092 & 29170962959 \\
    336 % Raise Other   & 195659245764 & 2376968982 &  86070431924 & 17552979675 & 32501882918 \\
    337 % Cross Handler &    397031776 &   12503552 &      1451225 &     6658628 &    42304965 \\
    338 % Cross Finally &      1136746 &        N/A &          N/A &     4468799 &    46155817 \\
    339 % Match All     &   3189512499 &   39124453 &   2667795989 &  1525889031 &   733785613 \\
    340 % Match None    &   4094675477 &   48749857 &   7850618572 &  1566713577 &   733478963 \\
    341 %
    342 % run-plg7a-04-a
    343 % --------------
    344 % 0.0 are unfilled.
    345 % Raise Empty   & 0.0 & 0.0 &  2770781479 & 0.0 & 0.0 \\
    346 % Raise D'tor   & 0.0 & 0.0 & 23530084907 & N/A & N/A \\
    347 % Raise Finally & 0.0 & 0.0 &         N/A & 0.0 & 0.0 \\
    348 % Raise Other   & 0.0 & 0.0 & 23816827982 & 0.0 & 0.0 \\
    349 % Cross Handler & 0.0 & 0.0 &     1422188 & 0.0 & 0.0 \\
    350 % Cross Finally & 0.0 & N/A &         N/A & 0.0 & 0.0 \\
    351 % Match All     & 0.0 & 0.0 &  2671989778 & 0.0 & 0.0 \\
    352 % Match None    & 0.0 & 0.0 &  7829059869 & 0.0 & 0.0 \\
    353 
    354 \begin{table}
     217% First, introduce the tables.
     218\autoref{t:PerformanceTermination},
     219\autoref{t:PerformanceResumption}
     220and~\autoref{t:PerformanceFixupRoutines}
     221show the test results.
     222In cases where a feature is not supported by a language, the test is skipped
     223for that language and the result is marked N/A.
     224There are also cases where the feature is supported but measuring its
     225cost is impossible. This happened with Java, which uses a JIT that optimize
     226away the tests and it cannot be stopped.\cite{Dice21}
     227These tests are marked N/C.
     228To get results in a consistent range (1 second to 1 minute is ideal,
     229going higher is better than going low) N, the number of iterations of the
     230main loop in each test, is varied between tests. It is also given in the
     231results and usually have a value in the millions.
     232
     233An anomaly in some results came from \CFA's use of gcc nested functions.
     234These nested functions are used to create closures that can access stack
     235variables in their lexical scope.
     236However, if they do so then they can cause the benchmark's run-time to
     237increase by an order of magnitude.
     238The simplest solution is to make those values global variables instead
     239of function local variables.
     240% Do we know if editing a global inside nested function is a problem?
     241Tests that had to be modified to avoid this problem have been marked
     242with a ``*'' in the results.
     243
     244% Now come the tables themselves:
     245% You might need a wider window for this.
     246
     247\begin{table}[htb]
    355248\centering
    356 \caption{Performance Results Termination (sec)}
     249\caption{Termination Performance Results (sec)}
    357250\label{t:PerformanceTermination}
    358251\begin{tabular}{|r|*{2}{|r r r r|}}
    359252\hline
    360                         & \multicolumn{4}{c||}{AMD}             & \multicolumn{4}{c|}{ARM}      \\
     253                       & \multicolumn{4}{c||}{AMD}         & \multicolumn{4}{c|}{ARM}  \\
    361254\cline{2-9}
    362 N\hspace{8pt}           & \multicolumn{1}{c}{\CFA} & \multicolumn{1}{c}{\Cpp} & \multicolumn{1}{c}{Java} & \multicolumn{1}{c||}{Python} &
    363                           \multicolumn{1}{c}{\CFA} & \multicolumn{1}{c}{\Cpp} & \multicolumn{1}{c}{Java} & \multicolumn{1}{c|}{Python} \\
    364 \hline                                                                             
    365 Throw Empty (1M)        & 3.4   & 2.8   & 18.3  & 23.4          & 3.7   & 3.2   & 15.5  & 14.8  \\
    366 Throw D'tor (1M)        & 48.4  & 23.6  & N/A   & N/A           & 64.2  & 29.0  & N/A   & N/A   \\
    367 Throw Finally (1M)      & 3.4*  & N/A   & 17.9  & 29.0          & 4.1*  & N/A   & 15.6  & 19.0  \\
    368 Throw Other (1M)        & 3.6*  & 23.2  & 18.2  & 32.7          & 4.0*  & 24.5  & 15.5  & 21.4  \\
    369 Try/Catch (100M)        & 6.0   & 0.9   & N/C   & 37.4          & 10.0  & 0.8   & N/C   & 32.2  \\
    370 Try/Finally (100M)      & 0.9   & N/A   & N/C   & 44.1          & 0.8   & N/A   & N/C   & 37.3  \\
    371 Match All (10M)         & 32.9  & 20.7  & 13.4  & 4.9           & 36.2  & 24.5  & 12.0  & 3.1   \\
    372 Match None (10M)        & 32.7  & 50.3  & 11.0  & 5.1           & 36.3  & 71.9  & 12.3  & 4.2   \\
     255N\hspace{8pt}          & \multicolumn{1}{c}{\CFA} & \multicolumn{1}{c}{\Cpp} & \multicolumn{1}{c}{Java} & \multicolumn{1}{c||}{Python} &
     256                         \multicolumn{1}{c}{\CFA} & \multicolumn{1}{c}{\Cpp} & \multicolumn{1}{c}{Java} & \multicolumn{1}{c|}{Python} \\
     257\hline
     258Empty Traversal (1M)   & 3.4   & 2.8   & 18.3  & 23.4      & 3.7   & 3.2   & 15.5  & 14.8  \\
     259D'tor Traversal (1M)   & 48.4  & 23.6  & N/A   & N/A       & 64.2  & 29.0  & N/A   & N/A   \\
     260Finally Traversal (1M) & 3.4*  & N/A   & 17.9  & 29.0      & 4.1*  & N/A   & 15.6  & 19.0  \\
     261Other Traversal (1M)   & 3.6*  & 23.2  & 18.2  & 32.7      & 4.0*  & 24.5  & 15.5  & 21.4  \\
     262Cross Handler (100M)   & 6.0   & 0.9   & N/C   & 37.4      & 10.0  & 0.8   & N/C   & 32.2  \\
     263Cross Finally (100M)   & 0.9   & N/A   & N/C   & 44.1      & 0.8   & N/A   & N/C   & 37.3  \\
     264Match All (10M)        & 32.9  & 20.7  & 13.4  & 4.9       & 36.2  & 24.5  & 12.0  & 3.1   \\
     265Match None (10M)       & 32.7  & 50.3  & 11.0  & 5.1       & 36.3  & 71.9  & 12.3  & 4.2   \\
    373266\hline
    374267\end{tabular}
    375268\end{table}
    376269
    377 \begin{table}
     270\begin{table}[htb]
     271\centering
     272\caption{Resumption Performance Results (sec)}
     273\label{t:PerformanceResumption}
     274\begin{tabular}{|r||r||r|}
     275\hline
     276N\hspace{8pt}
     277                        & AMD     & ARM  \\
     278\hline
     279Empty Traversal (10M)   & 0.2     & 0.3  \\
     280D'tor Traversal (10M)   & 1.8     & 1.0  \\
     281Finally Traversal (10M) & 1.7     & 1.0  \\
     282Other Traversal (10M)   & 22.6    & 25.9 \\
     283Cross Handler (100M)    & 8.4     & 11.9 \\
     284Match All (100M)        & 2.3     & 3.2  \\
     285Match None (100M)       & 2.9     & 3.9  \\
     286\hline
     287\end{tabular}
     288\end{table}
     289
     290\begin{table}[htb]
    378291\centering
    379292\small
    380 \caption{Performance Results Resumption (sec)}
    381 \label{t:PerformanceResumption}
     293\caption{Resumption/Fixup Routine Comparison (sec)}
     294\label{t:PerformanceFixupRoutines}
    382295\setlength{\tabcolsep}{5pt}
    383 \begin{tabular}{|r|*{2}{|r r r r|}}
    384 \hline
    385                         & \multicolumn{4}{c||}{AMD}             & \multicolumn{4}{c|}{ARM}      \\
    386 \cline{2-9}
    387 N\hspace{8pt}           & \multicolumn{1}{c}{\CFA (R/F)} & \multicolumn{1}{c}{\Cpp} & \multicolumn{1}{c}{Java} & \multicolumn{1}{c||}{Python} &
    388                           \multicolumn{1}{c}{\CFA (R/F)} & \multicolumn{1}{c}{\Cpp} & \multicolumn{1}{c}{Java} & \multicolumn{1}{c|}{Python} \\
    389 \hline                                                                             
    390 Resume Empty (10M)      & 3.8/3.5       & 14.7  & 2.3   & 176.1 & 0.3/0.1       & 8.9   & 1.2   & 119.9 \\
    391 Resume Other (10M)      & 4.0*/0.1*     & 21.9  & 6.2   & 381.0 & 0.3*/0.1*     & 13.2  & 5.0   & 290.7 \\
    392 Try/Resume (100M)       & 8.8           & N/A   & N/A   & N/A   & 12.3          & N/A   & N/A   & N/A   \\
    393 Match All (10M)         & 0.3           & N/A   & N/A   & N/A   & 0.3           & N/A   & N/A   & N/A   \\
    394 Match None (10M)        & 0.3           & N/A   & N/A   & N/A   & 0.4           & N/A   & N/A   & N/A   \\
     296\begin{tabular}{|r|*{2}{|r r r r r|}}
     297\hline
     298            & \multicolumn{5}{c||}{AMD}     & \multicolumn{5}{c|}{ARM}  \\
     299\cline{2-11}
     300N\hspace{8pt}       & \multicolumn{1}{c}{Raise} & \multicolumn{1}{c}{\CFA} & \multicolumn{1}{c}{\Cpp} & \multicolumn{1}{c}{Java} & \multicolumn{1}{c||}{Python} &
     301              \multicolumn{1}{c}{Raise} & \multicolumn{1}{c}{\CFA} & \multicolumn{1}{c}{\Cpp} & \multicolumn{1}{c}{Java} & \multicolumn{1}{c|}{Python} \\
     302\hline
     303Resume Empty (10M)  & 3.8  & 3.5  & 14.7  & 2.3   & 176.1 & 0.3  & 0.1  & 8.9   & 1.2   & 119.9 \\
     304%Resume Other (10M)  & 4.0* & 0.1* & 21.9  & 6.2   & 381.0 & 0.3* & 0.1* & 13.2  & 5.0   & 290.7 \\
    395305\hline
    396306\end{tabular}
    397307\end{table}
    398308
    399 As stated, the performance tests are not attempting to compare exception
    400 handling across languages.  The only performance requirement is to ensure the
    401 \CFA EHM implementation runs in a reasonable amount of time, given its
    402 constraints. In general, the \CFA implement did very well. Each of the tests is
    403 analysed.
     309% Now discuss the results in the tables.
     310One result not directly related to \CFA but important to keep in mind is that,
     311for exceptions the standard intuition about which languages should go
     312faster often does not hold.
     313For example, there are a few cases where Python out-performs
     314\CFA, \Cpp and Java.
     315The most likely explanation is that, since exceptions
     316are rarely considered to be the common case, the more optimized languages
     317make that case expensive to improve other cases.
     318In addition, languages with high-level representations have a much
     319easier time scanning the stack as there is less to decode.
     320
     321As stated,
     322the performance tests are not attempting to show \CFA has a new competitive
     323way of implementing exception handling.
     324The only performance requirement is to insure the \CFA EHM has reasonable
     325performance for prototyping.
     326Although that may be hard to exactly quantify, we believe it has succeeded
     327in that regard.
     328Details on the different test cases follow.
     329
    404330\begin{description}
    405 \item[Throw/Resume Empty]
    406 For termination, \CFA is close to \Cpp, where other languages have a higher cost.
    407 
    408 For resumption, \CFA is better than the fixup simulations in the other languages, except Java.
    409 The \CFA results on the ARM computer for both resumption and function simulation are particularly low;
    410 I have no explanation for this anomaly, except the optimizer has managed to remove part of the experiment.
    411 Python has a high cost for passing the lambda during the recursion.
    412 
    413 \item[Throw D'tor]
    414 For termination, \CFA is twice the cost of \Cpp.
    415 The higher cost for \CFA must be related to how destructors are handled.
    416 
    417 \item[Throw Finally]
    418 \CFA is better than the other languages with a @finally@ clause, which is the
    419 same for termination and resumption.
    420 
    421 \item[Throw/Resume Other]
    422 For termination, \CFA is better than the other languages.
    423 
    424 For resumption, \CFA is equal to or better the other languages.
    425 Again, the \CFA results on the ARM computer for both resumption and function simulation are particularly low.
    426 Python has a high cost for passing the lambda during the recursion.
    427 
    428 \item[Try/Catch/Resume]
    429 For termination, installing a try statement is more expressive than \Cpp
    430 because the try components are hoisted into local functions.  At runtime, these
    431 functions are than passed to libunwind functions to set up the try statement.
    432 \Cpp zero-cost try-entry accounts for its performance advantage.
    433 
    434 For resumption, there are similar costs to termination to set up the try
    435 statement but libunwind is not used.
    436 
    437 \item[Try/Finally]
    438 Setting up a try finally is less expensive in \CFA than setting up handlers,
    439 and is significantly less than other languages.
    440 
    441 \item[Throw/Resume Match All]
    442 For termination, \CFA is close to the other language simulations.
    443 
    444 For resumption, the stack unwinding is much faster because it does not use
    445 libunwind.  Instead resumption is just traversing a linked list with each node
    446 being the next stack frame with the try block.
    447 
    448 \item[Throw/Resume Match None]
    449 The same results as for Match All.
     331\item[Empty Traversal]
     332\CFA is slower than \Cpp, but is still faster than the other languages
     333and closer to \Cpp than other languages.
     334This is to be expected as \CFA is closer to \Cpp than the other languages.
     335
     336\item[D'tor Traversal]
     337Running destructors causes huge slowdown in every language that supports
     338them. \CFA has a higher proportionate slowdown but it is similar to \Cpp's.
     339Considering the amount of work done in destructors is so low the cost
     340likely comes from the change of context required to do that work.
     341
     342\item[Finally Traversal]
     343Speed is similar to Empty Traversal in all languages that support finally
     344clauses. Only Python seems to have a larger than random noise change in
     345its run-time and it is still not large.
     346Despite the similarity between finally clauses and destructors,
     347finally clauses seem to avoid the spike in run-time destructors have.
     348Possibly some optimization removes the cost of changing contexts.
     349\todo{OK, I think the finally clause may have been optimized out.}
     350
     351\item[Other Traversal]
     352For \Cpp, stopping to check if a handler applies seems to be about as
     353expensive as stopping to run a destructor.
     354This results in a significant jump.
     355
     356Other languages experiance a small increase in run-time.
     357The small increase likely comes from running the checks,
     358but they could avoid the spike by not having the same kind of overhead for
     359switching to the check's context.
     360
     361\todo{Could revist Other Traversal, after Finally Traversal.}
     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 doesn't 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 a 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
     387much more similar.
     388
    450389\end{description}
    451390
    452 \begin{comment}
    453 This observation means that while \CFA does not actually keep up with Python in
    454 every case, it is usually no worse than roughly half the speed of \Cpp. This
    455 performance is good enough for the prototyping purposes of the project.
    456 
    457 The test case where \CFA falls short is Raise Other, the case where the
    458 stack is unwound including a bunch of non-matching handlers.
    459 This slowdown seems to come from missing optimizations.
    460 
    461 This suggests that the performance issue in Raise Other is just an
    462 optimization not being applied. Later versions of gcc may be able to
    463 optimize this case further, at least down to the half of \Cpp mark.
    464 A \CFA compiler that directly produced assembly could do even better as it
    465 would not have to work across some of \CFA's current abstractions, like
    466 the try terminate function.
    467 
    468 Resumption exception handling is also incredibly fast. Often an order of
    469 magnitude or two better than the best termination speed.
    470 There is a simple explanation for this; traversing a linked list is much   
    471 faster than examining and unwinding the stack. When resumption does not do as
    472 well its when more try statements are used per raise. Updating the internal
    473 linked list is not very expensive but it does add up.
    474 
    475 The relative speed of the Match All and Match None tests (within each
    476 language) can also show the effectiveness conditional matching as compared
    477 to catch and rethrow.
    478 \begin{itemize}[nosep]
    479 \item
    480 Java and Python get similar values in both tests.
    481 Between the interpreted code, a higher level representation of the call
    482 stack and exception reuse it it is possible the cost for a second
    483 throw can be folded into the first.
    484 % Is this due to optimization?
    485 \item
    486 Both types of \CFA are slightly slower if there is not a match.
    487 For termination this likely comes from unwinding a bit more stack through
    488 libunwind instead of executing the code normally.
    489 For resumption there is extra work in traversing more of the list and running
    490 more checks for a matching exceptions.
    491 % Resumption is a bit high for that but this is my best theory.
    492 \item
    493 Then there is \Cpp, which takes 2--3 times longer to catch and rethrow vs.
    494 just the catch. This is very high, but it does have to repeat the same
    495 process of unwinding the stack and may have to parse the LSDA of the function
    496 with the catch and rethrow twice, once before the catch and once after the
    497 rethrow.
    498 % I spent a long time thinking of what could push it over twice, this is all
    499 % I have to explain it.
    500 \end{itemize}
    501 The difference in relative performance does show that there are savings to
    502 be made by performing the check without catching the exception.
    503 \end{comment}
    504 
    505 
    506 \begin{comment}
    507 From: Dave Dice <dave.dice@oracle.com>
    508 To: "Peter A. Buhr" <pabuhr@uwaterloo.ca>
    509 Subject: Re: [External] : JIT
    510 Date: Mon, 16 Aug 2021 01:21:56 +0000
    511 
    512 > On 2021-8-15, at 7:14 PM, Peter A. Buhr <pabuhr@uwaterloo.ca> wrote:
    513 >
    514 > My student is trying to measure the cost of installing a try block with a
    515 > finally clause in Java.
    516 >
    517 > We tried the random trick (see below). But if the try block is comment out, the
    518 > results are the same. So the program measures the calls to the random number
    519 > generator and there is no cost for installing the try block.
    520 >
    521 > Maybe there is no cost for a try block with an empty finally, i.e., the try is
    522 > optimized away from the get-go.
    523 
    524 There's quite a bit of optimization magic behind the HotSpot curtains for
    525 try-finally.  (I sound like the proverbial broken record (:>)).
    526 
    527 In many cases we can determine that the try block can't throw any exceptions,
    528 so we can elide all try-finally plumbing.  In other cases, we can convert the
    529 try-finally to normal if-then control flow, in the case where the exception is
    530 thrown into the same method.  This makes exceptions _almost cost-free.  If we
    531 actually need to "physically" rip down stacks, then things get expensive,
    532 impacting both the throw cost, and inhibiting other useful optimizations at the
    533 catch point.  Such "true" throws are not just expensive, they're _very
    534 expensive.  The extremely aggressive inlining used by the JIT helps, because we
    535 can convert cases where a heavy rip-down would normally needed back into simple
    536 control flow.
    537 
    538 Other quirks involve the thrown exception object.  If it's never accessed then
    539 we're apply a nice set of optimizations to avoid its construction.  If it's
    540 accessed but never escapes the catch frame (common) then we can also cheat.
    541 And if we find we're hitting lots of heavy rip-down cases, the JIT will
    542 consider recompilation - better inlining -- to see if we can merge the throw
    543 and catch into the same physical frame, and shift to simple branches.
    544 
    545 In your example below, System.out.print() can throw, I believe.  (I could be
    546 wrong, but most IO can throw).  Native calls that throw will "unwind" normally
    547 in C++ code until they hit the boundary where they reenter java emitted code,
    548 at which point the JIT-ed code checks for a potential pending exception.  So in
    549 a sense the throw point is implicitly after the call to the native method, so
    550 we can usually make those cases efficient.
    551 
    552 Also, when we're running in the interpreter and warming up, we'll notice that
    553 the == 42 case never occurs, and so when we start to JIT the code, we elide the
    554 call to System.out.print(), replacing it (and anything else which appears in
    555 that if x == 42 block) with a bit of code we call an "uncommon trap".  I'm
    556 presuming we encounter 42 rarely.  So if we ever hit the x == 42 case, control
    557 hits the trap, which triggers synchronous recompilation of the method, this
    558 time with the call to System.out.print() and, because of that, we now to adapt
    559 the new code to handle any traps thrown by print().  This is tricky stuff, as
    560 we may need to rebuild stack frames to reflect the newly emitted method.  And
    561 we have to construct a weird bit of "thunk" code that allows us to fall back
    562 directly into the newly emitted "if" block.  So there's a large one-time cost
    563 when we bump into the uncommon trap and recompile, and subsequent execution
    564 might get slightly slower as the exception could actually be generated, whereas
    565 before we hit the trap, we knew the exception could never be raised.
    566 
    567 Oh, and things also get expensive if we need to actually fill in the stack
    568 trace associated with the exception object.  Walking stacks is hellish.
    569 
    570 Quite a bit of effort was put into all this as some of the specjvm benchmarks
    571 showed significant benefit.
    572 
    573 It's hard to get sensible measurements as the JIT is working against you at
    574 every turn.  What's good for the normal user is awful for anybody trying to
    575 benchmark.  Also, all the magic results in fairly noisy and less reproducible
    576 results.
    577 
    578 Regards
    579 Dave
    580 
    581 p.s., I think I've mentioned this before, but throwing in C++ is grim as
    582 unrelated throws in different threads take common locks, so nothing scales as
    583 you might expect.
    584 \end{comment}
     391Moving on to resumption there is one general note,
     392resumption is \textit{fast}, the only test where it fell
     393behind termination is Cross Handler.
     394In every other case, the number of iterations had to be increased by a
     395factor of 10 to get the run-time in an approprate range
     396and in some cases resumption still took less time.
     397
     398% I tried \paragraph and \subparagraph, maybe if I could adjust spacing
     399% between paragraphs those would work.
     400\begin{description}
     401\item[Empty Traversal]
     402See above for the general speed-up notes.
     403This result is not surprising as resumption's link list approach
     404means that traversing over stack frames without a resumption handler is
     405$O(1)$.
     406
     407\item[D'tor Traversal]
     408Resumption does have the same spike in run-time that termination has.
     409The run-time is actually very similar to Finally Traversal.
     410As resumption does not unwind the stack both destructors and finally
     411clauses are run while walking down the stack normally.
     412So it follows their performance is similar.
     413
     414\item[Finally Traversal]
     415The increase in run-time fromm Empty Traversal (once adjusted for
     416the number of iterations) roughly the same as for termination.
     417This suggests that the
     418
     419\item[Other Traversal]
     420Traversing across handlers reduces resumption's advantage as it actually
     421has to stop and check each one.
     422Resumption still came out ahead (adjusting for iterations) but by much less
     423than the other cases.
     424
     425\item[Cross Handler]
     426The only test case where resumption could not keep up with termination,
     427although the difference is not as significant as many other cases.
     428It is simply a matter of where the costs come from. Even if \CFA termination
     429is not ``zero-cost" passing through an empty function still seems to be
     430cheaper than updating global values.
     431
     432\item[Conditional Match]
     433Resumption shows a slight slowdown if the exception is not matched
     434by the first handler, which follows from the fact the second handler now has
     435to be checked. However the difference is not large.
     436
     437\end{description}
     438
     439Finally are the results of the resumption/fixup routine comparison.
     440These results are surprisingly varied, it is possible that creating a closure
     441has more to do with performance than passing the argument through layers of
     442calls.
     443Even with 100 stack frames though, resumption is only about as fast as
     444manually passing a fixup routine.
     445So there is a cost for the additional power and flexibility exceptions
     446provide.
  • doc/theses/andrew_beach_MMath/uw-ethesis.tex

    r1d402be reaeca5f  
    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}}
Note: See TracChangeset for help on using the changeset viewer.