Changeset 006d4c4

Jun 20, 2024, 2:58:32 PM (5 weeks ago)
Michael Brooks <mlbrooks@…>

Linked-list background additions for identity model and end treatment.

4 added
1 edited


  • doc/theses/mike_brooks_MMath/background.tex

    r567c775 r006d4c4  
    750750A bespoke ``pointer to next @req@'' implementation often omits the latter type.
    751 Such a list model is ad-hoc.
     751The resulting identity model is ad-hoc.
     754        \centering
     755        \includegraphics{lst-issues-ident.pdf}
     756        \caption{
     757                Comparison of headed and ad-hoc list identities, for various list lengths.
     758                Pointers are logical, meaning that no claim is intended about which part of an object is being targeted.
     759        }
     760        \label{fig:lst-issues-ident}
     763Figure~\ref{fig:lst-issues-ident} shows the identity model's impact on
     764the existence of certain conceptual constructs, like zero-lengths lists and unlisted elements.
    753765In headed thinking, there are length-zero lists (heads with no elements), and an element can be listed or not listed.
    754766In ad-hoc thinking, there are no length-zero lists and every element belongs to a list of length at least one.
    755 \PAB{Create a figure for this.}
    757768By omitting the head, elements can enter into an adjacency relationship,
    776787Ability to offer heads is good.  Point: Does maintaining a head mean that the user has to provide more state when manipulating the list?  Requiring the user to do so is bad, because the user may have lots of "list" typed variables in scope, and detecting that the user passed the wrong one requires testing all the listing edge cases.
    778 \subsection{End treatment: Uniform }
     790\subsection{End treatment: Cased vs.\ Uniform }
     792This issue is implementation-level, relevant to achieving high performance.
     794A linear (non-circular), nonempty linked list has a first element and a last element, whether or not the list is headed.
     795A first element has no predecessor and a last element has no successor.
     798        \centering
     799        \includegraphics{lst-issues-end.pdf}
     800        \caption{
     801                LQ sub-object-level representation of links and ends.
     802                Each object's memory is pictured as a vertical strip.
     803                Pointers' target locations, within these strips, are significant.
     804                Uniform treatment of the first-end is evident from an assertion like \lstinline{(**this.pred == this)} holding for all nodes \lstinline{this}, including the first one.
     805                Cased treatment of the last-end is evident from the symmetric proposition, \lstinline{(this.succ.pred == &this.succ)}, failing when \lstinline{this} is the last node.
     806        }
     807        \label{fig:lst-issues-end}
     810End treatment refers to how the list represents the lack of a predecessor/successor.
     811The following elaboration refers to the LQ representations, detailed in Figure~\ref{fig:lst-issues-end}.
     813The most obvious representation, a null pointer, mandates a cased end treatment.
     814LQ uses this representation for its successor/last.
     815Consider the operation of inserting after a given element.
     816A doubly-linked list must update the given node's successor, to make its predecessor-pointer to refer to the new node.
     817This step must happen when the given node has a successor (when its successor pointer is non-null),
     818and must be skipped when it does not (when its successor pointer cannot be navigated).
     819So this operation contains a branch, to decide which case is happening.
     820All branches have pathological cases where branch prediction's success rate is low and the execution pipeline is stalling often.
     822This branch is sometimes avoidable; the result is a uniform end treatment.
     823Here is one example of such an implementation; it works for a headed list.
     824LQ uses uses this representation for its predecessor/first.  (All LQ offerings are headed at the front.)
     825For predecessor/first navigation, the relevant operation is inserting before a given element.
     826LQ's predecessor representation is not a pointer to a node, but a pointer to a pseudo-successor pointer.
     827When there is a predecessor node, that node contains a real-successor pointer; it is the target of the reference node's predecessor pointer.
     828When there is no predecessor node, the reference node (now known to be first node) acts as the pseudo-successor of the list head.
     829The list head contains a pointer to the first node.
     830When inserting before the first node, the list head's first-pointer is the one that must change.
     831So, the first node's ``predecessor'' pointer (to a pseudo-successor pointer) is set as the list head's first-pointer.
     832Now, inserting before a given element does the same logic in both cases:
     833follow the guaranteed-non-null predecessor pointer, and update what you find there to refer to the new node.
     834Applying this trick makes it possible to have list management routines that are completely free of control flow.
     835Considering a path length of only a few instructions (less than the processor's pipeline length),
     836such list management operations are often practically free,
     837with all the variance being due to the (inevitable) cache status of the nodes being managed.
Note: See TracChangeset for help on using the changeset viewer.