source: doc/theses/mike_brooks_MMath/list.tex@ 408f954

\chapter{Linked List}

This chapter presents my work on designing and building a linked-list library for \CFA.
Due to time limitations and the needs expressed by the \CFA runtime developers, I focussed on providing a doubly-linked list, and its bidirectional iterators for traversal. 
Simpler data-structures, like stack and queue, can be built from the doubly-linked mechanism with only a slight storage/performance cost because of the unused link field.
Reducing to data-structures with a single link follows directly from the more complex double links and its iterators.


\section{Plan-9 Inheritance}
\label{s:Plan9Inheritance}

This chapter uses a form of inheritance from the Plan-9 C dialect~\cite[\S~3.3]{Thompson90new}, which is supported by @gcc@ and @clang@ using @-fplan9-extensions@.
\CFA has its own variation of the Plan-9 mechanism, where the nested type is denoted using @inline@.
\begin{cfa}
union U {  int x;  double y;  char z; };
struct W { int i;  double j;  char k; };
struct S {
        @inline@ struct W;  $\C{// extended Plan-9 inheritance}$
        unsigned int tag;
        @inline@ U;                     $\C{// extended Plan-9 inheritance}$
} s;
\end{cfa}
Inline inheritance is containment, where the inlined field is unnamed and the type's internal fields are hoisted into the containing structure.
Hence, the field names must be unique, unlike \CC nested types, but any inlined type-names are at a nested scope level, unlike aggregate nesting in C.
Note, the position of the containment is normally unimportant, unless there is some form of memory or @union@ overlay.
Finally, the inheritance declaration of @U@ is not prefixed with @union@.
Like \CC, \CFA allows optional prefixing of type names with their kind, \eg @struct@, @union@, and @enum@, unless there is ambiguity with variable names in the same scope.

\VRef[Figure]{f:Plan9Polymorphism} shows the key polymorphic feature of Plan-9 inheritance: implicit conversion of values and pointers for nested types.
In the example, there are implicit conversions from @S@ to @U@ and @S@ to @W@, extracting the appropriate value or pointer for the substructure.
\VRef[Figure]{f:DiamondInheritancePattern} shows complex multiple inheritance patterns are possible, like the \newterm{diamond pattern}~\cite[\S~6.1]{Stroustrup89}\cite[\S~4]{Cargill91}.
Currently, the \CFA type-system does not support @virtual@ inheritance.

\begin{figure}
\begin{cfa}
void f( U, U * ); $\C{// value, pointer}$
void g( W, W * ); $\C{// value, pointer}$
U u, * up;   W w, * wp;   S s, * sp;
u = s;   up = sp; $\C{// value, pointer}$
w = s;   wp = sp; $\C{// value, pointer}$
f( s, &s ); $\C{// value, pointer}$
g( s, &s ); $\C{// value, pointer}$
\end{cfa}
\caption{Plan-9 Polymorphism}
\label{f:Plan9Polymorphism}
\end{figure}

\begin{figure}
\setlength{\tabcolsep}{10pt}
\begin{tabular}{ll@{}}
\multicolumn{1}{c}{\CC} & \multicolumn{1}{c}{\CFA}      \\
\begin{c++}
struct B { int b; };
struct L : @public B@ { int l, w; };
struct R : @public B@ { int r, w; };
struct T : @public L, R@ { int t; };
                              T
               B      L          B      R
T t = { { { 5 }, 3, 4 }, { { 8 }, 6, 7 }, 3 };
t.t = 42;
t.l = 42;
t.r = 42;
((L &)t).b = 42;  // disambiguate
\end{c++}
&
\begin{cfa}
struct B { int b; };
struct L { @inline B;@ int l, w; };
struct R { @inline B;@ int r, w; };
struct T { @inline L; inline R;@ int t; };
                              T
               B      L          B      R
T t = { { { 5 }, 3, 4 }, { { 8 }, 6, 7 }, 3 };
t.t = 42;
t.l = 42;
t.r = 42;
((L &)t).b = 42;  // disambiguate, proposed solution t.L.b = 42;
\end{cfa}
\end{tabular}
\caption{Diamond Non-Virtual Inheritance Pattern}
\label{f:DiamondInheritancePattern}
\end{figure}


\section{Features}

The following features directed this project, where the goal is high-performance list operations required by \CFA runtime components, like the threading library.


\subsection{Core Design Issues}

The doubly-linked list attaches links intrusively in a node, allows a node to appear on multiple lists (axes) simultaneously, integrates with user code via the type system, treats its ends uniformly, and identifies a list using an explicit head.
This design covers system and data management issues stated in \VRef{toc:lst:issue}.

\VRef[Figure]{fig:lst-features-intro} continues the running @req@ example from \VRef[Figure]{fig:lst-issues-attach} using the \CFA list @dlist@.
The \CFA link attachment is intrusive so the resulting memory layout is per user node, as for the LQ version of \VRef[Figure]{f:Intrusive}.
The \CFA framework provides generic type @dlink( T )@ (not to be confused with @dlist@) for the two link fields (front and back).
A user inserts the links into the @req@ structure via \CFA inline-inheritance \see{\VRef{s:Plan9Inheritance}}.
Lists leverage the automatic conversion of a pointer to anonymous inline field for assignments and function calls.
Therefore, a reference to a @req@ is implicitly convertible to @dlink@ in both contexts.
The links in @dlist@ point at another embedded @dlist@ node, know the offsets of all links (data is abstract but accessible), and any field-offset arithmetic or link-value changes are safe and abstract.

\begin{figure}
    \lstinput{20-30}{lst-features-intro.run.cfa}
    \caption[Multiple link axes in \CFA list library]{
        Demonstration of the running \lstinline{req} example, done using the \CFA list library.
        This example is equivalent to the three approaches in \VRef[Figure]{fig:lst-issues-attach}.
    }
    \label{fig:lst-features-intro}
\end{figure}

\VRef[Figure]{f:dlistOutline} shows the outline for types @dlink@ and @dlist@.
Note, the first @forall@ clause is distributed across all the declaration in its containing block, eliminating repetition on each declaration.
The second nested @forall@ on @dlist@ is also distributed and adds an optional second type parameter, @tLinks@, denoting the linking axis \see{\VRef{s:Axis}}, \ie the kind of list this node can appear on.

\begin{figure}
\begin{cfa}
forall( tE & ) {                                        $\C{// distributed}$
        struct @dlink@ { ...  };                $\C{// abstract type}$
        static inline void ?{}( dlink( tE ) & this );  $\C{// constructor}$

        forall( tLinks & = dlink( tE ) ) { $\C{// distributed, default type for axis}$
                struct @dlist@ { ... };         $\C{// abstract type}$
                static inline void ?{}( dlist( tE, tLinks ) & this ); $\C{// constructor}$
        }
}
\end{cfa}
\caption{\lstinline{dlisk} / \lstinline{dlist} Outline}
\label{f:dlistOutline}
\end{figure}

\VRef[Figure]{fig:lst-features-multidir} shows how the \CFA library supports multi-inline links, so a node has multiple axes.
The declaration of @req@ has two inline-inheriting @dlink@ occurrences.
The first of these gives a type named @req.by_pri@, @req@ inherits from it, and it inherits from @dlink@.
The second line @req.by_rqr@ is similar to @req.by_pri@.
Thus, there is a diamond, non-virtual, inheritance from @req@ to @dlink@, with @by_pri@ and @by_rqr@ being the mid-level types \see{\VRef[Figure]{f:DiamondInheritancePattern}}.

The declarations of the list-head objects, @reqs_pri@, @reqs_rqr_42@, @reqs_rqr_17@, and @reqs_rqr_99@, bind which link nodes in @req@ are used by this list.
Hence, the type of the variable @reqs_pri@, @dlist(req, req.by_pri)@, means operations on @reqs_pri@ implicitly select (disambiguate) the correct @dlink@s, \eg the calls @insert_first(reqs_pri, ...)@ imply, ``here, we are working by priority.''
As in \VRef[Figure]{fig:lst-issues-multi-static}, three lists are constructed, a priority list containing all nodes, a list with only nodes containing the value 42, and a list with only nodes containing the value 17.

\begin{figure}
\centering

\begin{tabular}{@{}ll@{}}
\multicolumn{1}{c}{\CFA} &      \multicolumn{1}{c}{C} \\
        \begin{tabular}{@{}l@{}}
        \lstinput{20-31}{lst-features-multidir.run.cfa} \\
        \lstinput{43-71}{lst-features-multidir.run.cfa}
        \end{tabular}
&
        \lstinput[language=C++]{20-60}{lst-issues-multi-static.run.c}
\end{tabular}

\caption{
        Demonstration of multiple static link axes done in the \CFA list library.
        The right example is from \VRef[Figure]{fig:lst-issues-multi-static}.
        The left \CFA example does the same job.
}
\label{fig:lst-features-multidir}
\end{figure}

The list library also supports the common case of single directionality more naturally than LQ.  
Returning to \VRef[Figure]{fig:lst-features-intro}, the single-axis list has no contrived name for the link axis as it uses the default type in the definition of @dlist@;
in contrast, the LQ list in \VRef[Figure]{f:Intrusive} adds the unnecessary field name @d@.
In \CFA, a single axis list sets up a single inheritance with @dlink@, and the default list axis is to itself.

When operating on a list with several axes and operations that do not take the list head, the list axis can be ambiguous.
For example, a call like @insert_after( r1, r2 )@ does not have enough information to know which axes to select implicitly.
Is @r2@ supposed to be the next-priority request after @r1@, or is @r2@ supposed to join the same-requester list of @r1@?
As such, the \CFA type-system gives an ambiguity error for this call.
There are multiple ways to resolve the ambiguity.
The simplest is an explicit cast on each call to select the specific axis, \eg @insert_after( (by_pri)r1, r2 )@.
However, multiple explicit casts are tedious and error-prone.
To mitigate this issue, the list library provides a hook for applying the \CFA language's scoping and priority rules.
\begin{cfa}
with ( DLINK_VIA( req, req.pri ) ) insert_after( r1, r2 );
\end{cfa}
Here, the @with@ statement opens the scope of the object type for the expression;
hence, the @DLINK_VIA@ result causes one of the list axes to become a more attractive candidate to \CFA's overload resolution.
This boost can be applied across multiple statements in a block or an entire function body.
\begin{cquote}
\setlength{\tabcolsep}{15pt}
\begin{tabular}{@{}ll@{}}
\begin{cfa}
@with( DLINK_VIA( req, req.pri ) ) {@
        ...  insert_after( r1, r2 );  ...
@}@
\end{cfa}
&
\begin{cfa}
void f() @with( DLINK_VIA( req, req.pri ) ) {@
        ... insert_after( r1, r2 ); ...
@}@
\end{cfa}
\end{tabular}
\end{cquote}
Within the @with@, the code acts as if there is only one list axis, without explicit casting.

Unlike the \CC template container-types, the \CFA library works completely within the type system;
both @dlink@ and @dlist@ are ordinary types, not language macros.
There is no textual expansion other than header-included static-inline function for performance.
Hence, errors in user code are reported only with mention of the library's declarations, versus long template names in error messages.
Finally, the library is separately compiled from the usage code, modulo inlining.


\section{List API}

\VRef[Figure]{f:ListAPI} shows the API for the doubly-link list operations, where each is explained.
\begin{itemize}[leftmargin=*]
\item
@listed@ returns true if the node is an element of a list and false otherwise.
\item
@empty@ returns true if the list has no nodes and false otherwise.
\item
@first@ returns a reference to the first node of the list without removing it or @0p@ if the list is empty.
\item
@last@ returns a reference to the last node of the list without removing it or @0p@ if the list is empty.
\item
@insert_before@ adds a node before a specified node \see{\lstinline{insert_last} for insertion at the end}\footnote{
Some list packages allow \lstinline{0p} (\lstinline{nullptr}) for the before/after node implying insert/remove at the start/end of the list, respectively.
However, this inserts an \lstinline{if} statement in the fastpath of a potentially commonly used list operation.}
\item
@insert_after@ adds a node after a specified node \see{\lstinline{insert_first} for insertion at the start}\footnotemark[\value{footnote}].
\item
@remove@ removes a specified node from the list (any location) and returns a reference to the node.
\item
@iter@ create an iterator for the list.
\item
@recede@ returns true if the iterator cursor is advanced to the previous (predecessor, towards first) node before the prior cursor node and false otherwise.
\item
@advance@ returns true if the iterator cursor is advanced to the next (successor, towards last) node after the prior cursor node and false otherwise.
\item
@first@ returns true if the node is the first node in the list and false otherwise.
\item
@last@ returns true if the node is the last node in the list and false otherwise.
\item
@pred@ returns a reference to the previous (predecessor, towards first) node before a specified node or @0p@ if a specified node is the first node in the list.
\item
@next@ returns a reference to the next (successor, towards last) node after a specified node or @0p@ if a specified node is the last node in the list.
\item
@insert_first@ adds a node to the start of the list so it becomes the first node and returns a reference to the node for cascading.
\item
@insert_last@ adds a node to the end of the list so it becomes the last node and returns returns a reference to the node for cascading.
\item
@remove_first@ removes the first node and returns a reference to it or @0p@ if the list is empty.
\item
@remove_last@ removes the last node and returns a reference to it or @0p@ if the list is empty.
\item
@transfer@ transfers all nodes from the @from@ list to the end of the @to@ list; the @from@ list is empty after the transfer.
\item
@split@ transfers the @from@ list up to node to the end of the @to@ list; the @from@ list becomes the list after the node.
The node must be in the @from@ list.
\end{itemize}
For operations @insert_*@, @insert@, and @remove@, a variable-sized list of nodes can be specified using \CFA's tuple type~\cite[\S~4.7]{Moss18} (not discussed), \eg @insert( list, n1, n2, n3 )@, recursively invokes @insert( list, n@$_i$@ )@.\footnote{
Currently, a resolver bug between tuple types and references means tuple routines must use pointer parameters.
Nevertheless, the imaginary reference versions are used here as the code is cleaner, \eg no \lstinline{&} on call arguments.}

\begin{figure}
\begin{cfa}
E & listed( E & node );
E & empty( dlist( E ) & list );
E & first( dlist( E ) & list );
E & last( dlist( E ) & list );
E & insert_before( E & before, E & node );
E & insert_after( E & after, E & node );
E & remove( E & node );
E & iter( dlist( E ) & list );
bool advance( E && refx );
bool recede( E && refx );
bool first( E & node );
bool last( E & node );
E & prev( E & node );
E & next( E & node );
E & insert_first( dlist( E ) & list, E & node );
E & insert_last( dlist( E ) & list, E & node ); // synonym insert
E & remove_first( dlist( E ) & list );
E & remove_last( dlist( E ) & list );
void transfer( dlist( E ) & to, dlist( E ) & from ) {
void split( dlist( E ) & to, dlist( E ) & from, E & node ) {
\end{cfa}
\caption{\CFA List API}
\label{f:ListAPI}
\end{figure}


\subsection{Iteration}

It is possible to iterate through a list manually or using a set of standard macros.
\VRef[Figure]{f:IteratorDriver} shows the iterator outline, managing a list of nodes, used throughout the following iterator examples.
Each example assumes its loop body prints the value in the current node.

\begin{figure}
\begin{cfa}
#include <fstream.hfa>
#include <list.hfa>
struct node {
        int v;
        inline dlink(node);
};
int main() {
        dlist(node) list;
        node n1 = { 1 }, n2 = { 2 }, n3 = { 3 }, n4 = { 4 };
        insert( list, n1, n2, n3, n4 );                                 $\C{// insert in any order}$
        sout | nlOff;
        @for ( ... )@ sout | it.v | ",";   sout | nl;   $\C{// iterator examples in text}$
        remove( n1, n2, n3, n4 );                                       $\C{// remove in any order}$
}
\end{cfa}
\caption{Iterator Driver}
\label{f:IteratorDriver}
\end{figure}

The manual method is low level but allows complete control of the iteration.
The list cursor (index) can be either a pointer or a reference to a node in the list.
The choice depends on how the programmer wants to access the fields: @it->f@ or @it.f@.
The following examples use a reference because the loop body manipulates the node values rather than the list pointers.
The end of iteration is denoted by the loop cursor returning @0p@.

\noindent
Iterating forward and reverse through the entire list.
\begin{cquote}
\setlength{\tabcolsep}{15pt}
\begin{tabular}{@{}l|l@{}}
\begin{cfa}
for ( node & it = @first@( list ); &it /* != 0p */ ; &it = &@next@( it ) ...
for ( node & it = @last@( list ); &it; &it = &@prev@( it ) ) ...
\end{cfa}
&
\begin{cfa}
1, 2, 3, 4,
4, 3, 2, 1,
\end{cfa}
\end{tabular}
\end{cquote}
Iterating forward and reverse from a starting node through the remaining list.
\begin{cquote}
\setlength{\tabcolsep}{15pt}
\begin{tabular}{@{}l|l@{}}
\begin{cfa}
for ( node & it = @n2@; &it; &it = &@next@( it ) ) ...
for ( node & it = @n3@; &it; &it = &@prev@( it ) ) ...
\end{cfa}
&
\begin{cfa}
2, 3, 4,
3, 2, 1,
\end{cfa}
\end{tabular}
\end{cquote}
Iterating forward and reverse from a starting node to an ending node through the contained list.
\begin{cquote}
\setlength{\tabcolsep}{15pt}
\begin{tabular}{@{}l|l@{}}
\begin{cfa}
for ( node & it = @n2@; &it @!= &n4@; &it = &@next@( it ) ) ...
for ( node & it = @n4@; &it @!= &n2@; &it = &@prev@( it ) ) ...
\end{cfa}
&
\begin{cfa}
2, 3,
4, 3,
\end{cfa}
\end{tabular}
\end{cquote}
Iterating forward and reverse through the entire list using the shorthand start at the list head and pick an axis.
In this case, @advance@ and @recede@ return a boolean, like \CC @while ( cin >> i )@.
\begin{cquote}
\setlength{\tabcolsep}{15pt}
\begin{tabular}{@{}l|l@{}}
\begin{cfa}
for ( node & it = @iter@( list ); @advance@( it ); ) ...
for ( node & it = @iter@( list ); @recede@( it ); ) ...
\end{cfa}
&
\begin{cfa}
1, 2, 3, 4,
4, 3, 2, 1,
\end{cfa}
\end{tabular}
\end{cquote}
Finally, there are convenience macros that look like @foreach@ in other programming languages.
Iterating forward and reverse through the entire list.
\begin{cquote}
\setlength{\tabcolsep}{15pt}
\begin{tabular}{@{}l|l@{}}
\begin{cfa}
FOREACH( list, it ) ...
FOREACH_REV( list, it ) ...
\end{cfa}
&
\begin{cfa}
1, 2, 3, 4,
4, 3, 2, 1,
\end{cfa}
\end{tabular}
\end{cquote}
Iterating forward and reverse through the entire list or until a predicate is triggered.
\begin{cquote}
\setlength{\tabcolsep}{15pt}
\begin{tabular}{@{}l|l@{}}
\begin{cfa}
FOREACH_COND( list, it, @it.v == 3@ ) ...
FOREACH_REV_COND( list, it, @it.v == 1@ ) ...
\end{cfa}
&
\begin{cfa}
1, 2,
4, 3, 2,
\end{cfa}
\end{tabular}
\end{cquote}
Macros are not ideal, so future work is to provide a language-level @foreach@ statement, like \CC.
Finally, a predicate can be added to any of the manual iteration loops.
\begin{cquote}
\setlength{\tabcolsep}{15pt}
\begin{tabular}{@{}l|l@{}}
\begin{cfa}
for ( node & it = first( list ); &it @&& !(it.v == 3)@; &it = &next( it ) ) ...
for ( node & it = last( list ); &it @&& !(it.v == 1)@; &it = &prev( it ) ) ...
for ( node & it = iter( list ); advance( it ) @&& !(it.v == 3)@; ) ...
for ( node & it = iter( list ); recede( it ) @&& !(it.v == 1)@; ) ...
\end{cfa}
&
\begin{cfa}
1, 2,
4, 3, 2,
1, 2,
4, 3, 2,
\end{cfa}
\end{tabular}
\end{cquote}

\begin{comment}
Many languages offer an iterator interface for collections, and a corresponding for-each loop syntax for consuming the items through implicit interface calls.
\CFA does not yet have a general-purpose form of such a feature, though it has a form that addresses some use cases.
This section shows why the incumbent \CFA pattern does not work for linked lists and gives the alternative now offered by the linked-list library.
Chapter 5 [TODO: deal with optimism here] presents a design that satisfies both uses and accommodates even more complex collections.

The current \CFA extensible loop syntax is:
\begin{cfa}
for( elem; end )
for( elem; begin ~ end )
for( elem; begin ~ end ~ step )
\end{cfa}
Many derived forms of @begin ~ end@ exist, but are used for defining numeric ranges, so they are excluded from the linked-list discussion.
These three forms are rely on the iterative trait:
\begin{cfa}
forall( T ) trait Iterate {
        void ?{}( T & t, zero_t );
        int ?<?( T t1, T t2 );
        int ?<=?( T t1, T t2 );
        int ?>?( T t1, T t2 );
        int ?>=?( T t1, T t2 );
        T ?+=?( T & t1, T t2 );
        T ?+=?( T & t, one_t );
        T ?-=?( T & t1, T t2 );
        T ?-=?( T & t, one_t );
}
\end{cfa}
where @zero_t@ and @one_t@ are constructors for the constants 0 and 1.
The simple loops above are abbreviates for:
\begin{cfa}
for( typeof(end) elem = @0@; elem @<@ end; elem @+=@ @1@ )
for( typeof(begin) elem = begin; elem @<@ end; elem @+=@ @1@ )
for( typeof(begin) elem = @0@; elem @<@ end; elem @+=@ @step@ )
\end{cfa}
which use a subset of the trait operations.
The shortened loop works well for iterating a number of times or through an array.
\begin{cfa}
for ( 20 ) // 20 iterations
for ( i: 1 ~= 21 ~ 2 ) // odd numbers
for ( i; n ) total += a[i]; // subscripts
\end{cfa}
which is similar to other languages, like JavaScript.
\begin{cfa}
for ( i in a ) total += a[i];
\end{cfa}
Albeit with different mechanisms for expressing the array's length.
It might be possible to take the \CC iterator:
\begin{c++}
for ( list<int>::iterator it=mylist.begin(); it != mylist.end(); ++it )
\end{c++}
and convert it to the \CFA form
\begin{cfa}
for ( it; begin() ~= end() )
\end{cfa}
by having a list operator @<=@ that just looks for equality, and @+=@ that moves to the next node, \etc.

However, the list usage is contrived, because a list does use its data values for relational comparison, only links for equality comparison.
Hence, the focus of a list iterator's stopping condition is fundamentally different.
So, iteration of a linked list via the existing loop syntax is to ask whether this syntax can also do double-duty for iterating values.
That is, to be an analog of JavaScript's @for..of@ syntax:
\begin{cfa}
for ( e of a ) total += e;
\end{cfa}

The \CFA team will likely implement an extension of this functionality that moves the @~@ syntax from being part of the loop, to being a first-class operator (with associated multi-pace operators for the elided derived forms).
With this change, both @begin ~ end@ and @end@ (in context of the latter ``two-place for'' expression) parse as \emph{ranges}, and the loop syntax becomes, simply:
\begin{cfa}
        for( elem; rangeExpr )
\end{cfa}
The expansion and underlying API are under discussion.
TODO: explain pivot from ``is at done?'' to ``has more?''
Advantages of this change include being able to pass ranges to functions, for example, projecting a numerically regular subsequence of array entries, and being able to use the loop syntax to cover more collection types, such as looping over the keys of a hashtable.

When iterating an empty list, the question, ``Is there a further element?'' needs to be posed once, receiving the answer, ``no.''
When iterating an $n$-item list, the same question gets $n$ ``yes'' answers (one for each element), plus one ``no'' answer, once there are no more elements; the question is posed $n+1$ times.

When iterating an empty list, the question, ``What is the value of the current element?'' is never posed, nor is the command, ``Move to the next element,'' issued.  When iterating an $n$-item list, each happens $n$ times.

So, asking about the existence of an element happens once more than retrieving an element's value and advancing the position.

Many iteration APIs deal with this fact by splitting these steps across different functions, and relying on the user's knowledge of iterator state to know when to call each.  In Java, the function @hasNext@ should be called $n+1$ times and @next@ should be called $n$ times (doing the double duty of advancing the iteration and returning a value).  In \CC, the jobs are split among the three actions, @it != end@, @it++@ and @*it@, the latter two being called one time more than the first.

TODO: deal with simultaneous axes: @DLINK_VIA@ just works

TODO: deal with spontaneous simultaneity, like a single-axis req, put into an array: which ``axis'' is @&req++@ navigating: array-adjacency vs link dereference.  It should sick according to how you got it in the first place: navigating dlist(req, req.pri) vs navigating array(req, 42).  (prob. future work)
\end{comment}


\section[C++ Lists]{\CC Lists}

It is worth addressing two API issues in \CC lists avoided in \CFA.
First, \CC lists require two steps to remove a node versus one in \CFA.
\begin{cquote}
\begin{tabular}{@{}ll@{}}
\multicolumn{1}{c}{\CC} & \multicolumn{1}{c}{\CFA} \\
\begin{c++}
list<node> li;
node n = li.first();  // assignment could raise exception
li.pop_front();
\end{c++}
&
\begin{cfa}
dlist(node) list;
node n = remove_first( list );

\end{cfa}
\end{tabular}
\end{cquote}
The argument for two steps is exception safety: returning an unknown T by value/move might throw an exception from T's copy/move constructor.
Hence, to be \emph{exception safe}, all internal list operations must complete before the copy/move so the list is consistent should the return fail.
This coding style can result in contrived code, but is usually possible;
however, it requires the container designer to anticipate the potential throw.
(Note, this anticipation issue is pervasive in exception systems, not just with containers.)
The solution moves the coding complexity from the container designer to the programer~\cite[ch~10, part 3]{Sutter99}.
First, obtain the node, which might fail, but the container is unmodified.
Second, remove the node, which modifies the container without the possibly of an exception.
This movement of responsibility increases the cognitive effort for programmers.
Unfortunately, this \emph{single-responsibility principle}, \ie preferring separate operations, is often repeated as a necessary requirement rather an an optional one.
Separate operations should always be available, but their composition should also be available.
Interestingly, this issue does not apply to intrusive lists, because the node data is never copied/moved in or out of a list;
only the link fields are accessed in list operations.

Second, \VRef[Figure]{f:CCvsCFAListIssues} shows an example where a \CC list operation is $O(N$) rather than $O(1)$ in \CFA.
This issue is inherent to wrapped (non-intrusive) lists.
Specifically, to remove a node requires access to the links that materialize its membership.
In a wrapped list, there is no access from node to links, and for abstract reasons, no direct pointers to wrapped nodes, so the links must be found indirectly by navigating the list.
The \CC iterator is the abstraction to navigate wrapped links.
So an iterator is needed, not because it offers go-next, but for managing the list membership.
Note, attempting to keep an array of iterators to each node requires high-complexity to ensure the list and array are harmonized.

\begin{figure}
\begin{tabular}{@{}ll@{}}
\multicolumn{1}{c}{\CC} & \multicolumn{1}{c}{\CFA} \\
\begin{c++}
list<node *> list;
node n1 = { 1 }, n2 = { 2 }, n3 = { 3 }, n4 = { 4 };
list.push_back( &n1 );  list.push_back( &n2 );
list.push_back( &n3 );  list.push_back( &n4 );
list<node *>::iterator it;
for ( it = list.begin(); it != list.end(); it ++ )
        if ( *it == &n3 ) { dl.erase( it ); break; }
\end{c++}
&
\begin{cfa}
dlist(node) list;
node n1 = { 1 }, n2 = { 2 }, n3 = { 3 }, n4 = { 4 };
insert( list, n1, n2, n3, n4 );



remove( list, n3 );
\end{cfa}
\end{tabular}
\caption{\CC \vs \CFA List Issues}
\label{f:CCvsCFAListIssues}
\end{figure}

\begin{comment}
Dave Dice:
There are what I'd call the "dark days" of C++, where the language \& libraries seemed to be getting progressively uglier - requiring more tokens to express something simple, and lots of arcana.
But over time, somehow, they seem to have mostly righted the ship and now I can write C++ code that's fairly terse, like python, by ignoring all the old constructs.
(They carry around the legacy baggage, of course, but seemed to have found a way to evolve away from it).

If you just want to traverse a std::list, then, using modern "for" loops, you never need to see an iterator.
I try hard never to need to write X.begin() or X.end().
(There are situations where I'll expose iterators for my own types, however, to enable modern "for" loops).
If I'm implementing simple linked lists, I'll usually skip std:: collections and do it myself, as it's less grief.
I just don't get that much advantage from std::list.  And my code is certainly not any shorter.
On the other hand, @std::map@, @unordered_map@, @set@, and friends, are terrific, and I can usually still avoid seeing any iterators, which are blight to the eye.
So those are a win and I get to move up an abstraction level, and write terse but easily understood code that still performs well.
(One slight concern here is that all the C++ collection/container code is templated and lives in include files, and not traditional libraries.
So the only way to replace something - say with a better algorithm, or you have a bug in the collections code - is to boil the oceans and recompile everything.
But on the other hand the compiler can specialize to the specific use case, which is often a nice performance win).

And yeah, the method names are pretty terrible.  I think they boxed themselves in early with a set of conventions that didn't age well, and they tried to stick with it and force regularity over the collection types.

I've never seen anything written up about the history, although lots of the cppcon talks make note of the "bad old days" idea and how collection \& container library design evolved.   The issue is certainly recognized.
\end{comment}


\section{Implementation}

\VRef[Figure]{fig:lst-impl-links} continues the running @req@ example, showing the \CFA list library's internal representation.
The @dlink@ structure contains exactly two pointers: @next@ and @prev@, which are opaque.
Even though the user-facing list model is linear, the \CFA library implements all listing as circular.
This choice helps achieve uniform end treatment.
% and \PAB{TODO finish summarizing benefit}.
A link pointer targets a neighbouring @dlink@ structure, rather than a neighbouring @req@.
(Recall, the running example has the user putting a @dlink@ within a @req@.)

\begin{figure}
        \centering
        \includegraphics[width=\textwidth]{lst-impl-links.pdf}
        \caption{
                \CFA list library representations for headed and headless lists.
        }
        \label{fig:lst-impl-links}
\end{figure}

Circular link-pointers (dashed lines) are tagged internally in the pointer to indicate linear endpoints.
Links among neighbour nodes are not tagged.
Iteration reports ``has more elements'' when accessing untagged links, and ``no more elements'' when accessing tagged links.
Hence, the tags are set on the links that a user cannot navigate.

The \CFA library works in headed and headless modes.
In a headed list, the list head (@dlist(req)@) acts as an extra element in the implementation-level circularly-linked list.
The content of a @dlist@ header is a (private) @dlink@, with the @next@ pointer to the first element, and the @prev@ pointer to the last element.
Since the head wraps a @dlink@, as does @req@, and since a link-pointer targets a @dlink@, the resulting cycle is among @dlink@ structures, situated inside of header/node.
An untagged pointer points within a @req@, while a tagged pointer points within a list head.
In a headless list, the circular backing list is only among @dlink@s within @req@s.

No distinction is made between an unlisted node (top left and middle) under a headed model and a singleton list under a headless model.
Both are represented as an item referring to itself, with both tags set.


\section{Assessment}
\label{toc:lst:assess}

This section examines the performance of the discussed list implementations.
The goal is to show the \CFA lists are competitive with other designs, but the different list designs may not have equivalent functionality, so it is impossible to select a winner encompassing both functionality and execution performance.

\subsection{Experiment Design}

\begin{figure}
\noindent
\begin{tabular}{p{1.75in}@{\ }p{4.5in}}
Insert-Remove (IR)
                & The atomic unit of work being measured: one insertion plus one remove (plus all looping/tracking overheads) \\
Use Case 
                & Pattern of add-remove calls. \\
-- Movement & \\
        \quad $\ni$ stack
                & Inserts and removes happen at the same end. \\
        \quad $\ni$ queue
                & Inserts and removes happen at opposite ends.  \\
-- Polarity
                & Which of the two orientations in which the movement happens. \\
        \quad $\ni$ insert-first
                & All inserts at front; stack removes at front; queue removes at back. \\
        \quad $\ni$ insert-last
                & All inserts at back; stack removes at back; queue removes at front. \\
-- Accessor
                & How an insertion position, or removal element, is specified.  The same position/element is picked either way. \\
        \quad $\ni$ all head
                & inserts and removes both through the head \\
        \quad $\ni$ insert element 
                & insert by element and remove through the head \\
        \quad $\ni$ remove element
                & insert through head and remove by element\\
Physical Context & \\
-- Size (number) &  Number of nodes being linked.  Unless specified, equals the \emph{length} of the program's sole list.  \emph{Width}, rarely used, is the number of lists. \\
-- Size Zone
                & Contiguous range of sizes, chosen to avoid known anomalies and to sample a brief plateau.  Each zone buckets four specific sizes.     \\
   \quad $\ni$ small 
                & lists of 4--16 elements \\
   \quad $\ni$ medium 
                & lists of 50--200 elements \\
   \quad $\ni$ (other)
                &   Not used for comparing intrusive frameworks. \\ 
-- machine
                & Computer running the experiment \\
        \quad $\ni$ AMD
                & smaller cache \\
        \quad $\ni$ Intel
                & bigger cache \\
Framework & A particular linked-list implementation (within its host language) \\
$\ni$ \CC       & The @std::list@ type of g++. \\
$\ni$ lq-list   & The @list@ type of LQ from glibc of gcc. \\
$\ni$ lq-tailq  & The @tailq@ type of the same. \\
$\ni$ \uCpp     & \uCpp's @uSequence@ \\
$\ni$ \CFA      & \CFA's @dlist@ \\
Explanation being 
                & How independent explanatory variable X is analyzed \\
-- Marginalized
                & Left alone, allowed to vary, yielding a more absolute measure.  Shows the effect that X causes.  If all explanations are marginalized, then absolute times are available and a relative time has a peer group that is the entire population.  \\
-- Conditioned
                & Held constant, yielding a more relative measure.  Hides the effect that X causes.  Conditioning on X creates more, smaller relative-measure peer groups, by isolating each X-domain value.  Resulting interpretation is, ``Assuming no change in X.'' \\
\end{tabular}
\caption{
        Glossary of terms used in the list performance evaluation.
}
\label{f:ListPerfGlossary}
\end{figure}


This section explains how the experiment is built.
Many of the parts following define terminology concerning tuning knobs.
\VRef[Figure]{f:ListPerfGlossary} provides a consolidated refence.


\subsubsection{Add-Remove Performance}
\label{s:AddRemovePerformance}

The fundamental job of a linked-list library is to manage the links that connect nodes.
Any link management is an action that causes pair(s) of elements to become, or cease to be, adjacent in the list.
Thus, adding and removing an element are the sole primitive actions.

Repeated adding and removing is necessary to measure timing because these operations can be as short as a dozen instructions.
These instruction sequences may have cases that proceed (in a modern, deep pipeline) without a stall.

This experiment takes the position that:
\begin{itemize}[leftmargin=*]
        \item The total time to add and remove is relevant, as opposed to having one time for adding and a separate time for removing.
                  Adds without removes quickly fill memory;
                  removing without adding is impossible.
        \item A relevant breakdown ``by operation'' is, rather, the usage pattern of the add/remove calls.
        A example pattern choice is adding and removing at the same end, making a stack, or opposite ends, for a queue.
        Another is pushing on the front by calling @insert_first(lst, e)@ \vs @insert(e, old_first_elm)@; this aspect provides the test's API coverage.
        \VRef[Section]{s:UseCases} gives the full breakdown.
        \item Speed differences caused by the host machine's memory hierarchy need to be identified and explained,
                  but do not represent advantages of one framework over another.
\end{itemize}

The experiment used to measure insert/remove cost measures the mean duration of a sequence of additions and removals.
The distribution of speeds experienced by an individual add-remove pair (tail latency) is not discussed.
Space efficiency is shown only indirectly, by way of caches' impact on speed.
The experiment is sensitive enough to show:
\begin{itemize}
        \item intrusive lists performing (majorly) differently than wrapped lists,
        \item a space of (lesser) performance differences among the intrusive lists.
\end{itemize}

In all cases, the quantity discussed is the duration of one insert-remove (IR).
An IR is the time taken to do one innermost insertion-loop iteration, one innermost removal-loop iteration, and its share of all overheads, ammortized.

Lower IR duration is better.
This experiment typically does an IR in 1--10 ns.
The short end of this range has durations of single-digit clock-cycle counts.
Therefore, the situations that achieve the best times are saturating the instruction pipeline successfully.

Often, an IR duration value needs to be considered relatively.
For example, \VRef[Section]{toc:sweet-sore} asks whether one linked list implementation is more sensitive than another to changing which computer runs the test.
A finding might be that a machine change slows implementation A by 10\% and B by 20\%.
This finding is not saying that A is faster than B (on either machine).
The finding could stand if B started 10\% faster and the machine change levelled them off, if B started slower and got worse, or in myriad other cases.
The finding asserts that such distinctions are not what's immediately relevant.
The arithmetic that produces the 10\% and 20\% answers is removing the information about which one starts, or ends up, faster.
Each implementation's to-machine duration is stated relatively to \emph{the same implementation's} from-machine duration.
The resulting measure is still about a duration.
The framework with the lower from-machine-relative duration handles the change better.


\subsubsection{Test Program}
\label{s:TetProgram}

The experiment driver defines a (intrusive) node type:
\begin{cfa}
struct Node {
        int i, j, k;  // fields
        // possible intrusive links
};
\end{cfa}
and considers the speed of building and tearing down a list of $n$ instances of it.
% A number of experimental rounds per clock check is precalculated to be appropriate to the value of $n$.
\begin{cfa}
// simplified harness: CFA implementation,
// stack movement, insert-first polarity, head-mediated access
size_t totalOpsDone = 0;
dlist( node_t ) lst;
node_t nodes[ n ];                                              $\C{// preallocated list storage}$
startTimer();
while ( CONTINUE ) {                                    $\C{// \(\approx\) 20 second duration}$
        for ( i; n ) insert_first( lst, nodes[i] );  $\C{// build up}$
        for ( i; n ) remove_first( lst );       $\C{// tear down}$
        totalOpsDone += n;
}
stopTimer();
reportedDuration = getTimerDuration() / totalOpsDone; // throughput per insert/remove operation
\end{cfa}
To reduce administrative overhead, the $n$ nodes for each experiment list are preallocated in an array (on the stack), which removes dynamic allocations for this storage.
These nodes contain an intrusive pointer for intrusive lists, or a pointer to it is stored in a dynamically-allocated internal-node for a wrapper list.
Copying the node for wrapped lists skews the results with administration costs.
The list insertion/removal operations are repeated for a typical 20+ second duration.
After each round, a counter is incremented by $n$ (for throughput).
Time is measured outside the loop because a large $n$ can overrun the time duration before the @CONTINUE@ flag is tested.
Hence, there is minimum of one outer (@CONTINUE@) loop iteration for large lists.
The loop duration is divided by the counter and this throughput is reported.
In a scatter-plot, each dot is one throughput, which means insert + remove + harness overhead.
The harness overhead is constant when comparing linked-list frameworks and is kept as small as possible.
% The remainder of the setup section discusses the choices that affected the harness overhead.

To test list operations, the experiment performs the inserts/removes in different patterns, \eg insert and remove from front, insert from front and remove from back, random insert and remove, \etc.
Unfortunately, the @std::list@ does \emph{not} support direct insert/remove from a node without an iterator, \ie no @erase( node )@, even though the list is doubly-linked.
To eliminate the iterator, a trick is used for random insertions without replacement, which takes advantage of the array nature of the nodes.
The @i@ fields in each node are initialized from @0..n-1@.
These @i@ values are then shuffled in the nodes, and the @i@ value is used to represent an indirection to that node for insertion.
Hence, the nodes are inserted in random order and removed in the same random order.
$\label{p:Shuffle}$
\begin{cfa}
        for ( i; n ) @nodes[i].i = i@;          $\C[3.25in]{// indirection}$
        shuffle( nodes, n );                            $\C{// random shuffle indirects within nodes}$

        while ( CONTINUE ) {
                for ( i; n ) {
                        node_t & temp = nodes[ nodes[i].i ]; $\C{// select random node in array}$
                        @temp.j = 0;@                           $\C{// only touch random node for wrapped nodes}$
                        insert_first( lst, temp );      $\C{// build up}$
                }
                for ( i; n ) pass( &remove_first( lst ) );      $\C{// tear down}\CRT$
                totalOpsDone += n;
        }
\end{cfa}
Note, insertion is traversing the list of nodes linearly, @node[i]@.
For intrusive lists, the inserted (random) node is always touched because its link fields are read/written for insertion into the list.
Hence, the array of nodes is being accessed both linearly and randomly during the traversal.
For wrapped lists, the wrapped nodes are traversed linearly but the random node is not accessed, only a pointer to it is inserted into the linearly accessed wrapped node.
Hence, the traversal is the same as the non-random traversal above.
To level the experiments, an explicit access to the random node is inserted after the insertion, @temp.j = 0@, for the wrapped experiment.
Furthermore, it is rare to insert/remove nodes and not access them.

% \emph{Interleaving} allows for movements other than pure stack and queue.
% Note that the earlier example of using the iterators' array is still a pure stack: the item selected for @erase(...)@ is always the first.
% Including a less predictable movement is important because real applications that justify doubly linked lists use them.
% Freedom to remove from arbitrary places (and to insert under more relaxed assumptions) is the characteristic function of a doubly linked list.
% A queue with drop-out is an example of such a movement.
% A list implementation can show unrepresentative speed under a simple movement, for example, by enjoying unchallenged ``Is first element?'' branch predictions.

% Interleaving brings ``at middle of list'' cases into a stream of add or remove invocations, which would otherwise be exclusively ``at end''.
% A chosen split, like half middle and half end, populates a boolean array, which is then shuffled.
% These booleans then direct the action to end-\vs-middle.
% 
% \begin{cfa}
% // harness (bookkeeping and shuffling elided): CFA implementation,
% // stack movement, insert-first polarity, interleaved element-based remove access
% dlist( item_t ) lst;
% item_t items[ n ];
% @bool interl[ n ];@  // elided: populate with weighted, shuffled [0,1]
% while ( CONTINUE ) {
%       item_t * iters[ n ];
%       for ( i; n ) {
%               insert_first( items[i] );
%               iters[i] = & items[i];
%       }
%       @item_t ** crsr[ 2 ]@ = { // two cursors into iters
%               & iters[ @0@ ], // at stack-insert-first's removal end
%               & iters[ @n / interl_frac@ ]  // in middle
%       };
%       for ( i; n ) {
%               item *** crsr_use = & crsr[ interl[ i ] ]@;
%               remove( *** crsr_use );  // removing from either middle or end
%               *crsr_use += 1;  // that item is done
%       }
%       assert( crsr[0] == & iters[ @n / interl_frac@ ] ); // through second's start
%       assert( crsr[1] == & iters[ @n@ ] );  // did the rest
% }
% \end{cfa}
% 
% By using the pair of cursors, the harness avoids branches, which could incur prediction stall times themselves, or prime a branch in the SUT.
% This harness avoids telling the hardware what the SUT is about to do.


\subsubsection{Use Cases}
\label{s:UseCases}

\begin{figure}
\begin{comment}
\centering
\setlength{\tabcolsep}{8pt}
\begin{tabular}{@{}ll@{}}
\begin{tabular}{@{}c|c|c@{}}
movement & polarity & accessor \\
\hline
\hline
stack &
        \begin{tabular}{@{}l@{}}
        insert-first \\
        \hline
        insert-last
        \end{tabular}
        &
        \begin{tabular}{@{}l@{}}
        insert-head / remove-head \\
        \hline
        insert-list / remove-head \\
        \hline
        insert-head / remove-list
        \end{tabular}
        \\
\hline
queue &
        \begin{tabular}{@{}l@{}}
        insert-first \\
        \hline
        insert-last
        \end{tabular}
        &
        \begin{tabular}{@{}l@{}}
        insert-head / remove-head \\
        \hline
        insert-list / remove-head \\
        \hline
        insert-head / remove-list
        \end{tabular}
\end{tabular}
&
        \setlength{\tabcolsep}{3pt}
        \small
        \begin{tabular}{@{}ll@{}}
        I:      & stack, insert first, all head \\
        II:     & stack, insert first, insert element \\
        III:& stack, insert first, remove element \\
        IV:     & stack, insert last, all head \\
        V:      & stack, insert last, insert element \\
        VI:     & stack, insert last, remove element \\
        VII:& queue, insert first, all head \\
        VIII:& queue, insert first, insert element \\
        IX:     & queue, insert first, remove element \\
        X:      &  queue, insert last, all head \\
        XI:     & queue, insert last, iinsert element \\
        XII:& queue, insert last, remove element \\
        \end{tabular}
\end{tabular}
\end{comment}
\setlength{\tabcolsep}{5pt}
\small
\begin{tabular}{rcccccccccccc}
& I & II        & III & IV & V & VI & VII & VIII & IX & X & XI & XII \\
Movement &
stack & stack & stack & stack & stack & stack &
queue & queue & queue & queue & queue & queue \\
Polarity &
i-first & i-first & i-first & i-last & i-last & i-last &
i-first & i-first & i-first & i-last & i-last & i-last \\
Acessor &
all hd & ins-e & rem-e & all hd & ins-e & rem-e &
all hd & ins-e & rem-e & all hd & ins-e & rem-e
\end{tabular}
\caption{Experiment use cases, numbered.}
\label{f:ExperimentOperations}
\end{figure}

Where \VRef[Figure]{f:ListPerfGlossary} enumerates the specific values, recall the use-case dimensions are:
\begin{description}
        \item[movement ($\times 2$)]
          In these experiments, strict stack and queue patterns are tested.
        \item[polarity ($\times 2$)]
          Obtain one polarity from the other by reversing uses of first/last.
        \item[accessor ($\times 3$)]
          Giving an add/remove location by a list head's first/last, \vs by a preexisting reference to an individual element?
\end{description}

A use case is a specific selection of movement, polarity and accessor.
These experiments run twelve use cases.
When a comparison is showing only what can happen when switching among use cases (as opposed to \eg how stacks are different from queues), the numbering scheme of \VRef[Figure]{f:ExperimentOperations} is used.

With accessor, when an action names its insertion position or removal element, the harness either
\begin{itemize}
\item defers to the list-head's tracking of first/last (``through the head''), or
\item applies its own knowledge of the current pattern, to name a position/element that happens to be first/last (``of known element'').
\end{itemize}

The accessor patterns, at the (\CFA) API level, are:
\begin{description}
  \item[all (through the) head:]  Both inserts and removes happen through the list head.  The list head operations are @insert_first@, @insert_last@, @remove_first@ and @remove_last@. \\
  \item[insert (of known) element] \dots and remove through head:  Inserts use @insert_before(e, first)@ or @insert_after(e, last)@, where @e@ is being inserted and @first@/@last@ are element references known by list-independent means.
  \item[remove (of known) element] \dots and insert through the head:  Removes use @remove(e)@, where @e@ is being removed.  List-independent knowledge establishes that @e@ is first or last, as appropriate.
\end{description}

Comparing all-head with insert-element gives the relative performance of head-mediated \vs element-oriented insertion, because both use the same removal style.
Comparing all-head with remove-element gives the relative performance of head-mediated \vs element-oriented removal, because both use the same insertion style.

\subsubsection{Sizing}


It is true, but perhaps not obvious, that buildind and destroying long lists is slower than building and destroying short lists.
Obviously, indeed, it takes longer to fuse and divide a hundred neighbours than five.
But the key metric in this work, AII, is about a single link--unlink.
So, critically, linking and unlinking a hundred neighbours actually takes \emph{more} than $20\times$ the time for five neighbours.
The main reason is caching; when more neighbours are being manipulated, more memory is being read and written.

But caching success is about more than the amount of memory worked on.
Subtle changes in pattern become butterfly effects.
Aggressive ILP scheduling, which enables short AIR times, is the amplifier.
A data dependency, present in one framework but not another, is critical path in one situation but in not another.
So, duration's response to size is not a steady worsening as size increases.
Rather, each size-independent configuration often responds to size increases with leaps of worsening.
Occasionally a leap is even followed size-run of retrograde response, where a suddenly incurred penalty has a chance to ammortize away.
The frameworks tend to leapfrog over each other, at different points, as size increases.

The analysis treats these behaviours as incidental.
It does not try to characterize various exact-size responses.
Rather, size zones are picked, specific effects inside of a zone are averaged away, and the story at one zone is compared to that at another zone.

\begin{figure}
\centering
  \setlength{\tabcolsep}{0pt}
  \begin{tabular}{p{3.4375in}p{0.125in}p{2.9375in}}
        \subfloat[ ]{\label{f:zoomin-abs-i-swift}
                \includegraphics{plot-list-zoomin-abs-i-swift.pdf}
        } & &
        \subfloat[ ]{\label{f:zoomin-abs-viii-java}
                \includegraphics{plot-list-zoomin-abs-viii-java.pdf}
        }
  \end{tabular}
  \caption{Variety of IR duration \vs list length, at small--medium lengths.  Two example use cases are shown: I, stack movement with head-only access (plot a); VIII, queue movement with element-oriented removal access (plot b); both use cases have insert-first polarity.  One example is run on each machine: UC-I on AMD (ploat a); UC-VIII on Intel (plot b).  Lower duration is better.}
  \label{fig:plot-list-zoomin-abs}
\end{figure}

\VRef[Figure]{fig:plot-list-zoomin-abs} gives two example responses to size. 
The dataset here is a small portion of the overall result and it is premature to attempt conclusions about framework differences from it.
These two examples show, firstly, how differently a pair of individual configurations can behave.
Of more immediate significance, they also have a pattern repeated, in all eight of their size responses.
Note the ``small'' and ``medium'' overlaid boxes, which call out the size zones' definitions.
Outside of an identified box, size response is erratic.
Inside a box, size response is smooth.
This pattern occurs generally throughout all the experimental results, beyond the two examples here.

To preview, \VRef[Section]{toc:coarse-compre} dismisses ``Large'' sizes (above 150 elements), where the performance story is dominated by the amount of memory touched, inherently, by the choice of intrusive list \vs wrapped, and where one intrusive framework is quite obviously as good as another.
At smaller sizes, comparing one intrusive framework to another makes sense; this comparison occurs in the remaining ``Result'' sections.
Among the remaining ``not Large'' sizes, two further zones, \VRef[Figure]{fig:plot-list-zoomin-abs}'s Small and Medium, are selected as representatives of what can vary when the scale is changed.
These particular ranges were chosen beacause each range tends to have one story repeated across its constituent sizes.
If \CFA's duration increases across Small, then the other frameworks' usually do too.
If \CFA is beating \uCpp at the low end of Large, then it usually is at the high end too.
The leapfrogging tends to happen outside of these two ranges.

A spot of poor performance appears in the general results for \CFA at size 1.
Section \MLB{TODO:xref} explores the phenomenon and concludes that it is an anomaly due to a quirky interaction with the testing rig.
To do so, two it considers size as either length or width.
Length is the number of elements in a list.
Width is a number of these lists being kept, worked upon in round-robin order.
Outside of \MLB{TODO:xref}, size always means length, and width is 1.



\subsubsection{Execution Environment}
\label{s:ExperimentalEnvironment}

The performance experiments are run on:
\begin{description}[leftmargin=*,topsep=3pt,itemsep=2pt,parsep=0pt]
%\item[PC]
%with a 64-bit eight-core AMD FX-8370E, with ``taskset'' pinning to core \#6.  The machine has 16 GB of RAM and 8 MB of last-level cache.
%\item[ARM]
%Gigabyte E252-P31 128-core socket 3.0 GHz, WO memory model
\item[AMD]
Supermicro AS--1125HS--TNR EPYC 9754 128--core socket, hyper-threading $\times$ 2 sockets (512 processing units) 2.25 GHz, TSO memory model, with cache structure 32KB L1i/L1d, 1024KB L2, 16MB L3, where each L3 cache covers 1 NUMA node and 8 cores (16 processors).
\item[Intel]
Supermicro SYS-121H-TNR Xeon Gold 6530 32--core, hyper-threading $\times$ 2 sockets (128 processing units) 2.1 GHz, TSO memory model, with cache structure 32KB L1i/L1d, 20248KB L2, 160MB L3, where each L3 cache covers 2 NUMA node and 32 cores (64 processors).
\end{description}
The experiments are single threaded and pinned to single core to prevent any OS movement, which might cause cache or NUMA effects perturbing the experiment.

The compiler is gcc/g++-14.2.0 running on the Linux v6.8.0-52-generic OS.
Switching between the default memory allocators @glibc@ and @llheap@ is done with @LD_PRELOAD@.
To prevent eliding certain code patterns, crucial parts of a test are wrapped by the function @pass@
\begin{cfa}
// prevent eliding, cheaper than volatile
static inline void * pass( void * v ) {  __asm__  __volatile__( "" : "+r"(v) );  return v;  }
...
pass( &remove_first( lst ) );                   // wrap call to prevent elision, insert cannot be elided now
\end{cfa}
The call to @pass@ can prevent a small number of compiler optimizations but this cost is the same for all lists.


The main difference in the machines is their cache structure.
The AMD has smaller caches that are shared less, while the Intel shares larger caches among more processors.
This difference, while an interesting tradeoff for highly concurrent use, is rather one-sided for sequential use, such as this experiment's.
The Intel offers a single processor a bigger cache.

\subsubsection{Recap and Master Legend}

There are 12 use cases, which are all combinations of 2 movents, 2 polarities and 3 accessors.
There are 4 pysical contexts, which are all combinations of 2 machines and 2 size (length) zones (and 1 width, of value 1).
Each physical context samples 4 specific sizes.

There are 3.25 frameworks.
This accounting considers how LQ-list supports only the movement--polarity combination "stack, insert first."
So LQ-list fills a quarter of the otherwise-orthogonal space.

Use case, physical context and framework are the explanatory factors.
Taking all combinations of the explanatory factors gives 624 individual configurations:
\[
        \textrm{624 individual configurations} =
        \sum_{\substack{
                \textrm{12 use cases}\\
                \textrm{4 physical contexts}\\
                \textrm{4 specific sizes}\\
                \textrm{3.25 frameworks}
        }}
        \textrm{1 individual configuration}
\]

\begin{figure}
\centering
  \setlength{\tabcolsep}{0pt}
  \includegraphics[trim={0in, 1.75in, 0in, 0in}, clip]{plot-list-legend-rel-i-swift.pdf}
  \begin{tabular}{p{2.75in}p{0.125in}p{3.625in}}
        \subfloat[ ]{\label{f:zoomin-rel-i-swift}
                \includegraphics{plot-list-zoomin-rel-i-swift.pdf}
        } & &
        \subfloat[ ]{\label{f:zoomin-histo-i-swift}
                \includegraphics{plot-list-histo-rel-i-swift.pdf}
        }
  \end{tabular}
  \caption{IR duration, transformed for general anaysis.  The analysis follows the single example setup of \VRef[Figure]{f:zoomin-abs-i-swift}, \ie Use Case I on AMD, where IR is given as absolute duration.  Plot (a) transforms the source dataset by conditioning on specific size.  Plot (b) takes the results from only the identified size zones, discards their specific-size information, and shows the resulting distribution.  Lower duration is better.}
  \label{fig:plot-list-rel}
\end{figure}

32 of these individual configurations, plucked from  \VRef[Figure]{f:zoomin-abs-i-swift}, are the subject of \VRef[Figure]{fig:plot-list-rel}, where they are now transformed into the format used for general analysis.
In \subref*{f:zoomin-rel-i-swift}, each of the 56 data points is an individual configuration; the subset within the two boxes has the 32 of interest.
In \subref*{f:zoomin-histo-i-swift}, the very leftmost histogram (Small, \CFA) summarizes the 4 Small--\CFA individual configurations.
Each remaining framework, at size zone Small, similarly summarizes 4 individual configurations.
This statement is the interpretation of the x-category label, ``Small (/4).''
Each line under the ``/4'' label has 4 individual configurations; so, this group has 16 individual configurations.
The interpretation of ``Medium (/4)'' is similar; it groups the remaining 16 configurations.
When both size zones are pooled together, ``Both (/8)'' results; this group revisits all 32 configurations.

This example's use of 32 individual configurations is in contrast with full-universe comparisons like the forthcoming \VRef[Figure]{fig:plot-list-1ord}, whose coverage further includes all use cases and both machines.

The transformation of \VRef[Figure]{f:zoomin-abs-i-swift} into \VRef[Figure]{f:zoomin-rel-i-swift} conditions on the configuration's specific size.
At a particular size, the average duration is computed, across the three frameworks that work on all use cases: \CFA, \uCpp and LQ-@tailq@.
\VRef[Figure]{fig:plot-list-rel} shows a particular configuration's duration relative to this average.

The effect of conditioning on specific size erases the fact that \VRef[Figure]{fig:plot-list-zoomin-abs} shows, aside from the coarse hops, all frameworks getting smoothly slower as size increases.
This effect is partiularly relevant \emph{within} a size zone, most noticeable as the data lines all going up across the Small box.
Now, with size conditioned, \VRef[Figure]{f:zoomin-rel-i-swift} has the trends inside a zone box being flat.
This flatness gives \subref*{f:histo-rel-i-swift} nicely separated histograms.

Specific size is the only factor conditioned in this view.
This choice was made to keep the relationship between \VRef[Figures]{f:zoomin-abs-i-swift} and \VRef[]{:zoomin-rel-i-swift} perceptible.
By contrast, general comparisons like \VRef[Figure]{fig:plot-list-1ord} condition on more, generally, everyting not presented.
Its physical-factor breakdown conditions on use case and framework, but not on physical factors; its other two breakdowns are defined similarly.

The noteworthy performance hop, in this example, is LQ-@list@, which \VRef[Figures]{f:zoomin-abs-i-swift} has as consistently slow in the Small range, and consistently fast in the Medium range.
Therefore, in \VRef{f:zoomin-histo-i-swift}, its two per-size-zone histograms are far apart, and its cross-size-zone histogram is bimdal.
Hops and distribution contributions, like this one, are common.
They are attention-grabbing curiosities when comparing nearly any pair of individual configurations.
They are the background noise of the all-in inter-configuration comparisons following.
With this one, \VRef[Figure]{fig:plot-list-1ord}'s LQ-@list@ distribution (farthest right) does have a perceptible bump at $1.8\times$, corresponding to the upper mode seen here.
But this UC-I--Intel contribution is only $1/6 = 8/48$ of the configurations summarized there.

Each individual configuration is tested by five trials, giving the error bars of \VRef[Figure]{:zoomin-rel-i-swift} (at min and max).
This trial error is unaffected by the size conditioning.
Though this error is presented only for the narrow slice of the current examples, the amount of it seen here is typical across all the configurations.
With a few exceptions, it is modest; so, the experiment is repeatable.
The data points in \subref{f:zoomin-rel-i-swift} show mean excluding min and max.
This value, alone, is the contribution to the histogram in \subref{f:zoomin-histo-i-swift}.
That is, inter-configuration rollups discard the modest trial-repeatability error.
The girth of a histogram's distribution is entirely the inter-configuration variance, of its configurations' expected performance.

Thus, in the forthcoming comparison plots:
\begin{itemize}
\item
The measure is mean IR among the middle 3 trials out of 5, that occurred for an individual configuration.
\item
The number of individual configurations per histogram is stated as ``/N,'' at a relevant grnaularity.
\item
All reported averages are geometric means and all IR duration axes (verticals) are logarithmic.
\item
Unless indicated otherwise, all explanatory factors appearing on a plot are marginalized, while those not appearing on the plot are conditioned.
\end{itemize}


\subsection{Result: Coarse comparison of styles}

This comparison establishes how an intrusive list performs compared with a wrapped-reference list.
\VRef[Figure]{fig:plot-list-zoomout} presents throughput at various list lengths for a linear and random (shuffled) insert/remove test.
Other kinds of scans were made, but the results are similar in many cases, so it is sufficient to discuss these two scans, representing difference ends of the access spectrum.
In the graphs, all four intrusive lists (lq-list, lq-tailq, upp-upp, cfa-cfa, see end of \VRef{s:Contenders}) are plotted with the same symbol;
sometimes theses symbols clump on top of each other, showing the performance difference among intrusive lists is small in comparison to the wrapped list (std::list).
See~\VRef{s:ComparingIntrusiveImplementations} for details among intrusive lists.

The list lengths start at 10 due to the short insert/remove times of 2--4 ns, for intrusive lists, \vs STL's wrapped-reference list of 15--20 ns.
For very short lists, like 4, the experiment time of 4 $\times$ 2.5 ns and experiment overhead (loops) of 2--4 ns, results in an artificial administrative bump at the start of the graph having nothing to do with the insert/remove times.
As the list size grows, the administrative overhead for intrusive lists quickly disappears.

\begin{figure}
  \centering
  \setlength{\tabcolsep}{0pt}
  \begin{tabular}{p{0.75in}p{2.75in}p{3in}}
  &
  \subfloat[Linear List Nodes, AMD]{\label{f:Linear-swift}
        \hspace*{-0.75in}
        \includegraphics{plot-list-zoomout-noshuf-swift.pdf}
  } % subfigure
  &
  \subfloat[Linear List Nodes, Intel]{\label{f:Linear-java}
        \includegraphics{plot-list-zoomout-noshuf-java.pdf}
  } % subfigure
  \\
  &
  \subfloat[Random List Nodes, AMD]{\label{f:Random-swift}
        \hspace*{-0.75in}
        \includegraphics{plot-list-zoomout-shuf-swift.pdf}
  } % subfigure
  &
  \subfloat[Random List Nodes, Intel]{\label{f:Random-java}
        \includegraphics{plot-list-zoomout-shuf-java.pdf}
  } % subfigure
  \end{tabular}
  \caption{Insert/remove duration \vs list length.
  Lengths go as large possible without error.
  One example use case is shown: I, stack movement, insert-first polarity and head-mediated access. Lower duration is better.}
  \label{fig:plot-list-zoomout}
\end{figure}

The key performance factor between the intrusive and the wrapped-reference lists is the dynamic allocation for the wrapped nodes.
Hence, this experiment is largely measuring the cost of @malloc@/\-@free@ rather than insert/remove, and is sensitive to the layout of memory by the allocator.
For insert/remove of an intrusive list, the cost is manipulating the link fields, which is seen by the relatively similar results for the different intrusive lists.
For insert/remove of a wrapped-reference list, the costs are: dynamically allocating/deallocating a wrapped node, copying a external-node pointer into the wrapped node for insertion, and linking the wrapped node to/from the list;
the allocation dominates these costs.
For example, the experiment was run with both glibc and llheap memory allocators, where llheap performance reduced the cost from 20 to 16 ns, still far from the 2--4 ns for linking an intrusive node.
Hence, there is no way to tease apart the allocation, copying, and linking costs for wrapped lists, as there is no way to preallocate the list nodes without writing a mini-allocator to manage that storage.

In detail, \VRef[Figure]{f:Linear-swift}--\subref*{f:Linear-java} shows linear insertion of all the nodes and then linear removal, both in the same direction.
For intrusive lists, the nodes are adjacent in memory from being preallocated in an array.
For wrapped lists, the wrapped nodes happen to be adjacent because the memory allocator uses bump allocation during the initial phase of allocation.
As a result, these memory layouts result in high spatial and temporal locality for both kinds of lists during the linear array traversal.
With address look-ahead, the hardware does an excellent job of managing the multi-level cache.
Hence, performance is largely constant for both kinds of lists, until L3 cache and NUMA boundaries are crossed for longer lists and the costs increase consistently for both kinds of lists.
For example, on AMD (\VRef[Figure]{f:Linear-swift}), there is one NUMA node but many small L3 caches, so performance slows down quickly as multiple L3 caches come into play, and remains constant at that level, except for some anomalies for very large lists.
On Intel (\VRef[Figure]{f:Linear-java}), there are four NUMA nodes and four slowdown steps as list-length increase.
At each step, the difference between the kinds of lists decreases as the NUMA effect increases.

In detail, \VRef[Figure]{f:Random-swift}--\subref*{f:Random-java} shows random insertion and removal of the nodes.
As for linear, there is the issue of memory allocation for the wrapped list.
As well, the consecutive storage-layout is the same (array and bump allocation).
Hence, the difference is the random linking among nodes, resulting in random accesses, even though the list is traversed linearly, resulting in similar cache events for both kinds of lists.
Both \VRef[Figures]{f:Random-swift}--\subref*{f:Random-java} show the slowdown of random access as the list-length grows resulting from stepping out of caches into main memory and crossing NUMA nodes.
% Insert and remove operations act on both sides of a link.
%Both a next unlisted item to insert (found in the items' array, seen through the shuffling array), and a next listed item to remove (found by traversing list links), introduce a new user-item location.
As for linear, the Intel (\VRef[Figure]{f:Random-java}) graph shows steps from the four NUMA nodes.
Interestingly, after $10^6$ nodes, intrusive lists are slower than wrapped.
I did not have time to track down this anomaly, but I speculate it results from the difference in touching the data in the accessed node, as the data and links are together for intrusive and separated for wrapped.
For the llheap memory-allocator and the two tested architectures, intrusive lists out perform wrapped lists up to size $10^3$ for both linear and random, and performance begins to converge around $10^6$ nodes as architectural issues begin to dominate.
Clearly, memory allocator and hardware architecture plays a large factor in the total cost and the crossover points as list-size increases.
% In an odd scenario where this intuition is incorrect, and where furthermore the program's total use of the memory allocator is sufficiently limited to yield approximately adjacent allocations for successive list insertions, a non-intrusive list may be preferred for lists of approximately the cache's size.

The takeaway from this experiment is that wrapped-list operations are expensive because memory allocation is expense at this fine-grained level of execution.
Hence, when possible, using intrusive links can produce a significant performance gain, even if nodes must be dynamically allocated, because the wrapping allocations are eliminated.
Even when space is a consideration, intrusive links may not use more storage if a node is often linked.
Unfortunately, many programmers are unaware of intrusive lists for dynamically-sized data-structures or their tool-set does not provide them.

% Note, linear access may not be realistic unless dynamic size changes may occur;
% if the nodes are known to be adjacent, use an array.

% In a wrapped-reference list, list nodes are allocated separately from the items put into the list.
% Intrusive beats wrapped at the smaller lengths, and when shuffling is avoided, because intrusive avoids dynamic memory allocation for list nodes.

% STL's performance is not affected by element order in memory.
%The field of intrusive lists begins with length-1 operations costing around 10 ns and enjoys a ``sweet spot'' in lengths 10--100 of 5--7-ns operations.
% This much is also unaffected by element order.
% Beyond this point, shuffled-element list performance worsens drastically, losing to STL beyond about half a million elements, and never particularly leveling off.
% In the same range, an unshuffled list sees some degradation, but holds onto a 1--2 $\times$ speedup over STL.

% The apparent intrusive ``sweet spot,'' particularly its better-than-length-1 speed, is not because of list operations truly running faster.
% Rather, the worsening as length decreases reflects the per-operation share of harness overheads incurred at the outer-loop level.
% Disabling the harness's ability to drive interleaving, even though the current scenario is using a ``never work in middle'' interleave, made this rise disappear.
% Subsequent analyses use length-controlled relative performance when comparing intrusive implementations, making this curiosity disappear.

% The remaining big-swing comparison points say more about a computer's memory hierarchy than about linked lists.
% The tests in this chapter are only inserting and removing.
% They are not operating on any user payload data that is being listed.
% The drastic differences at large list lengths reflect differences in link-field storage density and in correlation of link-field order to element order.
% These differences are inherent to the two list models.

% A wrapped-reference list's separate nodes are allocated right beside each other in this experiment, because no other memory allocation action is happening.
% As a result, the interlinked nodes of the STL list are generally referencing their immediate neighbours.
% This pattern occurs regardless of user-item shuffling because this test's ``use'' of the user-items' array is limited to storing element addresses.  
% This experiment, driving an STL list, is simply not touching the memory that holds the user data.
% Because the interlinked nodes, being the only touched memory, are generally adjacent, this case too has high memory locality and stays fast.

% But the comparison of unshuffled intrusive with wrapped-reference gives the performance of these two styles, with their the common impediment of overfilling the cache removed.
% Intrusive consistently beats wrapped-reference by about 20 ns, at all sizes.  
% This difference is appreciable below list length 0.5 M, and enormous below 10 K.


\subsection{Result: Intrusive Winners and Losers}
\label{s:ComparingIntrusiveImplementations}

The preceding result shows the intrusive frameworks have better performance than the wrapped lists for small to medium sized lists.
This analysis covers the experiment position taken in \VRef{s:AddRemovePerformance} for movement, polarity, and accessor.
\VRef[Figure]{f:ExperimentOperations} shows the experiment use cases tested, which results in 12 experiments (I--XII) for comparing intrusive frameworks.
To preclude hardware interference, only list sizes below 150 are examined to differentiate among the intrusive frameworks, 
The data is selected from the start of \VRef[Figures]{f:Linear-swift}--\subref*{f:Linear-java}, but the start of \VRef[Figures]{f:Random-swift}--\subref*{f:Random-java} is largely the same.


\begin{figure}
  \centering
  \includegraphics{plot-list-1ord.pdf} \\
  \small{\textsuperscript{\textdagger} LQ-@list@ is (/48) by its incomplete (25\%) use case coverage.  Its bars are scaled to match.}
  \caption{Histogram of IR durations, decomposed by all first-order effects.
  Each of the three breakdowns divides the entire population of test results into its mutually disjoint constituents. Lower duration is better.
  }
  \label{fig:plot-list-1ord}
\end{figure}

\VRef[Figure]{fig:plot-list-1ord} gives the first-order effects.
The first breakdown, architecture/size-zone (left), showing the overall performance of all 12 experiment on the two different hardware architectures.
The relative experiment duration for each experiment is shown as a bar in each column and the black bar in that column shows the average of all 12 experiments.
By inspection, Intel runs faster than AMD.
As well, the small zone (lists of 4--16 elements) runs faster than the medium zone (lists of 50--200 elements).
The size effect is more pronounced on the AMD with its smaller L3 cache than it is on the Intel.
(No NUMA effects for these list sizes.)
Specifically, a 20\% standard deviation exists here, between the means of the four physical-effect categories.
The key takeaway for this comparison is the context it establishes for interpreting the following framework comparisons.
Both the particulars of a machine's cache design, and a list length's effect on the program's cache friendliness, affect insert/remove speed in the manner illlustrated in this breakdown.
That is, if you are running on an unknown machine, at a scale above anomaly-prone individuals, and below where major LLC caching effects take over the general intrusive-list advantage, but with an unknown relationship to the sizing of your fickle low-level caches, you are likely to experience an unpredictable speed impact on the order of 20\%.

A similar situation comes from \VRef[Figure]{fig:plot-list-1ord}'s second comparison, by use case.
Specific interactions do occur, like framework X doing better on stacks than on queues; a selection of these is addressed in \VRef[Figure]{fig:plot-list-2ord} and discussed shortly.
But they are so irrelevant to the issue of picking a winning framework that it is sufficient here to number the use cases opaquely.
Whether a given list framework is suitable for a language's general library succeeds or fails without knowledge of whether your use will have stack or queue movement.
So you face another lottery, with a likely win-loss range of the standard deviation of the individual use cases' means: 9\%.

This context helps interpret \VRef[Figure]{fig:plot-list-1ord}'s final comparison, by framework.
In this result, \CFA runs similarly to \uCpp and LQ-@list@ runs similarly to @tailq@.
The standard deviation of the frameworks' means is 8\%.
Framework choice has, therefore, less impact on your speed than the lottery tickets you already hold.

Now, the LQs do indeed beat the UW languages by 15\%, a fact explored further in \MLB{TODO: xref}.
But so too does use case VIII typically beat use case IV by 38\%.
As does a small size on the Intel typically beat a medium size on the AMD by 66\%.
Framework choice is simply not where you stand to win or lose the most.


\subsection{Result: Sweet and Sore Spots}

\begin{figure}
        \centering
        \includegraphics{plot-list-2ord.pdf}\\

        \small{
        \textsuperscript{\textdagger} LQ-@list@ is absent from Movement and Polarity comparisons because it does not support queue and insert-last, respectively.\\
        \textsuperscript{\textdaggerdbl} LQ-@list@ is (/24) by its incomplete (25\%) use case coverage.  Its bars are scaled to match.\\
        \textsuperscript{*} The full population of 192 individual configurations applies (48 for LQ-@list@), but this analysis summarizes pairs of them, giving each histogram's 96 contributions (24 for LQ-@list@).
        }
        \caption{Histogram of IR durations, illustrating interactions with framework.
        Each distribution shows how its framework reacts to a single other factor being varied across one pair of options.
        Every (binned and mean-contributing) individual data point represents a pair of test setups, one with the criterion set to the option labelled at the top; the other setup uses the bottom option.
        This point's y-axis score is the ratio of these setups' durations.
        The point lands in a bin closer to the label of the option that performs better.
        }
        \label{fig:plot-list-2ord}
\end{figure}  

\VRef[Figure]{fig:plot-list-1ord} stays razor-focused on only first-order effects in order to contextualize a winner/loser framework observation.
But this perspective cannot address questions like, ``Where are \CFA's sore spots?''
Moreover, the shallow threatment of use cases by ordinals said nothing about how stack usage compares with queues'.

\VRef[Figure]{fig:plot-list-2ord} provides such answers.
Its size-zone criterion refines the obvious notion that a small size runs faster than a big size; this issue is by how much.
Indeed, all means favour small and few tails favour medium.
But the various frameworks do no respond to the different sizes and machines uniformly.
On the AMD, \CFA and \uCpp have a modest size sensitivity, LQ-tailq's is moderate amd LQ-list seems unaffected.
On the Intel, \CFA's increases to moderate, while \uCpp is now unaffected, and both LQs have a dramatic response.
The Intel is more sensitive to size than the AMD.

Turning next to movement and polarity, the responses appear more subdued.
Note that LQ-list has no represntation in these comparisons because it only supports stacks that push and pop with the first element.
\CFA is completely stable under movement and polarity changes.
\uCpp and LQ show modest responses favouring queues and insertion at last.

Finally, with accessor, a \CFA sore spot emerges.
Note the pair of two-way comparisons pulled from the three experiment setups used.
First, the all-head/insert-element opposition addresses which insertion style is better---by-head (top) and by-element (bottom).
Then, the all-head/remove-element opposition addresses which removal style is better---by-head (top) and by-element (bottom).
The LQs favour insertion by head and removal by element.
\CFA and \uCpp favour both operations by head.
The strongest effect is \CFA's aversion to removal by element---certainly an opportunity for improvement.


\subsection{\CFA Tiny-Size Anomaly}

The \CFA list occasionally showed a concerning slowdown at length 1.
The issue, seen in \VRef[Figure]{fig:plot-list-short} (top-left corner), has \CFA taking above 10 ns per IR (top-left corner).
It occurs only for the queue movement, only on the AMD machine, and only for the \CFA framework. 

Length-1 performance is an important case.
Lists like those of waiting threads are frequently left empty, with the occasional thread (or few) momentarily joining.
These scenarios need to work.

A cause of the slowdown was never determined.
Speculation is that \CFA's increased data dependency, a result of the tagging scheme, pairs poorly with the aliasing implied by queue movement.
The aliasing, at length 1, is: the head's first element is the head's last element.
With stack movement, one of these names for the first element is reaused for both insert and remove.
While with queue movement, both names are used in alternation.

The breakdowns earlier in the performance assessment vary length only.
That is, they see the story down the leftmost column in a triangle.
The insight for contextualizing this issue was to inspect both length and width.

The issue is seen as practically mitigated by noticing that the difficutly fades away as width increases.
This effect is seen both in \VRef[Figure]{fig:plot-list-short}'s easement across the top triangle rows, and, zoomed farther out, in \VRef[Figure]{fig:plot-list-wide}.

Increasing the width matters to the aliasing hypothesis.
In a narrow experiment, one element's insert and remove happen in rapid succession.
So, the two aliases are exercied closer together, making a data hazard (that lacks ideal hardware treatment) stretch the instruction-pipeline schedule more significantly.
Increasing the width adds harness-induced gaps between the uses of each alias, behind which a potential hazard can hide.

In the practical scenario that judges length-1 performance as relevant, width 1 is contrived.
A thread putting itself on an often-empty waiters' list is not doing so on one such list repeatedly, at least not without taking other situation-iduced pauses.

Thus, the congestion at low width + length comes from the harness using repetition (in order to obtain a measurable time).
It does not reflect the situation that motivates the legitimate desire for good length-1 performance.

There likely is a real hazard, unique to the \CFA framework, when a queue movement is repeated on a tiny list \emph{without other interventing action}.
Doing so is believed to occur only in contrived situations.


\begin{figure}
\centering
  \includegraphics[trim={00in, 5.5in, 0in, 0in}, clip, scale=0.8]{plot-list-short-temp.pdf}
  \caption{Behaviour at very short lengths.}
  \label{fig:plot-list-short}
\end{figure}

\begin{figure}
\centering
  \includegraphics[trim={0.25in, 1in, 0.25in, 1in}, clip, scale=0.5]{plot-list-wide-temp.pdf}
  \caption{Length-1 anomaly resolving at modest width.  Points are for varying widths, at fixed length 1.}
  \label{fig:plot-list-wide}
\end{figure}

\begin{comment}
        These remarks are mostly about 3ord over 2ord.
This analysis does not provide more detail about one framework beating another; it offers different benefits.
These interactions further illustrate the lottery-ticket unpredictability that a linked-list user inevitably faces, by revealing stronger-still performance swings hidden from the first-order view.
They illustrate the difficult signal-to-noise ratio that I had to overcome in preparing this data.
They may serve as a reference guiding future \CFA linked-list work by informing on where to target improvements.
Finally, the findings offer the conclusion that \CFA's list offers more consistent performance across usage scenarios, than the other lists.
\end{comment}

\begin{comment}
Further to the interpretation guidance of \VRef[Figure]{fig:plot-list-2ord}'s caption, a comparison with the construction of \VRef[Figure]{fig:plot-list-1ord} may be helpful.
In the first-order graph, the factors being compared had many options: four, twelve and four.
# XXX Each option contributes its own, seemingly independent, mean and distribution.
# XXX But, in fact, they are not totally independent.
# WRONG: it's not just about binary, you also need a split on a conditioned factor
        I'm trying to get to:
Side by side in earlier style, but they're opposites, so they mirror each other, so you take option B, flip it over, and have option A---I'll just show A
\end{comment}

\begin{comment}


\VRef[Figure]{fig:plot-list-zoomin} shows the sizes below 150 blown up.
% The same scenario as the coarse comparison is used: a stack, with insertions and removals happening at the end called ``first,'' ``head'' or ``front,'' and all changes occurring through a head-provided insert/remove operation.
The error bars show fastest and slowest time seen on five trials, and the central point is the mean of the remaining three trials.
For readability, the points are slightly staggered at a given horizontal value, where the points might otherwise appear on top of each other.
The experiment runs twelve use cases;
the ones chosen for their variety are scenarios I and VIII from the listing of \VRef[Figure]{fig:plot-list-mchn-szz}, and their results appear in the rows.
As in the previous experiment, each hardware architecture appears in a column.
Note that LQ-list does not support queue operations, so this framework is absent from Operation VIII.

At lengths 1 and 2, winner patterns seen at larger sizes generally do not apply.
Indeed, an issue with \CFA giving terrible on queues at length 1 is evident in \VRef[Figure]{f:AbsoluteTime-viii-swift}.
This phenomenon is elaborated in \MLB{TODO: xref}.
For the remainder of this section, these sizes are disregarded.

Even after the very-small anomalies, the selections of operation and machine significantly affect how speed responds to size.
For example, Operation I on the AMD (\VRef[Figure]{f:AbsoluteTime-i-swift}) has \CFA generally winning over LQ, while the opposite is seen by switching either to Operation VIII (\VRef[Figure]{f:AbsoluteTime-viii-swift}) or to the Intel (\VRef[Figure]{f:AbsoluteTime-i-java}).
For another, Operation I has sore spots at lengths in the middle for \uCpp on AMD and LQ-list on Intel, which resolve at larger lengths; yet no such pattern presents with Operation VIII.

In spite of these complex interactions, a couple spots of stability can be analyzed.
In these examples, the two defined Size Zones (4--16 being ``small,'' and above 50 being ``medium,'') covering four specific sizes apiece, each tends to show a simple winner/loser story.
Manual inspection of other such plots (not detailed) showed that this quality is generally upheld.
So these zones are used for basing comparison.

\MLB{Peter, caution beyond here.  I am reconsidering if this first-dismiss-physical approach to comparison is simplest.}

\begin{figure}
  \centering
  \includegraphics{plot-list-mchn-szz.pdf}
  \caption{Histogram of operation durations, decomposed by physical factors.
  Measurements are included from only the sizes in the ``small'' and ``medium'' stable zones.
  This breakdown divides the entire population of test results into four mutually disjoint constituents.
  \MLB{I see that I broke it. But we might be getting rid of it.}
  }
  \label{fig:plot-list-mchn-szz}
\end{figure}

\VRef[Figure]{fig:plot-list-mchn-szz} shows the effects of the physical factors of size zone and machine.
Each of these four histograms shows variation in duration coming from the four specific sizes in a size zone, from combining results of all twelve operations and all four frameworks.
Among the means of the four histograms, there is a standard deviation of 0.9 ns, which is 20\% of the global mean.
This variability is due solely to physical factors.

From the perspective of assessing winning/losing frameworks, these physical effects are noise.
So, subsequent analysis conditions on the phisical effects.
That is, it supposes you are put into an unknown physical situation (that is one of the four being tested), then presents all the ways your outcome could change as a result of non-physical factors, assuming that the physical situation is kept constant.
It does do by presenting results relative to the mean of the physical quadrant (\VRef[fig]{fig:plot-list-mchn-szz} histogram) to which it belogs.
With this adjustment, absolute duration values (in nonsecods) are lost.
In return, the physical quadrants are re-combined, enabling assessment of the non-physical factors.
\end{comment}

\begin{comment}
While preparing experiment results, I first tested on my old office PC, AMD FX-8370E Eight-Core, before switching to the large new server for final testing.
For this experiment, the results flipped in my favour when running on the server.
New CPU architectures are now amazingly good at branch prediction and micro-parallelism in the pipelines.
Specifically, on the PC, my \CFA and companion \uCpp lists are slower than lq-tail and lq-list by 10\% to 20\%.
On the server, \CFA and \uCpp lists are can be fast by up to 100\%.
Overall, LQ-tailq does the best at short lengths but loses out above a dozen elements.
\end{comment}

% \begin{figure}
% \centering
%   \begin{tabular}{c}
%   \includegraphics{plot-list-cmp-intrl-shift.pdf} \\
%   (a) \\
%   \includegraphics{plot-list-cmp-intrl-outcome.pdf} \\
%   (b) \\
%   \end{tabular}
%   \caption{Caption TODO}
%   \label{fig:plot-list-cmp-intrl}
% \end{figure}

\begin{comment}
\subsection{Result: \CFA cost attribution}

This comparison loosely itemizes the reasons that the \CFA implementation runs 15--20\% slower than LQ.
Each reason provides for safer programming.
For each reason, a version of the \CFA list was measured that forgoes its safety and regains some performance.
These potential sacrifices are:
\newcommand{\mandhead}{\emph{mand-head}}
\newcommand{\nolisted}{\emph{no-listed}}
\newcommand{\noiter}{\emph{no-iter}}
\begin{description}
\item[mand(atory)-head] Removing support for headless lists.
  A specific explanation of why headless support causes a slowdown is not offered.
  But it is reasonable for a cost to result from making one piece of code handle multiple cases; the subset of the \CFA list API that applies to headless lists shares its implementation with headed lists.
  In the \mandhead case, disabling the feature in \CFA means using an older version of the implementation, from before headless support was added.
  In the pre-headless library, trying to form a headless list (instructing, ``Insert loose element B after loose element A,'') is a checked runtime error.
  LQ does not support headless lists\footnote{
        Though its documentation does not mention the headless use case, this fact is due to one of its insert-before or insert-after routines being unusable in every list model.
        For \lstinline{tailq}, the API requires a head.
        For \lstinline{list}, this usage causes an ``uncaught'' runtime crash.}.
\item[no-listed] Removing support for the @is_listed@ API query.
  Along with it goes error checking such as ``When inserting an element, it must not already be listed, \ie be referred to from somewhere else.''
  These abilities have a cost because, in order to support them, a listed element that is being removed must be written to, to record its change in state.
  In \CFA's representation, this cost is two pointer writes.
  To disable the feature, these writes, and the error checking that consumes their result, are put behind an @#ifdef@.
  The result is that a removed element sees itself as still having neighbours (though these quasi-neighbours see it differently).
  This state is how LQ leaves a removed element; LQ does not offer an is-listed query.
\item[no-iter(ation)] Removing support for well-terminating iteration.
  The \CFA list uses bit-manipulation tagging on link poiters (rather than \eg null links) to express, ``No more elements this way.''
  This tagging has the cost of submitting a retrieved value to the ALU, and awaiting this operation's completion, before dereferencing a link pointer.
  In some cases, the is-terminating bit is transferred from one link to another, or has a similar influence on a resulting link value; this logic adds register pressure and more data dependency.
  To disable the feature, the @#ifdef@-controlled tag manipulation logic compiles in answers like, ``No, that link is not a terminator,'' ``The dereferenceable pointer is the value you read from memory,'' and ``The terminator-marked value you need to write is the pointer you started with.''
  Without this termination marking, repeated requests for a next valid item will always provide a positive response; when it should be negative, the indicated next element is garbage data at an address unlikely to trigger a memory error.
  LQ has a well-terminating iteration for listed elements.
  In the \noiter case, the slowdown is not inherent; it represents a \CFA optimization opportunity.
\end{description}
\MLB{Ensure benefits are discussed earlier and cross-reference}  % an LQ programmer must know not to ask, ``Who's next?'' about an unlisted element; an LQ programmer cannot write assertions about an item being listed; LQ requiring a head parameter is an opportunity for the user to provide inconsistent data

\begin{figure}
\centering
  \begin{tabular}{c}
  \includegraphics{plot-list-cfa-attrib-swift.pdf} \\
  (a) \\
  \includegraphics{plot-list-cfa-attrib-remelem-swift.pdf} \\
  (b) \\
  \end{tabular}
  \caption{Operation duration ranges for functionality-reduced \CFA list implementations.  (a) has the top level slices. (b) has the next level of slicing within the slower element-based removal operation.}
  \label{fig:plot-list-cfa-attrib}
\end{figure}

\VRef[Figure]{fig:plot-list-cfa-attrib} shows the \CFA list performance with these features, and their combinations, turned on and off.  When a series name is one of the three sacrifices above, the series is showing this sacrifice in isolation.  These further series names give combinations:
\newcommand{\attribFull}{\emph{full}}
\newcommand{\attribParity}{\emph{parity}}
\newcommand{\attribStrip}{\emph{strip}}
\begin{description}
        \item[full] No sacrifices.  Same as measurements presented earlier.
        \item[parity] \mandhead + \nolisted.  Feature parity with LQ.
        \item[strip] \mandhead + \nolisted + \noiter.  All options set to ``faster.''
\end{description}
All list implementations are \CFA, possibly stripped.
The plot uses the same LQ-relative basis as earlier.
So getting to zero means matching LQ's @tailq@.

\VRef[Figure]{fig:plot-list-cfa-attrib}-(a) summarizes the time attribution across the main operating scenarios.
The \attribFull series is repeated from \VRef[Figure]{fig:plot-list-cmp-overall}, part (b), while the series showing feature sacrifices are new.
Going all the way to \attribStrip at least nearly matches LQ in all operating scenarios, beats LQ often, and slightly beats LQ overall.
Except within the accessor splits, both sacrifices contribute improvements individually, \noiter helps more than \attribParity, and the total \attribStrip benefit depends on both contributions.
When the accessor is not element removal, the \attribParity shift appears to be counterproductive, leaving \noiter to deliver most of the benefit.
For element removals, \attribParity is the heavy hitter, with \noiter contributing modestly.

The counterproductive shift outside of element removals is likely due to optimization done in the \attribFull version after implementing headless support, \ie not present in the \mandhead version.
This work streamlined both head-based operations (head-based removal being half the work of the element-insertion test).
This improvement could be ported to a \mandhead-style implementation, which would bring down the \attribParity time in these cases.

More significantly, missing this optimization affects every \attribParity result because they all use head-based inserts or removes for at least half their operations.
It is likely a reason that \attribParity is not delivering as well overall as \noiter.
It even represents plausible further improvements in \attribStrip.

\VRef[Figure]{fig:plot-list-cfa-attrib}-(b) addresses element removal being the overall \CFA slow spot and element removal having a peculiar shape in the (a) analysis.
Here, the \attribParity sacrifice bundle is broken out into its two constituents.
The result is the same regardless of the operation.
All three individual sacrifices contribute noteworthy improvements (\nolisted slightly less).
The fullest improvement requires all of them.

The \noiter feature sacrifice is unpalatable.
But because it is not an inherent slowdown, there may be room to pursue a \noiter-level speed improvement without the \noiter feature sacrifice.
The performance crux for \noiter is the pointer-bit tagging scheme.
Alternative designs that may offer speedup with acceptable consequences include keeping the tag information in a separate field, and (for 64-bit architectures) keeping it in the high-order byte \ie using byte- rather than bit-oriented instructions to access it.
The \noiter speed improvement would bring \CFA to +5\% of LQ overall, and from high twenties to high teens, in the worst case of element removal.

Ultimately, this analysis provides options for a future effort that needs to get the most speed out of the \CFA list.

\end{comment}


\section{Future Work}
\label{toc:lst:futwork}

Not discussed in the chapter is a \CFA type-system issue with Plan-9 @inline@ declarations, implementing the trait @embedded@ to access the contained @dlist@ link-fields.
This trait defines an implicit conversion from derived to base (the safe direction).
Such a conversion exists implicitly for concrete types using the Plan-9 inheritance feature.
However, this implicit conversion is only partially implemented for polymorphism types, such as @dlist@, which prevents the straightforward list interface shown throughout the chapter.

My workaround is the macro @P9_EMBEDDED@ placed before an intrusive node is used to declare a list.
\begin{cfa}
struct node {
        int v;
        inline dlink(node);
};
@P9_EMBEDDED( node, dlink(node) );@
dlist( node ) dlist;
\end{cfa}
The macro creates specialized access functions to explicitly extract the required information for the polymorphic @dlist@ type.
These access functions could have been generated implicitly for each intrusive node by adding another compiler pass.
However, this would have been substantial temporary work, when the correct solution is the compiler fix.
Hence, the macro workaround is only a small temporary inconvenience;
otherwise, all the list API shown in this chapter works.


\begin{comment}
An API author has decided that the intended user experience is:
\begin{itemize}
\item
offer the user an opaque type that abstracts the API's internal state
\item
tell the user to extend this type
\item
provide functions with a ``user's type in, user's type out'' style
\end{itemize}
Fig XXX shows several attempts to provide this experience.
The types in (a) give the setup, achieving the first two points, while the pair of function declarations and calls of (b) are unsuccessful attempts at achieving the third point.
Both functions @f1@ and @f2@ allow calls of the form @f( d )@, but @f1@ has the wrong return type (@Base@) for initializing a @Derived@.
The @f1@ signature fails to meet ``user's type out;'' this signature does not give the \emph{user} a usable type.
On the other hand, the signature @f2@ offers the desired user experience, so the API author proceeds with trying to implement it.

\begin{figure}
\begin{cfa}
#ifdef SHOW_ERRS
#define E(...) __VA_ARGS__
#else
#define E(...)
#endif

// (a)
struct Base { /*...*/ }; // system offers
struct Derived { /*...*/ inline Base; }; // user writes

// (b)
// system offers
Base & f1( Base & );
forall( T ) T & f2( T & );
// user writes
void to_elide1() {
        Derived & d /* = ... */;
        f1( d );
        E(  Derived & d1 = f1( d );  )  // error: return is not Derived
        Derived & d2 = f2( d );

        // (d), user could write
        Base & b = d;
}

// (c), system has
static void helper( Base & );
forall( T ) T & f2( T & param ) {
        E( helper( param );  )  // error: param is not Base
        return param;
}
static void helper( Base & ) {}

#include <list2.hfa>
// (e)
// system offers, has
forall( T | embedded(T, Base, Base) )
        T & f3( T & param ) {
        helper( param`inner ); // ok
        return param;
}
// user writes
struct DerivedRedux { /*...*/ inline Base; };
P9_EMBEDDED( DerivedRedux, Base )
void to_elide2() {
        DerivedRedux & dr /* = ... */;
        DerivedRedux & dr3 = f3( dr );

        // (f)
        // user writes
        Derived & xxx /* = ... */;
        E(  Derived & yyy = f3( xxx );  )  // error: xxx is not embedded
}
\end{cfa}
\end{figure}


The \CFA list examples elide the @P9_EMBEDDED@ annotations that (TODO: xref P9E future work) proposes to obviate.
Thus, these examples illustrate a to-be state, free of what is to be historic clutter.
The elided portions are immaterial to the discussion and the examples work with the annotations provided.
The \CFA test suite (TODO:cite?) includes equivalent demonstrations, with the annotations included.
\begin{cfa}
struct mary {
        float anotherdatum;
        inline dlink(mary);
};
struct fred {
        float adatum;
        inline struct mine { inline dlink(fred); };
        inline struct yours { inline dlink(fred); };
};
\end{cfa}
like in the thesis examples.  You have to say
\begin{cfa}
struct mary {
        float anotherdatum;
        inline dlink(mary);
};
P9_EMBEDDED(mary, dlink(mary))
struct fred {
        float adatum;
        inline struct mine { inline dlink(fred); };
        inline struct yours { inline dlink(fred); };
};
P9_EMBEDDED(fred, fred.mine)
P9_EMBEDDED(fred, fred.yours)
P9_EMBEDDED(fred.mine, dlink(fred))
P9_EMBEDDED(fred.yours, dlink(fred))
\end{cfa}


The function definition in (c) gives this system-implementation attempt.
The system needs to operate on its own data, stored in the @Base@ part of the user's @d@, now called @param@.
Calling @helper@ represents this attempt to look inside.
It fails, because the @f2@ signature does not state that @param@ has any relationship to @Base@;
this signature does not give the \emph{system} a usable type.
The fact that the user's argument can be converted to @Base@ is lost when going through this signature.

Moving forward needs an @f@ signature that conveys the relationship that the argument @d@ has to @Base@.
\CFA conveys type abilities, from caller to callee, by way of traits; so the challenge is to state the right trait member.
As initialization (d) illustrates, the @d@--@Base@ capability is an implicit conversion.
Unfortunately, in present state, \CFA does not have a first-class representation of an implicit conversion, the way operator @?{}@ (which is a value), done with the right overload, is arguably an explicit conversion.
So \CFA cannot directly convey ``@T@ compatible with @Base@'' in a trait.

This work contributes a stand-in for such an ability, tunneled through the present-state trait system, shown in (e).
On the declaration/system side, the trait @embedded@, and its member, @`inner@, convey the ability to recover the @Base@, and thereby call @helper@.
On the user side, the @P9_EMBEDDED@ macro accompanies type definitions that work with @f3@-style declarations.
An option is presemt-state-available to compiler-emit @P9_EMBEDDED@ annotations automatically, upon each occurrence of an `inline` member.
The choice not to is based on conversions in \CFA being a moving target because of separate, ongoing work.

An intended finished state for this area is achieved if \CFA's future efforts with conversions include:
\begin{itemize}
\item
treat conversion as operator(s), \ie values
\item
re-frame the compiler's current Plan-9 ``magic'' as seeking an implicit conversion operator, rather than seeking an @inline@ member
\item
make Plan-9 syntax cause an implementation of implicit conversion to exist (much as @struct@ syntax causes @forall(T)@ compliance to exist)
\end{itemize}
To this end, the contributed @P9_EMBEDDED@ expansion shows how to implement this conversion.


like in tests/list/dlist-insert-remove.
Future work should autogen those @P9_EMBEDDED@ declarations whenever it sees a plan-9 declaration.
The exact scheme chosen should harmonize with general user-defined conversions.

Today's P9 scheme is:  mary gets a function `inner returning this as dlink(mary).
Fred gets four of them in a diamond.
They're defined so that `inner is transitive; i.e. fred has two further ambiguous overloads mapping fred to dlink(fred).
The scheme allows the dlist functions to give the assertion, "we work on any T that gives a `inner to dlink(T)."


TODO: deal with: A doubly linked list is being designed.

TODO: deal with: Link fields are system-managed.
Links in GDB.
\end{comment}