Changeset 20ffcf3 for doc/proposals/concurrency/text/results.tex

Timestamp:

Nov 13, 2017, 10:45:32 AM (6 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:

b3ffb61

Parents:

6d2386e

Message:

Commit after new draft

File:

• doc/proposals/concurrency/text/results.tex (modified) (6 diffs)

doc/proposals/concurrency/text/results.tex

@@ -1 +1 @@
 % ======================================================================
 % ======================================================================
-\chapter{Performance results}
+\chapter{Performance results} \label{results}
 % ======================================================================
 % ======================================================================
-
 \section{Machine setup}
-
-\begin{figure}
+Table \ref{tab:machine} shows the characteristiques of the machine used to run the benchmarks. All tests where made on this machine.
+\begin{figure}[H]
 \begin{center}
 \begin{tabular}{| l | r | l | r |}
@@ -37 +36 @@
 
 \section{Micro benchmarks}
+All benchmarks are run using the same harness to produce the results, seen as the \code{BENCH()} macro in the following examples. This macro uses the following logic to benchmark the code :
+\begin{pseudo}
+#define BENCH(run, result)
+        gettime();
+        run;
+        gettime();
+        result = (after - before) / N;
+\end{pseudo}
+The method used to get time is \code{clock_gettime(CLOCK_THREAD_CPUTIME_ID);}. Each benchmark is using many interations of a simple call to measure the cost of the call. The specific number of interation dependes on the specific benchmark.
+
+\subsection{Context-switching}
+The first interesting benchmark is to measure how long context-switches take. The simplest approach to do this is to yield on a thread, which executes a 2-step context switch. In order to make the comparison fair, coroutines also execute a 2-step context-switch, which is a resume/suspend cycle instead of a yield. Listing \ref{lst:ctx-switch} shows the code for coroutines and threads. All omitted tests are functionally identical to one of these tests. The results can be shown in table \ref{tab:ctx-switch}.
+\begin{figure}
+\begin{multicols}{2}
+\CFA Coroutines
+\begin{cfacode}
+coroutine GreatSuspender {};
+void main(GreatSuspender& this) {
+        while(true) { suspend(); }
+}
+int main() {
+        GreatSuspender s;
+        resume(s);
+        BENCH(
+                for(size_t i=0; i<n; i++) {
+                        resume(s);
+                },
+                result
+        )
+        printf("%llu\n", result);
+}
+\end{cfacode}
+\columnbreak
+\CFA Threads
+\begin{cfacode}
+
+
+
+
+int main() {
+
+
+        BENCH(
+                for(size_t i=0; i<n; i++) {
+                        yield();
+                },
+                result
+        )
+        printf("%llu\n", result);
+}
+\end{cfacode}
+\end{multicols}
+\caption{\CFA benchmark code used to measure context-switches for coroutines and threads.}
+\label{lst:ctx-switch}
+\end{figure}
 
 \begin{figure}
@@ -54 +108 @@
 \caption{Context Switch comparaison. All numbers are in nanoseconds(\si{\nano\second})}
 \label{tab:ctx-switch}
+\end{figure}
+
+\subsection{Mutual-exclusion}
+The next interesting benchmark is to measure the overhead to enter/leave a critical-section. For monitors, the simplest appraoch is to measure how long it takes enter and leave a monitor routine. Listing \ref{lst:mutex} shows the code for \CFA. To put the results in context, the cost of entering a non-inline function and the cost of acquiring and releasing a pthread mutex lock are also mesured. The results can be shown in table \ref{tab:mutex}.
+
+\begin{figure}
+\begin{cfacode}
+monitor M {};
+void __attribute__((noinline)) call( M & mutex m /*, m2, m3, m4*/ ) {}
+
+int main() {
+        M m/*, m2, m3, m4*/;
+        BENCH(
+                for(size_t i=0; i<n; i++) {
+                        call(m/*, m2, m3, m4*/);
+                },
+                result
+        )
+        printf("%llu\n", result);
+}
+\end{cfacode}
+\caption{\CFA benchmark code used to measure mutex routines.}
+\label{lst:mutex}
 \end{figure}
 
@@ -75 +152 @@
 \end{figure}
 
+\subsection{Internal scheduling}
+The Internal scheduling benchmark measures the cost of waiting on and signaling a condition variable. Listing \ref{lst:int-sched} shows the code for \CFA. The results can be shown in table \ref{tab:int-sched}. As with all other benchmarks, all omitted tests are functionally identical to one of these tests.
+
+\begin{figure}
+\begin{cfacode}
+volatile int go = 0;
+condition c;
+monitor M {};
+M m1;
+
+void __attribute__((noinline)) do_call( M & mutex a1 ) { signal(c); }
+
+thread T {};
+void ^?{}( T & mutex this ) {}
+void main( T & this ) {
+        while(go == 0) { yield(); }
+        while(go == 1) { do_call(m1); }
+}
+int  __attribute__((noinline)) do_wait( M & mutex a1 ) {
+        go = 1;
+        BENCH(
+                for(size_t i=0; i<n; i++) {
+                        wait(c);
+                },
+                result
+        )
+        printf("%llu\n", result);
+        go = 0;
+        return 0;
+}
+int main() {
+        T t;
+        return do_wait(m1);
+}
+\end{cfacode}
+\caption{Benchmark code for internal scheduling}
+\label{lst:int-sched}
+\end{figure}
+
 \begin{figure}
 \begin{center}
@@ -92 +208 @@
 \end{figure}
 
+\subsection{External scheduling}
+The Internal scheduling benchmark measures the cost of the \code{waitfor} statement (\code{_Accept} in \uC). Listing \ref{lst:ext-sched} shows the code for \CFA. The results can be shown in table \ref{tab:ext-sched}. As with all other benchmarks, all omitted tests are functionally identical to one of these tests.
+
+\begin{figure}
+\begin{cfacode}
+volatile int go = 0;
+monitor M {};
+M m1;
+thread T {};
+
+void __attribute__((noinline)) do_call( M & mutex a1 ) {}
+
+void ^?{}( T & mutex this ) {}
+void main( T & this ) {
+        while(go == 0) { yield(); }
+        while(go == 1) { do_call(m1); }
+}
+int  __attribute__((noinline)) do_wait( M & mutex a1 ) {
+        go = 1;
+        BENCH(
+                for(size_t i=0; i<n; i++) {
+                        waitfor(call, a1);
+                },
+                result
+        )
+        printf("%llu\n", result);
+        go = 0;
+        return 0;
+}
+int main() {
+        T t;
+        return do_wait(m1);
+}
+\end{cfacode}
+\caption{Benchmark code for external scheduling}
+\label{lst:ext-sched}
+\end{figure}
+
 \begin{figure}
 \begin{center}
@@ -109 +263 @@
 \end{figure}
 
-\begin{figure}
-\begin{center}
-\begin{tabular}{| l | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] |}
-\cline{2-4}
-\multicolumn{1}{c |}{} & \multicolumn{1}{c |}{ Median } &\multicolumn{1}{c |}{ Average } & \multicolumn{1}{c |}{ Standard Deviation} \\
-\hline
-Pthreads                & 26974.5       & 26977 & 124.12 \\
-\CFA Coroutines & 5             & 5             & 0      \\
-\CFA Threads    & 1122.5        & 1109.86       & 36.54  \\
-\uC Coroutines  & 106           & 107.04        & 1.61   \\
-\uC Threads             & 525.5 & 533.04        & 11.14  \\
+\subsection{Object creation}
+Finaly, the last benchmark measured is the cost of creation for concurrent objects. Listing \ref{lst:creation} shows the code for pthreads and \CFA threads. The results can be shown in table \ref{tab:creation}. As with all other benchmarks, all omitted tests are functionally identical to one of these tests. The only note here is that the callstacks of \CFA coroutines are lazily created, therefore without priming the coroutine, the creation cost is very low.
+
+\begin{figure}
+\begin{multicols}{2}
+pthread
+\begin{cfacode}
+int main() {
+        BENCH(
+                for(size_t i=0; i<n; i++) {
+                        pthread_t thread;
+                        if(pthread_create(
+                                &thread,
+                                NULL,
+                                foo,
+                                NULL
+                        ) < 0) {
+                                perror( "failure" );
+                                return 1;
+                        }
+
+                        if(pthread_join(
+                                thread,
+                                NULL
+                        ) < 0) {
+                                perror( "failure" );
+                                return 1;
+                        }
+                },
+                result
+        )
+        printf("%llu\n", result);
+}
+\end{cfacode}
+\columnbreak
+\CFA Threads
+\begin{cfacode}
+int main() {
+        BENCH(
+                for(size_t i=0; i<n; i++) {
+                        MyThread m;
+                },
+                result
+        )
+
+        printf("%llu\n", result);
+}
+\end{cfacode}
+\end{multicols}
+\caption{Bechmark code for pthreads and \CFA to measure object creation}
+\label{lst:creation}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\begin{tabular}{| l | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] |}
+\cline{2-4}
+\multicolumn{1}{c |}{} & \multicolumn{1}{c |}{ Median } &\multicolumn{1}{c |}{ Average } & \multicolumn{1}{c |}{ Standard Deviation} \\
+\hline
+Pthreads                        & 26974.5       & 26977 & 124.12 \\
+\CFA Coroutines Lazy    & 5             & 5             & 0      \\
+\CFA Coroutines Eager   & 335.0 & 357.67        & 34.2   \\
+\CFA Threads            & 1122.5        & 1109.86       & 36.54  \\
+\uC Coroutines          & 106           & 107.04        & 1.61   \\
+\uC Threads                     & 525.5 & 533.04        & 11.14  \\
 \hline
 \end{tabular}