Ignore:
Timestamp:
Jun 14, 2023, 11:35:49 AM (17 months ago)
Author:
caparsons <caparson@…>
Branches:
master
Children:
7e4bd9b6
Parents:
32a4f3e (diff), 8f557161 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/colby_parsons_MMAth/text/actors.tex

    r32a4f3e r5668740  
    66
    77% C_TODO: add citations throughout chapter
    8 Actors are a concurrent feature that abstracts threading away from a user, and instead provides \gls{actor}s and messages as building blocks for concurrency.
    9 Actors are another message passing concurrency feature, similar to channels, but with more abstraction.
    10 Actors enter the realm of what is called \gls{impl_concurrency}, where programmers can write concurrent code without having to worry about explicit thread synchronization and mutual exclusion.
    11 The study of actors can be broken into two concepts, the \gls{actor_model}, which describes the model of computation and the \gls{actor_system}, which refers to the implementation of the model in practice.
     8Actors are an indirect concurrent feature that abstracts threading away from a programmer, and instead provides \gls{actor}s and messages as building blocks for concurrency, where message passing means there is no shared data to protect, making actors amenable in a distributed environment.
     9Actors are another message passing concurrency feature, similar to channels but with more abstraction, and are in the realm of \gls{impl_concurrency}, where programmers write concurrent code without dealing with explicit thread create or interaction.
     10The study of actors can be broken into two concepts, the \gls{actor_model}, which describes the model of computation and the \gls{actor_system}, which refers to the implementation of the model.
    1211Before discussing \CFA's actor system in detail, it is important to first describe the actor model, and the classic approach to implementing an actor system.
    1312
    14 \section{The Actor Model}
    15 The actor model is a paradigm of concurrent computation, where tasks are broken into units of work that are distributed to actors in the form of messages \cite{Hewitt73}.
    16 Actors execute asynchronously upon receiving a message and can modify their own state, make decisions, spawn more actors, and send messages to other actors.
    17 The actor model is an implicit model of concurrency.
    18 As such, one strength of the actor model is that it abstracts away many considerations that are needed in other paradigms of concurrent computation.
    19 Mutual exclusion, and locking are rarely relevant concepts to users of an actor model, as actors typically operate on local state.
     13\section{Actor Model}
     14The actor model is a concurrent paradigm where computation is broken into units of work called actors, and the data for computation is distributed to actors in the form of messages~\cite{Hewitt73}.
     15An actor is composed of a \Newterm{mailbox} (message queue) and a set of \Newterm{behaviours} that receive from the mailbox to perform work.
     16Actors execute asynchronously upon receiving a message and can modify their own state, make decisions, spawn more actors, and send messages to other actors.
     17Because the actor model is implicit concurrency, its strength is that it abstracts away many details and concerns needed in other concurrent paradigms.
     18For example, mutual exclusion and locking are rarely relevant concepts in an actor model, as actors typically only operate on local state.
     19
     20An actor does not have a thread.
     21An actor is executed by an underlying \Newterm{executor} (kernel thread-pool) that fairly invokes each actor, where an actor invocation processes one or more messages from its mailbox.
     22The default number of executor threads is often proportional to the number of computer cores to achieve good performance.
     23An executor is often tunable with respect to the number of kernel threads and its scheduling algorithm, which optimize for specific actor applications and workloads \see{end of Section~\ref{s:CFAActorSyntax}}.
    2024
    2125\section{Classic Actor System}
    22 An implementation of the actor model with a community of actors is called an actor system.
    23 Actor systems largely follow the actor model, but differ in some ways.
    24 While the definition of the actor model provides no restrictions on message ordering, actor systems tend to guarantee that messages sent from a given actor $i$ to actor $j$ will arrive at actor $j$ in the order they were sent.
    25 Another way an actor system varies from the model is that actors are often allowed to access non-local state.
    26 When this occurs it can complicate the implementation as this will break any mutual exclusion guarantees given by accessing only local state.
     26An implementation of the actor model with a community of actors is called an actor system.
     27Actor systems largely follow the actor model, but can differ in some ways.
     28While the semantics of message \emph{send} is asynchronous, the implementation may be synchronous or a combination.
     29The default semantics for message \emph{receive} is FIFO, so an actor receives messages from its mailbox in temporal (arrival) order;
     30however, messages sent among actors arrive in any order.
     31Some actor systems provide priority-based mailboxes and/or priority-based message-selection within a mailbox, where custom message dispatchers search among or within a mailbox(es) with a predicate for specific kinds of actors and/or messages.
     32Some actor systems provide a shared mailbox where multiple actors receive from a common mailbox~\cite{Akka}, which is contrary to the no-sharing design of the basic actor-model (and requires additional locking).
     33For non-FIFO service, some notion of fairness (eventual progress) must exist, otherwise messages have a high latency or starve, \ie never received.
     34Finally, some actor systems provide multiple typed-mailboxes, which then lose the actor-\lstinline{become} mechanism (see Section~\ref{s:SafetyProductivity}).
     35%While the definition of the actor model provides no restrictions on message ordering, actor systems tend to guarantee that messages sent from a given actor $i$ to actor $j$ will arrive at actor $j$ in the order they were sent.
     36Another way an actor system varies from the model is allowing access to shared global-state.
     37When this occurs, it complicates the implementation as this breaks any implicit mutual-exclusion guarantees when only accessing local-state.
    2738
    2839\begin{figure}
    2940\begin{tabular}{l|l}
    30 \subfloat[Actor-centric system]{\label{f:standard_actor}\input{diagrams/standard_actor.tikz}} & 
    31 \subfloat[Message-centric system]{\label{f:inverted_actor}\raisebox{.1\height}{\input{diagrams/inverted_actor.tikz}}} 
     41\subfloat[Actor-centric system]{\label{f:standard_actor}\input{diagrams/standard_actor.tikz}} &
     42\subfloat[Message-centric system]{\label{f:inverted_actor}\raisebox{.1\height}{\input{diagrams/inverted_actor.tikz}}}
    3243\end{tabular}
    3344\caption{Classic and inverted actor implementation approaches with sharded queues.}
    … …  
    3546
    3647\section{\CFA Actors}
    37 Actor systems \cite{} have often been implemented as an actor-centric system.
    38 As such they are constructed as a set of actors that are scheduled and run on some underlying threads.
    39 Each actor has their own queue for receiving messages, sometimes called a mailbox.
    40 When they receive messages in their mailbox, actors are moved from idle to ready queues and then scheduled on a thread to run their unit of work.
    41 This approach can be implemented with a global queue of actors, but is often implemented as each worker thread owning a queue of actors.
    42 This is known as sharding the actor queue, which is done to decrease contention across worker threads.
    43 A diagram of an actor-centric system with a sharded actor queue is shown in Figure \ref{f:standard_actor}.
     48Figure~\ref{f:standard_actor} shows an actor system designed as \Newterm{actor-centric}, where a set of actors are scheduled and run on underlying executor threads~\cite{CAF,Akka,ProtoActor}.
     49The simplest design has a single global queue of actors accessed by the executor threads, but this approach results in high contention as both ends of the queue by the executor threads.
     50The more common design is to \Newterm{shard} the single queue among the executor threads, where actors are permanently assigned or can float among the queues.
     51Sharding significantly decreases contention among executor threads adding and removing actors to/from a queue.
     52Finally, each actor has a receive queue of messages (mailbox), which is a single consumer, multi-producer queue, \ie only the actor removes from the mailbox but multiple actors can attach messages.
     53When an actor receives a message in its mailbox, the actor is marked ready and scheduled by a thread to run the actor's current work unit on the message(s).
    4454
    4555% cite parallel theatre and our paper
    46 The actor system in \CFA is instead message-centric, an uses what is called an inverted actor system \cite{}.
    47 In this inverted actor system instead of each worker thread owning a queue of actors, they each own a queue of messages.
    48 This system is called inverted since in this scheme, actors belong to a message queue, whereas in the classic approach a message queue belongs to each actor.
    49 Since multiple actors belong to each message queue, messages to each actor are interleaved in the queue.
    50 In this scheme work is consumed from their queue and executed by underlying threads.
    51 In High-Performance Extended Actors \cite{} this inverted model is taken a step further and the message queues are sharded, so that each worker now instead owns a set of queues.
    52 A diagram of an inverted actor scheme with a sharded message queue is shown in Figure \ref{f:inverted_actor}.
    53 The arrows from the message queues to the actors in the diagram indicate interleaved messages addressed to each actor.
    54 
    55 The actor system in \CFA builds on top of the architecture laid out in High-Performance Extended Actors \cite{} and adds the following contributions:
    56 
     56Figure \ref{f:inverted_actor} shows an actor system designed as \Newterm{message-centric}, where a set of messages are scheduled and run on underlying executor threads~\cite{uC++,Nigro21}.
     57Again, the simplest design has a single global queue of messages accessed by the executor threads, but this approach has the same contention problem by the executor threads.
     58Therefore, the messages (mailboxes) are sharded and executor threads schedule each message, which points to its corresponding actor.
     59Here, an actor's messages are permanently assigned to one queue to ensure FIFO receiving and/or reduce searching for specific actor/messages.
     60Since multiple actors belong to each message queue, actor messages are interleaved on a queue.
     61This design is \Newterm{inverted} because actors belong to a message queue, whereas in the classic approach a message queue belongs to each actor.
     62% In this inverted actor system instead of each executor threads owning a queue of actors, they each own a queue of messages.
     63% In this scheme work is consumed from their queue and executed by underlying threads.
     64The inverted model can be taken a step further by sharding the message queues for each executor threads, so each executor thread owns a set of queues and cycles through them.
     65Again, this extra level of sharding is to reduce queue contention.
     66% The arrows from the message queues to the actors in the diagram indicate interleaved messages addressed to each actor.
     67
     68The actor system in \CFA uses a message-centric design, adopts several features from my prior actor work in \uC~\cite{}, and adds the following contributions related to \CFA:
    5769\begin{enumerate}[topsep=5pt,itemsep=3pt,parsep=0pt]
    5870\item
    59 Provides insight into the impact of envelope allocation in actor systems.
    60 In all actor systems dynamic allocation is needed to ensure that the lifetime of a unit of work persists from its creation until the unit of work is executed.
    61 This allocation is often called an envelope as it "packages" the information needed to run the unit of work, alongside any other information needed to send the unit of work, such as an actor's address or link fields for a list.
    62 This dynamic allocation occurs once per message sent. 
    63 This is a large source of contention on the memory allocator since all these allocations occur concurrently.
    64 A novel data structure is used to consolidate allocations to improve performance by minimizing contention on the allocator.
    65 
    66 \item
    67 Introduces work stealing in the inverted actor system.
    68 Work stealing in actor-centric systems tends to involve stealing one or more actors.
    69 In the inverted system the notion of stealing queues is introduced.
    70 The queue stealing is implemented such that the act of stealing work does not contend with non-stealing actors that are saturated with work.
    71 
    72 \item
    73 Introduces and evaluates a timestamp based work stealing heuristic with the goal of maintaining non-workstealing performance in work-saturated workloads, and improving performance on unbalanced workloads.
    74 
    75 \item
    76 Improves performance of the inverted actor system using multiple approaches to minimize contention on queues, such as queue gulping and avoiding atomic operations.
    77 
    78 \item
    79 Provides a suite of safety and productivity features including static-typing, detection of erroneous message sends, statistics tracking, and more.
     71Provide insight into the impact of envelope allocation in actor systems.
     72In all actor systems, dynamic allocation is needed to ensure the lifetime of a unit of work persists from its creation until the unit of work is executed.
     73This allocation is often called an \Newterm{envelope} as it ``packages'' the information needed to run the unit of work, alongside any other information needed to send the unit of work, such as an actor's address or link fields.
     74This dynamic allocation occurs once per message sent.
     75Unfortunately, the high rate of message sends in an actor system results in significant contention on the memory allocator.
     76A novel data structure is introduced to consolidate allocations to improve performance by minimizing allocator contention.
     77
     78\item
     79Improve performance of the inverted actor system using multiple approaches to minimize contention on queues, such as queue gulping and avoiding atomic operations.
     80
     81\item
     82Introduce work stealing in the inverted actor system.
     83Work stealing in an actor-centric system involves stealing one or more actors among executor threads.
     84In the inverted system, the notion of stealing message queues is introduced.
     85The queue stealing is implemented such that the act of stealing work does not contend with non-stealing executor threads running actors.
     86
     87\item
     88Introduce and evaluate a timestamp-based work-stealing heuristic with the goal of maintaining non-workstealing performance in work-saturated workloads and improving performance on unbalanced workloads.
     89
     90\item
     91Provide a suite of safety and productivity features including static-typing, detection of erroneous message sends, statistics tracking, and more.
    8092\end{enumerate}
    8193
    82 \section{\CFA Actor Syntax}
    83 \CFA is not an object oriented language and it does not have run-time type information (RTTI).
    84 As such all message sends and receives between actors occur using exact type matching.
    85 To use actors in \CFA you must \code{\#include <actors.hfa>}.
    86 To create an actor type one must define a struct which inherits from the base \code{actor} struct via the \code{inline} keyword.
    87 This is the Plan-9 C-style nominal inheritance discussed in Section \ref{s:poly}.
    88 Similarly to create a message type a user must define a struct which \code{inline}'s the base \code{message} struct.
    89 
    90 \begin{cfa}
    91 struct derived_actor {
    92         inline actor;      // Plan-9 C inheritance
    93 };
    94 void ?{}( derived_actor & this ) { // Default ctor
    95         ((actor &)this){};  // Call to actor ctor
    96 }
    97 
    98 struct derived_msg {
    99         inline message;  // Plan-9 C nominal inheritance
    100         char word[12];
    101 };
    102 void ?{}( derived_msg & this, char * new_word ) { // Overloaded ctor
    103         ((message &) this){ Nodelete }; // Passing allocation to ctor
    104         strcpy(this.word, new_word);
    105 }
    106 
    107 Allocation receive( derived_actor & receiver, derived_msg & msg ) {
    108         printf("The message contained the string: %s\n", msg.word);
    109         return Finished; // Return finished since actor is done
    110 }
    111 
    112 int main() {
    113         start_actor_system(); // Sets up executor
    114         derived_actor my_actor;         
    115         derived_msg my_msg{ "Hello World" }; // Constructor call
    116         my_actor << my_msg;   // Send message via left shift operator
    117         stop_actor_system(); // Waits until actors are finished
    118         return 0;
     94\section{\CFA Actor Syntax}\label{s:CFAActorSyntax}
     95\CFA is not an object oriented language and it does not have \gls{rtti}.
     96As such, all message sends and receives among actors can only occur using static type-matching, as in Typed-Akka~\cite{AkkaTyped}.
     97Figure~\ref{f:BehaviourStyles} contrasts dynamic and static type-matching.
     98Figure~\ref{l:dynamic_style} shows the dynamic style with a heterogeneous message receive and an indirect dynamic type-discrimination for message processing.
     99Figure~\ref{l:static_style} shows the static style with a homogeneous message receive and a direct static type-discrimination for message processing.
     100The static-typing style is safer because of the static check and faster because there is no dynamic type-discrimination.
     101The dynamic-typing style is more flexible because multiple kinds of messages can be handled in a behaviour condensing the processing code.
     102
     103\begin{figure}
     104\centering
     105
     106\begin{lrbox}{\myboxA}
     107\begin{cfa}[morekeywords=case]
     108allocation receive( message & msg ) {
     109        case( @msg_type1@, msg ) {      // discriminate type
     110                ... msg_d-> ...;        // msg_type1 msg_d
     111        } else case( @msg_type2@, msg ) {
     112                ... msg_d-> ...;        // msg_type2 msg_d
     113        ...
    119114}
    120115\end{cfa}
    121 
    122 The above code is a simple actor program in \CFA.
    123 There is one derived actor type and one derived message type.
    124 A single message containing a string is sent from the program main to an actor.
    125 Key things to highlight include the \code{receive} signature, and calls to \code{start_actor_system}, and \code{stop_actor_system}.
    126 To define a behaviour for some derived actor and derived message type, one must declare a routine with the signature:
     116\end{lrbox}
     117
     118\begin{lrbox}{\myboxB}
    127119\begin{cfa}
    128 Allocation receive( derived_actor & receiver, derived_msg & msg )
     120allocation receive( @msg_type1@ & msg ) {
     121        ... msg ...;
     122}
     123allocation receive( @msg_type2@ & msg ) {
     124        ... msg ...;
     125}
     126...
    129127\end{cfa}
    130 Where \code{derived_actor} and \code{derived_msg} can be any derived actor and derived message types respectively.
    131 The return value of \code{receive} must be a value from the \code{Allocation} enum:
     128\end{lrbox}
     129\subfloat[dynamic typing]{\label{l:dynamic_style}\usebox\myboxA}
     130\hspace*{10pt}
     131\vrule
     132\hspace*{10pt}
     133\subfloat[static typing]{\label{l:static_style}\usebox\myboxB}
     134\caption{Behaviour Styles}
     135\label{f:BehaviourStyles}
     136\end{figure}
     137
     138\begin{figure}
     139\centering
     140
    132141\begin{cfa}
    133 enum Allocation { Nodelete, Delete, Destroy, Finished };
     142// actor
     143struct my_actor {
     144        @inline actor;@                                                 $\C[3.25in]{// Plan-9 C inheritance}$
     145};
     146// messages
     147struct str_msg {
     148        @inline message;@                                               $\C{// Plan-9 C nominal inheritance}$
     149        char str[12];
     150};
     151void ?{}( str_msg & this, char * str ) { strcpy( this.str, str ); }  $\C{// constructor}$
     152struct int_msg {
     153        @inline message;@                                               $\C{// Plan-9 C nominal inheritance}$
     154        int i;
     155};
     156void ?{}( int_msg & this, int i ) { this.i = i; }       $\C{// constructor}$
     157// behaviours
     158allocation receive( my_actor &, @str_msg & msg@ ) {
     159        sout | "string message \"" | msg.str | "\"";
     160        return Nodelete;                                                $\C{// actor not finished}$
     161}
     162allocation receive( my_actor &, @int_msg & msg@ ) {
     163        sout | "integer message" | msg.i;
     164        return Nodelete;                                                $\C{// actor not finished}$
     165}
     166int main() {
     167        start_actor_system();                                   $\C{// sets up executor}$
     168        my_actor actor;                                                 $\C{// default constructor call}$
     169        str_msg str_msg{ "Hello World" };               $\C{// constructor call}$
     170        int_msg int_msg{ 42 };                                  $\C{// constructor call}$
     171        @actor << str_msg << int_msg;@                  $\C{// cascade sends}$
     172        @actor << int_msg;@                                             $\C{// send}$
     173        @actor << finished_msg;@                                $\C{// send => terminate actor (deallocation deferred)}$
     174        stop_actor_system();                                    $\C{// waits until actors finish}\CRT$
     175} // deallocate int_msg, str_msg, actor
    134176\end{cfa}
    135 The \code{Allocation} enum is a set of actions that dictate what the executor should do with a message or actor after a given behaviour has been completed.
    136 In the case of an actor, the \code{receive} routine returns the \code{Allocation} status to the executor which sets the status on the actor and takes the appropriate action.
    137 For messages, they either default to \code{Nodelete}, or they can be passed an \code{Allocation} via the \code{message} constructor.
    138 Message state can be updated via a call to:
     177\caption{\CFA Actor Syntax}
     178\label{f:CFAActorSyntax}
     179\end{figure}
     180
     181Figure~\ref{f:CFAActorSyntax} shows a complete \CFA actor example starting with the actor type @my_actor@ created by defining a @struct@ that inherits from the base @actor@ @struct@ via the @inline@ keyword.
     182This inheritance style is the Plan-9 C-style nominal inheritance discussed in Section~\ref{s:Inheritance}.
     183Similarly, the message types @str_msg@ and @int_msg@ are created by defining a @struct@ that inherits from the base @message@ @struct@ via the @inline@ keyword.
     184Both message types have constructors to set the message value.
     185There are two matching @receive@ (behaviour) routines that process the corresponding typed messages.
     186The program main begins by calling @start_actor_system@ to start the actor implementation, including executor threads to run the actors.
     187An actor and two messages are created on the stack, and four messages are sent to the actor using operator @<<@.
     188The last message is the builtin @finish_msg@, which returns @Finished@ to an executor thread, which removes the actor from the actor system \see{Section~\ref{s:ActorBehaviours}}.
     189The call to @stop_actor_system@ blocks program main until all actors are finished and removed from the actor system.
     190The program main ends by deleting the actor and messages from the stack.
     191The output for the program is:
    139192\begin{cfa}
    140 void set_allocation( message & this, Allocation state )
     193string message "Hello World"
     194integer message 42
     195integer message 42
    141196\end{cfa}
    142197
    143 The following describes the use of each of the \code{Allocation} values:
    144 
    145 \begin{description}
    146 \item[\LstBasicStyle{\textbf{Nodelete}}]
    147 tells the executor that no action is to be taken with regard to a message or actor with this status.
    148 This indicates that the actor will receive future behaviours, and that a message may be reused.
    149 
    150 \item[\LstBasicStyle{\textbf{Delete}}]
    151 tells the executor to call the appropriate destructor and then deallocate the respective actor or message.
    152 This status is typically used with dynamically allocated actors and messages.
    153 
    154 \item[\LstBasicStyle{\textbf{Destroy}}]
    155 tells the executor to call the object's destructor.
    156 The executor will not deallocate the respective actor or message.
    157 This status is typically used with dynamically allocated actors and messages whose storage will be reused.
    158 
    159 \item[\LstBasicStyle{\textbf{Finished}}]
    160 tells the executor to mark the respective actor as being finished executing.
    161 In this case the executor will not call any destructors or deallocate any objects.
    162 This status is used when the actors are stack allocated or if the user wants to manage deallocation of actors themselves.
    163 In the case of messages, \code{Finished} is no different than \code{Nodelete} since the executor does not need to track if messages are done work.
    164 As such \code{Finished} is not supported for messages and is used internally by the executor to track if messages have been used for debugging purposes.
    165 \end{description}
    166 
    167 For the actor system to gracefully terminate, all actors must have returned a status other than \code{Nodelete}.
    168 Once an actor's allocation status has been set to something other than \code{Nodelete}, it is erroneous for the actor to receive a message.
    169 Similarly messages cannot be safely reused after their related behaviour if their status is not \code{Nodelete}.
    170 Note, it is safe to construct a message with a non-\code{Nodelete} status since the executor will only take the appropriate allocation action after a message has been delivered.
    171 
    172 The calls to \code{start_actor_system}, and \code{stop_actor_system} mark the start and end of a \CFA actor system.
    173 The call to \code{start_actor_system} sets up the executor and worker threads for the actor system.
    174 \code{start_actor_system} has three overloaded signatures which all start the actor system, but vary in executor configuration:
    175 
    176 \noindent\code{void start_actor_system()} configures the executor with one underlying worker thread and processor.
    177 
    178 \noindent\code{void start_actor_system( size_t num_thds )} configures the executor with \code{num_thds} underlying processors and \code{num_thds} worker threads.
    179 It chooses amount of queue sharding as a function of \code{num_thds}.
    180 
    181 \noindent\code{void start_actor_system( executor & this )} allows the user to allocate, configure, and pass an executor so that they have full control of executor parameterization.
    182 Executor configuration options include number of worker threads, number of queues, number of processors, and a few other toggles.
    183 
    184 All actors must be created after calling \code{start_actor_system} so that the executor can keep track of the number of actors that have been allocated but have not yet terminated.
    185 
    186 All message sends are done using the left shift operater, \ie <<, similar to the syntax of \CC's output.
    187 The signature of the left shift operator is:
     198\subsection{Actor Behaviours}\label{s:ActorBehaviours}
     199In general, a behaviour for some derived actor and derived message type is defined with following signature:
    188200\begin{cfa}
    189 Allocation ?<<?( derived_actor & receiver, derived_msg & msg )
     201allocation receive( my_actor & receiver, my_msg & msg )
    190202\end{cfa}
    191 
    192 An astute eye will notice that this is the same signature as the \code{receive} routine which is no coincidence.
    193 The \CFA compiler generates a \code{?<<?} routine definition and forward declaration for each \code{receive} routine that has the appropriate signature.
    194 The generated routine packages the message and actor in an \hyperref[s:envelope]{envelope} and adds it to the executor's queues via an executor routine.
    195 As part of packaging the envelope, the \code{?<<?} routine sets a function pointer in the envelope to point to the appropriate receive routine for given actor and message types.
    196 
     203where @my_actor@ and @my_msg@ inherit from types @actor@ and @message@, respectively.
     204The return value of @receive@ must be a value from enumerated type, @allocation@:
     205\begin{cfa}
     206enum allocation { Nodelete, Delete, Destroy, Finished };
     207\end{cfa}
     208The values represent a set of actions that dictate what the executor does with an actor or message after a given behaviour returns.
     209For actors, the @receive@ routine returns the @allocation@ status to the executor, which takes the appropriate action.
     210For messages, either the default allocation, @Nodelete@, or any changed value in the message is examined by the executor, which takes the appropriate action.
     211Message state is updated via a call to:
     212\begin{cfa}
     213void set_allocation( message & this, allocation state )
     214\end{cfa}
     215
     216In detail, the actions taken by an executor for each of the @allocation@ values are:
     217
     218\noindent@Nodelete@
     219tells the executor that no action is to be taken with regard to an actor or message.
     220This status is used when an actor continues receiving messages or a message may be reused.
     221
     222\noindent@Delete@
     223tells the executor to call the object's destructor and deallocate (delete) the object.
     224This status is used with dynamically allocated actors and messages when they are not reused.
     225
     226\noindent@Destroy@
     227tells the executor to call the object's destructor, but not deallocate the object.
     228This status is used with dynamically allocated actors and messages whose storage is reused.
     229
     230\noindent@Finished@
     231tells the executor to mark the respective actor as finished executing, but not call the object's destructor nor deallocate the object.
     232This status is used when actors or messages are global or stack allocated, or a programmer wants to manage deallocation themselves.
     233
     234For the actor system to terminate, all actors must have returned a status other than @Nodelete@.
     235After an actor is terminated, it is erroneous to send messages to it.
     236Similarly,  after a message is terminated, it cannot be sent to an actor.
     237Note, it is safe to construct an actor or message with a status other than @Nodelete@, since the executor only examines the allocation action after a behaviour returns.
     238
     239\subsection{Actor System}\label{s:ActorSystem}
     240The calls to @start_actor_system@, and @stop_actor_system@ mark the start and end of a \CFA actor system.
     241The call to @start_actor_system@ sets up an executor and executor threads for the actor system.
     242It is possible to have multiple start/stop scenarios in a program.
     243
     244@start_actor_system@ has three overloaded signatures that vary the executor's configuration:
     245
     246\noindent@void start_actor_system()@
     247configures the executor to implicitly use all preallocated kernel-threads (processors), \ie the processors created by the program main prior to starting the actor system.
     248When the number of processors is greater than 1, each executor's message queue is sharded by a factor of 16 to reduce contention, \ie for 4 executor threads (processors), there is a total of 4 $\times$ 16 message queues evenly distributed across the executor threads.
     249
     250\noindent@void start_actor_system( size_t num_thds )@
     251configures the number of executor threads to @num_thds@, with the same message queue sharding.
     252
     253\noindent@void start_actor_system( executor & this )@
     254allows the programmer to explicitly create and configure an executor for use by the actor system.
     255Executor configuration options include are discussed in Section~\ref{s:executor}.
     256
     257\noindent
     258All actors must be created \emph{after} calling @start_actor_system@ so the executor can keep track of the number of actors that have entered the system but not yet terminated.
     259
     260% All message sends are done using the left-shift operator, @<<@, similar to the syntax of \CC's stream output.
     261% \begin{cfa}
     262% allocation ?<<?( my_actor & receiver, my_msg & msg )
     263% \end{cfa}
     264% Notice this signature is the same as the @receive@ routine, which is no coincidence.
     265% The \CFA compiler generates a @?<<?@ routine definition and forward declaration for each @receive@ routine that has the appropriate signature.
     266% The generated routine packages the message and actor in an \hyperref[s:envelope]{envelope} and adds it to the executor's queues via an executor routine.
     267% As part of packaging the envelope, the @?<<?@ routine sets a routine pointer in the envelope to point to the appropriate receive routine for given actor and message types.
     268
     269\subsection{Actor Send}\label{s:ActorSend}
     270All message sends are done using the left-shift operator, @<<@, similar to the syntax of \CC's stream output.
     271As stated, \CFA does not have named inheritance with RTTI.
     272\CFA does have a preliminary form of virtual routines, but it is not mature enough for use in this work.
     273Therefore, there is no mechanism to write a generic @<<@ routine taking a base actor and message type, and then dynamically selecting the @receive@ routine from the actor argument.
     274(For messages, the Plan-9 inheritance is sufficient because only the inherited fields are needed during the message send.)
     275Hence, programmers must write a matching @<<@ routine for each @receive@ routine, which is awkward and generates a maintenance problem.
     276Therefore, I chose to use a template-like approach, where the compiler generates a matching @<<@ routine for each @receive@ routine it finds with an actor/message type-signature.
     277Then, \CFA uses the type from the left-hand side of an assignment to select the matching receive routine.
     278(When the \CFA virtual routines mature, it should be possible to seamlessly transition to it from the template approach.)
     279
     280% Funneling all message sends through a single @allocation ?<<?(actor &, message &)@ routine is not feasible since the type of the actor and message would be erased, making it impossible to acquire a pointer to the correct @receive@.
     281% As such a @?<<?@ routine per @receive@ provides type information needed to write the correct "address" on the envelope.
     282
     283% The left-shift operator routines are generated by the compiler.
     284An example of a receive routine and its corresponding generated operator routine is shown in Figure~\ref{f:actor_gen}.
     285Notice the parameter signature of @?<<?@ is the same as the @receive@ routine.
     286A @?<<?@ routine is generated per @receive@ routine with a matching signature.
     287The @?<<?@ routine packages the message and actor in an \hyperref[s:envelope]{envelope} and adds it to the executor's queues via the executor routine @send@.
     288The envelope is conceptually "addressed" to a behaviour, which is stored in the envelope as a function pointer to a @receive@ routine.
     289The @?<<?@ routines ensure that messages are sent to the right address, \ie sent to the right @receive@ routine based on actor and message type.
     290
     291\begin{figure}
     292\begin{cfa}
     293$\LstCommentStyle{// from Figure~\ref{f:CFAActorSyntax}}$
     294struct my_actor { inline actor; };                                      $\C[3.5in]{// actor}$
     295struct int_msg { inline message; int i; };                      $\C{// message}$
     296void ?{}( int_msg & this, int i ) { this.i = i; }       $\C{// constructor}$
     297allocation receive( @my_actor &, int_msg & msg@ ) {     $\C{// receiver}$
     298        sout | "integer message" | msg.i;
     299        return Nodelete;
     300}
     301
     302// compiler generated operator
     303#define RECEIVER( A, M ) (allocation (*)(actor &, message &))(allocation (*)( A &, M & ))receive
     304my_actor & ?<<?( @my_actor & receiver, int_msg & msg@ ) {
     305        send( receiver, (request){ &receiver, &msg, RECEIVER( my_actor, int_msg ) } );
     306        return receiver;
     307}
     308\end{cfa}
     309\caption{Generated Send Operator}
     310\label{f:actor_gen}
     311\end{figure}
    197312
    198313\section{\CFA Executor}\label{s:executor}
    199 This section will describe the basic architecture of the \CFA executor.
    200 Any discussion of work stealing is omitted until Section \ref{s:steal}.
    201 The executor of an actor system is the scheduler that organizes where actors behaviours are run and how messages are sent and delivered.
    202 In \CFA the executor lays out actors across the sharded message queues in round robin order as they are created.
    203 The message queues are split across worker threads in equal chunks, or as equal as possible if the number of message queues is not divisible by the number of workers threads.
     314This section describes the basic architecture of the \CFA executor.
     315An executor of an actor system is the scheduler that organizes where actor behaviours are run and how messages are sent and delivered.
     316In \CFA, the executor is message-centric \see{Figure~\ref{f:inverted_actor}}, but extended by over sharding of a message queue \see{left side of Figure~\ref{f:gulp}}, \ie there are $M$ message queues where $M$ is greater than the number of executor threads $N$ (usually a multiple of $N$).
     317This approach reduces contention by spreading message delivery among the $M$ queues rather than $N$, while still maintaining actor FIFO message-delivery semantics.
     318The only extra overhead is each executor cycling (usually round-robin) through its $M$/$N$ queues.
     319The goal is to achieve better performance and scalability for certain kinds of actor applications by reducing executor locking.
     320Note, lock-free queues do not help because busy waiting on any atomic instruction is the source of the slowdown whether it is a lock or lock-free.
     321Work steal now becomes queue stealing, where an entire actor/message queue is stolen, which trivially preserves message ordering in a queue \see{Section~\ref{s:steal}}.
    204322
    205323\begin{figure}
    … …  
    207325\input{diagrams/gulp.tikz}
    208326\end{center}
    209 \caption{Diagram of the queue gulping mechanism.}
     327\caption{Queue Gulping Mechanism}
    210328\label{f:gulp}
    211329\end{figure}
    212330
    213 Each worker thread iterates over its own message queues until it finds one that contains messages.
    214 At this point the worker thread \textbf{gulps} the queue.
    215 A \textbf{gulp} is a term for consuming the contents of message queue and transferring them to the local queue of worker thread.
    216 After the gulp is done atomically, this allows the worker thread to process the queue locally without any need for atomicity until the next gulp.
    217 Messages can be added to the queue that was gulped in parallel with the processing of the local queue.
    218 Additionally, prior to each gulp, the worker non-atomically checks if a queue is empty before attempting to gulp it.
    219 Between this and the gulp, the worker avoids many potentially costly lock acquisitions.
    220 An example of the queue gulping operation is shown in Figure \ref{f:gulp} where a worker thread gulps queue 0 and begins to process it locally.
    221 
    222 To process its local queue, a worker thread takes each unit of work off the queue and executes it.
    223 Since all messages to a given actor will be in the same queue, this guarantees atomicity across behaviours of that actor since it can only execute on one thread at a time.
    224 After running behaviour, the worker thread looks at the returned allocation status and takes the corresponding action.
    225 Once all actors have marked themselves as being finished the executor initiates shutdown by inserting a sentinel value into the message queues.
    226 Once a worker thread sees a sentinel it stops running.
    227 After all workers stop running the actor system shutdown is complete.
     331Each executor thread iterates over its own message queues until it finds one with messages.
     332At this point, the executor thread atomically \gls{gulp}s the queue, meaning move the contents of message queue to a local queue of the executor thread using a single atomic instruction.
     333This step allows the executor threads to process the local queue without any atomics until the next gulp, while other executor threads are adding in parallel to the end of one of the message queues.
     334In detail, an executor thread performs a test-and-gulp, non-atomically checking if a queue is non-empty before gulping it.
     335If a test fails during a message add, the worst-case is cycling through all the message queues.
     336However, the gain is minimizing costly lock acquisitions.
     337An example of the queue gulping operation is shown in the right side of Figure \ref{f:gulp}, where a executor threads gulps queue 0 and begins to process it locally.
     338
     339Processing a local queue involves removing a unit of work from the queue and executing it.
     340Since all messages to a given actor are in the same queue, this guarantees atomicity across behaviours of that actor since it can only execute on one thread at a time.
     341After running a behaviour, the executor thread examines the returned allocation status from the @receive@ routine for the actor and internal status in the delivered message, and takes the appropriate action.
     342Once all actors have marked themselves as being finished the executor initiates shutdown by inserting a sentinel value into the message queues.
     343Once a executor threads sees a sentinel it stops running.
     344After all executors stop running the actor system shutdown is complete.
    228345
    229346\section{Envelopes}\label{s:envelope}
    230 In actor systems messages are sent and received by actors.
    231 When a actor receives a message it executes its behaviour that is associated with that message type.
    232 However the unit of work that stores the message, the receiving actor's address, and other pertinent information needs to persist between send and the receive.
    233 Furthermore the unit of work needs to be able to be stored in some fashion, usually in a queue, until it is executed by an actor.
    234 All these requirements are fulfilled by a construct called an envelope.
    235 The envelope wraps up the unit of work and also stores any information needed by data structures such as link fields.
    236 To meet the persistence requirement the envelope is dynamically allocated and cleaned up after it has been delivered and its payload has run.
    237 
    238 One may ask, "Could the link fields and other information be stored in the message?".
    239 This is a good question to ask since messages also need to have a lifetime that persists beyond the work it delivers.
    240 However, if one were to use messages as envelopes then a message would not be able to be sent to multiple actors at a time.
    241 Therefore this approach would just push the allocation into another location, and require the user to dynamically allocate a message for every send, or require careful ordering to allow for message reuse.
    242 
    243 This frequent allocation of envelopes with each message send between actors results in heavy contention on the memory allocator.
    244 As such, a way to alleviate contention on the memory allocator could result in performance improvement.
    245 Contention was reduced using a novel data structure that is called a copy queue.
    246 
    247 \subsection{The Copy Queue}\label{s:copyQueue}
    248 The copy queue is a thin layer over a dynamically sized array that is designed with the envelope use case in mind.
    249 A copy queue supports the typical queue operations of push/pop but in a different way than a typical array based queue.
    250 The copy queue is designed to take advantage of the \hyperref[s:executor]{gulping} pattern.
    251 As such the amortized rutime cost of each push/pop operation for the copy queue is $O(1)$.
    252 In contrast, a naive array based queue often has either push or pop cost $O(n)$ and the other cost $O(1)$ since for at least one of the operations all the elements of the queue have to be shifted over.
    253 Since the worker threads gulp each queue to operate on locally, this creates a usage pattern of the queue where all elements are popped from the copy queue without any interleaved pushes.
    254 As such, during pop operations there is no need to shift array elements.
    255 An index is stored in the copy queue data structure which keeps track of which element to pop next allowing pop to be $O(1)$.
    256 Push operations are amortized $O(1)$ since pushes may cause doubling reallocations of the underlying dynamic sized array.
     347As stated, each message, regardless of where it is allocated, can be sent to an arbitrary number of actors, and hence, appear on an arbitrary number of message queues.
     348Because a C program manages message lifetime, messages cannot be copied for each send, otherwise who manages the copies.
     349Therefore, it up to the actor program to manage message life-time across receives.
     350However, for a message to appear on multiple message queues, it needs an arbitrary number of link fields.
     351Hence, there is the concept of an envelop, which is dynamically allocated on each send, that wraps a message with any extra implementation fields needed to persist between send and receive.
     352Managing the envelop is straightforward because it is created at the send and deleted after the receive, \ie there is 1:1 relationship for an envelop and a many to one relationship for a message.
     353
     354% In actor systems, messages are sent and received by actors.
     355% When a actor receives a message it executes its behaviour that is associated with that message type.
     356% However the unit of work that stores the message, the receiving actor's address, and other pertinent information needs to persist between send and the receive.
     357% Furthermore the unit of work needs to be able to be stored in some fashion, usually in a queue, until it is executed by an actor.
     358% All these requirements are fulfilled by a construct called an envelope.
     359% The envelope wraps up the unit of work and also stores any information needed by data structures such as link fields.
     360
     361% One may ask, "Could the link fields and other information be stored in the message?".
     362% This is a good question to ask since messages also need to have a lifetime that persists beyond the work it delivers.
     363% However, if one were to use messages as envelopes then a message would not be able to be sent to multiple actors at a time.
     364% Therefore this approach would just push the allocation into another location, and require the user to dynamically allocate a message for every send, or require careful ordering to allow for message reuse.
     365
     366Unfortunately, this frequent allocation of envelopes for each send results in heavy contention on the memory allocator.
     367As such, a way to alleviate contention on the memory allocator would result in a performance improvement.
     368Contention is reduced using a novel data structure, called a \Newterm{copy queue}.
     369
     370\subsection{Copy Queue}\label{s:copyQueue}
     371The copy queue is a thin layer over a dynamically sized array that is designed with the envelope use case in mind.
     372A copy queue supports the typical queue operations of push/pop but in a different way than a typical array based queue.
     373The copy queue is designed to take advantage of the \gls{gulp}ing pattern.
     374As such, the amortized runtime cost of each push/pop operation for the copy queue is $O(1)$.
     375In contrast, a na\"ive array-based queue often has either push or pop cost $O(n)$ and the other cost $O(1)$ since one of the operations requires shifting the elements of the queue.
     376Since the executor threads gulp a queue to operate on it locally, this creates a usage pattern where all elements are popped from the copy queue without any interleaved pushes.
     377As such, during pop operations there is no need to shift array elements.
     378Instead, an index is stored in the copy-queue data-structure that keeps track of which element to pop next allowing pop to be $O(1)$.
     379Push operations are amortized $O(1)$ since pushes may cause doubling reallocations of the underlying dynamic-sized array (like \CC @vector@).
    257380
    258381% C_TODO: maybe make copy_queue diagram
    259382
    260 Since the copy queue is an array, envelopes are allocated first on the stack and then copied into the copy queue to persist until they are no longer needed.
    261 For a fixed message throughput workload, once the copy queues grow in size to facilitate the number of messages in flight, there are no longer any dynamic allocations occuring in the actor system.
    262 One problem that arises with this approach is that this array based approach will often allocate more storage than what is needed.
    263 Comparitively the individual envelope allocations of a list based queue mean that the actor system will always use the minimum amount of heap space needed and will clean up eagerly.
    264 Additionally, a workload with variable message throughput could cause copy queues to allocate large amounts of space to accomodate the peaks of the throughput, even if most of that storage is not needed for the rest of the workload's execution.
    265 
    266 
    267 To mitigate this a memory reclamation scheme was introduced.
    268 Initially the memory reclamation naively reclaimed one index of the array per gulp if the array size was above a low fixed threshold.
    269 This approach had a problem.
    270 The high memory usage watermark nearly doubled with this change! The issue with this approach can easily be highlighted with an example.
    271 Say that there is a fixed throughput workload where a queue never has more than 19 messages at a time.
    272 If the copy queue starts with a size of 10, it will end up doubling at some point to size 20 to accomodate 19 messages.
    273 However, after 2 gulps and subsequent reclamations the array would be size 18.
    274 The next time 19 messages are enqueued, the array size is doubled to 36! To avoid this issue a second check was added to reclamation.
    275 Each copy queue started tracking the utilization of their array size.
    276 Reclamation would only occur if less than half of the array was being utilized.
    277 In doing this the reclamation scheme was able to achieve a lower high watermark and a lower overall memory utilization when compared to the non-reclamation copy queues.
    278 However, the use of copy queues still incurs a higher memory cost than the list based queueing.
    279 With the inclusion of a memory reclamation scheme the increase in memory usage is reasonable considering the performance gains and will be discussed further in Section \ref{s:actor_perf}.
     383Since the copy queue is an array, envelopes are allocated first on the stack and then copied into the copy queue to persist until they are no longer needed.
     384For many workload, the copy queues grow in size to facilitate the average number of messages in flight and there is no further dynamic allocations.
     385One downside of this approach that more storage is allocated than needed, \ie each copy queue is only partially full.
     386Comparatively, the individual envelope allocations of a list based queue mean that the actor system always uses the minimum amount of heap space and cleans up eagerly.
     387Additionally, bursty workloads can cause the copy queues to allocate a large amounts of space to accommodate the peaks of the throughput, even if most of that storage is not needed for the rest of the workload's execution.
     388
     389To mitigate memory wastage, a reclamation scheme is introduced.
     390Initially, the memory reclamation na\"ively reclaims one index of the array per \gls{gulp}, if the array size is above a low fixed threshold.
     391However, this approach has a problem.
     392The high memory usage watermark nearly doubled!
     393The issue can easily be highlighted with an example.
     394Assume a fixed throughput workload, where a queue never has more than 19 messages at a time.
     395If the copy queue starts with a size of 10, it ends up doubling at some point to size 20 to accommodate 19 messages.
     396However, after 2 gulps and subsequent reclamations the array size is 18.
     397The next time 19 messages are enqueued, the array size is doubled to 36!
     398To avoid this issue a second check is added.
     399Each copy queue started tracking the utilization of its array size.
     400Reclamation only occurs if less than half of the array is utilized.
     401In doing this, the reclamation scheme is able to achieve a lower high-watermark and a lower overall memory utilization compared to the non-reclamation copy queues.
     402However, the use of copy queues still incurs a higher memory cost than list-based queueing.
     403With the inclusion of a memory reclamation scheme the increase in memory usage is reasonable considering the performance gains and is discussed further in Section~\ref{s:actor_perf}.
    280404
    281405\section{Work Stealing}\label{s:steal}
    282 Work stealing is a scheduling strategy that attempts to load balance, and increase resource untilization by having idle threads steal work.
     406Work stealing is a scheduling strategy that attempts to load balance, and increase resource utilization by having idle threads steal work.
    283407There are many parts that make up a work stealing actor scheduler, but the two that will be highlighted in this work are the stealing mechanism and victim selection.
    284408
    285409% C_TODO enter citation for langs
    286410\subsection{Stealing Mechanism}
    287 In this discussion of work stealing the worker being stolen from will be referred to as the \textbf{victim} and the worker stealing work will be called the \textbf{thief}. 
    288 The stealing mechanism presented here differs from existing work stealing actor systems due the inverted actor system. 
    289 Other actor systems such as Akka \cite{} and CAF \cite{} have work stealing, but since they use an classic actor system that is actor-centric, stealing work is the act of stealing an actor from a dequeue. 
    290 As an example, in CAF, the sharded actor queue is a set of double ended queues (dequeues). 
    291 Whenever an actor is moved to a ready queue, it is inserted into a worker's dequeue. 
    292 Workers then consume actors from the dequeue and execute their behaviours. 
    293 To steal work, thieves take one or more actors from a victim's dequeue. 
    294 This action creates contention on the dequeue, which can slow down the throughput of the victim. 
    295 The notion of which end of the dequeue is used for stealing, consuming, and inserting is not discussed since it isn't relevant. 
     411In this discussion of work stealing the worker being stolen from will be referred to as the \textbf{victim} and the worker stealing work will be called the \textbf{thief}.
     412The stealing mechanism presented here differs from existing work stealing actor systems due the inverted actor system.
     413Other actor systems such as Akka \cite{} and CAF \cite{} have work stealing, but since they use an classic actor system that is actor-centric, stealing work is the act of stealing an actor from a dequeue.
     414As an example, in CAF, the sharded actor queue is a set of double ended queues (dequeues).
     415Whenever an actor is moved to a ready queue, it is inserted into a worker's dequeue.
     416Workers then consume actors from the dequeue and execute their behaviours.
     417To steal work, thieves take one or more actors from a victim's dequeue.
     418This action creates contention on the dequeue, which can slow down the throughput of the victim.
     419The notion of which end of the dequeue is used for stealing, consuming, and inserting is not discussed since it isn't relevant.
    296420By the pigeon hole principle there are three dequeue operations (push/victim pop/thief pop) that can occur concurrently and only two ends to a dequeue, so work stealing being present in a dequeue based system will always result in a potential increase in contention on the dequeues.
    297421
    298422% C_TODO: maybe insert stealing diagram
    299423
    300 In \CFA, the actor work stealing implementation is unique. 
    301 While other systems are concerned with stealing actors, the \CFA actor system steals queues. 
    302 This is a result of \CFA's use of the inverted actor system. 
    303 The goal of the \CFA actor work stealing mechanism is to have a zero-victim-cost stealing mechanism. 
    304 This does not means that stealing has no cost. 
    305 This goal is to ensure that stealing work does not impact the performance of victim workers. 
    306 This means that thieves can not contend with victims, and that victims should perform no stealing related work unless they become a thief. 
    307 In theory this goal is not achieved, but results will be presented that show the goal is achieved in practice. 
    308 In \CFA's actor system workers own a set of sharded queues which they iterate over and gulp. 
    309 If a worker has iterated over the queues they own twice without finding any work, they try to steal a queue from another worker. 
    310 Stealing a queue is done wait-free with a few atomic instructions that can only create contention with other stealing workers. 
     424In \CFA, the actor work stealing implementation is unique.
     425While other systems are concerned with stealing actors, the \CFA actor system steals queues.
     426This is a result of \CFA's use of the inverted actor system.
     427The goal of the \CFA actor work stealing mechanism is to have a zero-victim-cost stealing mechanism.
     428This does not means that stealing has no cost.
     429This goal is to ensure that stealing work does not impact the performance of victim workers.
     430This means that thieves can not contend with victims, and that victims should perform no stealing related work unless they become a thief.
     431In theory this goal is not achieved, but results will be presented that show the goal is achieved in practice.
     432In \CFA's actor system workers own a set of sharded queues which they iterate over and gulp.
     433If a worker has iterated over the queues they own twice without finding any work, they try to steal a queue from another worker.
     434Stealing a queue is done wait-free with a few atomic instructions that can only create contention with other stealing workers.
    311435To steal a queue a worker does the following:
    312436\begin{enumerate}[topsep=5pt,itemsep=3pt,parsep=0pt]
    … …  
    315439
    316440\item
    317 The thief starts at a random index in the array of the victim's queues and searches for a candidate queue. 
    318 A candidate queue is any queue that is not empty, is not being stolen by another thief, and is not being processed by the victim. 
    319 These are not strictly enforced rules. 
    320 The candidate is identified non-atomically and as such queues that do not satisfy these rules may be stolen. 
    321 However, steals that do not meet these requirements do not affect correctness so they are allowed and do not constitute failed steals as the queues will still be swapped. 
    322 
    323 
    324 \item
    325 Once a candidate queue is chosen, the thief attempts a wait-free swap of the victim's queue and a random on of the thief's queues. 
    326 This swap can fail. 
    327 If the swap is successful the thief swaps the two queues. 
    328 If the swap fails, another thief must have attempted to steal one of the two queues being swapped. 
     441The thief starts at a random index in the array of the victim's queues and searches for a candidate queue.
     442A candidate queue is any queue that is not empty, is not being stolen by another thief, and is not being processed by the victim.
     443These are not strictly enforced rules.
     444The candidate is identified non-atomically and as such queues that do not satisfy these rules may be stolen.
     445However, steals that do not meet these requirements do not affect correctness so they are allowed and do not constitute failed steals as the queues will still be swapped.
     446
     447
     448\item
     449Once a candidate queue is chosen, the thief attempts a wait-free swap of the victim's queue and a random on of the thief's queues.
     450This swap can fail.
     451If the swap is successful the thief swaps the two queues.
     452If the swap fails, another thief must have attempted to steal one of the two queues being swapped.
    329453Failing to steal is good in this case since stealing a queue that was just swapped would likely result in stealing an empty queue.
    330454\end{enumerate}
    331455
    332 Once a thief fails or succeeds in stealing a queue, it goes back to its own set of queues and iterates over them again. 
    333 It will only try to steal again once it has completed two consecutive iterations over its owned queues without finding any work. 
    334 The key to the stealing mechnism is that the queues can still be operated on while they are being swapped.
    335 This elimates any contention between thieves and victims.
    336 The first key to this is that actors and workers maintain two distinct arrays of references to queues. 
    337 Actors will always receive messages via the same queues. 
    338 Workers, on the other hand will swap the pointers to queues in their shared array and operate on queues in the range of that array that they own. 
    339 Swapping queues is a matter of atomically swapping two pointers in the worker array. 
     456Once a thief fails or succeeds in stealing a queue, it goes back to its own set of queues and iterates over them again.
     457It will only try to steal again once it has completed two consecutive iterations over its owned queues without finding any work.
     458The key to the stealing mechanism is that the queues can still be operated on while they are being swapped.
     459This eliminates any contention between thieves and victims.
     460The first key to this is that actors and workers maintain two distinct arrays of references to queues.
     461Actors will always receive messages via the same queues.
     462Workers, on the other hand will swap the pointers to queues in their shared array and operate on queues in the range of that array that they own.
     463Swapping queues is a matter of atomically swapping two pointers in the worker array.
    340464As such pushes to the queues can happen concurrently during the swap since pushes happen via the actor queue references.
    341465
    342 Gulping can also occur during queue swapping, but the implementation requires more nuance than the pushes. 
    343 When a worker is not stealing it iterates across its own range of queues and gulps them one by one. 
    344 When a worker operates on a queue it first copies the current pointer from the worker array of references to a local variable. 
    345 It then uses that local variable for all queue operations until it moves to the next index of its range of the queue array. 
    346 This ensures that any swaps do not interrupt gulping operations, however this introduces a correctness issue. 
    347 If any behaviours from a queue are run by two workers at a time it violates both mutual exclusion and the actor ordering guarantees. 
    348 As such this must be avoided. 
    349 To avoid this each queue has a \code{being_processed} flag that is atomically set to \code{true} when a queue is gulped.
    350 The flag indicates that a queue is being processed locally and is set back to \code{false} once the local processing is finished.
    351 If a worker attempts to gulp a queue and finds that the \code{being_processed} flag is \code{true}, it does not gulp the queue and moves on to the next queue in its range.
    352 This is a source of contention between victims and thieves since a thief may steal a queue and set \code{being_processed} to \code{true} between a victim saving a pointer to a queue and gulping it.
    353 However, the window for this race is very small, making this contention rare. 
    354 This is why the claim is made that this mechanism is zero-victim-cost in practice but not in theory. 
    355 By collecting statistics on failed gulps due to the \code{being_processed} flag, it is found that this contention occurs ~0.05\% of the time when a gulp occurs.
     466Gulping can also occur during queue swapping, but the implementation requires more nuance than the pushes.
     467When a worker is not stealing it iterates across its own range of queues and gulps them one by one.
     468When a worker operates on a queue it first copies the current pointer from the worker array of references to a local variable.
     469It then uses that local variable for all queue operations until it moves to the next index of its range of the queue array.
     470This ensures that any swaps do not interrupt gulping operations, however this introduces a correctness issue.
     471If any behaviours from a queue are run by two workers at a time it violates both mutual exclusion and the actor ordering guarantees.
     472As such this must be avoided.
     473To avoid this each queue has a @being_processed@ flag that is atomically set to @true@ when a queue is gulped.
     474The flag indicates that a queue is being processed locally and is set back to @false@ once the local processing is finished.
     475If a worker attempts to gulp a queue and finds that the @being_processed@ flag is @true@, it does not gulp the queue and moves on to the next queue in its range.
     476This is a source of contention between victims and thieves since a thief may steal a queue and set @being_processed@ to @true@ between a victim saving a pointer to a queue and gulping it.
     477However, the window for this race is very small, making this contention rare.
     478This is why the claim is made that this mechanism is zero-victim-cost in practice but not in theory.
     479By collecting statistics on failed gulps due to the @being_processed@ flag, it is found that this contention occurs ~0.05\% of the time when a gulp occurs.
    356480Hence, the claim is made that this stealing mechanism has zero-victim-cost in practice.
    357481
    358482
    359483\subsection{Queue Swap Correctness}
    360 Given the wait-free swap used is novel, it is important to show that it is correct. 
    361 Firstly, it is clear to show that the swap is wait-free since all workers will fail or succeed in swapping the queues in a finite number of steps since there are no locks or looping. 
    362 There is no retry mechanism in the case of a failed swap, since a failed swap either means the work was already stolen, or that work was stolen from the thief. 
    363 In both cases it is apropos for a thief to given up on stealing. 
    364 \CFA-style pseudocode for the queue swap is presented below. 
    365 The swap uses compare-and-swap (\code{CAS}) which is just pseudocode for C's \code{__atomic_compare_exchange_n}.
    366 A pseudocode implementation of \code{CAS} is also shown below.
    367 The correctness of the wait-free swap will now be discussed in detail. 
     484Given the wait-free swap used is novel, it is important to show that it is correct.
     485Firstly, it is clear to show that the swap is wait-free since all workers will fail or succeed in swapping the queues in a finite number of steps since there are no locks or looping.
     486There is no retry mechanism in the case of a failed swap, since a failed swap either means the work was already stolen, or that work was stolen from the thief.
     487In both cases it is apropos for a thief to given up on stealing.
     488\CFA-style pseudocode for the queue swap is presented below.
     489The swap uses compare-and-swap (@CAS@) which is just pseudocode for C's @__atomic_compare_exchange_n@.
     490A pseudocode implementation of @CAS@ is also shown below.
     491The correctness of the wait-free swap will now be discussed in detail.
    368492To first verify sequential correctness, consider the equivalent sequential swap below:
    369493
    … …  
    382506\end{cfa}
    383507
    384 Step 1 is missing in the sequential example since in only matter in the concurrent context presented later. 
    385 By looking at the sequential swap it is easy to see that it is correct. 
     508Step 1 is missing in the sequential example since in only matter in the concurrent context presented later.
     509By looking at the sequential swap it is easy to see that it is correct.
    386510Temporary copies of each pointer being swapped are stored, and then the original values of each pointer are set using the copy of the other pointer.
    387511
    … …  
    403527        // Step 1:
    404528        // If either queue is 0p then they are in the process of being stolen
    405         // 0p is CForAll's equivalent of C++'s nullptr
     529        // 0p is Cforall's equivalent of C++'s nullptr
    406530        if ( vic_queue == 0p ) return false;
    407531
    … …  
    411535        if ( !CAS( &request_queues[my_idx], &my_queue, 0p ) )
    412536                return false;
    413        
     537
    414538        // Step 3:
    415539        // Try to set victim queue ptr to be thief's queue ptr.
    … …  
    434558Step 0 is the same as the sequential example, and the thief stores local copies of the two pointers to be swapped.
    435559\item
    436 Step 1 verifies that the stored copy of the victim queue pointer, \code{vic_queue}, is valid.
    437 If \code{vic_queue} is equal to \code{0p}, then the victim queue is part of another swap so the operation fails.
    438 No state has changed at this point so no fixups are needed. 
    439 Note, \code{my_queue} can never be equal to \code{0p} at this point since thieves only set their own queues pointers to \code{0p} when stealing.
    440 At no other point will a queue pointer be set to \code{0p}.
    441 Since each worker owns a disjoint range of the queue array, it is impossible for \code{my_queue} to be \code{0p}.
    442 \item
    443 Step 2 attempts to set the thief's queue pointer to \code{0p} via \code{CAS}.
    444 The \code{CAS} will only fail if the thief's queue pointer is no longer equal to \code{my_queue}, which implies that this thief has become a victim and its queue has been stolen.
    445 At this point the thief-turned-victim will fail and since it has not changed any state it just fails and returns false. 
    446 If the \code{CAS} succeeds then the thief's queue pointer will now be \code{0p}.
    447 Nulling the pointer is safe since only thieves look at other worker's queue ranges, and whenever thieves need to dereference a queue pointer they check for \code{0p}.
    448 \item
    449 Step 3 attempts to set the victim's queue pointer to be \code{my_queue} via \code{CAS}.
    450 If the \code{CAS} succeeds then the victim's queue pointer has been set and swap can no longer fail.
    451 If the \code{CAS} fails then the thief's queue pointer must be restored to its previous value before returning.
    452 \item 
    453 Step 4 sets the thief's queue pointer to be \code{vic_queue} completing the swap.
     560Step 1 verifies that the stored copy of the victim queue pointer, @vic_queue@, is valid.
     561If @vic_queue@ is equal to @0p@, then the victim queue is part of another swap so the operation fails.
     562No state has changed at this point so no fixups are needed.
     563Note, @my_queue@ can never be equal to @0p@ at this point since thieves only set their own queues pointers to @0p@ when stealing.
     564At no other point will a queue pointer be set to @0p@.
     565Since each worker owns a disjoint range of the queue array, it is impossible for @my_queue@ to be @0p@.
     566\item
     567Step 2 attempts to set the thief's queue pointer to @0p@ via @CAS@.
     568The @CAS@ will only fail if the thief's queue pointer is no longer equal to @my_queue@, which implies that this thief has become a victim and its queue has been stolen.
     569At this point the thief-turned-victim will fail and since it has not changed any state it just fails and returns false.
     570If the @CAS@ succeeds then the thief's queue pointer will now be @0p@.
     571Nulling the pointer is safe since only thieves look at other worker's queue ranges, and whenever thieves need to dereference a queue pointer they check for @0p@.
     572\item
     573Step 3 attempts to set the victim's queue pointer to be @my_queue@ via @CAS@.
     574If the @CAS@ succeeds then the victim's queue pointer has been set and swap can no longer fail.
     575If the @CAS@ fails then the thief's queue pointer must be restored to its previous value before returning.
     576\item
     577Step 4 sets the thief's queue pointer to be @vic_queue@ completing the swap.
    454578\end{enumerate}
    455579
    … …  
    458582\end{theorem}
    459583
    460 Correctness of the swap is shown through the existence of an invariant. 
    461 The invariant is that when a queue pointer is set to \code{0p} by a thief, then the next write to the pointer can only be performed by the same thief.
    462 To show that this invariant holds, it is shown that it is true at each step of the swap. 
    463 Step 0 and 1 do not write and as such they cannot invalidate the invariant of any other thieves. 
    464 In step 2 a thief attempts to write \code{0p} to one of their queue pointers.
    465 This queue pointer cannot be \code{0p}.
    466 As stated above, \code{my_queue} is never equal to \code{0p} since thieves will only write \code{0p} to queue pointers from their own queue range and all worker's queue ranges are disjoint.
    467 As such step 2 upholds the invariant since in a failure case no write occurs, and in the success case, the value of the queue pointer is guaranteed to not be 0p. 
    468 In step 3 the thief attempts to write \code{my_queue} to the victim's queue pointer.
    469 If the current value of the victim's queue pointer is \code{0p}, then the CAS will fail since \code{vic_queue} cannot be equal to \code{0p} because of the check in step 1.
    470 Therefore in the success case where the \code{CAS} succeeds, the value of the victim's queue pointer must not be \code{0p}.
    471 As such, the write will never overwrite a value of \code{0p}, hence the invariant is held in the \code{CAS} of step 3.
    472 The write back to the thief's queue pointer that happens in the failure case of step three and in step 4 hold the invariant since they are the subsequent write to a \code{0p} queue pointer and they are being set by the same thief that set the pointer to \code{0p}.
    473 
    474 Given this informal proof of invariance it can be shown that the successful swap is correct. 
    475 Once a thief atomically sets their queue pointer to be \code{0p} in step 2, the invariant guarantees that pointer will not change.
    476 As such, in the success case step 3 it is known that the value of the victim's queue pointer that was overwritten must be \code{vic_queue} due to the use of \code{CAS}.
    477 Given that pointers all have unique memory locations, this first write of the successful swap is correct since it can only occur when the pointer has not changed. 
    478 By the invariant the write back in the successful case is correct since no other worker can write to the \code{0p} pointer.
    479 
    480 In the failed case the outcome is correct in steps 1 and 2 since no writes have occured so the program state is unchanged.
    481 In the failed case of step 3 the program state is safely restored to its state it had prior to the \code{0p} write in step 2, thanks to the invariant that makes the write back to the \code{0p} pointer safe.
     584Correctness of the swap is shown through the existence of an invariant.
     585The invariant is that when a queue pointer is set to @0p@ by a thief, then the next write to the pointer can only be performed by the same thief.
     586To show that this invariant holds, it is shown that it is true at each step of the swap.
     587Step 0 and 1 do not write and as such they cannot invalidate the invariant of any other thieves.
     588In step 2 a thief attempts to write @0p@ to one of their queue pointers.
     589This queue pointer cannot be @0p@.
     590As stated above, @my_queue@ is never equal to @0p@ since thieves will only write @0p@ to queue pointers from their own queue range and all worker's queue ranges are disjoint.
     591As such step 2 upholds the invariant since in a failure case no write occurs, and in the success case, the value of the queue pointer is guaranteed to not be 0p.
     592In step 3 the thief attempts to write @my_queue@ to the victim's queue pointer.
     593If the current value of the victim's queue pointer is @0p@, then the CAS will fail since @vic_queue@ cannot be equal to @0p@ because of the check in step 1.
     594Therefore in the success case where the @CAS@ succeeds, the value of the victim's queue pointer must not be @0p@.
     595As such, the write will never overwrite a value of @0p@, hence the invariant is held in the @CAS@ of step 3.
     596The write back to the thief's queue pointer that happens in the failure case of step three and in step 4 hold the invariant since they are the subsequent write to a @0p@ queue pointer and they are being set by the same thief that set the pointer to @0p@.
     597
     598Given this informal proof of invariance it can be shown that the successful swap is correct.
     599Once a thief atomically sets their queue pointer to be @0p@ in step 2, the invariant guarantees that pointer will not change.
     600As such, in the success case step 3 it is known that the value of the victim's queue pointer that was overwritten must be @vic_queue@ due to the use of @CAS@.
     601Given that pointers all have unique memory locations, this first write of the successful swap is correct since it can only occur when the pointer has not changed.
     602By the invariant the write back in the successful case is correct since no other worker can write to the @0p@ pointer.
     603
     604In the failed case the outcome is correct in steps 1 and 2 since no writes have occurred so the program state is unchanged.
     605In the failed case of step 3 the program state is safely restored to its state it had prior to the @0p@ write in step 2, thanks to the invariant that makes the write back to the @0p@ pointer safe.
    482606
    483607\subsection{Stealing Guarantees}
    484608
    485609% C_TODO insert graphs for each proof
    486 Given that the stealing operation can potentially fail, it is important to discuss the guarantees provided by the stealing implementation. 
    487 Given a set of $N$ swaps a set of connected directed graphs can be constructed where each vertex is a queue and each edge is a swap directed from a thief queue to a victim queue. 
    488 Since each thief can only steal from one victim at a time, each vertex can only have at most one outgoing edge. 
     610Given that the stealing operation can potentially fail, it is important to discuss the guarantees provided by the stealing implementation.
     611Given a set of $N$ swaps a set of connected directed graphs can be constructed where each vertex is a queue and each edge is a swap directed from a thief queue to a victim queue.
     612Since each thief can only steal from one victim at a time, each vertex can only have at most one outgoing edge.
    489613A corollary that can be drawn from this, is that there are at most $V$ edges in this constructed set of connected directed graphs, where $V$ is the total number of vertices.
    490614
    … …  
    498622
    499623\begin{theorem}
    500 Given $M$ thieves queues all attempting to swap with one victim queue, and no other swaps occuring that involve these queues, at least one swap is guaranteed to succeed.
     624Given $M$ thieves queues all attempting to swap with one victim queue, and no other swaps occurring that involve these queues, at least one swap is guaranteed to succeed.
    501625\end{theorem}\label{t:one_vic}
    502626A graph of the $M$ thieves swapping with one victim discussed in this theorem is presented in Figure~\ref{f:M_one_swap}.
    503627\\
    504 First it is important to state that a thief will not attempt to steal from themselves. 
    505 As such, the victim here is not also a thief. 
    506 Stepping through the code in \ref{c:swap}, for all thieves steps 0-1 succeed since the victim is not stealing and will have no queue pointers set to be \code{0p}.
    507 Similarly for all thieves step 2 will succeed since no one is stealing from any of the thieves. 
    508 In step 3 the first thief to \code{CAS} will win the race and successfully swap the queue pointer.
    509 Since it is the first one to \code{CAS} and \code{CAS} is atomic, there is no way for the \code{CAS} to fail since no other thief could have written to the victim's queue pointer and the victim did not write to the pointer since they aren't stealing.
     628First it is important to state that a thief will not attempt to steal from themselves.
     629As such, the victim here is not also a thief.
     630Stepping through the code in \ref{c:swap}, for all thieves steps 0-1 succeed since the victim is not stealing and will have no queue pointers set to be @0p@.
     631Similarly for all thieves step 2 will succeed since no one is stealing from any of the thieves.
     632In step 3 the first thief to @CAS@ will win the race and successfully swap the queue pointer.
     633Since it is the first one to @CAS@ and @CAS@ is atomic, there is no way for the @CAS@ to fail since no other thief could have written to the victim's queue pointer and the victim did not write to the pointer since they aren't stealing.
    510634Hence at least one swap is guaranteed to succeed in this case.
    511635
    … …  
    519643
    520644\begin{theorem}
    521 Given $M$ > 1, ordered queues pointers all attempting to swap with the queue in front of them in the ordering, except the first queue, and no other swaps occuring that involve these queues, at least one swap is guaranteed to succeed.
     645Given $M$ > 1, ordered queues pointers all attempting to swap with the queue in front of them in the ordering, except the first queue, and no other swaps occurring that involve these queues, at least one swap is guaranteed to succeed.
    522646\end{theorem}\label{t:vic_chain}
    523647A graph of the chain of swaps discussed in this theorem is presented in Figure~\ref{f:chain_swap}.
    524648\\
    525 This is a proof by contradiction. 
    526 Assume no swaps occur. 
    527 Then all thieves must have failed at step 1, step 2 or step 3. 
    528 For a given thief $b$ to fail at step 1, thief $b + 1$ must have succeded at step 2 before $b$ executes step 0.
    529 Hence, not all thieves can fail at step 1. 
    530 Furthermore if a thief $b$ fails at step 1 it logically splits the chain into two subchains $0 <- b$ and $b + 1 <- M - 1$, where $b$ has become solely a victim since its swap has failed and it did not modify any state. 
    531 There must exist at least one chain containing two or more queues after since it is impossible for a split to occur both before and after a thief, since that requires failing at step 1 and succeeding at step 2. 
     649This is a proof by contradiction.
     650Assume no swaps occur.
     651Then all thieves must have failed at step 1, step 2 or step 3.
     652For a given thief $b$ to fail at step 1, thief $b + 1$ must have succeeded at step 2 before $b$ executes step 0.
     653Hence, not all thieves can fail at step 1.
     654Furthermore if a thief $b$ fails at step 1 it logically splits the chain into two subchains $0 <- b$ and $b + 1 <- M - 1$, where $b$ has become solely a victim since its swap has failed and it did not modify any state.
     655There must exist at least one chain containing two or more queues after since it is impossible for a split to occur both before and after a thief, since that requires failing at step 1 and succeeding at step 2.
    532656Hence, without loss of generality, whether thieves succeed or fail at step 1, this proof can proceed inductively.
    533657
    534 For a given thief $i$ to fail at step 2, it means that another thief $j$ had to have written to $i$'s queue pointer between $i$'s step 0 and step 2. 
    535 The only way for $j$ to write to $i$'s queue pointer would be if $j$ was stealing from $i$ and had successfully finished step 3. 
    536 If $j$ finished step 3 then the at least one swap was successful. 
    537 Therefore all thieves did not fail at step 2. 
    538 Hence all thieves must successfully complete step 2 and fail at step 3. 
    539 However, since the first worker, thief $0$, is solely a victim and not a thief, it does not change the state of any of its queue pointers. 
    540 Hence, in this case thief $1$ will always succeed in step 3 if all thieves succeed in step 2. 
     658For a given thief $i$ to fail at step 2, it means that another thief $j$ had to have written to $i$'s queue pointer between $i$'s step 0 and step 2.
     659The only way for $j$ to write to $i$'s queue pointer would be if $j$ was stealing from $i$ and had successfully finished step 3.
     660If $j$ finished step 3 then the at least one swap was successful.
     661Therefore all thieves did not fail at step 2.
     662Hence all thieves must successfully complete step 2 and fail at step 3.
     663However, since the first worker, thief $0$, is solely a victim and not a thief, it does not change the state of any of its queue pointers.
     664Hence, in this case thief $1$ will always succeed in step 3 if all thieves succeed in step 2.
    541665Thus, by contradiction with the earlier assumption that no swaps occur, at least one swap must succeed.
    542666
    … …  
    545669\centering
    546670\begin{tabular}{l|l}
    547 \subfloat[Cyclic Swap Graph]{\label{f:cyclic_swap}\input{diagrams/cyclic_swap.tikz}} & 
    548 \subfloat[Acyclic Swap Graph]{\label{f:acyclic_swap}\input{diagrams/acyclic_swap.tikz}} 
     671\subfloat[Cyclic Swap Graph]{\label{f:cyclic_swap}\input{diagrams/cyclic_swap.tikz}} &
     672\subfloat[Acyclic Swap Graph]{\label{f:acyclic_swap}\input{diagrams/acyclic_swap.tikz}}
    549673\end{tabular}
    550674\caption{Illustrations of cyclic and acyclic swap graphs.}
    … …  
    552676
    553677\begin{theorem}
    554 Given a set of $M > 1$ swaps occuring that form a single directed connected graph.
    555 At least one swap is guaranteed to suceed if and only if the graph does not contain a cycle.
     678Given a set of $M > 1$ swaps occurring that form a single directed connected graph.
     679At least one swap is guaranteed to succeed if and only if the graph does not contain a cycle.
    556680\end{theorem}\label{t:vic_cycle}
    557 Representations of cyclic and acylic swap graphs discussed in this theorem are presented in Figures~\ref{f:cyclic_swap} and \ref{f:acyclic_swap}.
     681Representations of cyclic and acyclic swap graphs discussed in this theorem are presented in Figures~\ref{f:cyclic_swap} and \ref{f:acyclic_swap}.
    558682\\
    559 First the reverse direction is proven. 
    560 If the graph does not contain a cycle, then there must be at least one successful swap. 
    561 Since the graph contains no cycles and is finite in size, then there must be a vertex $A$ with no outgoing edges. 
    562 The graph can then be formulated as a tree with $A$ at the top since each node only has at most one outgoing edge and there are no cycles. 
    563 The forward direction is proven by contradiction in a similar fashion to \ref{t:vic_chain}. 
    564 Assume no swaps occur. 
    565 Similar to \ref{t:vic_chain}, this graph can be inductively split into subgraphs of the same type by failure at step 1, so the proof proceeds without loss of generality. 
    566 Similar to \ref{t:vic_chain} the conclusion is drawn that all thieves must successfully complete step 2 for no swaps to occur, since for step 2 to fail, a different thief has to successfully complete step 3, which would imply a successful swap. 
    567 Hence, the only way forward is to assume all thieves successfully complete step 2. 
    568 Hence for there to be no swaps all thieves must fail step 3. 
    569 However, since $A$ has no outgoing edges, since the graph is connected there must be some $K$ such that $K < M - 1$ thieves are attempting to swap with $A$. 
    570 Since all $K$ thieves have passed step 2, similar to \ref{t:one_vic} the first one of the $K$ thieves to attempt step 3 is guaranteed to succeed. 
     683First the reverse direction is proven.
     684If the graph does not contain a cycle, then there must be at least one successful swap.
     685Since the graph contains no cycles and is finite in size, then there must be a vertex $A$ with no outgoing edges.
     686The graph can then be formulated as a tree with $A$ at the top since each node only has at most one outgoing edge and there are no cycles.
     687The forward direction is proven by contradiction in a similar fashion to \ref{t:vic_chain}.
     688Assume no swaps occur.
     689Similar to \ref{t:vic_chain}, this graph can be inductively split into subgraphs of the same type by failure at step 1, so the proof proceeds without loss of generality.
     690Similar to \ref{t:vic_chain} the conclusion is drawn that all thieves must successfully complete step 2 for no swaps to occur, since for step 2 to fail, a different thief has to successfully complete step 3, which would imply a successful swap.
     691Hence, the only way forward is to assume all thieves successfully complete step 2.
     692Hence for there to be no swaps all thieves must fail step 3.
     693However, since $A$ has no outgoing edges, since the graph is connected there must be some $K$ such that $K < M - 1$ thieves are attempting to swap with $A$.
     694Since all $K$ thieves have passed step 2, similar to \ref{t:one_vic} the first one of the $K$ thieves to attempt step 3 is guaranteed to succeed.
    571695Thus, by contradiction with the earlier assumption that no swaps occur, if the graph does not contain a cycle, at least one swap must succeed.
    572696
    573 The forward direction is proven by contrapositive. 
    574 If the graph contains a cycle then there exists a situation where no swaps occur. 
    575 This situation is constructed. 
    576 Since all vertices have at most one outgoing edge the cycle must be directed. 
    577 Furthermore, since the graph contains a cycle all vertices in the graph must have exactly one outgoing edge. 
    578 This is shown through construction of an aribtrary cyclic graph.
    579 The graph contains a directed cycle by definition, so the construction starts with $T$ vertices in a directed cycle. 
    580 Since the graph is connected, and each vertex has at most one outgoing edge, none of the vertices in the cycle have available outgoing edges to accomodate new vertices with no outgoing edges.
    581 Any vertices added to the graph must have an outgoing edge to connect, leaving the resulting graph with no available outgoing edges. 
    582 Thus, by induction all vertices in the graph must have exactly one outgoing edge. 
    583 Hence all vertices are thief queues. 
    584 Now consider the case where all thieves successfully complete step 0-1, and then they all complete step 2. 
    585 At this point all thieves are attempting to swap with a queue pointer whose value has changed to \code{0p}.
    586 If all thieves attempt the \code{CAS} before any write backs, then they will all fail.
    587 Thus, by contrapositive, if the graph contains a cycle then there exists a situation where no swaps occur. 
    588 Hence, at least one swap is guaranteed to suceed if and only if the graph does not contain a cycle.
     697The forward direction is proven by contrapositive.
     698If the graph contains a cycle then there exists a situation where no swaps occur.
     699This situation is constructed.
     700Since all vertices have at most one outgoing edge the cycle must be directed.
     701Furthermore, since the graph contains a cycle all vertices in the graph must have exactly one outgoing edge.
     702This is shown through construction of an arbitrary cyclic graph.
     703The graph contains a directed cycle by definition, so the construction starts with $T$ vertices in a directed cycle.
     704Since the graph is connected, and each vertex has at most one outgoing edge, none of the vertices in the cycle have available outgoing edges to accommodate new vertices with no outgoing edges.
     705Any vertices added to the graph must have an outgoing edge to connect, leaving the resulting graph with no available outgoing edges.
     706Thus, by induction all vertices in the graph must have exactly one outgoing edge.
     707Hence all vertices are thief queues.
     708Now consider the case where all thieves successfully complete step 0-1, and then they all complete step 2.
     709At this point all thieves are attempting to swap with a queue pointer whose value has changed to @0p@.
     710If all thieves attempt the @CAS@ before any write backs, then they will all fail.
     711Thus, by contrapositive, if the graph contains a cycle then there exists a situation where no swaps occur.
     712Hence, at least one swap is guaranteed to succeed if and only if the graph does not contain a cycle.
    589713
    590714% C_TODO: go through and use \paragraph to format to make it look nicer
    591715\subsection{Victim Selection}\label{s:victimSelect}
    592 In any work stealing algorithm thieves have some heuristic to determine which victim to choose from. 
    593 Choosing this algorithm is difficult and can have implications on performance. 
    594 There is no one selection heuristic that is known to be the best on all workloads. 
    595 Recent work focuses on locality aware scheduling in actor systems\cite{barghi18}\cite{wolke17}. 
    596 However, while locality aware scheduling provides good performance on some workloads, something as simple as randomized selection performs better on other workloads\cite{barghi18}. 
    597 Since locality aware scheduling has been explored recently, this work introduces a heuristic called \textbf{longest victim} and compares it to randomized work stealing. 
    598 The longest victim heuristic maintains a timestamp per worker thread that is updated every time a worker attempts to steal work.
    599 Thieves then attempt to steal from the thread with the oldest timestamp. 
    600 This means that if two thieves look to steal at the same time, they likely will attempt to steal from the same victim. 
    601 This does increase the chance at contention between thieves, however given that workers have multiple queues under them, often in the tens or hundreds of queues per worker it is rare for two queues to attempt so steal the same queue. 
    602 Furthermore in the case they attempt to steal the same queue at least one of them is guaranteed to successfully steal the queue as shown in Theorem \ref{t:one_vic}. 
    603 Additonally, the longest victim heuristic makes it very improbable that the no swap scenario presented in Theorem \ref{t:vic_cycle} manifests.
    604 Given the longest victim heuristic, for a cycle to manifest it would require all workers to attempt to steal in a short timeframe. 
    605 This is the only way that more than one thief could choose another thief as a victim, since timestamps are only updated upon attempts to steal. 
     716In any work stealing algorithm thieves have some heuristic to determine which victim to choose from.
     717Choosing this algorithm is difficult and can have implications on performance.
     718There is no one selection heuristic that is known to be the best on all workloads.
     719Recent work focuses on locality aware scheduling in actor systems\cite{barghi18}\cite{wolke17}.
     720However, while locality aware scheduling provides good performance on some workloads, something as simple as randomized selection performs better on other workloads\cite{barghi18}.
     721Since locality aware scheduling has been explored recently, this work introduces a heuristic called \textbf{longest victim} and compares it to randomized work stealing.
     722The longest victim heuristic maintains a timestamp per executor threads that is updated every time a worker attempts to steal work.
     723Thieves then attempt to steal from the thread with the oldest timestamp.
     724This means that if two thieves look to steal at the same time, they likely will attempt to steal from the same victim.
     725This does increase the chance at contention between thieves, however given that workers have multiple queues under them, often in the tens or hundreds of queues per worker it is rare for two queues to attempt so steal the same queue.
     726Furthermore in the case they attempt to steal the same queue at least one of them is guaranteed to successfully steal the queue as shown in Theorem \ref{t:one_vic}.
     727Additionally, the longest victim heuristic makes it very improbable that the no swap scenario presented in Theorem \ref{t:vic_cycle} manifests.
     728Given the longest victim heuristic, for a cycle to manifest it would require all workers to attempt to steal in a short timeframe.
     729This is the only way that more than one thief could choose another thief as a victim, since timestamps are only updated upon attempts to steal.
    606730In this case, the probability of lack of any successful swaps is a non issue, since it is likely that these steals were not important if all workers are trying to steal.
    607731
    608 \section{Safety and Productivity}
    609 \CFA's actor system comes with a suite of safety and productivity features. 
    610 Most of these features are present in \CFA's debug mode, but are removed when code is compiled in nodebug mode. 
     732\section{Safety and Productivity}\label{s:SafetyProductivity}
     733\CFA's actor system comes with a suite of safety and productivity features.
     734Most of these features are present in \CFA's debug mode, but are removed when code is compiled in nodebug mode.
    611735The suit of features include the following.
    612736
    613737\begin{itemize}
    614 \item Static-typed message sends. 
     738\item Static-typed message sends.
    615739If an actor does not support receiving a given message type, the actor program is rejected at compile time, allowing unsupported messages to never be sent to actors.
    616 \item Detection of message sends to Finished/Destroyed/Deleted actors. 
    617 All actors have a ticket that assigns them to a respective queue. 
     740\item Detection of message sends to Finished/Destroyed/Deleted actors.
     741All actors have a ticket that assigns them to a respective queue.
    618742The maximum integer value of the ticket is reserved to indicate that an actor is dead, and subsequent message sends result in an error.
    619 \item Actors made before the executor can result in undefined behaviour since an executor needs to be created beforehand so it can give out the tickets to actors. 
     743\item Actors made before the executor can result in undefined behaviour since an executor needs to be created beforehand so it can give out the tickets to actors.
    620744As such, this is detected and an error is printed.
    621 \item When an executor is created, the queues are handed out to worker threads in round robin order.
    622 If there are fewer queues than worker threads, then some workers will spin and never do any work.
    623 There is no reasonable use case for this behaviour so an error is printed if the number of queues is fewer than the number of worker threads.
    624 \item A warning is printed when messages are deallocated without being sent. 
    625 Since the \code{Finished} allocation status is unused for messages, it is used internally to detect if a message has been sent.
     745\item When an executor is created, the queues are handed out to executor threads in round robin order.
     746If there are fewer queues than executor threads, then some workers will spin and never do any work.
     747There is no reasonable use case for this behaviour so an error is printed if the number of queues is fewer than the number of executor threads.
     748\item A warning is printed when messages are deallocated without being sent.
     749Since the @Finished@ allocation status is unused for messages, it is used internally to detect if a message has been sent.
    626750Deallocating a message without sending it could indicate to a user that they are touching freed memory later, or it could point out extra allocations that could be removed.
    627751\end{itemize}
    628752
    629 In addition to these features, \CFA's actor system comes with a suite of statistics that can be toggled on and off. 
    630 These statistics have minimal impact on the actor system's performance since they are counted on a per worker thread basis.
    631 During shutdown of the actor system they are aggregated, ensuring that the only atomic instructions used by the statistics counting happen at shutdown. 
     753In addition to these features, \CFA's actor system comes with a suite of statistics that can be toggled on and off.
     754These statistics have minimal impact on the actor system's performance since they are counted on a per executor threads basis.
     755During shutdown of the actor system they are aggregated, ensuring that the only atomic instructions used by the statistics counting happen at shutdown.
    632756The statistics measured are as follows.
    633757
    634758\begin{description}
    635759\item[\LstBasicStyle{\textbf{Actors Created}}]
    636 Actors created. 
     760Actors created.
    637761Includes both actors made by the main and ones made by other actors.
    638762\item[\LstBasicStyle{\textbf{Messages Sent}}]
    639 Messages sent and received. 
    640 Includes termination messages send to the worker threads.
     763Messages sent and received.
     764Includes termination messages send to the executor threads.
    641765\item[\LstBasicStyle{\textbf{Gulps}}]
    642 Gulps that occured across the worker threads.
     766Gulps that occurred across the executor threads.
    643767\item[\LstBasicStyle{\textbf{Average Gulp Size}}]
    644768Average number of messages in a gulped queue.
    645769\item[\LstBasicStyle{\textbf{Missed gulps}}]
    646 Occurences where a worker missed a gulp due to the concurrent queue processing by another worker.
     770Occurrences where a worker missed a gulp due to the concurrent queue processing by another worker.
    647771\item[\LstBasicStyle{\textbf{Steal attempts}}]
    648 Worker threads attempts to steal work. 
     772Worker threads attempts to steal work.
    649773
    650774\item[\LstBasicStyle{\textbf{Steal failures (no candidates)}}]
    … …  
    658782\end{description}
    659783
    660 These statistics enable a user of \CFA's actor system to make informed choices about how to configure their executor, or how to structure their actor program. 
    661 For example, if there is a lot of messages being stolen relative to the number of messages sent, it could indicate to a user that their workload is heavily imbalanced across worker threads.
     784These statistics enable a user of \CFA's actor system to make informed choices about how to configure their executor, or how to structure their actor program.
     785For example, if there is a lot of messages being stolen relative to the number of messages sent, it could indicate to a user that their workload is heavily imbalanced across executor threads.
    662786In another example, if the average gulp size is very high, it could indicate that the executor could use more queue sharding.
    663787
    664788% C_TODO cite poison pill messages and add languages
    665 Another productivity feature that is included is a group of poison-pill messages. 
    666 Poison-pill messages are common across actor systems, including Akka and ProtoActor \cite{}. 
    667 Poison-pill messages inform an actor to terminate. 
    668 In \CFA, due to the allocation of actors and lack of garbage collection, there needs to be a suite of poison-pills. 
    669 The messages that \CFA provides are \code{DeleteMsg}, \code{DestroyMsg}, and \code{FinishedMsg}.
    670 These messages are supported on all actor types via inheritance and when sent to an actor, the actor takes the corresponding allocation action after receiving the message. 
    671 Note that any pending messages to the actor will still be sent. 
     789Another productivity feature that is included is a group of poison-pill messages.
     790Poison-pill messages are common across actor systems, including Akka and ProtoActor \cite{}.
     791Poison-pill messages inform an actor to terminate.
     792In \CFA, due to the allocation of actors and lack of garbage collection, there needs to be a suite of poison-pills.
     793The messages that \CFA provides are @DeleteMsg@, @DestroyMsg@, and @FinishedMsg@.
     794These messages are supported on all actor types via inheritance and when sent to an actor, the actor takes the corresponding allocation action after receiving the message.
     795Note that any pending messages to the actor will still be sent.
    672796It is still the user's responsibility to ensure that an actor does not receive any messages after termination.
    673797
    … …  
    675799\CAP{I will update the figures to have the larger font size and different line markers once we start editing this chapter.}
    676800The performance of \CFA's actor system is tested using a suite of microbenchmarks, and compared with other actor systems.
    677 Most of the benchmarks are the same as those presented in \ref{}, with a few additions. 
     801Most of the benchmarks are the same as those presented in \ref{}, with a few additions.
    678802% C_TODO cite actor paper
    679 At the time of this work the versions of the actor systems are as follows. 
    680 \CFA 1.0, \uC 7.0.0, Akka Typed 2.7.0, CAF 0.18.6, and ProtoActor-Go v0.0.0-20220528090104-f567b547ea07. 
     803At the time of this work the versions of the actor systems are as follows.
     804\CFA 1.0, \uC 7.0.0, Akka Typed 2.7.0, CAF 0.18.6, and ProtoActor-Go v0.0.0-20220528090104-f567b547ea07.
    681805Akka Classic is omitted as Akka Typed is their newest version and seems to be the direction they are headed in.
    682806The experiments are run on
    … …  
    688812\end{list}
    689813
    690 The benchmarks are run on up to 48 cores. 
    691 On the Intel, when going beyond 24 cores there is the choice to either hop sockets or to use hyperthreads. 
    692 Either choice will cause a blip in performance trends, which can be seen in the following performance figures. 
     814The benchmarks are run on up to 48 cores.
     815On the Intel, when going beyond 24 cores there is the choice to either hop sockets or to use hyperthreads.
     816Either choice will cause a blip in performance trends, which can be seen in the following performance figures.
    693817On the Intel the choice was made to hyperthread instead of hopping sockets for experiments with more than 24 cores.
    694818
    695 All benchmarks presented are run 5 times and the median is taken. 
    696 Error bars showing the 95\% confidence intervals are drawn on each point on the graphs. 
    697 If the confidence bars are small enough, they may be obscured by the point. 
    698 In this section \uC will be compared to \CFA frequently, as the actor system in \CFA was heavily based off \uC's actor system. 
    699 As such the peformance differences that arise are largely due to the contributions of this work.
     819All benchmarks presented are run 5 times and the median is taken.
     820Error bars showing the 95\% confidence intervals are drawn on each point on the graphs.
     821If the confidence bars are small enough, they may be obscured by the point.
     822In this section \uC will be compared to \CFA frequently, as the actor system in \CFA was heavily based off \uC's actor system.
     823As such the performance differences that arise are largely due to the contributions of this work.
    700824
    701825\begin{table}[t]
    … …  
    708832\begin{tabular}{*{5}{r|}r}
    709833        & \multicolumn{1}{c|}{\CFA (100M)} & \multicolumn{1}{c|}{CAF (10M)} & \multicolumn{1}{c|}{Akka (100M)} & \multicolumn{1}{c|}{\uC (100M)} & \multicolumn{1}{c@{}}{ProtoActor (100M)} \\
    710         \hline                                                                                                                                                 
     834        \hline
    711835        AMD             & \input{data/pykeSendStatic} \\
    712         \hline                                                                                                                                                 
     836        \hline
    713837        Intel   & \input{data/nasusSendStatic}
    714838\end{tabular}
    … …  
    721845\begin{tabular}{*{5}{r|}r}
    722846        & \multicolumn{1}{c|}{\CFA (20M)} & \multicolumn{1}{c|}{CAF (2M)} & \multicolumn{1}{c|}{Akka (2M)} & \multicolumn{1}{c|}{\uC (20M)} & \multicolumn{1}{c@{}}{ProtoActor (2M)} \\
    723         \hline                                                                                                                                                 
     847        \hline
    724848        AMD             & \input{data/pykeSendDynamic} \\
    725         \hline                                                                                                                                                 
     849        \hline
    726850        Intel   & \input{data/nasusSendDynamic}
    727851\end{tabular}
    … …  
    729853
    730854\subsection{Message Sends}
    731 Message sending is the key component of actor communication. 
    732 As such latency of a single message send is the fundamental unit of fast-path performance for an actor system. 
    733 The following two microbenchmarks evaluate the average latency for a static actor/message send and a dynamic actor/message send. 
    734 Static and dynamic refer to the allocation of the message and actor. 
    735 In the static send benchmark a message and actor are allocated once and then the message is sent to the same actor repeatedly until it has been sent 100 million (100M) times. 
    736 The average latency per message send is then calculated by dividing the duration by the number of sends. 
    737 This benchmark evaluates the cost of message sends in the actor use case where all actors and messages are allocated ahead of time and do not need to be created dynamically during execution. 
     855Message sending is the key component of actor communication.
     856As such latency of a single message send is the fundamental unit of fast-path performance for an actor system.
     857The following two microbenchmarks evaluate the average latency for a static actor/message send and a dynamic actor/message send.
     858Static and dynamic refer to the allocation of the message and actor.
     859In the static send benchmark a message and actor are allocated once and then the message is sent to the same actor repeatedly until it has been sent 100 million (100M) times.
     860The average latency per message send is then calculated by dividing the duration by the number of sends.
     861This benchmark evaluates the cost of message sends in the actor use case where all actors and messages are allocated ahead of time and do not need to be created dynamically during execution.
    738862The CAF static send benchmark only sends a message 10M times to avoid extensively long run times.
    739863
    740 In the dynamic send benchmark the same experiment is performed, with the change that with each send a new actor and message is allocated. 
    741 This evaluates the cost of message sends in the other common actor pattern where actors and message are created on the fly as the actor program tackles a workload of variable or unknown size. 
     864In the dynamic send benchmark the same experiment is performed, with the change that with each send a new actor and message is allocated.
     865This evaluates the cost of message sends in the other common actor pattern where actors and message are created on the fly as the actor program tackles a workload of variable or unknown size.
    742866Since dynamic sends are more expensive, this benchmark repeats the actor/message creation and send 20M times (\uC, \CFA), or 2M times (Akka, CAF, ProtoActor), to give an appropriate benchmark duration.
    743867
    744 The results from the static/dynamic send benchmarks are shown in Figures~\ref{t:StaticActorMessagePerformance} and \ref{t:DynamicActorMessagePerformance} respectively. 
    745 \CFA leads the charts in both benchmarks, largely due to the copy queue removing the majority of the envelope allocations. 
    746 In the static send benchmark all systems except CAF have static send costs that are in the same ballpark, only varying by ~70ns. 
    747 In the dynamic send benchmark all systems experience slower message sends, as expected due to the extra allocations. 
    748 However, Akka and ProtoActor, slow down by a more significant margin than the \uC and \CFA. 
     868The results from the static/dynamic send benchmarks are shown in Figures~\ref{t:StaticActorMessagePerformance} and \ref{t:DynamicActorMessagePerformance} respectively.
     869\CFA leads the charts in both benchmarks, largely due to the copy queue removing the majority of the envelope allocations.
     870In the static send benchmark all systems except CAF have static send costs that are in the same ballpark, only varying by ~70ns.
     871In the dynamic send benchmark all systems experience slower message sends, as expected due to the extra allocations.
     872However, Akka and ProtoActor, slow down by a more significant margin than the \uC and \CFA.
    749873This is likely a result of Akka and ProtoActor's garbage collection, which can suffer from hits in performance for allocation heavy workloads, whereas \uC and \CFA have explicit allocation/deallocation.
    750874
    751875\subsection{Work Stealing}
    752 \CFA's actor system has a work stealing mechanism which uses the longest victim heuristic, introduced in Section~ref{s:victimSelect}. 
     876\CFA's actor system has a work stealing mechanism which uses the longest victim heuristic, introduced in Section~ref{s:victimSelect}.
    753877In this performance section, \CFA with the longest victim heuristic is compared with other actor systems on the benchmark suite, and is separately compared with vanilla non-stealing \CFA and \CFA with randomized work stealing.
    754878
    … …  
    779903\end{figure}
    780904
    781 There are two benchmarks in which \CFA's work stealing is solely evaluated. 
    782 The main goal of introducing work stealing to \CFA's actor system is to eliminate the pathological unbalanced cases that can present themselves in a system without some form of load balancing. 
    783 The following two microbenchmarks construct two such pathological cases, and compare the work stealing variations of \CFA. 
    784 The balance benchmarks adversarily takes advantage of the round robin assignment of actors to load all actors that will do work on specific cores and create 'dummy' actors that terminate after a single message send on all other cores.
    785 The workload on the loaded cores is the same as the executor benchmark described in \ref{s:executorPerf}, but with fewer rounds. 
    786 The balance-one benchmark loads all the work on a single core, whereas the balance-multi loads all the work on half the cores (every other core). 
    787 Given this layout, one expects the ideal speedup of work stealing in the balance-one case to be $N / N - 1$ where $N$ is the number of threads. 
    788 In the balance-multi case the ideal speedup is 0.5. 
    789 Note that in the balance-one benchmark the workload is fixed so decreasing runtime is expected. 
     905There are two benchmarks in which \CFA's work stealing is solely evaluated.
     906The main goal of introducing work stealing to \CFA's actor system is to eliminate the pathological unbalanced cases that can present themselves in a system without some form of load balancing.
     907The following two microbenchmarks construct two such pathological cases, and compare the work stealing variations of \CFA.
     908The balance benchmarks adversarially takes advantage of the round robin assignment of actors to load all actors that will do work on specific cores and create 'dummy' actors that terminate after a single message send on all other cores.
     909The workload on the loaded cores is the same as the executor benchmark described in \ref{s:executorPerf}, but with fewer rounds.
     910The balance-one benchmark loads all the work on a single core, whereas the balance-multi loads all the work on half the cores (every other core).
     911Given this layout, one expects the ideal speedup of work stealing in the balance-one case to be $N / N - 1$ where $N$ is the number of threads.
     912In the balance-multi case the ideal speedup is 0.5.
     913Note that in the balance-one benchmark the workload is fixed so decreasing runtime is expected.
    790914In the balance-multi experiment, the workload increases with the number of cores so an increasing or constant runtime is expected.
    791915
    792 On both balance microbenchmarks slightly less than ideal speedup compared to the non stealing variation is achieved by both the random and longest victim stealing heuristics. 
    793 On the balance-multi benchmark \ref{f:BalanceMultiAMD},\ref{f:BalanceMultiIntel} the random heuristic outperforms the longest victim. 
    794 This is likely a result of the longest victim heuristic having a higher stealing cost as it needs to maintain timestamps and look at all timestamps before stealing. 
     916On both balance microbenchmarks slightly less than ideal speedup compared to the non stealing variation is achieved by both the random and longest victim stealing heuristics.
     917On the balance-multi benchmark \ref{f:BalanceMultiAMD},\ref{f:BalanceMultiIntel} the random heuristic outperforms the longest victim.
     918This is likely a result of the longest victim heuristic having a higher stealing cost as it needs to maintain timestamps and look at all timestamps before stealing.
    795919Additionally, a performance cost can be observed when hyperthreading kicks in in Figure~\ref{f:BalanceMultiIntel}.
    796920
    797 In the balance-one benchmark on AMD \ref{f:BalanceOneAMD}, the performance bottoms out at 32 cores onwards likely due to the amount of work becoming less than the cost to steal it and move it across cores and cache. 
    798 On Intel \ref{f:BalanceOneIntel}, above 32 cores the performance gets worse for all variants due to hyperthreading. 
     921In the balance-one benchmark on AMD \ref{f:BalanceOneAMD}, the performance bottoms out at 32 cores onwards likely due to the amount of work becoming less than the cost to steal it and move it across cores and cache.
     922On Intel \ref{f:BalanceOneIntel}, above 32 cores the performance gets worse for all variants due to hyperthreading.
    799923Note that the non stealing variation of balance-one will slow down marginally as the cores increase due to having to create more dummy actors on the inactive cores during startup.
    800924
    801925\subsection{Executor}\label{s:executorPerf}
    802 The microbenchmarks in this section are designed to stress the executor. 
    803 The executor is the scheduler of an actor system and is responsible for organizing the interaction of worker threads to service the needs of a workload.
    804 In the executor benchmark, 40'000 actors are created and assigned a group. 
    805 Each group of actors is a group of 100 actors who send and receive 100 messages from all other actors in their group. 
    806 Each time an actor completes all their sends and receives, they are done a round. 
    807 After all groups have completed 400 rounds the system terminates. 
    808 This microbenchmark is designed to flood the executor with a large number of messages flowing between actors. 
     926The microbenchmarks in this section are designed to stress the executor.
     927The executor is the scheduler of an actor system and is responsible for organizing the interaction of executor threads to service the needs of a workload.
     928In the executor benchmark, 40'000 actors are created and assigned a group.
     929Each group of actors is a group of 100 actors who send and receive 100 messages from all other actors in their group.
     930Each time an actor completes all their sends and receives, they are done a round.
     931After all groups have completed 400 rounds the system terminates.
     932This microbenchmark is designed to flood the executor with a large number of messages flowing between actors.
    809933Given there is no work associated with each message, other than sending more messages, the intended bottleneck of this experiment is the executor message send process.
    810934
    … …  
    822946\end{figure}
    823947
    824 The results of the executor benchmark in Figures~\ref{f:ExecutorIntel} and \ref{f:ExecutorAMD} show \CFA with the lowest runtime relative to its peers. 
    825 The difference in runtime between \uC and \CFA is largely due to the usage of the copy queue described in Section~\ref{s:copyQueue}. 
    826 The copy queue both reduces and consolidates allocations, heavily reducing contention on the memory allocator. 
    827 Additionally, due to the static typing in \CFA's actor system, it is able to get rid of expensive dynamic casts that occur in \uC to disciminate messages by type.
    828 Note that dynamic casts are ususally not very expensive, but relative to the high performance of the rest of the implementation of the \uC actor system, the cost is significant.
     948The results of the executor benchmark in Figures~\ref{f:ExecutorIntel} and \ref{f:ExecutorAMD} show \CFA with the lowest runtime relative to its peers.
     949The difference in runtime between \uC and \CFA is largely due to the usage of the copy queue described in Section~\ref{s:copyQueue}.
     950The copy queue both reduces and consolidates allocations, heavily reducing contention on the memory allocator.
     951Additionally, due to the static typing in \CFA's actor system, it is able to get rid of expensive dynamic casts that occur in \uC to discriminate messages by type.
     952Note that dynamic casts are usually not very expensive, but relative to the high performance of the rest of the implementation of the \uC actor system, the cost is significant.
    829953
    830954\begin{figure}
    … …  
    841965\end{figure}
    842966
    843 When comparing the \CFA stealing heuristics in Figure~\ref{f:cfaExecutorAMD} it can be seen that the random heuristic falls slightly behind the other two, but in Figure~\ref{f:cfaExecutorIntel} the runtime of all heuristics are nearly identical to eachother.
     967When comparing the \CFA stealing heuristics in Figure~\ref{f:cfaExecutorAMD} it can be seen that the random heuristic falls slightly behind the other two, but in Figure~\ref{f:cfaExecutorIntel} the runtime of all heuristics are nearly identical to each other.
    844968
    845969\begin{figure}
    … …  
    856980\end{figure}
    857981
    858 The repeat microbenchmark also evaluates the executor. 
    859 It stresses the executor's ability to withstand contention on queues, as it repeatedly fans out messages from a single client to 100000 servers who then all respond to the client. 
    860 After this scatter and gather repeats 200 times the benchmark terminates. 
    861 The messages from the servers to the client will likely all come in on the same queue, resulting in high contention. 
    862 As such this benchmark will not scale with the number of processors, since more processors will result in higher contention. 
    863 In Figure~\ref{f:RepeatAMD} we can see that \CFA performs well compared to \uC, however by less of a margin than the executor benchmark. 
    864 One factor in this result is that the contention on the queues poses a significant bottleneck. 
     982The repeat microbenchmark also evaluates the executor.
     983It stresses the executor's ability to withstand contention on queues, as it repeatedly fans out messages from a single client to 100000 servers who then all respond to the client.
     984After this scatter and gather repeats 200 times the benchmark terminates.
     985The messages from the servers to the client will likely all come in on the same queue, resulting in high contention.
     986As such this benchmark will not scale with the number of processors, since more processors will result in higher contention.
     987In Figure~\ref{f:RepeatAMD} we can see that \CFA performs well compared to \uC, however by less of a margin than the executor benchmark.
     988One factor in this result is that the contention on the queues poses a significant bottleneck.
    865989As such the gains from using the copy queue are much less apparent.
    866990
    … …  
    8791003
    8801004In Figure~\ref{f:RepeatIntel} \uC and \CFA are very comparable.
    881 In comparison with the other systems \uC does well on the repeat benchmark since it does not have work stealing. 
    882 The client of this experiment is long running and maintains a lot of state, as it needs to know the handles of all the servers. 
    883 When stealing the client or its respective queue (in \CFA's inverted model), moving the client incurs a high cost due to cache invalidation. 
    884 As such stealing the client can result in a hit in performance. 
     1005In comparison with the other systems \uC does well on the repeat benchmark since it does not have work stealing.
     1006The client of this experiment is long running and maintains a lot of state, as it needs to know the handles of all the servers.
     1007When stealing the client or its respective queue (in \CFA's inverted model), moving the client incurs a high cost due to cache invalidation.
     1008As such stealing the client can result in a hit in performance.
    8851009
    8861010This result is shown in Figure~\ref{f:cfaRepeatAMD} and \ref{f:cfaRepeatIntel} where the no-stealing version of \CFA performs better than both stealing variations.
    887 In particular on the Intel machine in Figure~\ref{f:cfaRepeatIntel}, the cost of stealing is higher, which can be seen in the vertical shift of Akka, CAF and CFA results in Figure~\ref{f:RepeatIntel} (\uC and ProtoActor do not have work stealing). 
     1011In particular on the Intel machine in Figure~\ref{f:cfaRepeatIntel}, the cost of stealing is higher, which can be seen in the vertical shift of Akka, CAF and CFA results in Figure~\ref{f:RepeatIntel} (\uC and ProtoActor do not have work stealing).
    8881012The shift for CAF is particularly large, which further supports the hypothesis that CAF's work stealing is particularly eager.
    889 In both the executor and the repeat benchmark CAF performs poorly. 
    890 It is hypothesized that CAF has an aggressive work stealing algorithm, that eagerly attempts to steal. 
    891 This results in poor performance in benchmarks with small messages containing little work per message. 
    892 On the other hand, in \ref{f:MatrixAMD} CAF performs much better since each message has a large amount of work, and few messages are sent, so the eager work stealing allows for the clean up of loose ends to occur faster. 
    893 This hypothesis stems from experimentation with \CFA. 
    894 CAF uses a randomized work stealing heuristic. 
     1013In both the executor and the repeat benchmark CAF performs poorly.
     1014It is hypothesized that CAF has an aggressive work stealing algorithm, that eagerly attempts to steal.
     1015This results in poor performance in benchmarks with small messages containing little work per message.
     1016On the other hand, in \ref{f:MatrixAMD} CAF performs much better since each message has a large amount of work, and few messages are sent, so the eager work stealing allows for the clean up of loose ends to occur faster.
     1017This hypothesis stems from experimentation with \CFA.
     1018CAF uses a randomized work stealing heuristic.
    8951019In \CFA if the system is tuned so that it steals work much more eagerly with a randomized it was able to replicate the results that CAF achieves in the matrix benchmark, but this tuning performed much worse on all other microbenchmarks that we present, since they all perform a small amount of work per message.
    8961020
    … …  
    8991023        \setlength{\extrarowheight}{2pt}
    9001024        \setlength{\tabcolsep}{5pt}
    901        
     1025
    9021026        \caption{Executor Program Memory High Watermark}
    9031027        \label{t:ExecutorMemory}
    9041028        \begin{tabular}{*{5}{r|}r}
    9051029                & \multicolumn{1}{c|}{\CFA} & \multicolumn{1}{c|}{CAF} & \multicolumn{1}{c|}{Akka} & \multicolumn{1}{c|}{\uC} & \multicolumn{1}{c@{}}{ProtoActor} \\
    906                 \hline                                                                                                                                                 
     1030                \hline
    9071031                AMD             & \input{data/pykeExecutorMem} \\
    908                 \hline                                                                                                                                                 
     1032                \hline
    9091033                Intel   & \input{data/nasusExecutorMem}
    9101034        \end{tabular}
    9111035\end{table}
    9121036
    913 Figure~\ref{t:ExecutorMemory} shows the high memory watermark of the actor systems when running the executor benchmark on 48 cores. 
    914 \CFA has a high watermark relative to the other non-garbage collected systems \uC, and CAF. 
    915 This is a result of the copy queue data structure, as it will overallocate storage and not clean up eagerly, whereas the per envelope allocations will always allocate exactly the amount of storage needed.
     1037Figure~\ref{t:ExecutorMemory} shows the high memory watermark of the actor systems when running the executor benchmark on 48 cores.
     1038\CFA has a high watermark relative to the other non-garbage collected systems \uC, and CAF.
     1039This is a result of the copy queue data structure, as it will over-allocate storage and not clean up eagerly, whereas the per envelope allocations will always allocate exactly the amount of storage needed.
    9161040
    9171041\subsection{Matrix Multiply}
    918 The matrix benchmark evaluates the actor systems in a practical application, where actors concurrently multiplies two matrices. 
     1042The matrix benchmark evaluates the actor systems in a practical application, where actors concurrently multiplies two matrices.
    9191043The majority of the computation in this benchmark involves computing the final matrix, so this benchmark stresses the actor systems' ability to have actors run work, rather than stressing the executor or message sending system.
    9201044
    … …  
    9241048\end{displaymath}
    9251049
    926 The benchmark uses input matrices $X$ and $Y$ that are both $3072$ by $3072$ in size. 
    927 An actor is made for each row of $X$ and is passed via message the information needed to calculate a row of the result matrix $Z$. 
    928 
    929 
    930 Given that the bottleneck of the benchmark is the computation of the result matrix, it follows that the results in Figures~\ref{f:MatrixAMD} and \ref{f:MatrixIntel} are clustered closer than other experiments. 
    931 In Figure~\ref{f:MatrixAMD} \uC and \CFA have identical performance and in Figure~\ref{f:MatrixIntel} \uC pulls ahead og \CFA after 24 cores likely due to costs associated with work stealing while hyperthreading.
    932 As mentioned in \ref{s:executorPerf}, it is hypothesized that CAF performs better in this benchmark compared to others due to its eager work stealing implementation. 
     1050The benchmark uses input matrices $X$ and $Y$ that are both $3072$ by $3072$ in size.
     1051An actor is made for each row of $X$ and is passed via message the information needed to calculate a row of the result matrix $Z$.
     1052
     1053
     1054Given that the bottleneck of the benchmark is the computation of the result matrix, it follows that the results in Figures~\ref{f:MatrixAMD} and \ref{f:MatrixIntel} are clustered closer than other experiments.
     1055In Figure~\ref{f:MatrixAMD} \uC and \CFA have identical performance and in Figure~\ref{f:MatrixIntel} \uC pulls ahead of \CFA after 24 cores likely due to costs associated with work stealing while hyperthreading.
     1056As mentioned in \ref{s:executorPerf}, it is hypothesized that CAF performs better in this benchmark compared to others due to its eager work stealing implementation.
    9331057In Figures~\ref{f:cfaMatrixAMD} and \ref{f:cfaMatrixIntel} there is little negligible performance difference across \CFA stealing heuristics.
    9341058
Note: See TracChangeset for help on using the changeset viewer.