source: doc/theses/colby_parsons_MMAth/text/actors.tex @ fee4436

% ======================================================================
% ======================================================================
\chapter{Actors}\label{s:actors}
% ======================================================================
% ======================================================================

Actors 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.
Hence, actors are in the realm of \gls{impl_concurrency}, where programmers write concurrent code without dealing with explicit thread creation or interaction.
Actor message-passing is similar to channels, but with more abstraction, so there is no shared data to protect, making actors amenable to a distributed environment.
Actors are often used for high-performance computing and other data-centric problems, where the ease of use and scalability of an actor system provides an advantage over channels.

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.
Before 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.

\section{Actor Model}
The \Newterm{actor model} is a concurrent paradigm where an actor is used as the fundamental building-block for computation, and the data for computation is distributed to actors in the form of messages~\cite{Hewitt73}.
An actor is composed of a \Newterm{mailbox} (message queue) and a set of \Newterm{behaviours} that receive from the mailbox to perform work.
Actors execute asynchronously upon receiving a message and can modify their own state, make decisions, spawn more actors, and send messages to other actors.
Conceptually, actor systems can be thought of in terms of channels, where each actor's mailbox is a channel.
However, a mailbox behaves like an unbounded channel, which differs from the fixed size channels discussed in the previous chapter.
Because the actor model is implicit concurrency, its strength is that it abstracts away many details and concerns needed in other concurrent paradigms.
For example, mutual exclusion and locking are rarely relevant concepts in an actor model, as actors typically only operate on local state.

\subsection{Classic Actor System}
An implementation of the actor model with a theatre (group) of actors is called an \Newterm{actor system}.
Actor systems largely follow the actor model, but can differ in some ways.

In an actor system, an actor does not have a thread.
An 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.
The default number of executor threads is often proportional to the number of computer cores to achieve good performance.
An 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{Section~\ref{s:ActorSystem}}.

While the semantics of message \emph{send} is asynchronous, the implementation may be synchronous or a combination.
The default semantics for message \emph{receive} is \gls{fifo}, so an actor receives messages from its mailbox in temporal (arrival) order.
% however, messages sent among actors arrive in any order.
Some 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.
Some 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 may require additional locking).
For non-\gls{fifo} service, some notion of fairness (eventual progress) should exist, otherwise messages have a high latency or starve, \ie are never received.
% Finally, some actor systems provide multiple typed-mailboxes, which then lose the actor-\lstinline{become} mechanism \see{Section~\ref{s:SafetyProductivity}}.
%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$ arrive at actor $j$ in the order they were sent.
Another way an actor system varies from the model is allowing access to shared global-state.
When this occurs, it complicates the implementation as this breaks any implicit mutual-exclusion guarantees when only accessing local-state.

\begin{figure}
\begin{tabular}{l|l}
\subfloat[Actor-centric system]{\label{f:standard_actor}\input{diagrams/standard_actor.tikz}} &
\subfloat[Message-centric system]{\label{f:inverted_actor}\raisebox{.1\height}{\input{diagrams/inverted_actor.tikz}}}
\end{tabular}
\caption{Classic and inverted actor implementation approaches with sharded queues.}
\end{figure}

\subsection{\CFA Actor System}
Figure~\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}.
The 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.
The 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.
Sharding significantly decreases contention among executor threads adding and removing actors to/from a queue.
Finally, 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 add messages.
When an actor receives a message in its mailbox, the actor is marked ready and scheduled by a thread to run the actor's current behaviour on the message(s).

% cite parallel theatre and our paper
Figure \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}.
This design is \Newterm{inverted} because actors belong to a message queue, whereas in the classic approach a message queue belongs to each actor.
Now a message send must query the actor to know which message queue to post the message to.
Again, 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.
Therefore, the messages (mailboxes) are sharded and executor threads schedule each message, which points to its corresponding actor.
Here, an actor's messages are permanently assigned to one queue to ensure \gls{fifo} receiving and/or reduce searching for specific actor/messages.
Since multiple actors belong to each message queue, actor messages are interleaved on a queue, but individually in FIFO order.
% In this inverted actor system instead of each executor threads owning a queue of actors, they each own a queue of messages.
% In this scheme work is consumed from their queue and executed by underlying threads.
The 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.
Again, this extra level of sharding is to reduce queue contention.
% The arrows from the message queues to the actors in the diagram indicate interleaved messages addressed to each actor.

The actor system in \CFA uses a message-centric design, adopts several features from my prior actor work in \uC~\cite{Buhr22} but is implemented in \CFA. My contributions to the prior actor work include introducing queue gulping, developing an actor benchmark suite, and extending promise support for actors. Furthermore, I improved the design and implementation of the \uC actor system to greatly increase its performance. As such, the actor system in \CFA started as a copy of the \uC implementation, which was then refined. This work adds the following new \CFA contributions:
\begin{enumerate}[topsep=5pt,itemsep=3pt,parsep=0pt]
\item
Provide insight into the impact of envelope allocation in actor systems \see{Section~\ref{s:envelope}}.
In 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.
This 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.
This dynamic allocation occurs once per message sent.
Unfortunately, the high rate of message sends in an actor system results in significant contention on the memory allocator.
A novel data structure is introduced to consolidate allocations to improve performance by minimizing allocator contention.

\item
Improve performance of the inverted actor system using multiple approaches to minimize contention on queues, such as queue gulping and avoiding atomic operations.

\item
Introduce work stealing in the inverted actor system.
Work stealing in an actor-centric system involves stealing one or more actors among executor threads.
In the inverted system, the notion of stealing message queues is introduced.
The queue stealing is implemented such that the act of stealing work does not contend with non-stealing executor threads running actors.

\item
Introduce 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.

\item
Provide a suite of safety and productivity features including static-typing, detection of erroneous message sends, statistics tracking, and more.
\end{enumerate}

\section{\CFA Actor}\label{s:CFAActor}
\CFA is not an object oriented language and it does not have \gls{rtti}.
As such, all message sends and receives among actors can only occur using static type-matching, as in Typed-Akka~\cite{AkkaTyped}.
Figure~\ref{f:BehaviourStyles} contrasts dynamic and static type-matching.
Figure~\ref{l:dynamic_style} shows the dynamic style with a heterogeneous message receive and an indirect dynamic type-discrimination for message processing.
Figure~\ref{l:static_style} shows the static style with a homogeneous message receive and a direct static type-discrimination for message processing.
The static-typing style is safer because of the static check and faster because there is no dynamic type-discrimination.
The dynamic-typing style is more flexible because multiple kinds of messages can be handled in a behaviour condensing the processing code.

\begin{figure}
\centering

\begin{lrbox}{\myboxA}
\begin{cfa}[morekeywords=case]
allocation receive( message & msg ) {
        case( @msg_type1@, msg ) {      // discriminate type
                ... msg_d-> ...;        // msg_type1 msg_d
        } else case( @msg_type2@, msg ) {
                ... msg_d-> ...;        // msg_type2 msg_d
        ...
}
\end{cfa}
\end{lrbox}

\begin{lrbox}{\myboxB}
\begin{cfa}
allocation receive( @msg_type1@ & msg ) {
        ... msg ...;
}
allocation receive( @msg_type2@ & msg ) {
        ... msg ...;
}
...
\end{cfa}
\end{lrbox}

\subfloat[dynamic typing]{\label{l:dynamic_style}\usebox\myboxA}
\hspace*{10pt}
\vrule
\hspace*{10pt}
\subfloat[static typing]{\label{l:static_style}\usebox\myboxB}
\caption{Behaviour Styles}
\label{f:BehaviourStyles}
\end{figure}

\begin{figure}
\centering

\begin{cfa}
// actor
struct my_actor {
        @inline actor;@                                                 $\C[3.25in]{// Plan-9 C inheritance}$
};
// messages
struct str_msg {
        char str[12];
        @inline message;@                                               $\C{// Plan-9 C inheritance}$
};
void ?{}( str_msg & this, char * str ) { strcpy( this.str, str ); }  $\C{// constructor}$
struct int_msg {
        int i;
        @inline message;@                                               $\C{// Plan-9 C inheritance}$
};
// behaviours
allocation receive( my_actor &, @str_msg & msg@ ) with(msg) {
        sout | "string message \"" | str | "\"";
        return Nodelete;                                                $\C{// actor not finished}$
}
allocation receive( my_actor &, @int_msg & msg@ ) with(msg) {
        sout | "integer message" | i;
        return Nodelete;                                                $\C{// actor not finished}$
}
int main() {
        str_msg str_msg{ "Hello World" };               $\C{// constructor call}$
        int_msg int_msg{ 42 };                                  $\C{// constructor call}$
        start_actor_system();                                   $\C{// sets up executor}$
        my_actor actor;                                                 $\C{// default constructor call}$
        @actor | str_msg | int_msg;@                    $\C{// cascade sends}$
        @actor | int_msg;@                                              $\C{// send}$
        @actor | finished_msg;@                                 $\C{// send => terminate actor (builtin Poison-Pill)}$
        stop_actor_system();                                    $\C{// waits until actors finish}\CRT$
} // deallocate actor, int_msg, str_msg
\end{cfa}
\caption{\CFA Actor Syntax}
\label{f:CFAActor}
\end{figure}

Figure~\ref{f:CFAActor} shows a complete \CFA actor example, which is discussed in detail.
The actor type @my_actor@ is a @struct@ that inherits from the base @actor@ @struct@ via the @inline@ keyword.
This inheritance style is the Plan-9 C-style \see{Section~\ref{s:Inheritance}}.
Similarly, the message types @str_msg@ and @int_msg@ are @struct@s that inherits from the base @message@ @struct@ via the @inline@ keyword.
Only @str_msg@ needs a constructor to copy the C string;
@int_msg@ is initialized using its \CFA auto-generated constructors.
There are two matching @receive@ (behaviour) routines that process the corresponding typed messages.
Both @receive@ routines use a @with@ clause so message fields are not qualified \see{Section~\ref{s:with}} and return @Nodelete@ indicating the actor is not finished \see{Section~\ref{s:ActorBehaviours}}.
Also, all messages are marked with @Nodelete@ as their default allocation state.
The program main begins by creating two messages on the stack.
Then the executor system is started by calling @start_actor_system@ \see{Section~\ref{s:ActorSystem}}.
Now an actor is created on the stack and four messages are sent to it using operator @?|?@ \see{Section~\ref{s:Operators}}.
The last message is the builtin @finish_msg@, which returns @Finished@ to an executor thread, causing it to remove the actor from the actor system \see{end of Section~\ref{s:ActorBehaviours}}.
The call to @stop_actor_system@ blocks the program main until all actors are finished and removed from the actor system.
The program main ends by deleting the actor and the two messages from the stack.
The output for the program is:
\begin{cfa}
string message "Hello World"
integer message 42
integer message 42
\end{cfa}

\subsection{Actor Behaviours}\label{s:ActorBehaviours}
In general, a behaviour for some derived actor and derived message type is defined with the following signature:
\begin{cfa}
allocation receive( my_actor & receiver, my_msg & msg )
\end{cfa}
where @my_actor@ and @my_msg@ inherit from types @actor@ and @message@, respectively.
The return value of @receive@ must be a value from enumerated type, @allocation@:
\begin{cfa}
enum allocation { Nodelete, Delete, Destroy, Finished };
\end{cfa}
The values represent a set of actions that dictate what the executor does with an actor or message after a given behaviour returns.
For actors, the @receive@ routine returns the @allocation@ status to the executor, which takes the appropriate action.
For messages, either the default allocation, @Nodelete@, or any changed value in the message is examined by the executor, which takes the appropriate action.
Message state is updated via a call to:
\begin{cfa}
void set_allocation( message & this, allocation state );
\end{cfa}

In detail, the actions taken by an executor for each of the @allocation@ values are:

\noindent@Nodelete@
tells the executor that no action is to be taken with regard to an actor or message.
This status is used when an actor continues receiving messages or a message is reused.

\noindent@Delete@
tells the executor to call the object's destructor and deallocate (delete) the object.
This status is used with dynamically allocated actors and messages when they are not reused.

\noindent@Destroy@
tells the executor to call the object's destructor, but not deallocate the object.
This status is used with dynamically allocated actors and messages whose storage is reused.

\noindent@Finished@
tells the executor to mark the respective actor as finished executing, but not call the object's destructor nor deallocate the object.
This status is used when actors or messages are global or stack allocated, or a programmer wants to manage deallocation themselves.
Note that for messages there is no difference between allocations @Nodelete@ and @Finished@ because both tell the executor to do nothing to the message.
Hence, @Finished@ is implicitly changed to @Nodelete@ in a message constructor, and @Nodelete@ is used internally for message error-checking \see{Section~\ref{s:SafetyProductivity}}.
Therefore, reading a message's allocation status after setting to @Finished@ may be either @Nodelete@ (after construction) or @Finished@ (after explicitly setting using @set_allocation@).

For the actor system to terminate, all actors must have returned a status other than @Nodelete@.
After an actor is terminated, it is erroneous to send messages to it.
Similarly,  after a message is terminated, it cannot be sent to an actor.
Note that it is safe to construct an actor or message with a status other than @Nodelete@, since the executor only examines the allocation action \emph{after} a behaviour returns.

\subsection{Actor Envelopes}\label{s:envelope}
As 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.
Because a C program manages message lifetime, messages cannot be copied for each send, otherwise who manages the copies?
Therefore, it is up to the actor program to manage message life-time across receives.
However, for a message to appear on multiple message queues, it needs an arbitrary number of associated destination behaviours.
Hence, there is the concept of an envelope, which is dynamically allocated on each send, that wraps a message with any extra implementation fields needed to persist between send and receive.
Managing the envelope is straightforward because it is created at the send and deleted after the receive, \ie there is 1:1 relationship for an envelope and a many to one relationship for a message.

% In actor systems, messages are sent and received by actors.
% When a actor receives a message it executes its behaviour that is associated with that message type.
% 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.
% 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.
% All these requirements are fulfilled by a construct called an envelope.
% The envelope wraps up the unit of work and also stores any information needed by data structures such as link fields.

% One may ask, "Could the link fields and other information be stored in the message?".
% This is a good question to ask since messages also need to have a lifetime that persists beyond the work it delivers.
% 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.
% 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.

\subsection{Actor System}\label{s:ActorSystem}
The calls to @start_actor_system@, and @stop_actor_system@ mark the start and end of a \CFA actor system.
The call to @start_actor_system@ sets up an executor and executor threads for the actor system.
It is possible to have multiple start/stop scenarios in a program.

@start_actor_system@ has three overloaded signatures that vary the executor's configuration:

\noindent@void start_actor_system()@
configures the executor to implicitly use all preallocated kernel-threads (processors), \ie the processors created by the program main prior to starting the actor system.
For example, the program main declares at the start:
\begin{cfa}
processor p[3];
\end{cfa}
which provides a total of 4 threads (3 + initial processor) for use by the executor.
When 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.

\noindent@void start_actor_system( size_t num_thds )@
configures the number of executor threads to @num_thds@, with the same message queue sharding.

\begin{sloppypar}
\noindent@void start_actor_system( executor & this )@
allows the programmer to explicitly create and configure an executor for use by the actor system.
Executor configuration options are discussed in Section~\ref{s:executor}.
\end{sloppypar}

\noindent
All 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.

\subsection{Actor Send}\label{s:ActorSend}
All message sends are done using the vertical-bar (bit-or) operator, @?|?@, similar to the syntax of the \CFA stream I/O.
One way to provide a generic operator is through the \CFA type system:
\begin{cfa}
actor & ?|?( actor &, message & ) { // base actor and message types
        // boilerplate to send message to executor mail queue
}
actor | str_msg | int_msg;   // rewritten: ?|?( ?|?( actor, int_msg ), str_msg )
\end{cfa}
In the \CFA type system, calls to this routine work for any pair of parameters that inherit from the @actor@ and @message@ types via Plan-9 inheritance.
However, within the body the routine, all type information about the derived actor and message is lost (type erasure), so this approach is unable to find the right @receive@ routine to put in the envelope.

If \CFA had a fully-fledged virtual system, the generic @?|?@ routine would work, since the virtual system could dynamically select the derived @receive@ routine via virtual dispatch.
\CFA does have a preliminary form of virtual routines, but it is not mature enough for use in this work, so a different approach is needed.

Without virtuals, the idiomatic \CFA way to create the generic @?|?@ routine is using @forall@:
\begin{cfa}
// forall types A, M that have a receive that returns allocation
forall( A &, M & | { allocation receive( A &, M & ); } ) 
A & ?|?( A &, M & ) { // actor and message types
        // boilerplate to send message to executor mail queue
}
\end{cfa}
This approach should work.
However, the \CFA type system is still a work in progress, and there is a nontrivial bug where inherited routines are not recognized by @forall@.
For example, Figure~\ref{f:type_problem} shows type @B@ has an inherited @foo@ routine through type @A@ and should find the @bar@ routine defined via the @forall@, but does not due the type-system bug.

\begin{figure}
\begin{cfa}
struct A {};
struct B { inline A; }
void foo( A & a ) { ... }

// for all types that have a foo routine here is a bar routine
forall( T & | { void foo( T & ); } ) 
void bar( T & t ) { ... }

int main() {
        B b;
        foo( b ); // B has a foo so it should find a bar via the forall
        bar( b ); // compilation error, no bar found for type B
}
\end{cfa}
\caption{\CFA Type-System Problem}
\label{f:type_problem}
\end{figure}

Users could be expected to write the @?|?@ routines, but this approach is error prone and creates maintenance issues.
As a stopgap until the \CFA type-system matures, a workaround was created using a template-like approach, where the compiler generates a matching @?|?@ routine for each @receive@ routine it finds with the correct actor/message type-signature.
This workaround is outside of the type system, but performs a type-system like action.
The workaround requires no annotation or additional code to be written by users;
thus, it resolves the maintenance and error problems.
It should be possible to seamlessly transition the workaround into any updated version of the \CFA type-system.

Figure~\ref{f:send_gen} shows the generated send routine for the @int_msg@ receive in Figure~\ref{f:CFAActor}.
Operator @?|?@ has the same parameter signature as the corresponding @receive@ routine and returns an @actor@ so the operator can be cascaded.
The routine sets @rec_fn@ to the matching @receive@ routine using the left-hand type to perform the selection.
Then the routine packages the actor and message, along with the receive routine into an envelope.
Finally, the envelope is added to the executor queue designated by the actor using the executor routine @send@.

\begin{figure}
\begin{cfa}
$\LstCommentStyle{// from Figure~\ref{f:CFAActor}}$
struct my_actor { inline actor; };                                              $\C[3.75in]{// actor}$
struct int_msg { inline message; int i; };                              $\C{// message}$
allocation receive( @my_actor &, int_msg & msg@ ) {...} $\C{// receiver}$

// compiler generated send operator
typedef allocation (*receive_t)( actor &, message & );
actor & ?|?( @my_actor & receiver, int_msg & msg@ ) {
        allocation (*rec_fn)( my_actor &, int_msg & ) = @receive@; // deduce receive routine
        request req{ (actor *)&receiver, (message *)&msg, (receive_t)rec_fn };
        send( receiver, req );                                                          $\C{// queue message for execution}\CRT$
        return receiver;
}
\end{cfa}
\caption{Generated Send Operator}
\label{f:send_gen}
\end{figure}

Figure~\ref{f:PoisonPillMessages} shows three builtin \Newterm{poison-pill} messages and receive routines used to terminate actors, depending on how an actor is allocated: @Delete@, @Destroy@ or @Finished@.
Poison-pill messages are common across actor systems, including Akka and ProtoActor~\cite{Akka,ProtoActor} to suggest or force actor termination.
For example, in Figure~\ref{f:CFAActor}, the builtin @finished_msg@ message and receive are used to terminate the actor because the actor is allocated on the stack, so no deallocation actions are performed by the executor.
Note that assignment is used to initialize these messages rather than constructors because the constructor changes the allocation to @Nodelete@ for error checking

\begin{figure}
\begin{cfa}
message __base_msg_finished $@$= { .allocation_ : Finished }; // use C initialization
struct delete_msg_t { inline message; } delete_msg = __base_msg_finished;
struct destroy_msg_t { inline message; } destroy_msg = __base_msg_finished;
struct finished_msg_t { inline message; } finished_msg = __base_msg_finished;

allocation receive( actor & this, delete_msg_t & msg ) { return Delete; }
allocation receive( actor & this, destroy_msg_t & msg ) { return Destroy; }
allocation receive( actor & this, finished_msg_t & msg ) { return Finished; }
\end{cfa}
\caption{Builtin Poison-Pill Messages}
\label{f:PoisonPillMessages}
\end{figure}

\subsection{Actor Termination}\label{s:ActorTerm}
During a message send, the receiving actor and message being sent are stored via pointers in the envelope.
These pointers have the base actor and message types, so type information of the derived actor and message is lost and must be recovered later when the typed receive routine is called.
After the receive routine is done, the executor must clean up the actor and message according to their allocation status.
If the allocation status is @Delete@ or @Destroy@, the appropriate destructor must be called by the executor.
This requirement poses a problem: the derived type of the actor or message is not available to the executor, but it needs to call the derived destructor.
This requires downcasting from the base type to the derived type, which requires a virtual system.
To accomplish the downcast, a rudimentary destructor-only virtual system was implemented in \CFA as part of this work.
This virtual system is used via Plan-9 inheritance of the @virtual_dtor@ type, shown in Figure~\ref{f:VirtDtor}.
The @virtual_dtor@ type maintains a pointer to the start of the object, and a pointer to the correct destructor.
When a type inherits @virtual_dtor@, the compiler adds code to its destructor to intercepted any destructor calls along this segment of the inheritance tree and restart at the appropriate destructor for that object.

\begin{figure}
\centering

\begin{lrbox}{\myboxA}
\begin{cfa}
struct base { inline virtual_dtor; };
void ^?{}( base & ) { sout | "^base"; }
struct intermediate { inline base; };
void ^?{}( intermediate & ) { sout | "^intermediate"; }
struct derived { inline intermediate; };
void ^?{}( derived & ) { sout | "^derived"; }

int main() {
        base & b;
        intermediate i;
        derived d1, d2, d3;
        intermediate & ri = d2;
        base & rb = d3;
        // explicit destructor calls
        ^d1{};  sout | nl;
        ^ri{};   sout | nl;
        ^rb{};  sout | nl;
} // ^i, ^b
\end{cfa}
\end{lrbox}

\begin{lrbox}{\myboxB}
\begin{cfa}
^derived
^intermediate
^base

^derived
^intermediate
^base

^derived
^intermediate
^base

^intermediate
^base




\end{cfa}

\end{lrbox}
\subfloat[Destructor calls]{\label{l:destructor_calls}\usebox\myboxA}
\hspace*{10pt}
\vrule
\hspace*{10pt}
\subfloat[Output]{\usebox\myboxB}

\caption{\CFA Virtual Destructor}
\label{f:VirtDtor}
\end{figure}

While this virtual destructor system was built for this work, it is general and can be used with any type in \CFA.
Actors and messages opt into this system by inheriting the @virtual_dtor@ type, which allows the executor to call the right destructor without knowing the derived actor or message type.
Again, it should be possible to seamlessly transition this workaround into any updated version of the \CFA type-system.

\section{\CFA Executor}\label{s:executor}
This section describes the basic architecture of the \CFA executor.
An executor of an actor system is the scheduler that organizes where actor behaviours are run and how messages are sent and delivered.
In \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$).
This approach reduces contention by spreading message delivery among the $M$ queues rather than $N$, while still maintaining actor \gls{fifo} message-delivery semantics.
The only extra overhead is each executor cycling (usually round-robin) through its $M$/$N$ queues.
The goal is to achieve better performance and scalability for certain kinds of actor applications by reducing executor locking.
Note that 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.

\begin{figure}
\begin{center}
\input{diagrams/gulp.tikz}
\end{center}
\caption{Queue Gulping Mechanism}
\label{f:gulp}
\end{figure}

Each executor thread iterates over its own message queues until it finds one with messages.
At this point, the executor thread atomically \gls{gulp}s the queue, meaning it moves the contents of message queue to a local queue of the executor thread.
Gulping moves the contents of the message queue as a batch rather than removing individual elements.
An example of the queue gulping operation is shown in the right side of Figure \ref{f:gulp}, where an executor thread gulps queue 0 and begins to process it locally.
This step allows the executor thread to process the local queue without any atomics until the next gulp.
Other executor threads can continue adding to the ends of the executor thread's message queues.
In detail, an executor thread performs a test-and-gulp, non-atomically checking if a queue is non-empty, before attempting to gulp it.
If an executor misses an non-empty queue due to a race, it eventually finds the queue after cycling through its message queues.
This approach minimizes costly lock acquisitions.

Processing a local queue involves: removing a unit of work from the queue, dereferencing the actor pointed-to by the work unit, running the actor's behaviour on the work-unit message, examining the returned allocation status from the @receive@ routine for the actor and internal status in the delivered message, and taking the appropriate actions.
Since 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.
As each actor is created or terminated by an executor thread, it atomically increments/decrements a global counter.
When an executor decrements the counter to zero, it sets a global boolean variable that is checked by each executor thread when it has no work.
Once a executor threads sees the flag is set it stops running.
After all executors stop, the actor system shutdown is complete.

\subsection{Copy Queue}\label{s:copyQueue}
Unfortunately, the frequent allocation of envelopes for each send results in heavy contention on the memory allocator.
This contention is reduced using a novel data structure, called a \Newterm{copy queue}.
The copy queue is a thin layer over a dynamically sized array that is designed with the envelope use-case in mind.
A copy queue supports the typical queue operations of push/pop but in a different way from a typical array-based queue.

The copy queue is designed to take advantage of the \gls{gulp}ing pattern, giving an amortized runtime cost for each push/pop operation of $O(1)$.
In 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.
Since 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.
As such, during pop operations there is no need to shift array elements.
Instead, 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)$.
Push operations are amortized $O(1)$ since pushes may cause doubling reallocations of the underlying dynamic-sized array (like \CC @vector@).
Note that the copy queue is similar to a circular buffer, but has a key difference.
After all elements are popped, the end of the queue is set back to index zero, whereas a standard circular buffer would leave the end in the same location.
Using a standard circular buffer would incur an additional $O(n)$ cost of fixing the buffer after a doubling reallocation.

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.
For many workloads, the copy queues reallocate and grow in size to facilitate the average number of messages in flight and there are no further dynamic allocations.
The downside of this approach is that more storage is allocated than needed, \ie each copy queue is only partially full.
Comparatively, 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.
Additionally, bursty workloads can cause the copy queues to allocate a large amount of space to accommodate the throughput peak, even if most of that storage is not needed for the rest of the workload's execution.

To mitigate memory wastage, a reclamation scheme is introduced.
Initially, the memory reclamation na\"ively reclaims one index of the array per \gls{gulp}, if the array size is above a low fixed threshold.
However, this approach has a problem.
The high memory watermark nearly doubled!
The issue is highlighted with an example.
Assume a fixed throughput workload, where a queue never has more than 19 messages at a time.
If the copy queue starts with a size of 10, it ends up doubling at some point to size 20 to accommodate 19 messages.
However, after 2 gulps and subsequent reclamations the array size is 18.
The next time 19 messages are enqueued, the array size is doubled to 36!
To avoid this issue, a second check is added.
Reclamation only occurs if less than half of the array is utilized.
This check achieves a lower total storage and overall memory utilization compared to the non-reclamation copy queues.
However, the use of copy queues still incurs a higher memory cost than list-based queueing, but the increase in memory usage is reasonable considering the performance gains \see{Section~\ref{s:actor_perf}}.

\section{Work Stealing}\label{s:steal}
Work stealing is a scheduling strategy to provide \Newterm{load balancing}.
The goal is to increase resource utilization by having an idle thread steal work from a working thread.
While there are multiple parts in a work-stealing scheduler, two important components are the stealing mechanism and victim selection.

\subsection{Stealing Mechanism}
In work stealing, the stealing worker is called the \Newterm{thief} and the worker being stolen from is called the \Newterm{victim}.
% Workers consume actors from their ready queue and execute their behaviours.
% Through these behaviours, a worker inserts messages onto its own and other worker ready-queues.
To steal, a thief takes work from a victim's ready queue, so work stealing always results in a potential increase in contention on ready queues between the victim gulping from a queue and the thief stealing the queue.
This contention can reduce the victim's throughput.
Note that the data structure used for the ready queue is not discussed since the largest cost is the mutual exclusion and its duration for safely performing the queue operations.

The stealing mechanism in this work differs from most work-stealing actor-systems because of the message-centric (inverted) actor-system.
Actor systems, such as Akka~\cite{Akka} and CAF~\cite{CAF} using actor-centric systems, steal by dequeuing an actor from a non-empty actor ready-queue and enqueue\-ing to an empty ready-queue.
% As an example, in CAF, the sharded actor ready queue is a set of double-ended queues (dequeues).
In \CFA, the actor work-stealing implementation is unique because of the message-centric system.
With this approach, it is impractical to steal actors because an actor's messages are distributed in temporal order along the message queue.
To ensure sequential actor execution and \gls{fifo} message delivery in a message-centric system, stealing requires finding and removing \emph{all} of an actor's messages, and inserting them consecutively in another message queue.
This operation is $O(N)$ with a non-trivial constant.
The only way for work stealing to become practical is to shard each worker's message queue \see{Section~\ref{s:executor}}, which also reduces contention, and to steal queues to eliminate queue searching.

Given queue stealing, the goal of the presented stealing implementation is to have an essentially zero-contention-cost stealing mechanism.
Achieving this goal requires work stealing to have minimal (practically no) effect on the performance of the victim.
The implication is that thieves cannot contend with a victim, and that a victim should perform no stealing related work unless it becomes a thief.
In theory, this goal is not achievable, but practical results show the goal is nearly achieved.

One important lesson learned while working on \uC actors~\cite{Buhr22} and through discussions with fellow student Thierry Delisle, who examined work-stealing for user-threads in his Ph.D.~\cite{Delisle22}, is \emph{not} to aggressively steal.
With reasonable workloads, being a thief should be a temporary state, \ie eventually work appears on the thief's ready-queues and it returns to normal operation.
Furthermore, the act of \emph{looking} to find work is invasive, possibly disrupting multiple victims.
Therefore, stealing should be done lazily in case work appears for the thief and to minimize disruption of victims.
Note that the cost of stealing is not crucial for the thief because it does not have anything else to do except poll or block.

The outline for lazy-stealing by a thief is: select a victim, scan its queues once, and return immediately if a queue is stolen.
The thief then assumes its normal operation of scanning over its own queues looking for work, where stolen work is placed at the end of the scan.
Hence, only one victim is affected and there is a reasonable delay between stealing events as the thief scans its ready queue looking for its own work before potentially stealing again.
This lazy examination by the thief has a low perturbation cost for victims, while still finding work in a moderately loaded system.
In all work-stealing algorithms, there is the pathological case where there is too little work and too many workers;
this scenario can only be handled by putting workers to sleep or deleting them.
This case is not examined in this work.

In more detail, the \CFA work-stealing algorithm begins by iterating over its message queues twice without finding any work before it tries to steal a queue from another worker.
Stealing a queue is done atomically with a few atomic instructions that only create contention with other stealing workers not the victim.
The complexity in the implementation is that victim gulping does not take the mailbox queue;
rather it atomically transfers the mailbox nodes to another queue leaving the mailbox empty, as discussed in Section~\ref{s:executor}.
Hence, the original mailbox is always available for new message deliveries.
However, this transfer logically subdivides the mailbox into two separate queues, and during this period, the mailbox cannot be stolen;
otherwise there are two threads simultaneously running messages on an actor in the two parts of the mailbox queue.
To solve this problem, an atomic gulp also marks the mailbox queue as subdivided making it ineligible for stealing.
Hence, a thief checks if a queue is eligible and non-empty before attempting an atomic steal of a queue.

Figure~\ref{f:steal} shows the queue architecture and stealing mechanism.
Internally, the mailbox queues are accessed through two arrays of size $N$, which are shared among all workers.
There is an array of mailbox queues, @mailboxes@, and an array of pointers to the mailboxes, @worker_queues@:
\begin{cfa}
struct work_queue {
        spinlock_t mutex_lock;                  $\C[2.75in]{// atomicity for queue operations}$
        copy_queue * owned_queue;               $\C{// copy queue}$
        copy_queue * c_queue;                   $\C{// current queue}$
        volatile bool being_processed;  $\C{// flag to prevent concurrent processing}$
};
work_queue * mailboxes;                         $\C{// master array of work request queues}$
work_queue ** worker_queues;            $\C{// secondary array of work queues to allow for swapping}\CRT$
\end{cfa}
A send inserts a request at the end of one of @mailboxes@.
A steal swaps two pointers in \snake{worker_queues}.
Conceptually, @worker_queues@ represents the ownership relation between mailboxes and workers.
Given $M$ workers and $N$ mailboxes, each worker owns a contiguous $M$/$N$ block of pointers in @worker_queues@.
When a worker gulps, it dereferences one of the pointers in its section of @worker_queues@ and then gulps the queue from the mailbox it points at.
To transfer ownership of a mailbox from one worker to another, a pointer from each of the workers' ranges are swapped.
This structure provides near-complete separation of stealing and gulping/send operations.
As such, operations can happen on @mailboxes@ independent of stealing, which avoids almost all contention between thief and victim threads.

\begin{figure}
\begin{center}
\input{diagrams/steal.tikz}
\end{center}
\caption{Queue Stealing Mechanism}
\label{f:steal}
\end{figure}

To steal a queue, a thief does the following:
\begin{enumerate}[topsep=5pt,itemsep=3pt,parsep=0pt]
\item
chooses a victim.
Victim selection heuristics are independent of the stealing mechanism and discussed in Section~\ref{s:victimSelect}.

\item
scan the victim's $M$/$N$ range of @worker_queues@ and non-atomically checks each mailbox to see if it is eligible and non-empty.
If a match is found, the thief attempts to steal the mailbox by swapping the appropriate victim worker-queue pointer with an empty thief's pointer, where the pointers come from the victim's and thief's ranges, respectively.
% The swap races to interchange the appropriate victim's mail-queue pointer with an empty mail-queue pointer in the thief's @worker_queues@ range.
This swap can fail if another thief steals the queue, which is discussed further in Section~\ref{s:swap}.
% Note that a thief never exceeds its $M$/$N$ worker range because it is always exchanging queues with other workers.
If no appropriate victim mailbox is found, no swap is attempted.
Note that since the mailbox checks happen non-atomically, the thieves effectively guess which mailbox is ripe for stealing.
The thief may read stale data and can end up stealing an ineligible or empty mailbox.
This is not a correctness issue and is addressed in Section~\ref{s:steal_prob}, but the steal will likely not be productive.
These unproductive steals are uncommon, but do occur with some frequency, and are a tradeoff that is made to achieve minimal victim contention.

\item
stops searching after a successful mailbox steal, a failed mailbox steal, or all mailboxes in the victim's range are examined.
The thief then resumes normal execution and ceases being a thief.
Hence, it iterates over its own worker queues because new messages may have arrived during stealing, including ones in the potentially stolen queue.
Stealing is only repeated after the worker completes two consecutive iterations over its message queues without finding work.
\end{enumerate}

\subsection{Stealing Problem}\label{s:steal_prob}
Each queue access (send or gulp) involving any worker (thief or victim) is protected using spinlock @mutex_lock@.
However, to achieve the goal of almost zero contention for the victim, it is necessary that the thief does not acquire any queue spinlocks in the stealing protocol.
The victim critical-section is gulping a queue, which involves two steps:
\begin{cfa}
temp = worker_queues[x];
// preemption and steal
transfer( local_queue, temp->c_queue );   // atomically sets being_processed
\end{cfa}
where @transfer@ gulps the work from @c_queue@ to the victim's @local_queue@ and leaves @c_queue@ empty, partitioning the mailbox.
Specifically,
\begin{enumerate}[topsep=5pt,itemsep=3pt,parsep=0pt]
\item
The victim must dereference its current mailbox pointer from @worker_queues@.
\item
The victim calls @transfer@ to gulp from the mailbox.
\end{enumerate}
If the victim is preempted after the dereference, a thief can steal the mailbox pointer before the victim calls @transfer@.
The thief then races ahead, transitions back to a victim, searches its mailboxes, finds the stolen non-empty mailbox, and gulps this queue.
The original victim now continues and gulps from the stolen mailbox pointed to by its dereference, even though the thief has logically subdivided this mailbox by gulping it.
At this point, the mailbox has been subdivided a second time, and the victim and thief are possibly processing messages sent to the same actor, which violates mutual exclusion and the message-ordering guarantee.
Preventing this race requires either a lock acquire or an atomic operation on the victim's fast-path to guarantee the victim's mailbox dereferenced pointer is not stale.
However, any form of locking here creates contention between thief and victim.

The alternative to locking is allowing the race and resolving it lazily.
% As mentioned, there is a race between a victim gulping and a thief stealing because gulping partitions a mailbox queue making it ineligible for stealing.
% Furthermore, after a thief steals, there is moment when victim gulps but the queue no longer 
% This algorithm largely eliminates contention among thieves and victims except for the rare moment when a victim/thief concurrently attempt to gulp/steal the same queue.
% Restating, when a victim operates on a queue, it first copies the queue pointer from @worker_queues@ to a local variable (gulp).
% It then uses that local variable for all queue operations until it moves to the next index of its range.
% This approach ensures any swaps do not interrupt gulping operations, however this introduces a correctness issue.
% There is a window for a race condition between the victim and a thief.
% Once a victim copies the queue pointer from @worker_queues@, a thief could steal that pointer and both may try to gulp from the same queue.
% These two gulps cannot be allowed to happen concurrently.
% If any behaviours from a queue are run by two workers at a time it violates both mutual exclusion and the actor ordering guarantees.
To resolve the race, each mailbox header stores a @being_processed@ flag that is atomically set when a queue is transferred.
The flag indicates that a mailbox has been gulped (logically subdivided) by a worker and the gulped queue is being processed locally.
The @being_processed@ flag is reset once the local processing is finished.
If a worker, either victim or thief turned victim, attempts to gulp from a mailbox and finds the @being_processed@ flag set, it does not gulp and moves onto the next mailbox in its range.
This resolves the race no matter the winner.
If the thief wins the race, it steals the mailbox and gulps, and the victim sees the flag set and skips gulping from the mailbox.
If the victim wins the race, it gulps from the mailbox, and the thief sees the flag set and does not gulp from the mailbox.

There is a final case where the race occurs and is resolved with \emph{both} gulps occurring.
Here, the winner of the race finishes processing the queue and resets the @being_processed@ flag.
Then the loser unblocks from its preemption and completes its gulp from the same mailbox and atomically sets the \snake{being_processed} flag.
The loser is now processing messages from a temporarily shared mailbox, which is safe because the winner ignores this mailbox, if it attempts another gulp since @being_processed@ is set.
The victim never attempts to gulp from the stolen mailbox again because its next cycle sees the swapped mailbox from the thief (which may or may not be empty at this point).
This race is now the only source of contention between victim and thief as they both try to acquire a lock on the same queue during a transfer.
However, the window for this race is extremely small, making this contention rare.
In theory, if this race occurs multiple times consecutively, \ie a thief steals, dereferences a stolen mailbox pointer, is interrupted, and stolen from, etc., this scenario can cascade across multiple workers all attempting to gulp from one mailbox.
The @being_processed@ flag ensures correctness even in this case, and the chance of a cascading scenario across multiple workers is even rarer.

It is straightforward to count the number of missed gulps due to the @being_processed@ flag and this counter is added to all benchmarks presented in Section~\ref{s:actor_perf}.
The results show the median count of missed gulps for each experiment is \emph{zero}, except for the repeat benchmark.
The repeat benchmark is an example of the pathological case described earlier where there is too little work and too many workers.
In the repeat benchmark, one actor has the majority of the workload, and no other actor has a consistent workload, which results in rampant stealing.
None of the work-stealing actor-systems examined in this work perform well on the repeat benchmark.
Hence, for all non-pathological cases, the claim is made that this stealing mechanism has a (probabilistically) zero-victim-cost in practice.
Future work on the work stealing system could include a backoff mechanism after failed steals to further address the pathological cases.

\subsection{Queue Pointer Swap}\label{s:swap}

To atomically swap the two @worker_queues@ pointers during work stealing, a novel atomic swap-algorithm is needed.
The \gls{cas} is a read-modify-write instruction available on most modern architectures.
It atomically compares two memory locations, and if the values are equal, it writes a new value into the first memory location.
A sequential specification of \gls{cas} is:
\begin{cfa}
// assume this routine executes atomically
bool CAS( T * assn, T comp, T new ) {   // T is a basic type
        if ( *assn != comp ) return false;
        *assn = new;
        return true;
}
\end{cfa}
However, this instruction does \emph{not} swap @assn@ and @new@, which is why compare-and-swap is a misnomer.
If @T@ can be a double-wide address-type (128 bits on a 64-bit machine), called a \gls{dwcas}, then it is possible to swap two values, if and only if the two addresses are juxtaposed in memory.
\begin{cfa}
union Pair {
        struct { void * ptr1, * ptr2; };   // 64-bit pointers
        __int128 atom;
};
Pair pair1 = { addr1, addr2 }, pair2 = { addr2, addr1 };
Pair top = pair1;
DWCAS( top.atom, pair1.atom, pair2.atom );
\end{cfa}
However, this approach does not apply because the mailbox pointers are seldom juxtaposed.

Only a few architectures provide a \gls{dcas}, which extends \gls{cas} to two memory locations~\cite{Doherty04}.
\begin{cfa}
// assume this routine executes atomically
bool DCAS( T * assn1, T * assn2, T comp1, T comp2, T new1, T new2 ) {
        if ( *assn1 == comp1 && *assn2 == comp2 ) {
                *assn1 = new1;
                *assn2 = new2;
                return true;
        }
        return false;
}
\end{cfa}
\gls{dcas} can be used to swap two values; for this use case the comparisons are superfluous.
\begin{cfa}
DCAS( x, y, x, y, y, x );
\end{cfa}
A restrictive form of \gls{dcas} can be simulated using \gls{ll}/\gls{sc}~\cite{Brown13} or more expensive transactional memory with the same progress property problems as LL/SC.
% (There is waning interest in transactional memory and it seems to be fading away.)

Similarly, very few architectures have a true memory/memory swap instruction (Motorola M68K, SPARC 32-bit).
The x86 XCHG instruction (and most other architectures with a similar instruction) only works between a register and memory location.
In this case, there is a race between loading the register and performing the swap (discussed shortly).

Either a true memory/memory swap instruction or a \gls{dcas} would provide the ability to atomically swap two memory locations, but unfortunately neither of these instructions are supported on the architectures used in this work.
There are lock-free implemetions of DCAS, or more generally K-word CAS (also known as MCAS or CASN)~\cite{Harris02} and LLX/SCX~\cite{Brown14} that can be used to provide the desired atomic swap capability.
However, these lock-free implementations were not used as it is advantageous in the work stealing case to let an attempted atomic swap fail instead of retrying.
Hence, a novel atomic swap specific to the actor use case is simulated, called \gls{qpcas}.
Note that this swap is \emph{not} lock-free.
The \gls{qpcas} is effectively a \gls{dcas} special cased in a few ways:
\begin{enumerate}
\item
It works on two separate memory locations, and hence, is logically the same as.
\begin{cfa}
bool QPCAS( T * dst, T * src ) {
        return DCAS( dest, src, *dest, *src, *src, *dest );
}
\end{cfa}
\item
The values swapped are never null pointers, so a null pointer can be used as an intermediate value during the swap. As such, null is effectively used as a lock for the swap.
\end{enumerate}
Figure~\ref{f:qpcasImpl} shows the \CFA pseudocode for the \gls{qpcas}.
In detail, a thief performs the following steps to swap two pointers:
\begin{enumerate}
\item
Stores local copies of the two pointers to be swapped.
\item
Verifies the stored copy of the victim queue pointer, @vic_queue@, is valid.
If @vic_queue@ is null, then the victim queue is part of another swap so the operation fails.
No state has changed at this point so the thief just returns.
Note that thieves only set their own queues pointers to null when stealing, and queue pointers are not set to null anywhere else.
As such, it is impossible for @my_queue@ to be null since each worker owns a disjoint range of the queue array.
Hence, only @vic_queue@ is checked for null.
\item
Attempts to atomically set the thief's queue pointer to null.
The @CAS@ only fails if the thief's queue pointer is no longer equal to @my_queue@, which implies this thief has become a victim and its queue has been stolen.
At this point, the thief-turned-victim fails, and since it has not changed any state, it just returns false.
If the @CAS@ succeeds, the thief's queue pointer is now null.
Only thieves look at other worker's queue ranges, and whenever thieves need to dereference a queue pointer, it is checked for null.
A thief can only see the null queue pointer when looking for queues to steal or attempting a queue swap.
If looking for queues, the thief will skip the null pointer, thus only the queue swap case needs to be considered for correctness.

\item
Attempts to atomically set the victim's queue pointer to @my_queue@.
If the @CAS@ succeeds, the victim's queue pointer has been set and the swap can no longer fail.
If the @CAS@ fails, the thief's queue pointer must be restored to its previous value before returning.
\item
Sets the thief's queue pointer to @vic_queue@ completing the swap.
\end{enumerate}

\begin{figure}
\begin{cfa}
bool try_swap_queues( worker & this, uint victim_idx, uint my_idx ) with(this) {
        // Step 1: mailboxes is the shared array of all sharded queues
        work_queue * my_queue = mailboxes[my_idx];
        work_queue * vic_queue = mailboxes[victim_idx];

        // Step 2 If the victim queue is 0p then they are in the process of stealing so return false
        // 0p is Cforall's equivalent of C++'s nullptr
        if ( vic_queue == 0p ) return false;

        // Step 3 Try to set our own (thief's) queue ptr to be 0p.
        // If this CAS fails someone stole our (thief's) queue so return false
        if ( !CAS( &mailboxes[my_idx], &my_queue, 0p ) )
                return false;

        // Step 4: Try to set victim queue ptr to be our (thief's) queue ptr.
        // If it fails someone stole the other queue, so fix up then return false
        if ( !CAS( &mailboxes[victim_idx], &vic_queue, my_queue ) ) {
                mailboxes[my_idx] = my_queue; // reset queue ptr back to prev val
                return false;
        }
        // Step 5: Successfully swapped.
        // Thief's ptr is 0p so no one touches it
        // Write back without CAS is safe
        mailboxes[my_idx] = vic_queue;
        return true;
}
\end{cfa}
\caption{QPCAS Concurrent}
\label{f:qpcasImpl}
\end{figure}

\begin{theorem}
\gls{qpcas} is correct in both the success and failure cases.
\end{theorem}
To verify sequential correctness, Figure~\ref{f:seqSwap} shows a simplified \gls{qpcas}.
Step 2 is missing in the sequential example since it only matters in the concurrent context.
By inspection, the sequential swap copies each pointer being swapped, and then the original values of each pointer are reset using the copy of the other pointer.

\begin{figure}
\begin{cfa}
void swap( uint victim_idx, uint my_idx ) {
        // Step 1:
        work_queue * my_queue = mailboxes[my_idx];
        work_queue * vic_queue = mailboxes[victim_idx];
        // Step 3:
        mailboxes[my_idx] = 0p;
        // Step 4:
        mailboxes[victim_idx] = my_queue;
        // Step 5:
        mailboxes[my_idx] = vic_queue;
}
\end{cfa}
\caption{QPCAS Sequential}
\label{f:seqSwap}
\end{figure}

% All thieves fail or succeed in swapping the queues in a finite number of steps.
% This is straightforward, because there are no locks or looping.
% As well, there is no retry mechanism in the case of a failed swap, since a failed swap either means the work is already stolen or that work is stolen from the thief.
% In both cases, it is apropos for a thief to give up stealing.

The concurrent proof of correctness is shown through the existence of an invariant.
The invariant states 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.
This is effictively a mutual exclusion condition for the later write.
To show that this invariant holds, it is shown that it is true at each step of the swap.
\begin{itemize}
\item
Step 1 and 2 do not write, and as such, they cannot invalidate the invariant of any other thieves.
\item
In step 3, a thief attempts to write @0p@ to one of their queue pointers.
This queue pointer cannot be @0p@.
As stated above, @my_queue@ is never equal to @0p@ since thieves only write @0p@ to queue pointers from their own queue range and all worker's queue ranges are disjoint.
As such, step 3 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.
\item
In step 4, the thief attempts to write @my_queue@ to the victim's queue pointer.
If the current value of the victim's queue pointer is @0p@, then the @CAS@ fails since @vic_queue@ cannot be equal to @0p@ because of the check in step 2.
Therefore, when the @CAS@ succeeds, the value of the victim's queue pointer must not be @0p@.
As such, the write never overwrites a value of @0p@, hence the invariant is held in the @CAS@ of step 4.
\item
The write back to the thief's queue pointer that happens in the failure case of step 4 and in step 5 hold the invariant since they are the subsequent write to a @0p@ queue pointer and are being set by the same thief that set the pointer to @0p@.
\end{itemize}

Given this informal proof of invariance it can be shown that the successful swap is correct.
Once a thief atomically sets their queue pointer to be @0p@ in step 3, the invariant guarantees that that pointer does not change.
In the success case of step 4, it is known the value of the victim's queue-pointer, which is not overwritten, must be @vic_queue@ due to the use of @CAS@.
Given that the pointers all have unique memory locations (a pointer is never swapped with itself), this first write of the successful swap is correct since it can only occur when the pointer has not changed.
By the invariant, the write back in the successful case is correct since no other worker can write to the @0p@ pointer.
In the failed case of step 4, the outcome is correct in steps 2 and 3 since no writes have occurred so the program state is unchanged.
Therefore, the program state is safely restored to the state it had prior to the @0p@ write in step 3, because the invariant makes the write back to the @0p@ pointer safe.
Note that the pointers having unique memory locations prevents the ABA problem.

\begin{comment}
\subsection{Stealing Guarantees}
Given that the stealing operation can potentially fail, it is important to discuss the guarantees provided by the stealing implementation.
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.
Since each thief can only steal from one victim at a time, each vertex can only have at most one outgoing edge.
A 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.

\begin{figure}
\begin{center}
\input{diagrams/M_to_one_swap.tikz}
\end{center}
\caption{Graph of $M$ thieves swapping with one victim.}
\label{f:M_one_swap}
\end{figure}

\begin{theorem}
Given $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.
\end{theorem}\label{t:one_vic}
A graph of the $M$ thieves swapping with one victim discussed in this theorem is presented in Figure~\ref{f:M_one_swap}.
\\
First it is important to state that a thief does not attempt to steal from themselves.
As such, the victim here is not also a thief.
Stepping through the code in \ref{f:qpcasImpl}, for all thieves, steps 0-1 succeed since the victim is not stealing and has no queue pointers set to be @0p@.
Similarly, for all thieves, step 3 succeeds since no one is stealing from any of the thieves.
In step 4, the first thief to @CAS@ wins the race and successfully swaps the queue pointer.
Since 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.
Hence at least one swap is guaranteed to succeed in this case.

\begin{figure}
\begin{center}
\input{diagrams/chain_swap.tikz}
\end{center}
\caption{Graph of a chain of swaps.}
\label{f:chain_swap}
\end{figure}

\begin{theorem}
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 occurring that involve these queues, at least one swap is guaranteed to succeed.
\end{theorem}\label{t:vic_chain}
A graph of the chain of swaps discussed in this theorem is presented in Figure~\ref{f:chain_swap}.
\\
This is a proof by contradiction.
Assume no swaps occur.
Then all thieves must have failed at step 2, step 3 or step 4.
For a given thief $b$ to fail at step 2, thief $b + 1$ must have succeeded at step 3 before $b$ executes step 1.
Hence, not all thieves can fail at step 2.
Furthermore if a thief $b$ fails at step 2 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.
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 2 and succeeding at step 3.
Hence, without loss of generality, whether thieves succeed or fail at step 2, this proof can proceed inductively.

For a given thief $i$ to fail at step 3, it means that another thief $j$ had to have written to $i$'s queue pointer between $i$'s step 1 and step 3.
The only way for $j$ to write to $i$'s queue pointer would be if $j$ was stealing from $i$ and had successfully finished 4.
If $j$ finished step 4, then at least one swap was successful.
Therefore all thieves did not fail at step 3.
Hence all thieves must successfully complete step 3 and fail at step 4.
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.
Hence, in this case thief $1$ always succeeds in step 4 if all thieves succeed in step 3.
Thus, by contradiction with the earlier assumption that no swaps occur, at least one swap must succeed.

% \raisebox{.1\height}{}
\begin{figure}
\centering
\begin{tabular}{l|l}
\subfloat[Cyclic Swap Graph]{\label{f:cyclic_swap}\input{diagrams/cyclic_swap.tikz}} &
\subfloat[Acyclic Swap Graph]{\label{f:acyclic_swap}\input{diagrams/acyclic_swap.tikz}}
\end{tabular}
\caption{Illustrations of cyclic and acyclic swap graphs.}
\end{figure}

\begin{theorem}
Given a set of $M > 1$ swaps occurring that form a single directed connected graph.
At least one swap is guaranteed to succeed if and only if the graph does not contain a cycle.
\end{theorem}\label{t:vic_cycle}
Representations of cyclic and acyclic swap graphs discussed in this theorem are presented in Figures~\ref{f:cyclic_swap} and \ref{f:acyclic_swap}.
\\
First the reverse direction is proven.
If the graph does not contain a cycle, then there must be at least one successful swap.
Since the graph contains no cycles and is finite in size, then there must be a vertex $A$ with no outgoing edges.
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.
The forward direction is proven by contradiction in a similar fashion to \ref{t:vic_chain}.
Assume no swaps occur.
Similar to \ref{t:vic_chain}, this graph can be inductively split into subgraphs of the same type by failure at step 2, so the proof proceeds without loss of generality.
Similar to \ref{t:vic_chain} the conclusion is drawn that all thieves must successfully complete step 3 for no swaps to occur, since for step 3 to fail, a different thief has to successfully complete step 4, which would imply a successful swap.
Hence, the only way forward is to assume all thieves successfully complete step 3.
Hence for there to be no swaps all thieves must fail step 4.
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$.
Since all $K$ thieves have passed step 3, similar to \ref{t:one_vic} the first one of the $K$ thieves to attempt step 4 is guaranteed to succeed.
Thus, by contradiction with the earlier assumption that no swaps occur, if the graph does not contain a cycle, at least one swap must succeed.

The forward direction is proven by contrapositive.
If the graph contains a cycle then there exists a situation where no swaps occur.
This situation is constructed.
Since all vertices have at most one outgoing edge the cycle must be directed.
Furthermore, since the graph contains a cycle all vertices in the graph must have exactly one outgoing edge.
This is shown through construction of an arbitrary cyclic graph.
The graph contains a directed cycle by definition, so the construction starts with $T$ vertices in a directed cycle.
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 accommodate new vertices with no outgoing edges.
Any vertices added to the graph must have an outgoing edge to connect, leaving the resulting graph with no available outgoing edges.
Thus, by induction all vertices in the graph must have exactly one outgoing edge.
Hence all vertices are thief queues.
Now consider the case where all thieves successfully complete step 1-2, and then they all complete step 3.
At this point all thieves are attempting to swap with a queue pointer whose value has changed to @0p@.
If all thieves attempt the @CAS@ before any write backs, then they all fail.
Thus, by contrapositive, if the graph contains a cycle then there exists a situation where no swaps occur.
Hence, at least one swap is guaranteed to succeed if and only if the graph does not contain a cycle.
\end{comment}

% C_TODO: go through and use \paragraph to format to make it look nicer
\subsection{Victim Selection}\label{s:victimSelect}

In any work stealing algorithm, thieves use a heuristic to determine which victim to choose.
Choosing this algorithm is difficult and can have implications on performance.
There is no one selection heuristic known to be best for all workloads.
Recent work focuses on locality aware scheduling in actor systems~\cite{barghi18,wolke17}.
However, while locality-aware scheduling provides good performance on some workloads, randomized selection performs better on other workloads~\cite{barghi18}.
Since locality aware scheduling has been explored recently, this work introduces a heuristic called \Newterm{longest victim} and compares it to randomized work stealing.

The longest-victim heuristic maintains a timestamp per executor thread that is updated every time a worker attempts to steal work.
The timestamps are generated using @rdtsc@~\cite{IntelManual} and are stored in a shared array, with one index per worker. 
Thieves then attempt to steal from the worker with the oldest timestamp, which is found by performing a linear search across the array of timestamps.
The intuition behind this heuristic is that the slowest worker receives help via work stealing until it becomes a thief, which indicates that it has caught up to the pace of the rest of the workers.
This heuristic should ideally result in lowered latency for message sends to victim workers that are overloaded with work.
It must be acknowledged that this linear search could cause a lot of cache coherence traffic.
Future work on this heuristic could include introducing a search that has less impact on caching.
A negative side-effect of this heuristic is that if multiple thieves steal at the same time, they likely steal from the same victim, which increases the chance of contention.
However, given that workers have multiple queues, often in the tens or hundreds of queues, it is rare for two thieves to attempt stealing from the same queue.
This approach may seem counter-intuitive, but in cases with not enough work to steal, the contention among thieves can result in less stealing, due to failed swaps.
This can be beneficial when there is not enough work for all the stealing to be productive.
This heuristic does not boast performance over randomized victim selection, but it is comparable \see{Section~\ref{s:steal_perf}}.
However, it constitutes an interesting contribution as it shows that adding some complexity to the heuristic of the stealing fast-path does not affect mainline performance, paving the way for more involved victim selection heuristics.

% 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}.
% Additionally, the longest victim heuristic makes it very improbable that the no swap scenario presented in Theorem~\ref{t:vic_cycle} manifests.
% Given the longest victim heuristic, for a cycle to manifest it requires all workers to attempt to steal in a short timeframe.
% This scenario 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.
% In this case, the probability of an unsuccessful swap is rare, since it is likely these steals are not important when all workers are trying to steal.

\section{Safety and Productivity}\label{s:SafetyProductivity}

\CFA's actor system comes with a suite of safety and productivity features.
Most of these features are only present in \CFA's debug mode, and hence, have zero-cost in no-debug mode.
The suite of features include the following.
\begin{itemize}
\item Static-typed message sends:
If an actor does not support receiving a given message type, the receive call is rejected at compile time, preventing unsupported messages from being sent to an actor.

\item Detection of message sends to Finished/Destroyed/Deleted actors:
All actors receive a ticket from the executor at creation that assigns them to a specific mailbox queue of a worker.
The maximum integer value of the ticket is reserved to indicate an actor is terminated, and assigned to an actor's ticket at termination.
Any subsequent message sends to this terminated actor results in an error.

\item Actors cannot be created before the executor starts:
Since the executor distributes mailbox tickets, correctness implies it must be created \emph{before} any actors so it can give out the tickets.

\item When an executor is configured, $M >= N$.
That is, each worker must receive at least one mailbox queue, since otherwise a worker cannot receive any work without a queue pull messages from.

\item Detection of unsent messages:
At program termination, a warning is printed for all deallocated messages that are not sent.
Since the @Finished@ allocation status is unused for messages, it is used internally to detect if a message has been sent.
Deallocating a message without sending it could indicate problems in the program design.

\item Detection of messages sent but not received:
As discussed in Section~\ref{s:executor}, once all actors have terminated, shutdown is communicated to the executor threads via a status flag.
During termination of the executor threads, each worker checks its mailbox queues for any messages.
If so, an error is reported.
Messages being sent but not received means their allocation action has not occur and their payload is not delivered.
Missed deallocations can lead to memory leaks and unreceived payloads can mean logic problems.
% Detecting can indicate a race or logic error in the user's code.
\end{itemize}

In addition to these features, the \CFA's actor system comes with a suite of statistics that can be toggled on and off when \CFA is built.
These statistics have minimal impact on the actor system's performance since they are counted independently by each worker thread.
During shutdown of the actor system, these counters are aggregated sequentially.
The statistics measured are as follows.
\begin{description}
\item[\LstBasicStyle{\textbf{Actors Created}}]
Includes both actors made in the program main and ones made by other actors.
\item[\LstBasicStyle{\textbf{Messages Sent and Received}}]
Includes termination messages send to the executor threads.
\item[\LstBasicStyle{\textbf{Gulps}}]
Gulps across all worker threads.
\item[\LstBasicStyle{\textbf{Average Gulp Size}}]
Average number of messages in a gulped queue.
\item[\LstBasicStyle{\textbf{Missed gulps}}]
Missed gulps due to the current queue being processed by another worker.
\item[\LstBasicStyle{\textbf{Steal attempts}}]
All worker thread attempts to steal work.
\item[\LstBasicStyle{\textbf{Steal failures (no candidates)}}]
Work stealing failures due to selected victim not having any non-empty or non-being-processed queues.
\item[\LstBasicStyle{\textbf{Steal failures (failed swaps)}}]
Work stealing failures due to the two-stage atomic-swap failing.
\item[\LstBasicStyle{\textbf{Messages stolen}}]
Aggregate number of messages in stolen queues.
\item[\LstBasicStyle{\textbf{Average steal size}}]
Average number of messages across stolen queues.
\end{description}

These statistics enable a user to make informed choices about how to configure the executor or how to structure the actor program.
For example, if there are a lot of messages being stolen relative to the number of messages sent, it indicates that the workload is heavily imbalanced across executor threads.
Another example is if the average gulp size is very high, it indicates the executor needs more queue sharding, \ie increase $M$.

Finally, the poison-pill messages and receive routines, shown earlier in Figure~\ref{f:PoisonPillMessages}, are a convenience for programmers and can be overloaded to have specific behaviour for derived actor types.

\section{Performance}\label{s:actor_perf}

The performance of the \CFA's actor system is tested using a suite of microbenchmarks, and compared with other actor systems.
Most of the benchmarks are the same as those presented in \cite{Buhr22}, with a few additions.
This work compares with the following actor systems: \CFA 1.0, \uC 7.0.0, Akka Typed 2.7.0, CAF 0.18.6, and ProtoActor-Go v0.0.0-20220528090104-f567b547ea07.
Akka Classic is omitted as Akka Typed is their newest version and seems to be the direction they are headed.
The experiments are run on two popular architectures:
\begin{list}{\arabic{enumi}.}{\usecounter{enumi}\topsep=5pt\parsep=5pt\itemsep=0pt}
\item
Supermicro SYS--6029U--TR4 Intel Xeon Gold 5220R 24--core socket, hyper-threading $\times$ 2 sockets (96 process\-ing units), running Linux v5.8.0--59--generic
\item
Supermicro AS--1123US--TR4 AMD EPYC 7662 64--core socket, hyper-threading $\times$ 2 sockets (256 processing units), running Linux v5.8.0--55--generic
\end{list}

The benchmarks are run on 1--48 cores.
On the Intel, with 24 core sockets, there is the choice to either hop sockets or use hyperthreads on the same socket.
Either choice causes a blip in performance, which is seen in the subsequent performance graphs.
The choice in this work is to use hyperthreading instead of hopping sockets for experiments with more than 24 cores.

All benchmarks are run 5 times and the median is taken.
Error bars showing the 95\% confidence intervals appear on each point in the graphs.
The confidence intervals are calculated using bootstrapping to avoid normality assumptions.
If the confidence bars are small enough, they may be obscured by the data point.
In this section, \uC is compared to \CFA frequently, as the actor system in \CFA is heavily based off of \uC's actor system.
As such, the performance differences that arise are largely due to the contributions of this work.
Future work is to port some of the new \CFA work back to \uC.

\subsection{Message Sends}

Message sending is the key component of actor communication.
As such, latency of a single message send is the fundamental unit of fast-path performance for an actor system.
The static and dynamic send-benchmarks evaluate the average latency for a static actor/message send and a dynamic actor/message send.
In the static-send benchmark, a message and actor are allocated once and then the message is sent to the same actor 100 million (100M) times.
The average latency per message send is then calculated by dividing the duration by the number of sends.
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.
The CAF static-send benchmark only sends a message 10M times to avoid extensively long run times.

In the dynamic-send benchmark, the same experiment is used, but for each send, a new actor and message is allocated.
This benchmark evaluates the cost of message sends in the other common actor pattern where actors and messages are created on the fly as the actor program tackles a workload of variable or unknown size.
Since 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.

\begin{table}[t]
\centering
\setlength{\extrarowheight}{2pt}
\setlength{\tabcolsep}{5pt}
\caption{Static Actor/Message Performance: message send, program memory (lower is better)}
\label{t:StaticActorMessagePerformance}
\begin{tabular}{*{5}{r|}r}
        & \multicolumn{1}{c|}{\CFA (100M)} & \multicolumn{1}{c|}{\uC (100M)} & \multicolumn{1}{c|}{CAF (10M)} & \multicolumn{1}{c|}{Akka (100M)} & \multicolumn{1}{c@{}}{ProtoActor (100M)} \\
        \hline
        AMD             & \input{data/nasusSendStatic} \\
        \hline
        Intel   & \input{data/pykeSendStatic}
\end{tabular}

\bigskip

\caption{Dynamic Actor/Message Performance: message send, program memory (lower is better)}
\label{t:DynamicActorMessagePerformance}

\begin{tabular}{*{5}{r|}r}
        & \multicolumn{1}{c|}{\CFA (20M)} & \multicolumn{1}{c|}{\uC (20M)} & \multicolumn{1}{c|}{CAF (2M)} & \multicolumn{1}{c|}{Akka (2M)} & \multicolumn{1}{c@{}}{ProtoActor (2M)} \\
        \hline
        AMD             & \input{data/nasusSendDynamic} \\
        \hline
        Intel   & \input{data/pykeSendDynamic}
\end{tabular}
\end{table}

The results from the static/dynamic-send benchmarks are shown in Tables~\ref{t:StaticActorMessagePerformance} and \ref{t:DynamicActorMessagePerformance}, respectively.
\CFA has the best results in both benchmarks, largely due to the copy queue removing the majority of the envelope allocations.
Additionally, the receive of all messages sent in \CFA is statically known and is determined via a function pointer cast, which incurs no runtime cost.
All the other systems use virtual dispatch to find the correct behaviour at message send.
This operation actually requires two virtual dispatches, which is an additional runtime send cost.
Note that Akka also statically checks message sends, but still uses the Java virtual system.
In the static-send benchmark, all systems except CAF have static send costs that are in the same ballpark, only varying by ~70ns.
In the dynamic-send benchmark, all systems experience slower message sends, due to the memory allocations.
However, Akka and ProtoActor, slow down by two-orders of magnitude.
This difference is likely a result of Akka and ProtoActor's garbage collection, which results in performance delays for allocation-heavy workloads, whereas \uC and \CFA have explicit allocation/deallocation.
Tuning the garage collection might reduce garbage-collection cost, but this exercise is beyond the scope of this work.

\subsection{Executor}\label{s:executorPerf}

The benchmarks in this section are designed to stress the executor.
The executor is the scheduler of an actor system and is responsible for organizing the interaction of executor threads to service the needs of an actor workload.
Three benchmarks are run: executor, repeat, and high-memory watermark.

The executor benchmark creates 40,000 actors, organizes the actors into adjacent groups of 100, where an actor sends a message to each group member, including itself, in round-robin order, and repeats the sending cycle 400 times.
This microbenchmark is designed to flood the executor with a large number of messages flowing among actors.
Given 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.

\begin{figure}
        \centering
        \subfloat[AMD Executor Benchmark]{
                \resizebox{0.5\textwidth}{!}{\input{figures/nasusExecutor.pgf}}
                \label{f:ExecutorAMD}
        }
        \subfloat[Intel Executor Benchmark]{
                \resizebox{0.5\textwidth}{!}{\input{figures/pykeExecutor.pgf}}
                \label{f:ExecutorIntel}
        }
        \caption{Executor benchmark comparing actor systems (lower is better).}
\end{figure}

Figures~\ref{f:ExecutorIntel} and~\ref{f:ExecutorAMD} show the results of the AMD and Intel executor benchmark.
There are three groupings of results, and the difference between AMD and Intel is small.
CAF is significantly slower than the other actor systems; followed by a tight grouping of \uC, ProroActor, and Akka; and finally \CFA with the lowest runtime relative to its peers.
The difference in runtime between \uC and \CFA is largely due to the copy queue described in Section~\ref{s:copyQueue}.
The copy queue both reduces and consolidates allocations, heavily reducing contention on the memory allocator.
Additionally, due to the static typing in \CFA's actor system, there is no expensive dynamic (RTTI) casts that occur in \uC to discriminate messages types.
Note that while dynamic cast is relatively inexpensive, the remaining send cost in both \uC and \CFA is small;
hence, the relative cost for the RTTI in \uC is significant.

The repeat benchmark also evaluates the executor.
It stresses the executor's ability to withstand contention on queues.
The repeat benchmark repeatedly fans out messages from a single client to 100,000 servers who then respond back to the client.
The scatter and gather repeats 200 times.
The messages from the servers to the client all come to the same mailbox queue associated with the client, resulting in high contention among servers.
As such, this benchmark does not scale with the number of processors, since more processors result in higher contention on the single mailbox queue.

Figures~\ref{f:RepeatAMD} and~\ref{f:RepeatIntel} show the results of the AMD and Intel repeat benchmark.
The results are spread out more, and there is a difference between AMD and Intel.
Again, CAF is significantly slower than the other actor systems.
To keep the graphs readable, the y-axis was cut at 100 seconds; as the core count increases from 8-32, CAF ranges around 200 seconds on AMD and between 300-1000 seconds on the Intel.
On the AMD there is a tight grouping of uC++, ProtoActor, and Akka;
on the Intel, uC++, ProtoActor, and Akka are spread out.
Finally, \CFA runs consistently on both of the AMD and Intel, and is faster than \uC on the AMD, but slightly slower on the Intel.
Here, gains from using the copy queue are much less apparent.

\begin{figure}
        \centering
        \subfloat[AMD Repeat Benchmark]{
                \resizebox{0.5\textwidth}{!}{\input{figures/nasusRepeat.pgf}}
                \label{f:RepeatAMD}
        }
        \subfloat[Intel Repeat Benchmark]{
                \resizebox{0.5\textwidth}{!}{\input{figures/pykeRepeat.pgf}}
                \label{f:RepeatIntel}
        }
        \caption{The repeat benchmark comparing actor systems (lower is better).}
\end{figure}

Table~\ref{t:ExecutorMemory} shows the high memory watermark of the actor systems when running the executor benchmark on 48 cores measured using the @time@ command.
\CFA's high watermark is slightly higher than the other non-garbage collected systems \uC and CAF.
This increase is from the over-allocation in the copy-queue data-structure with lazy deallocation.
Whereas, the per envelope allocations of \uC and CFA allocate exactly the amount of storage needed and eagerly deallocate.
The extra storage is the standard tradeoff of time versus space, where \CFA shows better performance.
As future work, tuning parameters can be provided to adjust the frequency and/or size of the copy-queue expansion.

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

        \caption{Executor Program Memory High Watermark}
        \label{t:ExecutorMemory}
        \begin{tabular}{*{5}{r|}r}
                & \multicolumn{1}{c|}{\CFA} & \multicolumn{1}{c|}{\uC} & \multicolumn{1}{c|}{CAF} & \multicolumn{1}{c|}{Akka} & \multicolumn{1}{c@{}}{ProtoActor} \\
                \hline
                AMD             & \input{data/pykeExecutorMem} \\
                \hline
                Intel   & \input{data/nasusExecutorMem}
        \end{tabular}
\end{table}

\subsection{Matrix Multiply}

The matrix-multiply benchmark evaluates the actor systems in a practical application, where actors concurrently multiply two matrices.
In detail, given $Z_{m,r} = X_{m,n} \cdot Y_{n,r}$, the matrix multiply is defined as:
\begin{displaymath}
X_{i,j} \cdot Y_{j,k} = \left( \sum_{c=1}^{j} X_{row,c}Y_{c,column} \right)_{i,k}
\end{displaymath}
The 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 message sending system, and might trigger some work stealing if a worker finishes early.

The matrix-multiply benchmark has input matrices $X$ and $Y$, which are both $3072$ by $3072$ in size.
An actor is made for each row of $X$ and sent a message indicating the row of $X$ and the column of $Y$ to calculate a row of the result matrix $Z$.
Because $Z$ is contiguous in memory, there can be small cache write-contention at the row boundaries.

Figures~\ref{f:MatrixAMD} and \ref{f:MatrixIntel} show the matrix-multiply results.
There are two groupings with Akka and ProtoActor being slightly slower than \uC, \CFA, and CAF.
On the Intel, there is an unexplained divergence between \uC and \CFA/CAF at 24 cores.
Given that the bottleneck of this benchmark is the computation of the result matrix, all executors perform well on this embarrassingly parallel application.
Hence, the results are tightly clustered across all actor systems.
This result also suggests CAF has a good executor but poor message passing, which results in its poor performance in the other message-passing benchmarks.

\begin{figure}
        \centering
        \subfloat[AMD Matrix Benchmark]{
                \resizebox{0.5\textwidth}{!}{\input{figures/nasusMatrix.pgf}}
                \label{f:MatrixAMD}
        }
        \subfloat[Intel Matrix Benchmark]{
                \resizebox{0.5\textwidth}{!}{\input{figures/pykeMatrix.pgf}}
                \label{f:MatrixIntel}
        }
        \caption{The matrix benchmark comparing actor systems (lower is better).}
\end{figure}

\subsection{Work Stealing}\label{s:steal_perf}

\CFA's work stealing mechanism uses the longest-victim heuristic, introduced in Section~\ref{s:victimSelect}.
In this performance section, \CFA's approach is first tested in isolation on a pathological unbalanced benchmark, then with other actor systems on general benchmarks.

Two pathological unbalanced cases are created, and compared using vanilla and randomized work stealing in \CFA.
These benchmarks adversarially take advantage of the round-robin assignment of actors to workers by loading actors only on specific cores (there is one worker per core).
The workload on the loaded cores is the same as the executor benchmark described in \ref{s:executorPerf}, but with fewer rounds.

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).
Given this layout, the ideal speedup of work stealing in the balance-one case should be $N / N - 1$ where $N$ is the number of threads;
in the balance-multi case, the ideal speedup is 0.5.
Note that in the balance-one benchmark, the workload is fixed so decreasing runtime is expected;
in the balance-multi experiment, the workload increases with the number of cores so an increasing or constant runtime is expected.

\begin{figure}
        \centering
        \subfloat[AMD \CFA Balance-One Benchmark]{
                \resizebox{0.5\textwidth}{!}{\input{figures/nasusCFABalance-One.pgf}}
                \label{f:BalanceOneAMD}
        }
        \subfloat[Intel \CFA Balance-One Benchmark]{
                \resizebox{0.5\textwidth}{!}{\input{figures/pykeCFABalance-One.pgf}}
                \label{f:BalanceOneIntel}
        }
        \caption{The balance-one benchmark comparing stealing heuristics (lower is better).}
\end{figure}

\begin{figure}
        \centering
        \subfloat[AMD \CFA Balance-Multi Benchmark]{
                \resizebox{0.5\textwidth}{!}{\input{figures/nasusCFABalance-Multi.pgf}}
                \label{f:BalanceMultiAMD}
        }
        \subfloat[Intel \CFA Balance-Multi Benchmark]{
                \resizebox{0.5\textwidth}{!}{\input{figures/pykeCFABalance-Multi.pgf}}
                \label{f:BalanceMultiIntel}
        }
        \caption{The balance-multi benchmark comparing stealing heuristics (lower is better).}
\end{figure}

% On both balance benchmarks, slightly less than ideal speedup compared to the non-stealing variation is achieved by both the random and longest victim stealing heuristics.

For the balance-one benchmark on AMD in Figure~\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.
On Intel in Figure~\ref{f:BalanceOneIntel}, above 32 cores the performance gets worse for all variants due to hyperthreading.
Here, the longest-victim and random heuristic are the same.
Note that the non-stealing variation of balance-one slows down slightly (no decrease in graph) as the cores increase, since a few \emph{dummy} actors are created for each of the extra cores beyond the first to adversarially layout all loaded actors on the first core.

For the balance-multi benchmark in Figures~\ref{f:BalanceMultiAMD} and~\ref{f:BalanceMultiIntel}, the random heuristic outperforms the longest victim.
The reason is that the longest-victim heuristic has a higher stealing cost as it needs to maintain timestamps and look at all timestamps before stealing.
Additionally, a performance cost on the Intel is observed when hyperthreading kicks in after 24 cores in Figure~\ref{f:BalanceMultiIntel}.

\begin{figure}
        \centering
        \subfloat[AMD \CFA Executor Benchmark]{
                \resizebox{0.5\textwidth}{!}{\input{figures/nasusCFAExecutor.pgf}}
                \label{f:cfaExecutorAMD}
        }
        \subfloat[Intel \CFA Executor Benchmark]{
                \resizebox{0.5\textwidth}{!}{\input{figures/pykeCFAExecutor.pgf}}
                \label{f:cfaExecutorIntel}
        }
        \caption{Executor benchmark comparing \CFA stealing heuristics (lower is better).}
        \label{f:ExecutorBenchmark}
\end{figure}

Figures~\ref{f:cfaExecutorAMD} and~\ref{f:cfaExecutorIntel} show the effects of the stealing heuristics for the executor benchmark.
For the AMD, in Figure~\ref{f:cfaExecutorAMD}, the random heuristic falls slightly behind the other two, but for the Intel, in Figure~\ref{f:cfaExecutorIntel}, the runtime of all heuristics are nearly identical to each other, except after crossing the 24-core boundary.

\begin{figure}
        \centering
        \subfloat[AMD \CFA Repeat Benchmark]{
                \resizebox{0.5\textwidth}{!}{\input{figures/nasusCFARepeat.pgf}}
                \label{f:cfaRepeatAMD}
        }
        \subfloat[Intel \CFA Repeat Benchmark]{
                \resizebox{0.5\textwidth}{!}{\input{figures/pykeCFARepeat.pgf}}
                \label{f:cfaRepeatIntel}
        }
        \caption{The repeat benchmark comparing \CFA stealing heuristics (lower is better).}
        \label{f:RepeatBenchmark}
\end{figure}

\begin{figure}
        \centering
        \subfloat[AMD \CFA Matrix Benchmark]{
                \resizebox{0.5\textwidth}{!}{\input{figures/nasusCFAMatrix.pgf}}
                \label{f:cfaMatrixAMD}
        }
        \subfloat[Intel \CFA Matrix Benchmark]{
                \resizebox{0.5\textwidth}{!}{\input{figures/pykeCFAMatrix.pgf}}
                \label{f:cfaMatrixIntel}
        }
        \caption{The matrix benchmark comparing \CFA stealing heuristics (lower is better).}
\end{figure}

Figures~\ref{f:cfaRepeatAMD} and~\ref{f:cfaRepeatIntel} show the effects of the stealing heuristics for the repeat benchmark.
This benchmark is a pathological case for work stealing actor systems, as the majority of work is being performed by the single actor conducting the scatter/gather.
The single actor (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.
When stealing the client or its respective queue (in \CFA's inverted model), moving the client incurs a high cost due to cache invalidation.
This worst-case steal is likely to happen since there is no other work in the system between scatter/gather rounds.
However, all heuristics are comparable in performance on the repeat benchmark.
This result is surprising especially for the No-Stealing variant, which should have better performance than the stealing variants.
However, stealing happens lazily and fails fast, hence the queue containing the long-running client actor is rarely stolen.

% Work stealing performance can be further analyzed by \emph{reexamining} the executor and repeat benchmarks in Figures~\ref{f:ExecutorBenchmark} and \ref{f:RepeatBenchmark}.
% In both benchmarks, CAF performs poorly.
% It is hypothesized that CAF has an aggressive work stealing algorithm that eagerly attempts to steal.
% This results in the poor performance with small messages containing little work per message in both of these benchmarks.
% In comparison with the other systems, \uC does well on both benchmarks since it does not have work stealing.

Finally, Figures~\ref{f:cfaMatrixAMD} and~\ref{f:cfaMatrixIntel} show the effects of the stealing heuristics for the matrix-multiply benchmark.
Here, there is negligible performance difference across stealing heuristics, because of the long-running workload of each message.

In theory, work stealing might improve performance marginally for the matrix-multiply benchmark.
Since all row actors cannot be created simultaneously at startup, they correspondingly do not shutdown simultaneously.
Hence, there is a small window at the start and end with idle workers so work stealing might improve performance.
For example, in \ref{f:MatrixAMD}, CAF is slightly better than \uC and \CFA, but not on the Intel.
Hence, it is difficult to attribute the AMD gain to the aggressive work stealing in CAF.

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