Changeset a927662 for doc/papers


Ignore:
Timestamp:
Mar 18, 2019, 10:28:04 AM (3 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
arm-eh, cleanup-dtors, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr
Children:
466b1c9, 9cb4fc8
Parents:
3f8ec70
Message:

more intro and coroutine changes

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/papers/concurrency/Paper.tex

    r3f8ec70 ra927662  
    215215{}
    216216\lstnewenvironment{Go}[1][]
    217 {\lstset{#1}}
     217{\lstset{language=go,moredelim=**[is][\protect\color{red}]{`}{`},#1}\lstset{#1}}
     218{}
     219\lstnewenvironment{python}[1][]
     220{\lstset{language=python,moredelim=**[is][\protect\color{red}]{`}{`},#1}\lstset{#1}}
    218221{}
    219222
     
    267270backwards-compatible extension of the C programming language~\cite{Moss18}.
    268271Within the \CFA framework, new control-flow features are created from scratch.
    269 ISO \Celeven defines only a subset of the \CFA extensions.
    270 The overlapping features are concurrency~\cite[\S~7.26]{C11};
    271 however, \Celeven concurrency is largely wrappers for a subset of the pthreads library~\cite{Butenhof97,Pthreads}.
    272 Furthermore, \Celeven and pthreads concurrency is basic, based on thread fork/join in a function and a few locks, which is low-level and error prone;
     272ISO \Celeven defines only a subset of the \CFA extensions, where the overlapping features are concurrency~\cite[\S~7.26]{C11}.
     273However, \Celeven concurrency is largely wrappers for a subset of the pthreads library~\cite{Butenhof97,Pthreads}.
     274Furthermore, \Celeven and pthreads concurrency is simple, based on thread fork/join in a function and a few locks, which is low-level and error prone;
    273275no high-level language concurrency features are defined.
    274276Interestingly, almost a decade after publication of the \Celeven standard, neither gcc-8, clang-8 nor msvc-19 (most recent versions) support the \Celeven include @threads.h@, indicating little interest in the C11 concurrency approach.
     
    293295While having a sufficient memory-model allows sound libraries to be constructed, writing these libraries can quickly become awkward and error prone, and using these low-level libraries has the same issues.
    294296Essentially, using low-level explicit locks is the concurrent equivalent of assembler programming.
    295 Just as most assembler programming is replaced with programming in a high-level language, explicit locks can be replaced with high-level concurrency constructs in a programming language.
     297Just as most assembler programming is replaced with high-level programming, explicit locks can be replaced with high-level concurrency in a programming language.
    296298Then the goal is for the compiler to check for correct usage and follow any complex coding conventions implicitly.
    297299The drawback is that language constructs may preclude certain specialized techniques, therefore introducing inefficiency or inhibiting concurrency.
     
    309311however, the reverse is seldom true, i.e., given implicit concurrency, e.g., actors, it is virtually impossible to create explicit concurrency, e.g., blocking thread objects.}
    310312Finally, with extended language features and user-level threading it is possible to discretely fold locking and non-blocking I/O multiplexing into the language's I/O libraries, so threading implicitly dovetails with the I/O subsystem.
    311 
    312313\CFA embraces language extensions and user-level threading to provide advanced control-flow (exception handling\footnote{
    313314\CFA exception handling will be presented in a separate paper.
    314315The key feature that dovetails with this paper is non-local exceptions allowing exceptions to be raised across stacks, with synchronous exceptions raised among coroutines and asynchronous exceptions raised among threads, similar to that in \uC~\cite[\S~5]{uC++}
    315316} and coroutines) and concurrency.
    316 We show the \CFA language extensions are demonstrably better than those proposed for \Celeven, \CC and other concurrent, imperative programming languages, and that the \CFA runtime is competitive with other similar extensions.
    317 The contributions of this work are:
     317
     318Most augmented traditional (Fortran 18~\cite{Fortran18}, Cobol 14~\cite{Cobol14}, Ada 12~\cite{Ada12}, Java 11~\cite{Java11}) and new languages (Go~\cite{Go}, Rust~\cite{Rust}, and D~\cite{D}), except \CC, diverge from C with different syntax and semantics, only interoperate indirectly with C, and are not systems languages, for those with managed memory.
     319As a result, there is a significant learning curve to move to these languages, and C legacy-code must be rewritten.
     320While \CC, like \CFA, takes an evolutionary approach to extend C, \CC's constantly growing complex and interdependent features-set (e.g., objects, inheritance, templates, etc.) mean idiomatic \CC code is difficult to use from C, and C programmers must expend significant effort learning \CC.
     321Hence, rewriting and retraining costs for these languages, even \CC, are prohibitive for companies with a large C software-base.
     322\CFA with its orthogonal feature-set, its high-performance runtime, and direct access to all existing C libraries circumvents these problems.
     323
     324We present comparative examples so the reader can judge if the \CFA control-flow extensions are equivalent or better than those in or proposed for \Celeven, \CC and other concurrent, imperative programming languages, and perform experiments to show the \CFA runtime is competitive with other similar mechanisms.
     325The detailed contributions of this work are:
    318326\begin{itemize}
    319327\item
     
    620628
    621629
    622 \section{Coroutines: A Stepping Stone}\label{coroutine}
    623 
    624 Advanced controlWhile the focus of this discussion is concurrency and parallelism, it is important to address coroutines, which are a significant building block of a concurrency system (but not concurrent among themselves).
     630\section{Coroutines: Stepping Stone}
     631\label{coroutine}
     632
    625633Coroutines are generalized routines allowing execution to be temporarily suspended and later resumed.
    626634Hence, unlike a normal routine, a coroutine may not terminate when it returns to its caller, allowing it to be restarted with the values and execution location present at the point of suspension.
     
    648656\begin{lrbox}{\myboxA}
    649657\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    650 `int f1, f2, state = 1;`   // single global variables
     658`int fn1, fn2, state = 1;`   // single global variables
    651659int fib() {
    652660        int fn;
    653661        `switch ( state )` {  // explicit execution state
    654           case 1: fn = 0;  f1 = fn;  state = 2;  break;
    655           case 2: fn = 1;  f2 = f1;  f1 = fn;  state = 3;  break;
    656           case 3: fn = f1 + f2;  f2 = f1;  f1 = fn;  break;
     662          case 1: fn = 0;  fn1 = fn;  state = 2;  break;
     663          case 2: fn = 1;  fn2 = fn1;  fn1 = fn;  state = 3;  break;
     664          case 3: fn = fn1 + fn2;  fn2 = fn1;  fn1 = fn;  break;
    657665        }
    658666        return fn;
     
    671679\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    672680#define FIB_INIT `{ 0, 1 }`
    673 typedef struct { int f2, f1; } Fib;
     681typedef struct { int fn2, fn1; } Fib;
    674682int fib( Fib * f ) {
    675683
    676         int ret = f->f2;
    677         int fn = f->f1 + f->f2;
    678         f->f2 = f->f1; f->f1 = fn;
     684        int ret = f->fn2;
     685        int fn = f->fn1 + f->fn2;
     686        f->fn2 = f->fn1; f->fn1 = fn;
    679687
    680688        return ret;
     
    683691        Fib f1 = FIB_INIT, f2 = FIB_INIT;
    684692        for ( int i = 0; i < 10; i += 1 ) {
    685                 printf( "%d %d\n", fib( &f1 ), fib( &f2 ) );
     693                printf( "%d %d\n", fib( &fn1 ), fib( &f2 ) );
    686694        }
    687695}
     
    689697\end{lrbox}
    690698
    691 \subfloat[3 States: global variables]{\label{f:GlobalVariables}\usebox\myboxA}
     699\subfloat[3 states: global variables]{\label{f:GlobalVariables}\usebox\myboxA}
    692700\qquad
    693 \subfloat[1 State: external variables]{\label{f:ExternalState}\usebox\myboxB}
    694 \caption{C Fibonacci Implementations}
     701\subfloat[1 state: encapsulated variables]{\label{f:ExternalState}\usebox\myboxB}
     702\caption{C fibonacci fsm}
    695703\label{f:C-fibonacci}
    696704
     
    702710`coroutine` Fib { int fn; };
    703711void main( Fib & fib ) with( fib ) {
    704         int f1, f2;
    705         fn = 0;  f1 = fn;  `suspend()`;
    706         fn = 1;  f2 = f1;  f1 = fn;  `suspend()`;
    707         for ( ;; ) {
    708                 fn = f1 + f2;  f2 = f1;  f1 = fn;  `suspend()`;
    709         }
    710 }
    711 int next( Fib & fib ) with( fib ) {
    712         `resume( fib );`
    713         return fn;
    714 }
     712        fn = 0;  int fn1 = fn; `suspend()`;
     713        fn = 1;  int fn2 = fn1;  fn1 = fn; `suspend()`;
     714        for () {
     715                fn = fn1 + fn2; fn2 = fn1; fn1 = fn; `suspend()`; }
     716}
     717int next( Fib & fib ) with( fib ) { `resume( fib );` return fn; }
    715718int main() {
    716719        Fib f1, f2;
    717         for ( int i = 1; i <= 10; i += 1 ) {
     720        for ( 10 )
    718721                sout | next( f1 ) | next( f2 );
    719         }
    720722}
    721723\end{cfa}
     
    723725\newbox\myboxB
    724726\begin{lrbox}{\myboxB}
    725 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
    726 `coroutine` Fib { int ret; };
    727 void main( Fib & f ) with( fib ) {
    728         int fn, f1 = 1, f2 = 0;
    729         for ( ;; ) {
    730                 ret = f2;
    731 
    732                 fn = f1 + f2;  f2 = f1;  f1 = fn; `suspend();`
    733         }
    734 }
    735 int next( Fib & fib ) with( fib ) {
    736         `resume( fib );`
    737         return ret;
    738 }
    739 
    740 
    741 
    742 
    743 
    744 
    745 \end{cfa}
     727\begin{python}[aboveskip=0pt,belowskip=0pt]
     728
     729def Fibonacci():
     730        fn = 0; fn1 = fn; `yield fn`  # suspend
     731        fn = 1; fn2 = fn1; fn1 = fn; `yield fn`
     732        while True:
     733                fn = fn1 + fn2; fn2 = fn1; fn1 = fn; `yield fn`
     734
     735
     736f1 = Fibonacci()
     737f2 = Fibonacci()
     738for i in range( 10 ):
     739        print( `next( f1 )`, `next( f2 )` ) # resume
     740
     741\end{python}
    746742\end{lrbox}
    747 \subfloat[3 States, internal variables]{\label{f:Coroutine3States}\usebox\myboxA}
    748 \qquad\qquad
    749 \subfloat[1 State, internal variables]{\label{f:Coroutine1State}\usebox\myboxB}
    750 \caption{\CFA Coroutine Fibonacci Implementations}
     743\subfloat[\CFA]{\label{f:Coroutine3States}\usebox\myboxA}
     744\qquad
     745\subfloat[Python]{\label{f:Coroutine1State}\usebox\myboxB}
     746\caption{Fibonacci input coroutine, 3 states, internal variables}
    751747\label{f:cfa-fibonacci}
    752748\end{figure}
     
    789785\begin{lrbox}{\myboxA}
    790786\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    791 `coroutine` Format {
    792         char ch;   // used for communication
    793         int g, b;  // global because used in destructor
     787`coroutine` Fmt {
     788        char ch;   // communication variables
     789        int g, b;   // needed in destructor
    794790};
    795 void main( Format & fmt ) with( fmt ) {
    796         for ( ;; ) {
    797                 for ( g = 0; g < 5; g += 1 ) {      // group
    798                         for ( b = 0; b < 4; b += 1 ) { // block
     791void main( Fmt & fmt ) with( fmt ) {
     792        for () {
     793                for ( g = 0; g < 5; g += 1 ) { // groups
     794                        for ( b = 0; b < 4; b += 1 ) { // blocks
    799795                                `suspend();`
    800                                 sout | ch;              // separator
    801                         }
    802                         sout | "  ";               // separator
    803                 }
    804                 sout | nl;
    805         }
    806 }
    807 void ?{}( Format & fmt ) { `resume( fmt );` }
    808 void ^?{}( Format & fmt ) with( fmt ) {
    809         if ( g != 0 || b != 0 ) sout | nl;
    810 }
    811 void format( Format & fmt ) {
    812         `resume( fmt );`
    813 }
     796                                sout | ch; } // print character
     797                        sout | "  "; } // block separator
     798                sout | nl; }  // group separator
     799}
     800void ?{}( Fmt & fmt ) { `resume( fmt );` } // prime
     801void ^?{}( Fmt & fmt ) with( fmt ) { // destructor
     802        if ( g != 0 || b != 0 ) // special case
     803                sout | nl; }
     804void send( Fmt & fmt, char c ) { fmt.ch = c; `resume( fmt )`; }
    814805int main() {
    815         Format fmt;
    816         eof: for ( ;; ) {
    817                 sin | fmt.ch;
    818           if ( eof( sin ) ) break eof;
    819                 format( fmt );
    820         }
     806        Fmt fmt;
     807        sout | nlOff;   // turn off auto newline
     808        for ( 41 )
     809                send( fmt, 'a' );
    821810}
    822811\end{cfa}
     
    825814\newbox\myboxB
    826815\begin{lrbox}{\myboxB}
    827 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
    828 struct Format {
    829         char ch;
    830         int g, b;
    831 };
    832 void format( struct Format * fmt ) {
    833         if ( fmt->ch != -1 ) {      // not EOF ?
    834                 printf( "%c", fmt->ch );
    835                 fmt->b += 1;
    836                 if ( fmt->b == 4 ) {  // block
    837                         printf( "  " );      // separator
    838                         fmt->b = 0;
    839                         fmt->g += 1;
    840                 }
    841                 if ( fmt->g == 5 ) {  // group
    842                         printf( "\n" );     // separator
    843                         fmt->g = 0;
    844                 }
    845         } else {
    846                 if ( fmt->g != 0 || fmt->b != 0 ) printf( "\n" );
    847         }
    848 }
    849 int main() {
    850         struct Format fmt = { 0, 0, 0 };
    851         for ( ;; ) {
    852                 scanf( "%c", &fmt.ch );
    853           if ( feof( stdin ) ) break;
    854                 format( &fmt );
    855         }
    856         fmt.ch = -1;
    857         format( &fmt );
    858 }
    859 \end{cfa}
     816\begin{python}[aboveskip=0pt,belowskip=0pt]
     817
     818
     819
     820def Fmt():
     821        try:
     822                while True:
     823                        for g in range( 5 ):
     824                                for b in range( 4 ):
     825
     826                                        print( `(yield)`, end='' )
     827                                print( '  ', end='' )
     828                        print()
     829
     830
     831        except GeneratorExit:
     832                if g != 0 | b != 0:
     833                        print()
     834
     835
     836fmt = Fmt()
     837`next( fmt )`                    # prime
     838for i in range( 41 ):
     839        `fmt.send( 'a' );`      # send to yield
     840
     841\end{python}
    860842\end{lrbox}
    861 \subfloat[\CFA Coroutine]{\label{f:CFAFmt}\usebox\myboxA}
     843\subfloat[\CFA]{\label{f:CFAFmt}\usebox\myboxA}
    862844\qquad
    863 \subfloat[C Linearized]{\label{f:CFmt}\usebox\myboxB}
    864 \caption{Formatting text into lines of 5 blocks of 4 characters.}
     845\subfloat[Python]{\label{f:CFmt}\usebox\myboxB}
     846\caption{Output formatting text}
    865847\label{f:fmt-line}
    866848\end{figure}
     
    883865void main( Prod & prod ) with( prod ) {
    884866        // 1st resume starts here
    885         for ( int i = 0; i < N; i += 1 ) {
     867        for ( i; N ) {
    886868                int p1 = random( 100 ), p2 = random( 100 );
    887869                sout | p1 | " " | p2;
     
    899881}
    900882void start( Prod & prod, int N, Cons &c ) {
    901         &prod.c = &c;
     883        &prod.c = &c; // reassignable reference
    902884        prod.[N, receipt] = [N, 0];
    903885        `resume( prod );`
     
    914896        Prod & p;
    915897        int p1, p2, status;
    916         _Bool done;
     898        bool done;
    917899};
    918900void ?{}( Cons & cons, Prod & p ) {
    919         &cons.p = &p;
     901        &cons.p = &p; // reassignable reference
    920902        cons.[status, done ] = [0, false];
    921903}
     
    974956The program main restarts after the resume in @start@.
    975957@start@ returns and the program main terminates.
     958
     959One \emph{killer} application for a coroutine is device drivers, which at one time caused 70\%-85\% of failures in Windows/Linux~\cite{Swift05}.
     960Many device drivers are a finite state-machine parsing a protocol, e.g.:
     961\begin{tabbing}
     962\ldots STX \= \ldots message \ldots \= ESC \= ETX \= \ldots message \ldots  \= ETX \= 2-byte crc \= \ldots      \kill
     963\ldots STX \> \ldots message \ldots \> ESC \> ETX \> \ldots message \ldots  \> ETX \> 2-byte crc \> \ldots
     964\end{tabbing}
     965where a network message begins with the control character STX and ends with an ETX, followed by a 2-byte cyclic-redundancy check.
     966Control characters may appear in a message if preceded by an ESC.
     967Because FSMs can be complex and occur frequently in important domains, direct support of the coroutine is crucial in a systems programminglanguage.
     968
     969\begin{figure}
     970\begin{cfa}
     971enum Status { CONT, MSG, ESTX, ELNTH, ECRC };
     972`coroutine` Driver {
     973        Status status;
     974        char * msg, byte;
     975};
     976void ?{}( Driver & d, char * m ) { d.msg = m; }         $\C[3.0in]{// constructor}$
     977Status next( Driver & d, char b ) with( d ) {           $\C{// 'with' opens scope}$
     978        byte = b; `resume( d );` return status;
     979}
     980void main( Driver & d ) with( d ) {
     981        enum { STX = '\002', ESC = '\033', ETX = '\003', MaxMsg = 64 };
     982        unsigned short int crc;                                                 $\C{// error checking}$
     983  msg: for () {                                                                         $\C{// parse message}$
     984                status = CONT;
     985                unsigned int lnth = 0, sum = 0;
     986                while ( byte != STX ) `suspend();`
     987          emsg: for () {
     988                        `suspend();`                                                    $\C{// process byte}$
     989                        choose ( byte ) {                                               $\C{// switch with default break}$
     990                          case STX:
     991                                status = ESTX; `suspend();` continue msg;
     992                          case ETX:
     993                                break emsg;
     994                          case ESC:
     995                                suspend();
     996                        } // choose
     997                        if ( lnth >= MaxMsg ) {                                 $\C{// buffer full ?}$
     998                                status = ELNTH; `suspend();` continue msg; }
     999                        msg[lnth++] = byte;
     1000                        sum += byte;
     1001                } // for
     1002                msg[lnth] = '\0';                                                       $\C{// terminate string}\CRT$
     1003                `suspend();`
     1004                crc = (unsigned char)byte << 8; // prevent sign extension for signed char
     1005                `suspend();`
     1006                status = (crc | (unsigned char)byte) == sum ? MSG : ECRC;
     1007                `suspend();`
     1008        } // for
     1009}
     1010\end{cfa}
     1011\caption{Device driver for simple communication protocol}
     1012\end{figure}
    9761013
    9771014
Note: See TracChangeset for help on using the changeset viewer.