Changeset 2581f1e


Ignore:
Timestamp:
Apr 13, 2026, 1:03:37 AM (2 weeks ago)
Author:
Michael Brooks <mlbrooks@…>
Branches:
master
Children:
1abcec9b
Parents:
e35ecd0 (diff), 6762d46 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge remote-tracking branch 'refs/remotes/origin/master'

File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/mike_brooks_MMath/list.tex

    re35ecd0 r2581f1e  
    655655
    656656\subsection{Add-Remove Performance}
     657\label{s:AddRemovePerformance}
    657658
    658659The fundamental job of a linked-list library is to manage the links that connect nodes.
    … …  
    957958\label{s:ComparingIntrusiveImplementations}
    958959
    959 The preceding result shows the intrusive implementations examined have better performance compared to wrapped lists for small to medium sized lists.
    960 This analysis picks list sizes below 150 and zooms in to differentiate among the intrusive implementations.
     960The preceding result shows the intrusive implementations have better performance to the wrapped lists for small to medium sized lists.
     961This analysis covers the experiment position taken in \VRef{s:AddRemovePerformance} for movement, polarity, and accessor.
     962\VRef[Figure]{f:ExperimentOperations} shows the experiment operations tested, which results in 12 experiments for comparing intrusive implementations.
     963To preclude hardware interference, only list sizes below 150 are examined to differentiate among the intrusive implementations,
    961964The 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.
     965
     966\begin{figure}
     967\centering
     968\setlength{\tabcolsep}{8pt}
     969\begin{tabular}{@{}ll@{}}
     970\begin{tabular}{@{}c|c|c@{}}
     971movement & polarity & accessor \\
     972\hline
     973\hline
     974stack &
     975        \begin{tabular}{@{}l@{}}
     976        insert-first \\
     977        \hline
     978        insert-last
     979        \end{tabular}
     980        &
     981        \begin{tabular}{@{}l@{}}
     982        insert-head / remove-head \\
     983        \hline
     984        insert-list / remove-head \\
     985        \hline
     986        insert-head / remove-list
     987        \end{tabular}
     988        \\
     989\hline
     990queue &
     991        \begin{tabular}{@{}l@{}}
     992        insert-first \\
     993        \hline
     994        insert-last
     995        \end{tabular}
     996        &
     997        \begin{tabular}{@{}l@{}}
     998        insert-head / remove-head \\
     999        \hline
     1000        insert-list / remove-head \\
     1001        \hline
     1002        insert-head / remove-list
     1003        \end{tabular}
     1004\end{tabular}
     1005&
     1006        \setlength{\tabcolsep}{3pt}
     1007        \small
     1008        \begin{tabular}{@{}ll@{}}
     1009        I:      & stack, insert first, I-head / R-head \\
     1010        II:     & stack, insert first, I-list / R-head \\
     1011        III:& stack, insert first, I-head / R-list \\
     1012        IV:     & stack, insert last, I-head / R-head \\
     1013        V:      & stack, insert last, I-list / R-head \\
     1014        VI:     & stack, insert last, I-head / R-list \\
     1015        VII:& queue, insert first, I-head / R-head \\
     1016        VIII:& queue, insert first, I-list / R-head \\
     1017        IX:     & queue, insert first, I-head / R-list \\
     1018        X:      &  queue, insert last, I-head / R-head \\
     1019        XI:     & queue, insert last, iI-list / R-head \\
     1020        XII:    & queue, insert last, I-head / R-list \\
     1021        \end{tabular}
     1022\end{tabular}
     1023\caption{Experiment Operations}
     1024\label{f:ExperimentOperations}
     1025\end{figure}
     1026
     1027\VRef[Figure]{fig:plot-list-1ord} gives the first-order effects.
     1028Its first breakdown, Machine--Size-Zone, shows the effects of an insert/remove's physical situation.
     1029The Intel runs faster than the AMD; the small zone runs faster than the medium zone.
     1030The size effect is more pronounced on the AMD than it is on the Intel.
     1031
     1032\begin{figure}
     1033  \centering
     1034  \includegraphics{plot-list-1ord.pdf}
     1035  \caption{Histogram of operation durations, decomposed by all first-order effects.
     1036  Each of the three breakdowns divides the entire population of test results into its mutually disjoint constituents.
     1037  \MLB{missing: overlay of means}}
     1038  \label{fig:plot-list-1ord}
     1039\end{figure}
     1040
     1041These facts stated, you will not be chosing between these particular mahines or whether to run at one of these specific size zones.
     1042The key takeaway from the physical comparison is the context it establishes for interpreting the framework comparison following.
     1043Both 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.
     1044Specifically, a 20\% standard deviation exists here, between the means four physical-effect categories.
     1045That 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\%.
     1046
     1047A similar situation comes from \VRef[Figure]{fig:plot-list-1ord}'s second comparison, by operation type.
     1048Specific interactions like framework X doing better on stacks do occur; a selection of them is addressed in \MLB{TODO: cross reference}.
     1049But they are so irrelevant to the issue of picking a winning framework that it is sufficient here to number the operations opaquely.
     1050Whether 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.
     1051So you face another lottery, with a likely win-loss range of the standard deviation of the individual operations' means: 9\%.
     1052
     1053This context helps interpret \VRef[Figure]{fig:plot-list-1ord}'s final comparison, by framework.
     1054In this result, \CFA runs similarly to \uCpp and LQ-@list@ runs similarly to @tailq@.
     1055The standard deviation of the frameworks' means is 8\%.
     1056Framework choice has, therefore, less impact on your speed than the lottery tickets you already hold.
     1057
     1058Now, the LQs do indeed beat the UW languages by 15\%, a fact explored further in \MLB{TODO: xref}.
     1059But so too does operation VIII typically beat operation IV by 38\%.
     1060As does a small size on the Intel typically beat a medium size on the AMD by 66\%.
     1061Framework choice is simply not where you stand to win or lose the most.
     1062
     1063\MLB{ TODO: find a home for these original conclusions:
     1064cfa-upp similarity holde for all halves by movement or polarity;
     1065splitting on accessor, \CFA has a poor result on element removal, LQ-list has a great result on the other accessors, and uC++ is unaffected. }
     1066
    9621067
    9631068\begin{figure}
    … …  
    10341139With this adjustment, absolute duration values (in nonsecods) are lost.
    10351140In return, the physical quadrants are re-combined, enabling assessment of the non-physical factors.
    1036 
    1037 \begin{figure}
    1038   \centering
    1039   \includegraphics{plot-list-1ord.pdf}
    1040   \caption{Histogram of operation durations, decomposed by all first-order effects.
    1041   Each of the three breakdowns divides the entire population of test results into its mutually disjoint constituents.
    1042   \MLB{missing: overlay of means}}
    1043   \label{fig:plot-list-1ord}
    1044 \end{figure}
    1045 
    1046 \MLB{Peter, resume at full strength here.  This first-order comparison is the key takeaway from my recent analysis work.}
    1047 
    1048 \VRef[Figure]{fig:plot-list-1ord} gives the first-order effects.
    1049 Its first breakdown, Machine--Size-Zone, shows the effects of an insert/remove's physical situation.
    1050 The Intel runs faster than the AMD; the small zone runs faster than the medium zone.
    1051 The size effect is more pronounced on the AMD than it is on the Intel.
    1052 
    1053 These facts stated, you will not be chosing between these particular mahines or whether to run at one of these specific size zones.
    1054 The key takeaway from the physical comparison is the context it establishes for interpreting the framework comparison following.
    1055 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.
    1056 Specifically, a 20\% standard deviation exists here, between the means four physical-effect categories.
    1057 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\%.
    1058 
    1059 A similar situation comes from \VRef[Figure]{fig:plot-list-1ord}'s second comparison, by operation type.
    1060 Specific interactions like framework X doing better on stacks do occur; a selection of them is addressed in \MLB{TODO: cross reference}.
    1061 But they are so irrelevant to the issue of picking a winning framework that it is sufficient here to number the operations opaquely.
    1062 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.
    1063 So you face another lottery, with a likely win-loss range of the standard deviation of the individual operations' means: 9\%.
    1064 
    1065 This context helps interpret \VRef[Figure]{fig:plot-list-1ord}'s final comparison, by framework.
    1066 In this result, \CFA runs similarly to \uCpp and LQ-@list@ runs similarly to @tailq@.
    1067 The standard deviation of the frameworks' means is 8\%.
    1068 Framework choice has, therefore, less impact on your speed than the lottery tickets you already hold.
    1069 
    1070 Now, the LQs do indeed beat the UW languages by 15\%, a fact explored further in \MLB{TODO: xref}.
    1071 But so too does operation VIII typically beat operation IV by 38\%.
    1072 As does a small size on the Intel typically beat a medium size on the AMD by 66\%.
    1073 Framework choice is simply not where you stand to win or lose the most.
    1074 
    1075 \MLB{ TODO: find a home for these original conclusions:
    1076 cfa-upp similarity holde for all halves by movement or polarity;
    1077 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. }
    1078 
    1079 
    1080 \MLB{Peter, stop here.  Rest of the section is coming.}
    10811141
    10821142\begin{comment}
Note: See TracChangeset for help on using the changeset viewer.