Changeset 35bae526 for doc/proposals/concurrency/text/basics.tex
- Timestamp:
- Nov 30, 2017, 12:41:59 PM (6 years ago)
- 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:
- c2b9f21
- Parents:
- 875a72f (diff), 389528b0 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)
links above to see all the changes relative to each parent. - File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/proposals/concurrency/text/basics.tex
r875a72f r35bae526 11 11 Execution with a single thread and multiple stacks where the thread is self-scheduling deterministically across the stacks is called coroutining. Execution with a single and multiple stacks but where the thread is scheduled by an oracle (non-deterministic from the thread perspective) across the stacks is called concurrency. 12 12 13 Therefore, a minimal concurrency system can be achieved by creating coroutines, which instead of context switching among each other, always ask an oracle where to context switch next. While coroutines can execute on the caller's stack-frame, stack full coroutines allow full generality and are sufficient as the basis for concurrency. The aforementioned oracle is a scheduler and the whole system now follows a cooperative threading-model (a.k.a non-preemptive scheduling). The oracle/scheduler can either be a stackless or stackfull entity and correspondingly require one or two context switches to run a different coroutine. In any case, a subset of concurrency related challenges start to appear. For the complete set of concurrency challenges to occur, the only feature missing is preemption.14 15 A scheduler introduces order of execution uncertainty, while preemption introduces uncertainty about where context-switches occur. Mutual-exclusion and synchroni sation are ways of limiting non-determinism in a concurrent system. Now it is important to understand that uncertainty is desireable; uncertainty can be used by runtime systems to significantly increase performance and is often the basis of giving a user the illusion that tasks are running in parallel. Optimal performance in concurrent applications is often obtained by having as much non-determinism as correctness allows.13 Therefore, a minimal concurrency system can be achieved by creating coroutines, which instead of context switching among each other, always ask an oracle where to context switch next. While coroutines can execute on the caller's stack-frame, stack-full coroutines allow full generality and are sufficient as the basis for concurrency. The aforementioned oracle is a scheduler and the whole system now follows a cooperative threading-model (a.k.a non-preemptive scheduling). The oracle/scheduler can either be a stack-less or stack-full entity and correspondingly require one or two context switches to run a different coroutine. In any case, a subset of concurrency related challenges start to appear. For the complete set of concurrency challenges to occur, the only feature missing is preemption. 14 15 A scheduler introduces order of execution uncertainty, while preemption introduces uncertainty about where context-switches occur. Mutual-exclusion and synchronization are ways of limiting non-determinism in a concurrent system. Now it is important to understand that uncertainty is desirable; uncertainty can be used by runtime systems to significantly increase performance and is often the basis of giving a user the illusion that tasks are running in parallel. Optimal performance in concurrent applications is often obtained by having as much non-determinism as correctness allows. 16 16 17 17 \section{\protect\CFA 's Thread Building Blocks} 18 One of the important features that is missing in C is threading. On modern architectures, a lack of threading is unacceptable \cite{Sutter05, Sutter05b}, and therefore modern programming languages must have the proper tools to allow users to write performant concurrent programs to take advantage of parallelism. As an extension of C, \CFA needs to express these concepts in a way that is as natural as possible to programmers familiar with imperative languages. And being a system-level language means programmers expect to choose precisely which features they need and which cost they are willing to pay.18 One of the important features that is missing in C is threading. On modern architectures, a lack of threading is unacceptable~\cite{Sutter05, Sutter05b}, and therefore modern programming languages must have the proper tools to allow users to write performant concurrent programs to take advantage of parallelism. As an extension of C, \CFA needs to express these concepts in a way that is as natural as possible to programmers familiar with imperative languages. And being a system-level language means programmers expect to choose precisely which features they need and which cost they are willing to pay. 19 19 20 20 \section{Coroutines: A stepping stone}\label{coroutine} 21 21 While the main focus of this proposal is concurrency and parallelism, it is important to address coroutines, which are actually a significant building block of a concurrency system. Coroutines need to deal with context-switches 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. Furthermore, many design challenges of threads are at least partially present in designing coroutines, which makes the design effort that much more relevant. The core \acrshort{api} of coroutines revolve around two features: independent call stacks and \code{suspend}/\code{resume}. 22 22 23 \begin{ figure}23 \begin{table} 24 24 \begin{center} 25 25 \begin{tabular}{c @{\hskip 0.025in}|@{\hskip 0.025in} c @{\hskip 0.025in}|@{\hskip 0.025in} c} … … 62 62 void fibonacci_array( 63 63 int n, 64 int 64 int* array 65 65 ) { 66 66 int f1 = 0; int f2 = 1; … … 99 99 100 100 int fibonacci_state( 101 Iterator_t 101 Iterator_t* it 102 102 ) { 103 103 int f; … … 129 129 \end{tabular} 130 130 \end{center} 131 \caption{Different implementations of a fibonacci sequence generator in C.}131 \caption{Different implementations of a Fibonacci sequence generator in C.}, 132 132 \label{lst:fibonacci-c} 133 \end{ figure}134 135 A good example of a problem made easier with coroutines is generators, like the fibonacci sequence. This problem comes with the challenge of decoupling how a sequence is generated and how it is used. Figure \ref{lst:fibonacci-c} shows conventional approaches to writing generators in C. All three of these approach suffer from strong coupling. The left and center approaches require that the generator have knowledge of how the sequence is used, while the rightmost approach requires holding internal state between calls on behalf of the generator and makes it much harder to handle corner cases like the Fibonacci seed.136 137 Figure \ref{lst:fibonacci-cfa} is an example of a solution to the fibonnaci problem using \CFA coroutines, where the coroutine stack holds sufficient state for the generation. This solution has the advantage of having very strong decoupling between how the sequence is generated and how it is used. Indeed, this version is as easy to use as the \code{fibonacci_state} solution, while the imlpementation is very similar to the \code{fibonacci_func} example.133 \end{table} 134 135 A good example of a problem made easier with coroutines is generators, like the Fibonacci sequence. This problem comes with the challenge of decoupling how a sequence is generated and how it is used. Table \ref{lst:fibonacci-c} shows conventional approaches to writing generators in C. All three of these approach suffer from strong coupling. The left and center approaches require that the generator have knowledge of how the sequence is used, while the rightmost approach requires holding internal state between calls on behalf of the generator and makes it much harder to handle corner cases like the Fibonacci seed. 136 137 Listing \ref{lst:fibonacci-cfa} is an example of a solution to the Fibonacci problem using \CFA coroutines, where the coroutine stack holds sufficient state for the next generation. This solution has the advantage of having very strong decoupling between how the sequence is generated and how it is used. Indeed, this version is as easy to use as the \code{fibonacci_state} solution, while the implementation is very similar to the \code{fibonacci_func} example. 138 138 139 139 \begin{figure} 140 \begin{cfacode} 140 \begin{cfacode}[caption={Implementation of Fibonacci using coroutines},label={lst:fibonacci-cfa}] 141 141 coroutine Fibonacci { 142 142 int fn; //used for communication 143 143 }; 144 144 145 void ?{}(Fibonacci 145 void ?{}(Fibonacci& this) { //constructor 146 146 this.fn = 0; 147 147 } 148 148 149 //main automa cically called on first resume150 void main(Fibonacci 149 //main automatically called on first resume 150 void main(Fibonacci& this) with (this) { 151 151 int fn1, fn2; //retained between resumes 152 152 fn = 0; … … 167 167 } 168 168 169 int next(Fibonacci 169 int next(Fibonacci& this) { 170 170 resume(this); //transfer to last suspend 171 171 return this.fn; … … 179 179 } 180 180 \end{cfacode} 181 \caption{Implementation of fibonacci using coroutines}182 \label{lst:fibonacci-cfa}183 181 \end{figure} 184 182 185 Figure \ref{lst:fmt-line} shows the \code{Format} coroutine which rearranges text in order to group characters intoblocks of fixed size. The example takes advantage of resuming coroutines in the constructor to simplify the code and highlights the idea that interesting control flow can occur in the constructor.183 Listing \ref{lst:fmt-line} shows the \code{Format} coroutine for restructuring text into groups of character blocks of fixed size. The example takes advantage of resuming coroutines in the constructor to simplify the code and highlights the idea that interesting control flow can occur in the constructor. 186 184 187 185 \begin{figure} 188 \begin{cfacode}[tabsize=3 ]186 \begin{cfacode}[tabsize=3,caption={Formatting text into lines of 5 blocks of 4 characters.},label={lst:fmt-line}] 189 187 //format characters into blocks of 4 and groups of 5 blocks per line 190 188 coroutine Format { … … 193 191 }; 194 192 195 void ?{}(Format 193 void ?{}(Format& fmt) { 196 194 resume( fmt ); //prime (start) coroutine 197 195 } 198 196 199 void ^?{}(Format 197 void ^?{}(Format& fmt) with fmt { 200 198 if ( fmt.g != 0 || fmt.b != 0 ) 201 199 sout | endl; 202 200 } 203 201 204 void main(Format 202 void main(Format& fmt) with fmt { 205 203 for ( ;; ) { //for as many characters 206 204 for(g = 0; g < 5; g++) { //groups of 5 blocks … … 230 228 } 231 229 \end{cfacode} 232 \caption{Formatting text into lines of 5 blocks of 4 characters.}233 \label{lst:fmt-line}234 230 \end{figure} 235 231 236 232 \subsection{Construction} 237 One important design challenge for coroutines and threads (shown in section \ref{threads}) is that the runtime system needs to run code after the user-constructor runs to connect the fully constructed object into the system. In the case of coroutines, this challenge is simpler since there is no non-determinism from preemption or scheduling. However, the underlying challenge remains the same for coroutines and threads.238 239 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 execution enters the coroutine main and to be able to resume the coroutine from the constructor. As regular objects, constructors can leak coroutines before they are ready.There are several solutions to this problem but the chosen options effectively forces the design of the coroutine.233 One important design challenge for implementing coroutines and threads (shown in section \ref{threads}) is that the runtime system needs to run code after the user-constructor runs to connect the fully constructed object into the system. In the case of coroutines, this challenge is simpler since there is no non-determinism from preemption or scheduling. However, the underlying challenge remains the same for coroutines and threads. 234 235 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 execution enters the coroutine main and to be able to resume the coroutine from the constructor. There are several solutions to this problem but the chosen options effectively forces the design of the coroutine. 240 236 241 237 Furthermore, \CFA faces an extra challenge as polymorphic routines create invisible thunks when casted to non-polymorphic routines and these thunks have function scope. For example, the following code, while looking benign, can run into undefined behaviour because of thunks: … … 258 254 259 255 \begin{ccode} 260 extern void async(/* omitted */, void (*func)(void *), void *obj);261 262 void noop(/* omitted */, void *obj){}256 extern void async(/* omitted */, void (*func)(void*), void* obj); 257 258 void noop(/* omitted */, void* obj){} 263 259 264 260 void bar(){ 265 261 int a; 266 void _thunk0(int *_p0){262 void _thunk0(int* _p0){ 267 263 /* omitted */ 268 264 noop(/* omitted */, _p0); 269 265 } 270 266 /* omitted */ 271 async(/* omitted */, ((void (*)(void 267 async(/* omitted */, ((void (*)(void*))(&_thunk0)), (&a)); 272 268 } 273 269 \end{ccode} 274 The problem in this example is a storage management issue, the function pointer \code{_thunk0} is only valid until the end of the block, which limits the viable solutions because storing the function pointer for too long causes undefined behavior; i.e., the stack-based thunk being destroyed before it can be used. This challenge is an extension of challenges that come with second-class routines. Indeed, GCC nested routines also have the limitation that nested routine cannot be passed outside of the declaration scope. The case of coroutines and threads is simply an extension of this problem to multiple call-stacks.270 The problem in this example is a storage management issue, the function pointer \code{_thunk0} is only valid until the end of the block, which limits the viable solutions because storing the function pointer for too long causes Undefined Behavior; i.e., the stack-based thunk being destroyed before it can be used. This challenge is an extension of challenges that come with second-class routines. Indeed, GCC nested routines also have the limitation that nested routine cannot be passed outside of the declaration scope. The case of coroutines and threads is simply an extension of this problem to multiple call-stacks. 275 271 276 272 \subsection{Alternative: Composition} 277 One solution to this challenge is to use composition/contain ement, where coroutine fields are added to manage the coroutine.273 One solution to this challenge is to use composition/containment, where coroutine fields are added to manage the coroutine. 278 274 279 275 \begin{cfacode} … … 283 279 }; 284 280 285 void FibMain(void 281 void FibMain(void*) { 286 282 //... 287 283 } 288 284 289 void ?{}(Fibonacci 285 void ?{}(Fibonacci& this) { 290 286 this.fn = 0; 291 287 //Call constructor to initialize coroutine … … 293 289 } 294 290 \end{cfacode} 295 The downside of this approach is that users need to correctly construct the coroutine handle before using it. Like any other objects, doing so the users carefully choose construction order to prevent usage of unconstructed objects. However, in the case of coroutines, users must also pass to the coroutine information about the coroutine main, like in the previous example. This opens the door for user errors and requires extra runtime storage to pass at runtime information that can be known statically.291 The downside of this approach is that users need to correctly construct the coroutine handle before using it. Like any other objects, the user must carefully choose construction order to prevent usage of objects not yet constructed. However, in the case of coroutines, users must also pass to the coroutine information about the coroutine main, like in the previous example. This opens the door for user errors and requires extra runtime storage to pass at runtime information that can be known statically. 296 292 297 293 \subsection{Alternative: Reserved keyword} … … 303 299 }; 304 300 \end{cfacode} 305 The \code{coroutine} keyword means the compiler can find and inject code where needed. The downside of this approach is that it makes coroutine a special case in the language. Users wantin tto 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 the programming language used. While this is ultimately the option used for idiomatic \CFA code, coroutines and threads can still be constructed by users without using the language support. The reserved keywords are only present to improve ease of use for the common cases.306 307 \subsection{Alternative: Lam da Objects}308 309 For coroutines as for threads, many implementations are based on routine pointers or function objects \cite{Butenhof97, ANSI14:C++, MS:VisualC++, BoostCoroutines15}. For example, Boost implements coroutines in terms of four functor object types:301 The \code{coroutine} keyword means the compiler can find and inject code where needed. The downside of this approach is that it makes coroutine a special case in the language. Users wanting 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 the programming language used. While this is ultimately the option used for idiomatic \CFA code, coroutines and threads can still be constructed by users without using the language support. The reserved keywords are only present to improve ease of use for the common cases. 302 303 \subsection{Alternative: Lambda Objects} 304 305 For coroutines as for threads, many implementations are based on routine pointers or function objects~\cite{Butenhof97, ANSI14:C++, MS:VisualC++, BoostCoroutines15}. For example, Boost implements coroutines in terms of four functor object types: 310 306 \begin{cfacode} 311 307 asymmetric_coroutine<>::pull_type … … 318 314 A variation of this would be to use a simple function pointer in the same way pthread does for threads : 319 315 \begin{cfacode} 320 void foo( coroutine_t cid, void 321 int * value = (int*)arg;316 void foo( coroutine_t cid, void* arg ) { 317 int* value = (int*)arg; 322 318 //Coroutine body 323 319 } … … 329 325 } 330 326 \end{cfacode} 331 This semantics is more common for thread interfaces than coroutines works equally well. As discussed in section \ref{threads}, this approach is superseeded by static approaches in terms of expressivity.327 This semantics is more common for thread interfaces but coroutines work equally well. As discussed in section \ref{threads}, this approach is superseded by static approaches in terms of expressivity. 332 328 333 329 \subsection{Alternative: Trait-based coroutines} … … 337 333 \begin{cfacode} 338 334 trait is_coroutine(dtype T) { 339 void main(T 340 coroutine_desc * get_coroutine(T& this);341 }; 342 343 forall( dtype T | is_coroutine(T) ) void suspend(T 344 forall( dtype T | is_coroutine(T) ) void resume (T 345 \end{cfacode} 346 This ensures an object is not a coroutine until \code{resume} 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. The advantage of this approach is that users can easily create different types of coroutines, for example, changing the memory layout of a coroutine is trivial when implementing the \code{get_coroutine} routine. The \CFA keyword \code{coroutine} only has the effect of implementing the getter and forward declarations required for users to only have toimplement the main routine.335 void main(T& this); 336 coroutine_desc* get_coroutine(T& this); 337 }; 338 339 forall( dtype T | is_coroutine(T) ) void suspend(T&); 340 forall( dtype T | is_coroutine(T) ) void resume (T&); 341 \end{cfacode} 342 This ensures an object is not a coroutine until \code{resume} 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. The advantage of this approach is that users can easily create different types of coroutines, for example, changing the memory layout of a coroutine is trivial when implementing the \code{get_coroutine} routine. The \CFA keyword \code{coroutine} only has the effect of implementing the getter and forward declarations required for users to implement the main routine. 347 343 348 344 \begin{center} … … 359 355 360 356 static inline 361 coroutine_desc 362 struct MyCoroutine 357 coroutine_desc* get_coroutine( 358 struct MyCoroutine& this 363 359 ) { 364 360 return &this.__cor; 365 361 } 366 362 367 void main(struct MyCoroutine 363 void main(struct MyCoroutine* this); 368 364 \end{cfacode} 369 365 \end{tabular} 370 366 \end{center} 371 367 372 The combination of these two approaches allows users new to coroutin ning and concurrency to have an easy and concise specification, while more advanced users have tighter control on memory layout and initialization.368 The combination of these two approaches allows users new to coroutining and concurrency to have an easy and concise specification, while more advanced users have tighter control on memory layout and initialization. 373 369 374 370 \section{Thread Interface}\label{threads} … … 379 375 \end{cfacode} 380 376 381 As for coroutines, the keyword is a thin wrapper aroun ta \CFA trait:377 As for coroutines, the keyword is a thin wrapper around a \CFA trait: 382 378 383 379 \begin{cfacode} … … 389 385 \end{cfacode} 390 386 391 Obviously, for this thread implementation to be useful l it must run some user code. Several other threading interfaces use a function-pointer representation as the interface of threads (for example \Csharp~\cite{Csharp} and Scala~\cite{Scala}). However, this proposal considers that statically tying a \code{main} routine to a thread superseeds this approach. Since the \code{main} routine is already a special routine in \CFA (where the program begins), it is a natural extension of the semantics using overloading to declare mains for different threads (the normal main being the main of the initial thread). As such the \code{main} routine of a thread can be defined as387 Obviously, for this thread implementation to be useful it must run some user code. Several other threading interfaces use a function-pointer representation as the interface of threads (for example \Csharp~\cite{Csharp} and Scala~\cite{Scala}). However, this proposal considers that statically tying a \code{main} routine to a thread supersedes this approach. Since the \code{main} routine is already a special routine in \CFA (where the program begins), it is a natural extension of the semantics using overloading to declare mains for different threads (the normal main being the main of the initial thread). As such the \code{main} routine of a thread can be defined as 392 388 \begin{cfacode} 393 389 thread foo {}; … … 416 412 this.func( this.arg ); 417 413 } 414 415 void hello(/*unused*/ int) { 416 sout | "Hello World!" | endl; 417 } 418 419 int main() { 420 FuncRunner f = {hello, 42}; 421 return 0' 422 } 418 423 \end{cfacode} 419 424 … … 439 444 \end{cfacode} 440 445 441 This semantic has several advantages over explicit semantics: a thread is always started and stopped exac lty once, users cannot make any progamming errors, and it naturally scales to multiple threads meaning basic synchronisation is very simple.446 This semantic has several advantages over explicit semantics: a thread is always started and stopped exactly once, users cannot make any programming errors, and it naturally scales to multiple threads meaning basic synchronization is very simple. 442 447 443 448 \begin{cfacode} … … 447 452 448 453 //main 449 void main(MyThread 454 void main(MyThread& this) { 450 455 //... 451 456 } … … 461 466 \end{cfacode} 462 467 463 However, one of the drawbacks of this approach is that threads now always form a lattice, that isthey are always destroyed in the opposite order of construction because of block structure. This restriction is relaxed by using dynamic allocation, so threads can outlive the scope in which they are created, much like dynamically allocating memory lets objects outlive the scope in which they are created.468 However, one of the drawbacks of this approach is that threads always form a lattice, i.e., they are always destroyed in the opposite order of construction because of block structure. This restriction is relaxed by using dynamic allocation, so threads can outlive the scope in which they are created, much like dynamically allocating memory lets objects outlive the scope in which they are created. 464 469 465 470 \begin{cfacode} … … 468 473 }; 469 474 470 void main(MyThread 475 void main(MyThread& this) { 471 476 //... 472 477 } 473 478 474 479 void foo() { 475 MyThread 480 MyThread* long_lived; 476 481 { 477 482 //Start a thread at the beginning of the scope
Note: See TracChangeset
for help on using the changeset viewer.