Index: doc/theses/mike_brooks_MMath/list.tex =================================================================== --- doc/theses/mike_brooks_MMath/list.tex (revision 75ba2fa6bfec80d9e7a6929eee5e8738f14cc496) +++ doc/theses/mike_brooks_MMath/list.tex (revision 6762d4666e9dadbd7d47829302e72bd6642c929a) @@ -655,4 +655,5 @@ \subsection{Add-Remove Performance} +\label{s:AddRemovePerformance} The fundamental job of a linked-list library is to manage the links that connect nodes. @@ -957,7 +958,111 @@ \label{s:ComparingIntrusiveImplementations} -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 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 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} @@ -1034,49 +1139,4 @@ 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}