Ignore:
Timestamp:
Oct 30, 2024, 11:05:29 PM (7 weeks ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
master
Children:
292d6cf6
Parents:
a3bd827
Message:

proofread background chapter, and other small changes

Location:
doc/theses/mike_brooks_MMath
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/mike_brooks_MMath/background.tex

    ra3bd827 r520fa9e  
    640640
    641641Linked-lists are blocks of storage connected using one or more pointers.
    642 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.
     642The 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.
    643643Since the data is opaque, list structures are often polymorphic over the data, which is often homogeneous.
    644644
    645 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.
     645The links organize nodes into a particular format, \eg queue, tree, hash table, \etc, with operations specific to that format.
    646646Because a node's existence is independent of the data structure that organizes it, all nodes are manipulated by address not value;
    647647hence, all data structure routines take and return pointers to nodes and not the nodes themselves.
    … …  
    651651\label{toc:lst:issue}
    652652
    653 This section introduces the design space for linked lists that target \emph{system programmers}.
    654 Within this restricted target, all design-issue discussions assume the following invariants.
    655 Alternatives to the assumptions are discussed under Future Work (Section~\ref{toc:lst:futwork}).
     653This thesis focuses on a reduced design space for linked lists that target \emph{system programmers}.
     654Within this restricted space, all design-issue discussions assume the following invariants;
     655alternatives to the assumptions are discussed under Future Work (Section~\ref{toc:lst:futwork}).
    656656\begin{itemize}
    657657        \item A doubly-linked list is being designed.
    … …  
    672672and further libraries are introduced as needed.
    673673\begin{enumerate}
    674         \item Linux Queue library\cite{lst:linuxq} (LQ) of @<sys/queue.h>@.
     674        \item Linux Queue library~\cite{lst:linuxq} (LQ) of @<sys/queue.h>@.
    675675        \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}
    676676\end{enumerate}
    677677%A general comparison of libraries' abilities is given under Related Work (Section~\ref{toc:lst:relwork}).
    678678For the discussion, assume the fictional type @req@ (request) is the user's payload in examples.
    679 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.
     679As 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.
    680680
    681681
    … …  
    684684
    685685Link attachment deals with the question:
    686 Where are the libraries' inter-element link fields stored, in relation to the user's payload data fields?
     686Where are the libraries' inter-node link-fields stored, in relation to the user's payload data fields?
    687687\VRef[Figure]{fig:lst-issues-attach} shows three basic styles.
    688688\VRef[Figure]{f:Intrusive} shows the \newterm{intrusive} style, placing the link fields inside the payload structure.
    … …  
    793793The 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.
    794794
    795 A further aspect of layout control is allowing the user to explicitly specify link fields controlling attributes and placement within the @req@ object.
    796 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.}
    797 supplying the link fields by inheritance makes them implicit and relies on compiler placement, such as the start or end of @req@.
    798 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.
     795A further aspect of layout control is allowing the user to explicitly specify link fields controlling placement and attributes within the @req@ object.
     796LQ 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.
     797An 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.
     798Supplying 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.
    799799Wrapped reference has no control over the link fields, but the separate data allows some control;
    800800wrapped value has no control over data or links.
    … …  
    805805The same is not true of STL, wrapped reference or value.
    806806There, the analogous operations, @iterator::operator++()@, @iterator::operator*()@, and @list::erase(iterator)@, work on a parameter of type @list<T>::iterator@;
    807 There is no mapping from @req &@ to @list<req>::iterator@. %, for linear search.
     807there is no mapping from @req &@ to @list<req>::iterator@. %, for linear search.
    808808
    809809The advantage of wrapped is the abstraction of a data item from its list membership(s).
    … …  
    870870Thus, the intrusive LQ example supports multiple, but statically many, link lists.
    871871Note, 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.
    872 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.
     872This feature is used in the \CFA runtime, where a thread node may be on a blocked or running list, but never on both simultaneously.
    873873
    874874Now consider the STL in the wrapped-reference arrangement of Figure~\ref{f:WrappedRef}.
    875875Here it is possible to construct the same simultaneity by creating multiple STL lists, each pointing at the appropriate nodes.
    876876Each group of intrusive links become the links for each separate STL list.
    877 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.
     877The upside is the unlimited number of lists a node can be associated with simultaneously, as any number of STL lists can be created dynamically.
    878878The downside is the dynamic allocation of the link nodes and managing multiple lists.
    879879Note, it might be possible to wrap the multiple lists in another type to hide this implementation issue.
    … …  
    881881Now consider the STL in the wrapped-value arrangement of Figure~\ref{f:WrappedValue}.
    882882Again, 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.
    883 The upside is the same as for wrapped-reference arrangement with an unlimited number of a list bindings.
    884 The downside is the dynamic allocation and significant storage usage due to node copying.
     883The upside is the same as for wrapped-reference arrangement with an unlimited number of list bindings.
     884The downside is the dynamic allocation, significant storage usage, and cost of copying nodes.
    885885As well, it is unclear how node updates work in this scenario, without some notation of ultimately merging node information.
    886886
    … …  
    895895% The example uses @x@; @reqs@ would be a more readily ignored choice. \PAB{wording?}
    896896
    897 \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.
     897An alternative system providing intrusive data-structures is \uCpp, a concurrent extension of \CC.
     898It provides a basic set of intrusive lists~\cite[appx.~F]{uC++}, where the link fields are defined with the data fields using inheritance.
    898899\begin{cquote}
    899900\setlength{\tabcolsep}{15pt}
    … …  
    960961\uCpp cheats by using inheritance for the first intrusive links, after which explicit naming of intrusive links is required.
    961962Furthermore, 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.
    962 At issue is whether an API for simultaneity can support one list (when several are not wanted) to be \emph{implicit}.
     963At issue is whether an API for simultaneity can support one \emph{implicit} list, when several are not wanted.
    963964\uCpp allows it, LQ does not, and the STL does not have this question.
    964965
    965966
    966967\subsection{User integration: preprocessed vs.\ type-system mediated}
     968
     969\PAB{What do you want to say here?}
    967970
    968971% example of poor error message due to LQ's preprocessed integration
    … …  
    977980\label{toc:lst:issue:ident}
    978981
    979 All examples so far have used distinct user-facing types:
    980 an item found in a list (type @req@, of variables like @r1@), and
    981 a list (type @reql@ or @list<req>@, of variables like @reqs@ or @reqs_rqr_42@).
    982 \see{Figure~\ref{fig:lst-issues-attach} and Figure~\ref{fig:lst-issues-multi-static}}
    983 The latter type is a head, and these examples are of headed lists.
    984 
    985 A bespoke ``pointer to next @req@'' implementation often omits the latter type.
     982All examples so far use distinct user-facing types:
     983an 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}).
     984The latter type is a head.
     985The resulting identity model (empty list) is just the head.
     986A bespoke ``pointer to next @req@'' implementation often omits the header;
     987hence, a pointer to any node can traverse its link fields: right or left and around, depending on the data structure.
    986988The resulting identity model is ad-hoc.
     989
     990Figure~\ref{fig:lst-issues-ident} shows the identity model's impact on
     991the existence of certain conceptual constructs, like zero-lengths lists and unlisted elements.
     992In headed thinking, there are length-zero lists (heads with no elements), and an element can be listed or not listed.
     993In ad-hoc thinking, there are no length-zero lists and every element belongs to a list of length at least one.
     994By 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.
    987995
    988996\begin{figure}
    … …  
    9961004\end{figure}
    9971005
    998 Figure~\ref{fig:lst-issues-ident} shows the identity model's impact on
    999 the existence of certain conceptual constructs, like zero-lengths lists and unlisted elements.
    1000 In headed thinking, there are length-zero lists (heads with no elements), and an element can be listed or not listed.
    1001 In ad-hoc thinking, there are no length-zero lists and every element belongs to a list of length at least one.
    1002 
    1003 By omitting the head, elements can enter into an adjacency relationship,
    1004 without requiring that someone allocate room for the head of the possibly-resulting list,
    1005 or being able to find a correct existing head.
    1006 
    10071006A head defines one or more element roles, among elements that share a transitive adjacency.
    10081007``First'' and ``last'' are element roles.
    … …  
    10101009
    10111010There is a cost to maintaining these roles.
    1012 A runtime component of this cost is evident in LQ's offering the choice of type generators @LIST@ vs.~@TAILQ@.
     1011A runtime component of this cost is evident in LQ's offering the choice of type generators @LIST@ \vs @TAILQ@.
    10131012Its @LIST@ maintains a ``first,'' but not a ``last;'' its @TAILQ@ maintains both roles.
    10141013(Both types are doubly linked and an analogous choice is available for singly linked.)
    … …  
    10251024\subsection{End treatment: cased vs.\ uniform }
    10261025
    1027 This issue is implementation-level, relevant to achieving high performance.
    1028 
    1029 A linear (non-circular), nonempty linked list has a first element and a last element, whether or not the list is headed.
     1026A linear (non-circular), nonempty linked-list has a first element and a last element, whether or not the list is headed.
    10301027A first element has no predecessor and a last element has no successor.
    10311028
    … …  
    10451042End treatment refers to how the list represents the lack of a predecessor/successor.
    10461043The following elaboration refers to the LQ representations, detailed in Figure~\ref{fig:lst-issues-end}.
    1047 
    10481044The most obvious representation, a null pointer, mandates a cased end treatment.
    10491045LQ uses this representation for its successor/last.
    10501046Consider the operation of inserting after a given element.
    1051 A doubly-linked list must update the given node's successor, to make its predecessor-pointer to refer to the new node.
     1047A doubly-linked list must update the given node's successor, to make its predecessor-pointer refer to the new node.
    10521048This step must happen when the given node has a successor (when its successor pointer is non-null),
    10531049and must be skipped when it does not (when its successor pointer cannot be navigated).
    10541050So this operation contains a branch, to decide which case is happening.
    10551051All branches have pathological cases where branch prediction's success rate is low and the execution pipeline is stalling often.
     1052Hence, this issue is implementation-level, relevant to achieving high performance.
    10561053
    10571054This branch is sometimes avoidable; the result is a uniform end treatment.
    1058 Here is one example of such an implementation; it works for a headed list.
    1059 LQ uses uses this representation for its predecessor/first.  (All LQ offerings are headed at the front.)
     1055Here is one example of such an implementation that works for a headed list.
     1056LQ uses this representation for its predecessor/first.  (All LQ offerings are headed at the front.)
    10601057For predecessor/first navigation, the relevant operation is inserting before a given element.
    10611058LQ's predecessor representation is not a pointer to a node, but a pointer to a pseudo-successor pointer.
    … …  
    10671064Now, inserting before a given element does the same logic in both cases:
    10681065follow the guaranteed-non-null predecessor pointer, and update what you find there to refer to the new node.
    1069 Applying this trick makes it possible to have list management routines that are completely free of control flow.
     1066Applying this trick makes it possible to have list management routines that are completely free of conditional control-flow.
    10701067Considering a path length of only a few instructions (less than the processor's pipeline length),
    10711068such list management operations are often practically free,

  • doc/theses/mike_brooks_MMath/intro.tex

    ra3bd827 r520fa9e  
    8888
    8989
    90 \subsection{C?}
     90\section{C?}
    9191
    9292Like many established programming languages, C has a standards committee and multiple ANSI/\-ISO language manuals~\cite{C99,C11,C18,C23}.

  • doc/theses/mike_brooks_MMath/programs/bkgd-carray-arrty.c

    ra3bd827 r520fa9e  
    5151        void f( float (*pa)[10] ) {
    5252                static_assert( sizeof( *pa ) == 40 ); $\C{// array}$
    53                 static_assert( sizeof( pa ) == 8 );     $\C{// pointer to array}$
     53                static_assert( sizeof( pa ) == 8 ); $\C{// pointer to array}$
    5454                static_assert( sizeof( (*pa)[0] ) == 4 ); $\C{// first element}$
    5555                static_assert( sizeof(&((*pa)[0])) == 8 ); $\C{// pointer to first element}$
    … …  
    5858
    5959        float fs@[]@ = {3.14, 1.77};
    60         char cs@[]@ = "hello";    // shorthand for 'h', 'e', 'l', 'l', 'o', '\0'
     60        char cs@[]@ = "hello";                                  // shorthand for { 'h', 'e', 'l', 'l', 'o', '\0' }
    6161        static_assert( sizeof(fs) == 2 * sizeof(float) );
    6262        static_assert( sizeof(cs) == 6 * sizeof(char) );  $\C{// 5 letters + 1 null terminator}$

  • doc/theses/mike_brooks_MMath/programs/bkgd-carray-decay.c

    ra3bd827 r520fa9e  
    3030        edit( "hello" );                        $\C{// Segmentation fault [decay here]}$
    3131
    32         void decay( float x[10] ) {
    33                 static_assert( sizeof(x) == sizeof(void *) );
     32        void decay( @float x[10]@ ) {
     33                static_assert(@sizeof(x) == sizeof(void *)@ );
    3434        }
    3535        static_assert( sizeof(ar) == 10 * sizeof(float) );
    3636        decay( ar );
    3737
    38         void no_decay( float (*px)[10] ) {
    39                 static_assert( sizeof(*px) == 10 * sizeof(float) );
     38        void no_decay( @float (*px)[10]@ ) {
     39                static_assert(@sizeof(*px) == 10 * sizeof(float)@);
    4040        }
    4141        static_assert( sizeof(*pa) == 10 * sizeof(float) );

  • doc/theses/mike_brooks_MMath/programs/bkgd-carray-mdim.c

    ra3bd827 r520fa9e  
    1515int main() {
    1616        float ar[3][10];
    17         static_assert(sizeof(float) == 4);                      $\C{// floats (atomic elements) are 4 bytes}$
    18         static_assert(sizeof(void*) == 8);                      $\C{// pointers are 8 bytes}$
     17        static_assert( sizeof(float) == 4 );    $\C{// floats (atomic elements) are 4 bytes}$
     18        static_assert( sizeof(void*) == 8 );    $\C{// pointers are 8 bytes}$
    1919
    20         static_assert(sizeof(ar) == 120);                       $\C{// the array, float[3][10]}$
    21         static_assert(sizeof(ar[0]) == 40);                     $\C{// its first element, float[10]}$
    22         static_assert(sizeof(ar[0][0]) == 4);           $\C{// its first grand element, float}$
     20        static_assert( sizeof(ar) == 120 );             $\C{// the array, float[3][10]}$
     21        static_assert( sizeof(ar[0]) == 40 );   $\C{// its first element, float[10]}$
     22        static_assert( sizeof(ar[0][0]) == 4 ); $\C{// its first grand element, float}$
    2323
    24         static_assert(sizeof(&(ar)) == 8);                      $\C{// pointer to the array, float(*)[3][10]}$
    25         static_assert(sizeof(&(ar[0])) == 8);           $\C{// pointer to its first element, float(*)[10]}$
    26         static_assert(sizeof(&(ar[0][0])) == 8);        $\C{// pointer to its first grand-element, float*}$
     24        static_assert( sizeof(&(ar)) == 8 );    $\C{// pointer to the array, float(*)[3][10]}$
     25        static_assert( sizeof(&(ar[0])) == 8 ); $\C{// pointer to its first element, float(*)[10]}$
     26        static_assert( sizeof(&(ar[0][0])) == 8 );      $\C{// pointer to its first grand-element, float*}$
    2727
    2828        float (*pa)[3][10] = &(ar);
    … …  
    3030        float *pa00 = &(ar[0][0]);
    3131
    32         static_assert((void*)&ar == (void*)&(ar[0] ));
    33         static_assert((void*)&ar == (void*)&(ar[0][0]));
     32        static_assert( (void*)&ar == (void*)&(ar[0] ) );
     33        static_assert( (void*)&ar == (void*)&(ar[0][0]) );
    3434
    3535        assert( (void *) pa == (void *) pa0 );
Note: See TracChangeset for help on using the changeset viewer.