Changeset b0ab7853


Ignore:
Timestamp:
Jun 26, 2019, 1:54:22 PM (5 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
256728f, d6a8aef
Parents:
35a408b7 (diff), 08065aa4 (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.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Files:
2 deleted
4 edited

Legend:

Unmodified
Added
Removed
  • benchmark/Makefile.am

    r35a408b7 rb0ab7853  
    1111## Created On       : Sun May 31 09:08:15 2015
    1212## Last Modified By : Peter A. Buhr
    13 ## Last Modified On : Sun Jun 23 12:34:29 2019
    14 ## Update Count     : 52
     13## Last Modified On : Mon Jun 24 16:45:42 2019
     14## Update Count     : 53
    1515###############################################################################
    1616
     
    3131BENCH_V_JAVAC = $(__bench_v_JAVAC_$(__quiet))
    3232BENCH_V_UPP = $(__bench_v_UPP_$(__quiet))
    33 BENCH_V_QTHREAD = $(__bench_v_QTHREAD_$(__quiet))
    3433
    3534__quiet = verbose
     
    4645__bench_v_JAVAC_verbose = $(AM_V_JAVAC)
    4746__bench_v_UPP_verbose = $(AM_V_UPP)
    48 __bench_v_QTHREAD_verbose = $(AM_V_CC)
    4947
    5048
     
    176174        ctxswitch-upp_thread.run        \
    177175        ctxswitch-goroutine.run         \
    178         ctxswitch-java_thread.run       \
    179         ctxswitch-qthreads.run
     176        ctxswitch-java_thread.run
    180177
    181178
     
    224221        @echo "java JavaThread" >> a.out
    225222        @chmod a+x a.out
    226 
    227 ctxswitch-qthreads$(EXEEXT):
    228         $(BENCH_V_QTHREADS)$(COMPILE) -DBENCH_N=50000000 -I/u/pabuhr/software/qthreads/include -L/u/pabuhr/software/qthreads/lib -Xlinker -R/u/pabuhr/software/qthreads/lib $(srcdir)/ctxswitch/qthreads.c -lqthread
    229223
    230224## =========================================================================================================
     
    320314        creation-upp_thread.run                 \
    321315        creation-goroutine.run                  \
    322         creation-java_thread.run                \
    323         creation-qthreads.run
     316        creation-java_thread.run
    324317
    325318creation-cfa_coroutine$(EXEEXT):
     
    349342        @echo "java JavaThread" >> a.out
    350343        @chmod a+x a.out
    351 
    352 creation-qthreads$(EXEEXT):
    353         $(BENCH_V_QTHREADS)$(COMPILE) -DBENCH_N=50000000 -I/u/pabuhr/software/qthreads/include -L/u/pabuhr/software/qthreads/lib -Xlinker -R/u/pabuhr/software/qthreads/lib $(srcdir)/ctxswitch/qthreads.c -lqthread
    354344
    355345## =========================================================================================================
  • doc/bibliography/pl.bib

    r35a408b7 rb0ab7853  
    954954    key         = {Cforall Benchmarks},
    955955    author      = {{\textsf{C}{$\mathbf{\forall}$} Benchmarks}},
    956     howpublished= {\href{https://plg.uwaterloo.ca/~cforall/benchmarks}{https://\-plg.uwaterloo.ca/\-$\sim$cforall/\-benchmarks}},
     956    howpublished= {\href{https://plg.uwaterloo.ca/~cforall/benchmark.tar}{https://\-plg.uwaterloo.ca/\-$\sim$cforall/\-benchmark.tar}},
    957957}
    958958
  • doc/papers/concurrency/Paper.tex

    r35a408b7 rb0ab7853  
    316316Finally, performant user-threading implementations (both time and space) meet or exceed direct kernel-threading implementations, while achieving the programming advantages of high concurrency levels and safety.
    317317
    318 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, \ie, some language features are unsafe in the presence of aggressive sequential optimizations~\cite{Buhr95a,Boehm05}.
     318A 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, \ie some language features are unsafe in the presence of aggressive sequential optimizations~\cite{Buhr95a,Boehm05}.
    319319The 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.
    320 One solution is low-level qualifiers and functions (\eg, @volatile@ and atomics) allowing \emph{programmers} to explicitly write safe (race-free~\cite{Boehm12}) programs.
     320One solution is low-level qualifiers and functions (\eg @volatile@ and atomics) allowing \emph{programmers} to explicitly write safe (race-free~\cite{Boehm12}) programs.
    321321A safer solution is high-level language constructs so the \emph{compiler} knows the optimization boundaries, and hence, provides implicit safety.
    322322This problem is best known with respect to concurrency, but applies to other complex control-flow, like exceptions\footnote{
     
    324324The key feature that dovetails with this paper is nonlocal 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++}
    325325} and coroutines.
    326 Finally, language solutions allow matching constructs with language paradigm, \ie, imperative and functional languages often have different presentations of the same concept to fit their programming model.
     326Finally, language solutions allow matching constructs with language paradigm, \ie imperative and functional languages often have different presentations of the same concept to fit their programming model.
    327327
    328328Finally, it is important for a language to provide safety over performance \emph{as the default}, allowing careful reduction of safety for performance when necessary.
    329 Two concurrency violations of this philosophy are \emph{spurious wakeup} (random wakeup~\cite[\S~8]{Buhr05a}) and \emph{barging} (signals-as-hints~\cite[\S~8]{Buhr05a}), where one is a consequence of the other, \ie, once there is spurious wakeup, signals-as-hints follow.
     329Two concurrency violations of this philosophy are \emph{spurious wakeup} (random wakeup~\cite[\S~8]{Buhr05a}) and \emph{barging} (signals-as-hints~\cite[\S~8]{Buhr05a}), where one is a consequence of the other, \ie once there is spurious wakeup, signals-as-hints follow.
    330330However, spurious wakeup is \emph{not} a foundational concurrency property~\cite[\S~8]{Buhr05a}, it is a performance design choice.
    331331Similarly, signals-as-hints are often a performance decision.
     
    337337Most 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.
    338338As a result, there is a significant learning curve to move to these languages, and C legacy-code must be rewritten.
    339 While \CC, like \CFA, takes an evolutionary approach to extend C, \CC's constantly growing complex and interdependent features-set (\eg, objects, inheritance, templates, etc.) mean idiomatic \CC code is difficult to use from C, and C programmers must expend significant effort learning \CC.
     339While \CC, like \CFA, takes an evolutionary approach to extend C, \CC's constantly growing complex and interdependent features-set (\eg objects, inheritance, templates, etc.) mean idiomatic \CC code is difficult to use from C, and C programmers must expend significant effort learning \CC.
    340340Hence, rewriting and retraining costs for these languages, even \CC, are prohibitive for companies with a large C software-base.
    341341\CFA with its orthogonal feature-set, its high-performance runtime, and direct access to all existing C libraries circumvents these problems.
     
    367367\section{Stateful Function}
    368368
    369 The stateful function is an old idea~\cite{Conway63,Marlin80} that is new again~\cite{C++20Coroutine19}, where execution is temporarily suspended and later resumed, \eg, plugin, device driver, finite-state machine.
     369The stateful function is an old idea~\cite{Conway63,Marlin80} that is new again~\cite{C++20Coroutine19}, where execution is temporarily suspended and later resumed, \eg plugin, device driver, finite-state machine.
    370370Hence, a stateful function may not end when it returns to its caller, allowing it to be restarted with the data and execution location present at the point of suspension.
    371371This capability is accomplished by retaining a data/execution \emph{closure} between invocations.
    372 If the closure is fixed size, we call it a \emph{generator} (or \emph{stackless}), and its control flow is restricted, \eg, suspending outside the generator is prohibited.
    373 If the closure is variably sized, we call it a \emph{coroutine} (or \emph{stackful}), and as the names implies, often implemented with a separate stack with no programming restrictions.
     372If the closure is fixed size, we call it a \emph{generator} (or \emph{stackless}), and its control flow is restricted, \eg suspending outside the generator is prohibited.
     373If the closure is variable size, we call it a \emph{coroutine} (or \emph{stackful}), and as the names implies, often implemented with a separate stack with no programming restrictions.
    374374Hence, refactoring a stackless coroutine may require changing it to stackful.
    375 A foundational property of all \emph{stateful functions} is that resume/suspend \emph{do not} cause incremental stack growth, \ie, resume/suspend operations are remembered through the closure not the stack.
     375A foundational property of all \emph{stateful functions} is that resume/suspend \emph{do not} cause incremental stack growth, \ie resume/suspend operations are remembered through the closure not the stack.
    376376As well, activating a stateful function is \emph{asymmetric} or \emph{symmetric}, identified by resume/suspend (no cycles) and resume/resume (cycles).
    377377A fixed closure activated by modified call/return is faster than a variable closure activated by context switching.
    378 Additionally, any storage management for the closure (especially in unmanaged languages, \ie, no garbage collection) must also be factored into design and performance.
     378Additionally, any storage management for the closure (especially in unmanaged languages, \ie no garbage collection) must also be factored into design and performance.
    379379Therefore, selecting between stackless and stackful semantics is a tradeoff between programming requirements and performance, where stackless is faster and stackful is more general.
    380380Note, creation cost is amortized across usage, so activation cost is usually the dominant factor.
     
    648648\end{center}
    649649The example takes advantage of resuming a generator in the constructor to prime the loops so the first character sent for formatting appears inside the nested loops.
    650 The destructor provides a newline if formatted text ends with a full line.
     650The destructor provides a newline, if formatted text ends with a full line.
    651651Figure~\ref{f:CFormatSim} shows the C implementation of the \CFA input generator with one additional field and the computed @goto@.
    652652For contrast, Figure~\ref{f:PythonFormatter} shows the equivalent Python format generator with the same properties as the Fibonacci generator.
     
    27192719Each benchmark experiment is run 31 times.
    27202720All omitted tests for other languages are functionally identical to the \CFA tests and available online~\cite{CforallBenchMarks}.
    2721 
     2721% tar --exclude=.deps --exclude=Makefile --exclude=Makefile.in --exclude=c.c --exclude=cxx.cpp --exclude=fetch_add.c -cvhf benchmark.tar benchmark
    27222722
    27232723\paragraph{Object Creation}
     
    27492749\multicolumn{1}{@{}c}{} & \multicolumn{1}{c}{Median} & \multicolumn{1}{c}{Average} & \multicolumn{1}{c@{}}{Std Dev} \\
    27502750\CFA Coroutine Lazy             & 14.3          & 14.3          & 0.32          \\
    2751 \CFA Coroutine Eager    & 2203.7        & 2205.6        & 26.03         \\
     2751\CFA Coroutine Eager    & 522.8         & 525.3         & 5.81          \\
    27522752\CFA Thread                             & 1257.8        & 1291.2        & 86.19         \\
    27532753\uC Coroutine                   & 92.2          & 91.4          & 1.58          \\
  • doc/user/user.tex

    r35a408b7 rb0ab7853  
    1111%% Created On       : Wed Apr  6 14:53:29 2016
    1212%% Last Modified By : Peter A. Buhr
    13 %% Last Modified On : Sat Jun 15 16:29:45 2019
    14 %% Update Count     : 3847
     13%% Last Modified On : Tue Jun 25 08:51:33 2019
     14%% Update Count     : 3871
    1515%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1616
     
    33463346
    33473347
    3348 \section{I/O Stream Library}
    3349 \label{s:IOStreamLibrary}
     3348\section{Stream I/O Library}
     3349\label{s:StreamIOLibrary}
    33503350\index{input/output stream library}
    33513351\index{stream library}
    33523352
    3353 The goal of \CFA input/output (I/O) is to simplify the common cases\index{I/O!common case}, while fully supporting polymorphism and user defined types in a consistent way.
    3354 \CFA I/O combines ideas from C ©printf©, \CC, and Python.
    3355 I/O can be unformatted or formatted.
    3356 Unformatted means \CFA selects the output or input format for values that match with the type of a variable.
    3357 Formatted means additional information is specified to augment how an output or input of value is interpreted.
    3358 \CFA formatting is a cross between C ©printf© and \CC ©cout© manipulators.
     3353The goal of \CFA stream input/output (I/O) is to simplify the common cases\index{I/O!common case}, while fully supporting polymorphism and user defined types in a consistent way.
     3354Stream I/O can be implicitly or explicitly formatted.
     3355Implicit formatting means \CFA selects the output or input format for values that match with the type of a variable.
     3356Explicit formatting means additional information is specified to augment how an output or input of value is interpreted.
     3357\CFA formatting is a cross between C ©printf© and \CC ©cout© manipulators, and Python implicit spacing and newline.
     3358Specifically:
    33593359\begin{itemize}
    33603360\item
    3361 ©printf© format codes are dense, making them difficult to read and remember.
     3361©printf©/Python format codes are dense, making them difficult to read and remember.
    33623362\CFA/\CC format manipulators are named, making them easier to read and remember.
    33633363\item
    3364 ©printf© separates format codes from associated variables, making it difficult to match codes with variables.
     3364©printf©/Python separates format codes from associated variables, making it difficult to match codes with variables.
    33653365\CFA/\CC co-locate codes with associated variables, where \CFA has the tighter binding.
    33663366\item
    3367 Format manipulators in \CC have global rather than local effect, except ©setw©.
     3367Format manipulators in \CFA have local effect, whereas \CC have global effect, except ©setw©.
    33683368Hence, it is common programming practice to toggle manipulators on and then back to the default to prevent downstream side-effects.
    33693369Without this programming style, errors occur when moving prints, as manipulator effects incorrectly flow into the new location.
    33703370(To guarantee no side-effects, manipulator values must be saved and restored across function calls.)
     3371\item
     3372\CFA has more sophisticated implicit spacing between values than Python, plus implicit newline at the end of a print.
    33713373\end{itemize}
    33723374The \CFA header file for the I/O library is \Indexc{fstream.hfa}.
    33733375
    3374 For unformatted output, the common case is printing a sequence of variables separated by whitespace.
     3376For implicit formatted output, the common case is printing a series of variables separated by whitespace.
    33753377\begin{cquote}
    3376 \begin{tabular}{@{}l@{\hspace{3em}}l@{}}
    3377 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{\CC}}      \\
     3378\begin{tabular}{@{}l@{\hspace{2em}}l@{\hspace{2em}}l@{}}
     3379\multicolumn{1}{c@{\hspace{2em}}}{\textbf{\CFA}}        & \multicolumn{1}{c@{\hspace{2em}}}{\textbf{\CC}}       & \multicolumn{1}{c}{\textbf{Python}}   \\
    33783380\begin{cfa}
    33793381int x = 1, y = 2, z = 3;
     
    33853387cout << x ®<< " "® << y ®<< " "® << z << endl;
    33863388\end{cfa}
     3389&
     3390\begin{cfa}
     3391x = 1;  y = 2;  z = 3
     3392print( x, y, z )
     3393\end{cfa}
    33873394\\
     3395\begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt]
     33961® ®2® ®3
     3397\end{cfa}
     3398&
    33883399\begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt]
    338934001® ®2® ®3
     
    34293440There is a weak similarity between the \CFA logical-or operator and the \Index{Shell pipe-operator} for moving data, where data flows in the correct direction for input but the opposite direction for output.
    34303441
    3431 For unformatter input, the common case is reading a sequence of values separated by whitespace, where the type of an input constant must match with the type of the input variable.
     3442For implicit formatted input, the common case is reading a sequence of values separated by whitespace, where the type of an input constant must match with the type of the input variable.
    34323443\begin{cquote}
    34333444\begin{lrbox}{\LstBox}
     
    34363447\end{cfa}
    34373448\end{lrbox}
    3438 \begin{tabular}{@{}l@{\hspace{3em}}l@{}}
     3449\begin{tabular}{@{}l@{\hspace{3em}}l@{\hspace{3em}}l@{}}
    34393450\multicolumn{1}{@{}l@{}}{\usebox\LstBox} \\
    3440 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{\CC}}      \\
     3451\multicolumn{1}{c@{\hspace{2em}}}{\textbf{\CFA}}        & \multicolumn{1}{c@{\hspace{2em}}}{\textbf{\CC}}       & \multicolumn{1}{c}{\textbf{Python}}   \\
    34413452\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    34423453sin | x | y | z;
     
    34463457cin >> x >> y >> z;
    34473458\end{cfa}
     3459&
     3460\begin{cfa}[aboveskip=0pt,belowskip=0pt]
     3461x = int(input());  y = float(input());  z = input();
     3462\end{cfa}
    34483463\\
    34493464\begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt]
    34503465®1® ®2.5® ®A®
     3466
     3467
    34513468\end{cfa}
    34523469&
    34533470\begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt]
    34543471®1® ®2.5® ®A®
     3472
     3473
     3474\end{cfa}
     3475&
     3476\begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt]
     3477®1®
     3478®2.5®
     3479®A®
    34553480\end{cfa}
    34563481\end{tabular}
     
    370537300b0 0b11011 0b11011 0b11011 0b11011
    37063731sout | bin( -27HH ) | bin( -27H ) | bin( -27 ) | bin( -27L );
    3707 0b11100101 0b1111111111100101 0b11111111111111111111111111100101 0b(58 1s)100101
     37320b11100101 0b1111111111100101 0b11111111111111111111111111100101 0b®(58 1s)®100101
    37083733\end{cfa}
    37093734
     
    37823807®  ®4.000000 ® ®4.000000 4.000000
    37833808®  ®ab ® ®ab ab
    3784     ab    ab ab
    37853809\end{cfa}
    37863810If the value is larger, it is printed without truncation, ignoring the ©minimum©.
Note: See TracChangeset for help on using the changeset viewer.