source: doc/theses/colby_parsons_MMAth/text/channels.tex @ b965774

% ======================================================================
% ======================================================================
\chapter{Channels}\label{s:channels}
% ======================================================================
% ======================================================================

Most modern concurrent programming languages do not subscribe to just one style of communication among threads and provide features that support multiple approaches.
Channels are a concurrent-language feature used to perform \Newterm{message-passing concurrency}: a model of concurrency where threads communicate by sending data as messages (mostly non\-blocking) and synchronizing by receiving sent messages (blocking).
This model is an alternative to shared-memory concurrency, where threads communicate directly by changing shared state.

Channels were first introduced by Kahn~\cite{Kahn74} and extended by Hoare~\cite{CSP} (CSP).
Both papers present a pseudo (unimplemented) concurrent language where processes communicate using input/output channels to send data.
Both languages are highly restrictive.
Kahn's language restricts a reading process to only wait for data on a single channel at a time and different writing processes cannot send data on the same channel.
Hoare's language restricts both the sender and receiver to explicitly name the process that is the destination of a channel send or the source of a channel receive.
These channel semantics remove the ability to have an anonymous sender or receiver.
Additionally all channel operations in CSP are synchronous (no buffering).
Advanced channels as a programming language feature has been popularized in recent years by the language Go~\cite{Go}, which encourages the use of channels as its fundamental concurrent feature.
It was the popularity of Go channels that lead to their implementation in \CFA.
Neither Go nor \CFA channels have the restrictions of the early channel-based concurrent systems.

Other popular languages and libraries that provide channels include C++ Boost~\cite{boost:channel}, Rust~\cite{rust:channel}, Haskell~\cite{haskell:channel}, OCaml~\cite{ocaml:channel}, and Kotlin~\cite{kotlin:channel}.
Boost channels only support asynchronous (non-blocking) operations, and Rust channels are limited to only having one consumer per channel.
Haskell channels are unbounded in size, and OCaml channels are zero-size.
These restrictions in Haskell and OCaml are likely due to their functional approach, which results in them both using a list as the underlying data structure for their channel.
These languages and libraries are not discussed further, as their channel implementation is not comparable to the bounded-buffer style channels present in Go and \CFA.
Kotlin channels are comparable to Go and \CFA, but unfortunately they were not identified as a comparator until after presentation of this thesis and are omitted due to time constraints.

\section{Producer-Consumer Problem}
A channel is an abstraction for a shared-memory buffer, which turns the implementation of a channel into the producer-consumer problem.
The producer-consumer problem, also known as the bounded-buffer problem, was introduced by Dijkstra~\cite[\S~4.1]{Dijkstra65}.
In the problem, threads interact with a buffer in two ways: producing threads insert values into the buffer and consuming threads remove values from the buffer.
In general, a buffer needs protection to ensure a producer only inserts into a non-full buffer and a consumer only removes from a non-empty buffer (synchronization).
As well, a buffer needs protection from concurrent access by multiple producers or consumers attempting to insert or remove simultaneously, which is often provided by MX.

\section{Channel Size}\label{s:ChannelSize}
Channels come in three flavours of buffers:
\begin{enumerate}
\item
Zero sized implies the communication is synchronous, \ie the producer must wait for the consumer to arrive or vice versa for a value to be communicated.
\item
Fixed sized (bounded) implies the communication is mostly asynchronous, \ie the producer can proceed up to the buffer size and vice versa for the consumer with respect to removal, at which point the producer/consumer would wait.
\item
Infinite sized (unbounded) implies the communication is asymmetrically asynchronous, \ie the producer never waits but the consumer waits when the buffer is empty.
\end{enumerate}

In general, the order values are processed by the consumer does not affect the correctness of the producer-consumer problem.
For example, the buffer can be \gls{lifo}, \gls{fifo}, or prioritized with respect to insertion and removal.
However, like MX, a buffer should ensure every value is eventually removed after some reasonable bounded time (no long-term starvation).
The simplest way to prevent starvation is to implement the buffer as a queue, either with a cyclic array or linked nodes.
While \gls{fifo} is not required for producer-consumer problem correctness, it is a desired property in channels as it provides predictable and often relied upon channel ordering behaviour to users.

\section{First-Come First-Served}
As pointed out, a bounded buffer implementation often provides MX among multiple producers or consumers.
This MX should be fair among threads, independent of the \gls{fifo} buffer being fair among values.
Fairness among threads is called \gls{fcfs} and was defined by Lamport~\cite[p.~454]{Lamport74}.
\gls{fcfs} is defined in relation to a doorway~\cite[p.~330]{Lamport86II}, which is the point at which an ordering among threads can be established.
Given this doorway, a CS is said to be \gls{fcfs}, if threads access the shared resource in the order they proceed through the doorway.
A consequence of \gls{fcfs} execution is the elimination of \Newterm{barging}, where barging means a thread arrives at a CS with waiting threads, and the MX protecting the CS allows the arriving thread to enter the CS ahead of one or more of the waiting threads.

\gls{fcfs} is a fairness property that prevents unequal access to the shared resource and prevents starvation, however it comes at a cost.
Implementing an algorithm with \gls{fcfs} can lead to \Newterm{double blocking}, where arriving threads block outside the doorway waiting for a thread in the lock entry-protocol and inside the doorway waiting for a thread in the CS.
An analogue is boarding an airplane: first you wait to get through security to the departure gates (short term), and then wait again at the departure gate for the airplane (long term).
As such, algorithms that are not \gls{fcfs} (barging) can be more performant by skipping the wait for the CS and entering directly;
however, this performance gain comes by introducing unfairness with possible starvation for waiting threads.

\section{Channel Implementation}\label{s:chan_impl}
The programming languages Go, Kotlin, and Erlang provide user-level threading where the primary communication mechanism is channels.
These languages have user-level threading and preemptive scheduling, and both use channels for communication.
Go and Kotlin provide multiple homogeneous channels; each have a single associated type.
Erlang, which is closely related to actor systems, provides one heterogeneous channel per thread (mailbox) with a typed receive pattern.
Go and Kotlin encourage users to communicate via channels, but provides them as an optional language feature.
On the other hand, Erlang's single heterogeneous channel is a fundamental part of the threading system design; using it is unavoidable.
Similar to Go and Kotlin, \CFA's channels are offered as an optional language feature.

While iterating on channel implementation, experiments were conducted that varied the producer-consumer algorithm and lock type used inside the channel.
With the exception of non-\gls{fcfs} or non-\gls{fifo} algorithms, no algorithm or lock usage in the channel implementation was found to be consistently more performant that Go's choice of algorithm and lock implementation.
Performance of channels can be improved by sharding the underlying buffer \cite{Dice11}. 
However, the \gls{fifo} property is lost, which is undesirable for user-facing channels.
Therefore, the low-level channel implementation in \CFA is largely copied from the Go implementation, but adapted to the \CFA type and runtime systems.
As such the research contributions added by \CFA's channel implementation lie in the realm of safety and productivity features.

The Go channel implementation utilizes cooperation among threads to achieve good performance~\cite{go:chan}.
This cooperation only occurs when producers or consumers need to block due to the buffer being full or empty.
After a producer blocks it must wait for a consumer to signal it and vice versa.
The consumer or producer that signals a blocked thread is called the signalling thread.
In these cases, a blocking thread stores their relevant data in a shared location and the signalling thread completes the blocking thread's operation before waking them;
\ie the blocking thread has no work to perform after it unblocks because the signalling threads has done this work.
This approach is similar to wait morphing for locks~\cite[p.~82]{Butenhof97} and improves performance in a few ways.
First, each thread interacting with the channel only acquires and releases the internal channel lock once.
As a result, contention on the internal lock is decreased; only entering threads compete for the lock since unblocking threads do not reacquire the lock.
The other advantage of Go's wait-morphing approach is that it eliminates the need to wait for signalled threads to run.
Note that the property of acquiring/releasing the lock only once can also be achieved with a different form of cooperation, called \Newterm{baton passing}.
Baton passing occurs when one thread acquires a lock but does not release it, and instead signals a thread inside the critical section, conceptually ``passing'' the mutual exclusion from the signalling thread to the signalled thread.
The baton-passing approach has threads cooperate to pass mutual exclusion without additional lock acquires or releases;
the wait-morphing approach has threads cooperate by completing the signalled thread's operation, thus removing a signalled thread's need for mutual exclusion after unblocking.
While baton passing is useful in some algorithms, it results in worse channel performance than the Go approach.
In the baton-passing approach, all threads need to wait for the signalled thread to unblock and run before other operations on the channel can proceed, since the signalled thread holds mutual exclusion;
in the wait-morphing approach, since the operation is completed before the signal, other threads can continue to operate on the channel without waiting for the signalled thread to run.

In this work, all channel sizes \see{Sections~\ref{s:ChannelSize}} are implemented with bounded buffers.
However, only non-zero-sized buffers are analysed because of their complexity and higher usage.

\section{Safety and Productivity}
Channels in \CFA come with safety and productivity features to aid users.
The features include the following.

\begin{itemize}
\item Toggle-able statistic collection on channel behaviour that count channel and blocking operations.
Tracking blocking operations helps illustrate usage for tuning the channel size, where the aim is to reduce blocking.

\item Deadlock detection on channel deallocation.
If threads are blocked inside a channel when it terminates, this case is detected and the user is informed, as this can cause a deadlock.

\item A @flush@ routine that delivers copies of an element to all waiting consumers, flushing the buffer.
Programmers use this mechanism to broadcast a sentinel value to multiple consumers.
Additionally, the @flush@ routine is more performant than looping around the @insert@ operation since it can deliver the elements without having to reacquire mutual exclusion for each element sent.

\item Go-style @?<<?@ shorthand operator for inserting and removing.
\begin{cfa}
channel(int) chan;
int i = 2;
chan << i;                      $\C{// insert i into chan}$
i << chan;              $\C{// remove element from chan into i}$
\end{cfa}
\end{itemize}

\subsection{Toggle-able Statistics}
As discussed, a channel is a concurrent layer over a bounded buffer.
To achieve efficient buffering, users should aim for as few blocking operations on a channel as possible.
Mechanisms to reduce blocking are: change the buffer size, shard a channel into multiple channels, or tweak the number of producer and consumer threads.
For users to be able to make informed decisions when tuning channel usage, toggle-able channel statistics are provided.
The statistics are toggled on during the \CFA build by defining the @CHAN_STATS@ macro, which guarantees zero cost when not using this feature.
When statistics are turned on, four counters are maintained per channel, two for inserting (producers) and two for removing (consumers).
The two counters per type of operation track the number of blocking operations and total operations.
In the channel destructor, the counters are printed out aggregated and also per type of operation.
An example use case is noting that producer inserts are blocking often while consumer removes do not block often.
This information can be used to increase the number of consumers to decrease the blocking producer operations, thus increasing the channel throughput.
Whereas, increasing the channel size in this scenario is unlikely to produce a benefit because the consumers can never keep up with the producers.

\subsection{Deadlock Detection}
The deadlock detection in the \CFA channels is fairly basic but detects a very common channel mistake during termination.
That is, it detects the case where threads are blocked on the channel during channel deallocation.
This case is guaranteed to deadlock since there are no other threads to supply or consume values needed by the waiting threads.
Only if a user maintained a separate reference to the blocked threads and manually unblocks them outside the channel could the deadlock be avoid.
However, without special semantics, this unblocking would generate other runtime errors where the unblocked thread attempts to access non-existing channel data or even a deallocated channel.
More robust deadlock detection needs to be implemented separate from channels since it requires knowledge about the threading system and other channel/thread state.

\subsection{Program Shutdown}
Terminating concurrent programs is often one of the most difficult parts of writing concurrent code, particularly if graceful termination is needed.
Graceful termination can be difficult to achieve with synchronization primitives that need to be handled carefully during shutdown.
It is easy to deadlock during termination if threads are left behind on synchronization primitives.
Additionally, most synchronization primitives are prone to \gls{toctou} issues where there is race between one thread checking the state of a concurrent object and another thread changing the state.
\gls{toctou} issues with synchronization primitives often involve a race between one thread checking the primitive for blocked threads and another thread blocking on it.
Channels are a particularly hard synchronization primitive to terminate since both sending and receiving to/from a channel can block.
Thus, improperly handled \gls{toctou} issues with channels often result in deadlocks as threads performing the termination may end up unexpectedly blocking in their attempt to help other threads exit the system.

\subsubsection{Go Channel Close}
Go channels provide a set of tools to help with concurrent shutdown~\cite{go:chan} using a @close@ operation in conjunction with the \Go{select} statement.
The \Go{select} statement is discussed in \ref{s:waituntil}, where \CFA's @waituntil@ statement is compared with the Go \Go{select} statement.

The @close@ operation on a channel in Go changes the state of the channel.
When a channel is closed, sends to the channel panic along with additional calls to @close@.
Receives are handled differently. 
Receivers (consumers) never block on a closed channel and continue to remove elements from the channel.
Once a channel is empty, receivers can continue to remove elements, but receive the zero-value version of the element type.
To avoid unwanted zero-value elements, Go provides the ability to iterate over a closed channel to remove the remaining elements.
These Go design choices enforce a specific interaction style with channels during termination: careful thought is needed to ensure additional @close@ calls do not occur and no sends occur after a channel is closed.
These design choices fit Go's paradigm of error management, where users are expected to explicitly check for errors, rather than letting errors occur and catching them.
If errors need to occur in Go, return codes are used to pass error information up call levels.
Note that panics in Go can be caught, but it is not the idiomatic way to write Go programs.

While Go's channel-closing semantics are powerful enough to perform any concurrent termination needed by a program, their lack of ease of use leaves much to be desired.
Since both closing and sending panic once a channel is closed, a user often has to synchronize the senders (producers) before the channel can be closed to avoid panics.
However, in doing so it renders the @close@ operation nearly useless, as the only utilities it provides are the ability to ensure receivers no longer block on the channel and receive zero-valued elements.
This functionality is only useful if the zero-typed element is recognized as a sentinel value, but if another sentinel value is necessary, then @close@ only provides the non-blocking feature.
To avoid \gls{toctou} issues during shutdown, a busy wait with a \Go{select} statement is often used to add or remove elements from a channel.
Hence, due to Go's asymmetric approach to channel shutdown, separate synchronization between producers and consumers of a channel has to occur during shutdown.

\subsubsection{\CFA Channel Close}
\CFA channels have access to an extensive exception handling mechanism~\cite{Beach21}.
As such \CFA uses an exception-based approach to channel shutdown that is symmetric for both producers and consumers, and supports graceful shutdown.

Exceptions in \CFA support both termination and resumption.
\Newterm{Termination exception}s perform a dynamic call that unwinds the stack preventing the exception handler from returning to the raise point, such as in \CC, Python and Java.
\Newterm{Resumption exception}s perform a dynamic call that does not unwind the stack allowing the exception handler to return to the raise point.
In \CFA, if a resumption exception is not handled, it is reraised as a termination exception.
This mechanism is used to create a flexible and robust termination system for channels.

When a channel in \CFA is closed, all subsequent calls to the channel raise a resumption exception at the caller.
If the resumption is handled, the caller attempts to complete the channel operation.
However, if the channel operation would block, a termination exception is thrown.
If the resumption is not handled, the exception is rethrown as a termination.
These termination exceptions allow for non-local transfer that is used to great effect to eagerly and gracefully shut down a thread.
When a channel is closed, if there are any blocked producers or consumers inside the channel, they are woken up and also have a resumption thrown at them.
The resumption exception, @channel_closed@, has internal fields to aid in handling the exception.
The exception contains a pointer to the channel it is thrown from and a pointer to a buffer element.
For exceptions thrown from @remove@, the buffer element pointer is null.
For exceptions thrown from @insert@, the element pointer points to the buffer element that the thread attempted to insert.
Utility routines @bool is_insert( channel_closed & e );@ and @bool is_remove( channel_closed & e );@ are provided for convenient checking of the element pointer.
This element pointer allows the handler to know which operation failed and also allows the element to not be lost on a failed insert since it can be moved elsewhere in the handler.
Furthermore, due to \CFA's powerful exception system, this data can be used to choose handlers based on which channel and operation failed.
For example, exception handlers in \CFA have an optional predicate which can be used to trigger or skip handlers based on the content of the matching exception.
It is worth mentioning that using exceptions for termination may incur a larger performance cost than the Go approach.
However, this should not be an issue, since termination is rarely on the fast-path of an application.
In contrast, ensuring termination can be easily implemented correctly is the aim of the exception approach.

\section{\CFA / Go channel Examples}
To highlight the differences between \CFA's and Go's close semantics, two examples are presented.
The first example is a simple shutdown case, where there are producer threads and consumer threads operating on a channel for a fixed duration.
Once the duration ends, producers and consumers terminate immediately leaving unprocessed elements in the channel.
The second example extends the first by requiring the channel to be empty after shutdown.
Both the first and second example are shown in Figure~\ref{f:ChannelTermination}.

\begin{figure}
\centering

\begin{lrbox}{\myboxA}
\begin{Golang}[aboveskip=0pt,belowskip=0pt]
var channel chan int = make( chan int, 128 )
var prodJoin chan int = make( chan int, 4 )
var consJoin chan int = make( chan int, 4 )
var cons_done, prod_done bool = false, false;
func producer() {
        for {
                if prod_done { break }
                channel <- 5
        }
        prodJoin <- 0 // synch with main thd
}

func consumer() {
        for {
                if cons_done { break }
                <- channel
        }
        consJoin <- 0 // synch with main thd
}


func main() {
        for j := 0; j < 4; j++ { go consumer() }
        for j := 0; j < 4; j++ { go producer() }
        time.Sleep( time.Second * 10 )
        prod_done = true
        for j := 0; j < 4 ; j++ { <- prodJoin }
        cons_done = true
        close(channel) // ensure no cons deadlock
        @for elem := range channel {@
                // process leftover values
        @}@
        for j := 0; j < 4; j++ { <- consJoin }
}
\end{Golang}
\end{lrbox}

\begin{lrbox}{\myboxB}
\begin{cfa}[aboveskip=0pt,belowskip=0pt]
channel( int ) chan{ 128 };
thread Consumer {};
thread Producer {};

void main( Producer & this ) {
        try {
                for ()
                        chan << 5;
        } catch( channel_closed * ) {
                // unhandled resume or full
        }
}
void main( Consumer & this ) {
        int i;
        try {
                for () { i << chan; }
        @} catchResume( channel_closed * ) {@
                // handled resume => consume from chan
        } catch( channel_closed * ) {
                // empty or unhandled resume
        }
}
int main() {
        Consumer c[4];
        Producer p[4];
        sleep( 10`s );
        close( chan );
}






\end{cfa}
\end{lrbox}

\subfloat[Go style]{\label{l:go_chan_term}\usebox\myboxA}
\hspace*{3pt}
\vrule
\hspace*{3pt}
\subfloat[\CFA style]{\label{l:cfa_chan_term}\usebox\myboxB}
\caption{Channel Termination Examples 1 and 2. Code specific to example 2 is highlighted.}
\label{f:ChannelTermination}
\end{figure}

Figure~\ref{l:go_chan_term} shows the Go solution.
Since some of the elements being passed through the channel are zero-valued, closing the channel in Go does not aid in communicating shutdown.
Instead, a different mechanism to communicate with the consumers and producers needs to be used.
Flag variables are common in Go-channel shutdown-code to avoid panics on a channel, meaning the channel shutdown has to be communicated with threads before it occurs.
Hence, the two flags @cons_done@ and @prod_done@ are used to communicate with the producers and consumers, respectively.
Furthermore, producers and consumers need to shutdown separately to ensure that producers terminate before the channel is closed to avoid panicking, and to avoid the case where all the consumers terminate first, which can result in a deadlock for producers if the channel is full.
The producer flag is set first;
then after all producers terminate, the consumer flag is set and the channel is closed leaving elements in the buffer.
To purge the buffer, a loop is added (red) that iterates over the closed channel to process any remaining values.

Figure~\ref{l:cfa_chan_term} shows the \CFA solution.
Here, shutdown is communicated directly to both producers and consumers via the @close@ call.
A @Producer@ thread knows to stop producing when the @insert@ call on a closed channel raises exception @channel_closed@.
If a @Consumer@ thread ignores the first resumption exception from the @close@, the exception is reraised as a termination exception and elements are left in the buffer.
If a @Consumer@ thread handles the resumptions exceptions (red), control returns to complete the remove.
A @Consumer@ thread knows to stop consuming after all elements of a closed channel are removed and the consumer would block, which causes a termination raise of @channel_closed@.
The \CFA semantics allow users to communicate channel shutdown directly through the channel, without having to share extra state between threads.
Additionally, when the channel needs to be drained, \CFA provides users with easy options for processing the leftover channel values in the main thread or in the consumer threads.

Figure~\ref{f:ChannelBarrierTermination} shows a final shutdown example using channels to implement a barrier.
A Go and \CFA style solution are presented but both are implemented using \CFA syntax so they can be easily compared.
Implementing a barrier is interesting because threads are both producers and consumers on the barrier-internal channels, @entryWait@ and @barWait@.
The outline for the barrier implementation starts by initially filling the @entryWait@ channel with $N$ tickets in the barrier constructor, allowing $N$ arriving threads to remove these values and enter the barrier.
After @entryWait@ is empty, arriving threads block when removing.
However, the arriving threads that entered the barrier cannot leave the barrier until $N$ threads have arrived.
Hence, the entering threads block on the empty @barWait@ channel until the $N$th arriving thread inserts $N-1$ elements into @barWait@ to unblock the $N-1$ threads calling @remove@.
The race between these arriving threads blocking on @barWait@ and the $N$th thread inserting values into @barWait@ does not affect correctness;
\ie an arriving thread may or may not block on channel @barWait@ to get its value.
Finally, the last thread to remove from @barWait@ with ticket $N-2$, refills channel @entryWait@ with $N$ values to start the next group into the barrier.

Now, the two channels makes termination synchronization between producers and consumers difficult.
Interestingly, the shutdown details for this problem are also applicable to other problems with threads producing and consuming from the same channel.
The Go-style solution cannot use the Go @close@ call since all threads are both potentially producers and consumers, causing panics on close to be unavoidable without complex synchronization.
As such in Figure \ref{l:go_chan_bar}, a flush routine is needed to insert a sentinel value, @-1@, to inform threads waiting in the buffer they need to leave the barrier.
This sentinel value has to be checked at two points along the fast-path and sentinel values daisy-chained into the buffers.
Furthermore, an additional flag @done@ is needed to communicate to threads once they have left the barrier that they are done.
Also note that in the Go version~\ref{l:go_chan_bar}, the size of the barrier channels has to be larger than in the \CFA version to ensure that the main thread does not block when attempting to clear the barrier.
For The \CFA solution~\ref{l:cfa_chan_bar}, the barrier shutdown results in an exception being thrown at threads operating on it, to inform waiting threads they must leave the barrier.
This avoids the need to use a separate communication method other than the barrier, and avoids extra conditional checks on the fast path of the barrier implementation.

\begin{figure}
\centering

\begin{lrbox}{\myboxA}
\begin{cfa}[aboveskip=0pt,belowskip=0pt]
struct barrier {
        channel( int ) barWait, entryWait;
        int size;
};
void ?{}( barrier & this, int size ) with(this) {
        barWait{size + 1};   entryWait{size + 1};
        this.size = size;
        for ( i; size )
                insert( entryWait, i );
}
void wait( barrier & this ) with(this) {
        int ticket = remove( entryWait );
        @if ( ticket == -1 ) { insert( entryWait, -1 ); return; }@
        if ( ticket == size - 1 ) {
                for ( i; size - 1 )
                        insert( barWait, i );
                return;
        }
        ticket = remove( barWait );
        @if ( ticket == -1 ) { insert( barWait, -1 ); return; }@
        if ( size == 1 || ticket == size - 2 ) { // last ?
                for ( i; size )
                        insert( entryWait, i );
        }
}
void flush(barrier & this) with(this) {
        @insert( entryWait, -1 );   insert( barWait, -1 );@
}
enum { Threads = 4 };
barrier b{Threads};
@bool done = false;@
thread Thread {};
void main( Thread & this ) {
        for () {
          @if ( done ) break;@
                wait( b );
        }
}
int main() {
        Thread t[Threads];
        sleep(10`s);
        done = true;
        flush( b );
} // wait for threads to terminate
\end{cfa}
\end{lrbox}

\begin{lrbox}{\myboxB}
\begin{cfa}[aboveskip=0pt,belowskip=0pt]
struct barrier {
        channel( int ) barWait, entryWait;
        int size;
};
void ?{}( barrier & this, int size ) with(this) {
        barWait{size};   entryWait{size};
        this.size = size;
        for ( i; size )
                insert( entryWait, i );
}
void wait( barrier & this ) with(this) {
        int ticket = remove( entryWait );

        if ( ticket == size - 1 ) {
                for ( i; size - 1 )
                        insert( barWait, i );
                return;
        }
        ticket = remove( barWait );

        if ( size == 1 || ticket == size - 2 ) { // last ?
                for ( i; size )
                        insert( entryWait, i );
        }
}
void flush(barrier & this) with(this) {
        @close( barWait );   close( entryWait );@
}
enum { Threads = 4 };
barrier b{Threads};

thread Thread {};
void main( Thread & this ) {
        @try {@
                for ()
                        wait( b );
        @} catch ( channel_closed * ) {}@
}
int main() {
        Thread t[Threads];
        sleep(10`s);

        flush( b );
} // wait for threads to terminate
\end{cfa}
\end{lrbox}

\subfloat[Go style]{\label{l:go_chan_bar}\usebox\myboxA}
\hspace*{3pt}
\vrule
\hspace*{3pt}
\subfloat[\CFA style]{\label{l:cfa_chan_bar}\usebox\myboxB}
\caption{Channel Barrier Termination}
\label{f:ChannelBarrierTermination}
\end{figure}

\section{Performance}

Given that the base implementation of the \CFA channels is very similar to the Go implementation, this section aims to show the performance of the two implementations are comparable.
The microbenchmark for the channel comparison is similar to Figure~\ref{f:ChannelTermination}, where the number of threads and processors is set from the command line.
The processors are divided equally between producers and consumers, with one producer or consumer owning each core.
The number of cores is varied to measure how throughput scales.

The results of the benchmark are shown in Figure~\ref{f:chanPerf}.
The performance of Go and \CFA channels on this microbenchmark is comparable.
Note that the performance should decline as the number of cores increases as the channel operations occur in a critical section, so increasing cores results in higher contention with no increase in parallelism.

The performance of \CFA and Go's shutdown mechanisms is not measured, as shutdown is an exceptional case that does not occur frequently in most programs. Additionally, it is difficult to measure channel shutdown performance; threads need to be synchronized between each subsequent shutdown, which is likely more expensive than the shutdown mechanism itself.

\begin{figure}
        \centering
        \subfloat[AMD Channel Benchmark]{
                \resizebox{0.5\textwidth}{!}{\input{figures/nasus_Channel_Contention.pgf}}
                \label{f:chanAMD}
        }
        \subfloat[Intel Channel Benchmark]{
                \resizebox{0.5\textwidth}{!}{\input{figures/pyke_Channel_Contention.pgf}}
                \label{f:chanIntel}
        }
        \caption{The channel contention benchmark comparing \CFA and Go channel throughput (higher is better).}
        \label{f:chanPerf}
\end{figure}

% Local Variables: %
% tab-width: 4 %
% End: %