Changeset 7372065 for doc


Ignore:
Timestamp:
Aug 21, 2021, 5:49:45 PM (3 years ago)
Author:
Andrew Beach <ajbeach@…>
Branches:
ADT, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, pthread-emulation, qualifiedEnum
Children:
c2a9d88
Parents:
d8f8d08
Message:

Saved and reverted another set of Peter's changes.

Location:
doc/theses/andrew_beach_MMath
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/andrew_beach_MMath/conclusion.tex

    rd8f8d08 r7372065  
    11\chapter{Conclusion}
    2 \label{c:conclusion}
    32% Just a little knot to tie the paper together.
    43
    5 In the previous chapters this thesis presents the design and implementation of
    6 \CFA's EHM.  Both the design and implementation are based off of tools and
    7 techniques developed for other programming languages but they were adapted to
    8 better fit \CFA's feature set and add a few features that do not exist in other
    9 EHMs, like conditional catch, default handlers, implicitly changing resumption
    10 into termination in the resumption default handler, and cancellation through
    11 coroutines and threads back to program main.
     4In the previous chapters this thesis presents the design and implementation
     5of \CFA's exception handling mechanism (EHM).
     6Both the design and implementation are based off of tools and techniques
     7developed for other programming languages but they were adapted to better fit
     8\CFA's feature set.
    129
    1310The resulting features cover all of the major use cases of the most popular
    1411termination EHMs of today, along with reintroducing resumption exceptions and
    15 creating some new features that fit with \CFA's larger programming patterns,
    16 such as virtuals independent of traditional objects.
     12creating some new features that fix with \CFA's larger programming patterns.
    1713
    18 The implementation has been tested through a set of small but interesting micro-benchmarks
    19 and compared to other implementations.
     14The implementation has been tested and compared to other implementations.
    2015The results, while not cutting edge, are good enough for prototyping, which
    21 is \CFA's current stage of development.
     16is \CFA's stage of development.
    2217
    23 This initial EHM is a valuable new feature for \CFA in its own right but also serves
    24 as a tool and motivation for other developments in the language.
     18This is a valuable new feature for \CFA in its own right but also serves
     19as a tool (and motivation) for other developments in the language.

  • doc/theses/andrew_beach_MMath/future.tex

    rd8f8d08 r7372065  
    22\label{c:future}
    33
    4 The following discussion covers both missing language features that affected my
    5 work and research based improvements.
    6 
    74\section{Language Improvements}
    8 
     5\todo{Future/Language Improvements seems to have gotten mixed up. It is
     6presented as ``waiting on language improvements" but really its more
     7non-research based impovements.}
    98\CFA is a developing programming language. As such, there are partially or
    10 unimplemented features (including several broken components)
    11 that I had to workaround while building an EHM largely in
     9unimplemented features of the language (including several broken components)
     10that I had to workaround while building an exception handling system largely in
    1211the \CFA language (some C components).  The following are a few of these
    1312issues, and once implemented/fixed, how they would affect the exception system.
    … …  
    1514\item
    1615The 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.
     16hand-crafted assembly statements.
     17The existing compilers cannot translate that for other platforms and those
     18sections must be ported by hand to
     19support more hardware architectures, such as the ARM processor.
    2220\item
    2321Due to a type-system problem, the catch clause cannot bind the exception to a
    … …  
    2927@return@, \etc. The reason is that current code generation hoists a handler
    3028into 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.
     29@try@ statement). Hence, when the handler runs, its code is not in the lexical
     30scope of the @try@ statement, where the local control-flow transfers are
     31meaningful.
    3532\item
    3633There is no detection of colliding unwinds. It is possible for clean-up code
    3734run during an unwind to trigger another unwind that escapes the clean-up code
    3835itself; 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
     36cancellation. There do exist ways to handle this but currently they are not
     37even detected and the first unwind will simply be forgotten, often leaving
    4138it in a bad state.
    4239\item
    43 Finally, the exception system has not have a lot programmer testing.
    44 More time with encouraged usage will reveal new
    45 quality of life upgrades that can be made.
     40Also the exception system did not have a lot of time to be tried and tested.
     41So just letting people use the exception system more will reveal new
     42quality of life upgrades that can be made with time.
    4643\end{itemize}
    4744
    … …  
    5047project, but was thrust upon it to do exception inheritance; hence, only
    5148minimal 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
     49it is not finalized.  A future \CFA project is to complete that work and then
    5350update the exception system that uses the current version.
    5451
    … …  
    5653exception traits. The most important one is an assertion to check one virtual
    5754type is a child of another. This check precisely captures many of the
    58 current ad-hoc correctness requirements.
     55correctness requirements.
    5956
    6057The full virtual system might also include other improvement like associated
    6158types to allow traits to refer to types not listed in their header. This
    6259feature allows exception traits to not refer to the virtual-table type
    63 explicitly. %, removing the need for the current interface macros.
     60explicitly, removing the need for the current interface macros.
    6461
    6562\section{Additional Raises}
    … …  
    9693Checked exceptions make exceptions part of a function's type by adding an
    9794exception signature. An exception signature must declare all checked
    98 exceptions 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
     95exceptions that could propagate from the function (either because they were
     96raised inside the function or came from a sub-function). This improves safety
    10097by making sure every checked exception is either handled or consciously
    10198passed on.
    10299
    103100However checked exceptions were never seriously considered for this project
    104 because they have significant trade-offs in usability and code reuse in
     101because they have significant trade-offs in usablity and code reuse in
    105102exchange for the increased safety.
    106103These trade-offs are most problematic when trying to pass exceptions through
    … …  
    132129not support a successful-exiting stack-search without doing an unwind.
    133130Workarounds are possible but awkward. Ideally an extension to libunwind could
    134 be made, but that would either require separate maintenance or gaining enough
    135 support to have it folded into the code base.
     131be made, but that would either require separate maintenance or gain enough
     132support to have it folded into the standard.
    136133
    137134Also new techniques to skip previously searched parts of the stack need to be
    … …  
    161158to leave the handler.
    162159Currently, mimicking this behaviour in \CFA is possible by throwing a
    163 termination exception inside a resumption handler.
     160termination inside a resumption handler.
    164161
    165162% Maybe talk about the escape; and escape CONTROL_STMT; statements or how

  • doc/theses/andrew_beach_MMath/implement.tex

    rd8f8d08 r7372065  
    2020
    2121\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.
     22Virtual types only have one change to their structure: the addition of a
     23pointer to the virtual table, which is called the \emph{virtual-table pointer}.
     24Internally, the field is called \snake{virtual_table}.
     25The field is fixed after construction. It is always the first field in the
     26structure so that its location is always known.
    2827\todo{Talk about constructors for virtual types (after they are working).}
    2928
     29The virtual table pointer binds an instance of a virtual type
     30to a virtual table.
     31The pointer is also the table's id and how the system accesses the
     32virtual table and the virtual members there.
     33
    3034\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.
    41 
    42 The 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 
     35Every virtual type has a unique id.
     36Type ids can be compared for equality,
     37which checks if the types reperented are the same,
     38or used to access the type's type information.
    8939The type information currently is only the parent's type id or, if the
    9040type has no parent, the null pointer.
     41
     42The id's are implemented as pointers to the type's type information instance.
     43Dereferencing the pointer gets the type information.
    9144The ancestors of a virtual type are found by traversing type ids through
    9245the type information.
    93 An example using helper macros looks like:
     46The information pushes the issue of creating a unique value (for
     47the type id) to the problem of creating a unique instance (for type
     48information), which the linker can solve.
     49
     50The advanced linker support is used here to avoid having to create
     51a new declaration to attach this data to.
     52With C/\CFA's header/implementation file divide for something to appear
     53exactly once it must come from a declaration that appears in exactly one
     54implementation file; the declarations in header files may exist only once
     55they can be included in many different translation units.
     56Therefore, structure's declaration will not work.
     57Neither will attaching the type information to the virtual table -- although
     58a vtable declarations are in implemention files they are not unique, see
     59\autoref{ss:VirtualTable}.
     60Instead the same type information is generated multiple times and then
     61the new attribute \snake{cfa_linkone} is used to removed duplicates.
     62
     63Type information is constructed as follows:
     64\begin{enumerate}
     65\item
     66Use the type's name to generate a name for the type information structure.
     67This is saved so it may be reused.
     68\item
     69Generate a new structure definition to store the type
     70information. The layout is the same in each case, just the parent's type id,
     71but the types used change from instance to instance.
     72The generated name is used for both this structure and, if relivant, the
     73parent pointer.
     74If the virtual type is polymorphic then the type information structure is
     75polymorphic as well, with the same polymorphic arguments.
     76\item
     77A seperate name for instances is generated from the type's name.
     78\item
     79The definition is generated and initialised.
     80The parent id is set to the null pointer or to the address of the parent's
     81type information instance. Name resolution handles the rest.
     82\item
     83\CFA's name mangler does its regular name mangling encoding the type of
     84the declaration into the instance name. This gives a completely unique name
     85including different instances of the same polymorphic type.
     86\end{enumerate}
     87\todo{The list is making me realise, some of this isn't ordered.}
     88
     89Writing that code manually, with helper macros for the early name mangling,
     90would look like this:
    9491\begin{cfa}
    9592struct INFO_TYPE(TYPE) {
    … …  
    103100\end{cfa}
    104101
    105 The type information is constructed as follows:
    106 \begin{enumerate}
    107 \item
    108 Use the type's name to generate a name for the type information structure,
    109 which is saved so it can be reused.
    110 \item
    111 Generate a new structure definition to store the type
    112 information. The layout is the same in each case, just the parent's type id,
    113 but the types used change from instance to instance.
    114 The generated name is used for both this structure and, if relevant, the
    115 parent pointer.
    116 If the virtual type is polymorphic then the type information structure is
    117 polymorphic as well, with the same polymorphic arguments.
    118 \item
    119 A separate name for instances is generated from the type's name.
    120 \item
    121 The definition is generated and initialized.
    122 The parent id is set to the null pointer or to the address of the parent's
    123 type information instance. Name resolution handles the rest.
    124 \item
    125 \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
    127 including different instances of the same polymorphic type.
    128 \end{enumerate}
    129 \todo{The list is making me realize, some of this isn't ordered.}
    130 
    131 
    132 \begin{comment}
    133102\subsubsection{\lstinline{cfa\_linkonce} Attribute}
    134 % I just realized: This is an extension of the inline keyword.
     103% I just realised: This is an extension of the inline keyword.
    135104% An extension of C's at least, it is very similar to C++'s.
    136105Another feature added to \CFA is a new attribute: \texttt{cfa\_linkonce}.
    … …  
    157126everything that comes after the special prefix, then only one is used
    158127and the other is discarded.
    159 \end{comment}
    160 
    161128
    162129\subsection{Virtual Table}
    … …  
    191158The first and second sections together mean that every virtual table has a
    192159prefix 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
     160This, combined with the fixed offset to the virtual table pointer, means that
    194161for any virtual type, it is always safe to access its virtual table and,
    195162from there, it is safe to check the type id to identify the exact type of the
    … …  
    209176type's alignment, is set using an @alignof@ expression.
    210177
    211 \subsection{Concurrency Integration}
     178\subsubsection{Concurrency Integration}
    212179Coroutines and threads need instances of @CoroutineCancelled@ and
    213180@ThreadCancelled@ respectively to use all of their functionality. When a new
    … …  
    216183at the definition of the main function.
    217184
    218 These transformations are shown through code re-writing in
    219 \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.
     185This is showned through code re-writing in
     186\autoref{f:ConcurrencyTypeTransformation} and
     187\autoref{f:ConcurrencyMainTransformation}.
     188In both cases the original declaration is not modified,
     189only new ones are added.
    223190
    224191\begin{figure}
    … …  
    240207extern CoroutineCancelled_vtable & _default_vtable;
    241208\end{cfa}
    242 \caption{Coroutine Type Transformation}
    243 \label{f:CoroutineTypeTransformation}
    244 %\end{figure}
    245 
    246 \bigskip
    247 
    248 %\begin{figure}
     209\caption{Concurrency Type Transformation}
     210\label{f:ConcurrencyTypeTransformation}
     211\end{figure}
     212
     213\begin{figure}
    249214\begin{cfa}
    250215void main(Example & this) {
    … …  
    264229        &_default_vtable_object_declaration;
    265230\end{cfa}
    266 \caption{Coroutine Main Transformation}
    267 \label{f:CoroutineMainTransformation}
     231\caption{Concurrency Main Transformation}
     232\label{f:ConcurrencyMainTransformation}
    268233\end{figure}
    269234
    … …  
    280245        struct __cfavir_type_id const * child );
    281246\end{cfa}
    282 The type id for the target type of the virtual cast is passed in as @parent@ and
     247The type id of target type of the virtual cast is passed in as @parent@ and
    283248the cast target is passed in as @child@.
    284 The generated C code wraps both arguments and the result with type casts.
     249
     250For generated C code wraps both arguments and the result with type casts.
    285251There is also an internal check inside the compiler to make sure that the
    286252target type is a virtual type.
    … …  
    294260
    295261\section{Exceptions}
    296 \todo{Anything about exception construction.}
     262% Anything about exception construction.
    297263
    298264\section{Unwinding}
    … …  
    308274stack. On function entry and return, unwinding is handled directly by the
    309275call/return code embedded in the function.
    310 \PAB{Meaning: In many cases, the position of the instruction pointer (relative to parameter
     276In many cases, the position of the instruction pointer (relative to parameter
    311277and local declarations) is enough to know the current size of the stack
    312 frame.}
     278frame.
    313279
    314280Usually, the stack-frame size is known statically based on parameter and
    315 local variable declarations. Even for a dynamic stack-size, the information
     281local variable declarations. Even with dynamic stack-size, the information
    316282to determine how much of the stack has to be removed is still contained
    317283within the function.
    … …  
    319285bumping the hardware stack-pointer up or down as needed.
    320286Constructing/destructing values within a stack frame has
    321 a similar complexity but larger constants, which takes longer.
     287a similar complexity but can add additional work and take longer.
    322288
    323289Unwinding across multiple stack frames is more complex because that
    324290information 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).
     291With seperate compilation a function has no way of knowing what its callers
     292are so it can't know how large those frames are.
    328293Without altering the main code path it is also hard to pass that work off
    329294to the caller.
    … …  
    337302This approach is fragile and requires extra work in the surrounding code.
    338303
    339 With respect to the extra work in the surrounding code,
     304With respect to the extra work in the surounding code,
    340305many languages define clean-up actions that must be taken when certain
    341306sections 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
     307is removed from the stack or when a try statement with a finally clause is
    343308(conceptually) popped from the stack.
    344 None of these cases should be handled by the user --- that would contradict the
     309None of these should be handled by the user --- that would contradict the
    345310intention of these features --- so they need to be handled automatically.
    346311
    … …  
    390355in this case @clean_up@, run when the variable goes out of scope.
    391356This feature is enough to mimic destructors,
    392 but not try statements that affect
     357but not try statements which can effect
    393358the unwinding.
    394359
    395360To get full unwinding support, all of these features must be handled directly
    396 in assembly and assembler directives; particularly the cfi directives
     361in assembly and assembler directives; partiularly the cfi directives
    397362\snake{.cfi_lsda} and \snake{.cfi_personality}.
    398363
    … …  
    434399@_UA_FORCE_UNWIND@ specifies a forced unwind call. Forced unwind only performs
    435400the cleanup phase and uses a different means to decide when to stop
    436 (see \autoref{s:ForcedUnwind}).
     401(see \vref{s:ForcedUnwind}).
    437402\end{enumerate}
    438403
    439404The @exception_class@ argument is a copy of the
    440405\code{C}{exception}'s @exception_class@ field,
    441 which is a number that identifies the EHM
     406which is a number that identifies the exception handling mechanism
    442407that created the exception.
    443408
    … …  
    529494needs its own exception context.
    530495
    531 An exception context is retrieved by calling the function
     496The exception context should be retrieved by calling the function
    532497\snake{this_exception_context}.
    533498For sequential execution, this function is defined as
    … …  
    554519The first step of a termination raise is to copy the exception into memory
    555520managed by the exception system. Currently, the system uses @malloc@, rather
    556 than reserved memory or the stack top. The EHM manages
     521than reserved memory or the stack top. The exception handling mechanism manages
    557522memory for the exception as well as memory for libunwind and the system's own
    558523per-exception storage.
    … …  
    653618\subsection{Try Statements and Catch Clauses}
    654619The try statement with termination handlers is complex because it must
    655 compensate for the C code-generation versus proper
     620compensate for the C code-generation versus
    656621assembly-code generated from \CFA. Libunwind
    657622requires an LSDA and personality function for control to unwind across a
    … …  
    659624
    660625The 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.
     626library. The contents of a try block and the termination handlers are converted
     627into functions. These are then passed to the try terminate function and it
     628calls them.
    664629Because this function is known and fixed (and not an arbitrary function that
    665 happens to contain a try statement), its LSDA can be generated ahead
     630happens to contain a try statement), the LSDA can be generated ahead
    666631of time.
    667632
    668 Both the LSDA and the personality function for @__cfaehm_try_terminate@ are set ahead of time using
     633Both the LSDA and the personality function are set ahead of time using
    669634embedded assembly. This assembly code is handcrafted using C @asm@ statements
    670635and contains
    671 enough information for a single try statement the function represents.
     636enough information for a single try statement the function repersents.
    672637
    673638The three functions passed to try terminate are:
    … …  
    681646decides if a catch clause matches the termination exception. It is constructed
    682647from 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
     648in turn, first checking to see if the exception type matches and then if the
     649condition is true. It takes a pointer to the exception and returns 0 if the
    688650exception is not handled here. Otherwise the return value is the id of the
    689651handler that matches the exception.
    … …  
    698660All three functions are created with GCC nested functions. GCC nested functions
    699661can 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
     662in other words functions that can refer to the state of other
     663functions on the stack. This approach allows the functions to refer to all the
    702664variables in scope for the function containing the @try@ statement. These
    703665nested functions and all other functions besides @__cfaehm_try_terminate@ in
    … …  
    707669
    708670\autoref{f:TerminationTransformation} shows the pattern used to transform
    709 a \CFA try statement with catch clauses into the appropriate C functions.
     671a \CFA try statement with catch clauses into the approprate C functions.
    710672\todo{Explain the Termination Transformation figure.}
    711673
    … …  
    776738Instead of storing the data in a special area using assembly,
    777739there is just a linked list of possible handlers for each stack,
    778 with each node on the list representing a try statement on the stack.
     740with each node on the list reperenting a try statement on the stack.
    779741
    780742The head of the list is stored in the exception context.
    … …  
    782744to the head of the list.
    783745Instead of traversing the stack, resumption handling traverses the list.
    784 At each node, the EHM checks to see if the try statement the node represents
     746At each node, the EHM checks to see if the try statement the node repersents
    785747can handle the exception. If it can, then the exception is handled and
    786748the operation finishes, otherwise the search continues to the next node.
    787749If the search reaches the end of the list without finding a try statement
    788750that can handle the exception, the default handler is executed and the
    789 operation finishes, unless it throws an exception.
     751operation finishes.
    790752
    791753Each node has a handler function that does most of the work.
    792754The handler function is passed the raised exception and returns true
    793755if the exception is handled and false otherwise.
     756
    794757The handler function checks each of its internal handlers in order,
    795758top-to-bottom, until it funds a match. If a match is found that handler is
    … …  
    797760If no match is found the function returns false.
    798761The 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.}
     762if the thrown exception is an instance of the declared exception or one of
     763its descendant type, then check to see if passes the custom predicate if one
     764is defined. This ordering gives the type guarantee used in the predicate.
    803765
    804766\autoref{f:ResumptionTransformation} shows the pattern used to transform
    805 a \CFA try statement with catch clauses into the appropriate C functions.
     767a \CFA try statement with catch clauses into the approprate C functions.
    806768\todo{Explain the Resumption Transformation figure.}
    807769
    … …  
    852814(see \vpageref{s:ResumptionMarking}), which ignores parts of
    853815the 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
     816already examined, is accomplished by updating the front of the list as the
     817search continues. Before the handler at a node is called, the head of the list
    856818is updated to the next node of the current node. After the search is complete,
    857819successful or not, the head of the list is reset.
    … …  
    860822been checked are not on the list while a handler is run. If a resumption is
    861823thrown during the handling of another resumption, the active handlers and all
    862 the other handlers checked up to this point are not checked again.
     824the other handler checked up to this point are not checked again.
    863825% No paragraph?
    864826This structure also supports new handlers added while the resumption is being
    … …  
    868830
    869831\begin{figure}
    870 \centering
    871832\input{resumption-marking}
    872833\caption{Resumption Marking}
    … …  
    890851\section{Finally}
    891852% 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
    896 then 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.
    899 
    900 \begin{figure}
    901 \begin{cfa}
    902 try {
    903         // TRY BLOCK
    904 } finally {
    905         // FINALLY BLOCK
    906 }
    907 \end{cfa}
    908 
    909 \transformline
    910 
    911 \begin{cfa}
    912 {
    913         void finally(void *__hook){
    914                 // FINALLY BLOCK
    915         }
    916         __attribute__ ((cleanup(finally)))
    917         struct __cfaehm_cleanup_hook __finally_hook;
    918         {
    919                 // TRY BLOCK
    920         }
    921 
    922 }
    923 \end{cfa}
    924 
    925 \caption{Finally Transformation}
    926 \label{f:FinallyTransformation}
    927 \end{figure}
     853A finally clause is placed into a GCC nested-function with a unique name,
     854and no arguments or return values.
     855This nested function is then set as the cleanup
     856function of an empty object that is declared at the beginning of a block placed
     857around the context of the associated @try@ statement.
    928858
    929859The rest is handled by GCC. The try block and all handlers are inside this
    … …  
    939869
    940870The first step of cancellation is to find the cancelled stack and its type:
    941 coroutine, thread, or main thread.
     871coroutine, thread or main thread.
    942872In \CFA, a thread (the construct the user works with) is a user-level thread
    943873(point of execution) paired with a coroutine, the thread's main coroutine.
    944874The thread library also stores pointers to the main thread and the current
    945 coroutine.
     875thread.
    946876If the current thread's main and current coroutines are the same then the
    947877current stack is a thread stack, otherwise it is a coroutine stack.
    … …  
    957887passed to the forced-unwind function. The general pattern of all three stop
    958888functions is the same: continue unwinding until the end of stack and
    959 then perform the appropriate transfer.
     889then preform the appropriate transfer.
    960890
    961891For main stack cancellation, the transfer is just a program abort.

  • doc/theses/andrew_beach_MMath/performance.tex

    rd8f8d08 r7372065  
    22\label{c:performance}
    33
    4 Performance is of secondary importance for most of this project.
    5 Instead, the focus was to get the features working. The only performance
    6 requirement is to ensure the tests for correctness run in a reasonable
    7 amount of time. Hence, a few basic performance tests were performed to
    8 check this requirement.
     4Performance has been of secondary importance for most of this project.
     5Instead, the focus has been to get the features working. The only performance
     6requirements is to ensure the tests for correctness run in a reasonable
     7amount of time.
    98
    109\section{Test Set-Up}
    11 Tests were run in \CFA, C++, Java and Python.
     10Tests will be run in \CFA, C++, Java and Python.
    1211In addition there are two sets of tests for \CFA,
    13 one for termination and one for resumption exceptions.
     12one for termination exceptions and once with resumption exceptions.
    1413
    1514C++ is the most comparable language because both it and \CFA use the same
    1615framework, libunwind.
    17 In fact, the comparison is almost entirely a quality of implementation.
    18 Specifically, \CFA's EHM has had significantly less time to be optimized and
     16In fact, the comparison is almost entirely a quality of implementation
     17comparison. \CFA's EHM has had significantly less time to be optimized and
    1918does 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,
    21 but otherwise \Cpp should have a significant advantage.
    22 
    23 Java is a popular language with similar termination semantics, but
    24 it is implemented in a very different environment, a virtual machine with
     19there are some features it does not handle, through utility functions,
     20but otherwise \Cpp has a significant advantage.
     21
     22Java is another very popular language with similar termination semantics.
     23It is implemented in a very different environment, a virtual machine with
    2524garbage collection.
    26 It also implements the @finally@ clause on @try@ blocks allowing for a direct
     25It also implements the finally clause on try blocks allowing for a direct
    2726feature-to-feature comparison.
    28 As with \Cpp, Java's implementation is mature, optimized
    29 and has extra features.
    30 
    31 Python 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
     27As with \Cpp, Java's implementation is more mature, has more optimizations
     28and more extra features.
     29
     30Python was used as a point of comparison because of the \CFA EHM's
     31current performance goals, which is not be prohibitively slow while the
    3332features are designed and examined. Python has similar performance goals for
    3433creating quick scripts and its wide use suggests it has achieved those goals.
    3534
    36 Unfortunately, there are no notable modern programming languages with
    37 resumption exceptions. Even the older programming languages with resumption
    38 seem 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.
    44 
    45 All tests are run inside a main loop that repeatedly performs a test.
    46 This approach avoids start-up or tear-down time from
     35Unfortunately there are no notable modern programming languages with
     36resumption exceptions. Even the older programming languages with resumptions
     37seem to be notable only for having resumptions.
     38So instead resumptions are compared to a less similar but much more familiar
     39feature, termination exceptions.
     40
     41All tests are run inside a main loop which will perform the test
     42repeatedly. This is to avoids start-up or tear-down time from
    4743affecting the timing results.
    48 Each test is run a N times (configurable from the command line).
    49 The Java tests runs the main loop 1000 times before
    50 beginning the actual test to ``warm-up" the JVM.
     44Tests ran their main loop a million times.
     45The Java versions of the test also run this loop an extra 1000 times before
     46beginning to time the results to ``warm-up" the JVM.
    5147
    5248Timing is done internally, with time measured immediately before and
    53 after the test loop. The difference is calculated and printed.
     49immediately after the test loop. The difference is calculated and printed.
     50
    5451The loop structure and internal timing means it is impossible to test
    5552unhandled exceptions in \Cpp and Java as that would cause the process to
    … …  
    5855critical.
    5956
    60 The exceptions used in these tests are always based off of
    61 a base exception. This requirement minimizes performance differences based
    62 on the object model used to represent the exception.
    63 
    64 All tests are designed to be as minimal as possible, while still preventing
    65 excessive optimizations.
     57The exceptions used in these tests will always be a exception based off of
     58the base exception. This requirement minimizes performance differences based
     59on the object model used to repersent the exception.
     60
     61All tests were designed to be as minimal as possible while still preventing
     62exessive optimizations.
    6663For example, empty inline assembly blocks are used in \CFA and \Cpp to
    6764prevent 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 
    8265
    8366% We don't use catch-alls but if we did:
    … …  
    8871The following tests were selected to test the performance of different
    8972components of the exception system.
    90 They should provide a guide as to where the EHM's costs are found.
     73The should provide a guide as to where the EHM's costs can be found.
    9174
    9275\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}]{@}{@}}]
    97 void unwind_empty(unsigned int frames) {
    98         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.
     76The first group of tests involve setting up
     77So there is three layers to the test. The first is set up and a loop, which
     78configures the test and then runs it repeatedly to reduce the impact of
     79start-up and shutdown on the results.
     80Each iteration of the main loop
    10581\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);
    119         } else {
    120                 int fixup = 17;
    121                 raised_rtn(fixup);
    122         }
    123 }
    124 \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.
     82\item Empty Function:
     83The repeating function is empty except for the necessary control code.
    13284\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}
     85The repeating function creates an object with a destructor before calling
     86itself.
    14587\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.
     88The repeating function calls itself inside a try block with a finally clause
     89attached.
    15890\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.
     91The repeating function calls itself inside a try block with a handler that
     92will not match the raised exception. (But is of the same kind of handler.)
    17393\end{itemize}
    17494
    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}
     95\paragraph{Cross Try Statement}
     96The next group measures the cost of a try statement when no exceptions are
     97raised. The test is set-up, then there is a loop to reduce the impact of
     98start-up and shutdown on the results.
     99In each iteration, a try statement is executed. Entering and leaving a loop
     100is all the test wants to do.
    183101\begin{itemize}[nosep]
    184102\item Handler:
    185 The try statement has a handler (catch/resume).
     103The try statement has a handler (of the matching kind).
    186104\item Finally:
    187105The try statement has a finally clause.
    … …  
    189107
    190108\paragraph{Conditional Matching}
    191 This group measures the cost of conditional matching.
     109This group of tests checks the cost of conditional matching.
    192110Only \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
     111the other languages must mimic with an ``unconditional" match (it still
     112checks the exception's type) and conditional re-raise if it was not supposed
    195113to handle that exception.
    196 \begin{center}
    197 \begin{tabular}{ll}
    198 \multicolumn{1}{c}{\CFA} & \multicolumn{1}{c}{\Cpp, Java, Python} \\
    199 \begin{cfa}
    200 try {
    201         throw_exception();
    202 } catch (empty_exception * exc;
    203                  should_catch) {
    204 }
    205 \end{cfa}
    206 &
    207 \begin{cfa}
    208 try {
    209         throw_exception();
    210 } catch (EmptyException & exc) {
    211         if (!should_catch) throw;
    212 }
    213 \end{cfa}
    214 \end{tabular}
    215 \end{center}
    216114\begin{itemize}[nosep]
    217115\item Match All:
    … …  
    221119\end{itemize}
    222120
    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}.
    227 
    228121%\section{Cost in Size}
    229122%Using exceptions also has a cost in the size of the executable.
    … …  
    237130
    238131\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.
     132Each test was run eleven times. The top three and bottom three results were
     133discarded and the remaining five values are averaged.
     134
     135In cases where a feature is not supported by a language the test is skipped
     136for that language. Similarly, if a test is does not change between resumption
     137and termination in \CFA, then only one test is written and the result
     138was put into the termination column.
    285139
    286140% Raw Data:
    … …  
    318172% Match None    & 0.0 & 0.0 &  9476060146 & 0.0 & 0.0 \\
    319173
     174\begin{tabular}{|l|c c c c c|}
     175\hline
     176              & \CFA (Terminate) & \CFA (Resume) & \Cpp & Java & Python \\
     177\hline
     178Raise Empty   & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
     179Raise D'tor   & 0.0 & 0.0 & 0.0 & N/A & N/A \\
     180Raise Finally & 0.0 & 0.0 & N/A & 0.0 & 0.0 \\
     181Raise Other   & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
     182Cross Handler & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
     183Cross Finally & 0.0 & N/A & N/A & 0.0 & 0.0 \\
     184Match All     & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
     185Match None    & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
     186\hline
     187\end{tabular}
     188
    320189% run-plg7a-a.sat
    321190% ---------------
    … …  
    352221% Match None    & 0.0 & 0.0 &  7829059869 & 0.0 & 0.0 \\
    353222
    354 \begin{table}
    355 \centering
    356 \caption{Performance Results Termination (sec)}
    357 \label{t:PerformanceTermination}
    358 \begin{tabular}{|r|*{2}{|r r r r|}}
    359 \hline
    360                         & \multicolumn{4}{c||}{AMD}             & \multicolumn{4}{c|}{ARM}      \\
    361 \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   \\
     223% PLG7A (in seconds)
     224\begin{tabular}{|l|c c c c c|}
     225\hline
     226              & \CFA (Terminate) & \CFA (Resume) & \Cpp & Java & Python \\
     227\hline
     228Raise Empty   & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
     229Raise D'tor   & 0.0 & 0.0 & 0.0 & N/A & N/A \\
     230Raise Finally & 0.0 & 0.0 & N/A & 0.0 & 0.0 \\
     231Raise Other   & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
     232Cross Handler & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
     233Cross Finally & 0.0 & N/A & N/A & 0.0 & 0.0 \\
     234Match All     & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
     235Match None    & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
    373236\hline
    374237\end{tabular}
    375 \end{table}
    376 
    377 \begin{table}
    378 \centering
    379 \small
    380 \caption{Performance Results Resumption (sec)}
    381 \label{t:PerformanceResumption}
    382 \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   \\
    395 \hline
    396 \end{tabular}
    397 \end{table}
    398 
    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.
    404 \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.
    450 \end{description}
    451 
    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.
     238
     239One result that is not directly related to \CFA but is important to keep in
     240mind is that in exceptions the standard intuitions about which languages
     241should go faster often do not hold. There are cases where Python out-preforms
     242\Cpp and Java. The most likely explination is that, since exceptions are
     243rarely considered to be the common case, the more optimized langages have
     244optimized at their expence. In addition languages with high level           
     245repersentations have a much easier time scanning the stack as there is less
     246to decode.
     247
     248This means that while \CFA does not actually keep up with Python in every
     249case it is usually no worse than roughly half the speed of \Cpp. This is good
     250enough for the prototyping purposes of the project.
    456251
    457252The test case where \CFA falls short is Raise Other, the case where the
    458253stack is unwound including a bunch of non-matching handlers.
    459 This slowdown seems to come from missing optimizations.
     254This slowdown seems to come from missing optimizations,
     255the results above came from gcc/g++ 10 (gcc as \CFA backend or g++ for \Cpp)
     256but the results change if they are run in gcc/g++ 9 instead.
     257Importantly, there is a huge slowdown in \Cpp's results bringing that brings
     258\CFA's performace back in that roughly half speed area. However many other
     259\CFA benchmarks increase their run-time by a similar amount falling far
     260behind their \Cpp counter-parts.
    460261
    461262This suggests that the performance issue in Raise Other is just an
    … …  
    468269Resumption exception handling is also incredibly fast. Often an order of
    469270magnitude or two better than the best termination speed.
    470 There is a simple explanation for this; traversing a linked list is much   
     271There is a simple explination for this; traversing a linked list is much   
    471272faster 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.
     273well its when more try statements are used per raise. Updating the interal
     274linked list is not very expencive but it does add up.
    474275
    475276The relative speed of the Match All and Match None tests (within each
    … …  
    479280\item
    480281Java and Python get similar values in both tests.
    481 Between the interpreted code, a higher level representation of the call
     282Between the interperated code, a higher level repersentation of the call
    482283stack and exception reuse it it is possible the cost for a second
    483284throw can be folded into the first.
    484285% Is this due to optimization?
    485286\item
    486 Both types of \CFA are slightly slower if there is not a match.
     287Both types of \CFA are slighly slower if there is not a match.
    487288For termination this likely comes from unwinding a bit more stack through
    488289libunwind instead of executing the code normally.
    … …  
    501302The difference in relative performance does show that there are savings to
    502303be 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}
Note: See TracChangeset for help on using the changeset viewer.