Context Navigation

-              r534188b
+              rbf73608
 \end{figure}
 Where \VRef[Figure]{f:ListPerfGlossary} enumerates the specific values, reall the use-case dimensions are:
+Where \VRef[Figure]{f:ListPerfGlossary} enumerates the specific values, recall the use-case dimensions are:
 \begin{description}
         \item[movement ($\times 2$)]
 …
 Rather, size zones are picked, specific effects inside of a zone are averaged away, and the story at one zone is compared to that at another zone.
+\begin{figure}
+\centering
+  \setlength{\tabcolsep}{0pt}
+  \begin{tabular}{p{3.4375in}p{0.125in}p{2.9375in}}
+        \subfloat[ ]{\label{f:zoomin-abs-i-swift}
+                \includegraphics{plot-list-zoomin-abs-i-swift.pdf}
+        } & &
+        \subfloat[ ]{\label{f:zoomin-abs-viii-java}
+                \includegraphics{plot-list-zoomin-abs-viii-java.pdf}
+        }
+  \end{tabular}
+  \caption{Variety of IR duration \vs list length, at small--medium lengths.  Two example use cases are shown: I, stack movement with head-only access (plot a); VIII, queue movement with element-oriented removal access (plot b); both use cases have insert-first polarity.  One example is run on each machine: UC-I on AMD (ploat a); UC-VIII on Intel (plot b).  Lower duration is better.}
+  \label{fig:plot-list-zoomin-abs}
+\end{figure}
+\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 examples show, firstly, how differently a pair of individual 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 smooth.
+This pattern occurs generally throughout all the experimental results, beyond the two examples here.
 To preview, \VRef[Section]{toc:coarse-compre} dismisses ``Large'' sizes (above 150 elements), where the performance story is dominated by the amount of memory touched, inherently, by the choice of intrusive list \vs wrapped, and where one intrusive framework is quite obviously as good as another.
 At smaller sizes, comparing one intrusive framework to another makes sense; this comparion occurs in the remaining ``Result'' sections.
 Among the ``not Large'' sizes used there, two further zones, Small and Medium, are selected as representatives of what can vary when the scale is changed.
+At smaller sizes, comparing one intrusive framework to another makes sense; this comparison occurs in the remaining ``Result'' sections.
+Among the remaining ``not Large'' sizes, two further zones, \VRef[Figure]{fig:plot-list-zoomin-abs}'s Small and Medium, are selected as representatives of what can vary when the scale is changed.
 These particular ranges were chosen beacause each range tends to have one story repeated across its constituent sizes.
 If \CFA's duration increases across Small, then the other frameworks' usually do too.
 …
 Use case, physical context and framework are the explanatory factors.
+Taking all combinations of the explanatory factors gives 624 individual configurations.
+Though there are multiple experimental trials of each configuration (to assure repeatability), the usual measure is mean AIR among the trials, considered for each of the 624 individual configurations.
+All means reported in this analysis are geometric.
+\MLB{TODO: add example plots; explain histogram of 624}
+Taking all combinations of the explanatory factors gives 624 individual configurations:
+\[
+        \textrm{624 individual configurations} =
+        \sum_{\substack{
+                \textrm{12 use cases}\\
+                \textrm{4 physical contexts}\\
+                \textrm{4 specific sizes}\\
+                \textrm{3.25 frameworks}
+        }}
+        \textrm{1 individual configuration}
+\]
+\begin{figure}
+\centering
+  \setlength{\tabcolsep}{0pt}
+  \includegraphics[trim={0in, 1.75in, 0in, 0in}, clip]{plot-list-legend-rel-i-swift.pdf}
+  \begin{tabular}{p{2.75in}p{0.125in}p{3.625in}}
+        \subfloat[ ]{\label{f:zoomin-rel-i-swift}
+                \includegraphics{plot-list-zoomin-rel-i-swift.pdf}
+        } & &
+        \subfloat[ ]{\label{f:zoomin-histo-i-swift}
+                \includegraphics{plot-list-histo-rel-i-swift.pdf}
+        }
+  \end{tabular}
+  \caption{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.  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.  Lower duration is better.}
+  \label{fig:plot-list-rel}
+\end{figure}
+of these individual configurations, plucked from  \VRef[Figure]{f:zoomin-abs-i-swift}, are the subject of \VRef[Figure]{fig:plot-list-rel}, where they are now transformed into the format used for general analysis.
+In \subref*{f:zoomin-rel-i-swift}, each of the 56 data points is an individual configuration; the subset within the two boxes has the 32 of interest.
+In \subref*{f:zoomin-histo-i-swift}, the very leftmost histogram (Small, \CFA) summarizes the 4 Small--\CFA individual configurations.
+Each remaining framework, at size zone Small, similarly summarizes 4 individual configurations.
+This statement is the interpretation of the x-category label, ``Small (/4).''
+Each line under the ``/4'' label has 4 individual configurations; so, this group has 16 individual configurations.
+The interpretation of ``Medium (/4)'' is similar; it groups the remaining 16 configurations.
+When both size zones are pooled together, ``Both (/8)'' results; this group revisits all 32 configurations.
+This example's use of 32 individual configurations is in contrast with full-universe comparisons like the forthcoming \VRef[Figure]{fig:plot-list-1ord}, whose coverage further includes all use cases and both machines.
+The transformation of \VRef[Figure]{f:zoomin-abs-i-swift} into \VRef[Figure]{f:zoomin-rel-i-swift} conditions on the configuration's specific size.
+At a particular size, the average duration is computed, across the three frameworks that work on all use cases: \CFA, \uCpp and LQ-@tailq@.
+\VRef[Figure]{fig:plot-list-rel} shows a particular configuration's duration relative to this average.
+The effect of conditioning on specific size erases the fact that \VRef[Figure]{fig:plot-list-zoomin-abs} shows, aside from the coarse hops, all frameworks getting smoothly slower as size increases.
+This effect is partiularly relevant \emph{within} a size zone, most noticeable as the data lines all going up across the Small box.
+Now, with size conditioned, \VRef[Figure]{f:zoomin-rel-i-swift} has the trends inside a zone box being flat.
+This flatness gives \subref*{f:histo-rel-i-swift} nicely separated histograms.
+Specific size is the only factor conditioned in this view.
+This choice was made to keep the relationship between \VRef[Figures]{f:zoomin-abs-i-swift} and \VRef[]{:zoomin-rel-i-swift} perceptible.
+By contrast, general comparisons like \VRef[Figure]{fig:plot-list-1ord} condition on more, generally, everyting not presented.
+Its physical-factor breakdown conditions on use case and framework, but not on physical factors; its other two breakdowns are defined similarly.
+The noteworthy performance hop, in this example, is LQ-@list@, which \VRef[Figures]{f:zoomin-abs-i-swift} has as consistently slow in the Small range, and consistently fast in the Medium range.
+Therefore, in \VRef{f:zoomin-histo-i-swift}, its two per-size-zone histograms are far apart, and its cross-size-zone histogram is bimdal.
+Hops and distribution contributions, like this one, are common.
+They are attention-grabbing curiosities when comparing nearly any pair of individual configurations.
+They are the background noise of the all-in inter-configuration comparisons following.
+With this one, \VRef[Figure]{fig:plot-list-1ord}'s LQ-@list@ distribution (farthest right) does have a perceptible bump at $1.8\times$, corresponding to the upper mode seen here.
+But this UC-I--Intel contribution is only $1/6 = 8/48$ of the configurations summarized there.
+Each individual configuration is tested by five trials, giving the error bars of \VRef[Figure]{:zoomin-rel-i-swift} (at min and max).
+This trial error is unaffected by the size conditioning.
+Though this error is presented only for the narrow slice of the current examples, the amount of it seen here is typical across all the configurations.
+With a few exceptions, it is modest; so, the experiment is repeatable.
+The data points in \subref{f:zoomin-rel-i-swift} show mean excluding min and max.
+This value, alone, is the contribution to the histogram in \subref{f:zoomin-histo-i-swift}.
+That is, inter-configuration rollups discard the modest trial-repeatability error.
+The girth of a histogram's distribution is entirely the inter-configuration variance, of its configurations' expected performance.
+Thus, in the forthcoming comparison plots:
+\begin{itemize}
+\item
+The measure is mean IR among the middle 3 trials out of 5, that occurred for an individual configuration.
+\item
+The number of individual configurations per histogram is stated as ``/N,'' at a relevant grnaularity.
+\item
+All reported averages are geometric means and all IR duration axes (verticals) are logarithmic.
+\item
+Unless indicated otherwise, all explanatory factors appearing on a plot are marginalized, while those not appearing on the plot are conditioned.
+\end{itemize}
 …
   \caption{Insert/remove duration \vs list length.
   Lengths go as large possible without error.
   One example use case is shown: stack movement, insert-first polarity and head-mediated access. Lower is better.}
+  One example use case is shown: I, stack movement, insert-first polarity and head-mediated access. Lower duration is better.}
   \label{fig:plot-list-zoomout}
 \end{figure}
 …
 \begin{figure}
   \centering
+  \includegraphics{plot-list-1ord.pdf}
+  \includegraphics{plot-list-1ord.pdf} \\
+  \small{\textsuperscript{\textdagger} LQ-@list@ is (/48) by its incomplete (25\%) use case coverage.  Its bars are scaled to match.}
   \caption{Histogram of IR durations, decomposed by all first-order effects.
   Each of the three breakdowns divides the entire population of test results into its mutually disjoint constituents. The measure is duration; lower is better.}
+  Each of the three breakdowns divides the entire population of test results into its mutually disjoint constituents. Lower duration is better. \MLB{To fix: the size-zone bars are broken (wrong data)}}
   \label{fig:plot-list-1ord}
 \end{figure}
 …
 \subsection{Intrusive Sweet and Sore Spots}
+\subsection{Result: Sweet and Sore Spots}
 \begin{figure}
         \centering
+        \includegraphics{plot-list-2ord.pdf}
+        \includegraphics{plot-list-2ord.pdf}\\
+        \small{
+        \textsuperscript{\textdagger} LQ-@list@ is absent from Movement and Polarity comparisons because it does not support queue and insert-last, respectively.\\
+        \textsuperscript{\textdaggerdbl} LQ-@list@ is (/24) by its incomplete (25\%) use case coverage.  Its bars are scaled to match.\\
+        \textsuperscript{*} The full population of 192 individual configurations applies (48 for LQ-@list@), but this analysis summarizes pairs of them, giving each histogram's 96 contributions (24 for LQ-@list@).
+        }
         \caption{Histogram of IR durations, illustrating interactions with framework.
         Each distribution shows how its framework reacts to a single other factor being varied across one pair of options.
         Every (binned and mean-contributing) individual data point represents a pair of test setups, one with the criterion set to the option labelled at the top; the other setup uses the bottom option.
         This point's y-axis score is the ratio of these setups' durations.
         The point lands in a bin closer to the label of the option that performs better.
+        The point lands in a bin closer to the label of the option that performs better. \MLB{To fix: the size-zone bars are broken (no data)}
+        }
         \label{fig:plot-list-2ord}
 …
 It occurs only for the queue movement, only on the AMD machine, and only for the \CFA framework.
 Length-1 performane is an important case.
+Length-1 performance is an important case.
 Lists like those of waiting threads are frequently left empty, with the occasional thread (or few) momentarily joining.
 These scenarios need to work.
 A cause of this behaviour was never determined.
 Speculation is that \CFA's increased data dependency, a result of the tagging scheme, pairs poorly with the situation implied by queue movement.
+A cause of the slowdown was never determined.
+Speculation is that \CFA's increased data dependency, a result of the tagging scheme, pairs poorly with the aliasing implied by queue movement.
 The aliasing, at length 1, is: the head's first element is the head's last element.
+With stack movement, one of these aliases is used twice, while with queue movement, both are used in alternation.
+The breakdowns earlier in the performane assessment work by varying length only.
+With stack movement, one of these names for the first element is reaused for both insert and remove.
+While with queue movement, both names are used in alternation.
+The breakdowns earlier in the performance assessment vary length only.
 That is, they see the story down the leftmost column in a triangle.
 The insight for contextualizing this issue was to inspect both length and width.
 …
 \begin{comment}
-\begin{figure}
-\centering
-  \setlength{\tabcolsep}{0pt}
-  \begin{tabular}{p{0.75in}p{2.75in}p{3in}}
+  &
-  \subfloat[Operation I, AMD]{\label{f:AbsoluteTime-i-swift}
-        \hspace*{-0.75in}
-        \includegraphics{plot-list-zoomin-abs-i-swift.pdf}
-  } % subfigure
+  &
-  \subfloat[Operation I, Intel]{\label{f:AbsoluteTime-i-java}
-        \includegraphics{plot-list-zoomin-abs-i-java.pdf}
-  } % subfigure
-  \\
+  &
-  \subfloat[Operation VIII, AMD]{\label{f:AbsoluteTime-viii-swift}
-        \hspace*{-0.75in}
-        \includegraphics{plot-list-zoomin-abs-viii-swift.pdf}
-  } % subfigure
+  &
-  \subfloat[Operation VIII, Intel]{\label{f:AbsoluteTime-viii-java}
-        \includegraphics{plot-list-zoomin-abs-viii-java.pdf}
-  } % subfigure
-  \end{tabular}
-  \caption{Operation duration \vs list length at small-medium lengths.  Two example operations are shown: [I] stack movement with head-only access (plots a and b); [VIII] queue movement with element-oriented removal access (plots c and d); both operations use insert-first polarity. Lower is better.}
-  \label{fig:plot-list-zoomin}
-\end{figure}
 \VRef[Figure]{fig:plot-list-zoomin} shows the sizes below 150 blown up.

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

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

Legend:

doc/theses/mike_brooks_MMath/list.tex

Download in other formats: