Index: doc/theses/mike_brooks_MMath/list.tex =================================================================== --- doc/theses/mike_brooks_MMath/list.tex (revision c910d308573cd6301dbb3c9ecb60bdf809d82c0e) +++ doc/theses/mike_brooks_MMath/list.tex (revision 741d004593f82a7c857e077c6a0af8e8f21cc2eb) @@ -659,12 +659,16 @@ This section explains how the experiment is built. Many of the following parts define terminology concerning tuning knobs. -\VRef[Figure]{f:ListPerfGlossary} provides a consolidated reference. - -\begin{figure} +\VRef[Table]{f:ListPerfGlossary} provides a consolidated reference. + +\begin{table} +\caption{ + Glossary of terms used in the list performance evaluation +} +\label{f:ListPerfGlossary} \noindent \begin{tabular}{p{1.75in}@{\ }p{4.5in}} Insert-Remove (IR) & The atomic unit of work being measured: one insertion plus one remove (plus all looping/tracking overheads) \\ -Use Case +Use Case & Pattern of add-remove calls. \\ -- Movement & \\ @@ -688,5 +692,5 @@ & insert through head and remove by element\\ Physical Context & \\ --- Size (number) & Number of nodes being linked. Unless specified, equals the \emph{length} of the program's sole list. \emph{Width}, rarely used, is the number of lists. \\ +-- Size (number) & Number of nodes being linked. Equals the length of the program's sole list. \\ -- Size Zone & Contiguous range of sizes, chosen to avoid known anomalies and to sample a brief plateau. Each zone buckets four specific sizes. \\ @@ -697,5 +701,5 @@ \quad $\ni$ (other) & Not used for comparing intrusive frameworks. \\ --- machine +-- Machine & Computer running the experiment \\ \quad $\ni$ AMD @@ -709,5 +713,9 @@ $\ni$ \uCpp & \uCpp's @uSequence@ \\ $\ni$ \CFA & \CFA's @dlist@ \\ -Explanation being +Individual config'n (IC) + & Specific situation in which an IR sequence is timed. One use case, on one machine, driving one exact list size, by one framework. \\ +Trial + & Timed run of the test program under a given IC, during which a few billion IRs occur. \\ +Explanation being & How independent explanatory variable X is analyzed \\ -- Marginalized @@ -716,9 +724,5 @@ & Held constant, yielding a more relative measure. Hides the effect that X causes. Conditioning on X creates more, smaller relative-measure peer groups, by isolating each X-domain value. Resulting interpretation is, ``Assuming no change in X.'' \\ \end{tabular} -\caption{ - Glossary of terms used in the list performance evaluation -} -\label{f:ListPerfGlossary} -\end{figure} +\end{table} @@ -886,5 +890,5 @@ \label{s:UseCases} -Where \VRef[Figure]{f:ListPerfGlossary} enumerates the specific values, recall the use-case dimensions are: +Where \VRef[Table]{f:ListPerfGlossary} enumerates the specific values, recall the use-case dimensions are: \begin{description} \item[movement ($\times 2$)] @@ -997,4 +1001,5 @@ \subsubsection{Sizing} +\label{s:experiment-sizing} Intuition suggests measuring IR for different sized lists should just be a multiple of the single linking/unlinking of a node. @@ -1047,13 +1052,15 @@ \VRef[Figure]{fig:plot-list-zoomin-abs} gives two example responses to size. % The dataset here is a small portion of the overall result and it is premature to attempt conclusions about framework differences from it. -These two example cases show how differently a pair of individual configurations behave. +These two example cases show how differently a pair of configurations can behave. % Of more immediate significance, they also have a pattern repeated, in all eight of their size responses. % Note the ``small'' and ``medium'' overlaid boxes, which call out the size zones' definitions. Outside of an identified box, size response is erratic. Inside a box, size response is relatively smooth. -Within and among boxes there are identifiable patterns, which occur throughout all the experimental results. -Each individual configuration is tested by five trials, giving the error bars at min and max. -The amount of error here is typical across the configurations. -With a few exceptions, it is modest, so experiments are repeatable. +Within and among the boxes there are identifiable patterns, which occur throughout all the experimental results. + +Every data point is one Individual Configuration (IC). +Each IC is tested by five trials; a point's error bars give the best and worst trial results; the point's centre is the mean of the middle three. +The amount of error here is typical across all the configurations (beyond the two shown here). +With a few exceptions, it is modest, so these experiments are repeatable. To preview, \VRef{s:ResultCoarseComparisonStyles} dismisses large sizes (above 150 elements) and wrapped lists, because the performance story is dominated by the amount of memory touched not by intrusive \vs wrapped lists. @@ -1115,12 +1122,12 @@ \subsubsection{Recap and Master Legend} -For experiments performed in later section, there are 12 use cases, which are all combinations of 2 movents, 2 polarities and 3 accessors. +For experiments performed in later sections, there are 12 use cases, which are all combinations of 2 movents, 2 polarities and 3 accessors. There are 4 pysical contexts, which are all combinations of 2 machines and 2 size (length) zones. -Each physical context samples 4 specific sizes. There are 3.25 frameworks. -This accounting considers how LQ-list supports only the movement--polarity combination "stack, insert first." +This accounting considers how LQ-list supports only the movement--polarity combination ``stack, insert first.'' So LQ-list fills a quarter of the otherwise-orthogonal space. -Use case, physical context and framework are the explanatory factors. -Taking all combinations of the explanatory factors gives 12 $\times$ 4 $\times$ 4 $\times$ 3.25 = 624 individual configurations. +Physical context, use case, and framework are the explanatory factors. +Each size zone summarizes samples of 4 specific sizes. +Taking all combinations of the explanatory factors and this sampling gives 4 $\times$ 12 $\times$ 3.25 $\times$ 4 = 624 individual configurations (ICs). % \[ @@ -1149,5 +1156,5 @@ \caption[IR duration, transformed for general anaysis]{ IR duration, transformed for general anaysis. - The analysis follows the single example setup of \VRef[Figure]{f:zoomin-abs-i-swift}, \ie Use Case I on AMD, where IR is given as absolute duration. + The analysis follows the single example setup of \VRef[Figure]{f:zoomin-abs-i-swift}, \ie Use Case I on AMD; there, IR is given as absolute duration. Plot (a) transforms the source dataset by conditioning on specific size. Plot (b) takes the results from only the identified size zones, discards their specific-size information, and shows the resulting distribution. @@ -1200,16 +1207,26 @@ \end{comment} -It is impossible to present this large amount of information in graphs. -Therefore, a condensed graphing style is used in subsequent plots. -\VRef[Figure]{fig:plot-list-rel} shows how the condensed graphing style is generated from raw data. -\VRef[Figure]{f:zoomin-rel-i-swift} is formed from the data in \VRef[Figure]{f:zoomin-abs-i-swift}, restructured on the Y-axis using a relative duration. -\VRef[Figure]{f:zoomin-histo-i-swift} shows the interesting data within the two boxes (Small/Medium) and their combination (Both). -This graph plots a vertical histogram for each of the 4 lists. +A condensed graphing style is used in subsequent plots to present this amount of data. +\VRef[Figure]{fig:plot-list-rel} shows how the condensed graphing style is generated from indvidual-configuration measures. +\VRef[Figure]{f:zoomin-rel-i-swift} is formed from the data in \VRef[Figure]{f:zoomin-abs-i-swift}, transformed on the Y-axis to show duration relative to the mean across all four frameworks, at each specific size. +\VRef[Figure]{f:zoomin-histo-i-swift} consenses the interesting data within the two boxes (Small/Medium) and their combination (Both). +This graph plots a vertical histogram for each of the 4 frameworks. +A data point on \VRef[Figure]{f:zoomin-abs-i-swift} is one-to-one with a point on \VRef[Figure]{f:zoomin-rel-i-swift}; each gives one IC. +Repeatability of the experimet being established previously, retry variance information (error bar on an individual-configuration point) is discarded, and only the expected performance of an IC (mean of its middle three out of five trials) is promoted into the histograms. +Each histogram bin (light-shaded area) counts the number of ICs whose expected performance falls in the bin's range. +A histogram's girth indicates the diversity of its qualifying configurations' performance expectations. +The overlaid tick symbol marks its group's mean performance. +An x label indicates the total number of ICs in a group, \eg ``/4'' $\Rightarrow$ 4 ICs per histogram (here, a size-zone/framework combination). +The totals are small here because attention is still restricted to the example slice of Use Case I on AMD. +But the graph format now scales to handle the full population of tested configurations, which is the subject of all subsequent plots. + +\begin{comment} The light-shaded histogram is the raw data (similar data values overlap), and the dark histogram is the goemean average when there are multiple experiments condensed in a column. -The caption indicates the number of values condensed into this histogram, e.g., ``/4'' $\Rightarrow$ 4 data points. -The vertical relationship among the averages gives a quick result for a specific experiment, where lower is better. + +The vertical relationship among the averages gives a quick result, where lower is better. The relative duration smooths the results, where smoothness diminishes as size increases. This flatness gives nicely separated histograms. Thus, in the forthcoming comparison plots: +\end{comment} % \begin{itemize}[leftmargin=*] @@ -1231,5 +1248,5 @@ \VRef[Figure]{fig:plot-list-zoomout} presents throughput at various list lengths for a linear and random (shuffled) IR test. Other kinds of scans were made, but the results are similar in many cases, so it is sufficient to discuss these two scans, representing difference ends of the access spectrum. -In the graphs, all four intrusive lists (lq-list, lq-tailq, \uCpp, \CFA, see Framework in \VRef[Figure]{f:ListPerfGlossary}) are plotted with the same symbol; +In the graphs, all four intrusive lists (lq-list, lq-tailq, \uCpp, \CFA, see Framework in \VRef[Table]{f:ListPerfGlossary}) are plotted with the same symbol; sometimes theses symbols clump on top of each other, showing the performance difference among intrusive lists is small in comparison to the wrapped list (std::list). See~\VRef{s:ComparingIntrusiveImplementations} for details among intrusive lists.