Changeset e8a7b66d for doc/theses/mike_brooks_MMath/list.tex

Timestamp:

Apr 11, 2026, 12:02:44 AM (40 hours ago)

Author:

Michael Brooks <mlbrooks@…>

Branches:

master

Children:

75ba2fa6

Parents:

e2e927e

Message:

switch list perf winner-loser plot to uniform treatment of all first-order effects; add discussion of key conclusion that fx is not your big-ticket item

File:

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

doc/theses/mike_brooks_MMath/list.tex

@@ -1035 +1035 @@
 \begin{figure}
   \centering
-  \includegraphics{plot-list-op-fx.pdf}
-  \caption{Histogram of operation durations, decomposed by non-physical factors.
-  The twelve-way by-operation breakdown, and the four-way by-framework breakdown, each divides the entire population of test results into its mutually disjoint constituents.}
-  \label{fig:plot-list-op-fx}
-\end{figure}
-
-\VRef[Figure]{fig:plot-list-op-fx} gives this non-physical decomposition.
-
-\MLB{Peter, stop here.  Discussion of these non-physical factos is coming.}
+  \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}}
+  \label{fig:plot-list-1ord}
+\end{figure}
+
+\MLB{Peter, resume at full strength here.  This first-order comparison is the key takeaway from my recent analysis work.}
+
+\VRef[Figure]{fig:plot-list-1ord} gives the first-order effects.
+Its first breakdown, Machine--Size-Zone, shows the effects of an insert/remove's physical situation.
+The Intel runs faster than the AMD; the small zone runs faster than the medium zone.
+The size effect is more pronounced on the AMD than it is on the Intel.
+
+These facts stated, you will not be chosing between these particular mahines or whether to run at one of these specific size zones.
+The key takeaway from the physical comparison is the context it establishes for interpreting the framework comparison following.
+Both the particulars of a the machine's cache design, and a list length's effect on the program's cache friendliness, affect add/remove speed in the manner illlustrated in this breakdown.
+Specifically, a 20\% standard deviation exists here, between the means four physical-effect categories.
+That is, if you are running on an unknown machine, at a scale above anomaly-prone individuals, and below where major LLC caching effects take over the general intrusive-list advantage, but with an unknown relationship to the sizing of your fickle low-level caches, you are likely to experience an unpredictable speed impact on the order of 20\%.
+
+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}.
+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.
+So you face another lottery, with a likely win-loss range of the standard deviation of the individual operations' means: 9\%.
+
+This context helps interpret \VRef[Figure]{fig:plot-list-1ord}'s final comparison, by framework.
+In this result, \CFA runs similarly to \uCpp and LQ-@list@ runs similarly to @tailq@.
+The standard deviation of the frameworks' means is 8\%.
+Framework choice has, therefore, less impact on your speed than the lottery tickets you already hold.
+
+Now, the LQs do indeed beat the UW languages by 15\%, a fact explored further in \MLB{TODO: xref}.
+But so too does operation VIII typically beat operation IV by 38\%.
+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.
+
+\MLB{ TODO: find a home for these original conclusions:
+cfa-upp similarity holde for all halves by movement or polarity;
+splitting on accessor, \CFA has a poor result on element removal, LQ-list has a great result on the other accessors, and uC++ is unaffected. }
+
+
+\MLB{Peter, stop here.  Rest of the section is coming.}
 
 \begin{comment}
@@ -1053 +1086 @@
 Overall, LQ-tailq does the best at short lengths but loses out above a dozen elements.
 \end{comment}
-
-
-\MLB{Here is the conclusion of the earlier analysis. It basically stands, but needs refreshing.}
-In the grand total, and in all halves by movement or polarity, \CFA and uC++ are equivalent, while LQ-@list@ beats them slightly.
-Splitting on accessor, \CFA has a poor result on element removal, LQ-@list@ has a great result on the other accessors, and uC++ is unaffected.
-The unseen @tailq@ dominates across every category and beats \CFA and uC++ by 15--20\%.
 
 % \begin{figure}