Changeset 006d4c4

Timestamp:

Jun 20, 2024, 2:58:32 PM (4 months ago)

Author:

Michael Brooks <mlbrooks@…>

Branches:

master

Children:

9d6082c

Parents:

567c775

Message:

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

Location:

doc/theses/mike_brooks_MMath

Files:

• background.tex (modified) (2 diffs)
• pictures/lst-issues-end.pdf (added)
• pictures/lst-issues-end.vsdx (added)
• pictures/lst-issues-ident.pdf (added)
• pictures/lst-issues-ident.vsdx (added)

doc/theses/mike_brooks_MMath/background.tex

@@ -749 +749 @@
 
 A bespoke ``pointer to next @req@'' implementation often omits the latter type.
-Such a list model is ad-hoc.
-
+The resulting identity model is ad-hoc.
+
+\begin{figure}
+        \centering
+        \includegraphics{lst-issues-ident.pdf}
+        \caption{
+                Comparison of headed and ad-hoc list identities, for various list lengths.
+                Pointers are logical, meaning that no claim is intended about which part of an object is being targeted.
+        }
+        \label{fig:lst-issues-ident}
+\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.
-\PAB{Create a figure for this.}
 
 By omitting the head, elements can enter into an adjacency relationship,
@@ -776 +787 @@
 Ability 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.
 
-\subsection{End treatment: Uniform }
-
+
+\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 first element has no predecessor and a last element has no successor.
+
+\begin{figure}
+        \centering
+        \includegraphics{lst-issues-end.pdf}
+        \caption{
+                LQ sub-object-level representation of links and ends.
+                Each object's memory is pictured as a vertical strip.
+                Pointers' target locations, within these strips, are significant.
+                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.
+                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.
+        }
+        \label{fig:lst-issues-end}
+\end{figure}
+
+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.
+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.
+
+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.)
+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.
+When there is a predecessor node, that node contains a real-successor pointer; it is the target of the reference node's predecessor pointer.
+When there is no predecessor node, the reference node (now known to be first node) acts as the pseudo-successor of the list head.
+The list head contains a pointer to the first node.
+When inserting before the first node, the list head's first-pointer is the one that must change.
+So, the first node's ``predecessor'' pointer (to a pseudo-successor pointer) is set as the list head's first-pointer.
+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.
+Considering a path length of only a few instructions (less than the processor's pipeline length),
+such list management operations are often practically free,
+with all the variance being due to the (inevitable) cache status of the nodes being managed.
 
 \section{String}