source: doc/theses/colby_parsons_MMAth/text/waituntil.tex @ 508671e

% ======================================================================
% ======================================================================
\chapter{Waituntil}\label{s:waituntil}
% ======================================================================
% ======================================================================

Consider the following motivational problem that we shall title the bathroom problem.
There are @N@ stalls (resources) in a bathroom and there are @M@ people (threads).
Each stall has their own lock since only one person may occupy a stall at a time.
The standard way that humans solve this problem is that they check if the stalls are occupied and if they all are they queue and watch the stalls until one is free and then enter and lock the stall.
This solution is simple in real life, but can be difficult to implement in a concurrent context as it requires the threads to somehow wait on all the stalls at the same time.
The naive solution to this is for each thread to spin indefinitely continually checking the stalls until one is free.
This wastes cycles and also results in no fairness among threads waiting for stalls as a thread will jump in the first stall available without any regard to other waiting threads.
The ability to wait for the first stall available without spinning can be done with concurrent tools that provide \gls{synch_multiplex}, the ability to wait synchronously for a resource or set of resources.

\section{History of Synchronous Multiplexing}
There is a history of tools that provide \gls{synch_multiplex}.
Some of the most well known include the set of unix system utilities: select(2)\cite{linux:select}, poll(2)\cite{linux:poll}, and epoll(7)\cite{linux:epoll}, and the select statement provided by Go\cite{go:selectref}.

Before one can examine the history of \gls{synch_multiplex} implementations in detail, the preceding theory must be discussed.
The theory surrounding this topic was largely introduced by Hoare in his 1985 CSP book \cite{Hoare85} and his later work with Roscoe on the theoretical language Occam\cite{Roscoe88}.
Both include guards for communication channels and the ability to wait for a single channel to be ready out of a set of channels.
The work on Occam in \cite{Roscoe88} calls their \gls{synch_multiplex} primitive ALT, which waits for one resource to be available and then executes a corresponding block of code.
Waiting for one resource out of a set of resources can be thought of as a logical exclusive or over the set of resources.
Guards are a conditional operator similar to an @if@, except they apply to the resource being waited on.
If a guard is false then the resource it guards is considered to not be in the set of resources being waited on.
Guards can be simulated using if statements, but to do so requires \[2^N\] if cases, where @N@ is the number of guards.
The equivalence between guards and exponential if statements comes from an Occam ALT statement rule~\cite{Roscoe88}, which is presented in \CFA syntax in Figure~\ref{f:wu_if}.
Providing guards allows for easy toggling of waituntil clauses without introducing repeated code.

\begin{figure}
\begin{cfa}
when( predicate ) waituntil( A ) {}
or waituntil( B ) {}
// ===
if ( predicate ) {
    waituntil( A ) {}
    or waituntil( B ) {}
} else {
    waituntil( B ) {}
}
\end{cfa}
\caption{Occam's guard to if statement equivalence shown in \CFA syntax.}
\label{f:wu_if}
\end{figure}

Switching to implementations, it is important to discuss the resources being multiplexed.
While the aforementioned theory discusses waiting on channels, the earliest known implementation of a synchronous multiplexing tool, Unix's select(2), is multiplexed over file descriptors.
The select(2) system call takes in sets of file descriptors to wait on as arguments and an optional timeout.
Select will block until either some subset of file descriptors are available or the timeout expires.
All file descriptors that are ready will be returned.
This early implementation differs from the theory as when the call from select returns it may provide more than one ready file descriptor.
As such select has a logical or multiplexing semantics, whereas the theory described exclusive-or semantics.
This is not a drawback.
A user can easily achieve exclusive-or semantics with select by arbitrarily choosing only one of the returned descriptors to operate on.
Select was followed by poll(2), and later epoll(7), which both improved upon drawbacks in their predecessors.
The syscall poll(2) improved on select by allowing users to monitor descriptors with numbers higher than 1024 which was not supported by select.
Epoll then improved on poll to return the set of file descriptors since poll would only say that some descriptor from the set was ready but not return which ones were ready.

It is worth noting these \gls{synch_multiplex} tools mentioned so far interact directly with the operating system and are often used to communicate between processes.
Later \gls{synch_multiplex} started to appear in user-space to support fast multiplexed concurrent communication between threads.
An early example of \gls{synch_multiplex} is the select statement in Ada~\cite[\S~9.7]{Ichbiah79}.
The select statement in Ada allows a task to multiplex over some subset of its own methods that it would like to @accept@ calls to.
Tasks in Ada can be thought of as threads which are an object of a specific class, and as such have methods, fields, etc.
This statement has the same exclusive-or semantics as ALT from Occam, and supports guards as described in Occam, however it multiplexes over methods on rather than multiplexing over channels.
A code block is associated with each @accept@, and the method that is @accept@ed first has its corresponding code block run after the task unblocks.
In this way the select statement in Ada provides rendezvous points for threads, rather than providing some resource through message passing.
The select statement in Ada also supports an optional timeout with the same semantics as select(2), and provides an @else@.
The @else@ changes the synchronous multiplexing to asynchronous multiplexing.
If an @else@ clause is in a select statement and no calls to the @accept@ed methods are immediately available the code block associated with the @else@ is run and the task does not block.

A popular example of user-space \gls{synch_multiplex} is Go with their select statement~\cite{go:selectref}.
Go's select statement operates on channels and has the same exclusive-or semantics as the ALT primitive from Occam, and has associated code blocks for each clause like ALT and Ada.
However, unlike Ada and ALT, Go does not provide any guards for their select statement cases.
Go provides a timeout utility and also provides a @default@ clause which has the same semantics as Ada's @else@ clause.

\uC provides \gls{synch_multiplex} over futures with their @_Select@ statement and Ada-style \gls{synch_multiplex} over monitor methods with their @_Accept@ statement~\cite{uC++}.
Their @_Accept@ statement builds upon the select statement offered by Ada, by offering both @and@ and @or@ semantics, which can be used together in the same statement.
These semantics are also supported for \uC's @_Select@ statement.
This enables fully expressive \gls{synch_multiplex} predicates.

There are many other languages that provide \gls{synch_multiplex}, including Rust's @select!@ over futures~\cite{rust:select}, OCaml's @select@ over channels~\cite{ocaml:channel}, and C++14's @when_any@ over futures~\cite{cpp:whenany}.
Note that while C++14 and Rust provide \gls{synch_multiplex}, their implemetations leave much to be desired as they both rely on busy-waiting polling to wait on multiple resources.

\section{Other Approaches to Synchronous Multiplexing}
To avoid the need for \gls{synch_multiplex}, all communication between threads/processes has to come from a single source.
One key example is Erlang, in which each process has a single heterogenous mailbox that is the sole source of concurrent communication, removing the need for \gls{synch_multiplex} as there is only one place to wait on resources.
In a similar vein, actor systems circumvent the \gls{synch_multiplex} problem as actors are traditionally non-blocking, so they will only block when waiting for the next message.
While these approaches solve the \gls{synch_multiplex} problem, they introduce other issues.
Consider the case where a thread has a single source of communication (like erlang and actor systems) wants one of a set of @N@ resources.
It requests @N@ resources and waits for responses.
In the meantime the thread may receive other communication, and may either has to save and postpone the related work or discard it.
After the thread receives one of the @N@ resources, it will continue to receive the other ones it requested, even if it does not need them.
If the requests for the other resources need to be retracted, the burden falls on the programmer to determine how to synchronize appropriately to ensure that only one resource is delivered.

\section{\CFA's Waituntil Statement}
The new \CFA \gls{synch_multiplex} utility introduced in this work is the @waituntil@ statement.
There is a @waitfor@ statement in \CFA that supports Ada-style \gls{synch_multiplex} over monitor methods, so this @waituntil@ focuses on synchronizing over other resources.
All of the \gls{synch_multiplex} features mentioned so far are monomorphic, only supporting one resource to wait on, select(2) supports file descriptors, Go's select supports channel operations, \uC's select supports futures, and Ada's select supports monitor method calls.
The waituntil statement in \CFA is polymorphic and provides \gls{synch_multiplex} over any objects that satisfy the trait in Figure~\ref{f:wu_trait}.
No other language provides a synchronous multiplexing tool polymorphic over resources like \CFA's waituntil.
All others them tie themselves to some specific type of resource.

\begin{figure}
\begin{cfa}
forall(T & | sized(T))
trait is_selectable {
    // For registering a waituntil stmt on a selectable type
    bool register_select( T &, select_node & );

    // For unregistering a waituntil stmt from a selectable type
    bool unregister_select( T &, select_node & );

    // on_selected is run on the selecting thread prior to executing the statement associated with the select_node
    void on_selected( T &, select_node & );
};
\end{cfa}
\caption{Trait for types that can be passed into \CFA's waituntil statement.}
\label{f:wu_trait}
\end{figure}

Currently locks, channels, futures and timeouts are supported by the waituntil statement, but this will be expanded as other use cases arise.
The waituntil statement supports guarded clauses, like Ada, and Occam, supports both @or@, and @and@ semantics, like \uC, and provides an @else@ for asynchronous multiplexing. An example of \CFA waituntil usage is shown in Figure~\ref{f:wu_example}. In Figure~\ref{f:wu_example} the waituntil statement is waiting for either @Lock@ to be available or for a value to be read from @Channel@ into @i@ and for @Future@ to be fulfilled. The semantics of the waituntil statement will be discussed in detail in the next section.

\begin{figure}
\begin{cfa}
future(int) Future;
channel(int) Channel;
owner_lock Lock;
int i = 0;

waituntil( Lock ) { ... }
or when( i == 0 ) waituntil( i << Channel ) { ... }
and waituntil( Future ) { ... }
\end{cfa}
\caption{Example of \CFA's waituntil statement}
\label{f:wu_example}
\end{figure}

\section{Waituntil Semantics}
There are two parts of the waituntil semantics to discuss, the semantics of the statement itself, \ie @and@, @or@, @when@ guards, and @else@ semantics, and the semantics of how the waituntil interacts with types like channels, locks and futures.
To start, the semantics of the statement itself will be discussed.

\subsection{Waituntil Statement Semantics}
The @or@ semantics are the most straightforward and nearly match those laid out in the ALT statement from Occam, the clauses have an exclusive-or relationship where the first one to be available will be run and only one clause is run.
\CFA's @or@ semantics differ from ALT semantics in one respect, instead of randomly picking a clause when multiple are available, the clause that appears first in the order of clauses will be picked.
\eg in the following example, if @foo@ and @bar@ are both available, @foo@ will always be selected since it comes first in the order of waituntil clauses.
\begin{cfa}
future(int) bar;
future(int) foo;
waituntil( foo ) { ... }
or waituntil( bar ) { ... }
\end{cfa}

The @and@ semantics match the @and@ semantics used by \uC.
When multiple clauses are joined by @and@, the waituntil will make a thread wait for all to be available, but will run the corresponding code blocks \emph{as they become available}.
As @and@ clauses are made available, the thread will be woken to run those clauses' code blocks and then the thread will wait again until all clauses have been run. 
This allows work to be done in parallel while synchronizing over a set of resources, and furthermore gives a good reason to use the @and@ operator.
If the @and@ operator waited for all clauses to be available before running, it would not provide much more use that just acquiring those resources one by one in subsequent lines of code.
The @and@ operator binds more tightly than the @or@ operator.
To give an @or@ operator higher precedence brackets can be used.
\eg the following waituntil unconditionally waits for @C@ and one of either @A@ or @B@, since the @or@ is given higher precendence via brackets.
\begin{cfa}
(waituntil( A ) { ... }
or waituntil( B ) { ... } )
and waituntil( C ) { ... }
\end{cfa}

The guards in the waituntil statement are called @when@ clauses.
The @when@ clause is passed a boolean expression.
All the @when@ boolean expressions are evaluated before the waituntil statement is run.
The guards in Occam's ALT effectively toggle clauses on and off, where a clause will only be evaluated and waited on if the corresponding guard is @true@.
The guards in the waituntil statement operate the same way, but require some nuance since both @and@ and @or@ operators are supported.
When a guard is false and a clause is removed, it can be thought of as removing that clause and its preceding operator from the statement.
\eg in the following example the two waituntil statements are semantically the same.
\begin{cfa}
when(true) waituntil( A ) { ... }
or when(false) waituntil( B ) { ... }
and waituntil( C ) { ... }
// === 
waituntil( A ) { ... }
and waituntil( C ) { ... }
\end{cfa}

The @else@ clause on the waituntil has identical semantics to the @else@ clause in Ada.
If all resources are not immediately available and there is an @else@ clause, the @else@ clause is run and the thread will not block.

\subsection{Waituntil Type Semantics}
As described earlier, to support interaction with the waituntil statement a type must support the trait shown in Figure~\ref{f:wu_trait}.
The waituntil statement expects types to register and unregister themselves via calls to @register_select@ and @unregister_select@ respectively.
When a resource becomes available, @on_selected@ is run.
Many types may not need @on_selected@, but it is provided since some types may need to check and set things before the resource can be accessed in the code block.
The register/unregister routines in the trait return booleans.
The return value of @register_select@ is @true@ if the resource is immediately available, and @false@ otherwise.
The return value of @unregister_select@ is @true@ if the corresponding code block should be run after unregistration and @false@ otherwise.
The routine @on_selected@, and the return value of @unregister_select@ were needed to support channels as a resource.
More detail on channels and their interaction with waituntil will be discussed in Section~\ref{s:wu_chans}.

\section{Waituntil Implementation}
The waituntil statement is not inherently complex, and can be described as a few steps.
The complexity of the statement comes from the consideration of race conditions and synchronization needed when supporting various primitives.
The basic steps that the waituntil statement follows are the following.

First the waituntil statement creates a @select_node@ per resource that is being waited on.
The @select_node@ is an object that stores the waituntil data pertaining to one of the resources.
Then, each @select_node@ is then registered with the corresponding resource.
The thread executing the waituntil then enters a loop that will loop until the entire waituntil statement being satisfied.
In each iteration of the loop the thread attempts to block.
If any clauses are satified the block will fail and the thread will proceed, otherwise the block succeeds.
After proceeding past the block all clauses are checked for completion and the completed clauses have their code blocks run.
Once the thread escapes the loop, the @select_nodes@ are unregistered from the resources.
In the case where the block suceeds, the thread will be woken by the thread that marks one of the resources as available.
Pseudocode detailing these steps is presented in the following code block.

\begin{cfa}
select_nodes s[N]; // N select nodes
for ( node in s )
    register_select( resource, node );
while( statement not satisfied ) {
    // try to block
    for ( resource in waituntil statement )
        if ( resource is avail ) run code block
}
for ( node in s )
    unregister_select( resource, node );
\end{cfa}

These steps give a basic, but mildly inaccurate overview of how the statement works.
Digging into some parts of the implementation will shed light on more of the specifics and provide some accuracy.

\subsection{Locks}
Locks are one of the resources supported in the waituntil statement.
When a thread waits on multiple locks via a waituntil, it enqueues a @select_node@ in each of the lock's waiting queues.
When a @select_node@ reaches the front of the queue and gains ownership of a lock, the blocked thread is notified.
The lock will be held until the node is unregistered.
To prevent the waiting thread from holding many locks at once and potentially introducing a deadlock, the node is unregistered right after the corresponding code block is executed.
This prevents deadlocks since the waiting thread will never hold a lock while waiting on another resource.
As such the only nodes unregistered at the end are the ones that have not run.

\subsection{Timeouts}
Timeouts in the waituntil take the form of a duration being passed to a @sleep@ or @timeout@ call.
An example is shown in the following code.

\begin{cfa}
waituntil( sleep( 1`ms ) ) {}
waituntil( timeout( 1`s ) ) {} or waituntil( timeout( 2`s ) ) {}
waituntil( timeout( 1`ns ) ) {} and waituntil( timeout( 2`s ) ) {}
\end{cfa}

The timeout implementation highlights a key part of the waituntil semantics, the expression is evaluated before the waituntil runs.
As such calls to @sleep@ and @timeout@ do not block, but instead return a type that supports the @is_selectable@ trait.
This mechanism is needed for types that want to support multiple operations such as channels that support reading and writing.

\subsection{Channels}\label{s:wu_chans}
To support both waiting on both reading and writing to channels, the opperators @?<<?@ and @?>>?@ are used to show reading and writing to a channel respectively, where the lefthand operand is the value and the righthand operand is the channel.
Channels require significant complexity to wait on for a few reasons.
The first reason is that reading or writing to a channel is a mutating operation.
What this means is that if a read or write to a channel occurs, the state of the channel has changed.
In comparison, for standard locks and futures, if a lock is acquired then released or a future is ready but not accessed, the states of the lock and the future are not modified.
In this way if a waituntil over locks or futures have some resources available that were not consumed, it is not an issue.
However, if a thread modifies a channel on behalf of a thread blocked on a waituntil statement, it is important that the corresponding waituntil code block is run, otherwise there is a potentially erroneous mismatch between the channel state and associated side effects.
As such, the @unregister_select@ routine has a boolean return that is used by channels to indicate when the operation was completed but the block was not run yet.
As such some channel code blocks may be run as part of the unregister.
Furthermore if there are both @and@ and @or@ operators, the @or@ operators stop behaving like exclusive-or semantics since this race between operations and unregisters exists.

It was deemed important that exclusive-or semantics were maintained when only @or@ operators were used, so this situation has been special-cased, and is handled by having all clauses race to set a value \emph{before} operating on the channel.
This approach is infeasible in the case where @and@ and @or@ operators are used.
To show this consider the following waituntil statement.

\begin{cfa}
waituntil( i >> A ) {} and waituntil( i >> B ) {}
or waituntil( i >> C ) {} and waituntil( i >> D ) {}
\end{cfa}

If exclusive-or semantics were followed, this waituntil would only run the code blocks for @A@ and @B@, or the code blocks for @C@ and @D@.
However, to race before operation completion in this case introduces a race whose complexity increases with the size of the waituntil statement.
In the example above, for @i@ to be inserted into @C@, to ensure the exclusive-or it must be ensured that @i@ can also be inserted into @D@.
Furthermore, the race for the @or@ would also need to be won.
However, due to TOCTOU issues, one cannot know that all resources are available without acquiring all the internal locks of channels in the subtree.
This is not a good solution for two reasons.
It is possible that once all the locks are acquired that the subtree is not satisfied and they must all be released.
This would incur high cost for signalling threads and also heavily increase contention on internal channel locks.
Furthermore, the waituntil statement is polymorphic and can support resources that do not have internal locks, which also makes this approach infeasible.
As such, the exclusive-or semantics are lost when using both @and@ and @or@ operators since they can not be supported without significant complexity and hits to waituntil statement performance.

The mechanism by which the predicate of the waituntil is checked is discussed in more detail in Section~\ref{s:wu_guards}.

Another consideration introduced by channels is that supporting both reading and writing to a channel in a waituntil means that one waituntil clause may be the notifier for another waituntil clause.
This becomes a problem when dealing with the special-cased @or@ where the clauses need to win a race to operate on a channel.
When you have both a special-case @or@ inserting on one thread and another special-case @or@ consuming is blocked on another thread there is not one but two races that need to be consolidated by the inserting thread.
(The race can occur in the opposite case with a blocked producer and signalling consumer too.)
For them to know that the insert succeeded, they need to win the race for their own waituntil and win the race for the other waituntil.
Go solves this problem in their select statement by acquiring the internal locks of all channels before registering the select on the channels.
This eliminates the race since no other threads can operate on the blocked channel since its lock will be held.

This approach is not used in \CFA since the waituntil is polymorphic.
Not all types in a waituntil have an internal lock, and when using non-channel types acquiring all the locks incurs extra uneeded overhead.
Instead this race is consolidated in \CFA in two phases by having an intermediate pending status value for the race.
This case is detectable, and if detected the thread attempting to signal will first race to set the race flag to be pending.
If it succeeds, it then attempts to set the consumer's race flag to its success value.
If the producer successfully sets the consumer race flag, then the operation can proceed, if not the signalling thread will set its own race flag back to the initial value.
If any other threads attempt to set the producer's flag and see a pending value, they will wait until the value changes before proceeding to ensure that in the case that the producer fails, the signal will not be lost.
This protocol ensures that signals will not be lost and that the two races can be resolved in a safe manner.

Channels in \CFA have exception based shutdown mechanisms that the waituntil statement needs to support.
These exception mechanisms were what brought in the @on_selected@ routine.
This routine is needed by channels to detect if they are closed upon waking from a waituntil statement, to ensure that the appropriate behaviour is taken.

\subsection{Guards and Statement Predicate}\label{s:wu_guards}
Checking for when a synchronous multiplexing utility is done is trivial when it has an or/xor relationship, since any resource becoming available means that the blocked thread can proceed.
In \uC and \CFA, their \gls{synch_multiplex} utilities involve both an @and@ and @or@ operator, which make the problem of checking for completion of the statement more difficult.

In the \uC @_Select@ statement, they solve this problem by constructing a tree of the resources, where the internal nodes are operators and the leafs are the resources.
The internal nodes also store the status of each of the subtrees beneath them.
When resources become available, their status is modified and the status of the leaf nodes percolate into the internal nodes update the state of the statement.
Once the root of the tree has both subtrees marked as @true@ then the statement is complete.
As an optimization, when the internal nodes are updated, their subtrees marked as @true@ are effectively pruned and are not touched again.
To support \uC's @_Select@ statement guards, the tree prunes the branch if the guard is false.

The \CFA waituntil statement blocks a thread until a set of resources have become available that satisfy the underlying predicate.
The waiting condition of the waituntil statement can be represented as a predicate over the resources, joined by the waituntil operators, where a resource is @true@ if it is available, and @false@ otherwise.
In \CFA, this representation is used as the mechanism to check if a thread is done waiting on the waituntil.
Leveraging the compiler, a routine is generated per waituntil that is passed the statuses of the resources and returns a boolean that is @true@ when the waituntil is done, and false otherwise.
To support guards on the \CFA waituntil statement, the status of a resource disabled by a guard is set to ensure that the predicate function behaves as if that resource is no longer part of the predicate.

In \uC's @_Select@, it supports operators both inside and outside the clauses of their statement.
\eg in the following example the code blocks will run once their corresponding predicate inside the round braces is satisfied.

% C_TODO put this is uC++ code style not cfa-style
\begin{cfa}
Future_ISM<int> A, B, C, D;
_Select( A || B && C ) { ... }
and _Select( D && E ) { ... }
\end{cfa}

This is more expressive that the waituntil statement in \CFA.
In \CFA, since the waituntil statement supports more resources than just futures, implmenting operators inside clauses was avoided for a few reasons.
As an example, suppose \CFA supported operators inside clauses and consider the code snippet in Figure~\ref{f:wu_inside_op}.

\begin{figure}
\begin{cfa}
owner_lock A, B, C, D;
waituntil( A && B ) { ... }
or waituntil( C && D ) { ... }
\end{cfa}
\caption{Example of unsupported operators inside clauses in \CFA.}
\label{f:wu_inside_op}
\end{figure}

If the waituntil in Figure~\ref{f:wu_inside_op} works with the same semantics as described and acquires each lock as it becomes available, it opens itself up to possible deadlocks since it is now holding locks and waiting on other resources.
As such other semantics would be needed to ensure that this operation is safe.
One possibility is to use \CC's @scoped_lock@ approach that was described in Section~\ref{s:DeadlockAvoidance}, however the potential for livelock leaves much to be desired.
Another possibility would be to use resource ordering similar to \CFA's @mutex@ statement, but that alone is not sufficient if the resource ordering is not used everywhere.
Additionally, using resource ordering could conflict with other semantics of the waituntil statement.
To show this conflict, consider if the locks in Figure~\ref{f:wu_inside_op} were ordered @D@, @B@, @C@, @A@.
If all the locks are available, it becomes complex to both respect the ordering of the waituntil in Figure~\ref{f:wu_inside_op} when choosing which code block to run and also respect the lock ordering of @D@, @B@, @C@, @A@ at the same time.
One other way this could be implemented is to wait until all resources for a given clause are available before proceeding to acquire them, but this also quickly becomes a poor approach.
This approach won't work due to TOCTOU issues, as it is not possible to ensure that the full set resources are available without holding them all first.
Operators inside clauses in \CFA could potentially be implemented with careful circumvention of the problems involved, but it was not deemed an important feature when taking into account the runtime cost that would need to be paid to handle these situations.
The problem of operators inside clauses also becomes a difficult issue to handle when supporting channels.
If internal operators were supported, it would require some way to ensure that channels with internal operators are modified on if and only if the corresponding code block is run, but that is not feasible due to reasons described in the exclusive-or portion of Section~\ref{s:wu_chans}. 

\section{Waituntil Performance}
The two \gls{synch_multiplex} utilities that are in the realm of comparability with the \CFA waituntil statement are the Go @select@ statement and the \uC @_Select@ statement.
As such, two microbenchmarks are presented, one for Go and one for \uC to contrast the systems.
The similar utilities discussed at the start of this chapter in C, Ada, Rust, \CC, and OCaml are either not meaningful or feasible to benchmark against.
The select(2) and related utilities in C are not comparable since they are system calls that go into the kernel and operate on file descriptors, whereas the waituntil exists solely in userspace.
Ada's @select@ only operates on methods, which is done in \CFA via the @waitfor@ utility so it is not feasible to benchmark against the @waituntil@, which cannot wait on the same resource.
Rust and \CC only offer a busy-wait based approach which is not meaningly comparable to a blocking approach.
OCaml's @select@ waits on channels that are not comparable with \CFA and Go channels, which makes the OCaml @select@ infeasible to compare it with Go's @select@ and \CFA's @waituntil@.
Given the differences in features, polymorphism, and expressibility between the waituntil and @select@, and @_Select@, the aim of the microbenchmarking in this chapter is to show that these implementations lie in the same realm of performance, not to pick a winner.

\subsection{Channel Benchmark}
The channel multiplexing microbenchmarks compare \CFA's waituntil and Go's select, where the resource being waited on is a set of channels.
The basic structure of the microbenchmark has the number of cores split evenly between producer and consumer threads, \ie, with 8 cores there would be 4 producer threads and 4 consumer threads.
The number of clauses @C@ is also varied, with results shown with 2, 4, and 8 clauses.
Each clause has a respective channel that is operates on.
Each producer and consumer repeatedly waits to either produce or consume from one of the @C@ clauses and respective channels.
An example in \CFA syntax of the work loop in the consumer main with @C = 4@ clauses follows.

\begin{cfa}
    for (;;)
        waituntil( val << chans[0] ) {} or waituntil( val << chans[1] ) {} 
        or waituntil( val << chans[2] ) {} or waituntil( val << chans[3] ) {}
\end{cfa}
A successful consumption is counted as a channel operation, and the throughput of these operations is measured over 10 seconds.
The first microbenchmark measures throughput of the producers and consumer synchronously waiting on the channels and the second has the threads asynchronously wait on the channels.
The results are shown in Figures~\ref{f:select_contend_bench} and~\ref{f:select_spin_bench} respectively.

\begin{figure}
        \centering
    \captionsetup[subfloat]{labelfont=footnotesize,textfont=footnotesize}
        \subfloat[AMD]{
                \resizebox{0.5\textwidth}{!}{\input{figures/nasus_Contend_2.pgf}}
        }
        \subfloat[Intel]{
                \resizebox{0.5\textwidth}{!}{\input{figures/pyke_Contend_2.pgf}}
        }
    \bigskip

        \subfloat[AMD]{
                \resizebox{0.5\textwidth}{!}{\input{figures/nasus_Contend_4.pgf}}
        }
        \subfloat[Intel]{
                \resizebox{0.5\textwidth}{!}{\input{figures/pyke_Contend_4.pgf}}
        }
    \bigskip

        \subfloat[AMD]{
                \resizebox{0.5\textwidth}{!}{\input{figures/nasus_Contend_8.pgf}}
        }
        \subfloat[Intel]{
                \resizebox{0.5\textwidth}{!}{\input{figures/pyke_Contend_8.pgf}}
        }
        \caption{The channel synchronous multiplexing benchmark comparing Go select and \CFA waituntil statement throughput (higher is better).}
        \label{f:select_contend_bench}
\end{figure}

\begin{figure}
        \centering
    \captionsetup[subfloat]{labelfont=footnotesize,textfont=footnotesize}
        \subfloat[AMD]{
                \resizebox{0.5\textwidth}{!}{\input{figures/nasus_Spin_2.pgf}}
        }
        \subfloat[Intel]{
                \resizebox{0.5\textwidth}{!}{\input{figures/pyke_Spin_2.pgf}}
        }
    \bigskip

        \subfloat[AMD]{
                \resizebox{0.5\textwidth}{!}{\input{figures/nasus_Spin_4.pgf}}
        }
        \subfloat[Intel]{
                \resizebox{0.5\textwidth}{!}{\input{figures/pyke_Spin_4.pgf}}
        }
    \bigskip

        \subfloat[AMD]{
                \resizebox{0.5\textwidth}{!}{\input{figures/nasus_Spin_8.pgf}}
        }
        \subfloat[Intel]{
                \resizebox{0.5\textwidth}{!}{\input{figures/pyke_Spin_8.pgf}}
        }
        \caption{The asynchronous multiplexing channel benchmark comparing Go select and \CFA waituntil statement throughput (higher is better).}
        \label{f:select_spin_bench}
\end{figure}

Both Figures~\ref{f:select_contend_bench} and~\ref{f:select_spin_bench} have similar results when comparing @select@ and @waituntil@.
In the AMD benchmarks, the performance is very similar as the number of cores scale.
The AMD machine has been observed to have higher caching contention cost, which creates on a bottleneck on the channel locks, which results in similar scaling between \CFA and Go.
At low cores, Go has significantly better performance, which is likely due to an optimization in their scheduler.
Go heavily optimizes thread handoffs on their local runqueue, which can result in very good performance for low numbers of threads which are parking/unparking eachother~\cite{go:sched}.
In the Intel benchmarks, \CFA performs better than Go as the number of cores scale and as the number of clauses scale.
This is likely due to Go's implementation choice of acquiring all channel locks when registering and unregistering channels on a @select@.
Go then has to hold a lock for every channel, so it follows that this results in worse performance as the number of channels increase.
In \CFA, since races are consolidated without holding all locks, it scales much better both with cores and clauses since more work can occur in parallel.
This scalability difference is more significant on the Intel machine than the AMD machine since the Intel machine has been observed to have lower cache contention costs.

The Go approach of holding all internal channel locks in the select has some additional drawbacks.
This approach results in some pathological cases where Go's system throughput on channels can greatly suffer.
Consider the case where there are two channels, @A@ and @B@.
There are both a producer thread and a consumer thread, @P1@ and @C1@, selecting both @A@ and @B@.
Additionally, there is another producer and another consumer thread, @P2@ and @C2@, that are both operating solely on @B@.
Compared to \CFA this setup results in significantly worse performance since @P2@ and @C2@ cannot operate in parallel with @P1@ and @C1@ due to all locks being acquired.
This case may not be as pathological as it may seem.
If the set of channels belonging to a select have channels that overlap with the set of another select, they lose the ability to operate on their select in parallel.
The implementation in \CFA only ever holds a single lock at a time, resulting in better locking granularity.
Comparison of this pathological case is shown in Table~\ref{t:pathGo}.
The AMD results highlight the worst case scenario for Go since contention is more costly on this machine than the Intel machine.

\begin{table}[t]
\centering
\setlength{\extrarowheight}{2pt}
\setlength{\tabcolsep}{5pt}

\caption{Throughput (channel operations per second) of \CFA and Go for a pathologically bad case for contention in Go's select implementation}
\label{t:pathGo}
\begin{tabular}{*{5}{r|}r}
    & \multicolumn{1}{c|}{\CFA} & \multicolumn{1}{c@{}}{Go} \\
    \hline
    AMD         & \input{data/nasus_Order} \\
    \hline
    Intel       & \input{data/pyke_Order}
\end{tabular}
\end{table}

Another difference between Go and \CFA is the order of clause selection when multiple clauses are available.
Go "randomly" selects a clause, but \CFA chooses the clause in the order they are listed~\cite{go:select}.
This \CFA design decision allows users to set implicit priorities, which can result in more predictable behaviour, and even better performance in certain cases, such as the case shown in  Table~\ref{}.
If \CFA didn't have priorities, the performance difference in Table~\ref{} would be less significant since @P1@ and @C1@ would try to compete to operate on @B@ more often with random selection.

\subsection{Future Benchmark}
The future benchmark compares \CFA's waituntil with \uC's @_Select@, with both utilities waiting on futures.
Both \CFA's @waituntil@ and \uC's @_Select@ have very similar semantics, however @_Select@ can only wait on futures, whereas the @waituntil@ is polymorphic. 
They both support @and@ and @or@ operators, but the underlying implementation of the operators differs between @waituntil@ and @_Select@.
The @waituntil@ statement checks for statement completion using a predicate function, whereas the @_Select@ statement maintains a tree that represents the state of the internal predicate.

\begin{figure}
        \centering
        \subfloat[AMD Future Synchronization Benchmark]{
                \resizebox{0.5\textwidth}{!}{\input{figures/nasus_Future.pgf}}
                \label{f:futureAMD}
        }
        \subfloat[Intel Future Synchronization Benchmark]{
                \resizebox{0.5\textwidth}{!}{\input{figures/pyke_Future.pgf}}
                \label{f:futureIntel}
        }
        \caption{\CFA waituntil and \uC \_Select statement throughput synchronizing on a set of futures with varying wait predicates (higher is better).}
    \caption{}
        \label{f:futurePerf}
\end{figure}

This microbenchmark aims to measure the impact of various predicates on the performance of the @waituntil@ and @_Select@ statements.
This benchmark and section does not try to directly compare the @waituntil@ and @_Select@ statements since the performance of futures in \CFA and \uC differ by a significant margin, making them incomparable.
Results of this benchmark are shown in Figure~\ref{f:futurePerf}.
Each set of columns is marked with a name representing the predicate for that set of columns.
The predicate name and corresponding waituntil statement is shown below:

\begin{cfa}
#ifdef OR
waituntil( A ) { get( A ); }
or waituntil( B ) { get( B ); }
or waituntil( C ) { get( C ); }
#endif
#ifdef AND
waituntil( A ) { get( A ); }
and waituntil( B ) { get( B ); }
and waituntil( C ) { get( C ); }
#endif
#ifdef ANDOR
waituntil( A ) { get( A ); }
and waituntil( B ) { get( B ); }
or waituntil( C ) { get( C ); }
#endif
#ifdef ORAND
(waituntil( A ) { get( A ); }
or waituntil( B ) { get( B ); }) // brackets create higher precedence for or
and waituntil( C ) { get( C ); }
#endif
\end{cfa}

In Figure~\ref{f:futurePerf}, the @OR@ column for \CFA is more performant than the other \CFA predicates, likely due to the special-casing of waituntil statements with only @or@ operators.
For both \uC and \CFA the @AND@ column is the least performant, which is expected since all three futures need to be fulfilled for each statement completion, unlike any of the other operators.
Interestingly, \CFA has lower variation across predicates on the AMD (excluding the special OR case), whereas \uC has lower variation on the Intel.