Changeset b7b3e41 for doc

doc/papers/llheap/Paper.tex

-              rfa5e1aa5
+              rb7b3e41
 Dynamic code/data memory is managed by the dynamic loader for libraries loaded at runtime, which is complex especially in a multi-threaded program~\cite{Huang06}.
 However, changes to the dynamic code/data space are typically infrequent, many occurring at program startup, and are largely outside of a program's control.
 Stack memory is managed by the program call/return-mechanism using a simple LIFO technique, which works well for sequential programs.
 For stackful coroutines and user threads, a new stack is commonly created in dynamic-allocation memory.
+Stack memory is managed by the program call/return-mechanism using a LIFO technique, which works well for sequential programs.
+For stackful coroutines and user threads, a new stack is commonly created in the dynamic-allocation memory.
 This work focuses solely on management of the dynamic-allocation memory.
 …
 \begin{enumerate}[leftmargin=*,itemsep=0pt]
 \item
 Implementation of a new stand-alone concurrent low-latency memory-allocator ($\approx$1,200 lines of code) for C/\CC programs using kernel threads (1:1 threading), and specialized versions of the allocator for the programming languages \uC and \CFA using user-level threads running on multiple kernel threads (M:N threading).
 \item
 Extend the standard C heap functionality by preserving with each allocation: its request size plus the amount allocated, whether an allocation is zero fill, and allocation alignment.
+Implementation of a new stand-alone concurrent low-latency memory-allocator ($\approx$1,200 lines of code) for C/\CC programs using kernel threads (1:1 threading), and specialized versions of the allocator for the programming languages \uC~\cite{uC++} and \CFA~\cite{Moss18,Delisle21} using user-level threads running on multiple kernel threads (M:N threading).
+\item
+Extend the standard C heap functionality by preserving with each allocation: its request size plus the amount allocated, whether an allocation is zero fill and/or allocation alignment.
 \item
 …
 The following discussion is a quick overview of the moving-pieces that affect the design of a memory allocator and its performance.
 It is assumed that dynamic allocates and deallocates acquire storage for a program variable, referred to as an \newterm{object}, through calls such as @malloc@ and @free@ in C, and @new@ and @delete@ in \CC.
+Dynamic acquires and releases obtain storage for a program variable, called an \newterm{object}, through calls such as @malloc@ and @free@ in C, and @new@ and @delete@ in \CC.
 Space for each allocated object comes from the dynamic-allocation zone.
 …
 Figure~\ref{f:AllocatorComponents} shows the two important data components for a memory allocator, management and storage, collectively called the \newterm{heap}.
+The \newterm{management data} is a data structure located at a known memory address and contains all information necessary to manage the storage data.
+The management data starts with fixed-sized information in the static-data memory that references components in the dynamic-allocation memory.
+The \newterm{management data} is a data structure located at a known memory address and contains fixed-sized information in the static-data memory that references components in the dynamic-allocation memory.
 For multi-threaded programs, additional management data may exist in \newterm{thread-local storage} (TLS) for each kernel thread executing the program.
 The \newterm{storage data} is composed of allocated and freed objects, and \newterm{reserved memory}.
 …
 \ie only the program knows the location of allocated storage not the memory allocator.
 Freed objects (white) represent memory deallocated by the program, which are linked into one or more lists facilitating easy location of new allocations.
 Reserved memory (dark grey) is one or more blocks of memory obtained from the operating system but not yet allocated to the program;
 if there are multiple reserved blocks, they are also chained together, usually internally.
+Reserved memory (dark grey) is one or more blocks of memory obtained from the \newterm{operating system} (OS) but not yet allocated to the program;
+if there are multiple reserved blocks, they are also chained together.
 \begin{figure}
 …
 \end{figure}
 In most allocator designs, allocated objects have management data embedded within them.
+In many allocator designs, allocated objects and reserved blocks have management data embedded within them (see also Section~\ref{s:ObjectContainers}).
 Figure~\ref{f:AllocatedObject} shows an allocated object with a header, trailer, and optional spacing around the object.
 The header contains information about the object, \eg size, type, etc.
 …
 When padding and spacing are necessary, neither can be used to satisfy a future allocation request while the current allocation exists.
 A free object also contains management data, \eg size, pointers, etc.
+A free object often contains management data, \eg size, pointers, etc.
 Often the free list is chained internally so it does not consume additional storage, \ie the link fields are placed at known locations in the unused memory blocks.
 For internal chaining, the amount of management data for a free node defines the minimum allocation size, \eg if 16 bytes are needed for a free-list node, allocation requests less than 16 bytes are rounded up.
 The information in an allocated or freed object is overwritten when it transitions from allocated to freed and vice-versa by new management information and/or program data.
+The information in an allocated or freed object is overwritten when it transitions from allocated to freed and vice-versa by new program data and/or management information.
 \begin{figure}
 …
 \label{s:Fragmentation}
 Fragmentation is memory requested from the operating system but not used by the program;
+Fragmentation is memory requested from the OS but not used by the program;
 hence, allocated objects are not fragmentation.
 Figure~\ref{f:InternalExternalFragmentation} shows fragmentation is divided into two forms: internal or external.
 …
 An allocator should strive to keep internal management information to a minimum.
 \newterm{External fragmentation} is all memory space reserved from the operating system but not allocated to the program~\cite{Wilson95,Lim98,Siebert00}, which includes all external management data, freed objects, and reserved memory.
+\newterm{External fragmentation} is all memory space reserved from the OS but not allocated to the program~\cite{Wilson95,Lim98,Siebert00}, which includes all external management data, freed objects, and reserved memory.
 This memory is problematic in two ways: heap blowup and highly fragmented memory.
 \newterm{Heap blowup} occurs when freed memory cannot be reused for future allocations leading to potentially unbounded external fragmentation growth~\cite{Berger00}.
 Memory can become \newterm{highly fragmented} after multiple allocations and deallocations of objects, resulting in a checkerboard of adjacent allocated and free areas, where the free blocks have become very small.
+Memory can become \newterm{highly fragmented} after multiple allocations and deallocations of objects, resulting in a checkerboard of adjacent allocated and free areas, where the free blocks have become to small to service requests.
 % Figure~\ref{f:MemoryFragmentation} shows an example of how a small block of memory fragments as objects are allocated and deallocated over time.
 Heap blowup can occur due to allocator policies that are too restrictive in reusing freed memory (the allocated size cannot use a larger free block) and/or no coalescing of free storage.
 …
 % Memory is highly fragmented when most free blocks are unusable because of their sizes.
 % For example, Figure~\ref{f:Contiguous} and Figure~\ref{f:HighlyFragmented} have the same quantity of external fragmentation, but Figure~\ref{f:HighlyFragmented} is highly fragmented.
 % If there is a request to allocate a large object, Figure~\ref{f:Contiguous} is more likely to be able to satisfy it with existing free memory, while Figure~\ref{f:HighlyFragmented} likely has to request more memory from the operating system.
+% If there is a request to allocate a large object, Figure~\ref{f:Contiguous} is more likely to be able to satisfy it with existing free memory, while Figure~\ref{f:HighlyFragmented} likely has to request more memory from the OS.
 % \begin{figure}
 …
 The first approach is a \newterm{sequential-fit algorithm} with one list of free objects that is searched for a block large enough to fit a requested object size.
 Different search policies determine the free object selected, \eg the first free object large enough or closest to the requested size.
 Any storage larger than the request can become spacing after the object or be split into a smaller free object.
+Any storage larger than the request can become spacing after the object or split into a smaller free object.
 % The cost of the search depends on the shape and quality of the free list, \eg a linear versus a binary-tree free-list, a sorted versus unsorted free-list.
 …
 The third approach is \newterm{splitting} and \newterm{coalescing algorithms}.
 When an object is allocated, if there are no free objects of the requested size, a larger free object may be split into two smaller objects to satisfy the allocation request without obtaining more memory from the operating system.
 For example, in the \newterm{buddy system}, a block of free memory is split into two equal chunks, one of those chunks is again split into two equal chunks, and so on until a block just large enough to fit the requested object is created.
 When an object is deallocated it is coalesced with the objects immediately before and after it in memory, if they are free, turning them into one larger object.
+When an object is allocated, if there are no free objects of the requested size, a larger free object is split into two smaller objects to satisfy the allocation request rather than obtaining more memory from the OS.
+For example, in the \newterm{buddy system}, a block of free memory is split into equal chunks, one of those chunks is again split, and so on until a minimal block is created that fits the requested object.
+When an object is deallocated, it is coalesced with the objects immediately before and after it in memory, if they are free, turning them into one larger block.
 Coalescing can be done eagerly at each deallocation or lazily when an allocation cannot be fulfilled.
 In all cases, coalescing increases allocation latency, hence some allocations can cause unbounded delays during coalescing.
+In all cases, coalescing increases allocation latency, hence some allocations can cause unbounded delays.
 While coalescing does not reduce external fragmentation, the coalesced blocks improve fragmentation quality so future allocations are less likely to cause heap blowup.
 % Splitting and coalescing can be used with other algorithms to avoid highly fragmented memory.
 …
 \label{s:Locality}
 The principle of locality recognizes that programs tend to reference a small set of data, called a working set, for a certain period of time, where a working set is composed of temporal and spatial accesses~\cite{Denning05}.
+The principle of locality recognizes that programs tend to reference a small set of data, called a \newterm{working set}, for a certain period of time, composed of temporal and spatial accesses~\cite{Denning05}.
 % Temporal clustering implies a group of objects are accessed repeatedly within a short time period, while spatial clustering implies a group of objects physically close together (nearby addresses) are accessed repeatedly within a short time period.
 % Temporal locality commonly occurs during an iterative computation with a fixed set of disjoint variables, while spatial locality commonly occurs when traversing an array.
 Hardware takes advantage of temporal and spatial locality through multiple levels of caching, \ie memory hierarchy.
+Hardware takes advantage of the working set through multiple levels of caching, \ie memory hierarchy.
 % When an object is accessed, the memory physically located around the object is also cached with the expectation that the current and nearby objects will be referenced within a short period of time.
 For example, entire cache lines are transferred between memory and cache and entire virtual-memory pages are transferred between disk and memory.
+For example, entire cache lines are transferred between cache and memory, and entire virtual-memory pages are transferred between memory and disk.
 % A program exhibiting good locality has better performance due to fewer cache misses and page faults\footnote{With the advent of large RAM memory, paging is becoming less of an issue in modern programming.}.
 …
 \label{s:MutualExclusion}
 \newterm{Mutual exclusion} provides sequential access to the shared management data of the heap.
+\newterm{Mutual exclusion} provides sequential access to the shared-management data of the heap.
 There are two performance issues for mutual exclusion.
 First is the overhead necessary to perform (at least) a hardware atomic operation every time a shared resource is accessed.
 Second is when multiple threads contend for a shared resource simultaneously, and hence, some threads must wait until the resource is released.
 Contention can be reduced in a number of ways:
 ) Using multiple fine-grained locks versus a single lock, spreading the contention across a number of locks.
+) Using multiple fine-grained locks versus a single lock to spread the contention across a number of locks.
 ) Using trylock and generating new storage if the lock is busy, yielding a classic space versus time tradeoff.
 ) Using one of the many lock-free approaches for reducing contention on basic data-structure operations~\cite{Oyama99}.
 …
 a memory allocator can only affect the latter two.
 Assume two objects, object$_1$ and object$_2$, share a cache line.
 \newterm{Program-induced false-sharing} occurs when thread$_1$ passes a reference to object$_2$ to thread$_2$, and then threads$_1$ modifies object$_1$ while thread$_2$ modifies object$_2$.
+Specifically, assume two objects, O$_1$ and O$_2$, share a cache line, with threads, T$_1$ and T$_2$.
+\newterm{Program-induced false-sharing} occurs when T$_1$ passes a reference to O$_2$ to T$_2$, and then T$_1$ modifies O$_1$ while T$_2$ modifies O$_2$.
 % Figure~\ref{f:ProgramInducedFalseSharing} shows when Thread$_1$ passes Object$_2$ to Thread$_2$, a false-sharing situation forms when Thread$_1$ modifies Object$_1$ and Thread$_2$ modifies Object$_2$.
 % Changes to Object$_1$ invalidate CPU$_2$'s cache line, and changes to Object$_2$ invalidate CPU$_1$'s cache line.
 …
 % \label{f:FalseSharing}
 % \end{figure}
 \newterm{Allocator-induced active false-sharing}\label{s:AllocatorInducedActiveFalseSharing} occurs when object$_1$ and object$_2$ are heap allocated and their references are passed to thread$_1$ and thread$_2$, which modify the objects.
+\newterm{Allocator-induced active false-sharing}\label{s:AllocatorInducedActiveFalseSharing} occurs when O$_1$ and O$_2$ are heap allocated and their references are passed to T$_1$ and T$_2$, which modify the objects.
 % For example, in Figure~\ref{f:AllocatorInducedActiveFalseSharing}, each thread allocates an object and loads a cache-line of memory into its associated cache.
 % Again, changes to Object$_1$ invalidate CPU$_2$'s cache line, and changes to Object$_2$ invalidate CPU$_1$'s cache line.
 …
 % is another form of allocator-induced false-sharing caused by program-induced false-sharing.
 % When an object in a program-induced false-sharing situation is deallocated, a future allocation of that object may cause passive false-sharing.
 when thread$_1$ passes object$_2$ to thread$_2$, and thread$_2$ subsequently deallocates object$_2$, and then object$_2$ is reallocated to thread$_2$ while thread$_1$ is still using object$_1$.
+when T$_1$ passes O$_2$ to T$_2$, and T$_2$ subsequently deallocates O$_2$, and then O$_2$ is reallocated to T$_2$ while T$_1$ is still using O$_1$.
 …
 \label{s:MultiThreadedMemoryAllocatorFeatures}
+The following features are used in the construction of multi-threaded memory-allocators:
+\begin{enumerate}[itemsep=0pt]
+\item multiple heaps: with or without a global heap, or with or without heap ownership.
+\item object containers: with or without ownership, fixed or variable sized, global or local free-lists.
+\item hybrid private/public heap
+\item allocation buffer
+\item lock-free operations
+\end{enumerate}
+The following features are used in the construction of multi-threaded memory-allocators: multiple heaps, user-level threading, ownership, object containers, allocation buffer, lock-free operations.
 The first feature, multiple heaps, pertains to different kinds of heaps.
 The second feature, object containers, pertains to the organization of objects within the storage area.
 …
 \subsection{Multiple Heaps}
+\subsubsection{Multiple Heaps}
 \label{s:MultipleHeaps}
 A multi-threaded allocator has potentially multiple threads and heaps.
 The multiple threads cause complexity, and multiple heaps are a mechanism for dealing with the complexity.
 The spectrum ranges from multiple threads using a single heap, denoted as T:1 (see Figure~\ref{f:SingleHeap}), to multiple threads sharing multiple heaps, denoted as T:H (see Figure~\ref{f:SharedHeaps}), to one thread per heap, denoted as 1:1 (see Figure~\ref{f:PerThreadHeap}), which is almost back to a single-threaded allocator.
+The spectrum ranges from multiple threads using a single heap, denoted as T:1, to multiple threads sharing multiple heaps, denoted as T:H, to one thread per heap, denoted as 1:1, which is almost back to a single-threaded allocator.
 \begin{figure}
 …
 \end{figure}
 \paragraph{T:1 model} where all threads allocate and deallocate objects from one heap.
 Memory is obtained from the freed objects, or reserved memory in the heap, or from the operating system (OS);
 the heap may also return freed memory to the operating system.
+\paragraph{T:1 model (see Figure~\ref{f:SingleHeap})} where all threads allocate and deallocate objects from one heap.
+Memory is obtained from the freed objects, or reserved memory in the heap, or from the OS;
+the heap may also return freed memory to the OS.
 The arrows indicate the direction memory conceptually moves for each kind of operation: allocation moves memory along the path from the heap/operating-system to the user application, while deallocation moves memory along the path from the application back to the heap/operating-system.
 To safely handle concurrency, a single lock may be used for all heap operations or fine-grained locking for different operations.
 Regardless, a single heap may be a significant source of contention for programs with a large amount of memory allocation.
 \paragraph{T:H model} where each thread allocates storage from several heaps depending on certain criteria, with the goal of reducing contention by spreading allocations/deallocations across the heaps.
+\paragraph{T:H model (see Figure~\ref{f:SharedHeaps})} where each thread allocates storage from several heaps depending on certain criteria, with the goal of reducing contention by spreading allocations/deallocations across the heaps.
 The decision on when to create a new heap and which heap a thread allocates from depends on the allocator design.
 To determine which heap to access, each thread must point to its associated heap in some way.
 …
 An alternative implementation is for all heaps to share one reserved memory, which requires a separate lock for the reserved storage to ensure mutual exclusion when acquiring new memory.
 Because multiple threads can allocate/free/reallocate adjacent storage, all forms of false sharing may occur.
 Other storage-management options are to use @mmap@ to set aside (large) areas of virtual memory for each heap and suballocate each heap's storage within that area, pushing part of the storage management complexity back to the operating system.
+Other storage-management options are to use @mmap@ to set aside (large) areas of virtual memory for each heap and suballocate each heap's storage within that area, pushing part of the storage management complexity back to the OS.
 % \begin{figure}
 …
 Multiple heaps increase external fragmentation as the ratio of heaps to threads increases, which can lead to heap blowup.
 The external fragmentation experienced by a program with a single heap is now multiplied by the number of heaps, since each heap manages its own free storage and allocates its own reserved memory.
 Additionally, objects freed by one heap cannot be reused by other threads without increasing the cost of the memory operations, except indirectly by returning free memory to the operating system, which can be expensive.
 Depending on how the operating system provides dynamic storage to an application, returning storage may be difficult or impossible, \eg the contiguous @sbrk@ area in Unix.
 In the worst case, a program in which objects are allocated from one heap but deallocated to another heap means these freed objects are never reused.
+Additionally, objects freed by one heap cannot be reused by other threads without increasing the cost of the memory operations, except indirectly by returning free memory to the OS (see Section~\ref{s:Ownership}).
+Returning storage to the OS may be difficult or impossible, \eg the contiguous @sbrk@ area in Unix.
+% In the worst case, a program in which objects are allocated from one heap but deallocated to another heap means these freed objects are never reused.
 Adding a \newterm{global heap} (G) attempts to reduce the cost of obtaining/returning memory among heaps (sharing) by buffering storage within the application address-space.
 Now, each heap obtains and returns storage to/from the global heap rather than the operating system.
+Now, each heap obtains and returns storage to/from the global heap rather than the OS.
 Storage is obtained from the global heap only when a heap allocation cannot be fulfilled, and returned to the global heap when a heap's free memory exceeds some threshold.
 Similarly, the global heap buffers this memory, obtaining and returning storage to/from the operating system as necessary.
+Similarly, the global heap buffers this memory, obtaining and returning storage to/from the OS as necessary.
 The global heap does not have its own thread and makes no internal allocation requests;
 instead, it uses the application thread, which called one of the multiple heaps and then the global heap, to perform operations.
 Hence, the worst-case cost of a memory operation includes all these steps.
+With respect to heap blowup, the global heap provides an indirect mechanism to move free memory among heaps, which usually has a much lower cost than interacting with the operating system to achieve the same goal and is independent of the mechanism used by the operating system to present dynamic memory to an address space.
+With respect to heap blowup, the global heap provides an indirect mechanism to move free memory among heaps, which usually has a much lower cost than interacting with the OS to achieve the same goal and is independent of the mechanism used by the OS to present dynamic memory to an address space.
 However, since any thread may indirectly perform a memory operation on the global heap, it is a shared resource that requires locking.
 A single lock can be used to protect the global heap or fine-grained locking can be used to reduce contention.
 In general, the cost is minimal since the majority of memory operations are completed without the use of the global heap.
+\paragraph{1:1 model (thread heaps)} where each thread has its own heap eliminating most contention and locking because threads seldom access another thread's heap (see ownership in Section~\ref{s:Ownership}).
+\paragraph{1:1 model (see Figure~\ref{f:PerThreadHeap})} where each thread has its own heap eliminating most contention and locking because threads seldom access another thread's heap (see Section~\ref{s:Ownership}).
 An additional benefit of thread heaps is improved locality due to better memory layout.
 As each thread only allocates from its heap, all objects are consolidated in the storage area for that heap, better utilizing each CPUs cache and accessing fewer pages.
 …
 Thread heaps can also eliminate allocator-induced active false-sharing, if memory is acquired so it does not overlap at crucial boundaries with memory for another thread's heap.
 For example, assume page boundaries coincide with cache line boundaries, if a thread heap always acquires pages of memory then no two threads share a page or cache line unless pointers are passed among them.
 Hence, allocator-induced active false-sharing cannot occur because the memory for thread heaps never overlaps.
+% Hence, allocator-induced active false-sharing cannot occur because the memory for thread heaps never overlaps.
 When a thread terminates, there are two options for handling its thread heap.
 …
 It is possible to use any of the heap models with user-level (M:N) threading.
 However, an important goal of user-level threading is for fast operations (creation/termination/context-switching) by not interacting with the operating system, which allows the ability to create large numbers of high-performance interacting threads ($>$ 10,000).
+However, an important goal of user-level threading is for fast operations (creation/termination/context-switching) by not interacting with the OS, which allows the ability to create large numbers of high-performance interacting threads ($>$ 10,000).
 It is difficult to retain this goal, if the user-threading model is directly involved with the heap model.
 Figure~\ref{f:UserLevelKernelHeaps} shows that virtually all user-level threading systems use whatever kernel-level heap-model is provided by the language runtime.
 …
 \end{figure}
 Adopting this model results in a subtle problem with shared heaps.
 With kernel threading, an operation that is started by a kernel thread is always completed by that thread.
 For example, if a kernel thread starts an allocation/deallocation on a shared heap, it always completes that operation with that heap even if preempted, \ie any locking correctness associated with the shared heap is preserved across preemption.
+Adopting user threading results in a subtle problem with shared heaps.
+With kernel threading, an operation started by a kernel thread is always completed by that thread.
+For example, if a kernel thread starts an allocation/deallocation on a shared heap, it always completes that operation with that heap, even if preempted, \ie any locking correctness associated with the shared heap is preserved across preemption.
 However, this correctness property is not preserved for user-level threading.
 A user thread can start an allocation/deallocation on one kernel thread, be preempted (time slice), and continue running on a different kernel thread to complete the operation~\cite{Dice02}.
 When the user thread continues on the new kernel thread, it may have pointers into the previous kernel-thread's heap and hold locks associated with it.
 To get the same kernel-thread safety, time slicing must be disabled/\-enabled around these operations, so the user thread cannot jump to another kernel thread.
 However, eagerly disabling/enabling time-slicing on the allocation/deallocation fast path is expensive, because preemption does not happen that frequently.
+However, eagerly disabling/enabling time-slicing on the allocation/deallocation fast path is expensive, because preemption is infrequent (milliseconds).
 Instead, techniques exist to lazily detect this case in the interrupt handler, abort the preemption, and return to the operation so it can complete atomically.
 Occasionally ignoring a preemption should be benign, but a persistent lack of preemption can result in both short and long term starvation;
 techniques like rollforward can be used to force an eventual preemption.
+Occasional ignoring of a preemption should be benign, but a persistent lack of preemption can result in starvation;
+techniques like rolling forward the preemption to the next context switch can be used.
 …
 % For example, in Figure~\ref{f:AllocatorInducedPassiveFalseSharing}, Object$_2$ may be deallocated to Thread$_2$'s heap initially.
 % If Thread$_2$ reallocates Object$_2$ before it is returned to its owner heap, then passive false-sharing may occur.
+For thread heaps with ownership, it is possible to combine these approaches into a hybrid approach with both private and public heaps.% (see~Figure~\ref{f:HybridPrivatePublicHeap}).
+The main goal of the hybrid approach is to eliminate locking on thread-local allocation/deallocation, while providing ownership to prevent heap blowup.
+In the hybrid approach, a thread first allocates from its private heap and second from its public heap if no free memory exists in the private heap.
+Similarly, a thread first deallocates an object to its private heap, and second to the public heap.
+Both private and public heaps can allocate/deallocate to/from the global heap if there is no free memory or excess free memory, although an implementation may choose to funnel all interaction with the global heap through one of the heaps.
+% Note, deallocation from the private to the public (dashed line) is unlikely because there is no obvious advantages unless the public heap provides the only interface to the global heap.
+Finally, when a thread frees an object it does not own, the object is either freed immediately to its owner's public heap or put in the freeing thread's private heap for delayed ownership, which does allows the freeing thread to temporarily reuse an object before returning it to its owner or batch objects for an owner heap into a single return.
+% \begin{figure}
+% \centering
+% \input{PrivatePublicHeaps.pstex_t}
+% \caption{Hybrid Private/Public Heap for Per-thread Heaps}
+% \label{f:HybridPrivatePublicHeap}
+% \vspace{10pt}
+% \input{RemoteFreeList.pstex_t}
+% \caption{Remote Free-List}
+% \label{f:RemoteFreeList}
+% \end{figure}
+% As mentioned, an implementation may have only one heap interact with the global heap, so the other heap can be simplified.
+% For example, if only the private heap interacts with the global heap, the public heap can be reduced to a lock-protected free-list of objects deallocated by other threads due to ownership, called a \newterm{remote free-list}.
+% To avoid heap blowup, the private heap allocates from the remote free-list when it reaches some threshold or it has no free storage.
+% Since the remote free-list is occasionally cleared during an allocation, this adds to that cost.
+% Clearing the remote free-list is $O(1)$ if the list can simply be added to the end of the private-heap's free-list, or $O(N)$ if some action must be performed for each freed object.
+% If only the public heap interacts with other threads and the global heap, the private heap can handle thread-local allocations and deallocations without locking.
+% In this scenario, the private heap must deallocate storage after reaching a certain threshold to the public heap (and then eventually to the global heap from the public heap) or heap blowup can occur.
+% If the public heap does the major management, the private heap can be simplified to provide high-performance thread-local allocations and deallocations.
+% The main disadvantage of each thread having both a private and public heap is the complexity of managing two heaps and their interactions in an allocator.
+% Interestingly, heap implementations often focus on either a private or public heap, giving the impression a single versus a hybrid approach is being used.
+% In many case, the hybrid approach is actually being used, but the simpler heap is just folded into the complex heap, even though the operations logically belong in separate heaps.
+% For example, a remote free-list is actually a simple public-heap, but may be implemented as an integral component of the complex private-heap in an allocator, masking the presence of a hybrid approach.
 …
 \subsection{Object Containers}
+\subsubsection{Object Containers}
 \label{s:ObjectContainers}
 …
 \eg an object is accessed by the program after it is allocated, while the header is accessed by the allocator after it is free.
 The alternative factors common header data to a separate location in memory and organizes associated free storage into blocks called \newterm{object containers} (\newterm{superblocks} in~\cite{Berger00}), as in Figure~\ref{f:ObjectContainer}.
+An alternative approach factors common header data to a separate location in memory and organizes associated free storage into blocks called \newterm{object containers} (\newterm{superblocks}~\cite{Berger00}), as in Figure~\ref{f:ObjectContainer}.
 The header for the container holds information necessary for all objects in the container;
 a trailer may also be used at the end of the container.
 …
 \subsubsection{Container Ownership}
+\paragraph{Container Ownership}
 \label{s:ContainerOwnership}
 …
 Additional restrictions may be applied to the movement of containers to prevent active false-sharing.
 For example, if a container changes ownership through the global heap, then when a thread allocates an object from the newly acquired container it is actively false-sharing even though no objects are passed among threads.
+For example, if a container changes ownership through the global heap, then a thread allocating from the newly acquired container is actively false-sharing even though no objects are passed among threads.
 Note, once the thread frees the object, no more false sharing can occur until the container changes ownership again.
 To prevent this form of false sharing, container movement may be restricted to when all objects in the container are free.
 One implementation approach that increases the freedom to return a free container to the operating system involves allocating containers using a call like @mmap@, which allows memory at an arbitrary address to be returned versus only storage at the end of the contiguous @sbrk@ area, again pushing storage management complexity back to the operating system.
+One implementation approach that increases the freedom to return a free container to the OS involves allocating containers using a call like @mmap@, which allows memory at an arbitrary address to be returned versus only storage at the end of the contiguous @sbrk@ area, again pushing storage management complexity back to the OS.
 % \begin{figure}
 …
 \subsubsection{Container Size}
+\paragraph{Container Size}
 \label{s:ContainerSize}
 …
 However, with more objects in a container, there may be more objects that are unallocated, increasing external fragmentation.
 With smaller containers, not only are there more containers, but a second new problem arises where objects are larger than the container.
 In general, large objects, \eg greater than 64\,KB, are allocated directly from the operating system and are returned immediately to the operating system to reduce long-term external fragmentation.
+In general, large objects, \eg greater than 64\,KB, are allocated directly from the OS and are returned immediately to the OS to reduce long-term external fragmentation.
 If the container size is small, \eg 1\,KB, then a 1.5\,KB object is treated as a large object, which is likely to be inappropriate.
 Ideally, it is best to use smaller containers for smaller objects, and larger containers for medium objects, which leads to the issue of locating the container header.
 …
 \subsubsection{Container Free-Lists}
+\paragraph{Container Free-Lists}
 \label{s:containersfreelists}
 …
+\subsubsection{Hybrid Private/Public Heap}
+\label{s:HybridPrivatePublicHeap}
+Section~\ref{s:Ownership} discusses advantages and disadvantages of public heaps (T:H model and with ownership) and private heaps (thread heaps with ownership).
+For thread heaps with ownership, it is possible to combine these approaches into a hybrid approach with both private and public heaps (see~Figure~\ref{f:HybridPrivatePublicHeap}).
+The main goal of the hybrid approach is to eliminate locking on thread-local allocation/deallocation, while providing ownership to prevent heap blowup.
+In the hybrid approach, a thread first allocates from its private heap and second from its public heap if no free memory exists in the private heap.
+Similarly, a thread first deallocates an object to its private heap, and second to the public heap.
+Both private and public heaps can allocate/deallocate to/from the global heap if there is no free memory or excess free memory, although an implementation may choose to funnel all interaction with the global heap through one of the heaps.
+Note, deallocation from the private to the public (dashed line) is unlikely because there is no obvious advantages unless the public heap provides the only interface to the global heap.
+Finally, when a thread frees an object it does not own, the object is either freed immediately to its owner's public heap or put in the freeing thread's private heap for delayed ownership, which allows the freeing thread to temporarily reuse an object before returning it to its owner or batch objects for an owner heap into a single return.
+\begin{figure}
+\centering
+\input{PrivatePublicHeaps.pstex_t}
+\caption{Hybrid Private/Public Heap for Per-thread Heaps}
+\label{f:HybridPrivatePublicHeap}
+% \vspace{10pt}
+% \input{RemoteFreeList.pstex_t}
+% \caption{Remote Free-List}
+% \label{f:RemoteFreeList}
+\end{figure}
+As mentioned, an implementation may have only one heap interact with the global heap, so the other heap can be simplified.
+For example, if only the private heap interacts with the global heap, the public heap can be reduced to a lock-protected free-list of objects deallocated by other threads due to ownership, called a \newterm{remote free-list}.
+To avoid heap blowup, the private heap allocates from the remote free-list when it reaches some threshold or it has no free storage.
+Since the remote free-list is occasionally cleared during an allocation, this adds to that cost.
+Clearing the remote free-list is $O(1)$ if the list can simply be added to the end of the private-heap's free-list, or $O(N)$ if some action must be performed for each freed object.
+If only the public heap interacts with other threads and the global heap, the private heap can handle thread-local allocations and deallocations without locking.
+In this scenario, the private heap must deallocate storage after reaching a certain threshold to the public heap (and then eventually to the global heap from the public heap) or heap blowup can occur.
+If the public heap does the major management, the private heap can be simplified to provide high-performance thread-local allocations and deallocations.
+The main disadvantage of each thread having both a private and public heap is the complexity of managing two heaps and their interactions in an allocator.
+Interestingly, heap implementations often focus on either a private or public heap, giving the impression a single versus a hybrid approach is being used.
+In many case, the hybrid approach is actually being used, but the simpler heap is just folded into the complex heap, even though the operations logically belong in separate heaps.
+For example, a remote free-list is actually a simple public-heap, but may be implemented as an integral component of the complex private-heap in an allocator, masking the presence of a hybrid approach.
+\subsection{Allocation Buffer}
+\subsubsection{Allocation Buffer}
 \label{s:AllocationBuffer}
 An allocation buffer is reserved memory (see Section~\ref{s:AllocatorComponents}) not yet allocated to the program, and is used for allocating objects when the free list is empty.
 That is, rather than requesting new storage for a single object, an entire buffer is requested from which multiple objects are allocated later.
 Any heap may use an allocation buffer, resulting in allocation from the buffer before requesting objects (containers) from the global heap or operating system, respectively.
+Any heap may use an allocation buffer, resulting in allocation from the buffer before requesting objects (containers) from the global heap or OS, respectively.
 The allocation buffer reduces contention and the number of global/operating-system calls.
 For coalescing, a buffer is split into smaller objects by allocations, and recomposed into larger buffer areas during deallocations.
 …
 Allocation buffers may increase external fragmentation, since some memory in the allocation buffer may never be allocated.
 A smaller allocation buffer reduces the amount of external fragmentation, but increases the number of calls to the global heap or operating system.
+A smaller allocation buffer reduces the amount of external fragmentation, but increases the number of calls to the global heap or OS.
 The allocation buffer also slightly increases internal fragmentation, since a pointer is necessary to locate the next free object in the buffer.
 …
 For example, when a container is created, rather than placing all objects within the container on the free list, the objects form an allocation buffer and are allocated from the buffer as allocation requests are made.
 This lazy method of constructing objects is beneficial in terms of paging and caching.
 For example, although an entire container, possibly spanning several pages, is allocated from the operating system, only a small part of the container is used in the working set of the allocator, reducing the number of pages and cache lines that are brought into higher levels of cache.
 \subsection{Lock-Free Operations}
+For example, although an entire container, possibly spanning several pages, is allocated from the OS, only a small part of the container is used in the working set of the allocator, reducing the number of pages and cache lines that are brought into higher levels of cache.
+\subsubsection{Lock-Free Operations}
 \label{s:LockFreeOperations}
 …
 % A sequence of code that is guaranteed to run to completion before being invoked to accept another input is called serially-reusable code.~\cite{SeriallyReusable}\label{p:SeriallyReusable}
 % \end{quote}
 % If a KT is preempted during an allocation operation, the operating system can schedule another KT on the same CPU, which can begin an allocation operation before the previous operation associated with this CPU has completed, invalidating heap correctness.
+% If a KT is preempted during an allocation operation, the OS can schedule another KT on the same CPU, which can begin an allocation operation before the previous operation associated with this CPU has completed, invalidating heap correctness.
 % Note, the serially-reusable problem can occur in sequential programs with preemption, if the signal handler calls the preempted function, unless the function is serially reusable.
 % Essentially, the serially-reusable problem is a race condition on an unprotected critical subsection, where the operating system is providing the second thread via the signal handler.
+% Essentially, the serially-reusable problem is a race condition on an unprotected critical subsection, where the OS is providing the second thread via the signal handler.
+%
 % Library @librseq@~\cite{librseq} was used to perform a fast determination of the CPU and to ensure all memory operations complete on one CPU using @librseq@'s restartable sequences, which restart the critical subsection after undoing its writes, if the critical subsection is preempted.
 …
 A sequence of code that is guaranteed to run to completion before being invoked to accept another input is called serially-reusable code.~\cite{SeriallyReusable}\label{p:SeriallyReusable}
 \end{quote}
 If a KT is preempted during an allocation operation, the operating system can schedule another KT on the same CPU, which can begin an allocation operation before the previous operation associated with this CPU has completed, invalidating heap correctness.
+If a KT is preempted during an allocation operation, the OS can schedule another KT on the same CPU, which can begin an allocation operation before the previous operation associated with this CPU has completed, invalidating heap correctness.
 Note, the serially-reusable problem can occur in sequential programs with preemption, if the signal handler calls the preempted function, unless the function is serially reusable.
 Essentially, the serially-reusable problem is a race condition on an unprotected critical subsection, where the operating system is providing the second thread via the signal handler.
+Essentially, the serially-reusable problem is a race condition on an unprotected critical subsection, where the OS is providing the second thread via the signal handler.
 Library @librseq@~\cite{librseq} was used to perform a fast determination of the CPU and to ensure all memory operations complete on one CPU using @librseq@'s restartable sequences, which restart the critical subsection after undoing its writes, if the critical subsection is preempted.
 …
 For the T:H=CPU and 1:1 models, locking is eliminated along the allocation fastpath.
 However, T:H=CPU has poor operating-system support to determine the CPU id (heap id) and prevent the serially-reusable problem for KTs.
 More operating system support is required to make this model viable, but there is still the serially-reusable problem with user-level threading.
+More OS support is required to make this model viable, but there is still the serially-reusable problem with user-level threading.
 So the 1:1 model had no atomic actions along the fastpath and no special operating-system support requirements.
 The 1:1 model still has the serially-reusable problem with user-level threading, which is addressed in Section~\ref{s:UserlevelThreadingSupport}, and the greatest potential for heap blowup for certain allocation patterns.
 …
 A primary goal of llheap is low latency, hence the name low-latency heap (llheap).
 Two forms of latency are internal and external.
 Internal latency is the time to perform an allocation, while external latency is time to obtain/return storage from/to the operating system.
+Internal latency is the time to perform an allocation, while external latency is time to obtain/return storage from/to the OS.
 Ideally latency is $O(1)$ with a small constant.
 …
 The mitigating factor is that most programs have well behaved allocation patterns, where the majority of allocation operations can be $O(1)$, and heap blowup does not occur without coalescing (although the allocation footprint may be slightly larger).
 To obtain $O(1)$ external latency means obtaining one large storage area from the operating system and subdividing it across all program allocations, which requires a good guess at the program storage high-watermark and potential large external fragmentation.
+To obtain $O(1)$ external latency means obtaining one large storage area from the OS and subdividing it across all program allocations, which requires a good guess at the program storage high-watermark and potential large external fragmentation.
 Excluding real-time operating-systems, operating-system operations are unbounded, and hence some external latency is unavoidable.
 The mitigating factor is that operating-system calls can often be reduced if a programmer has a sense of the storage high-watermark and the allocator is capable of using this information (see @malloc_expansion@ \pageref{p:malloc_expansion}).
 …
 headers per allocation versus containers,
 no coalescing to minimize latency,
 global heap memory (pool) obtained from the operating system using @mmap@ to create and reuse heaps needed by threads,
+global heap memory (pool) obtained from the OS using @mmap@ to create and reuse heaps needed by threads,
 local reserved memory (pool) per heap obtained from global pool,
 global reserved memory (pool) obtained from the operating system using @sbrk@ call,
+global reserved memory (pool) obtained from the OS using @sbrk@ call,
 optional fast-lookup table for converting allocation requests into bucket sizes,
 optional statistic-counters table for accumulating counts of allocation operations.
 …
 Each heap uses segregated free-buckets that have free objects distributed across 91 different sizes from 16 to 4M.
 All objects in a bucket are of the same size.
 The number of buckets used is determined dynamically depending on the crossover point from @sbrk@ to @mmap@ allocation using @mallopt( M_MMAP_THRESHOLD )@, \ie small objects managed by the program and large objects managed by the operating system.
+The number of buckets used is determined dynamically depending on the crossover point from @sbrk@ to @mmap@ allocation using @mallopt( M_MMAP_THRESHOLD )@, \ie small objects managed by the program and large objects managed by the OS.
 Each free bucket of a specific size has two lists.
 ) A free stack used solely by the KT heap-owner, so push/pop operations do not require locking.
 …
 Algorithm~\ref{alg:heapObjectAlloc} shows the allocation outline for an object of size $S$.
 First, the allocation is divided into small (@sbrk@) or large (@mmap@).
 For large allocations, the storage is mapped directly from the operating system.
+For large allocations, the storage is mapped directly from the OS.
 For small allocations, $S$ is quantized into a bucket size.
 Quantizing is performed using a binary search over the ordered bucket array.
 …
 heap's local pool,
 global pool,
 operating system (@sbrk@).
+OS (@sbrk@).
 \begin{algorithm}
 …
 Algorithm~\ref{alg:heapObjectFreeOwn} shows the de-allocation (free) outline for an object at address $A$ with ownership.
 First, the address is divided into small (@sbrk@) or large (@mmap@).
 For large allocations, the storage is unmapped back to the operating system.
+For large allocations, the storage is unmapped back to the OS.
 For small allocations, the bucket associated with the request size is retrieved.
 If the bucket is local to the thread, the allocation is pushed onto the thread's associated bucket.
 …
 \textsf{pt3} is the only memory allocator where the total dynamic memory goes down in the second half of the program lifetime when the memory is freed by the benchmark program.
 It makes pt3 the only memory allocator that gives memory back to the operating system as it is freed by the program.
+It makes pt3 the only memory allocator that gives memory back to the OS as it is freed by the program.
 % FOR 1 THREAD

doc/papers/llheap/figures/AllocatorComponents.fig

-              rfa5e1aa5
+              rb7b3e41
 -2
 2
-1275 2025 2700 2625
 2400 2025 2700 2625
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
 …
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
 2025 2700 2325 2400 2325 2400 2025 2700 2025
--6
-2 0 50 -1 2 11 0.0000 2 165 1005 2325 2400 Management\001
 -6
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
 …
 2 0 1 0 7 60 -1 13 0.000 0 0 -1 0 0 5
 2700 6300 2700 6300 3000 3300 3000 3300 2700
 0 0 50 -1 2 11 0.0000 2 165 585 3300 1725 Storage\001
+0 0 50 -1 2 11 0.0000 2 165 1005 3300 1725 Storage Data\001
 2 0 50 -1 0 11 0.0000 2 165 810 3000 1875 free objects\001
 2 0 50 -1 0 11 0.0000 2 135 1140 3000 2850 reserve memory\001
 1 0 50 -1 0 11 0.0000 2 120 795 2325 1500 Static Zone\001
 1 0 50 -1 0 11 0.0000 2 165 1845 4800 1500 Dynamic-Allocation Zone\001
+2 0 50 -1 2 11 0.0000 2 165 1005 2325 2325 Management\001
+2 0 50 -1 2 11 0.0000 2 135 375 2325 2525 Data\001

doc/theses/colby_parsons_MMAth/Makefile

-              rfa5e1aa5
+              rb7b3e41
         figures/nasus_Channel_Contention \
         figures/pyke_Channel_Contention \
+        figures/pyke_Future \
+        figures/nasus_Future \
+        figures/pyke_Contend_2 \
+        figures/pyke_Contend_4 \
+        figures/pyke_Contend_8 \
+        figures/pyke_Spin_2 \
+        figures/pyke_Spin_4 \
+        figures/pyke_Spin_8 \
+        figures/nasus_Contend_2 \
+        figures/nasus_Contend_4 \
+        figures/nasus_Contend_8 \
+        figures/nasus_Spin_2 \
+        figures/nasus_Spin_4 \
+        figures/nasus_Spin_8 \
+}
 …
 ${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${DATA} \
                 glossary.tex style/style.tex ${Macros}/common.tex ${Macros}/indexstyle local.bib ../../bibliography/pl.bib | ${Build}
+                glossary.tex style/style.tex ${Macros}/common.tex ${Macros}/lstlang.sty ${Macros}/indexstyle local.bib ../../bibliography/pl.bib | ${Build}
         # Must have *.aux file containing citations for bibtex
         if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi
 …
 ## Define the default recipes.
 ${Build}:
+${Build} :
         mkdir -p ${Build}

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/balance.cfa

-              rfa5e1aa5
+              rb7b3e41
 d_actor ** actor_arr;
 Allocation receive( d_actor & this, start_msg & msg ) with( this ) {
+allocation receive( d_actor & this, start_msg & msg ) with( this ) {
     for ( i; Set ) {
         *actor_arr[i + gstart] << shared_msg;
+        *actor_arr[i + gstart] | shared_msg;
+    }
     return Nodelete;
+}
 Allocation receive( d_actor & this, d_msg & msg ) with( this ) {
+allocation receive( d_actor & this, d_msg & msg ) with( this ) {
     if ( recs == rounds ) return Delete;
     if ( recs % Batch == 0 ) {
         for ( i; Batch ) {
             *actor_arr[gstart + sends % Set] << shared_msg;
+            *actor_arr[gstart + sends % Set] | shared_msg;
             sends += 1;
+        }
 …
+}
 Allocation receive( filler & this, d_msg & msg ) { return Delete; }
+allocation receive( filler & this, d_msg & msg ) { return Delete; }
 int main( int argc, char * argv[] ) {
 …
     #ifndef MULTI
         for ( i; qpw )
                 *actors[i * ActorsPerQueue] << start_send;
+                *actors[i * ActorsPerQueue] | start_send;
     #else
     for ( i; qpw * ActorProcs ) {
                 *actors[i * ActorsPerQueue] << start_send;
+                *actors[i * ActorsPerQueue] | start_send;
+    }
     #endif
     for ( i; FillActors )
         *filler_actors[i] << shared_msg;
+        *filler_actors[i] | shared_msg;
     stop_actor_system();

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/dynamic.cfa

-              rfa5e1aa5
+              rb7b3e41
 uint64_t start_time;
 Allocation receive( derived_actor & receiver, derived_msg & msg ) {
+allocation receive( derived_actor & receiver, derived_msg & msg ) {
     if ( msg.cnt >= Times ) {
         printf("%.2f\n", ((double)(bench_time() - start_time)) / ((double)Times) ); // ns
 …
     derived_actor * d_actor = malloc();
     (*d_actor){};
     *d_actor << *d_msg;
+    *d_actor | *d_msg;
     return Delete;
+}
 …
     derived_actor * d_actor = malloc();
     (*d_actor){};
     *d_actor << *d_msg;
+    *d_actor | *d_msg;

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/executor.cfa

-              rfa5e1aa5
+              rb7b3e41
 struct d_msg { inline message; } shared_msg;
 Allocation receive( d_actor & this, d_msg & msg ) with( this ) {
+allocation receive( d_actor & this, d_msg & msg ) with( this ) {
     if ( recs == rounds ) return Finished;
     if ( recs % Batch == 0 ) {
         for ( i; Batch ) {
             gstart[sends % Set] << shared_msg;
+            gstart[sends % Set] | shared_msg;
             sends += 1;
+        }
 …
         for ( i; Actors ) {
                 actors[i] << shared_msg;
+                actors[i] | shared_msg;
         } // for

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/matrix.cfa

-              rfa5e1aa5
+              rb7b3e41
+}
 Allocation receive( derived_actor & receiver, derived_msg & msg ) {
+allocation receive( derived_actor & receiver, derived_msg & msg ) {
     for ( unsigned int i = 0; i < yc; i += 1 ) { // multiply X_row by Y_col and sum products
         msg.Z[i] = 0;
 …
         for ( unsigned int r = 0; r < xr; r += 1 ) {
                 actors[r] << messages[r];
+                actors[r] | messages[r];
         } // for

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/repeat.cfa

-              rfa5e1aa5
+              rb7b3e41
 Client * cl;
 Allocation receive( Server & this, IntMsg & msg ) { msg.val = 7; *cl << msg; return Nodelete; }
 Allocation receive( Server & this, CharMsg & msg ) { msg.val = 'x'; *cl << msg; return Nodelete; }
 Allocation receive( Server & this, StateMsg & msg ) { return Finished; }
+allocation receive( Server & this, IntMsg & msg ) { msg.val = 7; *cl | msg; return Nodelete; }
+allocation receive( Server & this, CharMsg & msg ) { msg.val = 'x'; *cl | msg; return Nodelete; }
+allocation receive( Server & this, StateMsg & msg ) { return Finished; }
 void terminateServers( Client & this ) with(this) {
     for ( i; Messages ) {
         servers[i] << stateMsg;
+        servers[i] | stateMsg;
     } // for
+}
 Allocation reset( Client & this ) with(this) {
+allocation reset( Client & this ) with(this) {
     times += 1;
     if ( times == Times ) { terminateServers( this ); return Finished; }
     results = 0;
     this << stateMsg;
+    this | stateMsg;
     return Nodelete;
+}
 Allocation process( Client & this ) with(this) {
+allocation process( Client & this ) with(this) {
     this.results++;
     if ( results == 2 * Messages ) { return reset( this ); }
 …
+}
 Allocation receive( Client & this, IntMsg & msg ) { return process( this ); }
 Allocation receive( Client & this, CharMsg & msg ) { return process( this ); }
 Allocation receive( Client & this, StateMsg & msg ) with(this) {
+allocation receive( Client & this, IntMsg & msg ) { return process( this ); }
+allocation receive( Client & this, CharMsg & msg ) { return process( this ); }
+allocation receive( Client & this, StateMsg & msg ) with(this) {
     for ( i; Messages ) {
         servers[i] << intmsg[i];
         servers[i] << charmsg[i];
+        servers[i] | intmsg[i];
+        servers[i] | charmsg[i];
+    }
     return Nodelete;
 …
     Client client;
     cl = &client;
     client << stateMsg;
+    client | stateMsg;
     stop_actor_system();

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/static.cfa

-              rfa5e1aa5
+              rb7b3e41
 uint64_t start_time;
 Allocation receive( derived_actor & receiver, derived_msg & msg ) {
+allocation receive( derived_actor & receiver, derived_msg & msg ) {
     if ( msg.cnt >= Times ) {
         printf("%.2f\n", ((double)(bench_time() - start_time)) / ((double)Times) ); // ns
 …
+    }
     msg.cnt++;
     receiver << msg;
+    receiver | msg;
     return Nodelete;
+}
 …
     derived_actor actor;
     actor << msg;
+    actor | msg;
     stop_actor_system();

doc/theses/colby_parsons_MMAth/benchmarks/actors/plotData.py

rfa5e1aa5	rb7b3e41
166	166	for idx, arr in enumerate(data):
167	167	plt.errorbar( procs, arr, [bars[idx][0], bars[idx][1]], capsize=2, marker=next(marker) )
	168	marker = itertools.cycle(('o', 's', 'D', 'x', 'p', '^', 'h', '*', 'v' ))
168	169	if currBench == Bench.Executor or currBench == Bench.Matrix or currBench == Bench.Balance_One or currBench == Bench.Repeat:
169	170	plt.yscale("log")

doc/theses/colby_parsons_MMAth/benchmarks/channels/plotData.py

rfa5e1aa5	rb7b3e41
130	130	for idx, arr in enumerate(data):
131	131	plt.errorbar( procs, arr, [bars[idx][0], bars[idx][1]], capsize=2, marker=next(marker) )
132
	132	marker = itertools.cycle(('o', 's', 'D', 'x', 'p', '^', 'h', '*', 'v' ))
133	133	plt.yscale("log")
134	134	# plt.ylim(1, None)

doc/theses/colby_parsons_MMAth/benchmarks/mutex_stmt/plotData.py

rfa5e1aa5	rb7b3e41
103	103	for idx, arr in enumerate(data):
104	104	plt.errorbar( procs, arr, [bars[idx][0], bars[idx][1]], capsize=2, marker=next(marker) )
	105	marker = itertools.cycle(('o', 's', 'D', 'x', 'p', '^', 'h', '*', 'v' ))
105	106	plt.yscale("log")
106	107	plt.xticks(procs)

doc/theses/colby_parsons_MMAth/code/basic_actor_example.cfa

rfa5e1aa5	rb7b3e41
19	19	}
20	20
21		Allocation receive( derived_actor & receiver, derived_msg & msg ) {
	21	allocation receive( derived_actor & receiver, derived_msg & msg ) {
22	22	printf("The message contained the string: %s\n", msg.word);
23	23	return Finished; // Return allocation status of Finished now that the actor is done work

doc/theses/colby_parsons_MMAth/diagrams/gulp.tikz

-              rfa5e1aa5
+              rb7b3e41
 % Text Node
 \draw (23,6) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\footnotesize Worker}};
+\draw (15,6) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\footnotesize Executor Thread}};
 % Text Node
 \draw (85,18) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\footnotesize Empty local queue}};
+\draw (85,20) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\footnotesize Empty local queue}};
 % Text Node
 \draw (8,197) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\footnotesize Sharded message queues}};
 …
 \draw (70,71) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\footnotesize Gulps queue 0}};
 % Text Node
 \draw (312,6) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\footnotesize Worker}};
+\draw (303,6) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\footnotesize Executor Thread}};
 % Text Node
 \draw (374,18) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\footnotesize Local queue}};
+\draw (374,21) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\footnotesize Local queue}};
 % Text Node
 \draw (297,198) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\footnotesize Sharded message queues}};

doc/theses/colby_parsons_MMAth/diagrams/inverted_actor.tikz

-              rfa5e1aa5
+              rb7b3e41
 % Text Node
 \draw (245,-2) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\footnotesize Worker Threads}};
+\draw (258,-2) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\small Executor}};
 % Text Node
 \draw (155,-2) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\footnotesize Actors}};
+\draw (155,-2) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\small Actors}};
 % Text Node
 \draw (21,73) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\footnotesize Message}\\{\footnotesize Queues}};
+\draw (21,73) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\small Message}\\{\small Queues}};

doc/theses/colby_parsons_MMAth/diagrams/standard_actor.tikz

-              rfa5e1aa5
+              rb7b3e41
 % Text Node
 \draw (186,6) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\footnotesize Worker Threads}};
+\draw (197,6) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\small Executor}};
 % Text Node
 \draw (91,9) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\footnotesize Actors}};
+\draw (91,9) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\small Actors}};
 % Text Node
 \draw (81,207) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\footnotesize Mailboxes}};
+\draw (78,207) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\small Mailboxes}};

doc/theses/colby_parsons_MMAth/glossary.tex

-              rfa5e1aa5
+              rb7b3e41
 \newabbreviation{toctou}{TOCTOU}{\Newterm{time-of-check to time-of-use}}
+\newglossaryentry{actor}
+{
+\newglossaryentry{actor}{
 name=actor,
 description={A basic unit of an actor system that can store local state and send messages to other actors.}
+}
+\newglossaryentry{impl_concurrency}
+{
+\newglossaryentry{gulp}{
+name={gulp},
+first={\Newterm{gulp}},
+description={Move the contents of message queue to a local queue of the executor thread using a single atomic instruction.}
+}
+\newglossaryentry{impl_concurrency}{
 name=implicit concurrency,
+first={\Newterm{implicit concurrency}},
 description={A class of concurrency features that abstract away explicit thread synchronization and mutual exclusion.}
+}
+\newglossaryentry{actor_model}
+{
+\newglossaryentry{actor_model}{
 name=actor model,
+first={\Newterm{actor model}},
 description={A concurrent computation model, where tasks are broken into units of work that are distributed to actors in the form of messages.}
+}
+\newglossaryentry{actor_system}
+{
+\newglossaryentry{actor_system}{
 name=actor system,
+first={\Newterm{actor system}},
 description={An implementation of the actor model.}
+}
+\newglossaryentry{synch_multiplex}
+{
+\newglossaryentry{synch_multiplex}{
 name=synchronous multiplexing,
+first={\Newterm{synchronous multiplexing}},
 description={synchronization on some subset of a set of resources.}
+}

doc/theses/colby_parsons_MMAth/local.bib

-              rfa5e1aa5
+              rb7b3e41
+}
+@misc{go:sched,
+  author = "The Go Programming Language",
+  title = "src/runtime/proc.go",
+  howpublished = {\href{https://go.dev/src/runtime/proc.go}},
+  note = "[Online; accessed 23-May-2023]"
+}
 @misc{go:selectref,
   author = "The Go Programming Language Specification",
 …
 @misc{linux:select,
   author = "Linux man pages",
   title = "select(2) — Linux manual page",
+  title = "select(2) - Linux manual page",
   howpublished = {\href{https://man7.org/linux/man-pages/man2/select.2.html}},
   note = "[Online; accessed 23-May-2023]"
 …
 @misc{linux:poll,
   author = "Linux man pages",
   title = "poll(2) — Linux manual page",
+  title = "poll(2) - Linux manual page",
   howpublished = {\href{https://man7.org/linux/man-pages/man2/poll.2.html}},
   note = "[Online; accessed 23-May-2023]"
 …
 @misc{linux:epoll,
   author = "Linux man pages",
   title = "epoll(7) — Linux manual page",
+  title = "epoll(7) - Linux manual page",
   howpublished = {\href{https://man7.org/linux/man-pages/man7/epoll.7.html}},
   note = "[Online; accessed 23-May-2023]"

doc/theses/colby_parsons_MMAth/style/style.tex

-              rfa5e1aa5
+              rb7b3e41
 \CFAStyle                                               % CFA code-style
 \lstset{language=CFA}                                   % default language
+\setlength{\gcolumnposn}{3in}
 \newcommand{\newtermFont}{\emph}
 \newcommand{\Newterm}[1]{\newtermFont{#1}}
+%\renewcommand{\newterm}[1]{\newtermFont{#1}}
 \newcommand{\code}[1]{\lstinline[language=CFA]{#1}}

doc/theses/colby_parsons_MMAth/text/CFA_intro.tex

rfa5e1aa5	rb7b3e41
179	179	\end{cfa}
180	180
181		\subsection{Inheritance}
	181	\subsection{Inheritance}\label{s:Inheritance}
182	182	Inheritance in \CFA is taken from Plan-9 C's nominal inheritance.
183	183	In \CFA, @struct@s can @inline@ another struct type to gain its fields and masquerade as that type.

doc/theses/colby_parsons_MMAth/text/actors.tex

-              rfa5e1aa5
+              rb7b3e41
 % C_TODO: add citations throughout chapter
+Actors are a concurrent feature that abstracts threading away from a user, and instead provides \gls{actor}s and messages as building blocks for concurrency.
+Actors are another message passing concurrency feature, similar to channels, but with more abstraction.
+Actors enter the realm of what is called \gls{impl_concurrency}, where programmers can write concurrent code without having to worry about explicit thread synchronization and mutual exclusion.
+The study of actors can be broken into two concepts, the \gls{actor_model}, which describes the model of computation and the \gls{actor_system}, which refers to the implementation of the model in practice.
+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, where message passing means there is no shared data to protect, making actors amenable in a distributed environment.
+Actors are another message passing concurrency feature, similar to channels but with more abstraction, and are in the realm of \gls{impl_concurrency}, where programmers write concurrent code without dealing with explicit thread creation or interaction.
+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{The Actor Model}
+The actor model is a paradigm of concurrent computation, where tasks are broken into units of work that are distributed to actors in the form of messages \cite{Hewitt73}.
+Actors execute asynchronously upon receiving a message and can modify their own state, make decisions, spawn more actors, and send messages to other actors.
+The actor model is an implicit model of concurrency.
+As such, one strength of the actor model is that it abstracts away many considerations that are needed in other paradigms of concurrent computation.
+Mutual exclusion, and locking are rarely relevant concepts to users of an actor model, as actors typically operate on local state.
+\section{Classic Actor System}
+An implementation of the actor model with a community of actors is called an actor system.
+Actor systems largely follow the actor model, but differ in some ways.
+While the definition of the actor model provides no restrictions on message ordering, actor systems tend to guarantee that messages sent from a given actor $i$ to actor $j$ will arrive at actor $j$ in the order they were sent.
+Another way an actor system varies from the model is that actors are often allowed to access non-local state.
+When this occurs it can complicate the implementation as this will break any mutual exclusion guarantees given by accessing only local state.
+\section{Actor Model}
+The actor model is a concurrent paradigm where computation is broken into units of work called actors, and the data for computation is distributed to actors in the form of messages~\cite{Hewitt73}.
+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.
+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.
+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{end of Section~\ref{s:CFAActor}}.
+\subsection{Classic Actor System}
+An implementation of the actor model with a community of actors is called an actor system.
+Actor systems largely follow the actor model, but can differ in some ways.
+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 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 requires additional locking).
+For non-FIFO service, some notion of fairness (eventual progress) must exist, otherwise messages have a high latency or starve, \ie 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$ will 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}}}
+\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}
+\section{\CFA Actors}
+Actor systems \cite{} have often been implemented as an actor-centric system.
+As such they are constructed as a set of actors that are scheduled and run on some underlying threads.
+Each actor has their own queue for receiving messages, sometimes called a mailbox.
+When they receive messages in their mailbox, actors are moved from idle to ready queues and then scheduled on a thread to run their unit of work.
+This approach can be implemented with a global queue of actors, but is often implemented as each worker thread owning a queue of actors.
+This is known as sharding the actor queue, which is done to decrease contention across worker threads.
+A diagram of an actor-centric system with a sharded actor queue is shown in Figure \ref{f:standard_actor}.
+\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 can attach 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 work unit on the message(s).
 % cite parallel theatre and our paper
+The actor system in \CFA is instead message-centric, an uses what is called an inverted actor system \cite{}.
+In this inverted actor system instead of each worker thread owning a queue of actors, they each own a queue of messages.
+This system is called inverted since in this scheme, actors belong to a message queue, whereas in the classic approach a message queue belongs to each actor.
+Since multiple actors belong to each message queue, messages to each actor are interleaved in the queue.
+In this scheme work is consumed from their queue and executed by underlying threads.
+In High-Performance Extended Actors \cite{} this inverted model is taken a step further and the message queues are sharded, so that each worker now instead owns a set of queues.
+A diagram of an inverted actor scheme with a sharded message queue is shown in Figure \ref{f:inverted_actor}.
+The arrows from the message queues to the actors in the diagram indicate interleaved messages addressed to each actor.
+The actor system in \CFA builds on top of the architecture laid out in High-Performance Extended Actors \cite{} and adds the following contributions:
+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}.
+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 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.
+This design is \Newterm{inverted} because actors belong to a message queue, whereas in the classic approach a message queue belongs to each actor.
+% 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{}, and adds the following contributions related to \CFA:
 \begin{enumerate}[topsep=5pt,itemsep=3pt,parsep=0pt]
 \item
 Provides insight into the impact of envelope allocation in actor systems.
 In all actor systems dynamic allocation is needed to ensure that the lifetime of a unit of work persists from its creation until the unit of work is executed.
 This allocation is often called an envelope as it "packages" the information needed to run the unit of work, alongside any other information needed to send the unit of work, such as an actor's address or link fields for a list.
 This dynamic allocation occurs once per message sent.
+This is a large source of contention on the memory allocator since all these allocations occur concurrently.
 A novel data structure is used to consolidate allocations to improve performance by minimizing contention on the allocator.
 \item
 Introduces work stealing in the inverted actor system.
+Work stealing in actor-centric systems tends to involve stealing one or more actors.
+In the inverted system the notion of stealing queues is introduced.
 The queue stealing is implemented such that the act of stealing work does not contend with non-stealing actors that are saturated with work.
+\item
 Introduces and evaluates a timestamp based work stealing heuristic with the goal of maintaining non-workstealing performance in work-saturated workloads, and improving performance on unbalanced workloads.
 \item
 Improves performance of the inverted actor system using multiple approaches to minimize contention on queues, such as queue gulping and avoiding atomic operations.
 \item
 Provides a suite of safety and productivity features including static-typing, detection of erroneous message sends, statistics tracking, and more.
+Provide insight into the impact of envelope allocation in actor systems.
+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 Syntax}
+\CFA is not an object oriented language and it does not have run-time type information (RTTI).
+As such all message sends and receives between actors occur using exact type matching.
+To use actors in \CFA you must \code{\#include <actors.hfa>}.
+To create an actor type one must define a struct which inherits from the base \code{actor} struct via the \code{inline} keyword.
+This is the Plan-9 C-style nominal inheritance discussed in Section \ref{s:poly}.
+Similarly to create a message type a user must define a struct which \code{inline}'s the base \code{message} struct.
+\begin{cfa}
+struct derived_actor {
+        inline actor;      // Plan-9 C inheritance
+};
+void ?{}( derived_actor & this ) { // Default ctor
+        ((actor &)this){};  // Call to actor ctor
+}
+struct derived_msg {
+        inline message;  // Plan-9 C nominal inheritance
+        char word[12];
+};
+void ?{}( derived_msg & this, char * new_word ) { // Overloaded ctor
+        ((message &) this){ Nodelete }; // Passing allocation to ctor
+        strcpy(this.word, new_word);
+}
+Allocation receive( derived_actor & receiver, derived_msg & msg ) {
+        printf("The message contained the string: %s\n", msg.word);
+        return Finished; // Return finished since actor is done
+}
+int main() {
+        start_actor_system(); // Sets up executor
+        derived_actor my_actor;
+        derived_msg my_msg{ "Hello World" }; // Constructor call
+        my_actor << my_msg;   // Send message via left shift operator
+        stop_actor_system(); // Waits until actors are finished
+        return 0;
+\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}
+The above code is a simple actor program in \CFA.
+There is one derived actor type and one derived message type.
+A single message containing a string is sent from the program main to an actor.
+Key things to highlight include the \code{receive} signature, and calls to \code{start_actor_system}, and \code{stop_actor_system}.
+To define a behaviour for some derived actor and derived message type, one must declare a routine with the signature:
+\end{lrbox}
+\begin{lrbox}{\myboxB}
 \begin{cfa}
+Allocation receive( derived_actor & receiver, derived_msg & msg )
+allocation receive( @msg_type1@ & msg ) {
+        ... msg ...;
+}
+allocation receive( @msg_type2@ & msg ) {
+        ... msg ...;
+}
+...
 \end{cfa}
+Where \code{derived_actor} and \code{derived_msg} can be any derived actor and derived message types respectively.
+The return value of \code{receive} must be a value from the \code{Allocation} enum:
+\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}
+enum Allocation { Nodelete, Delete, Destroy, Finished };
+// 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 (deallocation deferred)}$
+        stop_actor_system();                                    $\C{// waits until actors finish}\CRT$
+} // deallocate int_msg, str_msg, actor
 \end{cfa}
+The \code{Allocation} enum is a set of actions that dictate what the executor should do with a message or actor after a given behaviour has been completed.
+In the case of an actor, the \code{receive} routine returns the \code{Allocation} status to the executor which sets the status on the actor and takes the appropriate action.
+For messages, they either default to \code{Nodelete}, or they can be passed an \code{Allocation} via the \code{message} constructor.
+Message state can be updated via a call to:
+\caption{\CFA Actor Syntax}
+\label{f:CFAActor}
+\end{figure}
+Figure~\ref{f:CFAActor} shows a complete \CFA actor example starting with the actor type @my_actor@ created by defining a @struct@ that inherits from the base @actor@ @struct@ via the @inline@ keyword.
+This inheritance style is the Plan-9 C-style inheritance discussed in Section~\ref{s:Inheritance}.
+Similarly, the message types @str_msg@ and @int_msg@ are created by defining a @struct@ that inherits from the base @message@ @struct@ via the @inline@ keyword.
+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 and return @Nodelete@ indicating the actor is not finished.
+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@.
+Now an actor is created on the stack and four messages are sent it using operator @?|?@.
+The last message is the builtin @finish_msg@, which returns @Finished@ to an executor thread, causing it to removes the actor from the actor system \see{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 two messages from the stack.
+The output for the program is:
 \begin{cfa}
+void set_allocation( message & this, Allocation state )
+string message "Hello World"
+integer message 42
+integer message 42
 \end{cfa}
+The following describes the use of each of the \code{Allocation} values:
+\begin{description}
+\item[\LstBasicStyle{\textbf{Nodelete}}]
+tells the executor that no action is to be taken with regard to a message or actor with this status.
+This indicates that the actor will receive future behaviours, and that a message may be reused.
+\item[\LstBasicStyle{\textbf{Delete}}]
+tells the executor to call the appropriate destructor and then deallocate the respective actor or message.
+This status is typically used with dynamically allocated actors and messages.
+\item[\LstBasicStyle{\textbf{Destroy}}]
+tells the executor to call the object's destructor.
+The executor will not deallocate the respective actor or message.
+This status is typically used with dynamically allocated actors and messages whose storage will be reused.
+\item[\LstBasicStyle{\textbf{Finished}}]
+tells the executor to mark the respective actor as being finished executing.
+In this case the executor will not call any destructors or deallocate any objects.
+This status is used when the actors are stack allocated or if the user wants to manage deallocation of actors themselves.
+In the case of messages, \code{Finished} is no different than \code{Nodelete} since the executor does not need to track if messages are done work.
+As such \code{Finished} is not supported for messages and is used internally by the executor to track if messages have been used for debugging purposes.
+\end{description}
+For the actor system to gracefully terminate, all actors must have returned a status other than \code{Nodelete}.
+Once an actor's allocation status has been set to something other than \code{Nodelete}, it is erroneous for the actor to receive a message.
+Similarly messages cannot be safely reused after their related behaviour if their status is not \code{Nodelete}.
+Note, it is safe to construct a message with a non-\code{Nodelete} status since the executor will only take the appropriate allocation action after a message has been delivered.
+The calls to \code{start_actor_system}, and \code{stop_actor_system} mark the start and end of a \CFA actor system.
+The call to \code{start_actor_system} sets up the executor and worker threads for the actor system.
+\code{start_actor_system} has three overloaded signatures which all start the actor system, but vary in executor configuration:
+\noindent\code{void start_actor_system()} configures the executor with one underlying worker thread and processor.
+\noindent\code{void start_actor_system( size_t num_thds )} configures the executor with \code{num_thds} underlying processors and \code{num_thds} worker threads.
+It chooses amount of queue sharding as a function of \code{num_thds}.
+\noindent\code{void start_actor_system( executor & this )} allows the user to allocate, configure, and pass an executor so that they have full control of executor parameterization.
+Executor configuration options include number of worker threads, number of queues, number of processors, and a few other toggles.
+All actors must be created after calling \code{start_actor_system} so that the executor can keep track of the number of actors that have been allocated but have not yet terminated.
+All message sends are done using the left shift operater, \ie <<, similar to the syntax of \CC's output.
+The signature of the left shift operator is:
+\subsection{Actor Behaviours}\label{s:ActorBehaviours}
+In general, a behaviour for some derived actor and derived message type is defined with following signature:
 \begin{cfa}
 Allocation ?<<?( derived_actor & receiver, derived_msg & msg )
+allocation receive( my_actor & receiver, my_msg & msg )
 \end{cfa}
+An astute eye will notice that this is the same signature as the \code{receive} routine which is no coincidence.
+The \CFA compiler generates a \code{?<<?} routine definition and forward declaration for each \code{receive} routine that has the appropriate signature.
+The generated routine packages the message and actor in an \hyperref[s:envelope]{envelope} and adds it to the executor's queues via an executor routine.
+As part of packaging the envelope, the \code{?<<?} routine sets a function pointer in the envelope to point to the appropriate receive routine for given actor and message types.
+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 may be 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.
+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, it is safe to construct an actor or message with a status other than @Nodelete@, since the executor only examines the allocation action after a behaviour returns.
+\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 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 envelop, 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 envelop is straightforward because it is created at the send and deleted after the receive, \ie there is 1:1 relationship for an envelop and a many to one relationship for a message.
+% 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.
+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.
+\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 include are discussed in Section~\ref{s:executor}.
+\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.
+Hence, programmers must write a matching @?|?@ routine for each @receive@ routine, which is awkward and generates a maintenance problem that must be solved.
+\CFA's current best approach for creating a generic @?|?@ routine requires users to create routines for their actor and message types that access the base type.
+Since these routines are not complex, they can be generated using macros that are used to annotate the user-defined actor and message types.
+This approach is used in \CFA's intrusive list data structure.
+This is not much better than asking users to write the @?|?@ routine themselves in terms of maintenance, since the user needs to remember the boilerplate macro annotation.
+As stated, \CFA does not have named inheritance with RTTI.
+\CFA does have a preliminary form of virtual routines, but it is not mature enough for use in this work.
+Virtuals would provide a mechanism to write a single generic @?|?@ routine taking a base actor and message type, that would dynamically select the @receive@ routine from the actor argument.
+Note, virtuals are not needed for the send; Plan-9 inheritance is sufficient because only the inherited fields are needed during the message send (only upcasting is needed).
+Therefore, a template-like approach was chosen, where the compiler generates a matching @?|?@ routine for each @receive@ routine it finds with the correct actor/message type-signature.
+This approach requires no annotation or additional code to be written by users, thus it resolves the maintenance problem.
+(When the \CFA virtual routines mature, it should be possible to seamlessly transition to it from the template approach.)
+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 base and derived actor and message and actor, along with the receive routine into an \hyperref[s:envelope]{envelope}.
+Finally, the envelop 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{ &receiver, (actor *)&receiver, &msg, (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}
+\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 actor and message is lost and then 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 poses a problem; the correct type of the actor or message is not available to the executor, but it needs to call the right destructor!
+This requires downcasting from the base type to derived type, which requires a virtual system.
+Thus, a rudimentary destructor-only virtual system was added to \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 the @virtual_dtor@ type, the compiler adds code to its destructor to make sure that any destructor calls along this segment of the inheritance tree is called are intercepted, and restart at the appropriate destructor for that object.
+\begin{figure}
+\begin{cfa}
+struct base_type { inline virtual_dtor; };
+struct intermediate_type { inline base_type; };
+struct derived_type { inline intermediate_type; };
+int main() {
+    derived_type d1, d2, d3;
+    intermediate_type & i = d2;
+    base_type & b = d3;
+    // these will call the destructors in the correct order
+    ^d1{}; ^i{}; ^b{};
+}
+\end{cfa}
+\caption{\CFA Virtual Destructor}
+\label{f:VirtDtor}
+\end{figure}
+This virtual destructor system was built for this work, but is general and can be used in 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.
+Figure~\ref{f:ConvenienceMessages} shows three builtin convenience messages and receive routines used to terminate actors, depending on how an actor is allocated: @Delete@, @Destroy@ or @Finished@.
+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.
+\begin{figure}
+\begin{cfa}
+message __base_msg_finished $@$= { .allocation_ : Finished }; // no auto-gen constructors
+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 Convenience Messages}
+\label{f:ConvenienceMessages}
+\end{figure}
 \section{\CFA Executor}\label{s:executor}
+This section will describe the basic architecture of the \CFA executor.
+Any discussion of work stealing is omitted until Section \ref{s:steal}.
+The executor of an actor system is the scheduler that organizes where actors behaviours are run and how messages are sent and delivered.
+In \CFA the executor lays out actors across the sharded message queues in round robin order as they are created.
+The message queues are split across worker threads in equal chunks, or as equal as possible if the number of message queues is not divisible by the number of workers threads.
+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 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, 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}
 …
 \input{diagrams/gulp.tikz}
 \end{center}
 \caption{Diagram of the queue gulping mechanism.}
+\caption{Queue Gulping Mechanism}
 \label{f:gulp}
 \end{figure}
+Each worker thread iterates over its own message queues until it finds one that contains messages.
+At this point the worker thread \textbf{gulps} the queue.
+A \textbf{gulp} is a term for consuming the contents of message queue and transferring them to the local queue of worker thread.
+After the gulp is done atomically, this allows the worker thread to process the queue locally without any need for atomicity until the next gulp.
+Messages can be added to the queue that was gulped in parallel with the processing of the local queue.
+Additionally, prior to each gulp, the worker non-atomically checks if a queue is empty before attempting to gulp it.
+Between this and the gulp, the worker avoids many potentially costly lock acquisitions.
+An example of the queue gulping operation is shown in Figure \ref{f:gulp} where a worker thread gulps queue 0 and begins to process it locally.
+To process its local queue, a worker thread takes each unit of work off the queue and executes it.
+Since all messages to a given actor will be in the same queue, this guarantees atomicity across behaviours of that actor since it can only execute on one thread at a time.
+After running behaviour, the worker thread looks at the returned allocation status and takes the corresponding action.
+Once all actors have marked themselves as being finished the executor initiates shutdown by inserting a sentinel value into the message queues.
+Once a worker thread sees a sentinel it stops running.
+After all workers stop running the actor system shutdown is complete.
+\section{Envelopes}\label{s:envelope}
+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.
+To meet the persistence requirement the envelope is dynamically allocated and cleaned up after it has been delivered and its payload has run.
+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.
+This frequent allocation of envelopes with each message send between actors results in heavy contention on the memory allocator.
+As such, a way to alleviate contention on the memory allocator could result in performance improvement.
+Contention was reduced using a novel data structure that is called a copy queue.
+\subsection{The Copy Queue}\label{s:copyQueue}
+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 than a typical array based queue.
+The copy queue is designed to take advantage of the \hyperref[s:executor]{gulping} pattern.
+As such the amortized rutime cost of each push/pop operation for the copy queue is $O(1)$.
+In contrast, a naive array based queue often has either push or pop cost $O(n)$ and the other cost $O(1)$ since for at least one of the operations all the elements of the queue have to be shifted over.
+Since the worker threads gulp each queue to operate on locally, this creates a usage pattern of the queue where all elements are popped from the copy queue without any interleaved pushes.
+As such, during pop operations there is no need to shift array elements.
+An index is stored in the copy queue data structure which keeps track of which element to pop next allowing pop to be $O(1)$.
+Push operations are amortized $O(1)$ since pushes may cause doubling reallocations of the underlying dynamic sized array.
+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 using a single atomic instruction.
+An example of the queue gulping operation is shown in the right side of Figure \ref{f:gulp}, where a executor threads gulps queue 0 and begins to process it locally.
+This step allows an executor thread to process the local queue without any atomics until the next gulp.
+Other executor threads can continue adding to the ends of 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 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@).
 % C_TODO: maybe make copy_queue diagram
+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 a fixed message throughput workload, once the copy queues grow in size to facilitate the number of messages in flight, there are no longer any dynamic allocations occuring in the actor system.
+One problem that arises with this approach is that this array based approach will often allocate more storage than what is needed.
+Comparitively the individual envelope allocations of a list based queue mean that the actor system will always use the minimum amount of heap space needed and will clean up eagerly.
+Additionally, a workload with variable message throughput could cause copy queues to allocate large amounts of space to accomodate the peaks of the throughput, even if most of that storage is not needed for the rest of the workload's execution.
+To mitigate this a memory reclamation scheme was introduced.
+Initially the memory reclamation naively reclaimed one index of the array per gulp if the array size was above a low fixed threshold.
+This approach had a problem.
+The high memory usage watermark nearly doubled with this change! The issue with this approach can easily be highlighted with an example.
+Say that there is 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 will end up doubling at some point to size 20 to accomodate 19 messages.
+However, after 2 gulps and subsequent reclamations the array would be size 18.
+The next time 19 messages are enqueued, the array size is doubled to 36! To avoid this issue a second check was added to reclamation.
+Each copy queue started tracking the utilization of their array size.
+Reclamation would only occur if less than half of the array was being utilized.
+In doing this the reclamation scheme was able to achieve a lower high watermark and a lower overall memory utilization when compared to the non-reclamation copy queues.
+However, the use of copy queues still incurs a higher memory cost than the list based queueing.
+With the inclusion of a memory reclamation scheme the increase in memory usage is reasonable considering the performance gains and will be discussed further in Section \ref{s:actor_perf}.
+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 workload, the copy queues grow in size to facilitate the average number of messages in flight and there is no further dynamic allocations.
+One downside of this approach 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 amounts of space to accommodate the peaks of the throughput, even if most of that storage is not needed for the rest of the workload's execution.
+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 that attempts to load balance, and increase resource untilization by having idle threads steal work.
 There are many parts that make up a work stealing actor scheduler, but the two that will be highlighted in this work are the stealing mechanism and victim selection.
+% C_TODO enter citation for langs
+Work stealing is a scheduling strategy to provide \Newterm{load balance}.
+The goal is to increase resource utilization by having idle threads steal work from working threads.
+While there are multiple parts in work-stealing scheduler, the two important components are victim selection and the stealing mechanism.
 \subsection{Stealing Mechanism}
+In this discussion of work stealing the worker being stolen from will be referred to as the \textbf{victim} and the worker stealing work will be called the \textbf{thief}.
+The stealing mechanism presented here differs from existing work stealing actor systems due the inverted actor system.
+Other actor systems such as Akka \cite{} and CAF \cite{} have work stealing, but since they use an classic actor system that is actor-centric, stealing work is the act of stealing an actor from a dequeue.
+As an example, in CAF, the sharded actor queue is a set of double ended queues (dequeues).
+Whenever an actor is moved to a ready queue, it is inserted into a worker's dequeue.
+Workers then consume actors from the dequeue and execute their behaviours.
+To steal work, thieves take one or more actors from a victim's dequeue.
+This action creates contention on the dequeue, which can slow down the throughput of the victim.
+The notion of which end of the dequeue is used for stealing, consuming, and inserting is not discussed since it isn't relevant.
+By the pigeon hole principle there are three dequeue operations (push/victim pop/thief pop) that can occur concurrently and only two ends to a dequeue, so work stealing being present in a dequeue based system will always result in a potential increase in contention on the dequeues.
+In work stealing, the stealing worker is called the \Newterm{thief} and the stolen-from worker is called the \Newterm{victim}.
+The stealing mechanism presented here differs from existing work-stealing actor-systems because of the message-centric (inverted) actor-system.
+Other actor systems, such as Akka~\cite{Akka} and CAF~\cite{CAF}, have work stealing, but use an actor-centric system where stealing is dequeuing from a non-empty ready-queue to an empty ready-queue.
+As an example, in CAF, the sharded actor queue is a set of double-ended queues (dequeues).
+When an actor has messages, it is inserted into a worker's dequeue (ready queue).
+Workers then consume actors from the dequeue and execute their behaviours.
+To steal work, thieves take one or more actors from a victim's dequeue.
+By the pigeon hole principle, there are three dequeue operations (push/victim pop/thief pop) that can occur concurrently and only two ends to a dequeue, so work stealing in a dequeue-based system always results in a potential increase in contention on the dequeues.
+This contention can slows down the victim's throughput.
+Note, which end of the dequeue is used for stealing, consuming, and inserting is not discussed since the largest cost is the mutual exclusion and its duration for safely performing the queue operations.
+Work steal now becomes queue stealing, where an entire actor/message queue is stolen, which trivially preserves message ordering in a queue \see{Section~\ref{s:steal}}.
 % C_TODO: maybe insert stealing diagram
+In \CFA, the actor work stealing implementation is unique.
+While other systems are concerned with stealing actors, the \CFA actor system steals queues.
+This is a result of \CFA's use of the inverted actor system.
+The goal of the \CFA actor work stealing mechanism is to have a zero-victim-cost stealing mechanism.
+This does not means that stealing has no cost.
+This goal is to ensure that stealing work does not impact the performance of victim workers.
+This means that thieves can not contend with victims, and that victims should perform no stealing related work unless they become a thief.
+In theory this goal is not achieved, but results will be presented that show the goal is achieved in practice.
+In \CFA's actor system workers own a set of sharded queues which they iterate over and gulp.
+If a worker has iterated over the queues they own twice without finding any work, they try to steal a queue from another worker.
+Stealing a queue is done wait-free with a few atomic instructions that can only create contention with other stealing workers.
+To steal a queue a worker does the following:
+In \CFA, the actor work-stealing implementation is unique because of the message-centric system.
+In this system, 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 FIFO message delivery, actor stealing requires finding and removing 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 the message queue, which also reduces contention, and steal queues to eliminate queue searching.
+Given queue stealing, the goal is to have a zero-victim-cost stealing mechanism, which does not mean stealing has no cost.
+It means work stealing does not affect the performance of the victim worker.
+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 results show the goal is achieved in practice.
+In \CFA's actor system, workers own a set of sharded queues, which they iterate over and gulp.
+If a worker has iterated over its message queues twice without finding any work, it tries to steal a queue from another worker.
+Stealing a queue is done wait-free with a few atomic instructions that can only create contention with other stealing workers, not the victim.
+To steal a queue, a worker does the following:
 \begin{enumerate}[topsep=5pt,itemsep=3pt,parsep=0pt]
 \item
+The thief chooses a victim.
+\item
+The thief starts at a random index in the array of the victim's queues and searches for a candidate queue.
+A candidate queue is any queue that is not empty, is not being stolen by another thief, and is not being processed by the victim.
+These are not strictly enforced rules.
+The candidate is identified non-atomically and as such queues that do not satisfy these rules may be stolen.
+However, steals that do not meet these requirements do not affect correctness so they are allowed and do not constitute failed steals as the queues will still be swapped.
+\item
+Once a candidate queue is chosen, the thief attempts a wait-free swap of the victim's queue and a random on of the thief's queues.
+This swap can fail.
+If the swap is successful the thief swaps the two queues.
+If the swap fails, another thief must have attempted to steal one of the two queues being swapped.
+Failing to steal is good in this case since stealing a queue that was just swapped would likely result in stealing an empty queue.
+The thief chooses a victim, which is trivial because all workers are stored in a shared array.
+\item
+The thief starts at a random index in the array of the victim's queues and searches for a candidate queue.
+A candidate queue is any non-empty queue not being processed by the victim and not being stolen by another thief.
+These rules are not strictly enforced.
+A candidate is identified non-atomically, and as such, queues that do not satisfy these rules may be stolen.
+However, steals not meeting the rules do not affect correctness and do not constitute failed steals as the queue is always swapped.
+\item
+Once a candidate queue is chosen, the thief attempts a wait-free swap of a victim's queue to a random empty thief queue.
+If the swap successes, the steal is completed.
+If the swap fails, the victim may have been gulping that message queue or another thief must have attempted to steal the victim's queue.
+In either case, that message queue is highly likely to be empty.
+\item
+Once a thief fails or succeeds in stealing a queue, it iterates over its messages queues again because new messages may have arrived during stealing.
+Stealing is only repeated after two consecutive iterations over its owned queues without finding work.
 \end{enumerate}
+Once a thief fails or succeeds in stealing a queue, it goes back to its own set of queues and iterates over them again.
+It will only try to steal again once it has completed two consecutive iterations over its owned queues without finding any work.
+The key to the stealing mechnism is that the queues can still be operated on while they are being swapped.
+This elimates any contention between thieves and victims.
+The first key to this is that actors and workers maintain two distinct arrays of references to queues.
+Actors will always receive messages via the same queues.
+Workers, on the other hand will swap the pointers to queues in their shared array and operate on queues in the range of that array that they own.
+Swapping queues is a matter of atomically swapping two pointers in the worker array.
+The key to the stealing mechanism is that the queues can still be operated on while they are being swapped.
+This functionality eliminates any contention among thieves and victims.
+The first key to this is that actors and workers maintain two distinct arrays of references to queues.
+Actors will always receive messages via the same queues.
+Workers, on the other hand will swap the pointers to queues in their shared array and operate on queues in the range of that array that they own.
+Swapping queues is a matter of atomically swapping two pointers in the worker array.
 As such pushes to the queues can happen concurrently during the swap since pushes happen via the actor queue references.
 Gulping can also occur during queue swapping, but the implementation requires more nuance than the pushes.
 When a worker is not stealing it iterates across its own range of queues and gulps them one by one.
 When a worker operates on a queue it first copies the current pointer from the worker array of references to a local variable.
 It then uses that local variable for all queue operations until it moves to the next index of its range of the queue array.
 This ensures that any swaps do not interrupt gulping operations, however this introduces a correctness issue.
 If any behaviours from a queue are run by two workers at a time it violates both mutual exclusion and the actor ordering guarantees.
 As such this must be avoided.
 To avoid this each queue has a \code{being_processed} flag that is atomically set to \code{true} when a queue is gulped.
 The flag indicates that a queue is being processed locally and is set back to \code{false} once the local processing is finished.
 If a worker attempts to gulp a queue and finds that the \code{being_processed} flag is \code{true}, it does not gulp the queue and moves on to the next queue in its range.
 This is a source of contention between victims and thieves since a thief may steal a queue and set \code{being_processed} to \code{true} between a victim saving a pointer to a queue and gulping it.
 However, the window for this race is very small, making this contention rare.
 This is why the claim is made that this mechanism is zero-victim-cost in practice but not in theory.
 By collecting statistics on failed gulps due to the \code{being_processed} flag, it is found that this contention occurs ~0.05\% of the time when a gulp occurs.
+Gulping can also occur during queue swapping, but the implementation requires more nuance than the pushes.
+When a worker is not stealing it iterates across its own range of queues and gulps them one by one.
+When a worker operates on a queue it first copies the current pointer from the worker array of references to a local variable.
+It then uses that local variable for all queue operations until it moves to the next index of its range of the queue array.
+This ensures that any swaps do not interrupt gulping operations, however this introduces a correctness issue.
+If any behaviours from a queue are run by two workers at a time it violates both mutual exclusion and the actor ordering guarantees.
+As such this must be avoided.
+To avoid this each queue has a @being_processed@ flag that is atomically set to @true@ when a queue is gulped.
+The flag indicates that a queue is being processed locally and is set back to @false@ once the local processing is finished.
+If a worker attempts to gulp a queue and finds that the @being_processed@ flag is @true@, it does not gulp the queue and moves on to the next queue in its range.
+This is a source of contention between victims and thieves since a thief may steal a queue and set @being_processed@ to @true@ between a victim saving a pointer to a queue and gulping it.
+However, the window for this race is very small, making this contention rare.
+This is why the claim is made that this mechanism is zero-victim-cost in practice but not in theory.
+By collecting statistics on failed gulps due to the @being_processed@ flag, it is found that this contention occurs ~0.05\% of the time when a gulp occurs.
 Hence, the claim is made that this stealing mechanism has zero-victim-cost in practice.
 \subsection{Queue Swap Correctness}
 Given the wait-free swap used is novel, it is important to show that it is correct.
 Firstly, it is clear to show that the swap is wait-free since all workers will fail or succeed in swapping the queues in a finite number of steps since there are no locks or looping.
 There is no retry mechanism in the case of a failed swap, since a failed swap either means the work was already stolen, or that work was stolen from the thief.
 In both cases it is apropos for a thief to given up on stealing.
 \CFA-style pseudocode for the queue swap is presented below.
 The swap uses compare-and-swap (\code{CAS}) which is just pseudocode for C's \code{__atomic_compare_exchange_n}.
 A pseudocode implementation of \code{CAS} is also shown below.
 The correctness of the wait-free swap will now be discussed in detail.
+Given the wait-free swap used is novel, it is important to show that it is correct.
+Firstly, it is clear to show that the swap is wait-free since all workers will fail or succeed in swapping the queues in a finite number of steps since there are no locks or looping.
+There is no retry mechanism in the case of a failed swap, since a failed swap either means the work was already stolen, or that work was stolen from the thief.
+In both cases it is apropos for a thief to given up on stealing.
+\CFA-style pseudocode for the queue swap is presented below.
+The swap uses compare-and-swap (@CAS@) which is just pseudocode for C's @__atomic_compare_exchange_n@.
+A pseudocode implementation of @CAS@ is also shown below.
+The correctness of the wait-free swap will now be discussed in detail.
 To first verify sequential correctness, consider the equivalent sequential swap below:
 …
 \end{cfa}
 Step 1 is missing in the sequential example since in only matter in the concurrent context presented later.
 By looking at the sequential swap it is easy to see that it is correct.
+Step 1 is missing in the sequential example since in only matter in the concurrent context presented later.
+By looking at the sequential swap it is easy to see that it is correct.
 Temporary copies of each pointer being swapped are stored, and then the original values of each pointer are set using the copy of the other pointer.
 …
         // Step 1:
         // If either queue is 0p then they are in the process of being stolen
         // 0p is CForAll's equivalent of C++'s nullptr
+        // 0p is Cforall's equivalent of C++'s nullptr
         if ( vic_queue == 0p ) return false;
 …
         if ( !CAS( &request_queues[my_idx], &my_queue, 0p ) )
                 return false;
         // Step 3:
         // Try to set victim queue ptr to be thief's queue ptr.
 …
 Step 0 is the same as the sequential example, and the thief stores local copies of the two pointers to be swapped.
 \item
 Step 1 verifies that the stored copy of the victim queue pointer, \code{vic_queue}, is valid.
 If \code{vic_queue} is equal to \code{0p}, then the victim queue is part of another swap so the operation fails.
 No state has changed at this point so no fixups are needed.
 Note, \code{my_queue} can never be equal to \code{0p} at this point since thieves only set their own queues pointers to \code{0p} when stealing.
 At no other point will a queue pointer be set to \code{0p}.
 Since each worker owns a disjoint range of the queue array, it is impossible for \code{my_queue} to be \code{0p}.
 \item
 Step 2 attempts to set the thief's queue pointer to \code{0p} via \code{CAS}.
 The \code{CAS} will only fail if the thief's queue pointer is no longer equal to \code{my_queue}, which implies that this thief has become a victim and its queue has been stolen.
 At this point the thief-turned-victim will fail and since it has not changed any state it just fails and returns false.
 If the \code{CAS} succeeds then the thief's queue pointer will now be \code{0p}.
 Nulling the pointer is safe since only thieves look at other worker's queue ranges, and whenever thieves need to dereference a queue pointer they check for \code{0p}.
 \item
 Step 3 attempts to set the victim's queue pointer to be \code{my_queue} via \code{CAS}.
 If the \code{CAS} succeeds then the victim's queue pointer has been set and swap can no longer fail.
 If the \code{CAS} fails then the thief's queue pointer must be restored to its previous value before returning.
 \item
 Step 4 sets the thief's queue pointer to be \code{vic_queue} completing the swap.
+Step 1 verifies that the stored copy of the victim queue pointer, @vic_queue@, is valid.
+If @vic_queue@ is equal to @0p@, then the victim queue is part of another swap so the operation fails.
+No state has changed at this point so no fixups are needed.
+Note, @my_queue@ can never be equal to @0p@ at this point since thieves only set their own queues pointers to @0p@ when stealing.
+At no other point will a queue pointer be set to @0p@.
+Since each worker owns a disjoint range of the queue array, it is impossible for @my_queue@ to be @0p@.
+\item
+Step 2 attempts to set the thief's queue pointer to @0p@ via @CAS@.
+The @CAS@ will only fail if the thief's queue pointer is no longer equal to @my_queue@, which implies that this thief has become a victim and its queue has been stolen.
+At this point the thief-turned-victim will fail and since it has not changed any state it just fails and returns false.
+If the @CAS@ succeeds then the thief's queue pointer will now be @0p@.
+Nulling the pointer is safe since only thieves look at other worker's queue ranges, and whenever thieves need to dereference a queue pointer they check for @0p@.
+\item
+Step 3 attempts to set the victim's queue pointer to be @my_queue@ via @CAS@.
+If the @CAS@ succeeds then the victim's queue pointer has been set and swap can no longer fail.
+If the @CAS@ fails then the thief's queue pointer must be restored to its previous value before returning.
+\item
+Step 4 sets the thief's queue pointer to be @vic_queue@ completing the swap.
 \end{enumerate}
 …
 \end{theorem}
 Correctness of the swap is shown through the existence of an invariant.
 The invariant is that when a queue pointer is set to \code{0p} by a thief, then the next write to the pointer can only be performed by the same thief.
 To show that this invariant holds, it is shown that it is true at each step of the swap.
 Step 0 and 1 do not write and as such they cannot invalidate the invariant of any other thieves.
 In step 2 a thief attempts to write \code{0p} to one of their queue pointers.
 This queue pointer cannot be \code{0p}.
 As stated above, \code{my_queue} is never equal to \code{0p} since thieves will only write \code{0p} to queue pointers from their own queue range and all worker's queue ranges are disjoint.
 As such step 2 upholds the invariant since in a failure case no write occurs, and in the success case, the value of the queue pointer is guaranteed to not be 0p.
 In step 3 the thief attempts to write \code{my_queue} to the victim's queue pointer.
 If the current value of the victim's queue pointer is \code{0p}, then the CAS will fail since \code{vic_queue} cannot be equal to \code{0p} because of the check in step 1.
 Therefore in the success case where the \code{CAS} succeeds, the value of the victim's queue pointer must not be \code{0p}.
 As such, the write will never overwrite a value of \code{0p}, hence the invariant is held in the \code{CAS} of step 3.
 The write back to the thief's queue pointer that happens in the failure case of step three and in step 4 hold the invariant since they are the subsequent write to a \code{0p} queue pointer and they are being set by the same thief that set the pointer to \code{0p}.
 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 \code{0p} in step 2, the invariant guarantees that pointer will not change.
 As such, in the success case step 3 it is known that the value of the victim's queue pointer that was overwritten must be \code{vic_queue} due to the use of \code{CAS}.
 Given that pointers all have unique memory locations, this first write of the successful swap is correct since it can only occur when the pointer has not changed.
 By the invariant the write back in the successful case is correct since no other worker can write to the \code{0p} pointer.
 In the failed case the outcome is correct in steps 1 and 2 since no writes have occured so the program state is unchanged.
 In the failed case of step 3 the program state is safely restored to its state it had prior to the \code{0p} write in step 2, thanks to the invariant that makes the write back to the \code{0p} pointer safe.
+Correctness of the swap is shown through the existence of an invariant.
+The invariant is that when a queue pointer is set to @0p@ by a thief, then the next write to the pointer can only be performed by the same thief.
+To show that this invariant holds, it is shown that it is true at each step of the swap.
+Step 0 and 1 do not write and as such they cannot invalidate the invariant of any other thieves.
+In step 2 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 will only write @0p@ to queue pointers from their own queue range and all worker's queue ranges are disjoint.
+As such step 2 upholds the invariant since in a failure case no write occurs, and in the success case, the value of the queue pointer is guaranteed to not be 0p.
+In step 3 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 will fail since @vic_queue@ cannot be equal to @0p@ because of the check in step 1.
+Therefore in the success case where the @CAS@ succeeds, the value of the victim's queue pointer must not be @0p@.
+As such, the write will never overwrite a value of @0p@, hence the invariant is held in the @CAS@ of step 3.
+The write back to the thief's queue pointer that happens in the failure case of step three and in step 4 hold the invariant since they are the subsequent write to a @0p@ queue pointer and they are being set by the same thief that set the pointer to @0p@.
+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 2, the invariant guarantees that pointer will not change.
+As such, in the success case step 3 it is known that the value of the victim's queue pointer that was overwritten must be @vic_queue@ due to the use of @CAS@.
+Given that pointers all have unique memory locations, this first write of the successful swap is correct since it can only occur when the pointer has not changed.
+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 the outcome is correct in steps 1 and 2 since no writes have occurred so the program state is unchanged.
+In the failed case of step 3 the program state is safely restored to its state it had prior to the @0p@ write in step 2, thanks to the invariant that makes the write back to the @0p@ pointer safe.
 \subsection{Stealing Guarantees}
+% C_TODO insert graphs for each proof
+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.
+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{theorem}
 Given $M$ thieves queues all attempting to swap with one victim queue, and no other swaps occuring that involve these queues, at least one swap is guaranteed to succeed.
+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 will not attempt to steal from themselves.
 As such, the victim here is not also a thief.
 Stepping through the code in \ref{c:swap}, for all thieves steps 0-1 succeed since the victim is not stealing and will have no queue pointers set to be \code{0p}.
 Similarly for all thieves step 2 will succeed since no one is stealing from any of the thieves.
 In step 3 the first thief to \code{CAS} will win the race and successfully swap the queue pointer.
 Since it is the first one to \code{CAS} and \code{CAS} is atomic, there is no way for the \code{CAS} to fail since no other thief could have written to the victim's queue pointer and the victim did not write to the pointer since they aren't stealing.
+First it is important to state that a thief will not attempt to steal from themselves.
+As such, the victim here is not also a thief.
+Stepping through the code in \ref{c:swap}, for all thieves steps 0-1 succeed since the victim is not stealing and will have no queue pointers set to be @0p@.
+Similarly for all thieves step 2 will succeed since no one is stealing from any of the thieves.
+In step 3 the first thief to @CAS@ will win the race and successfully swap 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{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 occuring that involve these queues, at least one swap is guaranteed to succeed.
+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 1, step 2 or step 3.
 For a given thief $b$ to fail at step 1, thief $b + 1$ must have succeded at step 2 before $b$ executes step 0.
 Hence, not all thieves can fail at step 1.
 Furthermore if a thief $b$ fails at step 1 it logically splits the chain into two subchains $0 <- b$ and $b + 1 <- M - 1$, where $b$ has become solely a victim since its swap has failed and it did not modify any state.
 There must exist at least one chain containing two or more queues after since it is impossible for a split to occur both before and after a thief, since that requires failing at step 1 and succeeding at step 2.
+This is a proof by contradiction.
+Assume no swaps occur.
+Then all thieves must have failed at step 1, step 2 or step 3.
+For a given thief $b$ to fail at step 1, thief $b + 1$ must have succeeded at step 2 before $b$ executes step 0.
+Hence, not all thieves can fail at step 1.
+Furthermore if a thief $b$ fails at step 1 it logically splits the chain into two subchains $0 <- b$ and $b + 1 <- M - 1$, where $b$ has become solely a victim since its swap has failed and it did not modify any state.
+There must exist at least one chain containing two or more queues after since it is impossible for a split to occur both before and after a thief, since that requires failing at step 1 and succeeding at step 2.
 Hence, without loss of generality, whether thieves succeed or fail at step 1, this proof can proceed inductively.
 For a given thief $i$ to fail at step 2, it means that another thief $j$ had to have written to $i$'s queue pointer between $i$'s step 0 and step 2.
 The only way for $j$ to write to $i$'s queue pointer would be if $j$ was stealing from $i$ and had successfully finished step 3.
 If $j$ finished step 3 then the at least one swap was successful.
 Therefore all thieves did not fail at step 2.
 Hence all thieves must successfully complete step 2 and fail at step 3.
 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$ will always succeed in step 3 if all thieves succeed in step 2.
+For a given thief $i$ to fail at step 2, it means that another thief $j$ had to have written to $i$'s queue pointer between $i$'s step 0 and step 2.
+The only way for $j$ to write to $i$'s queue pointer would be if $j$ was stealing from $i$ and had successfully finished step 3.
+If $j$ finished step 3 then the at least one swap was successful.
+Therefore all thieves did not fail at step 2.
+Hence all thieves must successfully complete step 2 and fail at step 3.
+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$ will always succeed in step 3 if all thieves succeed in step 2.
 Thus, by contradiction with the earlier assumption that no swaps occur, at least one swap must succeed.
 …
 \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}}
+\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.}
 …
 \begin{theorem}
 Given a set of $M > 1$ swaps occuring that form a single directed connected graph.
 At least one swap is guaranteed to suceed if and only if the graph does not contain a cycle.
+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 acylic swap graphs discussed in this theorem are presented in Figures~\ref{f:cyclic_swap} and \ref{f:acyclic_swap}.
+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 1, 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 2 for no swaps to occur, since for step 2 to fail, a different thief has to successfully complete step 3, which would imply a successful swap.
 Hence, the only way forward is to assume all thieves successfully complete step 2.
 Hence for there to be no swaps all thieves must fail step 3.
 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 2, similar to \ref{t:one_vic} the first one of the $K$ thieves to attempt step 3 is guaranteed to succeed.
+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 1, 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 2 for no swaps to occur, since for step 2 to fail, a different thief has to successfully complete step 3, which would imply a successful swap.
+Hence, the only way forward is to assume all thieves successfully complete step 2.
+Hence for there to be no swaps all thieves must fail step 3.
+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 2, similar to \ref{t:one_vic} the first one of the $K$ thieves to attempt step 3 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 aribtrary 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 accomodate 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 0-1, and then they all complete step 2.
 At this point all thieves are attempting to swap with a queue pointer whose value has changed to \code{0p}.
 If all thieves attempt the \code{CAS} before any write backs, then they will 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 suceed if and only if the graph does not contain a cycle.
+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 0-1, and then they all complete step 2.
+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 will 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.
 % 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 have some heuristic to determine which victim to choose from.
 Choosing this algorithm is difficult and can have implications on performance.
 There is no one selection heuristic that is known to be the best on all workloads.
 Recent work focuses on locality aware scheduling in actor systems\cite{barghi18}\cite{wolke17}.
 However, while locality aware scheduling provides good performance on some workloads, something as simple as randomized selection performs better on other workloads\cite{barghi18}.
 Since locality aware scheduling has been explored recently, this work introduces a heuristic called \textbf{longest victim} and compares it to randomized work stealing.
 The longest victim heuristic maintains a timestamp per worker thread that is updated every time a worker attempts to steal work.
 Thieves then attempt to steal from the thread with the oldest timestamp.
 This means that if two thieves look to steal at the same time, they likely will attempt to steal from the same victim.
 This does increase the chance at contention between thieves, however given that workers have multiple queues under them, often in the tens or hundreds of queues per worker it is rare for two queues to attempt so steal the same queue.
 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}.
 Additonally, 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 would require all workers to attempt to steal in a short timeframe.
 This is the only way that more than one thief could choose another thief as a victim, since timestamps are only updated upon attempts to steal.
+In any work stealing algorithm thieves have some heuristic to determine which victim to choose from.
+Choosing this algorithm is difficult and can have implications on performance.
+There is no one selection heuristic that is known to be the best on all workloads.
+Recent work focuses on locality aware scheduling in actor systems\cite{barghi18}\cite{wolke17}.
+However, while locality aware scheduling provides good performance on some workloads, something as simple as randomized selection performs better on other workloads\cite{barghi18}.
+Since locality aware scheduling has been explored recently, this work introduces a heuristic called \textbf{longest victim} and compares it to randomized work stealing.
+The longest victim heuristic maintains a timestamp per executor threads that is updated every time a worker attempts to steal work.
+Thieves then attempt to steal from the thread with the oldest timestamp.
+This means that if two thieves look to steal at the same time, they likely will attempt to steal from the same victim.
+This does increase the chance at contention between thieves, however given that workers have multiple queues under them, often in the tens or hundreds of queues per worker it is rare for two queues to attempt so steal the same queue.
+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 would require all workers to attempt to steal in a short timeframe.
+This is the only way that more than one thief could choose another thief as a victim, since timestamps are only updated upon attempts to steal.
 In this case, the probability of lack of any successful swaps is a non issue, since it is likely that these steals were not important if all workers are trying to steal.
 \section{Safety and Productivity}
 \CFA's actor system comes with a suite of safety and productivity features.
 Most of these features are present in \CFA's debug mode, but are removed when code is compiled in nodebug mode.
+\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 present in \CFA's debug mode, but are removed when code is compiled in nodebug mode.
 The suit of features include the following.
 \begin{itemize}
 \item Static-typed message sends.
+\item Static-typed message sends.
 If an actor does not support receiving a given message type, the actor program is rejected at compile time, allowing unsupported messages to never be sent to actors.
 \item Detection of message sends to Finished/Destroyed/Deleted actors.
 All actors have a ticket that assigns them to a respective queue.
+\item Detection of message sends to Finished/Destroyed/Deleted actors.
+All actors have a ticket that assigns them to a respective queue.
 The maximum integer value of the ticket is reserved to indicate that an actor is dead, and subsequent message sends result in an error.
 \item Actors made before the executor can result in undefined behaviour since an executor needs to be created beforehand so it can give out the tickets to actors.
+\item Actors made before the executor can result in undefined behaviour since an executor needs to be created beforehand so it can give out the tickets to actors.
 As such, this is detected and an error is printed.
 \item When an executor is created, the queues are handed out to worker threads in round robin order.
 If there are fewer queues than worker threads, then some workers will spin and never do any work.
 There is no reasonable use case for this behaviour so an error is printed if the number of queues is fewer than the number of worker threads.
 \item A warning is printed when messages are deallocated without being sent.
 Since the \code{Finished} allocation status is unused for messages, it is used internally to detect if a message has been sent.
+\item When an executor is created, the queues are handed out to executor threads in round robin order.
+If there are fewer queues than executor threads, then some workers will spin and never do any work.
+There is no reasonable use case for this behaviour so an error is printed if the number of queues is fewer than the number of executor threads.
+\item A warning is printed when messages are deallocated without being 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 to a user that they are touching freed memory later, or it could point out extra allocations that could be removed.
+\item Detection of messages sent but not received
+As discussed in Section~\ref{s:executor}, once all actors have terminated shutdown is communicated to executor threads via a status flag. Upon termination the executor threads check their queues to see if any contain messages. If they do, an error is reported. Messages being sent but not received means that their allocation action did not occur and their payload was not delivered. Missing the allocation action can lead to memory leaks and missed payloads can cause unpredictable behaviour. Detecting this can indicate a race or logic error in the user's code.
 \end{itemize}
 In addition to these features, \CFA's actor system comes with a suite of statistics that can be toggled on and off.
 These statistics have minimal impact on the actor system's performance since they are counted on a per worker thread basis.
 During shutdown of the actor system they are aggregated, ensuring that the only atomic instructions used by the statistics counting happen at shutdown.
+In addition to these features, \CFA's actor system comes with a suite of statistics that can be toggled on and off.
+These statistics have minimal impact on the actor system's performance since they are counted on a per executor threads basis.
+During shutdown of the actor system they are aggregated, ensuring that the only atomic instructions used by the statistics counting happen at shutdown.
 The statistics measured are as follows.
 \begin{description}
 \item[\LstBasicStyle{\textbf{Actors Created}}]
 Actors created.
+Actors created.
 Includes both actors made by the main and ones made by other actors.
 \item[\LstBasicStyle{\textbf{Messages Sent}}]
 Messages sent and received.
 Includes termination messages send to the worker threads.
+Messages sent and received.
+Includes termination messages send to the executor threads.
 \item[\LstBasicStyle{\textbf{Gulps}}]
 Gulps that occured across the worker threads.
+Gulps that occurred across the executor threads.
 \item[\LstBasicStyle{\textbf{Average Gulp Size}}]
 Average number of messages in a gulped queue.
 \item[\LstBasicStyle{\textbf{Missed gulps}}]
 Occurences where a worker missed a gulp due to the concurrent queue processing by another worker.
+Occurrences where a worker missed a gulp due to the concurrent queue processing by another worker.
 \item[\LstBasicStyle{\textbf{Steal attempts}}]
 Worker threads attempts to steal work.
+Worker threads attempts to steal work.
 \item[\LstBasicStyle{\textbf{Steal failures (no candidates)}}]
 …
 \end{description}
 These statistics enable a user of \CFA's actor system to make informed choices about how to configure their executor, or how to structure their actor program.
 For example, if there is a lot of messages being stolen relative to the number of messages sent, it could indicate to a user that their workload is heavily imbalanced across worker threads.
+These statistics enable a user of \CFA's actor system to make informed choices about how to configure their executor, or how to structure their actor program.
+For example, if there is a lot of messages being stolen relative to the number of messages sent, it could indicate to a user that their workload is heavily imbalanced across executor threads.
 In another example, if the average gulp size is very high, it could indicate that the executor could use more queue sharding.
 % C_TODO cite poison pill messages and add languages
 Another productivity feature that is included is a group of poison-pill messages.
 Poison-pill messages are common across actor systems, including Akka and ProtoActor \cite{}.
 Poison-pill messages inform an actor to terminate.
 In \CFA, due to the allocation of actors and lack of garbage collection, there needs to be a suite of poison-pills.
 The messages that \CFA provides are \code{DeleteMsg}, \code{DestroyMsg}, and \code{FinishedMsg}.
 These messages are supported on all actor types via inheritance and when sent to an actor, the actor takes the corresponding allocation action after receiving the message.
 Note that any pending messages to the actor will still be sent.
+Another productivity feature that is included is a group of poison-pill messages.
+Poison-pill messages are common across actor systems, including Akka and ProtoActor \cite{}.
+Poison-pill messages inform an actor to terminate.
+In \CFA, due to the allocation of actors and lack of garbage collection, there needs to be a suite of poison-pills.
+The messages that \CFA provides are @DeleteMsg@, @DestroyMsg@, and @FinishedMsg@.
+These messages are supported on all actor types via inheritance and when sent to an actor, the actor takes the corresponding allocation action after receiving the message.
+Note that any pending messages to the actor will still be sent.
 It is still the user's responsibility to ensure that an actor does not receive any messages after termination.
 …
 \CAP{I will update the figures to have the larger font size and different line markers once we start editing this chapter.}
 The performance of \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 \ref{}, with a few additions.
+Most of the benchmarks are the same as those presented in \ref{}, with a few additions.
 % C_TODO cite actor paper
 At the time of this work the versions of the actor systems are as follows.
 \CFA 1.0, \uC 7.0.0, Akka Typed 2.7.0, CAF 0.18.6, and ProtoActor-Go v0.0.0-20220528090104-f567b547ea07.
+At the time of this work the versions of the actor systems are as follows.
+\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 in.
 The experiments are run on
 …
 \end{list}
 The benchmarks are run on up to 48 cores.
 On the Intel, when going beyond 24 cores there is the choice to either hop sockets or to use hyperthreads.
 Either choice will cause a blip in performance trends, which can be seen in the following performance figures.
+The benchmarks are run on up to 48 cores.
+On the Intel, when going beyond 24 cores there is the choice to either hop sockets or to use hyperthreads.
+Either choice will cause a blip in performance trends, which can be seen in the following performance figures.
 On the Intel the choice was made to hyperthread instead of hopping sockets for experiments with more than 24 cores.
 All benchmarks presented are run 5 times and the median is taken.
 Error bars showing the 95\% confidence intervals are drawn on each point on the graphs.
 If the confidence bars are small enough, they may be obscured by the point.
 In this section \uC will be compared to \CFA frequently, as the actor system in \CFA was heavily based off \uC's actor system.
 As such the peformance differences that arise are largely due to the contributions of this work.
+All benchmarks presented are run 5 times and the median is taken.
+Error bars showing the 95\% confidence intervals are drawn on each point on the graphs.
+If the confidence bars are small enough, they may be obscured by the point.
+In this section \uC will be compared to \CFA frequently, as the actor system in \CFA was heavily based off \uC's actor system.
+As such the performance differences that arise are largely due to the contributions of this work.
 \begin{table}[t]
 …
 \begin{tabular}{*{5}{r|}r}
         & \multicolumn{1}{c|}{\CFA (100M)} & \multicolumn{1}{c|}{CAF (10M)} & \multicolumn{1}{c|}{Akka (100M)} & \multicolumn{1}{c|}{\uC (100M)} & \multicolumn{1}{c@{}}{ProtoActor (100M)} \\
         \hline
+        \hline
         AMD             & \input{data/pykeSendStatic} \\
         \hline
+        \hline
         Intel   & \input{data/nasusSendStatic}
 \end{tabular}
 …
 \begin{tabular}{*{5}{r|}r}
         & \multicolumn{1}{c|}{\CFA (20M)} & \multicolumn{1}{c|}{CAF (2M)} & \multicolumn{1}{c|}{Akka (2M)} & \multicolumn{1}{c|}{\uC (20M)} & \multicolumn{1}{c@{}}{ProtoActor (2M)} \\
         \hline
+        \hline
         AMD             & \input{data/pykeSendDynamic} \\
         \hline
+        \hline
         Intel   & \input{data/nasusSendDynamic}
 \end{tabular}
 …
 \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 following two microbenchmarks evaluate the average latency for a static actor/message send and a dynamic actor/message send.
 Static and dynamic refer to the allocation of the message and actor.
 In the static send benchmark a message and actor are allocated once and then the message is sent to the same actor repeatedly until it has been sent 100 million (100M) times.
 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.
+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 following two microbenchmarks evaluate the average latency for a static actor/message send and a dynamic actor/message send.
+Static and dynamic refer to the allocation of the message and actor.
+In the static send benchmark a message and actor are allocated once and then the message is sent to the same actor repeatedly until it has been sent 100 million (100M) times.
+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 performed, with the change that with each send a new actor and message is allocated.
 This evaluates the cost of message sends in the other common actor pattern where actors and message are created on the fly as the actor program tackles a workload of variable or unknown size.
+In the dynamic send benchmark the same experiment is performed, with the change that with each send a new actor and message is allocated.
+This evaluates the cost of message sends in the other common actor pattern where actors and message are created on the fly as the actor program tackles a workload of variable or unknown size.
 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.
 The results from the static/dynamic send benchmarks are shown in Figures~\ref{t:StaticActorMessagePerformance} and \ref{t:DynamicActorMessagePerformance} respectively.
 \CFA leads the charts in both benchmarks, largely due to the copy queue removing the majority of the envelope allocations.
 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, as expected due to the extra allocations.
 However, Akka and ProtoActor, slow down by a more significant margin than the \uC and \CFA.
+The results from the static/dynamic send benchmarks are shown in Figures~\ref{t:StaticActorMessagePerformance} and \ref{t:DynamicActorMessagePerformance} respectively.
+\CFA leads the charts in both benchmarks, largely due to the copy queue removing the majority of the envelope allocations.
+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, as expected due to the extra allocations.
+However, Akka and ProtoActor, slow down by a more significant margin than the \uC and \CFA.
 This is likely a result of Akka and ProtoActor's garbage collection, which can suffer from hits in performance for allocation heavy workloads, whereas \uC and \CFA have explicit allocation/deallocation.
 \subsection{Work Stealing}
 \CFA's actor system has a work stealing mechanism which uses the longest victim heuristic, introduced in Section~ref{s:victimSelect}.
+\CFA's actor system has a work stealing mechanism which uses the longest victim heuristic, introduced in Section~ref{s:victimSelect}.
 In this performance section, \CFA with the longest victim heuristic is compared with other actor systems on the benchmark suite, and is separately compared with vanilla non-stealing \CFA and \CFA with randomized work stealing.
 …
 \end{figure}
 There are two benchmarks in which \CFA's work stealing is solely evaluated.
 The main goal of introducing work stealing to \CFA's actor system is to eliminate the pathological unbalanced cases that can present themselves in a system without some form of load balancing.
 The following two microbenchmarks construct two such pathological cases, and compare the work stealing variations of \CFA.
 The balance benchmarks adversarily takes advantage of the round robin assignment of actors to load all actors that will do work on specific cores and create 'dummy' actors that terminate after a single message send on all other cores.
 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, one expects the ideal speedup of work stealing in the balance-one case to be $N / N - 1$ where $N$ is the number of threads.
 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.
+There are two benchmarks in which \CFA's work stealing is solely evaluated.
+The main goal of introducing work stealing to \CFA's actor system is to eliminate the pathological unbalanced cases that can present themselves in a system without some form of load balancing.
+The following two microbenchmarks construct two such pathological cases, and compare the work stealing variations of \CFA.
+The balance benchmarks adversarially takes advantage of the round robin assignment of actors to load all actors that will do work on specific cores and create 'dummy' actors that terminate after a single message send on all other cores.
+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, one expects the ideal speedup of work stealing in the balance-one case to be $N / N - 1$ where $N$ is the number of threads.
+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.
 On both balance microbenchmarks slightly less than ideal speedup compared to the non stealing variation is achieved by both the random and longest victim stealing heuristics.
 On the balance-multi benchmark \ref{f:BalanceMultiAMD},\ref{f:BalanceMultiIntel} the random heuristic outperforms the longest victim.
 This is likely a result of the longest victim heuristic having a higher stealing cost as it needs to maintain timestamps and look at all timestamps before stealing.
+On both balance microbenchmarks slightly less than ideal speedup compared to the non stealing variation is achieved by both the random and longest victim stealing heuristics.
+On the balance-multi benchmark \ref{f:BalanceMultiAMD},\ref{f:BalanceMultiIntel} the random heuristic outperforms the longest victim.
+This is likely a result of the longest victim heuristic having a higher stealing cost as it needs to maintain timestamps and look at all timestamps before stealing.
 Additionally, a performance cost can be observed when hyperthreading kicks in in Figure~\ref{f:BalanceMultiIntel}.
 In the balance-one benchmark on AMD \ref{f:BalanceOneAMD}, the performance bottoms out at 32 cores onwards likely due to the amount of work becoming less than the cost to steal it and move it across cores and cache.
 On Intel \ref{f:BalanceOneIntel}, above 32 cores the performance gets worse for all variants due to hyperthreading.
+In the balance-one benchmark on AMD \ref{f:BalanceOneAMD}, the performance bottoms out at 32 cores onwards likely due to the amount of work becoming less than the cost to steal it and move it across cores and cache.
+On Intel \ref{f:BalanceOneIntel}, above 32 cores the performance gets worse for all variants due to hyperthreading.
 Note that the non stealing variation of balance-one will slow down marginally as the cores increase due to having to create more dummy actors on the inactive cores during startup.
 \subsection{Executor}\label{s:executorPerf}
 The microbenchmarks 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 worker threads to service the needs of a workload.
 In the executor benchmark, 40'000 actors are created and assigned a group.
 Each group of actors is a group of 100 actors who send and receive 100 messages from all other actors in their group.
 Each time an actor completes all their sends and receives, they are done a round.
 After all groups have completed 400 rounds the system terminates.
 This microbenchmark is designed to flood the executor with a large number of messages flowing between actors.
+The microbenchmarks 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 a workload.
+In the executor benchmark, 40'000 actors are created and assigned a group.
+Each group of actors is a group of 100 actors who send and receive 100 messages from all other actors in their group.
+Each time an actor completes all their sends and receives, they are done a round.
+After all groups have completed 400 rounds the system terminates.
+This microbenchmark is designed to flood the executor with a large number of messages flowing between 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.
 …
 \end{figure}
 The results of the executor benchmark in Figures~\ref{f:ExecutorIntel} and \ref{f:ExecutorAMD} show \CFA with the lowest runtime relative to its peers.
 The difference in runtime between \uC and \CFA is largely due to the usage of 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, it is able to get rid of expensive dynamic casts that occur in \uC to disciminate messages by type.
 Note that dynamic casts are ususally not very expensive, but relative to the high performance of the rest of the implementation of the \uC actor system, the cost is significant.
+The results of the executor benchmark in Figures~\ref{f:ExecutorIntel} and \ref{f:ExecutorAMD} show \CFA with the lowest runtime relative to its peers.
+The difference in runtime between \uC and \CFA is largely due to the usage of 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, it is able to get rid of expensive dynamic casts that occur in \uC to discriminate messages by type.
+Note that dynamic casts are usually not very expensive, but relative to the high performance of the rest of the implementation of the \uC actor system, the cost is significant.
 \begin{figure}
 …
 \end{figure}
 When comparing the \CFA stealing heuristics in Figure~\ref{f:cfaExecutorAMD} it can be seen that the random heuristic falls slightly behind the other two, but in Figure~\ref{f:cfaExecutorIntel} the runtime of all heuristics are nearly identical to eachother.
+When comparing the \CFA stealing heuristics in Figure~\ref{f:cfaExecutorAMD} it can be seen that the random heuristic falls slightly behind the other two, but in Figure~\ref{f:cfaExecutorIntel} the runtime of all heuristics are nearly identical to each other.
 \begin{figure}
 …
 \end{figure}
 The repeat microbenchmark also evaluates the executor.
 It stresses the executor's ability to withstand contention on queues, as it repeatedly fans out messages from a single client to 100000 servers who then all respond to the client.
 After this scatter and gather repeats 200 times the benchmark terminates.
 The messages from the servers to the client will likely all come in on the same queue, resulting in high contention.
 As such this benchmark will not scale with the number of processors, since more processors will result in higher contention.
 In Figure~\ref{f:RepeatAMD} we can see that \CFA performs well compared to \uC, however by less of a margin than the executor benchmark.
 One factor in this result is that the contention on the queues poses a significant bottleneck.
+The repeat microbenchmark also evaluates the executor.
+It stresses the executor's ability to withstand contention on queues, as it repeatedly fans out messages from a single client to 100000 servers who then all respond to the client.
+After this scatter and gather repeats 200 times the benchmark terminates.
+The messages from the servers to the client will likely all come in on the same queue, resulting in high contention.
+As such this benchmark will not scale with the number of processors, since more processors will result in higher contention.
+In Figure~\ref{f:RepeatAMD} we can see that \CFA performs well compared to \uC, however by less of a margin than the executor benchmark.
+One factor in this result is that the contention on the queues poses a significant bottleneck.
 As such the gains from using the copy queue are much less apparent.
 …
 In Figure~\ref{f:RepeatIntel} \uC and \CFA are very comparable.
 In comparison with the other systems \uC does well on the repeat benchmark since it does not have work stealing.
 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.
 As such stealing the client can result in a hit in performance.
+In comparison with the other systems \uC does well on the repeat benchmark since it does not have work stealing.
+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.
+As such stealing the client can result in a hit in performance.
 This result is shown in Figure~\ref{f:cfaRepeatAMD} and \ref{f:cfaRepeatIntel} where the no-stealing version of \CFA performs better than both stealing variations.
 In particular on the Intel machine in Figure~\ref{f:cfaRepeatIntel}, the cost of stealing is higher, which can be seen in the vertical shift of Akka, CAF and CFA results in Figure~\ref{f:RepeatIntel} (\uC and ProtoActor do not have work stealing).
+In particular on the Intel machine in Figure~\ref{f:cfaRepeatIntel}, the cost of stealing is higher, which can be seen in the vertical shift of Akka, CAF and CFA results in Figure~\ref{f:RepeatIntel} (\uC and ProtoActor do not have work stealing).
 The shift for CAF is particularly large, which further supports the hypothesis that CAF's work stealing is particularly eager.
 In both the executor and the repeat benchmark CAF performs poorly.
 It is hypothesized that CAF has an aggressive work stealing algorithm, that eagerly attempts to steal.
 This results in poor performance in benchmarks with small messages containing little work per message.
 On the other hand, in \ref{f:MatrixAMD} CAF performs much better since each message has a large amount of work, and few messages are sent, so the eager work stealing allows for the clean up of loose ends to occur faster.
 This hypothesis stems from experimentation with \CFA.
 CAF uses a randomized work stealing heuristic.
+In both the executor and the repeat benchmark CAF performs poorly.
+It is hypothesized that CAF has an aggressive work stealing algorithm, that eagerly attempts to steal.
+This results in poor performance in benchmarks with small messages containing little work per message.
+On the other hand, in \ref{f:MatrixAMD} CAF performs much better since each message has a large amount of work, and few messages are sent, so the eager work stealing allows for the clean up of loose ends to occur faster.
+This hypothesis stems from experimentation with \CFA.
+CAF uses a randomized work stealing heuristic.
 In \CFA if the system is tuned so that it steals work much more eagerly with a randomized it was able to replicate the results that CAF achieves in the matrix benchmark, but this tuning performed much worse on all other microbenchmarks that we present, since they all perform a small amount of work per message.
 …
         \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|}{CAF} & \multicolumn{1}{c|}{Akka} & \multicolumn{1}{c|}{\uC} & \multicolumn{1}{c@{}}{ProtoActor} \\
                 \hline
+                \hline
                 AMD             & \input{data/pykeExecutorMem} \\
                 \hline
+                \hline
                 Intel   & \input{data/nasusExecutorMem}
         \end{tabular}
 \end{table}
 Figure~\ref{t:ExecutorMemory} shows the high memory watermark of the actor systems when running the executor benchmark on 48 cores.
 \CFA has a high watermark relative to the other non-garbage collected systems \uC, and CAF.
 This is a result of the copy queue data structure, as it will overallocate storage and not clean up eagerly, whereas the per envelope allocations will always allocate exactly the amount of storage needed.
+Figure~\ref{t:ExecutorMemory} shows the high memory watermark of the actor systems when running the executor benchmark on 48 cores.
+\CFA has a high watermark relative to the other non-garbage collected systems \uC, and CAF.
+This is a result of the copy queue data structure, as it will over-allocate storage and not clean up eagerly, whereas the per envelope allocations will always allocate exactly the amount of storage needed.
 \subsection{Matrix Multiply}
 The matrix benchmark evaluates the actor systems in a practical application, where actors concurrently multiplies two matrices.
+The matrix benchmark evaluates the actor systems in a practical application, where actors concurrently multiplies two matrices.
 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 executor or message sending system.
 …
 \end{displaymath}
 The benchmark uses input matrices $X$ and $Y$ that are both $3072$ by $3072$ in size.
 An actor is made for each row of $X$ and is passed via message the information needed to calculate a row of the result matrix $Z$.
 Given that the bottleneck of the benchmark is the computation of the result matrix, it follows that the results in Figures~\ref{f:MatrixAMD} and \ref{f:MatrixIntel} are clustered closer than other experiments.
 In Figure~\ref{f:MatrixAMD} \uC and \CFA have identical performance and in Figure~\ref{f:MatrixIntel} \uC pulls ahead og \CFA after 24 cores likely due to costs associated with work stealing while hyperthreading.
 As mentioned in \ref{s:executorPerf}, it is hypothesized that CAF performs better in this benchmark compared to others due to its eager work stealing implementation.
+The benchmark uses input matrices $X$ and $Y$ that are both $3072$ by $3072$ in size.
+An actor is made for each row of $X$ and is passed via message the information needed to calculate a row of the result matrix $Z$.
+Given that the bottleneck of the benchmark is the computation of the result matrix, it follows that the results in Figures~\ref{f:MatrixAMD} and \ref{f:MatrixIntel} are clustered closer than other experiments.
+In Figure~\ref{f:MatrixAMD} \uC and \CFA have identical performance and in Figure~\ref{f:MatrixIntel} \uC pulls ahead of \CFA after 24 cores likely due to costs associated with work stealing while hyperthreading.
+As mentioned in \ref{s:executorPerf}, it is hypothesized that CAF performs better in this benchmark compared to others due to its eager work stealing implementation.
 In Figures~\ref{f:cfaMatrixAMD} and \ref{f:cfaMatrixIntel} there is little negligible performance difference across \CFA stealing heuristics.

doc/theses/colby_parsons_MMAth/text/mutex_stmt.tex

-              rfa5e1aa5
+              rb7b3e41
 \begin{figure}
         \centering
+    \captionsetup[subfloat]{labelfont=footnotesize,textfont=footnotesize}
         \subfloat[AMD]{
                 \resizebox{0.5\textwidth}{!}{\input{figures/nasus_Aggregate_Lock_2.pgf}}
 …
                 \resizebox{0.5\textwidth}{!}{\input{figures/pyke_Aggregate_Lock_2.pgf}}
+        }
+    \bigskip
         \subfloat[AMD]{
 …
                 \resizebox{0.5\textwidth}{!}{\input{figures/pyke_Aggregate_Lock_4.pgf}}
+        }
+    \bigskip
         \subfloat[AMD]{

doc/theses/colby_parsons_MMAth/thesis.tex

-              rfa5e1aa5
+              rb7b3e41
     citecolor=blue,         % color of links to bibliography
     filecolor=magenta,      % color of file links
     urlcolor=cyan,          % color of external links
+    urlcolor=blue,          % color of external links
     breaklinks=true
+}
 …
     urlcolor=black}
 }{} % end of ifthenelse (no else)
+\usepackage{breakurl}
+\urlstyle{rm}
 % \usepackage[acronym]{glossaries}

doc/user/figures/EHMHierarchy.fig

-              rfa5e1aa5
+              rb7b3e41
 1 1.00 60.00 90.00
 1950 4950 1725
 1 0 50 -1 0 13 0.0000 2 135 225 1950 1650 IO\001
 1 0 50 -1 0 13 0.0000 2 135 915 4950 1650 Arithmetic\001
 1 0 50 -1 0 13 0.0000 2 150 330 1350 2100 File\001
 1 0 50 -1 0 13 0.0000 2 135 735 2550 2100 Network\001
 1 0 50 -1 0 13 0.0000 2 180 1215 3750 2100 DivideByZero\001
 1 0 50 -1 0 13 0.0000 2 150 810 4950 2100 Overflow\001
 1 0 50 -1 0 13 0.0000 2 150 915 6000 2100 Underflow\001
 1 0 50 -1 0 13 0.0000 2 180 855 3450 1200 Exception\001
+1 0 50 -1 0 12 0.0000 2 135 225 1950 1650 IO\001
+1 0 50 -1 0 12 0.0000 2 135 915 4950 1650 Arithmetic\001
+1 0 50 -1 0 12 0.0000 2 150 330 1350 2100 File\001
+1 0 50 -1 0 12 0.0000 2 135 735 2550 2100 Network\001
+1 0 50 -1 0 12 0.0000 2 180 1215 3750 2100 DivideByZero\001
+1 0 50 -1 0 12 0.0000 2 150 810 4950 2100 Overflow\001
+1 0 50 -1 0 12 0.0000 2 150 915 6000 2100 Underflow\001
+1 0 50 -1 0 12 0.0000 2 180 855 3450 1200 Exception\001

doc/user/user.tex

-              rfa5e1aa5
+              rb7b3e41
 %% Created On       : Wed Apr  6 14:53:29 2016
 %% Last Modified By : Peter A. Buhr
 %% Last Modified On : Mon Aug 22 23:43:30 2022
 %% Update Count     : 5503
+%% Last Modified On : Mon Jun  5 21:18:29 2023
+%% Update Count     : 5521
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 …
 \huge \CFA Team (past and present) \medskip \\
 \Large Andrew Beach, Richard Bilson, Michael Brooks, Peter A. Buhr, Thierry Delisle, \smallskip \\
 \Large Glen Ditchfield, Rodolfo G. Esteves, Aaron Moss, Colby Parsons, Rob Schluntz, \smallskip \\
 \Large Fangren Yu, Mubeen Zulfiqar
+\Large Glen Ditchfield, Rodolfo G. Esteves, Jiada Liang, Aaron Moss, Colby Parsons \smallskip \\
+\Large Rob Schluntz, Fangren Yu, Mubeen Zulfiqar
 }% author
 …
 Like \Index*[C++]{\CC{}}, there may be both old and new ways to achieve the same effect.
 For example, the following programs compare the C, \CFA, and \CC I/O mechanisms, where the programs output the same result.
 \begin{flushleft}
 \begin{tabular}{@{}l@{\hspace{1em}}l@{\hspace{1em}}l@{}}
 \multicolumn{1}{@{}c@{\hspace{1em}}}{\textbf{C}}        & \multicolumn{1}{c}{\textbf{\CFA}}     & \multicolumn{1}{c@{}}{\textbf{\CC}}   \\
+\begin{center}
+\begin{tabular}{@{}lll@{}}
+\multicolumn{1}{@{}c}{\textbf{C}}       & \multicolumn{1}{c}{\textbf{\CFA}}     & \multicolumn{1}{c@{}}{\textbf{\CC}}   \\
 \begin{cfa}[tabsize=3]
 #include <stdio.h>$\indexc{stdio.h}$
 …
 \end{cfa}
 \end{tabular}
 \end{flushleft}
+\end{center}
 While \CFA I/O \see{\VRef{s:StreamIOLibrary}} looks similar to \Index*[C++]{\CC{}}, there are important differences, such as automatic spacing between variables and an implicit newline at the end of the expression list, similar to \Index*{Python}~\cite{Python}.
 …
 still works.
 Nevertheless, reversing the default action would have a non-trivial effect on case actions that compound, such as the above example of processing shell arguments.
 Therefore, to preserve backwards compatibility, it is necessary to introduce a new kind of ©switch© statement, called \Indexc{choose}, with no implicit fall-through semantics and an explicit fall-through if the last statement of a case-clause ends with the new keyword \Indexc{fallthrough}/\Indexc{fallthru}, \eg:
+Therefore, to preserve backwards compatibility, it is necessary to introduce a new kind of ©switch© statement, called \Indexc{choose}, with no implicit fall-through semantics and an explicit fall-through if the last statement of a case-clause ends with the new keyword \Indexc{fallthrough}/\-\Indexc{fallthru}, \eg:
 \begin{cfa}
 ®choose® ( i ) {
 …
 \end{cfa}
 \end{itemize}
 \R{Warning}: specifying the down-to range maybe unexcepted because the loop control \emph{implicitly} switches the L and H values (and toggles the increment/decrement for I):
+\R{Warning}: specifying the down-to range maybe unexpected because the loop control \emph{implicitly} switches the L and H values (and toggles the increment/decrement for I):
 \begin{cfa}
 for ( i; 1 ~ 10 )       ${\C[1.5in]{// up range}$
 …
 for ( i; ®10 -~ 1® )    ${\C{// \R{WRONG down range!}}\CRT}$
 \end{cfa}
 The reason for this sematics is that the range direction can be toggled by adding/removing the minus, ©'-'©, versus interchanging the L and H expressions, which has a greater chance of introducing errors.
+The reason for this semantics is that the range direction can be toggled by adding/removing the minus, ©'-'©, versus interchanging the L and H expressions, which has a greater chance of introducing errors.
 …
 Days days = Mon; // enumeration type declaration and initialization
 \end{cfa}
+The set of enums are injected into the variable namespace at the definition scope.
+Hence, enums may be overloaded with enum/variable/function names.
+\begin{cfa}
+The set of enums is injected into the variable namespace at the definition scope.
+Hence, enums may be overloaded with variable, enum, and function names.
+\begin{cfa}
+int Foo;                        $\C{// type/variable separate namespaces}$
 enum Foo { Bar };
 enum Goo { Bar };       $\C[1.75in]{// overload Foo.Bar}$
-int Foo;                        $\C{// type/variable separate namespace}$
 double Bar;                     $\C{// overload Foo.Bar, Goo.Bar}\CRT$
 \end{cfa}
 …
 Hence, the value of enum ©Mon© is 0, ©Tue© is 1, ...\,, ©Sun© is 6.
 If an enum value is specified, numbering continues by one from that value for subsequent unnumbered enums.
 If an enum value is an expression, the compiler performs constant-folding to obtain a constant value.
+If an enum value is a \emph{constant} expression, the compiler performs constant-folding to obtain a constant value.
 \CFA allows other integral types with associated values.
 …
 \begin{cfa}
 // non-integral numeric
 enum( ®double® ) Math { PI_2 = 1.570796, PI = 3.141597,  E = 2.718282 }
+enum( ®double® ) Math { PI_2 = 1.570796, PI = 3.141597, E = 2.718282 }
 // pointer
 enum( ®char *® ) Name { Fred = "Fred",  Mary = "Mary",  Jane = "Jane" };
+enum( ®char *® ) Name { Fred = "Fred",  Mary = "Mary", Jane = "Jane" };
 int i, j, k;
 enum( ®int *® ) ptr { I = &i,  J = &j,  K = &k };
 enum( ®int &® ) ref { I = i,  J = j,  K = k };
+enum( ®int &® ) ref { I = i,   J = j,   K = k };
 // tuple
 enum( ®[int, int]® ) { T = [ 1, 2 ] };
 …
 \begin{cfa}
 enum( char * ) Name2 { ®inline Name®, Jack = "Jack", Jill = "Jill" };
 enum ®/* inferred */®  Name3 { ®inline Name2®, Sue = "Sue", Tom = "Tom" };
+enum ®/* inferred */® Name3 { ®inline Name2®, Sue = "Sue", Tom = "Tom" };
 \end{cfa}
 Enumeration ©Name2© inherits all the enums and their values from enumeration ©Name© by containment, and a ©Name© enumeration is a subtype of enumeration ©Name2©.
 …
                                    "[ output-file (default stdout) ] ]";
                 } // choose
         } catch( ®Open_Failure® * ex; ex->istream == &in ) {
+        } catch( ®open_failure® * ex; ex->istream == &in ) { $\C{// input file errors}$
                 ®exit® | "Unable to open input file" | argv[1];
         } catch( ®Open_Failure® * ex; ex->ostream == &out ) {
+        } catch( ®open_failure® * ex; ex->ostream == &out ) { $\C{// output file errors}$
                 ®close®( in );                                          $\C{// optional}$
                 ®exit® | "Unable to open output file" | argv[2];
 …
 \item
 \Indexc{sepDisable}\index{manipulator!sepDisable@©sepDisable©} and \Indexc{sepEnable}\index{manipulator!sepEnable@©sepEnable©} toggle printing the separator.
+\Indexc{sepDisable}\index{manipulator!sepDisable@©sepDisable©} and \Indexc{sepEnable}\index{manipulator!sepEnable@©sepEnable©} globally toggle printing the separator.
 \begin{cfa}[belowskip=0pt]
 sout | sepDisable | 1 | 2 | 3; $\C{// turn off implicit separator}$
 …
 \item
 \Indexc{sepOn}\index{manipulator!sepOn@©sepOn©} and \Indexc{sepOff}\index{manipulator!sepOff@©sepOff©} toggle printing the separator with respect to the next printed item, and then return to the global separator setting.
+\Indexc{sepOn}\index{manipulator!sepOn@©sepOn©} and \Indexc{sepOff}\index{manipulator!sepOff@©sepOff©} locally toggle printing the separator with respect to the next printed item, and then return to the global separator setting.
 \begin{cfa}[belowskip=0pt]
 sout | 1 | sepOff | 2 | 3; $\C{// turn off implicit separator for the next item}$
 …
 \end{cfa}
 Note, a terminating ©nl© is merged (overrides) with the implicit newline at the end of the ©sout© expression, otherwise it is impossible to to print a single newline
+Note, a terminating ©nl© is merged (overrides) with the implicit newline at the end of the ©sout© expression, otherwise it is impossible to print a single newline
 \item
 \Indexc{nlOn}\index{manipulator!nlOn@©nlOn©} implicitly prints a newline at the end of each output expression.

Context Navigation

Legend:

doc/papers/llheap/Paper.tex

doc/papers/llheap/figures/AllocatorComponents.fig

doc/theses/colby_parsons_MMAth/Makefile

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/balance.cfa

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/dynamic.cfa

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/executor.cfa

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/matrix.cfa

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/repeat.cfa

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/static.cfa

doc/theses/colby_parsons_MMAth/benchmarks/actors/plotData.py

doc/theses/colby_parsons_MMAth/benchmarks/channels/plotData.py

doc/theses/colby_parsons_MMAth/benchmarks/mutex_stmt/plotData.py

doc/theses/colby_parsons_MMAth/code/basic_actor_example.cfa

doc/theses/colby_parsons_MMAth/diagrams/gulp.tikz

doc/theses/colby_parsons_MMAth/diagrams/inverted_actor.tikz

doc/theses/colby_parsons_MMAth/diagrams/standard_actor.tikz

doc/theses/colby_parsons_MMAth/glossary.tex

doc/theses/colby_parsons_MMAth/local.bib

doc/theses/colby_parsons_MMAth/style/style.tex

doc/theses/colby_parsons_MMAth/text/CFA_intro.tex

doc/theses/colby_parsons_MMAth/text/actors.tex

doc/theses/colby_parsons_MMAth/text/mutex_stmt.tex

doc/theses/colby_parsons_MMAth/thesis.tex

doc/user/figures/EHMHierarchy.fig

doc/user/user.tex

Download in other formats: