Changes in / [292d6cf6:5485bcac]


Ignore:
Location:
doc/theses/mike_brooks_MMath
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/mike_brooks_MMath/background.tex

    r292d6cf6 r5485bcac  
    640640
    641641Linked-lists are blocks of storage connected using one or more pointers.
    642 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.
     642The 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.
    643643Since the data is opaque, list structures are often polymorphic over the data, which is often homogeneous.
    644644
    645 The links organize nodes into a particular format, \eg queue, tree, hash table, \etc, with operations specific to that format.
     645Storage 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.
    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 thesis focuses on a reduced design space for linked lists that target \emph{system programmers}.
    654 Within this restricted space, all design-issue discussions assume the following invariants;
    655 alternatives to the assumptions are discussed under Future Work (Section~\ref{toc:lst:futwork}).
     653This section introduces the design space for linked lists that target \emph{system programmers}.
     654Within this restricted target, 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-node link-fields stored, in relation to the user's payload data fields?
     686Where are the libraries' inter-element 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 placement and attributes 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.}, which can be placed anywhere in the node.
    797 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.
    798 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.
     795A further aspect of layout control is allowing the user to explicitly specify link fields controlling attributes and placement 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.}
     797supplying the link fields by inheritance makes them implicit and relies on compiler placement, such as the start or end of @req@.
     798An 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.
    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, but never on both simultaneously.
     872This feature is used in the \CFA runtime where a thread node may be on a blocked or running list, both 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 lists a node can be associated with simultaneously, as any number of STL lists can be created dynamically.
     877The upside is the unlimited number of a lists a node can be associated with simultaneously, 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 list bindings.
    884 The downside is the dynamic allocation, significant storage usage, and cost of copying nodes.
     883The upside is the same as for wrapped-reference arrangement with an unlimited number of a list bindings.
     884The downside is the dynamic allocation and significant storage usage due to node copying.
    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 An alternative system providing intrusive data-structures is \uCpp, a concurrent extension of \CC.
    898 It provides a basic set of intrusive lists~\cite[appx.~F]{uC++}, where the link fields are defined with the data fields using inheritance.
     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.
    899898\begin{cquote}
    900899\setlength{\tabcolsep}{15pt}
    … …  
    961960\uCpp cheats by using inheritance for the first intrusive links, after which explicit naming of intrusive links is required.
    962961Furthermore, 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.
    963 At issue is whether an API for simultaneity can support one \emph{implicit} list, when several are not wanted.
     962At issue is whether an API for simultaneity can support one list (when several are not wanted) to be \emph{implicit}.
    964963\uCpp allows it, LQ does not, and the STL does not have this question.
    965964
    966965
    967966\subsection{User integration: preprocessed vs.\ type-system mediated}
    968 
    969 \PAB{What do you want to say here?}
    970967
    971968% example of poor error message due to LQ's preprocessed integration
    … …  
    980977\label{toc:lst:issue:ident}
    981978
    982 All examples so far use distinct user-facing types:
    983 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}).
    984 The latter type is a head.
    985 The resulting identity model (empty list) is just the head.
    986 A bespoke ``pointer to next @req@'' implementation often omits the header;
    987 hence, a pointer to any node can traverse its link fields: right or left and around, depending on the data structure.
     979All examples so far have used distinct user-facing types:
     980an item found in a list (type @req@, of variables like @r1@), and
     981a 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}}
     983The latter type is a head, and these examples are of headed lists.
     984
     985A bespoke ``pointer to next @req@'' implementation often omits the latter type.
    988986The resulting identity model is ad-hoc.
    989 
    990 Figure~\ref{fig:lst-issues-ident} shows the identity model's impact on
    991 the existence of certain conceptual constructs, like zero-lengths lists and unlisted elements.
    992 In headed thinking, there are length-zero lists (heads with no elements), and an element can be listed or not listed.
    993 In ad-hoc thinking, there are no length-zero lists and every element belongs to a list of length at least one.
    994 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.
    995987
    996988\begin{figure}
    … …  
    1004996\end{figure}
    1005997
     998Figure~\ref{fig:lst-issues-ident} shows the identity model's impact on
     999the existence of certain conceptual constructs, like zero-lengths lists and unlisted elements.
     1000In headed thinking, there are length-zero lists (heads with no elements), and an element can be listed or not listed.
     1001In ad-hoc thinking, there are no length-zero lists and every element belongs to a list of length at least one.
     1002
     1003By omitting the head, elements can enter into an adjacency relationship,
     1004without requiring that someone allocate room for the head of the possibly-resulting list,
     1005or being able to find a correct existing head.
     1006
    10061007A head defines one or more element roles, among elements that share a transitive adjacency.
    10071008``First'' and ``last'' are element roles.
    … …  
    10091010
    10101011There is a cost to maintaining these roles.
    1011 A runtime component of this cost is evident in LQ's offering the choice of type generators @LIST@ \vs @TAILQ@.
     1012A runtime component of this cost is evident in LQ's offering the choice of type generators @LIST@ vs.~@TAILQ@.
    10121013Its @LIST@ maintains a ``first,'' but not a ``last;'' its @TAILQ@ maintains both roles.
    10131014(Both types are doubly linked and an analogous choice is available for singly linked.)
    … …  
    10241025\subsection{End treatment: cased vs.\ uniform }
    10251026
    1026 A linear (non-circular), nonempty linked-list has a first element and a last element, whether or not the list is headed.
     1027This issue is implementation-level, relevant to achieving high performance.
     1028
     1029A linear (non-circular), nonempty linked list has a first element and a last element, whether or not the list is headed.
    10271030A first element has no predecessor and a last element has no successor.
    10281031
    … …  
    10421045End treatment refers to how the list represents the lack of a predecessor/successor.
    10431046The following elaboration refers to the LQ representations, detailed in Figure~\ref{fig:lst-issues-end}.
     1047
    10441048The most obvious representation, a null pointer, mandates a cased end treatment.
    10451049LQ uses this representation for its successor/last.
    10461050Consider the operation of inserting after a given element.
    1047 A doubly-linked list must update the given node's successor, to make its predecessor-pointer refer to the new node.
     1051A doubly-linked list must update the given node's successor, to make its predecessor-pointer to refer to the new node.
    10481052This step must happen when the given node has a successor (when its successor pointer is non-null),
    10491053and must be skipped when it does not (when its successor pointer cannot be navigated).
    10501054So this operation contains a branch, to decide which case is happening.
    10511055All branches have pathological cases where branch prediction's success rate is low and the execution pipeline is stalling often.
    1052 Hence, this issue is implementation-level, relevant to achieving high performance.
    10531056
    10541057This branch is sometimes avoidable; the result is a uniform end treatment.
    1055 Here is one example of such an implementation that works for a headed list.
    1056 LQ uses this representation for its predecessor/first.  (All LQ offerings are headed at the front.)
     1058Here is one example of such an implementation; it works for a headed list.
     1059LQ uses uses this representation for its predecessor/first.  (All LQ offerings are headed at the front.)
    10571060For predecessor/first navigation, the relevant operation is inserting before a given element.
    10581061LQ's predecessor representation is not a pointer to a node, but a pointer to a pseudo-successor pointer.
    … …  
    10641067Now, inserting before a given element does the same logic in both cases:
    10651068follow the guaranteed-non-null predecessor pointer, and update what you find there to refer to the new node.
    1066 Applying this trick makes it possible to have list management routines that are completely free of conditional control-flow.
     1069Applying this trick makes it possible to have list management routines that are completely free of control flow.
    10671070Considering a path length of only a few instructions (less than the processor's pipeline length),
    10681071such list management operations are often practically free,

  • doc/theses/mike_brooks_MMath/intro.tex

    r292d6cf6 r5485bcac  
    8888
    8989
    90 \section{C?}
     90\subsection{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

    r292d6cf6 r5485bcac  
    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

    r292d6cf6 r5485bcac  
    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

    r292d6cf6 r5485bcac  
    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.