Index: doc/theses/mike_brooks_MMath/list.tex =================================================================== --- doc/theses/mike_brooks_MMath/list.tex (revision e2e927eec770a0ff2d35ee0a0ec54765732411c3) +++ doc/theses/mike_brooks_MMath/list.tex (revision e8a7b66dfa975451475c2e36363c47605ebfcb74) @@ -1035,13 +1035,46 @@ \begin{figure} \centering - \includegraphics{plot-list-op-fx.pdf} - \caption{Histogram of operation durations, decomposed by non-physical factors. - The twelve-way by-operation breakdown, and the four-way by-framework breakdown, each divides the entire population of test results into its mutually disjoint constituents.} - \label{fig:plot-list-op-fx} -\end{figure} - -\VRef[Figure]{fig:plot-list-op-fx} gives this non-physical decomposition. - -\MLB{Peter, stop here. Discussion of these non-physical factos is coming.} + \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} @@ -1053,10 +1086,4 @@ Overall, LQ-tailq does the best at short lengths but loses out above a dozen elements. \end{comment} - - -\MLB{Here is the conclusion of the earlier analysis. It basically stands, but needs refreshing.} -In the grand total, and in all halves by movement or polarity, \CFA and uC++ are equivalent, while LQ-@list@ beats them slightly. -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. -The unseen @tailq@ dominates across every category and beats \CFA and uC++ by 15--20\%. % \begin{figure} Index: doc/theses/mike_brooks_MMath/plots/list-1ord.d =================================================================== --- doc/theses/mike_brooks_MMath/plots/list-1ord.d (revision e8a7b66dfa975451475c2e36363c47605ebfcb74) +++ doc/theses/mike_brooks_MMath/plots/list-1ord.d (revision e8a7b66dfa975451475c2e36363c47605ebfcb74) @@ -0,0 +1,2 @@ +plots/list-1ord.gp.INPUTS: build/plot-list-1ord.dat | build +plots/list-1ord.py.INPUTS: benchmarks/list/results-swift-general.csv Index: doc/theses/mike_brooks_MMath/plots/list-1ord.gp =================================================================== --- doc/theses/mike_brooks_MMath/plots/list-1ord.gp (revision e8a7b66dfa975451475c2e36363c47605ebfcb74) +++ doc/theses/mike_brooks_MMath/plots/list-1ord.gp (revision e8a7b66dfa975451475c2e36363c47605ebfcb74) @@ -0,0 +1,113 @@ +set terminal pdfcairo color enhanced size 6.5in,3.5in font "Times,17" + +set size 1.0, 1.0 # scale of plot area inside terminal +set origin 0.0, 0.0 # bottom-left corner + +INDIR="build" +OUTDIR="build" + +set macros +set output OUTDIR."/plot-list-1ord.pdf" + +set lmargin 10 +set bmargin 7 + +set grid +set nokey +set logscale y 2 +set yrange [0.4:3.0]; +set ytics ( \ + "+40%%" 1.666666667, \ + "+30%%" 1.428571429, \ + "+20%%" 1.25, \ + "+10%%" 1.111111111, \ + "0" 1, \ + "-20%%" 0.833333333, \ + "-40%%" 0.714285714, \ + "-60%%" 0.625, \ + "-80%%" 0.555555556, \ + "-100%%" 0.5, \ + "-130%%" 0.434782609, \ + "-160%%" 0.384615385, \ + "-200%%" 0.333333333 \ +) +set xrange [-5.5:17.5]; +set xlabel "Machine, Size Zone; Operation; Framework; \nPrevalence Prevalence Prevalence" +set xtics ( \ + "AMD, sm" -5, \ + "AMD, med" -4, \ + "Intel, sm" -3, \ + "Intel, med" -2, \ +\ + "I" 0, \ + "II" 1, \ + "III" 2, \ + "IV" 3, \ + "V" 4, \ + "VI" 5, \ + "VII" 6, \ + "VIII" 7, \ + "IX" 8, \ + "X" 9, \ + "XI" 10, \ + "XII" 11, \ +\ + "{/Helvetica=15 C{/Symbol \42}}" 13, \ + "{/Symbol \155}C++" 14, \ + "LQ: tailq" 15, \ + "LQ: list" 16, \ +) rotate by -45 + +set ylabel "Duration (relative)" offset -1.0,0 +set errorbars 2.0 +set pointintervalbox 0 + +barHtScale_phys = 0.05 +barHtScale_op = 0.1 +barHtScale_fx = 0.05 + + +plot INDIR."/plot-list-1ord.dat" \ + i 3 using (0):(0):(-1 - 1):(-1 - 1 + barHtScale_phys * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ + '' i 2 using (0):(0):(-1 - 2):(-1 - 2 + barHtScale_phys * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ + '' i 1 using (0):(0):(-1 - 3):(-1 - 3 + barHtScale_phys * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ + '' i 0 using (0):(0):(-1 - 4):(-1 - 4 + barHtScale_phys * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ + '' i 3 using (-1 - 1 + barHtScale_phys * $3):2 notitle with steps lc rgb "black" lw 0.3, \ + '' i 2 using (-1 - 2 + barHtScale_phys * $3):2 notitle with steps lc rgb "black" lw 0.3, \ + '' i 1 using (-1 - 3 + barHtScale_phys * $3):2 notitle with steps lc rgb "black" lw 0.3, \ + '' i 0 using (-1 - 4 + barHtScale_phys * $3):2 notitle with steps lc rgb "black" lw 0.3, \ +\ + '' i 10 using (0):(0):( 0):( 0 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ + '' i 11 using (0):(0):( 1):( 1 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ + '' i 12 using (0):(0):( 2):( 2 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ + '' i 13 using (0):(0):( 3):( 3 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ + '' i 14 using (0):(0):( 4):( 4 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ + '' i 15 using (0):(0):( 5):( 5 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ + '' i 4 using (0):(0):( 6):( 6 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ + '' i 5 using (0):(0):( 7):( 7 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ + '' i 6 using (0):(0):( 8):( 8 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ + '' i 7 using (0):(0):( 9):( 9 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ + '' i 8 using (0):(0):(10):(10 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ + '' i 9 using (0):(0):(11):(11 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ + '' i 10 using ( 0 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ + '' i 11 using ( 1 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ + '' i 12 using ( 2 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ + '' i 13 using ( 3 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ + '' i 14 using ( 4 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ + '' i 15 using ( 5 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ + '' i 4 using ( 6 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ + '' i 5 using ( 7 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ + '' i 6 using ( 8 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ + '' i 7 using ( 9 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ + '' i 8 using (10 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ + '' i 9 using (11 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ +\ + '' i 16 using (0):(0):(1 + 12):(1 + 12 + barHtScale_fx * $3):1:2 title columnheader(1) with boxxyerror fc rgb "blue" fs transparent solid 0.15 noborder, \ + '' i 19 using (0):(0):(1 + 13):(1 + 13 + barHtScale_fx * $3):1:2 title columnheader(1) with boxxyerror fc rgb "dark-orange" fs transparent solid 0.15 noborder, \ + '' i 18 using (0):(0):(1 + 14):(1 + 14 + barHtScale_fx * $3):1:2 title columnheader(1) with boxxyerror fc rgb "magenta" fs transparent solid 0.15 noborder, \ + '' i 17 using (0):(0):(1 + 15):(1 + 15 + 3.5 * barHtScale_fx * $3):1:2 title columnheader(1) with boxxyerror fc rgb "purple" fs transparent solid 0.35 noborder, \ + '' i 16 using (1 + 12 + barHtScale_fx * $3):2 notitle with steps lc rgb "blue" lw 0.3, \ + '' i 19 using (1 + 13 + barHtScale_fx * $3):2 notitle with steps lc rgb "dark-orange" lw 0.3, \ + '' i 18 using (1 + 14 + barHtScale_fx * $3):2 notitle with steps lc rgb "magenta" lw 0.3, \ + '' i 17 using (1 + 15 + 3.5 * barHtScale_fx * $3):2 notitle with steps lc rgb "purple" lw 0.3 + Index: doc/theses/mike_brooks_MMath/plots/list-1ord.py =================================================================== --- doc/theses/mike_brooks_MMath/plots/list-1ord.py (revision e8a7b66dfa975451475c2e36363c47605ebfcb74) +++ doc/theses/mike_brooks_MMath/plots/list-1ord.py (revision e8a7b66dfa975451475c2e36363c47605ebfcb74) @@ -0,0 +1,35 @@ +import pandas as pd +import numpy as np +import os +import sys + +sys.path.insert(0, os.path.dirname(__file__)) +from ListCommon import * + +physicals = ['machine', 'SizeZone'] +ops = ['movement', 'polarity', 'accessor'] +fx = ['fx'] +bkgnd = ['NumNodes'] # never drilled/marginalized, always conditioned + +assert( set( explanations ) + - set( ['InterleaveFrac'] ) # unused and always zero + == + set(physicals) | set(ops) | set(fx) | set(bkgnd) ) + +printHistos( + tgtMovement = 'all', + tgtPolarity = 'all', + tgtAccessor = 'all', + drillOn=physicals ) + +printHistos( + tgtMovement = 'all', + tgtPolarity = 'all', + tgtAccessor = 'all', + drillOn=ops ) + +printHistos( + tgtMovement = 'all', + tgtPolarity = 'all', + tgtAccessor = 'all', + drillOn=fx ) Index: c/theses/mike_brooks_MMath/plots/list-op-fx.d =================================================================== --- doc/theses/mike_brooks_MMath/plots/list-op-fx.d (revision e2e927eec770a0ff2d35ee0a0ec54765732411c3) +++ (revision ) @@ -1,2 +1,0 @@ -plots/list-op-fx.gp.INPUTS: build/plot-list-op-fx.dat | build -plots/list-op-fx.py.INPUTS: benchmarks/list/results-swift-general.csv Index: c/theses/mike_brooks_MMath/plots/list-op-fx.gp =================================================================== --- doc/theses/mike_brooks_MMath/plots/list-op-fx.gp (revision e2e927eec770a0ff2d35ee0a0ec54765732411c3) +++ (revision ) @@ -1,98 +1,0 @@ -set terminal pdfcairo color enhanced size 6.5in,3.0in font "Times,17" - -set size 1.0, 1.0 # scale of plot area inside terminal -set origin 0.0, 0.0 # bottom-left corner - -INDIR="build" -OUTDIR="build" - -set macros -set output OUTDIR."/plot-list-op-fx.pdf" - -set lmargin 10 -set bmargin 5 - -set grid -set nokey -set logscale y 2 -set yrange [0.4:3.0]; -set ytics ( \ - "+40%%" 1.666666667, \ - "+30%%" 1.428571429, \ - "+20%%" 1.25, \ - "+10%%" 1.111111111, \ - "0" 1, \ - "-20%%" 0.833333333, \ - "-40%%" 0.714285714, \ - "-60%%" 0.625, \ - "-80%%" 0.555555556, \ - "-100%%" 0.5, \ - "-130%%" 0.434782609, \ - "-160%%" 0.384615385, \ - "-200%%" 0.333333333 \ -) -set xrange [-0.5:17.5]; -set xlabel "Operation; Prevalence Framework; Prevalence" offset 7,-1 -set xtics ( \ - "I" 0, \ - "II" 1, \ - "III" 2, \ - "IV" 3, \ - "V" 4, \ - "VI" 5, \ - "VII" 6, \ - "VIII" 7, \ - "IX" 8, \ - "X" 9, \ - "XI" 10, \ - "XII" 11, \ -\ - "cfa" 13, \ - "upp" 14, \ - "lq\ntailq" 15, \ - "lq\nlist" 16, \ -) - -set ylabel "Duration (relative)" offset -1.0,0 -set errorbars 2.0 -set pointintervalbox 0 - -barHtScale_op = 0.1 -barHtScale_fx = 0.05 - - -plot INDIR."/plot-list-op-fx.dat" \ - i 6 using (0):(0):( 0):( 0 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ - '' i 7 using (0):(0):( 1):( 1 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ - '' i 8 using (0):(0):( 2):( 2 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ - '' i 9 using (0):(0):( 3):( 3 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ - '' i 10 using (0):(0):( 4):( 4 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ - '' i 11 using (0):(0):( 5):( 5 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ - '' i 0 using (0):(0):( 6):( 6 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ - '' i 1 using (0):(0):( 7):( 7 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ - '' i 2 using (0):(0):( 8):( 8 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ - '' i 3 using (0):(0):( 9):( 9 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ - '' i 4 using (0):(0):(10):(10 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ - '' i 5 using (0):(0):(11):(11 + barHtScale_op * $3):1:2 title columnheader(1) with boxxyerror fc rgb "black" fs transparent solid 0.15 noborder, \ - '' i 6 using ( 0 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ - '' i 7 using ( 1 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ - '' i 8 using ( 2 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ - '' i 9 using ( 3 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ - '' i 10 using ( 4 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ - '' i 11 using ( 5 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ - '' i 0 using ( 6 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ - '' i 1 using ( 7 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ - '' i 2 using ( 8 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ - '' i 3 using ( 9 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ - '' i 4 using (10 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ - '' i 5 using (11 + barHtScale_op * $3):2 notitle with steps lc rgb "black" lw 0.3, \ -\ - '' i 12 using (0):(0):(1 + 12):(1 + 12 + barHtScale_fx * $3):1:2 title columnheader(1) with boxxyerror fc rgb "blue" fs transparent solid 0.15 noborder, \ - '' i 15 using (0):(0):(1 + 13):(1 + 13 + barHtScale_fx * $3):1:2 title columnheader(1) with boxxyerror fc rgb "dark-orange" fs transparent solid 0.15 noborder, \ - '' i 14 using (0):(0):(1 + 14):(1 + 14 + barHtScale_fx * $3):1:2 title columnheader(1) with boxxyerror fc rgb "magenta" fs transparent solid 0.15 noborder, \ - '' i 13 using (0):(0):(1 + 15):(1 + 15 + 3.5 * barHtScale_fx * $3):1:2 title columnheader(1) with boxxyerror fc rgb "purple" fs transparent solid 0.35 noborder, \ - '' i 12 using (1 + 12 + barHtScale_fx * $3):2 notitle with steps lc rgb "blue" lw 0.3, \ - '' i 15 using (1 + 13 + barHtScale_fx * $3):2 notitle with steps lc rgb "dark-orange" lw 0.3, \ - '' i 14 using (1 + 14 + barHtScale_fx * $3):2 notitle with steps lc rgb "magenta" lw 0.3, \ - '' i 13 using (1 + 15 + 3.5 * barHtScale_fx * $3):2 notitle with steps lc rgb "purple" lw 0.3 - Index: c/theses/mike_brooks_MMath/plots/list-op-fx.py =================================================================== --- doc/theses/mike_brooks_MMath/plots/list-op-fx.py (revision e2e927eec770a0ff2d35ee0a0ec54765732411c3) +++ (revision ) @@ -1,29 +1,0 @@ -import pandas as pd -import numpy as np -import os -import sys - -sys.path.insert(0, os.path.dirname(__file__)) -from ListCommon import * - -conditionOnBase = ['machine', 'NumNodes', 'SizeZone'] # physicals -drillOn1 = ['movement', 'polarity', 'accessor'] -drillOn2 = ['fx'] - -assert( set( explanations ) - - set( ['InterleaveFrac'] ) # unused and always zero - == - set(conditionOnBase ) | - set(drillOn1) | set(drillOn2) ) - -printHistos( - tgtMovement = 'all', - tgtPolarity = 'all', - tgtAccessor = 'all', - drillOn=drillOn1 ) - -printHistos( - tgtMovement = 'all', - tgtPolarity = 'all', - tgtAccessor = 'all', - drillOn=drillOn2 )