Changeset f7ff3fb

Timestamp:

Jan 9, 2017, 4:35:40 PM (8 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc

Children:

17e5e2b

Parents:

66f8528

Message:

Some more work on concurrency proposal paper

Location:

doc/proposals/concurrency

Files:

• concurrency.tex (modified) (6 diffs)
• cor-thread-traits.c (added)
• version (modified) (1 diff)

doc/proposals/concurrency/concurrency.tex ¶

@@ -149 +149 @@
 
 \begin{lstlisting}
-        mutex struct counter_t { /*...see section §\ref{data}§...*/ };
+        mutex struct counter_t { /*...see section §\ref{data}§...*/ };
 
         void ?{}(counter_t & nomutex this); //constructor
@@ -767 +767 @@
 TO BE CONTINUED...
 
+
+
+
+
+
+
+
+
+
 \newpage
 % ######     #    ######     #    #       #       ####### #       ###  #####  #     #
@@ -807 +816 @@
 As a system-level language, \CFA should offer both performance and flexibilty as its primary goals, simplicity and user-friendliness being a secondary concern. Therefore, the core of parallelism in \CFA should prioritize power and efficiency. With this said, deconstructing popular paradigms in order to get simple building blocks yields \glspl{uthread} as the core parallelism block. \Glspl{pool} and other parallelism paradigms can then be built on top of the underlying threading model.
 
+\subsection{Coroutines : A stepping stone}\label{coroutine}
+While the main focus of this proposal is concurrency and paralellism, it is important to adress coroutines which are actually a significant underlying aspect of the concurrency system. Indeed, while having nothing todo with parallelism and arguably very little to do with concurrency, coroutines need to deal with context-switchs and and other context management operations. Therefore, this proposal includes coroutines both as an intermediate step for the implementation of threads and a first class feature of \CFA.
+
+The core API of coroutines revolve around two features : independent stacks and \code{suspend}/\code{resume}.
+Here is an example of a solution to the fibonnaci problem using \CFA coroutines :
+\begin{lstlisting}
+        struct Fibonacci {
+              int fn; // used for communication
+              coroutine_descriptor c;
+        };
+
+        void ?{}(Fibonacci* this) {
+              this->fn = 0;
+        }
+
+        coroutine_descriptor* get_¶coroutine¶(Fibonacci* this) {
+              return &this->c;
+        }
+
+        void co_main(Fibonacci* this) {
+                int fn1, fn2;           // retained between resumes
+                this->fn = 0;
+                fn1 = this->fn;
+                suspend(this);          // return to last resume
+
+                this->fn = 1;
+                fn2 = fn1;
+                fn1 = this->fn;
+                suspend(this);          // return to last resume
+
+                for ( ;; ) {
+                        this->fn = fn1 + fn2;
+                        fn2 = fn1;
+                        fn1 = this->fn;
+                        suspend(this);  // return to last resume
+                }
+        }
+
+        int next(Fibonacci* this) {
+                resume(this); // transfer to last suspend
+                return this.fn;
+        }
+
+        void main() {
+                Fibonacci f1, f2;
+                for ( int i = 1; i <= 10; i += 1 ) {
+                        sout | next(&f1) | '§\verb+ +§' | next(&f2) | endl;
+                }
+        }
+\end{lstlisting}
+
+\subsubsection{Construction}
+One important design challenge for coroutines and threads (shown in section \ref{threads}) is that the runtime system needs to run some code after the user-constructor runs. In the case of the coroutines this challenge is simpler since there is no loss of determinism brough by preemption or scheduling, however, the underlying challenge remains the same for coroutines and threads.
+
+The runtime system needs to create the coroutine's stack and more importantly prepare it for the first resumption. The timing of the creation is non trivial since users both expect to have fully constructed objects once the main is called and to be able to resume the coroutine from the main (Obviously we only solve cases where these two statements don't conflict). There are several solutions to this problem but the chosen options effectively forces the design of the coroutine.
+
+Furthermore, \CFA faces an extra challenge which is that polymorphique routines rely on invisible thunks when casted to non-polymorphic routines and these thunks have function scope, for example :
+
+TODO : Simple case where a thunk would be created.
+
+
+
+\subsubsection{Alternative: Inheritance}
+One solution to this challenge would be to use inheritence,
+
+\begin{lstlisting}
+        struct Fibonacci {
+              int fn; // used for communication
+              coroutine c;
+        };
+
+        void ?{}(Fibonacci* this) {
+              this->fn = 0;
+                (&this->c){};
+        }
+\end{lstlisting}
+
+There are two downsides to the approach. The first, which is relatively minor, is that the base class needs to be made aware of the main routine pointer, regardless of whether we use a parameter or a virtual pointer, this means the coroutine data must be made larger to store a value that is actually a compile time constant (The address of the main routine). The second problem which is both subtle but significant, is that now can get the initialisation order of there coroutines wrong. Indeed, every field of a \CFA struct will be constructed but in the order of declaration, unless users explicitly write otherwise. This means that users who forget to initialize a the coroutine at the right time may resume the coroutine at with an uninitilized object. For coroutines, this is unlikely to be a problem, for threads however, this is a significant problem.
+
+\subsubsection{Alternative: Reserved keyword}
+The next alternative is to use language support to annotate coroutines as follows :
+
+\begin{lstlisting}
+        coroutine struct Fibonacci {
+              int fn; // used for communication
+        };
+\end{lstlisting}
+
+This mean the compiler can solve problems by injecting code where needed. The downside of this approach is that it makes coroutine a special case in the language. Users who would want to extend coroutines or build their own for various reasons can only do so in ways offered by the language. Furthermore, implementing coroutines without language supports also displays the power of \CFA.
+
+\subsubsection{Alternative: Lamda Objects}
+
+Boost does not use objects...
+TO BE CONTINUED...
+
+\subsubsection{Trait based coroutines}
+
+Finally the approach chosen, which is the one closest to \CFA idioms, is to use trait-based lazy coroutines, the approach shown in section \ref{coroutine}. This approach defines a coroutine as anything that satisfies the \code{is_coroutine} and is used as a coroutine is a coroutine. This entails the an object is not a coroutine until \code{resume} (and \code{prime}) is called on the object. Correspondingly, any object that is passed to \code{resume} is a coroutine since it must satisfy the \code{is_coroutine} trait to compile.
+
 % ####### #     # ######  #######    #    ######   #####
 %    #    #     # #     # #         # #   #     # #     #
@@ -815 +923 @@
 %    #    #     # #     # ####### #     # ######   #####
 
-\subsection{Thread Interface}
+\subsection{Thread Interface}\label{threads}
 The basic building blocks of \CFA are \glspl{cfathread}. By default these are implemented as \glspl{uthread}, and as such, offer a flexible and lightweight threading interface (lightweight compared to \glspl{kthread}). A thread can be declared using a struct declaration with prefix \code{thread} as follows :
 
 \begin{lstlisting}
+        trait is_¶thread¶(dtype T) {
+                void co_main(T* this);
+                coroutine* get_coroutine(T* this);
+        };
+
         thread struct foo {};
 \end{lstlisting}
@@ -845 +958 @@
 
         //main
-        void ?main(FuncRunner* this) {
+        void t_main(FuncRunner* this) {
                 this->func();
         }
@@ -927 +1040 @@
 
                 //Wait for the 10 threads to finish
-        }
-\end{lstlisting}
-
-\subsection{Coroutines : A stepping stone}\label{coroutine}
-While the main focus of this proposal is concurrency and paralellism, it is important to adress coroutines which are actually a significant underlying aspect of the concurrency system. Indeed, while having nothing todo with parallelism and arguably very little to do with concurrency, coroutines need to deal with context-switchs and and other context management operations. Therefore, this proposal includes coroutines both as an intermediate step for the implementation of threads and a first class feature of \CFA.
-
-The core API of coroutines revolve around two features : independent stacks and suspedn/resume. Much like threads the syntax for declaring a coroutine is declaring a type and a main routine for it to start :
-\begin{lstlisting}
-        coroutine struct MyCoroutine {
-                //...
-        };
-
-        //ctor
-        void ?{}(MyCoroutine* this) {
-
-        }
-
-        //main
-        void ?main(MyCoroutine* this) {
-                sout | "Hello World!" | endl;
-        }
-\end{lstlisting}
-
-One a coroutine is created, users can context switch to it using \code{suspend} and come back using \code{resume}. Here is an example of a solution to the fibonnaci problem using coroutines :
-\begin{lstlisting}
-        coroutine struct Fibonacci {
-                int fn; // used for communication
-        };
-
-        void ?main(Fibonacci* this) {
-                int fn1, fn2;           // retained between resumes
-                this->fn = 0;
-                fn1 = this->fn;
-                suspend(this);          // return to last resume
-
-                this->fn = 1;
-                fn2 = fn1;
-                fn1 = this->fn;
-                suspend(this);          // return to last resume
-
-                for ( ;; ) {
-                        this->fn = fn1 + fn2;
-                        fn2 = fn1;
-                        fn1 = this->fn;
-                        suspend(this);  // return to last resume
-                }
-        }
-
-        int next(Fibonacci& this) {
-                resume(&this); // transfer to last suspend
-                return this.fn;
-        }
-
-        void main() {
-                Fibonacci f1, f2;
-                for ( int i = 1; i <= 10; i += 1 ) {
-                        sout | next(f1) | '§\verb+ +§' | next(f2) | endl;
-                }
         }
 \end{lstlisting}

doc/proposals/concurrency/version ¶

@@ -1 @@
-0.7.48
+0.7.61