Changeset 1abcec9b for doc/theses/mike_brooks_MMath/list.tex

Timestamp:

Apr 13, 2026, 3:05:44 AM (2 weeks ago)

Author:

Michael Brooks <mlbrooks@…>

Branches:

master

Children:

5b21636b

Parents:

2581f1e

Message:

Add overlaid means to list perf histograms. Add 2nd-order graph to the paper and its discussion.

File:

• doc/theses/mike_brooks_MMath/list.tex (modified) (5 diffs)

doc/theses/mike_brooks_MMath/list.tex

@@ -1034 +1034 @@
   \includegraphics{plot-list-1ord.pdf}
   \caption{Histogram of operation durations, decomposed by all first-order effects.
-  Each of the three breakdowns divides the entire population of test results into its mutually disjoint constituents.
-  \MLB{missing: overlay of means}}
+  Each of the three breakdowns divides the entire population of test results into its mutually disjoint constituents.}
   \label{fig:plot-list-1ord}
 \end{figure}
@@ -1046 +1045 @@
 
 A similar situation comes from \VRef[Figure]{fig:plot-list-1ord}'s second comparison, by operation type.
-Specific interactions like framework X doing better on stacks do occur; a selection of them is addressed in \MLB{TODO: cross reference}.
+Specific interactions do occur, like framework X doing better on stacks than on queues; a selection of these is addressed in \VRef[Figure]{fig:plot-list-2ord} and discussed shortly.
 But they are so irrelevant to the issue of picking a winning framework that it is sufficient here to number the operations opaquely.
 Whether a given list implementation is suitable for a language's general library succeeds or fails without knowledge of whether your use will have stack or queue movement.
@@ -1060 +1059 @@
 As does a small size on the Intel typically beat a medium size on the AMD by 66\%.
 Framework choice is simply not where you stand to win or lose the most.
+
+\begin{figure}
+        \centering
+        \includegraphics{plot-list-2ord.pdf}
+        \caption{Histogram of operation durations, illustrating interactions with framework.
+        Each distribution shows how its framework reacts to a single other factor being varied across one pair of options.
+        Every (binned and mean-contributing) individual data point represents a pair of test setups, one with the criterion set to the option labelled at the top; the other setup uses the bottom option.
+        This point's y-axis score is the ratio of these setups' durations.
+        The point lands in a bin closer to the label of the option that performs better.
+        }
+        \label{fig:plot-list-2ord}
+\end{figure}  
+
+\VRef[Figure]{fig:plot-list-1ord} stays razor-focused on only first-order effects in order to contextualize a winner/loser framework observation.
+But this perspective cannot address questions like, ``Where are \CFA's sore spots?''
+Moreover, the shallow threatment of operations by ordinals said nothing about how stack usage compares with queues'.
+
+\VRef[Figure]{fig:plot-list-2ord} provides such answers.
+Its size-zone criterion refines the obvious notion that a small size runs faster than a big size; this issue is by how much.
+Indeed, all means favour small and few tails favour medium.
+But the various frameworks do no respond to the different sizes and machines uniformly.
+On the AMD, \CFA and \uCpp have a modest size sensitivity, LQ-tailq's is moderate amd LQ-list seems unaffected.
+On the Intel, \CFA's increases to moderate, while \uCpp is now unaffected, and both LQs have a dramatic response.
+The Intel is more sensitive to size than the AMD.
+
+Turning next to movement and polarity, the responses appear more subdued.
+Note that LQ-list has no represntation in these comparisons because it only supports stacks that push and pop with the first element.
+\CFA is completely stable under movement and polarity changes.
+\uCpp and LQ show modest responses favouring queues and insertion at last.
+
+Finally, with accessor, a \CFA sore spot emerges.
+Note the pair of two-way comparisons pulled from the three experiment setups used.
+First, the all-head/insert-element opposition addresses which insertion style is better---by-head (top) and by-element (bottom).
+Then, the all-head/remove-element opposition addresses which removal style is better---by-head (top) and by-element (bottom).
+The LQs favour insertion by head and removal by element.
+\CFA and \uCpp favour both operations by head.
+The strongest effect is \CFA's aversion to removal by element---certainly an opportunity for improvement.
+
+\begin{comment}
+        These remarks are mostly about 3ord over 2ord.
+This analysis does not provide more detail about one framework beating another; it offers different benefits.
+These interactions further illustrate the lottery-ticket unpredictability that a linked-list user inevitably faces, by revealing stronger-still performance swings hidden from the first-order view.
+They illustrate the difficult signal-to-noise ratio that I had to overcome in preparing this data.
+They may serve as a reference guiding future \CFA linked-list work by informing on where to target improvements.
+Finally, the findings offer the conclusion that \CFA's list offers more consostent performance across usage scenarios, than the other lists.
+\end{comment}
+
+\begin{comment}
+Further to the interpretation guidance of \VRef[Figure]{fig:plot-list-2ord}'s caption, a comparison with the construction of \VRef[Figure]{fig:plot-list-1ord} may be helpful.
+In the first-order graph, the factors being compared had many options: four, twelve and four.
+# XXX Each option contributes its own, seemingly independent, mean and distribution.
+# XXX But, in fact, they are not totally independent.
+# WRONG: it's not just about binary, you also need a split on a conditioned factor
+        I'm trying to get to:
+Side by side in earlier style, but they're opposites, so they mirror each other, so you take option B, flip it over, and have option A---I'll just show A
+\end{comment}
+
+
 
 \MLB{ TODO: find a home for these original conclusions:
@@ -1124 +1181 @@
   \caption{Histogram of operation durations, decomposed by physical factors.
   Measurements are included from only the sizes in the ``small'' and ``medium'' stable zones.
-  This breakdown divides the entire population of test results into four mutually disjoint constituents.}
+  This breakdown divides the entire population of test results into four mutually disjoint constituents.
+  \MLB{I see that I broke it. But we might be getting rid of it.}
+  }
   \label{fig:plot-list-mchn-szz}
 \end{figure}
@@ -1131 +1190 @@
 Each of these four histograms shows variation in duration coming from the four specific sizes in a size zone, from combining results of all twelve operations and all four frameworks.
 Among the means of the four histograms, there is a standard deviation of 0.9 ns, which is 20\% of the global mean.
-This variability is due solely to physial factors.
+This variability is due solely to physical factors.
 
 From the perspective of assessing winning/losing frameworks, these physical effects are noise.