Index: doc/theses/mike_brooks_MMath/background.tex =================================================================== --- doc/theses/mike_brooks_MMath/background.tex (revision 7ef4438154228273f1e40137bc17a3cd20e74ce5) +++ doc/theses/mike_brooks_MMath/background.tex (revision 520fa9e26472c80c05dc91004ccb5b6373b697da) @@ -640,8 +640,8 @@ Linked-lists are blocks of storage connected using one or more pointers. -The storage block is logically divided into data (user payload) and links (list pointers), where the links are the only component used by the list structure. +The storage block (node) is logically divided into data (user payload) and links (list pointers), where the links are the only component used by the list structure. Since the data is opaque, list structures are often polymorphic over the data, which is often homogeneous. -Storage linking is used to build data structures, which are a group of nodes, containing data and links, organized in a particular format, with specific operations peculiar to that format, \eg queue, tree, hash table, \etc. +The links organize nodes into a particular format, \eg queue, tree, hash table, \etc, with operations specific to that format. Because a node's existence is independent of the data structure that organizes it, all nodes are manipulated by address not value; hence, all data structure routines take and return pointers to nodes and not the nodes themselves. @@ -651,7 +651,7 @@ \label{toc:lst:issue} -This section introduces the design space for linked lists that target \emph{system programmers}. -Within this restricted target, all design-issue discussions assume the following invariants. -Alternatives to the assumptions are discussed under Future Work (Section~\ref{toc:lst:futwork}). +This thesis focuses on a reduced design space for linked lists that target \emph{system programmers}. +Within this restricted space, all design-issue discussions assume the following invariants; +alternatives to the assumptions are discussed under Future Work (Section~\ref{toc:lst:futwork}). \begin{itemize} \item A doubly-linked list is being designed. @@ -672,10 +672,10 @@ and further libraries are introduced as needed. \begin{enumerate} - \item Linux Queue library\cite{lst:linuxq} (LQ) of @@. + \item Linux Queue library~\cite{lst:linuxq} (LQ) of @@. \item \CC Standard Template Library's (STL)\footnote{The term STL is contentious as some people prefer the term standard library.} @std::list@\cite{lst:stl} \end{enumerate} %A general comparison of libraries' abilities is given under Related Work (Section~\ref{toc:lst:relwork}). For the discussion, assume the fictional type @req@ (request) is the user's payload in examples. -As well, the list library is helping the user manage (organize) requests, \eg a request can be work on the level of handling a network arrival event or scheduling a thread. +As well, the list library is helping the user manage (organize) requests, \eg a request can be work on the level of handling a network arrival-event or scheduling a thread. @@ -684,5 +684,5 @@ Link attachment deals with the question: -Where are the libraries' inter-element link fields stored, in relation to the user's payload data fields? +Where are the libraries' inter-node link-fields stored, in relation to the user's payload data fields? \VRef[Figure]{fig:lst-issues-attach} shows three basic styles. \VRef[Figure]{f:Intrusive} shows the \newterm{intrusive} style, placing the link fields inside the payload structure. @@ -793,8 +793,8 @@ The traversal actually moves from link fields to link fields within a node and sets the node cursor from the pointer within the link fields back to the node. -A further aspect of layout control is allowing the user to explicitly specify link fields controlling attributes and placement within the @req@ object. -LQ allows this ability through the @LIST_ENTRY@ macro;\footnote{It is possible to have multiple named linked fields allowing a node to appear on multiple lists simultaneously.} -supplying the link fields by inheritance makes them implicit and relies on compiler placement, such as the start or end of @req@. -An example of an explicit attribute is cache alignment of the link fields in conjunction with other @req@ fields, improving locality and/or avoiding false sharing. +A further aspect of layout control is allowing the user to explicitly specify link fields controlling placement and attributes within the @req@ object. +LQ allows this ability through the @LIST_ENTRY@ macro\footnote{It is possible to have multiple named linked fields allowing a node to appear on multiple lists simultaneously.}, which can be placed anywhere in the node. +An example of an attribute on the link fields is cache alignment, possibly in conjunction with other @req@ fields, improving locality and/or avoiding false sharing. +Supplying the link fields by inheritance makes them implicit and relies on compiler placement, such as the start or end of @req@, and no explicit attributes. Wrapped reference has no control over the link fields, but the separate data allows some control; wrapped value has no control over data or links. @@ -805,5 +805,5 @@ The same is not true of STL, wrapped reference or value. There, the analogous operations, @iterator::operator++()@, @iterator::operator*()@, and @list::erase(iterator)@, work on a parameter of type @list::iterator@; -There is no mapping from @req &@ to @list::iterator@. %, for linear search. +there is no mapping from @req &@ to @list::iterator@. %, for linear search. The advantage of wrapped is the abstraction of a data item from its list membership(s). @@ -870,10 +870,10 @@ Thus, the intrusive LQ example supports multiple, but statically many, link lists. Note, it is possible to reuse links for different purposes, \eg if a list in linked one way at one time and another way at another time, and these times do not overlap, the two different linkings can use the same link fields. -This feature is used in the \CFA runtime where a thread node may be on a blocked or running list, both never on both simultaneously. +This feature is used in the \CFA runtime, where a thread node may be on a blocked or running list, but never on both simultaneously. Now consider the STL in the wrapped-reference arrangement of Figure~\ref{f:WrappedRef}. Here it is possible to construct the same simultaneity by creating multiple STL lists, each pointing at the appropriate nodes. Each group of intrusive links become the links for each separate STL list. -The upside is the unlimited number of a lists a node can be associated with simultaneously, any number of STL lists can be created dynamically. +The upside is the unlimited number of lists a node can be associated with simultaneously, as any number of STL lists can be created dynamically. The downside is the dynamic allocation of the link nodes and managing multiple lists. Note, it might be possible to wrap the multiple lists in another type to hide this implementation issue. @@ -881,6 +881,6 @@ Now consider the STL in the wrapped-value arrangement of Figure~\ref{f:WrappedValue}. Again, it is possible to construct the same simultaneity by creating multiple STL lists, each copying the appropriate nodes, where the intrusive links become the links for each separate STL list. -The upside is the same as for wrapped-reference arrangement with an unlimited number of a list bindings. -The downside is the dynamic allocation and significant storage usage due to node copying. +The upside is the same as for wrapped-reference arrangement with an unlimited number of list bindings. +The downside is the dynamic allocation, significant storage usage, and cost of copying nodes. As well, it is unclear how node updates work in this scenario, without some notation of ultimately merging node information. @@ -895,5 +895,6 @@ % The example uses @x@; @reqs@ would be a more readily ignored choice. \PAB{wording?} -\uCpp is a concurrent extension of \CC, which provides a basic set of intrusive lists~\cite[appx.~F]{uC++}, where the link fields are defined with the data fields using inheritance. +An alternative system providing intrusive data-structures is \uCpp, a concurrent extension of \CC. +It provides a basic set of intrusive lists~\cite[appx.~F]{uC++}, where the link fields are defined with the data fields using inheritance. \begin{cquote} \setlength{\tabcolsep}{15pt} @@ -960,9 +961,11 @@ \uCpp cheats by using inheritance for the first intrusive links, after which explicit naming of intrusive links is required. Furthermore, these link names must be used in all list operations, including iterating, whereas wrapped reference and value hide the list names in the implicit dynamically-allocated node-structure. -At issue is whether an API for simultaneity can support one list (when several are not wanted) to be \emph{implicit}. +At issue is whether an API for simultaneity can support one \emph{implicit} list, when several are not wanted. \uCpp allows it, LQ does not, and the STL does not have this question. \subsection{User integration: preprocessed vs.\ type-system mediated} + +\PAB{What do you want to say here?} % example of poor error message due to LQ's preprocessed integration @@ -977,12 +980,17 @@ \label{toc:lst:issue:ident} -All examples so far have used distinct user-facing types: -an item found in a list (type @req@, of variables like @r1@), and -a list (type @reql@ or @list@, of variables like @reqs@ or @reqs_rqr_42@). -\see{Figure~\ref{fig:lst-issues-attach} and Figure~\ref{fig:lst-issues-multi-static}} -The latter type is a head, and these examples are of headed lists. - -A bespoke ``pointer to next @req@'' implementation often omits the latter type. +All examples so far use distinct user-facing types: +an item found in a list (type @req@ of variable @r1@, see \VRef[Figure]{fig:lst-issues-attach}), and a list (type @reql@ of variable @reqs_pri@, see \VRef[Figure]{fig:lst-issues-ident}). +The latter type is a head. +The resulting identity model (empty list) is just the head. +A bespoke ``pointer to next @req@'' implementation often omits the header; +hence, a pointer to any node can traverse its link fields: right or left and around, depending on the data structure. The resulting identity model is ad-hoc. + +Figure~\ref{fig:lst-issues-ident} shows the identity model's impact on +the existence of certain conceptual constructs, like zero-lengths lists and unlisted elements. +In headed thinking, there are length-zero lists (heads with no elements), and an element can be listed or not listed. +In ad-hoc thinking, there are no length-zero lists and every element belongs to a list of length at least one. +By omitting the head, elements can enter into an adjacency relationship, without requiring allocation for a head for the list, or finding a correct existing head. \begin{figure} @@ -996,13 +1004,4 @@ \end{figure} -Figure~\ref{fig:lst-issues-ident} shows the identity model's impact on -the existence of certain conceptual constructs, like zero-lengths lists and unlisted elements. -In headed thinking, there are length-zero lists (heads with no elements), and an element can be listed or not listed. -In ad-hoc thinking, there are no length-zero lists and every element belongs to a list of length at least one. - -By omitting the head, elements can enter into an adjacency relationship, -without requiring that someone allocate room for the head of the possibly-resulting list, -or being able to find a correct existing head. - A head defines one or more element roles, among elements that share a transitive adjacency. ``First'' and ``last'' are element roles. @@ -1010,5 +1009,5 @@ There is a cost to maintaining these roles. -A runtime component of this cost is evident in LQ's offering the choice of type generators @LIST@ vs.~@TAILQ@. +A runtime component of this cost is evident in LQ's offering the choice of type generators @LIST@ \vs @TAILQ@. Its @LIST@ maintains a ``first,'' but not a ``last;'' its @TAILQ@ maintains both roles. (Both types are doubly linked and an analogous choice is available for singly linked.) @@ -1025,7 +1024,5 @@ \subsection{End treatment: cased vs.\ uniform } -This issue is implementation-level, relevant to achieving high performance. - -A linear (non-circular), nonempty linked list has a first element and a last element, whether or not the list is headed. +A linear (non-circular), nonempty linked-list has a first element and a last element, whether or not the list is headed. A first element has no predecessor and a last element has no successor. @@ -1045,17 +1042,17 @@ End treatment refers to how the list represents the lack of a predecessor/successor. The following elaboration refers to the LQ representations, detailed in Figure~\ref{fig:lst-issues-end}. - The most obvious representation, a null pointer, mandates a cased end treatment. LQ uses this representation for its successor/last. Consider the operation of inserting after a given element. -A doubly-linked list must update the given node's successor, to make its predecessor-pointer to refer to the new node. +A doubly-linked list must update the given node's successor, to make its predecessor-pointer refer to the new node. This step must happen when the given node has a successor (when its successor pointer is non-null), and must be skipped when it does not (when its successor pointer cannot be navigated). So this operation contains a branch, to decide which case is happening. All branches have pathological cases where branch prediction's success rate is low and the execution pipeline is stalling often. +Hence, this issue is implementation-level, relevant to achieving high performance. This branch is sometimes avoidable; the result is a uniform end treatment. -Here is one example of such an implementation; it works for a headed list. -LQ uses uses this representation for its predecessor/first. (All LQ offerings are headed at the front.) +Here is one example of such an implementation that works for a headed list. +LQ uses this representation for its predecessor/first. (All LQ offerings are headed at the front.) For predecessor/first navigation, the relevant operation is inserting before a given element. LQ's predecessor representation is not a pointer to a node, but a pointer to a pseudo-successor pointer. @@ -1067,5 +1064,5 @@ Now, inserting before a given element does the same logic in both cases: follow the guaranteed-non-null predecessor pointer, and update what you find there to refer to the new node. -Applying this trick makes it possible to have list management routines that are completely free of control flow. +Applying this trick makes it possible to have list management routines that are completely free of conditional control-flow. Considering a path length of only a few instructions (less than the processor's pipeline length), such list management operations are often practically free, Index: doc/theses/mike_brooks_MMath/intro.tex =================================================================== --- doc/theses/mike_brooks_MMath/intro.tex (revision 7ef4438154228273f1e40137bc17a3cd20e74ce5) +++ doc/theses/mike_brooks_MMath/intro.tex (revision 520fa9e26472c80c05dc91004ccb5b6373b697da) @@ -88,5 +88,5 @@ -\subsection{C?} +\section{C?} Like many established programming languages, C has a standards committee and multiple ANSI/\-ISO language manuals~\cite{C99,C11,C18,C23}. Index: doc/theses/mike_brooks_MMath/programs/bkgd-carray-arrty.c =================================================================== --- doc/theses/mike_brooks_MMath/programs/bkgd-carray-arrty.c (revision 7ef4438154228273f1e40137bc17a3cd20e74ce5) +++ doc/theses/mike_brooks_MMath/programs/bkgd-carray-arrty.c (revision 520fa9e26472c80c05dc91004ccb5b6373b697da) @@ -51,5 +51,5 @@ void f( float (*pa)[10] ) { static_assert( sizeof( *pa ) == 40 ); $\C{// array}$ - static_assert( sizeof( pa ) == 8 ); $\C{// pointer to array}$ + static_assert( sizeof( pa ) == 8 ); $\C{// pointer to array}$ static_assert( sizeof( (*pa)[0] ) == 4 ); $\C{// first element}$ static_assert( sizeof(&((*pa)[0])) == 8 ); $\C{// pointer to first element}$ @@ -58,5 +58,5 @@ float fs@[]@ = {3.14, 1.77}; - char cs@[]@ = "hello"; // shorthand for 'h', 'e', 'l', 'l', 'o', '\0' + char cs@[]@ = "hello"; // shorthand for { 'h', 'e', 'l', 'l', 'o', '\0' } static_assert( sizeof(fs) == 2 * sizeof(float) ); static_assert( sizeof(cs) == 6 * sizeof(char) ); $\C{// 5 letters + 1 null terminator}$ Index: doc/theses/mike_brooks_MMath/programs/bkgd-carray-decay.c =================================================================== --- doc/theses/mike_brooks_MMath/programs/bkgd-carray-decay.c (revision 7ef4438154228273f1e40137bc17a3cd20e74ce5) +++ doc/theses/mike_brooks_MMath/programs/bkgd-carray-decay.c (revision 520fa9e26472c80c05dc91004ccb5b6373b697da) @@ -30,12 +30,12 @@ edit( "hello" ); $\C{// Segmentation fault [decay here]}$ - void decay( float x[10] ) { - static_assert( sizeof(x) == sizeof(void *) ); + void decay( @float x[10]@ ) { + static_assert(@sizeof(x) == sizeof(void *)@ ); } static_assert( sizeof(ar) == 10 * sizeof(float) ); decay( ar ); - void no_decay( float (*px)[10] ) { - static_assert( sizeof(*px) == 10 * sizeof(float) ); + void no_decay( @float (*px)[10]@ ) { + static_assert(@sizeof(*px) == 10 * sizeof(float)@); } static_assert( sizeof(*pa) == 10 * sizeof(float) ); Index: doc/theses/mike_brooks_MMath/programs/bkgd-carray-mdim.c =================================================================== --- doc/theses/mike_brooks_MMath/programs/bkgd-carray-mdim.c (revision 7ef4438154228273f1e40137bc17a3cd20e74ce5) +++ doc/theses/mike_brooks_MMath/programs/bkgd-carray-mdim.c (revision 520fa9e26472c80c05dc91004ccb5b6373b697da) @@ -15,14 +15,14 @@ int main() { float ar[3][10]; - static_assert(sizeof(float) == 4); $\C{// floats (atomic elements) are 4 bytes}$ - static_assert(sizeof(void*) == 8); $\C{// pointers are 8 bytes}$ + static_assert( sizeof(float) == 4 ); $\C{// floats (atomic elements) are 4 bytes}$ + static_assert( sizeof(void*) == 8 ); $\C{// pointers are 8 bytes}$ - static_assert(sizeof(ar) == 120); $\C{// the array, float[3][10]}$ - static_assert(sizeof(ar[0]) == 40); $\C{// its first element, float[10]}$ - static_assert(sizeof(ar[0][0]) == 4); $\C{// its first grand element, float}$ + static_assert( sizeof(ar) == 120 ); $\C{// the array, float[3][10]}$ + static_assert( sizeof(ar[0]) == 40 ); $\C{// its first element, float[10]}$ + static_assert( sizeof(ar[0][0]) == 4 ); $\C{// its first grand element, float}$ - static_assert(sizeof(&(ar)) == 8); $\C{// pointer to the array, float(*)[3][10]}$ - static_assert(sizeof(&(ar[0])) == 8); $\C{// pointer to its first element, float(*)[10]}$ - static_assert(sizeof(&(ar[0][0])) == 8); $\C{// pointer to its first grand-element, float*}$ + static_assert( sizeof(&(ar)) == 8 ); $\C{// pointer to the array, float(*)[3][10]}$ + static_assert( sizeof(&(ar[0])) == 8 ); $\C{// pointer to its first element, float(*)[10]}$ + static_assert( sizeof(&(ar[0][0])) == 8 ); $\C{// pointer to its first grand-element, float*}$ float (*pa)[3][10] = &(ar); @@ -30,6 +30,6 @@ float *pa00 = &(ar[0][0]); - static_assert((void*)&ar == (void*)&(ar[0] )); - static_assert((void*)&ar == (void*)&(ar[0][0])); + static_assert( (void*)&ar == (void*)&(ar[0] ) ); + static_assert( (void*)&ar == (void*)&(ar[0][0]) ); assert( (void *) pa == (void *) pa0 );