Changes in / [d3a85240:dd0c97b]
- Files:
-
- 1 deleted
- 11 edited
-
doc/proposals/concurrency/concurrency.tex (modified) (6 diffs)
-
doc/proposals/concurrency/cor-thread-traits.c (deleted)
-
doc/proposals/concurrency/version (modified) (1 diff)
-
src/libcfa/concurrency/threads (modified) (2 diffs)
-
src/libcfa/containers/vector (modified) (2 diffs)
-
src/libcfa/fstream (modified) (2 diffs)
-
src/libcfa/iostream (modified) (2 diffs)
-
src/libcfa/iterator (modified) (2 diffs)
-
src/libcfa/limits (modified) (2 diffs)
-
src/libcfa/math (modified) (2 diffs)
-
src/libcfa/rational (modified) (2 diffs)
-
src/libcfa/stdlib (modified) (2 diffs)
Legend:
- Unmodified
- Added
- Removed
-
doc/proposals/concurrency/concurrency.tex
rd3a85240 rdd0c97b 149 149 150 150 \begin{lstlisting} 151 mutex struct counter_t { /*...see section §\ref{data}§...*/ };151 mutex struct counter_t { /*...see section §\ref{data}§...*/ }; 152 152 153 153 void ?{}(counter_t & nomutex this); //constructor … … 767 767 TO BE CONTINUED... 768 768 769 770 771 772 773 774 775 776 777 778 769 \newpage 779 770 % ###### # ###### # # # ####### # ### ##### # # … … 816 807 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. 817 808 818 \subsection{Coroutines : A stepping stone}\label{coroutine}819 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.820 821 The core API of coroutines revolve around two features : independent stacks and \code{suspend}/\code{resume}.822 Here is an example of a solution to the fibonnaci problem using \CFA coroutines :823 \begin{lstlisting}824 struct Fibonacci {825 int fn; // used for communication826 coroutine_descriptor c;827 };828 829 void ?{}(Fibonacci* this) {830 this->fn = 0;831 }832 833 coroutine_descriptor* get_¶coroutine¶(Fibonacci* this) {834 return &this->c;835 }836 837 void co_main(Fibonacci* this) {838 int fn1, fn2; // retained between resumes839 this->fn = 0;840 fn1 = this->fn;841 suspend(this); // return to last resume842 843 this->fn = 1;844 fn2 = fn1;845 fn1 = this->fn;846 suspend(this); // return to last resume847 848 for ( ;; ) {849 this->fn = fn1 + fn2;850 fn2 = fn1;851 fn1 = this->fn;852 suspend(this); // return to last resume853 }854 }855 856 int next(Fibonacci* this) {857 resume(this); // transfer to last suspend858 return this.fn;859 }860 861 void main() {862 Fibonacci f1, f2;863 for ( int i = 1; i <= 10; i += 1 ) {864 sout | next(&f1) | '§\verb+ +§' | next(&f2) | endl;865 }866 }867 \end{lstlisting}868 869 \subsubsection{Construction}870 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.871 872 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.873 874 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 :875 876 TODO : Simple case where a thunk would be created.877 878 879 880 \subsubsection{Alternative: Inheritance}881 One solution to this challenge would be to use inheritence,882 883 \begin{lstlisting}884 struct Fibonacci {885 int fn; // used for communication886 coroutine c;887 };888 889 void ?{}(Fibonacci* this) {890 this->fn = 0;891 (&this->c){};892 }893 \end{lstlisting}894 895 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.896 897 \subsubsection{Alternative: Reserved keyword}898 The next alternative is to use language support to annotate coroutines as follows :899 900 \begin{lstlisting}901 coroutine struct Fibonacci {902 int fn; // used for communication903 };904 \end{lstlisting}905 906 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.907 908 \subsubsection{Alternative: Lamda Objects}909 910 Boost does not use objects...911 TO BE CONTINUED...912 913 \subsubsection{Trait based coroutines}914 915 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.916 917 809 % ####### # # ###### ####### # ###### ##### 918 810 % # # # # # # # # # # # # … … 923 815 % # # # # # ####### # # ###### ##### 924 816 925 \subsection{Thread Interface} \label{threads}817 \subsection{Thread Interface} 926 818 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 : 927 819 928 820 \begin{lstlisting} 929 trait is_¶thread¶(dtype T) {930 void co_main(T* this);931 coroutine* get_coroutine(T* this);932 };933 934 821 thread struct foo {}; 935 822 \end{lstlisting} … … 958 845 959 846 //main 960 void t_main(FuncRunner* this) {847 void ?main(FuncRunner* this) { 961 848 this->func(); 962 849 } … … 1040 927 1041 928 //Wait for the 10 threads to finish 929 } 930 \end{lstlisting} 931 932 \subsection{Coroutines : A stepping stone}\label{coroutine} 933 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. 934 935 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 : 936 \begin{lstlisting} 937 coroutine struct MyCoroutine { 938 //... 939 }; 940 941 //ctor 942 void ?{}(MyCoroutine* this) { 943 944 } 945 946 //main 947 void ?main(MyCoroutine* this) { 948 sout | "Hello World!" | endl; 949 } 950 \end{lstlisting} 951 952 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 : 953 \begin{lstlisting} 954 coroutine struct Fibonacci { 955 int fn; // used for communication 956 }; 957 958 void ?main(Fibonacci* this) { 959 int fn1, fn2; // retained between resumes 960 this->fn = 0; 961 fn1 = this->fn; 962 suspend(this); // return to last resume 963 964 this->fn = 1; 965 fn2 = fn1; 966 fn1 = this->fn; 967 suspend(this); // return to last resume 968 969 for ( ;; ) { 970 this->fn = fn1 + fn2; 971 fn2 = fn1; 972 fn1 = this->fn; 973 suspend(this); // return to last resume 974 } 975 } 976 977 int next(Fibonacci& this) { 978 resume(&this); // transfer to last suspend 979 return this.fn; 980 } 981 982 void main() { 983 Fibonacci f1, f2; 984 for ( int i = 1; i <= 10; i += 1 ) { 985 sout | next(f1) | '§\verb+ +§' | next(f2) | endl; 986 } 1042 987 } 1043 988 \end{lstlisting} -
doc/proposals/concurrency/version
rd3a85240 rdd0c97b 1 0.7. 611 0.7.48 -
src/libcfa/concurrency/threads
rd3a85240 rdd0c97b 15 15 // 16 16 17 #ifdef __CFORALL__ 18 19 #ifndef THREADS_H 20 #define THREADS_H 17 #ifndef __THREADS_H__ 18 #define __THREADS_H__ 21 19 22 20 #include "assert" // … … 113 111 } 114 112 115 #endif //THREADS_H 116 117 #else 118 #include_next <thread> 119 #endif //__CFORALL__ 113 #endif //__THREADS_H__ 120 114 121 115 // Local Variables: // -
src/libcfa/containers/vector
rd3a85240 rdd0c97b 14 14 // 15 15 16 #ifdef __CFORALL__ 17 18 #ifndef VECTOR_H 19 #define VECTOR_H 16 #pragma once 20 17 21 18 extern "C" { … … 168 165 } 169 166 170 #endif // VECTOR_H171 172 #else173 #include_next <vector>174 #endif //__CFORALL__175 176 167 // Local Variables: // 177 168 // mode: c // -
src/libcfa/fstream
rd3a85240 rdd0c97b 13 13 // Update Count : 88 14 14 // 15 16 #ifdef __CFORALL__17 15 18 16 #ifndef __FSTREAM_H__ … … 64 62 #endif // __FSTREAM_H__ 65 63 66 #else67 #include_next <fstream>68 #endif //__CFORALL__69 70 64 // Local Variables: // 71 65 // mode: c // -
src/libcfa/iostream
rd3a85240 rdd0c97b 13 13 // Update Count : 93 14 14 // 15 16 #ifdef __CFORALL__17 15 18 16 #ifndef __IOSTREAM_H__ … … 126 124 forall( dtype istype | istream( istype ) ) istype * ?|?( istype *, _Istream_cstrC ); 127 125 128 #endif // __IOSTREAM_H 129 130 #else 131 #include_next <iostream> 132 #endif //__CFORALL__ 126 #endif // __IOSTREAM_H__ 133 127 134 128 // Local Variables: // -
src/libcfa/iterator
rd3a85240 rdd0c97b 13 13 // Update Count : 9 14 14 // 15 16 #ifdef __CFORALL__17 15 18 16 #ifndef ITERATOR_H … … 48 46 #endif // ITERATOR_H 49 47 50 #else51 #include_next <iterator>52 #endif //__CFORALL__53 54 48 // Local Variables: // 55 49 // mode: c // -
src/libcfa/limits
rd3a85240 rdd0c97b 13 13 // Update Count : 6 14 14 // 15 16 #ifdef __CFORALL__17 18 #ifndef LIMITS_H19 #define LIMITS_H20 15 21 16 // Integral Constants … … 112 107 extern const long _Complex _1_SQRT_2; // 1 / sqrt(2) 113 108 114 #endif // LIMITS_H115 116 #else117 #include_next <limits>118 #endif //__CFORALL__119 120 109 // Local Variables: // 121 110 // mode: c // -
src/libcfa/math
rd3a85240 rdd0c97b 14 14 // 15 15 16 #ifdef __CFORALL__17 18 #ifndef MATH_H19 #define MATH_H20 21 16 extern "C" { 22 17 #include <math.h> // fpclassify, isfinite, isnormal, isnan, isinf … … 354 349 long double scalbln( long double, long int ); 355 350 356 #endif // MATH_H357 358 #else359 #include_next <math>360 #endif //__CFORALL__361 362 351 // Local Variables: // 363 352 // mode: c // -
src/libcfa/rational
rd3a85240 rdd0c97b 15 15 // Update Count : 16 16 16 // 17 #ifdef __CFORALL__18 19 #ifndef RATIONAL_H20 #define RATIONAL_H21 17 22 18 #include "iostream" … … 65 61 forall( dtype ostype | ostream( ostype ) ) ostype * ?|?( ostype *, Rational ); 66 62 67 #endif // RATIONAL_H68 69 #else70 #include_next <rational>71 #endif //__CFORALL__72 73 63 // Local Variables: // 74 64 // mode: c // -
src/libcfa/stdlib
rd3a85240 rdd0c97b 13 13 // Update Count : 99 14 14 // 15 16 #ifdef __CFORALL__17 18 #ifndef STDLIB_H19 #define STDLIB_H20 15 21 16 //--------------------------------------- … … 136 131 void swap( T * t1, T * t2 ); 137 132 138 #endif // STDLIB_H139 140 #else141 #include_next <stdlib>142 #endif //__CFORALL__143 144 133 // Local Variables: // 145 134 // mode: c //
Note:
See TracChangeset
for help on using the changeset viewer.
