Diff [81e1984bc450631534fe266ecbbd83ed5d17c16c:58a4cdea77230370ce82af37f08a51930a236d31] for / – Cforall

doc/proposals/modules-alvin/proposal.md

-              r81e1984b
+              r58a4cde
 <!--
 I fleshed out some problems with strong module theory after working through some examples and writing some code, and got a better idea of how to actually implement my vision. The cynic in me says that I've simply solved many hard problems by slapping "compile-time reflection" on it, but my formalism shows that works. I'm quite happy with the result - its focus on making it possible to export individual top-level declarations provides a really nice logical interface, and many of its concepts are used in other programming languages, so the strategy seems at least reasonable.
 There are still some aspects that need to be added: initialization order, handling forward declarations of symbols defined outside of modules, handling the full C spec instead of restricting top-level statements, and addressing the additional features that Cforall provides on top of C. In my modules proposal v5 I'll rearrange some of the sections and rewrite some parts in order to make it easier to follow (some sections are outdated, as my ideas changed slightly as I wrote this proposal). This will allow me to better address some of these missing aspects.
+I fleshed out some problems with strong module theory after working through some examples and writing some code, and got a better idea of how to actually implement my vision. The cynic in me says that I've simply solved many hard problems by slapping "compile-time reflection" on it (which is by no means a simple thing to engineer), but it does solve a number of glaring issues with my previous attempts. Additionally, it takes many concepts from other programming languages, so the strategy seems at least reasonable.
+Now, the biggest hole in my proposal is that I do not address the issue of initialization order (I'm kind of putting this one off, because I think I can handle this separately). Additionally, I still need to present "walkthrough examples" and present a formalism.
 Motivation
 …
     Forall polymorphism
 Walkthrough
-    Symbols of a module
-    How importing modules use symbols
 Formalism
-    Layout of the codebase
-    Individual module information
-    Resolving names of exported declarations
-    Providing additional information for importers
-    Resolving names for compilation
 -->
 …
 How do we actually implement this "oracle"? After analyzing the alternatives, option 2 feels the most "natural", despite its inherent complexity.
 . We can perform whole-program analysis to analyze all type-related information, similar to how Rust does it. This allows for maximum expressiveness since this gives us full visibility into the entire program, and can rely on the analyzer to automatically resolve circularly dependent modules (eg. module `A` imports module `B`, which in turn imports module `A`, but in a way that is still resolvable). However, this breaks the principle of separate compilation by accessing the entire program, and raises questions such as "what gets reanalyzed if `A` changes?"
 . We can also extract type information into a separate generated module interface. This aligns closer to the principle of separate compilation, though it still requires special analysis to resolve circularly dependent modules (eg. module `A` imports module `B`, which in turn imports module `A`, but in a way that is still resolvable. In order to avoid a circular import error, this requires only importing the symbols from `B` that `A` needs). A criticism is that this does not really resolve the transitive dependency issue; in a certain sense, it's offloading the problem to a compile-time reflection mechanism. This level of compile-time reflection is also non-trivial, poentially requiring significant re-engineering and validation of an existing C compiler in order to implement. Despite these concerns, this strategy seems to align best with general intuition when analyzing an existing codebase.
+. We can also extract type information into a separate generated module interface. This aligns closer to the principle of separate compilation, though it still requires special analysis to resolve circularly dependent modules (eg. module `A` imports module `B`, which in turn imports module `A`, but in a way that is still resolvable. In order to avoid a circular import error, this requires only importing the symbols from `B` that `A` needs). A criticism is that this does not really resolve the transitive dependency issue; in a certain sense, it's offloading the problem to a compile-time reflection mechanism. This level of compile-time reflection is also non-trivial, poentially requiring significant re-engineering and validation of an existing C compiler in order to implement. Despite these concerns, this strategy seems to align best with general intuitition when analyzing an existing codebase.
 ### C macros are not exportable
 …
 ### Forall polymorphism
 The forall keyword is an addition to Cforall to support polymorphism, with polymorphic functions using vtables and a single implementation. If a module exports a forall statement, the module owns the polymorphic function implementations, while the polymorphic function declarations are exported (if these were declared inline, the definition could be exported, similar to C++20 modules). Polymorphic types are instantiated from the caller's side, so their definitions are exported. This may present problems, but currently I am not familiar enough with Cforall to judge.
+The forall keyword is an addition to Cforall to support polymorphism, with polymorphic functions using vtables and a single implementation. If a module exports a forall statement, the module owns the polymorphic function implementations, while the polymorphic function declarations are exported (if these were declared inline, the definition could be exported, similar to C++20 modules). Polymorphic types are instantiated from the caller's side, so their definitions are exported. This does not present the same issues as those in the "handling unboxed types" section, as non-polymorphic function declarations cannot inadvertently capture these types (thus, they cannot "leak" outside of a module).
 An interesting case is to consider if Cforall could be updated to perform specialization (multiple implementations for a single function) in addition to the single implementation strategy. This would be similar to Rust's `impl` vs `dyn` traits. To support this, the module system would need to be updated, as we would want the multiple implementations to exist within the module that owns the forall statement.
 …
 ## Walkthrough
-A module holds a collection of symbols to be exported. What we're concerned with is how the importing module can use these symbols. In order to answer this, we will analyze:
-* What are the kinds of symbols and what does the importing module see?
-* How does the importing module disambiguate between symbols?
-Our guiding principle behind our modules is that, as much as is possible, **every symbol definition should have full control over who can see it.** This means that you cannot declare a function or struct that is defined in another module unless that module exports it and you import said module (of course, it may be accessible using `extern "C"`). We will see certain cases where types and inline functions break this abstraction somewhat, but we try to limit this "information leakage" as much as we can. A benefit of this is that our inductive proof usually only needs to reason using the previous step, as every symbol is logically isolated from each other.
-### Symbols of a module
-Modules in our modules are either types, functions or variables. While types can be defined in the same line as a variable (eg. `struct {int i;} name = {5};`), we will make the simplifying assumption right now that this does not happen (in the example, both `name` and the anonymous struct would be exported together).
-#### Types
-There are 3 kinds of types: builtins (eg. `int`), user-defined (ie. `struct`) and aliases (ie. `typedef`). We defer discussion on pointers, references and arrays until afterwards.
-Built-ins are provided by the compiler to every module, so we don't need to consider them. We can simplify aliases as a `struct` with one field, which has an implicit field access.
-So `struct` is really the only type we need to concern ourselves with. Based on our guiding principle, if we export a `struct` that has a `struct` field which is not itself, then it should not export any information related to that field's type. The importer will be able to access all of its fields, but the `struct` field is essentially an opaque type (if a module also wants access to that, it needs to import that `struct` too).
-Unfortunately, this isn't technically possible. First, we have unboxed types (boxed types are implemented as a pointer to the actual object). This means we need to know the size and alignment of every field, so we know how large the struct is and the offsets of each field. Second, when a user initializes a variable with a field, they need to be able to write down the type name (eg. `struct Exported e; struct Field f = e.f1;`). So we need to know the size, alignment and name of a field (in the previous example, move/copy constructors may also need to be considered, but in C we simply copy bytes). A similar thing happens when returning types from functions (eg. `struct Unexported foo();`), which we will discuss later.
-How do we obtain this size/alignment/name information? We use compile-time reflection to crawl import modules as needed. Note that this needs to handle circular imports, as it should only fail if we encounter a type name ambiguity (eg. we import module `A` and `B` which both export `struct S`, and we need a `struct S`) or the type has infinite size (eg. `struct A {struct B b;}; struct B {struct A a; int i;};`). This means the number of modules that need to be analyzed in order to determine the size/alignment of a `struct` is only bounded by the size of the codebase, but in practice this should not happen often.
-Pointers and references are boxed values, so size/alignment information of the underlying type is not gathered. However, we still require modules to import the symbol in order to handle name disambiguation. Arrays may be parameterized by an integer whose value must be immediately available. This is key, otherwise we can end up with cases such as `struct S {struct T t[sizeof(struct U)];};`, which may require fixpoint analysis. In our case, we can simply leverage compile-time reflection in the same manner as we do with field structs.
-#### Functions
-Functions have the form `returnType name(parameterType, ...numberOfParameters) {...body}`. In order for importers to use this function, we need to provide the size, alignment and name of any types in its declaration. We use compile-time reflection to resolve the details (see Types section for details).
-If we are exporting an inline function, from the compiler's perspective the function body is also exported. This may also use compile-time reflection in order to resolve the symbols within the function body (which is done within the context of the containing module, not the importing module).
-Cforall introduces a keyword called `forall`, which can be used to create polymorphic functions. At the moment, these functions do not specialize - there is only one instance of this function, and callers need to pass a vtable alongside any polymorphic type parameters, similar to how the `dyn` trait in Rust works. This means that trait information must be provided to the importing module, which unfortunately breaks our guiding principle somewhat. Within a `forall` block we can also define polymorphic types, which can be used as the return value of a polymorphic function. In that case we need size/align/name information, and the first two are currently handled by calling a "layout function" at runtime (this could possibly be moved to happening at compile-time, but isn't at the moment). As such, we need provide the layout function to the importing module, which unfortunately breaks our guiding principle too. So polymorphic functions can be made to work with our system, but they break our guiding principles to some extent.
-#### Variables
-Variables have the form `variableType name = expression;`. We make the simplifying assumption that only one name is defined at a time (ie. no `int a, b, c;`). An importing module needs to provide the size, alignment and name of `variableType` in its declaration to any importing modules. We use compile-time reflection to resolve the details (see Types section for details).
-If the variable is actually a polymorphic type (see Function section for details), I'm actually not sure how this works. The layout function can only be called at runtime, but you need the information in order to allocate the appropriate amount of space in the `.data` section. More analysis is needed here.
-### How importing modules use symbols
-The previous section notes compile-time reflection as the solution to many of our challenges with modules. Here we will explain how symbol names are resolved to the correct modules, allowing us to define how our compile-time reflection crawls through modules in order to determine the information it requires.
-#### Gathering symbols
-First, we scan the top-level declarations of a module, gathering a list of imported modules and top-level symbol names defined within the module.
-```
-// module data/graph/node
-module;
-import edge;
-import ../minheap;
-import stdlib;
-const int maxEdges = 10;
-export struct Node {
-    int id;
-    int value;
-    struct Edge edges[maxEdges];
-    struct MinHeap someField;
-};
-// Shadows imported MinHeap
-struct MinHeap {int capacity; int size; int *data;};
-struct MinHeap initHeap(int capacity) {
-    // Assumes malloc doesn't return error code
-    return {capacity, 0, (int*)malloc(sizeof(int) * capacity)};
+}
-void destroyHeap(struct MinHeap* h) {
-    free(h->data);
-    h.capacity = 0;
-    h.size = 0;
+}
-```
-We first look for the import relative to the current directory - if that fails we look at libraries. So our set of imports here are: `data/graph/edge`, `data/minheap` and `stdlib` (library module).
-The top-level symbol names are: `maxEdges`, `Node`, `MinHeap`, `initHeap` and `destroyHeap`.
-#### Crawling other modules
-Continuing with our example, we do the same top-level analysis with the imported modules.
-If `data/minheap` has `export import minheap/functions;` defined, then it is as if `data/graph/node` has `import ../minheap/functions;` defined. This can keep going - if `data/minheap/functions` has `export import`, it is also added to `data/graph/node`. After all `export import` have been resolved, we can look at the top-level declarations of every imported module in order to determine what symbols are visible to `data/graph/node`.
-Now, we can bind each symbol within `data/graph/node` to the correct module. The details of how multiple symbols are disambiguated are described in the Overload resolution section.
-In addition to name disambiguation, some symbols need additional information in order to be useable by importers. For example, size/alignment information of types, function bodies for inline functions, and trait information for polymorphic functions. This information is obtained by performing the above steps, but on the importing module instead of `data/graph/node`.
-This recursive task raises the problem of circular imports: What if we recurse back to `data/graph/node` (or any module that creates a cycle)? As long as we are analyzing different symbols inside the circularly imported module, this should not pose a problem. This leaves us with handling the problem where we circle back to the same symbol. For size/alignment analysis, coming back to the same type means that said type contains itself, which for our purposes is not resolvable/infinite size. If an inline function calls other inline functions that mutually recurse with itself, we can either produce a forward declaration of the function within the underlying C implementation (Cforall compiles down to C), or make mutual recursion be a regular function call. The first option is ideal, but if this is not supported in the C spec, we can fall back to the second option. For trait information, we could emit a warning, but if a trait includes itself, that can be safely ignored (a trait is a collection of conditions, it contains itself by definition). Since we can handle all of our circular problems, our system is well-defined here.
-#### Overload resolution
-A key aspect about our modules is that imported symbols are used in the same way as they are defined - no namespacing needed (eg. `struct Edge` in the provided example). While this raises the potential for name collisions, we argue that with the right compiler tools and the ability to disambiguate between different modules (eg. `A::a` means "symbol `a` within module `A`"), this can be a reasonable tradeoff (unfortunately, much of the tooling here is out of scope for this proposal).
-The reason behind this decision comes from 2 places: First, if we add namespacing to imports, then when we have an imported function that returns a type defined in another module, we would be forced to write the module name (the alternatives don't fare much better in terms of brevity and readability). Second, a core feature of Cforall is its advanced overloading system (eg. allowing multiple variables with the same name but different types to coexist). Adding namespaces would likely limit our ability to research and take advantage of this feature.
-This means we have both symbols defined within our module and imported symbols participating in overload resolution. This requires extending our existing overload resolution algorithm to handle multiple types with the same name (currently we handle multiple functions and variables with the same name, but not types). This also requires refactoring the overload resolution algorithm to hold the full name of a symbol (symbol name + module name). Finally, if overload resolution favours two options equally, it should favour symbols defined within the given module (eg. `struct MinHeap` in the provided example). Note that this will only happen if the alternative is strictly better, otherwise it is ambiguous.
 ## Formalism
-Taking the Walkthrough section a step further, we will provide a rough sketch of a formal argument that our module system is well-defined.
-We'll first describe the layout of our module system by providing a rough description of the file structure and grammar we are working with. Then we describe what we can grab from each module file separately. By combining this information with those from other modules, we can determine which module's symbol is being referred to in each exported declaration. Note that for some symbols to be properly used by importers, additional information like size/alignment information will be necessary, which we will show is possible to obtain. Finally, with this information, we can resolve every symbol within a function body or expression, thereby completing the compilation process.
-### Layout of the codebase
-In order to provide a formal argument that our module system is sound, we need to first describe the format of the codebase we are trying to analyze.
-The file system is set up so that imports are relative to the current directory, or found in a library. For example, a module file `data/graph.cfa` trying to access `data/graph/node.cfa` would write `import graph/node;`. If such a file doesn't exist, we will look for `graph/node` within the provided libraries (starting from the root directory of each library).
-Module files have `module;` as their first statement. Import statements are written as `import filePath;`, where the file path can be escaped with double-quotes if necessary. Only top-level statements can be exported, which is done by placing `export` at the beginning (eg. `export const int i = 3;`). The available top-level statements are:
-* Types: `struct` and `typedef` statements. Only one `struct` can be defined per top-level statement (eg. no `typedef struct {int i;} MyStruct;`).
-* Functions: Format is `returnType name(parameterType ...numberOfParameters) {...functionBody}`.
-* Variables: Format is `variableType name = initializerExpression;`. Initializer may be omitted. Only one variable can be declared per top-level statement (eg. no `int a, b;`).
-The syntax of function bodies and initializer expressions can mostly remain unrestricted, as compilation is outside of the module system's purview (we provide the symbols and sufficient information on how to use them to importers). Some aspects we need to note are:
-* No user-defined copy/move constructors: In order to handle `func(s.f1)` (where `void func(struct Field);`), we need to be able to create a copy of `struct Field` without knowing its fields (in the example, the importer knows `func` and the type of `s`, but does not need to know the details of `struct Field`). Having user-defined copy/move constructors can be done, but we opt to avoid it here.
-* `::` operator: Sometimes we need to disambiguate which module a symbol belongs to. `struct InBothModules foo();` can either use `struct InBothModules;` from `import a;` or `import b;`. Trying to resolve this by analyzing the function body of `foo()` may be possible, but would likely be very challenging to implement. To resolve this, we can write `struct a::inBothModules foo();` instead.
-### Individual module information
-For every module file, we can collect the import list and the top-level symbols, without needing to consult any other files. The top-level symbols include types, functions and variables.
-Top-level statements, at least the way we have it set up here, avoid any context-sensitive sections (eg. `MyType * a;` can be multiplication or a variable). This means we have no issues parsing all symbols at the top-level (function bodies and initializer expressions are context-sensitive, but we don't need to deal with them here). This means that for each module file, we can grab an import list, a type list, a function list and a (global) variable list, as well as determine which are exported.
-### Resolving names of exported declarations
-Now we wish to resolve every symbol in any module's top-level declaration (this does not include the function bodies or initializer expressions). In order to do this, we first collect a module's full import list, then all of its imported symbols, before finally resolving our symbols.
-In order to determine a module's full import list, we first look at the individual module information of each imported module. We initially look for the imported module relative to the current directory of the module that the import statement is in - if it does not exist, it will look starting at the root directory of any provided libraries (if we can't find the module, we error out). If any imported module has `export import moduleName;` (or some other module name), then we look at those too. If we end up importing any modules we have already imported (or the module we are getting the full import list of), we can ignore those. Since there are a finite number of modules in a codebase (plus any provided libraries) and we don't analyze a module twice, this search will terminate with a full import list.
-To collect all the imported symbols, we take every module in the full import list and we grab all of the top-level statements that have `export` as their first keyword. This gives us a imported type list, a imported function list and a full variable list.
-Now that we have a list of imported symbols as well as the module's own, we can start resolving symbols in the top-level declarations. Since our grammar is not context-sensitive outside of function bodies and initializer expressions, there is no ambiguity determine whether a type or variable is needed. To resolve names, we first check to see if it uses the `::` operator - if so, then we look using the same strategy when looking for imported modules (if the module isn't in the full import list, we error out). Then we look in the module's own top-level symbols to see if we have a type/variable that matches the symbol's name (this means a module's symbols shadow its imported symbols). If we don't find a match, then we look in the list of imported symbols. If the list of imported symbols has more than one match, we error out due to ambiguity (it may be possible to use overload resolution here, but for now we'll prompt the user to use a `::` operator).
-Something to note about this setup is that forward declarations are neither necessary nor allowed, because all visible symbols are known before attempting to resolve names.
-### Providing additional information for importers
-Unfortunately, in order to use some of these top-level symbols, simply resolving the names within top-level declarations (ie. not including function bodies or initializer expressions) is not enough for an importer to be able to use it. For example, if a function returns a `struct`, we need to at least know the size/ alignment of the `struct` in order to use it.
-Type names are found within the definitions of other types, the return and parameters of a function, and the type of a variable. In order to fully specify a type, we must at least know the size/alignment of its fields. To use a function, we also need to know size/alignment of return and parameter types. To use a variable, the size/alignment of its type is not technically required, but to keep its semantics consistent with that of field access, we require it (eg. `struct Unimported x = s.f1; struct Unimported x1 = importedVariable;`).
-For functions and variables, we first resolve the type (for types, we move to the next step). Then we look at the fields of that type and resolve those types (pointers don't need to be resolved because pointers have a defined size/alignment). We keep recursing until we resolve everything or find a cycle (if we have a cycle, we error out), and this terminates because there are a finite number of symbols. Additionally, types may be arrays, which are parameterized by an integer (if we resolve to something that is not an integer, we error out). The C spec requires that this integer's value must be constant and immediately calculable, which means `char padding[64-sizeof(int)]` is fine but not `char padding[64-sizeof(struct U)];` (this functionality can be supported and may be useful for cache-aware programming, but we will not support this for now). This means we can fully resolve everything within a well-defined type, and therefore collect its size/alignment.
-While the importing module doesn't change its behaviour whether a function is inline or not, the compiler must see the function body, which means it must be included in the file sent to the compiler. In order to resolve the inline function body, then from the perspective of the module that contains the inline function, we must collect the full import list, then all of the imported symbols. If any of those imported symbols are inline functions, then we need to keep recursing. If we find a mututally recursive inline function, we would emit a forward declaration (eg. `inline float a();`). Note that the module that owns the inline function must use `extern` (eg. `extern inline float a() {return 5;}`) in order to ensure a definition is emitted. Since there are a finite number of modules, this will terminate. Note that if an imported module contains an inline function, we do not provide the function definitions of its non-inline functions - this means the compiler cannot inadvertently expand the definition of a function it is not meant to have access to.
-Cforall introduces the `forall` keyword, which allows creating polymorphic functions and types. I am not completely familiar with the internal implementation of these (hence it isn't actually a part of this formalism), but I know they use a single implementation, with callers passing in a vtable for each concrete instance of a polymorphic type (similar to Rust's `dyn` trait). This means that we need to provide the traits of each polymorphic type in a polymorphic function in order for an importer to use it. This analysis follows a similar logic to the size/alignment of types, except that we're working to define a trait rather than a type. As such, if a trait mutually includes another trait, we ignore the circular reference. I am unsure if resolving traits requires resolving more than the symbol names of each type - if necessary we use the same technique as size/alignment analysis.
-### Resolving names for compilation
-Now that we have every top-level symbol visible to a module ready to be used, we can proceed to resolve every symbol in each function body or initializer expression. This functionality is actually the domain of the overload resolution system rather than the module system, but the module system adds additional features which need to be handled by the overload resolution system.
-First, name resolution needs to be augmented to also store the containing module name. We also need to support the `::` operator, used when specifying a specific module name. This doesn't change how the overload resolution algorithm would work, but we need the containing module name in order to generate the full symbol name in the generated C code.
-Additionally, we have the fact that the imports' symbols are now available to participate in overload resolution. In this formalism, our module's symbols have priority over the imports' if they are deemed equal by the overload resolver, and we error out if we have to choose between two imported types with the same name. This allows us to handle the 2 special cases that our module system introduces to the overload resolver.

doc/theses/mike_brooks_MMath/background.tex

-              r81e1984b
+              r58a4cde
                 head objects are discussed in \VRef{toc:lst:issue:ident}.
                 In (a), the field \lstinline{req.x} names a list direction;
                 these are discussed in \VRef{s:Axis}.
+                these are discussed in \VRef{toc:lst:issue:simultaneity}.
                 In (b) and (c), the type \lstinline{node} represents a system-internal type,
                 which is \lstinline{std::_List_node} in the GNU implementation.
 …
                 head objects are discussed in \VRef{toc:lst:issue:ident}.
                 In \protect\subref*{f:Intrusive}, the field \lstinline{req.d} names a list direction;
                 these are discussed in \VRef{s:Axis}.
+                these are discussed in \VRef{toc:lst:issue:simultaneity}.
                 In \protect\subref*{f:WrappedRef} and \protect\subref*{f:WrappedValue}, the type \lstinline{node} represents a
                 library-internal type, which is \lstinline{std::_List_node} in the GNU implementation
 …
 In wrapped value, the @req@ is copied, which increases storage usage, but allows independent simultaneous changes;
 however, knowing which of the @req@ object is the \emph{true} object becomes complex.
 \see*{\VRef{s:Axis} for further discussion.}
+\see*{\VRef{toc:lst:issue:simultaneity} for further discussion.}
 The implementation of @LIST_ENTRY@ uses a trick to find the links and the node containing the links.
 …
 \subsection{Axis: Single \vs Multi-Static \vs Dynamic}
 \label{s:Axis}
+\subsection{Simultaneity: Single \vs Multi-Static \vs Dynamic}
+\label{toc:lst:issue:simultaneity}
 \begin{figure}
 …
 \end{figure}
 \newterm{Axis} deals with the question:
+\newterm{Simultaneity} deals with the question:
 In how many different lists can a node be stored, at the same time?
 \VRef[Figure]{fig:lst-issues-multi-static} shows an example that can traverse all requests in priority order (field @pri@) or navigate among requests with the same request value (field @rqr@).
 …
 \end{c++}
 Axis cannot be done with multiple inheritance, because there is no mechanism to either know the order of inheritance fields or name each inheritance.
+Simultaneity cannot be done with multiple inheritance, because there is no mechanism to either know the order of inheritance fields or name each inheritance.
 Instead, a special type is require that contains the link fields and points at the node.
 \begin{cquote}
 …
 \begin{figure}
         \centering
         \includegraphics[width=\textwidth]{lst-issues-ident.pdf}
+        \includegraphics{lst-issues-ident.pdf}
         \caption{
                 Comparison of headed and ad-hoc list identities, for various list lengths.
 …
 \begin{figure}
         \centering
         \includegraphics[width=0.55\textwidth]{lst-issues-end.pdf}
+        \includegraphics{lst-issues-end.pdf}
         \caption{
                 LQ sub-object-level representation of links and ends.
 …
 For UTF-8 string literals, the array elements have type @char@ and are initialized with the characters of the multi-byte character sequences, \eg @u8"\xe1\x90\x87"@ (Canadian syllabics Y-Cree OO).
 For wide string literals prefixed by the letter @L@, the array elements have type @wchar_t@ and are initialized with the wide characters corresponding to the multi-byte character sequence, \eg @L"abc@$\mu$@"@ and are read/printed using @wscanf@/@wprintf@.
+For wide string literals prefixed by the letter @L@, the array elements have type @wchar_t@ and are initialized with the wide characters corresponding to the multi-byte character sequence, \eg @L"abc@$\mu$@"@ and are read/printed using @wsanf@/@wprintf@.
 The value of a wide-character is implementation-defined, usually a UTF-16 character.
 For wide string literals prefixed by the letter @u@ or @U@, the array elements have type @char16_t@ or @char32_t@, respectively, and are initialized with wide characters corresponding to the multi-byte character sequence, \eg @u"abc@$\mu$@"@, @U"abc@$\mu$@"@.

doc/theses/mike_brooks_MMath/list.tex

-              r81e1984b
+              r58a4cde
-\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, \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 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 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}
 …
 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@.
+\VRef[Figure]{fig:lst-features-intro} continues the running @req@ example from \VRef[Figure]{fig:lst-issues-attach} using the \CFA list.
 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.
+The \CFA framework provides generic type @dlink( T, T )@ for the two link fields (front and back).
+A user inserts the links into the @req@ structure via \CFA inline-inheritance from the Plan-9 C dialect~\cite[\S~3.3]{Thompson90new}.
+Inline inheritance is containment, where the inlined field is unnamed but the type's internal fields are hoisted into the containing structure.
+Hence, the field names must be unique, unlike \CC nested types, but the 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.
+The key feature of inlined inheritance is that a pointer to the containing structure is automatically converted to a pointer to any anonymous inline field for assignments and function calls, providing containment inheritance with implicit subtyping.
+Therefore, a reference to a @req@ is implicitly convertible to @dlink@ in assignments and function calls.
+% These links have a nontrivial, user-specified location within the @req@ structure;
+% this convention encapsulates the implied pointer arithmetic safely.
+The links in @dlist@ point at (links) in the containing node, know the offsets of all links (data is abstract), and any field-offset arithmetic or link-value changes are safe and abstract.
 \begin{figure}
 …
 \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 can be on one or more lists simultaneously.
 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 called on @reqs_pri@ implicitly select (disambiguate) the correct @dlink@s, \eg the calls @insert_first(reqs_pri, ...)@ imply, ``here, we are working by priority.''
+Thus, there is a diamond, non-virtual, inheritance from @req@ to @dlink@, with @by_pri@ and @by_rqr@ being the mid-level types.
+Disambiguation occurs in the declarations of the list-head objects: @reqs_pri_global@, @reqs_rqr_42@, @reqs_rqr_17@, and @reqs_rqr_99@.
+The type of the variable @reqs_pri_global@ is @dlist(req, req.by_pri)@, meaning operations called on @reqs_pri_global@ are implicitly disambiguated.
+In the example, the calls @insert_first(reqs_pri_global, ...)@ 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.
 …
 \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-direction list has no contrived name for the link direction 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 direction list sets up a single inheritance with @dlink@, and the default list axis is to itself.
+When operating on a list with several directions 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.
+The \CFA library also supports the common case, of single directionality, more naturally than LQ.
+\VRef[Figure]{fig:lst-features-intro} shows a single-direction list done with no contrived name for the link direction,
+where \VRef[Figure]{f:Intrusive} adds the unnecessary field name, @d@.
+In \CFA, a user doing a single direction (\VRef[Figure]{fig:lst-features-intro}) sets up a simple inheritance with @dlink@, and declares a list head to have the simpler type @dlist( T )@.
+In contrast, (\VRef[Figure]{fig:lst-features-multidir}) sets up a diamond inheritance with @dlink@, and declares a list head to have the more-informed type @dlist( T, DIR )@.
+The directionality issue also has an advanced corner-case that needs treatment.
+When working with multiple directions, calls like @insert_first@ benefit from implicit direction disambiguation;
+however, other calls like @insert_after@ still require explicit disambiguation, \eg the call
+\begin{cfa}
+insert_after(r1, r2);
+\end{cfa}
+does not have enough information to clarify which of a request's simultaneous list directions is intended.
 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 );
+As such, the \CFA compiler gives an ambiguity error for this call.
+To resolve the ambiguity, the list library provides a hook for applying the \CFA language's scoping and priority rules.
+It applies as:
+\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 directions 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.
+This boost applies within the scope of the following statement, but could also be a custom 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 );  ...
+@}@
+void f() @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 ); ...
+@}@
+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 direction.
+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.
+By using a larger scope, a user can put code within that acts as if there is only one list direction.
+This boost is needed only when operating on a list with several directions, using operations that do not take the list head.
+Otherwise, the sole applicable list direction \emph{just works}.
+Unlike \CC templates container-types, the \CFA library works completely within the type system;
+both @dlink@ and @dlist@ are ordinary types.
 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.
+Finally, the library is separately compiled from the usage code, modulo inlining.
+The \CFA library works in headed and headless modes.
+\PAB{TODO: elaborate.}
+Errors in user code are reported only with mention of the library's declarations.
+Finally, the library is separately compiled from the usage code.
+The \CFA library works in headed and headless modes.  TODO: elaborate.
 …
 @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.
+@insert_before@ adds a node before the specified node and returns the added node for cascading.
+\item
+@insert_after@ adds a node after the specified node and returns the added node for cascading.
+\item
+@remove@ removes the specified node from the list (any location) and returns a reference to the node.
 \item
 @iter@ create an iterator for the list.
 …
 @isLast@ 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.
+@pred@ returns a reference to the previous (predecessor, towards first) node before the specified node or @0p@ if the specified node is the first node in the list.
+\item
+@next@ returns a reference to the next (successor, towards last) node after the specified node or @0p@ if the 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.
 …
 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@.
+The end of iteration is denoted by the loop cursor having the null pointer, denoted @0p@ in \CFA.
 \noindent
 …
 \VRef[Figure]{fig:lst-impl-links} continues the running @req@ example, now showing the \CFA list library's internal representation.
 The @dlink@ structure contains exactly two pointers: @next@ and @prev@, which are opaque.
+The @dlink@ structure contains exactly two pointers: @next@ and @prev@, which are opaque to a user.
 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}.
+This choice helps achieve uniform end treatment and 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}
+        \includegraphics{lst-impl-links.pdf}
         \caption{
                 \CFA list library representations for the cases under discussion.
 …
 \end{figure}
 Circular link-pointers (dashed lines) are tagged internally in the pointer to indicate linear endpoints.
+System-added link pointers (dashed lines) are internally tagged to indicate linear endpoints that are the circular pointers.
 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.
+Iteration reports ``has more elements'' when crossing natural links, and ``no more elements'' upon reaching a tagged link.
 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.
+The content of a @dlist@ 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 a @req@ does too, 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.
+The tags are set on the links that a user cannot navigate.
+No distinction is made between an unlisted item 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.
 …
 \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{Add-Remove Performance}
 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.
+The fundamental job of a linked-list library is to manage the links that connect users' items.
+Any link management is an action that causes pair(s) of elements to become, or cease to be, adjacent.
 Thus, adding and removing an element are the sole primitive actions.
 …
 These instruction sequences may have cases that proceed (in a modern, deep pipeline) without a stall.
 This experiment takes the position that:
+This experiment takes the position that
 \begin{itemize}
     \item The total time to add and remove is relevant \vs individual times for add and remove.
           Adds without removes quickly fill memory;
                   removes without adds is meaningless.
     \item A relevant breakdown ``by operation'' is:
+    \item The total time to add and remove is relevant; an attribution of time spent adding vs.\ removing is not.
+          Any use case for which addition speed matters necessarily has removes paired with adds.
+                  For otherwise, the alleged usage would exhaust the amount of work expressable as a main-memory full of nodes within a few seconds.
+    \item A relevant breakdown ``by operation'' is, rather, one that considers the structural context of these requests.
                 \begin{description}
                 \item[movement]
           Is the add/remove applied to a stack, queue, or something else?
+          Is the add/remove order that of a stack, a queue, or something else?
                 \item[polarity]
+                  In which direction does the action apply?
+                  For a queue, do items flow from first to last or last to first?
+                  For a stack, is the first or last end used for adding and removing?
+                  In which direction does the movement's action apply?  For a queue, do items flow from first to last or last to first?  For a stack, is the first-end or the last-end used for adding and removing?
                 \item[accessor]
           Is an add/remove location given by a list head's ``first''/``last'', or by a reference to an individual element?
 …
 \end{itemize}
 The experiment used to measure insert/remove cost measures the mean duration of a sequence of additions and removals.
+This experiment measures the mean duration of a list addition and removal.
 Confidence bounds, on this mean, are discussed.
 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:
+%~MONITOR
+% If able to show cases with CFA doing better, reword.
+The goal is to show the \CFA library performing comparably to other intrusive libraries,
+in an experimental context sensitive enough to show also:
 \begin{itemize}
     \item intrusive lists performing (majorly) differently than wrapped lists,
     \item a space of (minor) performance differences among the intrusive lists.
+    \item intrusive lists performing (majorly) differently than wrapped lists
+    \item a space of (minor) performance differences typical of existing intrusive lists
 \end{itemize}
 …
 \subsubsection{Experiment setup}
+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$.
+The experiment defines a user's datatype and considers
+the speed of building, and tearing down, a list of $n$ instances of the user's type.
+The timings are taken with a fixed-duration method based on checks @clock()@.
+In a typical 5-sec run, the outer looping checks the clock about 200 times.
+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}$
+dlist( item_t ) lst;
+item_t items[ n ];
 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}$
+while ( SHOULD_CONTINUE ) {
+        for ( i; n ) insert_first( lst, items[i] );
+        for ( i; n ) remove_first( lst );
         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.
+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 implementations and keep 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 this additional cost in the harness, a trick is used for random insertions without replacement.
+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, so the nodes are inserted in random order, and hence, removed in th same random order.
+$\label{p:Shuffle}$
+reportedDuration = getTimerDuration() / totalOpsDone;
+\end{cfa}
+One experimental round is, first, a tight loop of inserting $n$ elements into a list, followed by another, to remove these $n$ elements.
+A counter is incremented by $n$ each round.
+When the whole experiment is done, the total elapsed time, divided by final value of the operation counter,
+is reported as the observed mean operation duration.
+In a scatterplot presentation, each dot would be one such reported mean duration.
+So, ``operation'' really means insert + remove + harness overhead.
+The harness overheads are held constant when comparing linked-list implementations.
+The remainder of the setup section discusses the choices that affected the harness overhead.
+An \emph{iterators' array} provides support for element-level operations on non-intrusive lists.
+As elaborated in Section \ref{toc:lst:issue:attach},
+wrapped-attachment lists use a distinct type (at a distinct memory location) to represent ``an item that's in the list.''
+Operations like insert-after and remove-here consume iterators.
+In the STL implementation, an iterator is a pointer to a \lstinline{std::_List_node}.
+For the STL case, the driver obtains an iterator value
+at the time of adding to the list, and stores the iterator in an array, for consumption by subsequent element-oriented operations.
+For intrusive-list cases, the driver stores the user object's address in the iterators' array.
 \begin{c++}
+        for ( i; n ) @nodes[i].i = i@;          $\C{// indirection}$
+        shuffle( nodes, n );                            $\C{// random shuffle indirects within nodes}$
+        while ( CONTINUE ) {
+                for ( i; n ) insert_first( lst, nodes[ @nodes[i].i@ ] ); $\C{// build up}$
+                for ( i; n ) pass( &remove_first( lst ) );      $\C{// tear down}$
+                totalOpsDone += n;
+// further simplified harness (bookkeeping elided): STL implementation,
+// stack movement, insert-first polarity, element-based remove access
+list< item_t * > lst;
+item_t items[ n ];
+while ( SHOULD_CONTINUE ) {
+        @list< item_t * >::iterator iters[ n ];@
+        for ( int i = 0; i < n; i += 1 ) {
+                lst.push_front( & items[i] );
+                @iters[i]@ = lst.begin();
+        }
+        for ( int i = 0; i < n; i += 1 ) {
+                lst.erase( @iters[i]@ );
+        }
+}
 \end{c++}
+This approach works across intrusive and wrapped lists.
+% \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.
+%~MONITOR
+% If running insert-random scenarios, revise the assessment
+A \emph{shuffling array} helps control the memory layout of user items.
+The control required is when choosing a next item to insert.
+The user items are allocated in a contiguous array.
+Without shuffling, the driver's insert phase visits these items in order, producing a list whose adjavency links hop uniform strides.
+With shuffling active, the driver's insert phase visits only the shuffling array in order,
+which applies pseudo-random indirection to the selection of a next-to-insert element from the user-item array.
+The result is a list whose links travel randomly far.
+\begin{cfa}
+// harness (bookkeeping and iterators elided): CFA implementation,
+// stack movement, insert-first polarity, head-mediated access
+dlist( item_t ) lst;
+item_t items[ n ];
+size_t insert_ord[ n ];  // elided: populate with shuffled [0,n)
+while ( SHOULD_CONTINUE ) {
+        for ( i; n ) insert_first( lst, items[ @insert_ord[@ i @]@ ] );
+        for ( i; n ) remove_first( lst );
+}
+\end{cfa}
+\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 ( SHOULD_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.
+These experiments are single threaded.  They run on a 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.
 The comparator linked-list implementations are:
 \begin{description}
+\item[std::list]  The @list@ type of g++.
+\item[lq-list]  The @list@ type of LQ from glibc of gcc.
+\item[lq-list]  The @list@ type of LQ from glibc of GCC-11.
 \item[lq-tailq] The @tailq@ type of the same.
 \item[upp-upp]  \uCpp provided @uSequence@
+\item[upp-upp]  uC++ provided @uSequence@
 \item[cfa-cfa]  \CFA's @dlist@
 \end{description}
-\subsection{Experimental 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 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
-\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.
 \subsubsection{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 are plotted with the same symbol;
+theses symbols clumped on top of each, showing the performance difference among intrusive lists is small in comparison to the wrapped 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.
+This comparison establishes how an intrusive list performs, compared with a wrapped-reference list.
+It also establishes the context within which it is meaningful to compare one intrusive list to another.
+%These goals notwithstanding, the effect of the host machine's memory hierarchy is more significant here than linked-list implementation.
 \begin{figure}
+  \centering
+  \subfloat[Linear List Nodes]{\label{f:Linear}
+    \includegraphics{plot-list-zoomout-noshuf.pdf}
+  } % subfigure
+  \\
+  \subfloat[Shuffled List Nodes]{\label{f:Shuffled}
+    \includegraphics{plot-list-zoomout-shuf.pdf}
+  } % subfigure
+  \caption{Insert/remove duration \vs list length.
+  Lengths go as large possible without error.
+  One example operation is shown: stack movement, insert-first polarity and head-mediated access.}
+\centering
+  \begin{tabular}{c}
+  \includegraphics{plot-list-zoomout-shuf.pdf} \\
+  (a) \\
+  \includegraphics{plot-list-zoomout-noshuf.pdf} \\
+  (b) \\
+  \end{tabular}
+  \caption{Operation duration \vs list length at full spectrum of list lengths.  One example operation is shown: stack movement, insert-first polarity and head-mediated access.  Lengths go as large as completes without error.  Version (a) uses shuffled items, while version (b) links items with their physical neighbours.}
   \label{fig:plot-list-zoomout}
 \end{figure}
+The large difference in performance between intrusive and wrapped-reference lists results from the dynamic allocation for the wrapped nodes.
+In effect, this experiment is largely measuring the cost of malloc/free rather than the insert/remove, and is affected by the layout of memory by the allocator.
+Fundamentally, insert/remove for a doubly linked-list has a basic cost, which is seen by the similar results for the intrusive lists.
+Hence, the costs for a wrapped-reference list are: 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 dynamic allocation dominates these costs.
+For example, the experiment was run with both glibc and llheap memory allocators, where performance from llheap reduced the cost from 20 to 16 ns, which is still far from the 2--4 ns for intrusive lists.
+Unfortunately, there is no way to tease apart the linking and allocation costs for wrapped lists, as there is no way to preallocate the list nodes without writing a mini-allocator to manage the storage.
+Hence, dynamic allocation cost is fundamental for wrapped lists.
+In detail, \VRef[Figure]{f:Linear} shows linear insertion of all the nodes and then linear removal, both in the same direction.
+For intrusive lists, the nodes are adjacent because they are preallocated in an array.
+For wrapped lists, the wrapped nodes are still adjacent because the memory allocator happens to use bump allocation for the small fixed-sized wrapped nodes.
+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 cache and NUMA boundaries are crossed for longer lists and the costs increase consistently for both kinds of lists.
+In detail, \VRef[Figure]{f:Shuffled} shows shuffle insertion of all the nodes and then linear removal, both in the same direction.
+As for linear, there are issues with the wrapped list and memory allocation.
+For intrusive lists, it is possible to link the nodes randomly, so consecutive nodes in memory seldom point at adjacent nodes.
+For wrapped lists, the placement of wrapped nodes is dictated by the memory allocator, and results in memory layout virtually the same as for linear, \ie the wrapped nodes are laid out consecutively in memory, but each wrapped node points at a randomly located external node.
+As seen on \VPageref{p:Shuffle}, the random access reads data from external node, which are located in random order.
+So while the wrapped nodes are accessed linearly, external nodes are touched randomly for both kinds of lists resulting in similar cache events.
+The slowdown of shuffled occurs as the experiment's length grows from last-level cache into main memory.
+% 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.
+\VRef[Figure]{fig:plot-list-zoomout} presents the speed measures at various list lengths.
+STL's wrapped-reference list begins with operations on a length-1 list costing around 30 ns.
+This time grows modetly as list length increases, apart from more drastic worsening at the largest lengths.
+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.
+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.
+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.
+The slowdown of shuffled intrusive occurs as the experiment's length grows from last-level cache, into main memory.
+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.
 Each time a next item is processed, the memory access is a hop to a randomly far address.
+The target is unavailable in the cache and a slowdown results.
+Note, the external-data no-touch assumption is often unrealistic: decisions like,``Should I remove this item?'' need to look at the item.
+Therefore, under realistic assumptions, both intrusive and wrapped-reference lists suffer similar caching issues for very large lists.
+% 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 any more storage if a node is mostly linked.
+Unfortunately, many programmers are unaware of intrusive lists for dynamically-sized data-structures.
+% 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.
+The target is not available in cache and a slowdown results.
+With the unshuffled intrusive list, each link connects to an adjacent location.  So, this case has high memory locality and stays fast.  But the unshuffled assumption is simply not realistic: if you know items are adjacent, you don't need a linked list.
+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 referenceing their immediate neighbours.
+This pattern occurs regardless of user-item suffling 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 user-data no-touch assumption is often unrealistic: decisions like,``Should I remove this item?'' need to look at the item.
+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 nonintrusive list may be preferred for lists of approximately the chache's size.
+Therefore, under clearly typical situational assumptions, both intrusive and wrapped-reference lists will suffer similarly from a large list overfilling the memory cache, experiencing degradation like shuffled intrusive shows here.
+But the comparison of unshuffled intrusive with wrapped-reference gives the peformance 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.
 \section{Result: Comparing intrusive implementations}
+\label{s:ComparingIntrusiveImplementations}
+The preceding result shows that all the intrusive implementations examined have noteworthy performance compared to wrapped lists.
+This analysis picks the list region 10-150 and zooms-in to differentiate among the different intrusive implementations.
+The data is selected from the start of \VRef[Figure]{f:Linear}, but the start of \VRef[Figure]{f:Shuffled} would be largely the same.
+The preceding result shows that intrusive implementations have noteworthy performance differences below 150 nodes.
+This analysis zooms in on this area and identifies the participants.
 \begin{figure}
 \centering
+  \subfloat[Absolute Time]{\label{f:AbsoluteTime}
+  \includegraphics{plot-list-zoomin-abs.pdf}
+  } % subfigure
+  \\
+  \subfloat[Relative Time]{\label{f:RelativeTime}
+  \includegraphics{plot-list-zoomin-rel.pdf}
+  } % subfigure
+  \begin{tabular}{c}
+  \includegraphics{plot-list-zoomin-abs.pdf} \\
+  (a) \\
+  \includegraphics{plot-list-zoomin-rel.pdf} \\
+  (b) \\
+  \end{tabular}
   \caption{Operation duration \vs list length at small-medium lengths.  One example operation is shown: stack movement, insert-first polarity and head-mediated access.  (a) has absolute times.  (b) has times relative to those of LQ-\lstinline{tailq}.}
   \label{fig:plot-list-zoomin}
 \end{figure}
 \VRef[Figure]{fig:plot-list-zoomin} shows the zone from 10--150 blown up, both in absolute and relative time.
 % 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.
+In \VRef{fig:plot-list-zoomin} part (a) shows exactly this zoom-in.
+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 occuring 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.
+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.
+\VRef[Figure]{f:RelativeTime} shows the percentage difference by treating @tailq@ as the control benchmark, and showing the other list results relative to it.
+For readability, the frameworks are slightly staggered in the horizontal, but all trials near a given size were run at the same size.
+For this particular operation, uC++ fares the worst, followed by \CFA, then LQ's @tailq@.
+Its @list@ does the best at smaller lengths but loses its edge above a dozen elements.
+Moving toward being able to consider several scenarios, \VRef{fig:plot-list-zoomin} part (b) shows the same result, adjusted to treat @tailq@ as a benchmark, and expressing all the results relative to it.
 This change does not affect the who-wins statements, it just removes the ``sweet spot'' bend that the earlier discussion dismissed as incidental.
+Runs faster than @tailq@'s are below the zero and slower runs are above;
+@tailq@'s mean is always zero by definition, but its error bars, representing a single scenario's re-run stability, are still meaningful.
+Runs faster than @tailq@'s are below the zero and slower runs are above; @tailq@'s mean is always zero by definition, but its error bars, representing a single scenario's re-run stability, are still meaningful.
 With this bend straightened out, aggregating across lengths is feasible.
 \begin{figure}
 \centering
+  \subfloat[Supersets]{\label{f:Superset}
+  \includegraphics{plot-list-cmp-exout.pdf}
+  } % subfigure
+  \\
+  \subfloat[1st Level Slice]{\label{f:1stLevelSlice}
+  \includegraphics{plot-list-cmp-survey.pdf}
+  } % subfigure
+  \begin{tabular}{c}
+  \includegraphics{plot-list-cmp-exout.pdf} \\
+  (a) \\
+  \includegraphics{plot-list-cmp-survey.pdf} \\
+  (b) \\
+  \end{tabular}
   \caption{Operation duration ranges across operational scenarios.  (a) has the supersets of the running example operation.  (b) has the first-level slices of the full space of operations.}
   \label{fig:plot-list-cmp-overall}
 \end{figure}
 \VRef[Figure]{fig:plot-list-cmp-overall} introduces alternative views of the data.
+\VRef{fig:plot-list-cmp-overall} introduces the resulting format.
 Part (a)'s first column summarizes all the data of \VRef{fig:plot-list-zoomin}-(b).
 Its x-axis label, ``stack/insfirst/allhead,'' names the concrete scenario that has been discussed until now.
 Moving across the columns, the next three each stretch to include more scenarios on each of the operation dimensions, one at a time.
 The second column considers the scenarios $\{\mathrm{stack}\} \times \{\mathrm{insfirst}\} \times \{\mathrm{allhead}, \mathrm{inselem}, \mathrm{remelem}\}$,
 while the third stretches polarity and the fourth stretches accessor.
+while the third stretches polarity and the fourth streches accessor.
 Then next three columns each stretch two scenario dimensions and the last column stretches all three.
 The \CFA bar in the last column is summarizing 840 test-program runs: 14 list lengths, 2 movements, 2 polarities, 3 accessors and 5 repetitions.
 …
 The chosen benchmark of LQ-@tailq@ is not shown in this format because it would be trivial here.
 With iter-scenario differences dominating the bar size, and @tailq@'s mean performance defined to be zero in all scenarios, a @tailq@ bar on this plot would only show @tailq@'s re-run stability, which is of no comparison value.
+With iter-scenario differences dominating the bar size, and @tailq@'s mean performance defined to be zero in all scenarios, a @tailq@ bar on this plot would only show @tailq@'s re-run stabiity, which is of no comparison value.
 The LQ-@list@ implementation does not support all scenarios, only stack movement with insert-first polarity.
 …
 % \end{figure}
 \section{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:
+This comparison loosely itemizes the reasons that the \CFA implementation runs 15--20\% slower than LQ.  Each reason provides for safer programming.  For each reaon, 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}}
 …
 \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.
+  But it is reasonable for a cost to result from making one pieceof 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.
 …
         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.''
+  Along with it goes error checking such as ``When instering 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.
 …
   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.
+  In the \noiter case, the slowdown is not inherent; it represents a \CFA optimization opporunity.
 \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
 …
 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.
+The couterproductive 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.
 …
 \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.
+Here, the \attribParity sacrifice bundle is broken out into its two consituents.
 The result is the same regardless of the operation.
 All three individual sacrifices contribute noteworthy improvements (\nolisted slightly less).
 …
 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.
+Utimately, this analysis provides options for a future effort that needs to get the most speed out of the \CFA list.

doc/theses/mike_brooks_MMath/plots/list-cfa-attrib-remelem.gp

r81e1984b	r58a4cde
32	32	"-30%%" 0.769230769, \
33	33	)
34		set ylabel "Duration (tailq-Relative)" ~~offset -1.0,0~~
	34	set ylabel "Duration (tailq-Relative)"
35	35
36	36	# Draw axis-like line at speedup=0% (y=1.0)

doc/theses/mike_brooks_MMath/plots/list-cfa-attrib.gp

r81e1984b	r58a4cde
25	25	"-30%%" 0.769230769, \
26	26	)
27		set ylabel "Duration (tailq-Relative)" ~~offset -1.0,0~~
	27	set ylabel "Duration (tailq-Relative)"
28	28
29	29	# Draw axis-like line at speedup=0% (y=1.0)

doc/theses/mike_brooks_MMath/plots/list-cmp-exout.gp

r81e1984b	r58a4cde
25	25	"-30%%" 0.769230769, \
26	26	)
27		set ylabel "Duration (tailq-Relative)" ~~offset -1.0,0~~
	27	set ylabel "Duration (tailq-Relative)"
28	28
29	29	# Draw axis-like line at speedup=0% (y=1.0)

doc/theses/mike_brooks_MMath/plots/list-cmp-survey.gp

r81e1984b	r58a4cde
25	25	"-30%%" 0.769230769, \
26	26	)
27		set ylabel "Duration (tailq-Relative)" ~~offset -1.0,0~~
	27	set ylabel "Duration (tailq-Relative)"
28	28
29	29	# Draw axis-like line at speedup=0% (y=1.0)

doc/theses/mike_brooks_MMath/plots/list-zoomin-abs.gp

r81e1984b	r58a4cde
15	15	set xrange [0.75:128];
16	16	set xlabel "List length (item count)" offset 2,0
17		set ylabel "Duration (ns)" ~~offset -1.0,0~~
	17	set ylabel "Duration (ns)"
18	18	set errorbars 2.0
19	19

doc/theses/mike_brooks_MMath/plots/list-zoomin-rel.gp

r81e1984b	r58a4cde
24	24	set xrange [0.75:128];
25	25	set xlabel "List length (item count)" offset 2,0
26		set ylabel "Duration (tailq-Relative)" ~~offset -1.0,0~~
	26	set ylabel "Duration (tailq-Relative)"
27	27	set errorbars 2.0
28	28

doc/theses/mike_brooks_MMath/plots/list-zoomout-noshuf.gp

-              r81e1984b
+              r58a4cde
 set key top left
 set logscale x
+set xrange [10:*]
+#set logscale y
+#set yrange [32:*];
+set logscale y
+set yrange [4:200];
 set xlabel "List length (item count)" offset 2,0
 set ylabel "Duration (ns)"

doc/theses/mike_brooks_MMath/plots/list-zoomout-shuf.gp

-              r81e1984b
+              r58a4cde
 set key top left
 set logscale x
+set xrange [10:*]
+#set logscale y
+#set yrange [32:200]
+set logscale y
+set yrange [4:200];
 set xlabel "List length (item count)" offset 2,0
 set ylabel "Duration (ns)"

doc/theses/mike_brooks_MMath/programs/lst-features-intro.run.cfa

r81e1984b	r58a4cde
20	20	struct req {
21	21	int pri, rqr;
22		~~@inline dlink(req);@~~ // containment inheritance, fields hoisted into structure
	22	inline dlink(req); // containment inheritance, fields hoisted into structure
23	23	};
24	24

doc/theses/mike_brooks_MMath/programs/lst-features-multidir.run.cfa

-              r81e1984b
+              r58a4cde
 dlist(req, req.by_pri) reqs_pri;
+dlist(req, req.by_pri) reqs_pri_global;
 dlist(req, req.by_rqr) reqs_rqr_42;
 dlist(req, req.by_rqr) reqs_rqr_17;
 …
         r99a = {3, 99};
 insert_first(reqs_pri, r17c);
 insert_first(reqs_pri, r99a);
 insert_first(reqs_pri, r17b);
 insert_first(reqs_pri, r42b);
 insert_first(reqs_pri, r17a);
 insert_first(reqs_pri, r42a);
+insert_first(reqs_pri_global, r17c);
+insert_first(reqs_pri_global, r99a);
+insert_first(reqs_pri_global, r17b);
+insert_first(reqs_pri_global, r42b);
+insert_first(reqs_pri_global, r17a);
+insert_first(reqs_pri_global, r42a);
 insert_first(reqs_rqr_42, r42b);
 …
 with(DLINK_VIA(req, req.by_pri)) {
         while( req & cur = iter( reqs_pri ); advance( cur ) )
+        while( req & cur = iter( reqs_pri_global ); advance( cur ) )
                 printf("{%d %d} ", cur.pri, cur.rqr);
         printf("| ");

doc/theses/mike_brooks_MMath/uw-ethesis.bib

r81e1984b	r58a4cde
31	31
32	32	@misc{cxx:raii-abi,
33		~~key = {Itanium},~~
34	33	title = {Itanium C++ ABI},
35	34	howpublished= {\url{https://itanium-cxx-abi.github.io/cxx-abi/abi.html}},

doc/theses/mike_brooks_MMath/uw-ethesis.tex

-              r81e1984b
+              r58a4cde
 \newcommand{\cmark}{\ding{51}}
 \newcommand{\xmark}{\ding{55}}
+\usepackage[labelformat=simple,aboveskip=0pt,farskip=0pt,font=normalsize]{subfig}
 \usepackage{multirow}
-\usepackage[labelformat=simple,aboveskip=0pt,farskip=0pt,font=normalsize]{subfig}
 \renewcommand\thesubfigure{(\alph{subfigure})}
 …
 \newcommand{\uCpp}{$\mu$\CC}
 \newcommand{\PAB}[1]{{\color{magenta}PAB: #1}}
+\newcommand{\PAB}[1]{{\color{red}PAB: #1}}
 \newcommand{\MLB}[1]{{\color{red}MLB: #1}}
 …
 \urlstyle{sf}
-\setcounter{secnumdepth}{4}     % number subsubsection
-\setcounter{tocdepth}{4} % subsubsection in TOC
 %\usepackage[automake,toc,abbreviations]{glossaries-extra} % Exception to the rule of hyperref being the last add-on package
 % If glossaries-extra is not in your LaTeX distribution, get it from CTAN (http://ctan.org/pkg/glossaries-extra),
 …
 \setlength{\evensidemargin}{0.125in} % Adds 1/8 in. to binding side of all
 % even-numbered pages when the "twoside" printing option is selected
 %\setlength{\oddsidemargin}{0.125in} % Adds 1/8 in. to the left of all pages when "oneside" printing is selected, and to the left of all odd-numbered pages when "twoside" printing is selected
 %\setlength{\textwidth}{6.375in} % assuming US letter paper (8.5 in. x 11 in.) and side margins as above
+\setlength{\oddsidemargin}{0.125in} % Adds 1/8 in. to the left of all pages when "oneside" printing is selected, and to the left of all odd-numbered pages when "twoside" printing is selected
+\setlength{\textwidth}{6.375in} % assuming US letter paper (8.5 in. x 11 in.) and side margins as above
 \raggedbottom

libcfa/src/collections/list.hfa

-              r81e1984b
+              r58a4cde
 // Created On       : Wed Apr 22 18:00:00 2020
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Thu Aug  7 10:46:08 2025
 // Update Count     : 75
+// Last Modified On : Thu Apr 24 18:12:59 2025
+// Update Count     : 72
 //
 …
 forall( tE & ) {
         struct dlink{
+                tE * next, * prev;
+                tE * next;
+                tE * prev;
         };
 …
+        }
+        forall( tLinks & = dlink( tE ) ) {
+                struct dlist {
+                        inline dlink( tE );
+                };
+                forall( | embedded( tE, tLinks, dlink( tE ) ) ) {
+                        static inline tE * $get_list_origin_addr( dlist( tE, tLinks ) & list ) {
+                                dlink( tE ) & link_from_null = (*(tE *)0p)`inner;
+                                ptrdiff_t link_offset = (ptrdiff_t)&link_from_null;
+                                size_t origin_addr = ((size_t)&list) - link_offset;
+                                size_t preResult = ORIGIN_TAG_SET( origin_addr );
+                                return (tE *)preResult;
+                        }
+                        static inline void ?{}( dlist( tE, tLinks ) & this ) {
+                                tE * listOrigin = $get_list_origin_addr( this );
+                                ((dlink( tE ) &)this){ listOrigin, listOrigin };
+                        }
+        forall( tLinks & = dlink( tE ) )
+        struct dlist {
+                inline dlink( tE );
+        };
+        forall( tLinks & | embedded( tE, tLinks, dlink( tE ) ) ) {
+                static inline tE * $get_list_origin_addr( dlist( tE, tLinks ) & list ) {
+                        dlink( tE ) & link_from_null = (*(tE *)0p)`inner;
+                        ptrdiff_t link_offset = (ptrdiff_t)&link_from_null;
+                        size_t origin_addr = ((size_t)&list) - link_offset;
+                        size_t preResult = ORIGIN_TAG_SET( origin_addr );
+                        return (tE *)preResult;
+                }
+                static inline void ?{}( dlist( tE, tLinks ) & this ) {
+                        tE * listOrigin = $get_list_origin_addr( this );
+                        ((dlink( tE ) &)this){ listOrigin, listOrigin };
+                }
+        }

Context Navigation

Changes in / [81e1984b:58a4cde]

Legend:

doc/proposals/modules-alvin/proposal.md

doc/theses/mike_brooks_MMath/background.tex

doc/theses/mike_brooks_MMath/list.tex

doc/theses/mike_brooks_MMath/plots/list-cfa-attrib-remelem.gp

doc/theses/mike_brooks_MMath/plots/list-cfa-attrib.gp

doc/theses/mike_brooks_MMath/plots/list-cmp-exout.gp

doc/theses/mike_brooks_MMath/plots/list-cmp-survey.gp

doc/theses/mike_brooks_MMath/plots/list-zoomin-abs.gp

doc/theses/mike_brooks_MMath/plots/list-zoomin-rel.gp

doc/theses/mike_brooks_MMath/plots/list-zoomout-noshuf.gp

doc/theses/mike_brooks_MMath/plots/list-zoomout-shuf.gp

doc/theses/mike_brooks_MMath/programs/lst-features-intro.run.cfa

doc/theses/mike_brooks_MMath/programs/lst-features-multidir.run.cfa

doc/theses/mike_brooks_MMath/uw-ethesis.bib

doc/theses/mike_brooks_MMath/uw-ethesis.tex

libcfa/src/collections/list.hfa

Download in other formats: