Changes in / [b1d3ee1:cedb545]
- Files:
-
- 5 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/papers/concurrency/Paper.tex
rb1d3ee1 rcedb545 241 241 \corres{*Peter A. Buhr, Cheriton School of Computer Science, University of Waterloo, 200 University Avenue West, Waterloo, ON, N2L 3G1, Canada. \email{pabuhr{\char`\@}uwaterloo.ca}} 242 242 243 %\fundingInfo{Natural Sciences and Engineering Research Council of Canada}243 \fundingInfo{Natural Sciences and Engineering Research Council of Canada} 244 244 245 245 \abstract[Summary]{ 246 \CFA is a polymorphic, non-object-oriented, concurrent, backwards-compatible extension of the C programming language. 247 This paper discusses the design philosophy and implementation of its advanced control-flow and concurrent/parallel features, along with the supporting runtime. 248 These features are created from scratch as ISO C has only low-level and/or unimplemented concurrency, so C programmers continue to rely on library features like C pthreads. 249 \CFA introduces modern language-level control-flow mechanisms, like coroutines, user-level threading, and monitors for mutual exclusion and synchronization. 250 Library extension for executors, futures, and actors are built on these basic mechanisms. 251 The runtime provides significant programmer simplification and safety by eliminating spurious wakeup and reducing monitor barging. 252 The runtime also ensures multiple monitors can be safely acquired \emph{simultaneously} (deadlock free), and this feature is fully integrated with all monitor synchronization mechanisms. 253 All language features integrate with the \CFA polymorphic type-system and exception handling, while respecting the expectations and style of C programmers. 246 \CFA is a modern, polymorphic, non-object-oriented, backwards-compatible extension of the C programming language. 247 This paper discusses some advanced control-flow and concurrency/parallelism features in \CFA, along with the supporting runtime. 248 These features are created from scratch because they do not exist in ISO C, or are low-level and/or unimplemented, so C programmers continue to rely on library features, like C pthreads. 249 \CFA introduces language-level control-flow mechanisms, like coroutines, user-level threading, and monitors for mutual exclusion and synchronization. 250 A unique contribution of this work is allowing multiple monitors to be safely acquired \emph{simultaneously} (deadlock free), while integrating this capability with monitor synchronization mechanisms. 251 These features also integrate with the \CFA polymorphic type-system and exception handling, while respecting the expectations and style of C programmers. 254 252 Experimental results show comparable performance of the new features with similar mechanisms in other concurrent programming-languages. 255 253 }% … … 266 264 \section{Introduction} 267 265 268 This paper discusses the design philosophy and implementation of advanced language-level control-flow and concurrent/parallel features in \CFA~\cite{Moss18}and its runtime.266 This paper discusses the design of language-level control-flow and concurrency/parallelism extensions in \CFA and its runtime. 269 267 \CFA is a modern, polymorphic, non-object-oriented\footnote{ 270 268 \CFA has features often associated with object-oriented programming languages, such as constructors, destructors, virtuals and simple inheritance. 271 269 However, functions \emph{cannot} be nested in structures, so there is no lexical binding between a structure and set of functions (member/method) implemented by an implicit \lstinline@this@ (receiver) parameter.}, 272 backwards-compatible extension of the C programming language .270 backwards-compatible extension of the C programming language~\cite{Moss18}. 273 271 Within the \CFA framework, new control-flow features are created from scratch. 274 272 ISO \Celeven defines only a subset of the \CFA extensions, where the overlapping features are concurrency~\cite[\S~7.26]{C11}. … … 277 275 no high-level language concurrency features are defined. 278 276 Interestingly, 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. 279 Finally, while the \Celeven standard does not state a threadingmodel, the historical association with pthreads suggests implementations would adopt kernel-level threading (1:1)~\cite{ThreadModel}.277 Finally, while the \Celeven standard does not state a concurrent threading-model, the historical association with pthreads suggests implementations would adopt kernel-level threading (1:1)~\cite{ThreadModel}. 280 278 281 279 In contrast, there has been a renewed interest during the past decade in user-level (M:N, green) threading in old and new programming languages. … … 283 281 Kernel threading was chosen, largely because of its simplicity and fit with the simpler operating systems and hardware architectures at the time, which gave it a performance advantage~\cite{Drepper03}. 284 282 Libraries like pthreads were developed for C, and the Solaris operating-system switched from user (JDK 1.1~\cite{JDK1.1}) to kernel threads. 285 As a result, languages like Java, Scala~\cite{Scala}, Objective-C~\cite{obj-c-book}, \CCeleven~\cite{C11}, and C\#~\cite{Csharp} adopt the 1:1 kernel-threading model, with a variety of presentation mechanisms.283 As a result, languages like Java, Scala~\cite{Scala}, Objective-C~\cite{obj-c-book}, \CCeleven~\cite{C11}, and C\#~\cite{Csharp} adopted the 1:1 kernel-threading model, with a variety of presentation mechanisms. 286 284 From 2000 onwards, languages like Go~\cite{Go}, Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, D~\cite{D}, and \uC~\cite{uC++,uC++book} have championed the M:N user-threading model, and many user-threading libraries have appeared~\cite{Qthreads,MPC,BoostThreads}, including putting green threads back into Java~\cite{Quasar}. 287 285 The main argument for user-level threading is that they are lighter weight than kernel threads (locking and context switching do not cross the kernel boundary), so there is less restriction on programming styles that encourage large numbers of threads performing smaller work-units to facilitate load balancing by the runtime~\cite{Verch12}. … … 289 287 Finally, performant user-threading implementations (both time and space) are largely competitive with direct kernel-threading implementations, while achieving the programming advantages of high concurrency levels and safety. 290 288 291 A further effort over the past two decades is the development of language memory-models to deal with the conflict between language features and compiler/hardware optimizations, i.e., some language features are unsafe in the presence of aggressive sequential optimizations~\cite{Buhr95a,Boehm05}. 292 The consequence is that a language must provide sufficient tools to program around safety issues, as inline and library code is all sequential to the compiler. 293 One solution is low-level qualifiers and functions (e.g., @volatile@ and atomics) allowing \emph{programmers} to explicitly write safe (race-free~\cite{Boehm12}) programs. 294 A safer solution is high-level language constructs so the \emph{compiler} knows the optimization boundaries, and hence, provides implicit safety. 295 This problem is best know with respect to concurrency, but applies to other complex control-flow, like exceptions\footnote{ 296 \CFA exception handling will be presented in a separate paper. 297 The 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++} 298 } and coroutines. 299 Finally, solutions in the language allows matching constructs with language paradigm, i.e., imperative and functional languages have different presentations of the same concept. 300 301 Finally, it is important for a language to provide safety over performance \emph{as the default}, allowing careful reduction of safety for performance when necessary. 302 Two concurrency violations of this philosophy are \emph{spurious wakeup} and \emph{barging}, i.e., random wakeup~\cite[\S~8]{Buhr05a} and signalling-as-hints~\cite[\S~8]{Buhr05a}, where one begats the other. 303 If you believe spurious wakeup is a foundational concurrency property, than unblocking (signalling) a thread is always a hint. 304 If you \emph{do not} believe spurious wakeup is foundational, than signalling-as-hints is a performance decision. 305 Most importantly, removing spurious wakeup and signals-as-hints makes concurrent programming significantly safer because it removes local non-determinism. 306 Clawing back performance where the local non-determinism is unimportant, should be an option not the default. 307 308 \begin{comment} 289 A further effort over the past decade is the development of language memory-models to deal with the conflict between certain language features and compiler/hardware optimizations. 290 This issue can be rephrased as: some language features are pervasive (language and runtime) and cannot be safely added via a library to prevent invalidation by sequential optimizations~\cite{Buhr95a,Boehm05}. 291 The consequence is that a language must be cognizant of these features and provide sufficient tools to program around any safety issues. 292 For example, C created the @volatile@ qualifier to provide correct execution for @setjmp@/@logjmp@ (concurrency came later). 293 The common solution is to provide a handful of complex qualifiers and functions (e.g., @volatile@ and atomics) allowing programmers to write consistent/race-free programs, often in the sequentially-consistent memory-model~\cite{Boehm12}. 294 295 While 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. 296 Essentially, using low-level explicit locks is the concurrent equivalent of assembler programming. 297 Just as most assembler programming is replaced with high-level programming, explicit locks can be replaced with high-level concurrency in a programming language. 298 Then the goal is for the compiler to check for correct usage and follow any complex coding conventions implicitly. 299 The drawback is that language constructs may preclude certain specialized techniques, therefore introducing inefficiency or inhibiting concurrency. 300 For most concurrent programs, these drawbacks are insignificant in comparison to the speed of composition, and subsequent reliability and maintainability of the high-level concurrent program. 301 (The same is true for high-level programming versus assembler programming.) 302 Only very rarely should it be necessary to drop down to races and/or explicit locks to apply a specialized technique to achieve maximum speed or concurrency. 303 As stated, this observation applies to non-concurrent forms of complex control-flow, like exception handling and coroutines. 304 305 Adapting the programming language to these features also allows matching the control-flow model with the programming-language style, versus adopting one general (sound) library/paradigm. 309 306 For example, it is possible to provide exceptions, coroutines, monitors, and tasks as specialized types in an object-oriented language, integrating these constructs to allow leveraging the type-system (static type-checking) and all other object-oriented capabilities~\cite{uC++}. 310 307 It is also possible to leverage call/return for blocking communication via new control structures, versus switching to alternative communication paradigms, like channels or message passing. … … 324 321 Hence, rewriting and retraining costs for these languages, even \CC, are prohibitive for companies with a large C software-base. 325 322 \CFA with its orthogonal feature-set, its high-performance runtime, and direct access to all existing C libraries circumvents these problems. 326 \end{comment} 327 328 \CFA embraces user-level threading, language extensions for advanced control-flow, and safety as the default. 329 We present comparative examples so the reader can judge if the \CFA control-flow extensions are better and safer 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. 330 The main contributions of this work are: 323 324 We 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. 325 The detailed contributions of this work are: 331 326 \begin{itemize} 332 327 \item 333 expressive language-level coroutines and user-level threading, which respect the expectations of C programmers.328 allowing multiple monitors to be safely acquired \emph{simultaneously} (deadlock free), while seamlessly integrating this capability with all monitor synchronization mechanisms. 334 329 \item 335 monitor synchronization without barging.330 all control-flow features respect the expectations of C programmers, with statically type-safe interfaces that integrate with the \CFA polymorphic type-system and other language features. 336 331 \item 337 safely acquiring multiple monitors \emph{simultaneously} (deadlock free), while seamlessly integrating this capability with all monitor synchronization mechanisms. 338 \item 339 providing statically type-safe interfaces that integrate with the \CFA polymorphic type-system and other language features. 340 \item 341 library extensions for executors, futures, and actors built on the basic mechanisms. 342 \item 343 a runtime system with no spurious wakeup. 344 \item 345 experimental results showing comparable performance of the new features with similar mechanisms in other concurrent programming-languages. 332 experimental results show comparable performance of the new features with similar mechanisms in other concurrent programming-languages. 346 333 \end{itemize} 347 334 -
doc/user/user.tex
rb1d3ee1 rcedb545 11 11 %% Created On : Wed Apr 6 14:53:29 2016 12 12 %% Last Modified By : Peter A. Buhr 13 %% Last Modified On : Sun May 5 18:24:50201914 %% Update Count : 34 8913 %% Last Modified On : Sun Apr 14 11:02:34 2019 14 %% Update Count : 3443 15 15 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 16 16 … … 193 193 \end{center} 194 194 While the \CFA I/O looks similar to the \Index*[C++]{\CC{}} output style, there are important differences, such as automatic spacing between variables as in \Index*{Python} (see~\VRef{s:IOLibrary}). 195 196 195 197 196 \subsection{Background} … … 432 431 \end{cfa} 433 432 which conditionally includes the correct header file, if the program is compiled using \Indexc{gcc} or \Indexc{cfa}. 434 435 The \CFA translator has multiple steps.436 The following flags control how the tranlator works, the stages run, and printing within a stage.437 The majority of these flags are used by \CFA developers, but some are occasionally useful to programmers.438 \begin{description}[topsep=5pt,itemsep=0pt,parsep=0pt]439 \item440 \Indexc{-h}\index{translator option!-h@{©-h©}}, \Indexc{--help}\index{translator option!--help@{©--help©}} \, print help message441 \item442 \Indexc{-l}\index{translator option!-l@{©-l©}}, \Indexc{--libcfa}\index{translator option!--libcfa@{©--libcfa©}} \, generate libcfa.c443 \item444 \Indexc{-L}\index{translator option!-L@{©-L©}}, \Indexc{--linemarks}\index{translator option!--linemarks@{©--linemarks©}} \, generate line marks445 \item446 \Indexc{-m}\index{translator option!-m@{©-m©}}, \Indexc{--no-main}\index{translator option!--no-main@{©--no-main©}} \, do not replace main447 \item448 \Indexc{-N}\index{translator option!-N@{©-N©}}, \Indexc{--no-linemarks}\index{translator option!--no-linemarks@{©--no-linemarks©}} \, do not generate line marks449 \item450 \Indexc{-n}\index{translator option!-n@{©-n©}}, \Indexc{--no-prelude}\index{translator option!--no-prelude@{©--no-prelude©}} \, do not read prelude451 \item452 \Indexc{-p}\index{translator option!-p@{©-p©}}, \Indexc{--prototypes}\index{translator option!--prototypes@{©--prototypes©}} \, generate prototypes for prelude functions453 \item454 \Indexc{-P}\index{translator option!-P@{©-P©}}, \Indexc{--print}\index{translator option!--print@{©--print©}} \, one of:455 \begin{description}[topsep=0pt,itemsep=0pt,parsep=0pt]456 \item457 \Indexc{altexpr}\index{translator option!-P@{©-P©}!©altexpr©}\index{translator option!--print@{©-print©}!©altexpr©} \, alternatives for expressions458 \item459 \Indexc{ascodegen}\index{translator option!-P@{©-P©}!©ascodegen©}\index{translator option!--print@{©-print©}!©ascodegen©} \, as codegen rather than AST460 \item461 \Indexc{ast}\index{translator option!-P@{©-P©}!©ast©}\index{translator option!--print@{©-print©}!©ast©} \, AST after parsing462 \item463 \Indexc{astdecl}\index{translator option!-P@{©-P©}!©astdecl©}\index{translator option!--print@{©-print©}!©astdecl©} \, AST after declaration validation pass464 \item465 \Indexc{asterr}\index{translator option!-P@{©-P©}!©asterr©}\index{translator option!--print@{©-print©}!©asterr©} \, AST on error466 \item467 \Indexc{astexpr}\index{translator option!-P@{©-P©}!©astexpr©}\index{translator option!--print@{©-print©}!©altexpr©} \, AST after expression analysis468 \item469 \Indexc{astgen}\index{translator option!-P@{©-P©}!©astgen©}\index{translator option!--print@{©-print©}!©astgen©} \, AST after instantiate generics470 \item471 \Indexc{box}\index{translator option!-P@{©-P©}!©box©}\index{translator option!--print@{©-print©}!©box©} \, before box step472 \item473 \Indexc{ctordtor}\index{translator option!-P@{©-P©}!©ctordtor©}\index{translator option!--print@{©-print©}!©ctordtor©} \, after ctor/dtor are replaced474 \item475 \Indexc{codegen}\index{translator option!-P@{©-P©}!©codegen©}\index{translator option!--print@{©-print©}!©codegen©} \, before code generation476 \item477 \Indexc{declstats}\index{translator option!-P@{©-P©}!©declstats©}\index{translator option!--print@{©-print©}!©declstats©} \, code property statistics478 \item479 \Indexc{parse}\index{translator option!-P@{©-P©}!©parse©}\index{translator option!--print@{©-print©}!©parse©} \, yacc (parsing) debug information480 \item481 \Indexc{pretty}\index{translator option!-P@{©-P©}!©pretty©}\index{translator option!--print@{©-print©}!©pretty©} \, prettyprint for ascodegen flag482 \item483 \Indexc{resolver}\index{translator option!-P@{©-P©}!©resolver©}\index{translator option!--print@{©-print©}!©resolver©} \, before resolver step484 \item485 \Indexc{rproto}\index{translator option!-P@{©-P©}!©rproto©}\index{translator option!--print@{©-print©}!©rproto©} \, resolver-proto instance486 \item487 \Indexc{rsteps}\index{translator option!-P@{©-P©}!©rsteps©}\index{translator option!--print@{©-print©}!©rsteps©} \, resolver steps488 \item489 \Indexc{symevt}\index{translator option!-P@{©-P©}!©symevt©}\index{translator option!--print@{©-print©}!©symevt©} \, symbol table events490 \item491 \Indexc{tree}\index{translator option!-P@{©-P©}!©tree©}\index{translator option!--print@{©-print©}!©tree©} \, parse tree492 \item493 \Indexc{tuple}\index{translator option!-P@{©-P©}!©tuple©}\index{translator option!--print@{©-print©}!©tuple©} \, after tuple expansion494 \end{description}495 \item496 \Indexc{--prelude-dir} <directory> \, prelude directory for debug/nodebug497 \item498 \Indexc{-S}\index{translator option!-S@{©-S©}!©counters,heap,time,all,none©}, \Indexc{--statistics}\index{translator option!--statistics@{©--statistics©}!©counters,heap,time,all,none©} <option-list> \, enable profiling information:499 \begin{description}[topsep=0pt,itemsep=0pt,parsep=0pt]500 \item501 \Indexc{counters,heap,time,all,none}502 \end{description}503 \item504 \Indexc{-t}\index{translator option!-t@{©-t©}}, \Indexc{--tree}\index{translator option!--tree@{©--tree©}} build in tree505 \end{description}506 433 507 434 -
libcfa/src/iostream.hfa
rb1d3ee1 rcedb545 10 10 // Created On : Wed May 27 17:56:53 2015 11 11 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Fri May 3 22:55:04201913 // Update Count : 2 3012 // Last Modified On : Sat Apr 20 12:04:07 2019 13 // Update Count : 226 14 14 // 15 15 … … 48 48 void close( ostype & os ); 49 49 ostype & write( ostype &, const char *, size_t ); 50 int fmt( ostype &, const char format[], ... ) __attribute__(( format(printf, 2, 3) ));50 int fmt( ostype &, const char format[], ... ); 51 51 }; // ostream 52 52 … … 158 158 istype & read( istype &, char *, size_t ); 159 159 istype & ungetc( istype &, char ); 160 int fmt( istype &, const char format[], ... ) __attribute__(( format(scanf, 2, 3) ));160 int fmt( istype &, const char format[], ... ); 161 161 }; // istream 162 162 -
src/BasicTypes-gen.cc
rb1d3ee1 rcedb545 1 #include <algorithm>2 1 #include <queue> 3 2 #include <iostream> … … 341 340 } // for 342 341 code << "\t}; // costMatrix" << endl; 343 344 // maximum conversion cost from int345 code << "\tstatic const int maxIntCost = " << *max_element(costMatrix[SignedInt], costMatrix[SignedInt] + NUMBER_OF_BASIC_TYPES) << ";" << endl;346 342 code << "\t"; // indentation for end marker 347 343 348 344 if ( (start = str.find( ENDMK, start + 1 )) == string::npos ) Abort( "end", ConversionCost ); 349 345 if ( (end = str.find( STARTMK, start + 1 )) == string::npos ) Abort( "start", ConversionCost ); -
src/ResolvExpr/ConversionCost.cc
rb1d3ee1 rcedb545 10 10 // Created On : Sun May 17 07:06:19 2015 11 11 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Mon May 6 14:18:22201913 // Update Count : 2 512 // Last Modified On : Fri Apr 26 16:33:04 2019 13 // Update Count : 24 14 14 // 15 15 … … 249 249 /*_FLDXC*/ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, }, 250 250 }; // costMatrix 251 static const int maxIntCost = 15;252 251 // GENERATED END 253 252 static_assert( … … 462 461 } // if 463 462 } else if ( dynamic_cast< PointerType* >( dest ) ) { 464 cost = Cost::zero; 465 cost.incSafe( maxIntCost + 2 ); // +1 for zero_t -> int, +1 for disambiguation 463 cost = Cost::safe; 466 464 } // if 467 465 }
Note: See TracChangeset
for help on using the changeset viewer.