source: doc/theses/colby_parsons_MMAth/text/intro.tex @ 1f10959

% ======================================================================
% ======================================================================
\chapter{Introduction}\label{s:intro}
% ======================================================================
% ======================================================================

Concurrent programs are the wild west of programming because determinism and simple ordering of program operations go out the window. 
To seize the reins and write performant and safe concurrent code, high-level concurrent-language features are needed. 
Like any other craftsmen, programmers are only as good as their tools, and concurrent tooling and features are no exception. 

This thesis presents a suite of high-level concurrent-language features implemented in the new programming-language \CFA. 
These features aim to improve the performance of concurrent programs, aid in writing safe programs, and assist user productivity by improving the ease of concurrent programming. 
The groundwork for concurrent features in \CFA was implemented by Thierry Delisle~\cite{Delisle18}, who contributed the threading system, coroutines, monitors and other tools. 
This thesis builds on top of that foundation by providing a suite of high-level concurrent features. 
The features include a @mutex@ statement, channels, a @waituntil@ statement, and an actor system. 
All of these features exist in other programming languages in some shape or form, however this thesis extends the original ideas by improving performance, productivity, and safety.

\section{The Need For Concurrent Features}
Asking a programmer to write a complex concurrent program without any concurrent language features is asking them to undertake a very difficult task.
They would only be able to rely on the atomicity that their hardware provides and would have to build up from there.
This would be like asking a programmer to write a complex sequential program only in assembly.
Both are doable, but would often be easier and less error prone with higher level tooling.

Concurrent programming has many pitfalls that are unique and do not show up in sequential code:
\begin{enumerate}
\item Deadlock, where threads cyclically wait on resources, blocking them indefinitely.
\item Livelock, where threads constantly attempt a concurrent operation unsuccessfully, resulting in no progress being made.
\item Race conditions, where thread orderings can result in differing behaviours and correctness of a program execution.
\item Starvation, where threads may be deprived of access to some shared resource due to unfairness and never make progress.
\end{enumerate}
Even with the guiding hand of concurrent tools these pitfalls can still catch unwary programmers, but good language support can prevent, detect, and mitigate these problems.

\section{A Brief Overview}

The first chapter of this thesis aims to familiarize the reader with the language \CFA.
In this chapter, syntax and features of the \CFA language that appear in this work are discussed The next chapter briefly discusses prior concurrency work in \CFA and how this work builds on top of existing features.
The remaining chapters each introduce a concurrent language feature, discuss prior related work, and present contributions which are then benchmarked against other languages and systems.
The first of these chapters discusses the @mutex@ statement, a language feature that improves ease of use and safety of lock usage.
The @mutex@ statement is compared both in terms of safety and performance with similar tools in \CC and Java.
The following chapter discusses channels, a message passing concurrency primitive that provides an avenue for safe synchronous and asynchronous communication across threads.
Channels in \CFA are compared to Go, which popularized the use of channels in modern concurrent programs.
The following chapter discusses the \CFA actor system.
The \CFA actor system is a close cousin of channels, as it also belongs to the message passing paradigm of concurrency.
However, the actor system provides a great degree of abstraction and ease of scalability, making it useful for a different range of problems than channels.
The actor system in \CFA is compared with a variety of other systems on a suite of benchmarks, where it achieves significant performance gains over other systems due to its design.
The final chapter discusses the \CFA @waituntil@ statement which provides the ability to synchronize while waiting for a resource, such as acquiring a lock, accessing a future, or writing to a channel.
The @waituntil@ statement presented provides greater flexibility and expressibility than similar features in other languages.
All in all, the features presented aim to fill in gaps in the current \CFA concurrent language support, and enable users to write a wider range of complex concurrent programs with ease.

\section{Contributions}
This work presents the following contributions:
\begin{enumerate}
\item The @mutex@ statement which:
\begin{itemize}[itemsep=0pt]
\item
provides deadlock-free multiple lock acquisition,
\item
clearly denotes lock acquisition and release,
\item
and has good performance irrespective of lock ordering.
\end{itemize}
\item Channels which:
\begin{itemize}[itemsep=0pt]
    \item
    achieves comparable performance to Go, the gold standard for concurrent channels,
    \item
    has deadlock detection,
    \item
    introduces easy-to-use exception-based @close@ semantics,
    \item
    and provides toggle-able statistics for performance tuning.
\end{itemize}
\item An in-memory actor system that:
\begin{itemize}[itemsep=0pt]
    \item
    achieves the lowest latency message send of all tested systems,
    \item
    is the first inverted actor system to introduce queue stealing,
    \item
    attains zero-victim-cost stealing through a carefully constructed stealing mechanism,
    \item
    gains performance through static-typed message sends, eliminating the need for dynamic dispatch,
    \item
    introduces the copy queue, an array based queue specialized for the actor use case to minimize calls to the memory allocator,
    \item
    has robust detection of six tricky, but common actor programming errors,
    \item
    achieves very good performance on a diverse benchmark suite compared to other actor systems,
    \item
    and provides toggle-able statistics for performance tuning.
\end{itemize}

\item A @waituntil@ statement which:
\begin{itemize}[itemsep=0pt]
    \item
    is the only known polymorphic synchronous multiplexing language feature,
    \item
    provides greater expressibility of waiting conditions than other languages,
    \item
    and achieves comparable performance to similar features in two other languages,
\end{itemize}
\end{enumerate}