Changeset b51e389c for doc/theses/andrew_beach_MMath
- Timestamp:
- Jun 15, 2021, 4:17:05 PM (3 years ago)
- Branches:
- ADT, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 6071efc
- Parents:
- 2f19e03
- Location:
- doc/theses/andrew_beach_MMath
- Files:
-
- 3 edited
-
future.tex (modified) (7 diffs)
-
implement.tex (modified) (35 diffs)
-
performance.tex (modified) (7 diffs)
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/andrew_beach_MMath/future.tex
r2f19e03 rb51e389c 7 7 that I had to workaround while building an exception handling system largely in 8 8 the \CFA language (some C components). The following are a few of these 9 issues, and once implemented/fixed, how th eywould affect the exception system.9 issues, and once implemented/fixed, how this would affect the exception system. 10 10 \begin{itemize} 11 11 \item … … 13 13 hand-crafted assembly statements. These sections must be ported by hand to 14 14 support more hardware architectures, such as the ARM processor. 15 \PAB{I think this is a straw-man problem because the hand-coded assembler code16 has to be generated somewhere, and that somewhere is hand-coded.}17 15 \item 18 16 Due to a type-system problem, the catch clause cannot bind the exception to a 19 17 reference instead of a pointer. Since \CFA has a very general reference 20 18 capability, programmers will want to use it. Once fixed, this capability should 21 result in little or no change in the exception system but simplify usage.19 result in little or no change in the exception system. 22 20 \item 23 21 Termination handlers cannot use local control-flow transfers, \eg by @break@, … … 30 28 There is no detection of colliding unwinds. It is possible for clean-up code 31 29 run during an unwind to trigger another unwind that escapes the clean-up code 32 itself , \eg,a termination exception caught further down the stack or a33 cancellation. There do exist ways to handle this issue,but currently they are not34 even detected and the first unwind is simply dropped, often leaving35 it in a bad state. \Cpp terminates the program in this case, and Java picks the ...30 itself; such as a termination exception caught further down the stack or a 31 cancellation. There do exist ways to handle this but currently they are not 32 even detected and the first unwind will simply be forgotten, often leaving 33 it in a bad state. 36 34 \item 37 35 Also the exception system did not have a lot of time to be tried and tested. … … 43 41 The virtual system should be completed. It was not supposed to be part of this 44 42 project, but was thrust upon it to do exception inheritance; hence, only 45 minimal work is done. A draft for a complete virtual system is available but43 minimal work was done. A draft for a complete virtual system is available but 46 44 it is not finalized. A future \CFA project is to complete that work and then 47 45 update the exception system that uses the current version. … … 69 67 bad software engineering. 70 68 71 Non-local/concurrent r aise requires more coordination between the concurrency system69 Non-local/concurrent requires more coordination between the concurrency system 72 70 and the exception system. Many of the interesting design decisions centre 73 around masking , \ie controlling which exceptions may be thrown at a stack. It71 around masking (controlling which exceptions may be thrown at a stack). It 74 72 would likely require more of the virtual system and would also effect how 75 73 default handlers are set. … … 87 85 88 86 \section{Checked Exceptions} 89 Checked exceptions make exceptions part of a function's type by adding an87 Checked exceptions make exceptions part of a function's type by adding the 90 88 exception signature. An exception signature must declare all checked 91 exceptions that could prop agate from the function (either because they were89 exceptions that could propogate from the function (either because they were 92 90 raised inside the function or came from a sub-function). This improves safety 93 91 by making sure every checked exception is either handled or consciously 94 92 passed on. 95 93 96 However checked exceptions were never seriously considered for this project because 97 they have significant usability and reuse trade-offs in 94 However checked exceptions were never seriously considered for this project 95 for two reasons. The first is due to time constraints, even copying an 96 existing checked exception system would be pushing the remaining time and 97 trying to address the second problem would take even longer. The second 98 problem is that checked exceptions have some real usability trade-offs in 98 99 exchange for the increased safety. 100 99 101 These trade-offs are most problematic when trying to pass exceptions through 100 102 higher-order functions from the functions the user passed into the 101 103 higher-order function. There are no well known solutions to this problem 102 that were s atisfactory for \CFA (which carries some of C's flexibility103 over safety design) so additional research is needed.104 that were statifactory for \CFA (which carries some of C's flexability 105 over safety design) so one would have to be researched and developed. 104 106 105 Follow-up work might find a compromise design for checked exceptions in\CFA, possibly using106 polymorphic exception signatures, a form of tunneling\cite{Zhang19} ,or107 Follow-up work might add checked exceptions to \CFA, possibly using 108 polymorphic exception signatures, a form of tunneling\cite{Zhang19} or 107 109 checked and unchecked raises. 108 110 … … 148 150 For instance, resumption could be extended to cover this use by allowing local 149 151 control flow out of it. This approach would require an unwind as part of the 150 transition as there are stack frames that have to be removed back to the resumption handler. This approach151 means no special statement is required in the handler to continue after it.152 Currently, \CFA allows a termination exception tobe thrown from within any resumption handler so153 there is already a way to partially mimic signal exceptions.152 transition as there are stack frames that have to be removed. This approach 153 means there is no notify raise, but because \CFA does not have exception 154 signatures, a termination can be thrown from within any resumption handler so 155 there is already a way to do mimic this in existing \CFA. 154 156 155 157 % Maybe talk about the escape; and escape CONTROL_STMT; statements or how -
doc/theses/andrew_beach_MMath/implement.tex
r2f19e03 rb51e389c 2 2 \label{c:implement} 3 3 4 The implementation work for this thesis covers t he two components:virtual4 The implementation work for this thesis covers two components: the virtual 5 5 system and exceptions. Each component is discussed in detail. 6 6 … … 17 17 pointer to the virtual table, which is called the \emph{virtual-table pointer}. 18 18 Internally, the field is called \snake{virtual_table}. 19 The field is fixed after construction and is the first field in the19 The field is fixed after construction. It is always the first field in the 20 20 structure so that its location is always known. 21 21 \todo{Talk about constructors for virtual types (after they are working).} 22 22 23 Th e virtual-table pointer is what binds an instance of a virtual type to itsvirtual table. This24 pointer is used as an identity check, and to access the23 This is what binds an instance of a virtual type to a virtual table. This 24 pointer can be used as an identity check. It can also be used to access the 25 25 virtual table and the virtual members there. 26 26 27 27 \subsection{Type Id} 28 28 Every virtual type has a unique id. 29 Type ids can be compared for equality ( \ie the types represented are the same)29 Type ids can be compared for equality (the types reperented are the same) 30 30 or used to access the type's type information. 31 31 The type information currently is only the parent's type id or, if the 32 type has no parent, @0p@.32 type has no parent, zero. 33 33 34 34 The id's are implemented as pointers to the type's type information instance. 35 Derefe rencing the pointer gets the type information.36 The ancestors of a virtual type are found by traversing the type id through 37 the type info rmation.38 An idalso pushes the issue of creating a unique value (for35 Derefencing the pointer gets the type information. 36 By going back-and-forth between the type id and 37 the type info one can find every ancestor of a virtual type. 38 It also pushes the issue of creating a unique value (for 39 39 the type id) to the problem of creating a unique instance (for type 40 information) ,which the linker can solve.40 information) which the linker can solve. 41 41 42 42 Advanced linker support is required because there is no place that appears 43 43 only once to attach the type information to. There should be one structure 44 definition but it is included in multiple translation units because of separate compilation. Each virtual45 table definition should be unique but there are an arbitrary number of th ese,46 so the special section prefix \texttt{.gnu.linkonce} is used.47 With a generated unique suffix (making the entire section name unique) the linker48 remove s multiple definition ensuringonly one version exists after linking.44 definition but it is included in multiple translation units. Each virtual 45 table definition should be unique but there are an arbitrary number of thoses. 46 So the special section prefix \texttt{.gnu.linkonce} is used. 47 With a unique suffix (making the entire section name unique) the linker will 48 remove multiple definition making sure only one version exists after linking. 49 49 Then it is just a matter of making sure there is a unique name for each type. 50 50 51 These steps are done in three phases. 52 \begin{enumerate} 53 \item 51 This is done in three phases. 54 52 The first phase is to generate a new structure definition to store the type 55 53 information. The layout is the same in each case, just the parent's type id, … … 57 55 The structure's name is change, it is based off the virtual type's name, and 58 56 the type of the parent's type id. 59 If the virtual type is polymorphic ,then the type information structure is57 If the virtual type is polymorphic then the type information structure is 60 58 polymorphic as well, with the same polymorphic arguments. 61 \item 59 62 60 The second phase is to generate an instance of the type information with a 63 61 almost unique name, generated by mangling the virtual type name. 64 \item 62 65 63 The third phase is implicit with \CFA's overloading scheme. \CFA mangles 66 64 names with type information so that all of the symbols exported to the linker 67 are unique even if in the\CFA code they are the same. Having two declarations65 are unique even if in \CFA code they are the same. Having two declarations 68 66 with the same name and same type is forbidden because it is impossible for 69 overload resolution to pick between them. This is the reasonwhy a unique type is67 overload resolution to pick between them. This is why a unique type is 70 68 generated for each virtual type. 71 69 Polymorphic information is included in this mangling so polymorphic 72 types have separate instances for each set of polymorphic arguments. 73 \end{enumerate} 74 The following example shows the components for a generated virtual type. 70 types will have seperate instances for each set of polymorphic arguments. 71 75 72 \begin{cfa} 76 73 struct TYPE_ID_TYPE { … … 84 81 \end{cfa} 85 82 86 \subsubsection{ \lstinline{cfa_linkonce}Attribute}83 \subsubsection{cfa\_linkonce Attribute} 87 84 Another feature added to \CFA is a new attribute: \texttt{cfa\_linkonce}. 88 This attribute is attached toan object or function definition89 (any global declaration with a name and a type) 90 allowing it to be definedmultiple times.91 All matching definitions must have the link-once attribute on them andshould85 This attribute can be put on an object or function definition 86 (any global declaration with a name and a type). 87 This allows you to define that object or function multiple times. 88 All definitions should have the link-once attribute on them and all should 92 89 be identical. 93 This attributed prototype is placed in a header file with other 94 forward declaration. 95 96 This technique is used for type-id instances, as there is no unique location 97 associated with a type, except for the type definition in a header. 98 The result is the unique type-id object generated by the linker. 99 100 Internally, @cfa_linkonce@ is replaced with 90 91 The simplist way to use it is to put a definition in a header where the 92 forward declaration would usually go. 93 This is how it is used for type-id instances. There was is no unique location 94 associated with a type except for the type definition which is in a header. 95 This allows the unique type-id object to be generated there. 96 97 Internally @cfa_linkonce@ removes all @section@ attributes 98 from the declaration (as well as itself) and replaces them with 101 99 @section(".gnu.linkonce.NAME")@ where \texttt{NAME} is replaced by the 102 100 mangled name of the object. 103 Any other @section@ attributes are also removed from the declaration.104 101 The prefix \texttt{.gnu.linkonce} in section names is recognized by the 105 linker. If two of these sections appearwith the same name, including everything106 that comes after the special prefix, then only one isused and the other107 discarded.102 linker. If two of these sections with the same name, including everything 103 that comes after the special prefix, then only one will be used and the other 104 will be discarded. 108 105 109 106 \subsection{Virtual Table} … … 115 112 below. 116 113 117 Figure~\ref{f:VirtualTableLayout} shows the layout is in three parts. 118 \PAB{Number the parts in the figure.} 119 \begin{enumerate} 120 \item 114 The layout always comes in three parts. 121 115 The first section is just the type id at the head of the table. It is always 122 there to ensure that \PAB{... missing text to end this sentence} 123 \item 116 there to ensure that 124 117 The second section are all the virtual members of the parent, in the same 125 118 order as they appear in the parent's virtual table. Note that the type may 126 change slightly as references to the @this@ change. This structureis limited to119 change slightly as references to the ``this" will change. This is limited to 127 120 inside pointers/references and via function pointers so that the size (and 128 121 hence the offsets) are the same. 129 \item130 122 The third section is similar to the second except that it is the new virtual 131 123 members introduced at this level in the hierarchy. 132 \end{enumerate}133 124 134 125 \begin{figure} … … 142 133 prefix that has the same layout and types as its parent virtual table. 143 134 This, combined with the fixed offset to the virtual table pointer, means that 144 for any virtual type ,it or any of its145 descendants can be accessedthrough135 for any virtual type it doesn't matter if we have it or any of its 136 descendants, it is still always safe to access the virtual table through 146 137 the virtual table pointer. 147 From there ,it is safe to check the type id to identify the exact type of the148 underlying object, access any of the virtual members ,and pass the object to138 From there it is safe to check the type id to identify the exact type of the 139 underlying object, access any of the virtual members and pass the object to 149 140 any of the method-like virtual members. 150 141 151 When a virtual table is declared ,the user decides where to declare it and its142 When a virtual table is declared the user decides where to declare it and its 152 143 name. The initialization of the virtual table is entirely automatic based on 153 144 the context of the declaration. 154 145 155 The type id is always fixed with each virtual table type having146 The type id is always fixed, each virtual table type will always have one 156 147 exactly one possible type id. 157 The virtual members are usually filled in during typeresolution. The best match for158 a given name and type at the declaration site is used.148 The virtual members are usually filled in by resolution. The best match for 149 a given name and type at the declaration site is filled in. 159 150 There are two exceptions to that rule: the @size@ field is the type's size 160 set using a @sizeof@ expression, andthe @align@ field is the161 type's alignment set usingan @alignof@ expression.151 and is set to the result of a @sizeof@ expression, the @align@ field is the 152 type's alignment and similarly uses an @alignof@ expression. 162 153 163 154 \subsubsection{Concurrency Integration} 164 155 Coroutines and threads need instances of @CoroutineCancelled@ and 165 156 @ThreadCancelled@ respectively to use all of their functionality. When a new 166 data type is declared with @coroutine@ or @thread@ , aforward declaration for157 data type is declared with @coroutine@ or @thread@ the forward declaration for 167 158 the instance is created as well. The definition of the virtual table is created 168 159 at the definition of the main function. 169 170 Figure~\ref{f:ConcurrencyTransformations} shows ...171 \todo{Improve Concurrency Transformations figure.}172 160 173 161 \begin{figure} … … 206 194 \label{f:ConcurrencyTransformations} 207 195 \end{figure} 196 \todo{Improve Concurrency Transformations figure.} 208 197 209 198 \subsection{Virtual Cast} … … 222 211 the cast target is passed in as @child@. 223 212 224 The generated C code wraps both arguments and the resultwith type casts.225 There is also an internal checkinside the compiler to make sure that the213 For C generation both arguments and the result are wrapped with type casts. 214 There is also an internal store inside the compiler to make sure that the 226 215 target type is a virtual type. 227 216 % It also checks for conflicting definitions. 228 217 229 The virtual cast either returns the original pointer as a new type or 0p.230 So the function just does the parent check and returns the appropr iate value.218 The virtual cast either returns the original pointer as a new type or null. 219 So the function just does the parent check and returns the approprate value. 231 220 The parent check is a simple linear search of child's ancestors using the 232 221 type information. … … 240 229 % resumption doesn't as well. 241 230 242 % Many modern languages work with an inter nal stack that function push and pop231 % Many modern languages work with an interal stack that function push and pop 243 232 % their local data to. Stack unwinding removes large sections of the stack, 244 233 % often across functions. … … 247 236 stack. On function entry and return, unwinding is handled directly by the 248 237 call/return code embedded in the function. 249 In many cases ,the position of the instruction pointer (relative to parameter238 In many cases the position of the instruction pointer (relative to parameter 250 239 and local declarations) is enough to know the current size of the stack 251 240 frame. 252 241 253 242 Usually, the stack-frame size is known statically based on parameter and 254 local variable declarations. Even with dynamic stack-size ,the information255 to determ inehow much of the stack has to be removed is still contained243 local variable declarations. Even with dynamic stack-size the information 244 to determain how much of the stack has to be removed is still contained 256 245 within the function. 257 246 Allocating/deallocating stack space is usually an $O(1)$ operation achieved by 258 247 bumping the hardware stack-pointer up or down as needed. 259 In fact, constructing/destructing values within a stack frame is of similar complexity but often takes longer. 248 Constructing/destructing values on the stack takes longer put in terms of 249 figuring out what needs to be done is of similar complexity. 260 250 261 251 Unwinding across multiple stack frames is more complex because that 262 252 information is no longer contained within the current function. 263 With sep arate compilation a function has no way of knowing what its callers264 so it can not know how large those frames are.265 Without altering the main code path ,it is also hard to pass that work off253 With seperate compilation a function has no way of knowing what its callers 254 are so it can't know how large those frames are. 255 Without altering the main code path it is also hard to pass that work off 266 256 to the caller. 267 257 … … 271 261 reseting to a snap-shot of an arbitrary but existing function frame on the 272 262 stack. It is up to the programmer to ensure the snap-shot is valid when it is 273 reset and that all required clean-up from the unwound stacks is p erformed.274 This approach is fragile and forces extra work in the surrounding code.275 276 With respect to th e extra work in the surrounding code,263 reset and that all required clean-up from the unwound stacks is preformed. 264 This approach is fragile and forces a work onto the surounding code. 265 266 With respect to that work forced onto the surounding code, 277 267 many languages define clean-up actions that must be taken when certain 278 268 sections of the stack are removed. Such as when the storage for a variable 279 is removed from the stack or when a @try@statement with a finally clause is269 is removed from the stack or when a try statement with a finally clause is 280 270 (conceptually) popped from the stack. 281 None of these should be handled explicitly by the user ---that would contradict the282 intention of these features ---so they need to be handled automatically.283 284 To safely remove sections of the stack ,the language must be able to find and271 None of these should be handled by the user, that would contradict the 272 intention of these features, so they need to be handled automatically. 273 274 To safely remove sections of the stack the language must be able to find and 285 275 run these clean-up actions even when removing multiple functions unknown at 286 276 the beginning of the unwinding. … … 304 294 current stack frame, and what handlers should be checked. Theoretically, the 305 295 LSDA can contain any information but conventionally it is a table with entries 306 representing regions of afunction and what has to be done there during296 representing regions of the function and what has to be done there during 307 297 unwinding. These regions are bracketed by instruction addresses. If the 308 298 instruction pointer is within a region's start/end, then execution is currently 309 299 executing in that region. Regions are used to mark out the scopes of objects 310 with destructors and @try@blocks.300 with destructors and try blocks. 311 301 312 302 % Libunwind actually does very little, it simply moves down the stack from … … 324 314 int avar __attribute__(( cleanup(clean_up) )); 325 315 \end{cfa} 326 The attribu te is used on a variable and specifies a function,316 The attribue is used on a variable and specifies a function, 327 317 in this case @clean_up@, run when the variable goes out of scope. 328 This capability is enough to mimic destructors, but not @try@statements which can effect318 This is enough to mimic destructors, but not try statements which can effect 329 319 the unwinding. 330 320 331 To get full unwinding support , all of these components mustdone directly with332 assembly and assembler directives , particularly the cfi directives333 \snake{.cfi_ Leda} and \snake{.cfi_personality}.321 To get full unwinding support all of this has to be done directly with 322 assembly and assembler directives. Partiularly the cfi directives 323 \snake{.cfi_lsda} and \snake{.cfi_personality}. 334 324 335 325 \subsection{Personality Functions} … … 337 327 section covers some of the important parts of the interface. 338 328 339 A personality function can p erform different actions depending on how it is329 A personality function can preform different actions depending on how it is 340 330 called. 341 331 \begin{lstlisting} … … 374 364 375 365 The @exception_class@ argument is a copy of the 376 \code{C}{exception}'s @exception_class@ field ,377 whichis a number that identifies the exception handling mechanism that created378 the \PAB{... missing text to end this sentence}379 380 The \code{C}{exception} argument is a pointer to auser366 \code{C}{exception}'s @exception_class@ field. 367 This a number that identifies the exception handling mechanism that created 368 the 369 370 The \code{C}{exception} argument is a pointer to the user 381 371 provided storage object. It has two public fields: the @exception_class@, 382 372 which is described above, and the @exception_cleanup@ function. 383 The clean-up function is used by the EHM to clean-up the exception ,if it373 The clean-up function is used by the EHM to clean-up the exception if it 384 374 should need to be freed at an unusual time, it takes an argument that says 385 375 why it had to be cleaned up. … … 392 382 messages for special cases (some of which should never be used by the 393 383 personality function) and error codes. However, unless otherwise noted, the 394 personality function always return @_URC_CONTINUE_UNWIND@.384 personality function should always return @_URC_CONTINUE_UNWIND@. 395 385 396 386 \subsection{Raise Exception} 397 Raising an exception is the central function of libunwind and it performs the387 Raising an exception is the central function of libunwind and it performs a 398 388 two-staged unwinding. 399 389 \begin{cfa} … … 482 472 % catches. Talk about GCC nested functions. 483 473 484 \CFA termination exceptions use libunwind heavily because they match 474 \CFA termination exceptions use libunwind heavily because they match \Cpp 485 475 \Cpp exceptions closely. The main complication for \CFA is that the 486 476 compiler generates C code, making it very difficult to generate the assembly to 487 form the LSDA for @try@blocks or destructors.477 form the LSDA for try blocks or destructors. 488 478 489 479 \subsection{Memory Management} … … 495 485 496 486 \begin{figure} 497 \centering498 487 \input{exception-layout} 499 488 \caption{Exception Layout} … … 502 491 \todo*{Convert the exception layout to an actual diagram.} 503 492 504 Exceptions are stored in variable-sized blocks (see Figure~\vref{f:ExceptionLayout}).493 Exceptions are stored in variable-sized blocks (see \vref{f:ExceptionLayout}). 505 494 The first component is a fixed-sized data structure that contains the 506 495 information for libunwind and the exception system. The second component is an … … 509 498 @_Unwind_Exception@ to the entire node. 510 499 511 Multip le exceptions can exist at the same time because exceptions can be500 Multipe exceptions can exist at the same time because exceptions can be 512 501 raised inside handlers, destructors and finally blocks. 513 502 Figure~\vref{f:MultipleExceptions} shows a program that has multiple 514 503 exceptions active at one time. 515 504 Each time an exception is thrown and caught the stack unwinds and the finally 516 clause runs. This handler throwsanother exception (until @num_exceptions@ gets517 high enough) ,which must be allocated. The previous exceptions may not be505 clause runs. This will throw another exception (until @num_exceptions@ gets 506 high enough) which must be allocated. The previous exceptions may not be 518 507 freed because the handler/catch clause has not been run. 519 Therefore, the EHM must keep all of these exceptionsalive while it allocates exceptions for new throws.508 So the EHM must keep them alive while it allocates exceptions for new throws. 520 509 521 510 \begin{figure} … … 570 559 \todo*{Work on multiple exceptions code sample.} 571 560 572 All exceptions are stored in nodes , which are then linked together in lists561 All exceptions are stored in nodes which are then linked together in lists, 573 562 one list per stack, with the 574 563 list head stored in the exception context. Within each linked list, the most … … 577 566 exception is being handled. The exception at the head of the list is currently 578 567 being handled, while other exceptions wait for the exceptions before them to be 579 handled andremoved.568 removed. 580 569 581 570 The virtual members in the exception's virtual table provide the size of the … … 584 573 exception into managed memory. After the exception is handled, the free 585 574 function is used to clean up the exception and then the entire node is 586 passed to free so the memory is returnedto the heap.575 passed to free so the memory can be given back to the heap. 587 576 588 577 \subsection{Try Statements and Catch Clauses} 589 The @try@statement with termination handlers is complex because it must590 compensate for the C code-generation versus assembly-code generationfrom \CFA. Libunwind578 The try statement with termination handlers is complex because it must 579 compensate for the lack of assembly-code generated from \CFA. Libunwind 591 580 requires an LSDA and personality function for control to unwind across a 592 581 function. The LSDA in particular is hard to mimic in generated C code. 593 582 594 583 The workaround is a function called @__cfaehm_try_terminate@ in the standard 595 library. The contents of a @try@block and the termination handlers are converted584 library. The contents of a try block and the termination handlers are converted 596 585 into functions. These are then passed to the try terminate function and it 597 586 calls them. 598 587 Because this function is known and fixed (and not an arbitrary function that 599 happens to contain a @try@statement), the LSDA can be generated ahead588 happens to contain a try statement), the LSDA can be generated ahead 600 589 of time. 601 590 … … 603 592 embedded assembly. This assembly code is handcrafted using C @asm@ statements 604 593 and contains 605 enough information for a single @try@ statement the function represents.594 enough information for the single try statement the function repersents. 606 595 607 596 The three functions passed to try terminate are: 608 597 \begin{description} 609 \item[try function:] This function is the @try@ block, whereall the code inside the610 @try@ block is wrapped inside thefunction. It takes no parameters and has no598 \item[try function:] This function is the try block, all the code inside the 599 try block is placed inside the try function. It takes no parameters and has no 611 600 return value. This function is called during regular execution to run the try 612 601 block. … … 620 609 handler that matches the exception. 621 610 622 \item[handler function:] This function handles the exception, where the code inside 623 is constructed by stitching together the bodies of 624 each handler of a @try@ statement and dispatches to the selected handler. 625 It takes a 611 \item[handler function:] This function handles the exception. It takes a 626 612 pointer to the exception and the handler's id and returns nothing. It is called 627 after the cleanup phase. 613 after the cleanup phase. It is constructed by stitching together the bodies of 614 each handler and dispatches to the selected handler. 628 615 \end{description} 629 616 All three functions are created with GCC nested functions. GCC nested functions 630 can be used to create closures, \iefunctions that can refer to the state of other617 can be used to create closures, functions that can refer to the state of other 631 618 functions on the stack. This approach allows the functions to refer to all the 632 619 variables in scope for the function containing the @try@ statement. These … … 636 623 Using this pattern, \CFA implements destructors with the cleanup attribute. 637 624 638 Figure~\ref{f:TerminationTransformation} shows an example transformation for a \CFA @try@639 statement with @catch@ clauses into corresponding C functions. \PAB{Walk the reader through the example code.}640 641 625 \begin{figure} 642 626 \begin{cfa} … … 649 633 } 650 634 \end{cfa} 651 652 \medskip653 \hrule654 \medskip655 635 656 636 \begin{cfa} … … 703 683 % The stack-local data, the linked list of nodes. 704 684 705 Resumption issimpler to implement than termination685 Resumption simpler to implement than termination 706 686 because there is no stack unwinding. 707 687 Instead of storing the data in a special area using assembly, 708 688 there is just a linked list of possible handlers for each stack, 709 with each list node representing a @try@statement on the stack.689 with each node on the list reperenting a try statement on the stack. 710 690 711 691 The head of the list is stored in the exception context. 712 The nodes are stored in order, with the more recent @try@statements closer692 The nodes are stored in order, with the more recent try statements closer 713 693 to the head of the list. 714 Instead of traversing the stack ,resumption handling traverses the list.715 At each node , the EHM checks to see if the @try@ statement it represents694 Instead of traversing the stack resumption handling traverses the list. 695 At each node the EHM checks to see if the try statement the node repersents 716 696 can handle the exception. If it can, then the exception is handled and 717 697 the operation finishes, otherwise the search continues to the next node. 718 If the search reaches the end of the list without finding a @try@statement719 that can handle the exception ,the default handler is executed and the698 If the search reaches the end of the list without finding a try statement 699 that can handle the exception the default handler is executed and the 720 700 operation finishes. 721 701 722 Each node has a handler function that does most of the work. 723 The handler function is passed the raised exception and returns true 724 if the exception is handled and false otherwise. 725 726 For each @catchResume@ clause, the handler function: 727 \begin{itemize} 728 \item 729 checks to see if the raised exception is a descendant type of the declared 730 exception type, 731 \item 732 if it is and there is a conditional expression then it 733 runs the test, 734 \item 735 if both checks pass the handling code for the clause is run and the function returns true, 736 \item 737 otherwise it moves onto the next clause. 738 \end{itemize} 702 In each node is a handler function which does most of the work there. 703 The handler function is passed the raised the exception and returns true 704 if the exception is handled and false if it cannot be handled here. 705 706 For each @catchResume@ clause the handler function will: 707 check to see if the raised exception is a descendant type of the declared 708 exception type, if it is and there is a conditional expression then it will 709 run the test, if both checks pass the handling code for the clause is run 710 and the function returns true, otherwise it moves onto the next clause. 739 711 If this is the last @catchResume@ clause then instead of moving onto 740 712 the next clause the function returns false as no handler could be found. 741 742 Figure~\ref{f:ResumptionTransformation} shows an example transformation for a \CFA @try@743 statement with @catchResume@ clauses into corresponding C functions. \PAB{Walk the reader through the example code.}744 713 745 714 \begin{figure} … … 784 753 785 754 % Recursive Resumption Stuff: 786 Figure~\ref{f:ResumptionMarking} shows the search skipping (see \vpageref{s:ResumptionMarking}), which ignores parts of755 Search skipping (see \vpageref{s:ResumptionMarking}), which ignores parts of 787 756 the stack 788 757 already examined, is accomplished by updating the front of the list as the … … 790 759 is updated to the next node of the current node. After the search is complete, 791 760 successful or not, the head of the list is reset. 761 792 762 This mechanism means the current handler and every handler that has already 793 763 been checked are not on the list while a handler is run. If a resumption is 794 thrown during the handling of another resumption ,the active handlers and all764 thrown during the handling of another resumption the active handlers and all 795 765 the other handler checked up to this point are not checked again. 796 This structure also supports new handlers added while the resumption is being 766 767 This structure also supports new handler added while the resumption is being 797 768 handled. These are added to the front of the list, pointing back along the 798 769 stack -- the first one points over all the checked handlers -- and the ordering 799 770 is maintained. 800 \PAB{Maybe number the figure and use the numbers in the description to help the reader follow.}801 771 802 772 \begin{figure} … … 808 778 809 779 \label{p:zero-cost} 810 Finally, the resumption implementation has a cost for entering/exiting a @try@780 Note, the resumption implementation has a cost for entering/exiting a @try@ 811 781 statement with @catchResume@ clauses, whereas a @try@ statement with @catch@ 812 782 clauses has zero-cost entry/exit. While resumption does not need the stack … … 828 798 around the context of the associated @try@ statement. 829 799 830 The rest is handled by GCC. The @try@block and all handlers are inside this800 The rest is handled by GCC. The try block and all handlers are inside this 831 801 block. At completion, control exits the block and the empty object is cleaned 832 802 up, which runs the function that contains the finally code. … … 842 812 coroutine or thread. Fortunately, the thread library stores the main thread 843 813 pointer and the current thread pointer, and every thread stores a pointer to 844 its coroutine and the coroutine it is currently executing. 845 If the current thread's main and current coroutines are the same then the 846 current stack is a thread stack, otherwise it is a coroutine stack. 847 Note, the runtime considers a thread as a coroutine with an associated user-level thread; 848 hence, for many operations a thread and coroutine are treated uniformly. 849 %\todo*{Consider adding a description of how threads are coroutines.} 850 851 % Furthermore it is easy to compare the 852 % current thread to the main thread to see if they are the same. And if this 853 % is not a thread stack then it must be a coroutine stack. 814 its main coroutine and the coroutine it is currently executing. 815 \todo*{Consider adding a description of how threads are coroutines.} 816 817 If a the current thread's main and current coroutines are the same then the 818 current stack is a thread stack. Furthermore it is easy to compare the 819 current thread to the main thread to see if they are the same. And if this 820 is not a thread stack then it must be a coroutine stack. 854 821 855 822 However, if the threading library is not linked, the sequential execution is on 856 823 the main stack. Hence, the entire check is skipped because the weak-symbol 857 function is loaded. Therefore, main thread cancellation is unconditionally824 function is loaded. Therefore, a main thread cancellation is unconditionally 858 825 performed. 859 826 860 827 Regardless of how the stack is chosen, the stop function and parameter are 861 828 passed to the forced-unwind function. The general pattern of all three stop 862 functions is the same: continue unwinding until the end of stack and863 then p erform the appropriatetransfer.829 functions is the same: they continue unwinding until the end of stack and 830 then preform their transfer. 864 831 865 832 For main stack cancellation, the transfer is just a program abort. … … 867 834 For coroutine cancellation, the exception is stored on the coroutine's stack, 868 835 and the coroutine context switches to its last resumer. The rest is handled on 869 the backside of the resume, which check sif the resumed coroutine is836 the backside of the resume, which check if the resumed coroutine is 870 837 cancelled. If cancelled, the exception is retrieved from the resumed coroutine, 871 838 and a @CoroutineCancelled@ exception is constructed and loaded with the 872 839 cancelled exception. It is then resumed as a regular exception with the default 873 840 handler coming from the context of the resumption call. 874 This semantics allows a cancellation to cascade through an arbitrary set of resumed875 coroutines back to the thread's coroutine, performing cleanup along the way.876 841 877 842 For thread cancellation, the exception is stored on the thread's main stack and … … 883 848 null (as it is for the auto-generated joins on destructor call), the default is 884 849 used, which is a program abort. 885 This semantics allows a cancellation to cascade through an arbitrary set of joining886 threads back to the program's main, performing cleanup along the way.887 850 %; which gives the required handling on implicate join. -
doc/theses/andrew_beach_MMath/performance.tex
r2f19e03 rb51e389c 6 6 7 7 Performance has been of secondary importance for most of this project. 8 Instead, the goal has been to get the features working. 9 The only performance 10 requirements is to ensure the exception tests for correctness ran in a reasonable 8 The driving for has been to get the features working, the only performance 9 requirements were to make sure the tests for correctness rain in a reasonable 11 10 amount of time. 12 Much of the implementation is still reasonable and could be used for similar prototypes. 13 Hence, 14 the work still has some use. 15 To get a rough idea about the \CFA implementation, tests are run on \CFA, C++ and Java, which have similar termination-handling exceptions. 16 Tests are also run on \CFA and uC++, which has similar resumption-handling exceptions. 11 Still this is an implementation others could use for similar prototypes and 12 so the results still have some use. 17 13 18 \section{Termination Comparison} 14 \section{Test Set-Up} 15 Tests will be run on \CFA, C++ and Java. 16 19 17 C++ is the most comparable language because both it and \CFA use the same 20 18 framework, libunwind. 21 In fact ,the comparison is almost entirely a quality of implementation19 In fact the comparison is almost entirely a quality of implementation 22 20 comparison. \CFA's EHM has had significantly less time to be optimized and 23 21 does not generate its own assembly. It does have a slight advantage in that 24 22 there are some features it does not handle. 25 23 26 The Java comparison is an opportunity to compare a managed memory model with unmanaged, 27 to see if there are any effects related to the exception model. 24 % Some languages I left out: 25 % Python: Its a scripting language, different 26 % uC++: Not well known and should the same results as C++, except for 27 % resumption which should be the same. 28 \todo{Can we find a good language to compare resumptions in.} 28 29 29 \subsection{Test Set-Up} 30 All tests are run inside a main loop that performs the test 31 repeatedly. This design avoids start-up or tear-down time from 30 All tests will be run inside a main loop which will perform the test 31 repeatedly. This is to avoid letting and start-up or tear-down time from 32 32 affecting the timing results. 33 A consequence is that tests cannot terminate the program, which does limit33 This also means that tests cannot terminate the program, which does limit 34 34 how tests can be implemented. There are catch-alls to keep unhandled 35 exceptions from terminating t ests.35 exceptions from terminating the program. 36 36 37 The exceptions used in this test are alwaysa new exception based off of38 the base exception. This requirement minimizes performance differences based37 The exceptions used in this test will always be a new exception based off of 38 the base exception. This should minimize and preformance differences based 39 39 on the object model. 40 Catch-alls are done by catching the root exception type (not using \Cpp's40 Catch-alls will be done by catching the root exception type (not using \Cpp's 41 41 \code{C++}{catch(...)}). 42 42 … … 44 44 hot. 45 45 46 \subsection{Tests} 47 The following tests capture the most important aspects of exception handling and should provide 48 a reasonable guide to programmers of where EHM costs occur. 49 46 \section{Tests} 50 47 \paragraph{Raise/Handle} 51 48 What is the basic cost to raise and handle an exception? 52 49 53 There are a number of factors that can effect this. 54 For \CFA this includes 50 There are a number of factors that can effect this, for \CFA this includes 55 51 the type of raise, 56 52 … … 65 61 This has the same set-up as the raise/handle test except the intermediate 66 62 stack frames contain either an object declaration with a destructor or a 67 @try@ statement with no handlers except and a @finally@clause.63 try statement with no handlers except for a finally clause. 68 64 69 65 \paragraph{Enter/Leave} … … 71 67 is thrown? 72 68 73 Th e test is a simple matter of entering69 This is the simplist pattern to test as it is a simple matter of entering 74 70 and leaving a try statement. 75 71 … … 78 74 79 75 \paragraph{Re-throw and Conditional-Catch} 80 How expen sive it is to run a non-exception type check for a handler?76 How expencive it is to run a non-exception type check for a handler? 81 77 82 78 In this case different languages approach this problem differently, either 83 79 through a re-throw or a conditional-catch. 84 Where \CFA uses its condition , other languages mustunconditionally80 Where \CFA uses its condition other languages will have to unconditionally 85 81 catch the exception then re-throw if the condition if the condition is false. 86 82 … … 90 86 % We could do a Cforall test without the catch all and a new default handler 91 87 % that does a catch all. 92 As a point of comparison ,one of the raise/handle tests (which one?) has88 As a point of comparison one of the raise/handle tests (which one?) has 93 89 same layout but never catches anything. 94 90 … … 104 100 %(I haven't actually figured out how to compare this, probably using something 105 101 %related to -fexceptions.) 106 107 108 \section{Resumption Comparison}109 % Some languages I left out:110 % Python: Its a scripting language, different111 % uC++: Not well known and should the same results as C++, except for112 % resumption which should be the same.113 \todo{Can we find a good language to compare resumptions in.}
Note: See TracChangeset
for help on using the changeset viewer.
