Changes in / [35ea4f3:0edd11a]


Ignore:
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/andrew_beach_MMath/features.tex

    r35ea4f3 r0edd11a  
    1010of they virtual system was designed and implemented.
    1111
    12 Virtual types are organized in simple hierarchies. Each virtual type may have
     12Virtual types are organizied in simple hierarchies. Each virtual type may have
    1313a parent and can have any number of children. A type's descendants are its
    1414children and its children's descendants. A type may not be its own descendant.
    … …  
    1717structure that has fields for all the virtual members of a type. A virtual
    1818type has all the virtual members of its parent and can add more. It may also
    19 update the values of the virtual members and should in many cases.
     19update the values of the virtual members.
    2020
    2121Except for virtual casts, this is only used internally in the exception
    … …  
    2727\end{lstlisting}
    2828
    29 This has the same precedence as a traditional C-cast and can be used in the
     29This has the same precidence as a traditional C-cast and can be used in the
    3030same places. This will convert the result of EXPRESSION to the type TYPE. Both
    3131the type of EXPRESSION and TYPE must be pointers to virtual types.
    … …  
    4141% features all exceptions support.
    4242
    43 \subsection{Exception Traits}
    44 Exceptions are defined by the trait system; there are a series of traits and
    45 if a type satisfies them then they can be used as exceptions.
    46 
    47 \begin{lstlisting}
    48 trait is_exception(dtype exceptT, dtype virtualT) {
    49     virtualT const & get_exception_vtable(exceptT *);
    50 };
    51 \end{lstlisting}
    52 This is the base trait that all exceptions need to match.
    53 The single function takes any pointer (including the null pointer) and
    54 returns a reference to the virtual table instance. Defining this function
    55 also establishes the virtual type and virtual table pair to the resolver
    56 and promises that \codeCFA{exceptT} is a virtual type and a child of the
    57 base exception type.
    58 
    59 One odd thing about \codeCFA{get_exception_vtable} is that it should always
    60 be a constant function, returning the same value regardless of its argument.
    61 A pointer or reference to the virtual table instance could be used instead,
    62 however using a function has some ease of implementation advantages and
    63 allows for easier disambiguation because the virtual type name (or the
    64 address of an instance that is in scope) can be used instead of the mangled
    65 virtual table name.
    66 
    67 Also note the use of the word ``promise" in the trait description. \CFA
    68 cannot currently check to see if either \codeCFA{exceptT} or
    69 \codeCFA{virtualT} match the layout requirements. Currently this is
    70 considered part of \codeCFA{get_exception_vtable}'s correct implementation.
    71 
    72 \begin{lstlisting}
    73 trait is_termination_exception(
    74         dtype exceptT, dtype virtualT | is_exception(exceptT, virtualT)) {
    75     void defaultTerminationHandler(exceptT &);
    76 };
    77 \end{lstlisting}
    78 The only additional function required to make the exception usable with
    79 termination is a default handler. This function is called whenever a
    80 termination throw on an exception of this type is preformed and no handler
    81 is found.
    82 
    83 \begin{lstlisting}
    84 trait is_resumption_exception(
    85         dtype exceptT, dtype virtualT | is_exception(exceptT, virtualT)) {
    86     void defaultResumptionHandler(exceptT &);
    87 };
    88 \end{lstlisting}
    89 Creating a resumption exception is exactly the same except for resumption.
    90 The name change reflects that and the function is called when a resumption
    91 throw on an exception of this type is preformed and no handler is found.
    92 
    93 Finally there are three additional macros that can be used to refer to the
    94 these traits. They are \codeCFA{IS_EXCEPTION},
    95 \codeCFA{IS_TERMINATION_EXCEPTION} and \codeCFA{IS_RESUMPTION_EXCEPTION}.
    96 Each takes the virtual type's name and, for polymorphic types only, the
    97 parenthesized list of polymorphic arguments. These do the name mangling to
    98 get the virtual table name and provide the arguments to both sides.
    99 
    10043\section{Termination}
    10144
    102 Termination exception throws are likely the most familiar kind, as they are
     45Termination exception throws are likely the most framilar kind, as they are
    10346used in several popular programming languages. A termination will throw an
    10447exception, search the stack for a handler, unwind the stack to where the
    … …  
    12366
    12467Then the exception system will search the stack starting from the throw and
    125 proceeding towards the base of the stack, from callee to caller. As it goes
     68proceding towards the base of the stack, from callee to caller. As it goes
    12669it will check any termination handlers it finds:
    12770
    … …  
    168111\paragraph{Re-Throwing}
    169112
    170 You can also re-throw the most recent termination exception with
     113You can also rethrow the most recent termination exception with
    171114\codeCFA{throw;}. % This is terrible and you should never do it.
    172115This can be done in a handler or any function that could be called from a
    … …  
    192135\end{lstlisting}
    193136The result of EXPRESSION must be a resumption exception type. A resumption
    194 exception type is any type that satisfies the assertion
     137exception type is any type that satifies the assertion
    195138\codeCFA{void defaultResumptionHandler(T &);} (the default handler). When the
    196139statement is executed the expression is evaluated and the result is thrown.
    … …  
    216159continues from the throw statement.
    217160
    218 If no appropriate handler is found then the default handler is called. The
     161If no approprate handler is found then the default handler is called. The
    219162throw statement acts as a regular function call passing the exception to
    220163the default handler and after the handler finishes executing control continues
    … …  
    231174which is what most users expect.
    232175
    233 % This might need a diagram. But it is an important part of the justification
     176% This might need a diagram. But it is an important part of the justifaction
    234177% of the design of the traversal order.
    235178It also avoids the recursive resumption problem. If the entire stack is
    … …  
    241184system an A resumed from the top of the stack will be handled by the first
    242185handler. A B resumed from the top or from the first handler it will be handled
    243 by the second handler. The only difference is when A is thrown from the second
     186by the second hander. The only difference is when A is thrown from the second
    244187handler. The entire stack search will call the first handler again, creating a
    245188loop. Starting from the position in the stack though will break this loop.
    … …  
    255198It also has the same behaviour, after the exception type has been matched
    256199with the EXCEPTION\_TYPE the CONDITION is evaluated with NAME in scope. If
    257 the result is true then the handler is run, otherwise the search continues
     200the result is true then the hander is run, otherwise the search continues
    258201just as if there had been a type mismatch.
    259202
    … …  
    298241the finally block. Other ways to leave the finally block - such as a long
    299242jump or termination - are much harder to check, at best requiring additional
    300 run-time overhead, and so are merely discouraged.
     243runtime overhead, and so are merely discouraged.
    301244
    302245\section{Cancellation}
    … …  
    307250
    308251There is no special statement for starting a cancellation, instead you call
    309 the standard library function \codeCFA{cancel\_stack} which takes an exception.
     252the standard libary function \codeCFA{cancel\_stack} which takes an exception.
    310253Unlike in a throw this exception is not used in control flow but is just there
    311254to pass information about why the cancellation happened.
    312255
    313 The handler is decided entirely by which stack is being canceled. There are
     256The handler is decided entirely by which stack is being cancelled. There are
    314257three handlers that apply to three different groups of stacks:
    315258\begin{itemize}
    … …  
    323266
    324267\item Thread Stack:
    325 Thread stacks are those created \codeCFA{thread} or otherwise satisfy the
     268Thread stacks are those created \codeCFA{thread} or otherwise satify the
    326269\codeCFA{is\_thread} trait.
    327270
    … …  
    345288context required for the other. This can happen with join but as the
    346289destructors will always be run when the stack is being unwound and one
    347 termination/cancellation is already active. Also since they are implicit they
     290termination/cancellation is already active. Also since they are implicite they
    348291are easier to forget about.
    349292
    350293\item Coroutine Stack:
    351294Coroutine stacks are those created with \codeCFA{coroutine} or otherwise
    352 satisfy the \codeCFA{is\_coroutine} trait.
     295satify the \codeCFA{is\_coroutine} trait.
    353296
    354297A coroutine knows of two other coroutines, its starter and its last resumer.
    … …  
    358301Resume will resume throw a \codeCFA{CoroutineCancelled} exception, which is
    359302polymorphic over the coroutine type and has a pointer to the coroutine being
    360 canceled and the canceling exception. The resume function also has an
     303cancelled and the cancelling exception. The resume function also has an
    361304assertion that the \codeCFA{defaultResumptionHandler} for the exception. So it
    362305will use the default handler like a regular throw.

  • doc/theses/andrew_beach_MMath/future.tex

    r35ea4f3 r0edd11a  
    88parts of the exception system that use the current version.
    99
    10 There are several improvements to the virtual system that would improve
    11 the exception traits. The biggest one is an assertion that checks that one
    12 virtual type is a child of another virtual type. This would capture many of
    13 the requirements much more precisely.
    14 
    15 The full virtual system might also include other improvement like associated
    16 types. This is a proposed feature that would allow traits to refer to types
    17 not listed in their header. This would allow the exception traits to not
    18 refer to the virtual table type explicatly which would remove the need for
    19 the interface macros.
     10For instance a full virtual system would probably allow for several
     11improvements to the exception traits. Although they do currently work they
     12could be made easier to use by making the virtual table type implitate in the
     13trait (which would remove the need for those wrapper marcos) or allowing
     14for assertions that give the layout of a virtual table for safety.
    2015
    2116\section{Additional Throws}
    … …  
    7065
    7166Also new techniques to skip previously searched parts of the stack will have
    72 to be developed. The recursive resume problem still remains and ideally the
    73 same pattern of ignoring sections of the stack.
     67to be developed.
    7468
    75 \section{Signal Exceptions}
    76 Exception Handling: Issues and a Proposed Notation suggests there are three
    77 types of exceptions: escape, notify and signal.
    78 Escape exceptions are our termination exceptions, notify exceptions are
    79 resumption exceptions and that leaves signal exception unimplemented.
     69\section{Support for More Platforms}
     70Termination is not portable because it is implemented with inline assembly.
     71Those sections will have to be rewritten to support different architectures
    8072
    81 Signal exceptions allow either behaviour, that is after the exception is
    82 handled control can either return to the throw or from where the handler is
    83 defined.
    84 
    85 The design should be rexamined and be updated for \CFA. A very direct
    86 translation would perhaps have a new throw and catch pair and a statement
    87 (or statements) could be used to decide if the handler returns to the throw
    88 or continues where it is, but there are other options.
    89 
    90 For instance resumption could be extended to cover this use by allowing
    91 local control flow out of it. This would require an unwind as part of the
    92 transition as there are stack frames that have to be removed.
    93 This would mean there is no notify like throw but because \CFA does not have
    94 exception signatures a termination can be thrown from any resumption handler
    95 already so there are already ways one could try to do this in existing \CFA.
    96 
    97 % Maybe talk about the escape; and escape CONTROL_STMT; statements or how
    98 % if we could choose if _Unwind_Resume proceeded to the clean-up stage this
    99 % would be much easier to implement.
    100 
    101 \section{Language Improvements}
    102 There is also a lot of work that are not follow ups to this work in terms of
    103 research, some have no interesting research to be done at all, but would
    104 improve \CFA as a programming language. The full list of these would
    105 naturally be quite extensive but here are a few examples that involve
    106 exceptions:
     73\section{Quality-of-Life Improvements}
     74Finally come various improvements to the usability of \CFA. Most of these
     75would just require time. Time that would not lead to interesting research so
     76it has been left aside for now. A few examples are included here but there
     77are more:
    10778
    10879\begin{itemize}
    109 \item The implementation of termination is not portable because it includes
    110 some assembly statements. These sections will have to be re-written to so
    111 \CFA has full support on more machines.
    11280\item Allowing exception handler to bind the exception to a reference instead
    11381of a pointer. This should actually result in no change in behaviour so there
    … …  
    12088much easier. (To do the same for try blocks would probably wait for zero-cost
    12189exceptions, which would allow the try block to be inlined as well.)
     90\item Enabling local control flow out of a resumption handler. This would be
     91a weighty operation, causing a stack unwind like a termination, so there might
     92be a different statement or a statement modifier to make sure the user does
     93this purposefully.
     94
     95However this would require the more complex system as they cannot be inlined
     96into the original function as they can be run at a different place on the
     97stack. So instead the unwinding will have to carry with it information on
     98which one of these points to continue at and possibly also the return value
     99for the function if a \codeCFA{return} statement was used.
    122100\end{itemize}

  • doc/theses/fangren_yu_COOP_F20/Report.tex

    r35ea4f3 r0edd11a  
    8787
    8888\begin{abstract}
    89 
    90 \CFA is an evolutionary extension to the C programming language, featuring a parametric type system, and is currently under active development. The reference compiler for \CFA language, @cfa-cc@, has some of its major components dated back to early 2000s, and is based on inefficient data structures and algorithms. Some improvements targeting the expression resolution algorithm, suggested by a recent prototype experiment on a simplified model, are implemented in @cfa-cc@ to support the full \CFA language. These optimizations speed up the compiler significantly by a factor of 20 across the existing \CFA codebase, bringing the compilation time of a mid-sized \CFA source file down to 10-second level. A few cases derived from realistic code examples that causes trouble to the compiler are analyzed in detail, with proposed solutions. This step of \CFA project development is critical to its eventual goal to be used alongside C for large software systems.
    91 
    9289\end{abstract}
    9390
    9491\section{Introduction}
    95 
    96 \CFA language, developed by the Programming Language Group at University of Waterloo, has a long history, with the first proof-of-concept compiler built in 2003 by Richard Bilson~\cite{Bilson03}. Many new features are added to the language over time, but the core of \CFA, parametric functions introduced by the @forall@ clause (hence the name of the language), with the type system supporting parametric overloading, remains mostly unchanged.
    97 
    98 The current \CFA reference compiler @cfa-cc@ still includes many parts taken directly from the original Bilson's implementation, and serves as a starting point for the enhancement work to the type system. Unfortunately, it does not provide the efficiency required for the language to be used practically: a \CFA source file of approximately 1000 lines of code can take a few minutes to compile. The cause of the problem is that the old compiler used inefficient data structures and algorithms for expression resolution, which involved a lot of copying and redundant work.
    99 
    100 This paper presents a series of optimizations to the performance-critical parts of the resolver, with a major rework of the data structure used by the compiler, using a functional programming approach to reduce memory complexity. Subsequent improvements are mostly suggested by running the compiler builds with a performance profiler against the \CFA standard library source code and a test suite to find the most underperforming components in the compiler algorithm.
    101 
    102 The \CFA team endorses a pragmatic philosophy in work that mostly focuses on practical implications of language design and implementation, rather than the theoretical limits. In particular, the compiler is designed to work on production \CFA code efficiently and keep type safety, while sometimes making compromises to expressiveness in extreme corner cases. However, when these corner cases do appear in actual usage, they need to be thoroughly investigated. Analysis presented in this paper, therefore, are conducted on a case-by-case basis. Some of them eventually point to certain weaknesses in the language design and solutions are proposed based on experimental results.
    10392
    10493\section{Completed work}
    … …  
    455444\section{Timing results}
    456445
    457 For the timing results presented here, the \CFA compiler is built with gcc 9.3.0, and tested on a server machine running Ubuntu 20.04, 64GB RAM and 32-core 2.2 GHz CPU, results reported by the time command, and using only 8 cores in parallel such that the time is close to the case with 100\% CPU utilization on a single thread.
     446For the timing results presented here, the \CFA compiler is built with gcc 9.3.0, and tested on a server machine running Ubuntu 20.04, 64GB RAM and 32-core 2.2 GHz CPU, results reported by the time command, and using only 8 cores in parallel such that the time is close to the case with 100% CPU utilization on a single thread.
    458447
    459448On the most recent build, the \CFA standard library (~1.3 MB of source code) compiles in 4 minutes 47 seconds total processor time (single thread equivalent), with the slowest file taking 13 seconds. The test suite (178 test cases, ~2.2MB of source code) completes within 25 minutes total processor time,\footnote{Including a few runtime tests; total time spent in compilation is approximately 21 minutes.} with the slowest file taking 23 seconds. In contrast, the library build on old compiler takes 85 minutes total, 5 minutes for the slowest file. Full test suite takes too long with old compiler build and is therefore not run, but the slowest test cases take approximately 5 minutes. Overall, the most recent build compared to old build in April 2020, before the project started, is consistently faster by a factor of 20.

  • libcfa/src/stdlib.hfa

    r35ea4f3 r0edd11a  
    191191                } else if(Fill.tag == 't') {
    192192                        for ( int i = copy_end; i < Dim * size; i += size ) {
    193 #pragma GCC diagnostic push
    194 #pragma GCC diagnostic ignored "-Warray-bounds"
    195 #pragma GCC diagnostic push
    196 #pragma GCC diagnostic ignored "-Wstringop-overflow="
    197193                                memcpy( (char *)ptr + i, &Fill.t, size );
    198 #pragma GCC diagnostic pop
    199 #pragma GCC diagnostic pop
    200194                        }
    201195                } else if(Fill.tag == 'a') {
Note: See TracChangeset for help on using the changeset viewer.