\chapter{Micro-Benchmarks}\label{microbench}

The first step in evaluating this work is to test small controlled cases to ensure the basics work properly.
This chapter presents five different experimental setups for evaluating the basic features of the \CFA, libfibre~\cite{libfibre}, Go, and Tokio~\cite{Tokio} schedulers.
All of these systems have a \gls{uthrding} model.
The goal in this chapter is show the \CFA scheduler obtains equivalent performance to other less fair schedulers through the different experiments.
Note, only the code of the \CFA tests is shown;
all tests in the other systems are functionally identical and available online~\cite{SchedulingBenchmarks}.

\section{Benchmark Environment}\label{microenv}

All benchmarks are run on two distinct hardware platforms.
\begin{description}
\item[AMD] is a server with two AMD EPYC 7662 CPUs and 256GB of DDR4 RAM.
The EPYC CPU has 64 cores with 2 \glspl{hthrd} per core, for 128 \glspl{hthrd} per socket with 2 sockets for a total of 256 \glspl{hthrd}.
Each CPU has 4 MB, 64 MB and 512 MB of L1, L2 and L3 caches, respectively.
Each L1 and L2 instance are only shared by \glspl{hthrd} on a given core, but each L3 instance is shared by 4 cores, therefore 8 \glspl{hthrd}.
The server runs Ubuntu 20.04.2 LTS on top of Linux Kernel 5.8.0-55.

\item[Intel] is a server with four Intel Xeon Platinum 8160 CPUs and 384GB of DDR4 RAM.
The Xeon CPU has 24 cores with 2 \glspl{hthrd} per core, for 48 \glspl{hthrd} per socket with 4 sockets for a total of 196 \glspl{hthrd}.
Each CPU has 3 MB, 96 MB and 132 MB of L1, L2 and L3 caches respectively.
Each L1 and L2 instance are only shared by \glspl{hthrd} on a given core, but each L3 instance is shared across the entire CPU, therefore 48 \glspl{hthrd}.
The server runs Ubuntu 20.04.2 LTS on top of Linux Kernel 5.8.0-55.
\end{description}

For all benchmarks, @taskset@ is used to limit the experiment to 1 NUMA node with no hyper threading.
If more \glspl{hthrd} are needed, then 1 NUMA node with hyperthreading is used.
If still more \glspl{hthrd} are needed, then the experiment is limited to as few NUMA nodes as needed.
For the Intel machine, this means that from 1 to 24 \procs one socket and \emph{no} hyperthreading is used, and from 25 to 48 \procs still only one socket is used but \emph{with} hyperthreading.
This pattern is repeated between 49 and 96, between 97 and 144, and between 145 and 192.
On AMD, the same algorithm is used, but the machine only has 2 sockets.
So hyperthreading\footnote{
Hyperthreading normally refers specifically to the technique used by Intel, however it is often used generically to refer to any equivalent feature.}
is used when the \proc count reach 65 and 193.

The limited sharing of the last-level cache on the AMD machine is markedly different than the Intel machine.
Indeed, while on both architectures L2 cache misses that are served by L3 caches on a different CPU incur a significant latency, on the AMD it is also the case that cache misses served by a different L3 instance on the same CPU also incur high latency.

\section{Experimental setup}

Each experiment is run 15 times varying the number of processors depending on the two different computers.
All experiments gather throughput data and secondary data for scalability or latency.
The data is graphed using a solid, a dashed and a dotted line, representing the median, maximum and minimum result respectively, where the minimum/maximum lines are referred to as the \emph{extremes}.\footnote{
An alternative display is to use error bars with min/max as the bottom/top for the bar.
However, this approach is not truly an error bar around a mean value and I felt the connected lines are easier to read.}
This graph presentation offers an overview of the distribution of the results for each experiment.

For each experiment, four graphs are generated showing traditional throughput on the top row and \newterm{scalability} or \newterm{latency} on the bottom row (peek ahead to Figure~\ref{fig:cycle:jax}).
Scalability uses the same data as throughput but the Y axis is calculated as the number of \procs over the throughput.
In this representation, perfect scalability should appear as a horizontal line, \eg, if doubling the number of \procs doubles the throughput, then the relation stays the same.

The left column shows results for hundreds of \ats per \proc, enough to always keep every \proc busy.
The right column shows results for very few \ats per \proc, where the ready queues are expected to be near empty most of the time.
The distinction between many and few \ats is meaningful because the idle sleep subsystem is expected to matter only in the right column, where spurious effects can cause a \proc to run out of work temporarily.

\section{Cycle}

The most basic evaluation of any ready queue is the latency needed to push and pop one element from the ready queue.
Since these two operations also describe a @yield@ operation, many systems use this operation as the fundamental benchmark.
However, yielding can be treated as a special case by optimizing it away since the number of ready \ats does not change.
Hence, systems that perform this optimization have an artificial performance benefit because the yield becomes a \emph{nop}.
For this reason, I designed a different push/pop benchmark, called \newterm{Cycle Benchmark}.
This benchmark arranges a number of \ats into a ring, as seen in Figure~\ref{fig:cycle}, where the ring is a circular singly-linked list.
At runtime, each \at unparks the next \at before parking itself.
Unparking the next \at pushes that \at onto the ready queue while the ensuing park leads to a \at being popped from the ready queue.

\begin{figure}
	\centering
	\input{cycle.pstex_t}
	\caption[Cycle benchmark]{Cycle benchmark\smallskip\newline Each \at unparks the next \at in the cycle before parking itself.}
	\label{fig:cycle}
\end{figure}

Therefore, the underlying runtime cannot rely on the number of ready \ats staying constant over the duration of the experiment.
In fact, the total number of \ats waiting on the ready queue is expected to vary because of the race between the next \at unparking and the current \at parking.
That is, the runtime cannot anticipate that the current task immediately parks.
As well, the size of the cycle is also decided based on this race, \eg a small cycle may see the chain of unparks go full circle before the first \at parks because of time-slicing or multiple \procs.
If this happens, the scheduler push and pop are avoided and the results of the experiment are skewed.
(Note, an unpark is like a V on a semaphore, so the subsequent park (P) may not block.)
Every runtime system must handle this race and cannot optimized away the ready-queue pushes and pops.
To prevent any attempt of silently omitting ready-queue operations, the ring of \ats is made big enough so the \ats have time to fully park before being unparked again.
Finally, to further mitigate any underlying push/pop optimizations, especially on SMP machines, multiple rings are created in the experiment.

Figure~\ref{fig:cycle:code} shows the pseudo code for this benchmark, where each cycle has 5 \ats.
There is additional complexity to handle termination (not shown), which requires a binary semaphore or a channel instead of raw @park@/@unpark@ and carefully picking the order of the @P@ and @V@ with respect to the loop condition.

\begin{figure}
\begin{cfa}
Thread.main() {
	count := 0
	for {
		@this.next.wake()@
		@wait()@
		count ++
		if must_stop() { break }
	}
	global.count += count
}
\end{cfa}
\caption[Cycle Benchmark : Pseudo Code]{Cycle Benchmark : Pseudo Code}
\label{fig:cycle:code}
%\end{figure}ll have a physical key so it's not urgent.


%\begin{figure}
	\subfloat[][Throughput, 100 cycles per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.cycle.jax.ops.pstex_t}
		}
		\label{fig:cycle:jax:ops}
	}
	\subfloat[][Throughput, 1 cycle per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.cycle.low.jax.ops.pstex_t}
		}
		\label{fig:cycle:jax:low:ops}
	}

	\subfloat[][Scalability, 100 cycles per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.cycle.jax.ns.pstex_t}
		}
		\label{fig:cycle:jax:ns}
	}
	\subfloat[][Scalability, 1 cycle per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.cycle.low.jax.ns.pstex_t}
		}
		\label{fig:cycle:jax:low:ns}
	}
	\caption[Cycle Benchmark on Intel]{Cycle Benchmark on Intel\smallskip\newline Throughput and scalability as a function of \proc count, 5 \ats per cycle, and different cycle count.
	For throughput, higher is better, for scalability, lower is better.
	Each series represent 15 independent runs, the dashed lines are maximums of each series while the solid lines are the median and the dotted lines are the minimums.}
	\label{fig:cycle:jax}
\end{figure}

\begin{figure}
	\subfloat[][Throughput, 100 cycles per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.cycle.nasus.ops.pstex_t}
		}
		\label{fig:cycle:nasus:ops}
	}
	\subfloat[][Throughput, 1 cycle per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.cycle.low.nasus.ops.pstex_t}
		}
		\label{fig:cycle:nasus:low:ops}
	}

	\subfloat[][Scalability, 100 cycles per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.cycle.nasus.ns.pstex_t}
		}
		\label{fig:cycle:nasus:ns}
	}
	\subfloat[][Scalability, 1 cycle per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.cycle.low.nasus.ns.pstex_t}
		}
		\label{fig:cycle:nasus:low:ns}
	}
	\caption[Cycle Benchmark on AMD]{Cycle Benchmark on AMD\smallskip\newline Throughput and scalability as a function of \proc count, 5 \ats per cycle, and different cycle counts.
	For throughput, higher is better, for scalability, lower is better.
	Each series represent 15 independent runs, the dashed lines are maximums of each series while the solid lines are the median and the dotted lines are the minimums.}
	\label{fig:cycle:nasus}
\end{figure}

\subsection{Results}

Figures~\ref{fig:cycle:jax} and \ref{fig:cycle:nasus} show the results for the cycle experiment.
Looking at the left column on Intel first, Figures~\ref{fig:cycle:jax:ops} and \ref{fig:cycle:jax:ns}, which shows the results for many \ats, in this case 100 cycles of 5 \ats for each \proc.
\CFA, Go and Tokio all obtain effectively the same throughput performance.
Libfibre is slightly behind in this case but still scales decently.
As a result of the \gls{kthrd} placement, additional \procs from 25 to 48 offer less performance improvement for all runtimes, which can be seen as a flatting of the line.
This effect even causes a decrease in throughput in libfibre's case.
As expected, this pattern repeats again between \proc count 72 and 96.

Looking next at the right column on Intel, Figures~\ref{fig:cycle:jax:low:ops} and \ref{fig:cycle:jax:low:ns}, which shows the results for few threads, in this case 1 cycle of 5 \ats for each \proc.
\CFA and Tokio obtain very similar results overall, but Tokio shows more variations in the results.
Go achieves slightly better performance than \CFA and Tokio, but all three display significantly workst performance compared to the left column.
This decrease in performance is likely due to the additional overhead of the idle-sleep mechanism.
This can either be the result of \procs actually running out of work, or simply additional overhead from tracking whether or not there is work available.
Indeed, unlike the left column, it is likely that the ready-queue will be transiently empty, which likely triggers additional synchronization steps.
Interestingly, libfibre achieves better performance with 1 cycle.

Looking now at the results for the AMD architecture, Figure~\ref{fig:cycle:nasus}, the results show a story that is overall similar to the results on the Intel, with close to double the performance overall but with slightly increased variation and some differences in the details.
Note that the maximum of the Y-axis on Intel and AMD differ significantly.
Looking at the left column first, Figures~\ref{fig:cycle:nasus:ops} and \ref{fig:cycle:nasus:ns}, unlike Intel, on AMD all 4 runtimes achieve very similar throughput and scalability.
However, as the number of \procs grows higher, the results on AMD show notably more variability than on Intel.
The different performance improvements and plateaus are due to cache topology and appear at the expected \proc counts of 64, 128 and 192, for the same reasons as on Intel.
Looking next at the right column, Figures~\ref{fig:cycle:nasus:low:ops} and \ref{fig:cycle:nasus:low:ns}, Tokio and Go have the same throughput performance, while \CFA is slightly slower.
This is different than on Intel, where Tokio behaved like \CFA rather than behaving like Go.
Again, the same performance increase for libfibre is visible when running fewer \ats.
Note, I did not investigate the libfibre performance boost for 1 cycle in this experiment.

The conclusion from both architectures is that all of the compared runtime have fairly equivalent performance for this micro-benchmark.
Clearly, the pathological case with 1 cycle per \proc can affect fairness algorithms managing mostly idle processors, \eg \CFA, but only at high core counts.
For this case, \emph{any} helping is likely to cause a cascade of \procs running out of work and attempting to steal.
For this experiment, the \CFA scheduler has achieved the goal of obtaining equivalent performance to other less fair schedulers.

\section{Yield}

For completion, the classic yield benchmark is included.
Here, the throughput is dominated by the mechanism used to handle the @yield@ function.
Figure~\ref{fig:yield:code} shows pseudo code for this benchmark, where the cycle @wait/next.wake@ is replaced by @yield@.
As mentioned, this benchmark may not be representative because of optimization shortcuts in @yield@.
The only interesting variable in this benchmark is the number of \ats per \procs, where ratios close to 1 means the ready queue(s) can be empty, which again puts a strain on the idle-sleep handling.

\begin{figure}
\begin{cfa}
Thread.main() {
	count := 0
	for {
		@yield()@
		count ++
		if must_stop() { break }
	}
	global.count += count
}
\end{cfa}
\caption[Yield Benchmark : Pseudo Code]{Yield Benchmark : Pseudo Code}
\label{fig:yield:code}
%\end{figure}
\bigskip
%\begin{figure}
	\subfloat[][Throughput, 100 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.yield.jax.ops.pstex_t}
		}
		\label{fig:yield:jax:ops}
	}
	\subfloat[][Throughput, 1 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
		\input{result.yield.low.jax.ops.pstex_t}
		}
		\label{fig:yield:jax:low:ops}
	}

	\subfloat[][Scalability, 100 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
		\input{result.yield.jax.ns.pstex_t}
		}
		\label{fig:yield:jax:ns}
	}
	\subfloat[][Scalability, 1 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
		\input{result.yield.low.jax.ns.pstex_t}
		}
		\label{fig:yield:jax:low:ns}
	}
	\caption[Yield Benchmark on Intel]{Yield Benchmark on Intel\smallskip\newline Throughput and scalability as a function of \proc count.
	For throughput, higher is better, for scalability, lower is better.
	Each series represent 15 independent runs, the dashed lines are maximums of each series while the solid lines are the median and the dotted lines are the minimums.}
	\label{fig:yield:jax}
\end{figure}

\subsection{Results}

Figures~\ref{fig:yield:jax} and \ref{fig:yield:nasus} show the results for the yield experiment.
Looking at the left column on Intel first, Figures~\ref{fig:yield:jax:ops} and \ref{fig:yield:jax:ns}, which shows the results for many \ats, in this case 100 \ats for each \proc.
Note, the Y-axis on the graph is twice as large as the Intel cycle-graph.
A visual glance between the left columns of the cycle and yield graphs confirms my claim that the yield benchmark is unreliable.
\CFA has no special handling for @yield@, but this experiment requires less synchronization than the @cycle@ experiment.
Hence, the @yield@ throughput and scalability graphs have similar shapes to the corresponding @cycle@ graphs.
The only difference is sightly better performance for @yield@ because of less synchronization.
Libfibre has special handling for @yield@ using the fact that the number of ready fibres does not change, and therefore, by-passing the idle-sleep mechanism entirely.
Hence, libfibre behaves very differently in the cycle and yield benchmarks, with a 4 times increase in performance on the left column.
Go has special handling for @yield@ by putting a yielding goroutine on a secondary global ready-queue, giving it lower priority.
The result is that multiple \glspl{hthrd} contend for the global queue and performance suffers drastically.
Hence, Go behaves very differently in the cycle and yield benchmarks, with a complete performance collapse in @yield@.
Tokio has a similar performance collapse after 16 processors, and therefore, its special @yield@ handling is probably related to a Go-like scheduler problem and/or a \CFA idle-sleep problem.
(I did not dig through the Rust code to ascertain the exact reason for the collapse.)
Note that since there is no communication among \ats, locality problems are much less likely than for the cycle benchmark.
This lack of communication is probably why the plateaus due to topology are not present.

Lookking next at the right column on Intel, Figures~\ref{fig:yield:jax:low:ops} and \ref{fig:yield:jax:low:ns}, which shows the results for few threads, in this case 1 \at for each \proc.
As for @cycle@, \CFA's cost of idle sleep comes into play in a very significant way in Figure~\ref{fig:yield:jax:low:ns}, where the scaling is not flat.
This is to be expected since fewet \ats means \procs are more likely to run out of work.
On the other hand, when only running 1 \at per \proc, libfibre optimizes further, and forgoes the context-switch entirely.
This results in libfibre outperforming other runtimes even more, achieving 8 times more throughput than for @cycle@.
Finally, Go and Tokio performance collapse is still the same with fewer \ats.
The only exception is Tokio running on 24 \proc, deepening the mystery of its yielding mechanism further.

\begin{figure}
	\subfloat[][Throughput, 100 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.yield.nasus.ops.pstex_t}
		}
		\label{fig:yield:nasus:ops}
	}
	\subfloat[][Throughput, 1 \at per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.yield.low.nasus.ops.pstex_t}
		}
		\label{fig:yield:nasus:low:ops}
	}

	\subfloat[][Scalability, 100 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.yield.nasus.ns.pstex_t}
		}
		\label{fig:yield:nasus:ns}
	}
	\subfloat[][Scalability, 1 \at per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.yield.low.nasus.ns.pstex_t}
		}
		\label{fig:yield:nasus:low:ns}
	}
	\caption[Yield Benchmark on AMD]{Yield Benchmark on AMD\smallskip\newline Throughput and scalability as a function of \proc count.
	For throughput, higher is better, for scalability, lower is better.
	Each series represent 15 independent runs, the dashed lines are maximums of each series while the solid lines are the median and the dotted lines are the minimums.}
	\label{fig:yield:nasus}
\end{figure}

Looking now at the results for the AMD architecture, Figure~\ref{fig:yield:nasus}, the results again show a story that is overall similar to the results on the Intel, with increased variation and some differences in the details.
Note that the maximum of the Y-axis on Intel and AMD differ less in @yield@ than @cycle@.
Looking at the left column first, Figures~\ref{fig:yield:nasus:ops} and \ref{fig:yield:nasus:ns}, \CFA achieves very similar throughput and scaling.
Libfibre still outpaces all other runtimes, but it encounter a performance hit at 64 \procs.
This suggest some amount of communication between the \procs that the Intel machine was able to mask where the AMD is not once hyperthreading is needed.
Go and Tokio still display the same performance collapse than on Intel.
Looking next at the right column, Figures~\ref{fig:yield:nasus:low:ops} and \ref{fig:yield:nasus:low:ns}, all runtime effectively behave the same as they did on the Intel machine.
At high \ats count the only difference was Libfibre's scaling and this difference disappears on the right column.
This suggest that whatever communication benchmark it encountered on the left is completely circumvented on the right.

It is difficult to draw conclusions for this benchmark when runtime system treat @yield@ so differently.
The win for \CFA is its consistency between the cycle and yield benchmarks making it simpler for programmers to use and understand, \ie the \CFA semantics match with programmer intuition.


\section{Churn}

The Cycle and Yield benchmark represent an \emph{easy} scenario for a scheduler, \eg an embarrassingly parallel application.
In these benchmarks, \ats can be easily partitioned over the different \procs upfront and none of the \ats communicate with each other.

The Churn benchmark represents more chaotic executions, where there is more communication among \ats but no relationship between the last \proc on which a \at ran and blocked and the \proc that subsequently unblocks it.
With processor-specific ready-queues, when a \at is unblocked by a different \proc that means the unblocking \proc must either ``steal'' the \at from another processor or find it on a remote queue.
This dequeuing results in either contention on the remote queue and/or \glspl{rmr} on the \at data structure.
Hence, this benchmark has performance dominated by the cache traffic as \procs are constantly accessing each other's data.
In either case, this benchmark aims to measure how well a scheduler handles these cases, since both cases can lead to performance degradation if not handled correctly.

This benchmark uses a fixed-size array of counting semaphores.
Each \at picks a random semaphore, @V@s it to unblock any waiting \at, and then @P@s (maybe blocks) the \ats on the semaphore.
This creates a flow where \ats push each other out of the semaphores before being pushed out themselves.
For this benchmark to work, the number of \ats must be equal or greater than the number of semaphores plus the number of \procs;
\eg if there are 10 semaphores and 5 \procs, but only 3 \ats, all 3 \ats can block (P) on a random semaphore and now there is no \ats to unblock (V) them.
Note, the nature of these semaphores mean the counter can go beyond 1, which can lead to nonblocking calls to @P@.
Figure~\ref{fig:churn:code} shows pseudo code for this benchmark, where the @yield@ is replaced by @V@ and @P@.

\begin{figure}
\begin{cfa}
Thread.main() {
	count := 0
	for {
		r := random() % len(spots)
		@spots[r].V()@
		@spots[r].P()@
		count ++
		if must_stop() { break }
	}
	global.count += count
}
\end{cfa}
\caption[Churn Benchmark : Pseudo Code]{Churn Benchmark : Pseudo Code}
\label{fig:churn:code}
%\end{figure}
\bigskip
%\begin{figure}
	\subfloat[][Throughput, 100 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.churn.jax.ops.pstex_t}
		}
		\label{fig:churn:jax:ops}
	}
	\subfloat[][Throughput, 2 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.churn.low.jax.ops.pstex_t}
		}
		\label{fig:churn:jax:low:ops}
	}

	\subfloat[][Scalability, 100 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.churn.jax.ns.pstex_t}
		}
		\label{fig:churn:jax:ns}
	}
	\subfloat[][Scalability, 2 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.churn.low.jax.ns.pstex_t}
		}
		\label{fig:churn:jax:low:ns}
	}
	\caption[Churn Benchmark on Intel]{\centering Churn Benchmark on Intel\smallskip\newline Throughput and scalability of the Churn on the benchmark on the Intel machine.
	For throughput, higher is better, for scalability, lower is better.
	Each series represent 15 independent runs, the dashed lines are maximums of each series while the solid lines are the median and the dotted lines are the minimums.}
	\label{fig:churn:jax}
\end{figure}

\subsection{Results}

Figures~\ref{fig:churn:jax} and Figure~\ref{fig:churn:nasus} show the results for the churn experiment.
Looking at the left column on Intel first, Figures~\ref{fig:churn:jax:ops} and \ref{fig:churn:jax:ns}, which shows the results for many \ats, in this case 100 \ats for each \proc, all runtime obtain fairly similar throughput for most \proc counts.
\CFA does very well on a single \proc but quickly loses its advantage over the other runtimes.
As expected it scales decently up to 48 \procs and then basically plateaus.
Tokio achieves very similar performance to \CFA until 48 \procs, after which it takes a significant hit but does keep scaling somewhat.
Libfibre obtains effectively the same results as Tokio with slightly less scaling, \ie the scaling curve is the same but with slightly higher values.
Finally Go gets the most peculiar results, scaling worst than other runtimes until 48 \procs.
At 72 \procs, the results of the Go runtime vary significantly, sometimes scaling sometimes plateauing.
However, beyond this point Go keeps this level of variation but does not scale in any of the runs.

Throughput and scalability is notably worst for all runtimes than the previous benchmarks since there is inherently more communication between processors.
Indeed, none of the runtime reach 40 million operations per second while in the cycle benchmark all but libfibre reached 400 million operations per second.
Figures~\ref{fig:churn:jax:ns} and \ref{fig:churn:jax:low:ns} show that for all \proc count, all runtime produce poor scaling.
However, once the number of \glspl{hthrd} goes beyond a single socket, at 48 \procs, scaling goes from bad to worst and performance completely ceases to improve.
At this point, the benchmark is dominated by inter-socket communication costs for all runtimes.

An interesting aspect to note here is that the runtimes differ in how they handle this situation.
Indeed, when a \proc unparks a \at that was last run on a different \proc, the \at could be appended to the ready-queue local \proc or to the ready-queue of the remote \proc, which previously ran the \at.
\CFA, Tokio and Go all use the approach of unparking to the local \proc while Libfibre unparks to the remote \proc.
In this particular benchmark, the inherent chaos of the benchmark in addition to small memory footprint means neither approach wins over the other.

Looking next at the right column on Intel, Figures~\ref{fig:churn:jax:low:ops} and \ref{fig:churn:jax:low:ns}, which shows the results for few threads, in this case 1 \at for each \proc, many of the differences between the runtime disappear.
\CFA outperforms other runtimes by a minuscule margin.
Libfibre follows very closely behind with basically the same performance and scaling.
Tokio maintains effectively the same curve shapes as it did with many threads, but it incurs extra costs for all \proc count.
As a result it is slightly outperformed by \CFA and libfibre.
While Go maintains overall similar results to the others, it again encounters significant variation at high \proc counts.
Inexplicably resulting in super-linear scaling for some runs, \ie the scalability curves displays a negative slope.

Interestingly, unlike the cycle benchmark, running with fewer \ats does not produce drastically different results.
In fact, the overall throughput stays almost exactly the same on the left and right column.

\begin{figure}
	\subfloat[][Throughput, 100 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.churn.nasus.ops.pstex_t}
		}
		\label{fig:churn:nasus:ops}
	}
	\subfloat[][Throughput, 2 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.churn.low.nasus.ops.pstex_t}
		}
		\label{fig:churn:nasus:low:ops}
	}

	\subfloat[][Scalability, 100 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.churn.nasus.ns.pstex_t}
		}
		\label{fig:churn:nasus:ns}
	}
	\subfloat[][Scalability, 2 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.churn.low.nasus.ns.pstex_t}
		}
		\label{fig:churn:nasus:low:ns}
	}
	\caption[Churn Benchmark on AMD]{\centering Churn Benchmark on AMD\smallskip\newline Throughput and scalability of the Churn on the benchmark on the AMD machine.
	For throughput, higher is better, for scalability, lower is better.
	Each series represent 15 independent runs, the dashed lines are maximums of each series while the solid lines are the median and the dotted lines are the minimums.}
	\label{fig:churn:nasus}
\end{figure}


Looking now at the results for the AMD architecture, Figure~\ref{fig:churn:nasus}, the results show a somewhat different story.
Looking at the left column first, Figures~\ref{fig:churn:nasus:ops} and \ref{fig:churn:nasus:ns}, \CFA, Libfibre and Tokio all produce decent scalability.
\CFA suffers particular from a larger variations at higher \proc counts, but almost all run still outperform the other runtimes.
Go still produces intriguing results in this case and even more intriguingly, the results have fairly low variation.

One possible explanation for this difference is that since Go has very few available concurrent primitives, a channel was used instead of a semaphore.
On paper a semaphore can be replaced by a channel and with zero-sized objects passed along equivalent performance could be expected.
However, in practice there can be implementation difference between the two.
This is especially true if the semaphore count can get somewhat high.
Note that this replacement is also made in the cycle benchmark, however in that context it did not seem to have a notable impact.

As second possible explanation is that Go may sometimes use the heap when allocating variables based on the result of escape analysis of the code.
It is possible that variables that should be placed on the stack are placed on the heap.
This could cause extra pointer chasing in the benchmark, heightening locality effects.
Depending on how the heap is structure, this could also lead to false sharing.

I did not further investigate what causes these unusual results.

Looking next at the right column, Figures~\ref{fig:churn:nasus:low:ops} and \ref{fig:churn:nasus:low:ns}, like for Intel all runtime obtain overall similar throughput between the left and right column.
\CFA, Libfibre and Tokio all have very close results.
Go still suffers from poor scalability but is now unusual in a different way.
While it obtains effectively constant performance regardless of \proc count, this ``sequential'' performance is higher than the other runtimes for low \proc count.
Up to 32 \procs, after which the other runtime manage to outscale Go.

The objective of this benchmark is to demonstrate that unparking \ats from remote \procs do not cause too much contention on the local queues.
Indeed, the fact most runtimes achieve some scaling between various \proc count demonstrate that migrations do not need to be serialized.
Again these result demonstrate \CFA achieves satisfactory performance.

\section{Locality}

\begin{figure}
\newsavebox{\myboxA}
\newsavebox{\myboxB}

\begin{lrbox}{\myboxA}
\begin{cfa}[tabsize=3]
Thread.main() {
	count := 0
	for {
		r := random() % len(spots)
		// go through the array
		@work( a )@

		spots[r].V()
		spots[r].P()
		count ++
		if must_stop() { break }
	}
	global.count += count
}
\end{cfa}
\end{lrbox}

\begin{lrbox}{\myboxB}
\begin{cfa}[tabsize=3]
Thread.main() {
	count := 0
	for {
		r := random() % len(spots)
		// go through the array
		@work( a )@
		// pass array to next thread
		spots[r].V( @a@ )
		@a = @spots[r].P()
		count ++
		if must_stop() { break }
	}
	global.count += count
}
\end{cfa}
\end{lrbox}

\subfloat[Thread$_1$]{\label{f:CFibonacci}\usebox\myboxA}
\hspace{3pt}
\vrule
\hspace{3pt}
\subfloat[Thread$_2$]{\label{f:CFAFibonacciGen}\usebox\myboxB}

\caption[Locality Benchmark : Pseudo Code]{Locality Benchmark : Pseudo Code}
\label{fig:locality:code}
\end{figure}

As mentioned in the churn benchmark, when unparking a \at, it is possible to either unpark to the local or remote ready-queue.
\footnote{It is also possible to unpark to a third unrelated ready-queue, but without additional knowledge about the situation, there is little to suggest this would not degrade performance.}
The locality experiment includes two variations of the churn benchmark, where an array of data is added.
In both variations, before @V@ing the semaphore, each \at increment random cells inside the array.
The @share@ variation then passes the array to the shadow-queue of the semaphore, transferring ownership of the array to the woken thread.
In the @noshare@ variation the array is not passed on and each thread continuously accesses its private array.

The objective here is to highlight the different decision made by the runtime when unparking.
Since each thread unparks a random semaphore, it means that it is unlikely that a \at will be unparked from the last \proc it ran on.
In the @share@ version, this means that unparking the \at on the local \proc is appropriate since the data was last modified on that \proc.
In the @noshare@ version, the unparking the \at on the remote \proc is the appropriate approach.

The expectation for this benchmark is to see a performance inversion, where runtimes will fare notably better in the variation which matches their unparking policy.
This should lead to \CFA, Go and Tokio achieving better performance in @share@ while libfibre achieves better performance in @noshare@.
Indeed, \CFA, Go and Tokio have the default policy of unpark \ats on the local \proc, where as libfibre has the default policy of unparks \ats wherever they last ran.

\subsection{Results}

\begin{figure}
	\subfloat[][Throughput share]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.locality.share.jax.ops.pstex_t}
		}
		\label{fig:locality:jax:share:ops}
	}
	\subfloat[][Throughput noshare]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.locality.noshare.jax.ops.pstex_t}
		}
		\label{fig:locality:jax:noshare:ops}
	}

	\subfloat[][Scalability share]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.locality.share.jax.ns.pstex_t}
		}
		\label{fig:locality:jax:share:ns}
	}
	\subfloat[][Scalability noshare]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.locality.noshare.jax.ns.pstex_t}
		}
		\label{fig:locality:jax:noshare:ns}
	}
	\caption[Locality Benchmark on Intel]{Locality Benchmark on Intel\smallskip\newline Throughput and scalability as a function of \proc count.
	For throughput, higher is better, for scalability, lower is better.
	Each series represent 15 independent runs, the dashed lines are maximums of each series while the solid lines are the median and the dotted lines are the minimums.}
	\label{fig:locality:jax}
\end{figure}
\begin{figure}
	\subfloat[][Throughput share]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.locality.share.nasus.ops.pstex_t}
		}
		\label{fig:locality:nasus:share:ops}
	}
	\subfloat[][Throughput noshare]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.locality.noshare.nasus.ops.pstex_t}
		}
		\label{fig:locality:nasus:noshare:ops}
	}

	\subfloat[][Scalability share]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.locality.share.nasus.ns.pstex_t}
		}
		\label{fig:locality:nasus:share:ns}
	}
	\subfloat[][Scalability noshare]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.locality.noshare.nasus.ns.pstex_t}
		}
		\label{fig:locality:nasus:noshare:ns}
	}
	\caption[Locality Benchmark on AMD]{Locality Benchmark on AMD\smallskip\newline Throughput and scalability as a function of \proc count.
	For throughput, higher is better, for scalability, lower is better.
	Each series represent 15 independent runs, the dashed lines are maximums of each series while the solid lines are the median and the dotted lines are the minimums.}
	\label{fig:locality:nasus}
\end{figure}

Figures~\ref{fig:locality:jax} and \ref{fig:locality:nasus} show the results for the locality experiment.
In both cases, the graphs on the left column show the results for the @share@ variation and the graphs on the right column show the results for the @noshare@.
Looking at the left column on Intel first, Figures~\ref{fig:locality:jax:share:ops} and \ref{fig:locality:jax:share:ns}, which shows the results for the @share@ variation.
\CFA and Tokio slightly outperform libfibre, as expected based on their \ats placement approach.
\CFA and Tokio both unpark locally and do not suffer cache misses on the transferred array.
Libfibre on the other hand unparks remotely, and as such the unparked \at is likely to miss on the shared data.
Go trails behind in this experiment, presumably for the same reasons that were observable in the churn benchmark.
Otherwise the results are similar to the churn benchmark, with lower throughput due to the array processing.
As for most previous results, all runtime suffer a performance hit after 48 \proc, which is the socket boundary.

Looking next at the right column on Intel, Figures~\ref{fig:locality:jax:noshare:ops} and \ref{fig:locality:jax:noshare:ns}, which shows the results for the @noshare@ variation.
The graph show the expected performance inversion where libfibre now outperforms \CFA and Tokio.
Indeed, in this case, unparking remotely means the unparked \at is less likely to suffer a cache miss on the array.
The leaves the \at data structure and the remote queue as the only source of likely cache misses.
Results show both are armotized fairly well in this case.
\CFA and Tokio both unpark locally and as a result suffer a marginal performance degradation from the cache miss on the array.

Looking now at the results for the AMD architecture, Figure~\ref{fig:locality:nasus}, the results show a story that is overall similar to the results on the Intel.
Again overall performance is higher and slightly more variation is visible.
Looking at the left column first, Figures~\ref{fig:locality:nasus:share:ops} and \ref{fig:locality:nasus:share:ns}, \CFA and Tokio still outperform libfibre, this time more significantly.
This is expected from the AMD server, which has smaller and more narrow caches that magnify the costs of processing the array.
Go still sees the same poor performance as on Intel.

Finally looking at the right column, Figures~\ref{fig:locality:nasus:noshare:ops} and \ref{fig:locality:nasus:noshare:ns}, like on Intel, the same performance inversion is present between libfibre and \CFA/Tokio.
Go still sees the same poor performance.

Overall, this experiment mostly demonstrates the two options available when unparking a \at.
Depending on the workload, either of these options can be the appropriate one.
Since it is prohibitively difficult to detect which approach is appropriate, all runtime much choose one of the two and live with the consequences.

Once again, this demonstrate that \CFA achieves equivalent performance to the other runtime, in this case matching the faster Tokio rather than Go which is trailing behind.

\section{Transfer}
The last benchmark is more of an experiment than a benchmark.
It tests the behaviour of the schedulers for a misbehaved workload.
In this workload, one of the \at is selected at random to be the leader.
The leader then spins in a tight loop until it has observed that all other \ats have acknowledged its leadership.
The leader \at then picks a new \at to be the next leader and the cycle repeats.
The benchmark comes in two flavours for the non-leader \ats:
once they acknowledged the leader, they either block on a semaphore or spin yielding.

The experiment is designed to evaluate the short-term load-balancing of a scheduler.
Indeed, schedulers where the runnable \ats are partitioned on the \procs may need to balance the \ats for this experiment to terminate.
This problem occurs because the spinning \at is effectively preventing the \proc from running any other \at.
In the semaphore flavour, the number of runnable \ats eventually dwindles down to only the leader.
This scenario is a simpler case to handle for schedulers since \procs eventually run out of work.
In the yielding flavour, the number of runnable \ats stays constant.
This scenario is a harder case to handle because corrective measures must be taken even when work is available.
Note, runtime systems with preemption circumvent this problem by forcing the spinner to yield.

In both flavours, the experiment effectively measures how long it takes for all \ats to run once after a given synchronization point.
In an ideal scenario where the scheduler is strictly FIFO, every thread would run once after the synchronization and therefore the delay between leaders would be given by:
$ \frac{CSL + SL}{NP - 1}$, where $CSL$ is the context switch latency, $SL$ is the cost for enqueueing and dequeuing a \at and $NP$ is the number of \procs.
However, if the scheduler allows \ats to run many times before other \ats are able to run once, this delay will increase.
The semaphore version is an approximation of the strictly FIFO scheduling, where none of the \ats \emph{attempt} to run more than once.
The benchmark effectively provides the fairness guarantee in this case.
In the yielding version however, the benchmark provides no such guarantee, which means the scheduler has full responsibility and any unfairness will be measurable.

While this is a fairly artificial scenario, it requires only a few simple pieces.
The yielding version of this simply creates a scenario where a \at runs uninterrupted in a saturated system, and starvation has an easily measured impact.
However, \emph{any} \at that runs uninterrupted for a significant period of time in a saturated system could lead to this kind of starvation.

\begin{figure}
\begin{cfa}
Thread.lead() {
	this.idx_seen = ++lead_idx
	if lead_idx > stop_idx {
		done := true
		return
	}
	// Wait for everyone to acknowledge my leadership
	start: = timeNow()
	for t in threads {
		while t.idx_seen != lead_idx {
			asm pause
			if (timeNow() - start) > 5 seconds { error() }
		}
	}
	// pick next leader
	leader := threads[ prng() % len(threads) ]
	// wake every one
	if ! exhaust {
		for t in threads {
			if t != me { t.wake() }
		}
	}
}
Thread.wait() {
	this.idx_seen := lead_idx
	if exhaust { wait() }
	else { yield() }
}
Thread.main() {
	while !done  {
		if leader == me { this.lead() }
		else { this.wait() }
	}
}
\end{cfa}
\caption[Transfer Benchmark : Pseudo Code]{Transfer Benchmark : Pseudo Code}
\label{fig:transfer:code}
\end{figure}

\subsection{Results}
\begin{figure}
\begin{centering}
\begin{tabular}{r | c c c c | c c c c }
Machine   &			\multicolumn{4}{c |}{Intel}                &          \multicolumn{4}{c}{AMD}                    \\
Variation & \multicolumn{2}{c}{Park} & \multicolumn{2}{c |}{Yield} & \multicolumn{2}{c}{Park} & \multicolumn{2}{c}{Yield} \\
\procs    &      2      &      192   &      2      &      192      &      2      &      256   &      2      &      256    \\
\hline
\CFA      & 106 $\mu$s  & ~19.9 ms   & 68.4 $\mu$s & ~1.2 ms       & 174 $\mu$s  & ~28.4 ms   & 78.8~~$\mu$s& ~~1.21 ms   \\
libfibre  & 127 $\mu$s  & ~33.5 ms   & DNC         & DNC           & 156 $\mu$s  & ~36.7 ms   & DNC         & DNC         \\
Go        & 106 $\mu$s  & ~64.0 ms   & 24.6 ms     & 74.3 ms       & 271 $\mu$s  & 121.6 ms   & ~~1.21~ms   & 117.4 ms    \\
Tokio     & 289 $\mu$s  & 180.6 ms   & DNC         & DNC           & 157 $\mu$s  & 111.0 ms   & DNC         & DNC
\end{tabular}
\end{centering}
\caption[Transfer Benchmark on Intel and AMD]{Transfer Benchmark on Intel and AMD\smallskip\newline Average measurement of how long it takes for all \ats to acknowledge the leader \at.
DNC stands for ``did not complete'', meaning that after 5 seconds of a new leader being decided, some \ats still had not acknowledged the new leader.}
\label{fig:transfer:res}
\end{figure}

Figure~\ref{fig:transfer:res} shows the result for the transfer benchmark with 2 \procs and all \procs, where each experiment runs 100 \at per \proc.
Note that the results here are only meaningful as a coarse measurement of fairness, beyond which small cost differences in the runtime and concurrent primitives begin to matter.
As such, data points that are the on the same order of magnitude as each other should be basically considered equal.
The takeaway of this experiment is the presence of very large differences.
The semaphore variation is denoted ``Park'', where the number of \ats dwindles down as the new leader is acknowledged.
The yielding variation is denoted ``Yield''.
The experiment was only run for the extremes of the number of \procs since the scaling is not the focus of this experiment.

The first two columns show the results for the the semaphore variation on Intel.
While there are some differences in latencies, \CFA is consistenly the fastest and Tokio the slowest, all runtime achieve results that are fairly close.
Again, this experiment is meant to highlight major differences so latencies within $10\times$ of each other are considered close to each other.

Looking at the next two columns, the results for the yield variation in Intel, the story is very different.
\CFA achieves better latencies, presumably due to the lack of synchronization on the semaphore.
Neither Libfibre or Tokio complete the experiment.
Both runtime use classical work-stealing scheduling and therefore since non of the work-queues are ever emptied no load balancing occurs.
Go does complete the experiment, but with drastically higher latency:
latency at 2 \procs is $350\times$ higher than \CFA and $70\times$ higher at 192 \procs.
This is because Go also has a classic work-stealing scheduler, but it adds preemption which interrupts the spinning leader after a period.

Looking now at the results for the AMD architecture, the results show effectively the same story.
The first two columns show all runtime obtaining results well within $10\times$ of each other.
The next two columns again show \CFA producing low latencies while Libfibre and Tokio do not complete the experiment.
Go still has notably higher latency but the difference is less drastic on 2 \procs, where it produces a $15\times$ difference as opposed to a $100\times$ difference on 256 \procs.

This experiments clearly demonstrate that while the other runtimes achieve similar performance in previous benchmarks, here \CFA achieves significantly better fairness.
The semaphore variation serves as a control group, where all runtimes are expected to transfer leadership fairly quickly.
Since \ats block after acknowledging the leader, this experiment effectively measures how quickly \procs can steal \ats from the \proc running leader.
Figure~\ref{fig:transfer:res} shows that while Go and Tokio are slower, all runtime achieve decent latency.
However, the yielding variation shows an entirely different picture.
Since libfibre and Tokio have a traditional work-stealing scheduler, \procs that have \ats on their local queues will never steal from other \procs.
The result is that the experiment simply does not complete for these runtime.
Without \procs stealing from the \proc running the leader, the experiment will simply never terminate.
Go manages to complete the experiment because it adds preemption on top of classic work-stealing.
However, since preemption is fairly costly it achieves significantly worst performance.
In contrast, \CFA achieves equivalent performance in both variations, demonstrating very good fairness.
Interestingly \CFA achieves better delays in the yielding version than the semaphore version, however, that is likely due to fairness being equivalent but removing the cost of the semaphores and idle-sleep.