Changes in / [2581f1e:e35ecd0]

File:

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

doc/theses/mike_brooks_MMath/list.tex

@@ -655 +655 @@
 
 \subsection{Add-Remove Performance}
-\label{s:AddRemovePerformance}
 
 The fundamental job of a linked-list library is to manage the links that connect nodes.
@@ -958 +957 @@
 \label{s:ComparingIntrusiveImplementations}
 
-The preceding result shows the intrusive implementations have better performance to the wrapped lists for small to medium sized lists.
-This analysis covers the experiment position taken in \VRef{s:AddRemovePerformance} for movement, polarity, and accessor.
-\VRef[Figure]{f:ExperimentOperations} shows the experiment operations tested, which results in 12 experiments for comparing intrusive implementations.
-To preclude hardware interference, only list sizes below 150 are examined to differentiate among the intrusive implementations, 
+The preceding result shows the intrusive implementations examined have better performance compared to wrapped lists for small to medium sized lists.
+This analysis picks list sizes below 150 and zooms in to differentiate among the intrusive implementations.
 The data is selected from the start of \VRef[Figures]{f:Linear-swift}--\subref*{f:Linear-java}, but the start of \VRef[Figures]{f:Random-swift}--\subref*{f:Random-java} is largely the same.
-
-\begin{figure}
-\centering
-\setlength{\tabcolsep}{8pt}
-\begin{tabular}{@{}ll@{}}
-\begin{tabular}{@{}c|c|c@{}}
-movement & polarity & accessor \\
-\hline
-\hline
-stack &
-        \begin{tabular}{@{}l@{}}
-        insert-first \\
-        \hline
-        insert-last
-        \end{tabular}
-        &
-        \begin{tabular}{@{}l@{}}
-        insert-head / remove-head \\
-        \hline
-        insert-list / remove-head \\
-        \hline
-        insert-head / remove-list
-        \end{tabular}
-        \\
-\hline
-queue &
-        \begin{tabular}{@{}l@{}}
-        insert-first \\
-        \hline
-        insert-last
-        \end{tabular}
-        &
-        \begin{tabular}{@{}l@{}}
-        insert-head / remove-head \\
-        \hline
-        insert-list / remove-head \\
-        \hline
-        insert-head / remove-list
-        \end{tabular}
-\end{tabular}
-&
-        \setlength{\tabcolsep}{3pt}
-        \small
-        \begin{tabular}{@{}ll@{}}
-        I:      & stack, insert first, I-head / R-head \\
-        II:     & stack, insert first, I-list / R-head \\
-        III:& stack, insert first, I-head / R-list \\
-        IV:     & stack, insert last, I-head / R-head \\
-        V:      & stack, insert last, I-list / R-head \\
-        VI:     & stack, insert last, I-head / R-list \\
-        VII:& queue, insert first, I-head / R-head \\
-        VIII:& queue, insert first, I-list / R-head \\
-        IX:     & queue, insert first, I-head / R-list \\
-        X:      &  queue, insert last, I-head / R-head \\
-        XI:     & queue, insert last, iI-list / R-head \\
-        XII:    & queue, insert last, I-head / R-list \\
-        \end{tabular}
-\end{tabular}
-\caption{Experiment Operations}
-\label{f:ExperimentOperations}
-\end{figure}
-
-\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.
-
-\begin{figure}
-  \centering
-  \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}
-
-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. }
-
 
 \begin{figure}
@@ -1139 +1034 @@
 With this adjustment, absolute duration values (in nonsecods) are lost.
 In return, the physical quadrants are re-combined, enabling assessment of the non-physical factors.
+
+\begin{figure}
+  \centering
+  \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}