Index: doc/theses/mike_brooks_MMath/Makefile =================================================================== --- doc/theses/mike_brooks_MMath/Makefile (revision 379b6ea2877f786ddcc4f854aef2c757966b114d) +++ doc/theses/mike_brooks_MMath/Makefile (revision b1c220a2399317045242cbfc0393a483f0424241) @@ -87,9 +87,9 @@ $< > $@ -string-graph-peq-cppemu.pdf: string-graph-peq-cppemu.dat plot-peg-cppemu.gp | ${Build} - gnuplot plot-peg-cppemu.gp +string-graph-peq-cppemu.pdf: string-graph-peq-cppemu.dat plot-peq-cppemu.gp | ${Build} + gnuplot plot-peq-cppemu.gp -string-graph-peq-sharing.pdf: string-graph-peq-sharing.dat plot-peg-sharing.gp | ${Build} - gnuplot plot-peg-sharing.gp +string-graph-peq-sharing.pdf: string-graph-peq-sharing.dat plot-peq-sharing.gp | ${Build} + gnuplot plot-peq-sharing.gp string-graph-pta-sharing.pdf: string-graph-pta-sharing.dat plot-pta-sharing.gp | ${Build} Index: doc/theses/mike_brooks_MMath/pictures/string-graph-pbv.dat =================================================================== --- doc/theses/mike_brooks_MMath/pictures/string-graph-pbv.dat (revision 379b6ea2877f786ddcc4f854aef2c757966b114d) +++ doc/theses/mike_brooks_MMath/pictures/string-graph-pbv.dat (revision b1c220a2399317045242cbfc0393a483f0424241) @@ -1,3 +1,3 @@ -"cfa-ll-share-na" +"{/Helvetica=15 C{/Symbol \42}} share" 1 17.7 2 17.3 @@ -11,5 +11,5 @@ -"cfa-ll-noshare-na" +"{/Helvetica=15 C{/Symbol \42}} noshare" 1 181.9 2 181.8 @@ -23,5 +23,5 @@ -"stl-na-na-na" +"STL" 1 7.9 2 12.4 Index: doc/theses/mike_brooks_MMath/pictures/string-graph-peq-cppemu.dat =================================================================== --- doc/theses/mike_brooks_MMath/pictures/string-graph-peq-cppemu.dat (revision 379b6ea2877f786ddcc4f854aef2c757966b114d) +++ doc/theses/mike_brooks_MMath/pictures/string-graph-peq-cppemu.dat (revision b1c220a2399317045242cbfc0393a483f0424241) @@ -1,3 +1,15 @@ -"cfa-ll-noshare-reuse" +"{/Helvetica=15 C{/Symbol \42} +=} noshare fresh" +1 21.4 +2 26.5 +5 29.8 +10 31.3 +20 33.6 +50 41.3 +100 55.3 +200 63.7 +500 117.4 + + +"{/Helvetica=15 C{/Symbol \42} +=} noshare reuse" 1 16.3 2 19.2 @@ -11,17 +23,17 @@ -"cfa-ll-noshare-fresh" -1 21.4 -2 26.5 -5 29.8 -10 31.3 -20 33.6 -50 41.3 -100 55.3 -200 63.7 -500 117.4 +"STL {/Helvetica=15 +=} fresh" +1 14.4 +2 20.2 +5 25.8 +10 26.7 +20 29.9 +50 37.4 +100 49.3 +200 59.6 +500 114.5 -"stl-na-na-reuse" +"STL {/Helvetica=15 +=} reuse" 1 11.6 2 14.6 @@ -33,14 +45,2 @@ 200 39.4 500 73.9 - - -"stl-na-na-fresh" -1 14.4 -2 20.2 -5 25.8 -10 26.7 -20 29.9 -50 37.4 -100 49.3 -200 59.6 -500 114.5 Index: doc/theses/mike_brooks_MMath/pictures/string-graph-peq-sharing.dat =================================================================== --- doc/theses/mike_brooks_MMath/pictures/string-graph-peq-sharing.dat (revision 379b6ea2877f786ddcc4f854aef2c757966b114d) +++ doc/theses/mike_brooks_MMath/pictures/string-graph-peq-sharing.dat (revision b1c220a2399317045242cbfc0393a483f0424241) @@ -1,3 +1,15 @@ -"cfa-ll-share-reuse" +"{/Helvetica=15 C{/Symbol \42} +=} share fresh" +1 16.3 +2 21.1 +5 23.0 +10 23.1 +20 26.3 +50 30.3 +100 39.9 +200 50.3 +500 79.2 + + +"{/Helvetica=15 C{/Symbol \42} +=} share reuse" 1 17.4 2 21.5 @@ -11,17 +23,17 @@ -"cfa-ll-share-fresh" -1 16.3 -2 21.1 -5 23.0 -10 23.1 -20 26.3 -50 30.3 -100 39.9 -200 50.3 -500 79.2 +"STL {/Helvetica=15 +=} fresh" +1 14.4 +2 20.2 +5 25.8 +10 26.7 +20 29.9 +50 37.4 +100 49.3 +200 59.6 +500 114.5 -"stl-na-na-reuse" +"STL {/Helvetica=15 +=} reuse" 1 11.6 2 14.6 @@ -33,14 +45,2 @@ 200 39.4 500 73.9 - - -"stl-na-na-fresh" -1 14.4 -2 20.2 -5 25.8 -10 26.7 -20 29.9 -50 37.4 -100 49.3 -200 59.6 -500 114.5 Index: doc/theses/mike_brooks_MMath/pictures/string-graph-pta-sharing.dat =================================================================== --- doc/theses/mike_brooks_MMath/pictures/string-graph-pta-sharing.dat (revision 379b6ea2877f786ddcc4f854aef2c757966b114d) +++ doc/theses/mike_brooks_MMath/pictures/string-graph-pta-sharing.dat (revision b1c220a2399317045242cbfc0393a483f0424241) @@ -1,3 +1,3 @@ -"perfexp-cfa-peq-ll-share-fresh" +"{/Helvetica=15 C{/Symbol \42} +=} share fresh" 1 16.3 2 21.1 @@ -11,5 +11,5 @@ -"perfexp-cfa-pta-ll-share-fresh" +"{/Helvetica=15 C{/Symbol \42} x = x + y} share fresh" 1 44.1 2 49.1 @@ -23,5 +23,5 @@ -"perfexp-stl-peq-na-na-fresh" +"STL {/Helvetica=15 +=} fresh" 1 14.4 2 20.2 @@ -35,5 +35,17 @@ -"perfexp-stl-peq-na-na-reuse" +"STL {/Helvetica=15 x = x + y} fresh" +1 174.5 +2 189.3 +5 214.9 +10 223.7 +20 292.1 +50 404.7 +100 789.1 +200 1267.1 +500 3643.8 + + +"STL {/Helvetica=15 +=} reuse" 1 11.6 2 14.6 @@ -45,14 +57,2 @@ 200 39.4 500 73.9 - - -"perfexp-stl-pta-na-na-fresh" -1 174.5 -2 189.3 -5 214.9 -10 223.7 -20 292.1 -50 404.7 -100 789.1 -200 1267.1 -500 3643.8 Index: c/theses/mike_brooks_MMath/plot-peg-cppemu.gp =================================================================== --- doc/theses/mike_brooks_MMath/plot-peg-cppemu.gp (revision 379b6ea2877f786ddcc4f854aef2c757966b114d) +++ (revision ) @@ -1,23 +1,0 @@ -set terminal pdf color enhanced size 6.0in,3.0in font "Times,17" -#set terminal postscript portrait enhanced size 7.5, 10. color solid 9.5; -#set terminal wxt size 950,1250 - -DIR="pictures" - -set macros -set output "build/string-graph-peq-cppemu.pdf" -#set pointsize 2.0 -set grid -set key top left -set xtics (1,2,5,10,20,50,100,200,500) -set logscale x -#set logscale y 2 -set xlabel "String Length being appended (mean, geo. dist.), log scale" offset 2,0 -set ylabel "Time per append (ns, mean)" -set linetype 3 dashtype 2 -set linetype 4 dashtype 2 -plot DIR."/string-graph-peq-cppemu.dat" \ - i 0 using 1:2 title columnheader(1) with linespoints lt rgb "blue" pt 2 ps 1 lw 1, \ - '' i 1 using 1:2 title columnheader(1) with linespoints lt rgb "red" pt 3 ps 1 lw 1, \ - '' i 2 using 1:2 title columnheader(1) with linespoints lt rgb "blue" pt 6 ps 1 lw 1, \ - '' i 3 using 1:2 title columnheader(1) with linespoints lt rgb "red" pt 8 ps 1 lw 1 Index: c/theses/mike_brooks_MMath/plot-peg-sharing.gp =================================================================== --- doc/theses/mike_brooks_MMath/plot-peg-sharing.gp (revision 379b6ea2877f786ddcc4f854aef2c757966b114d) +++ (revision ) @@ -1,23 +1,0 @@ -set terminal pdf color enhanced size 6.0in,3.0in font "Times,17" -#set terminal postscript portrait enhanced size 7.5, 10. color solid 9.5; -#set terminal wxt size 950,1250 - -DIR="pictures" - -set macros -set output "build/string-graph-peq-sharing.pdf" -#set pointsize 2.0 -set grid -set key top left -set xtics (1,2,5,10,20,50,100,200,500) -set logscale x -#set logscale y 2 -set xlabel "String Length being appended (mean, geo. dist.), log scale" offset 2,0 -set ylabel "Time per append (ns, mean)" -set linetype 3 dashtype 2 -set linetype 4 dashtype 2 -plot DIR."/string-graph-peq-sharing.dat" \ - i 0 using 1:2 title columnheader(1) with linespoints lt rgb "blue" pt 2 ps 1 lw 1, \ - '' i 1 using 1:2 title columnheader(1) with linespoints lt rgb "red" pt 3 ps 1 lw 1, \ - '' i 2 using 1:2 title columnheader(1) with linespoints lt rgb "blue" pt 6 ps 1 lw 1, \ - '' i 3 using 1:2 title columnheader(1) with linespoints lt rgb "red" pt 8 ps 1 lw 1 Index: doc/theses/mike_brooks_MMath/plot-peq-cppemu.gp =================================================================== --- doc/theses/mike_brooks_MMath/plot-peq-cppemu.gp (revision b1c220a2399317045242cbfc0393a483f0424241) +++ doc/theses/mike_brooks_MMath/plot-peq-cppemu.gp (revision b1c220a2399317045242cbfc0393a483f0424241) @@ -0,0 +1,23 @@ +set terminal pdf color enhanced size 6.0in,3.0in font "Times,17" +#set terminal postscript portrait enhanced size 7.5, 10. color solid 9.5; +#set terminal wxt size 950,1250 + +DIR="pictures" + +set macros +set output "build/string-graph-peq-cppemu.pdf" +#set pointsize 2.0 +set grid +set key top left +set xtics (1,2,5,10,20,50,100,200,500) +set logscale x +#set logscale y 2 +set xlabel "String Length being appended (mean, geo. dist.), log scale" offset 2,0 +set ylabel "Time per append (ns, mean)" +set linetype 2 dashtype 2 +set linetype 4 dashtype 2 +plot DIR."/string-graph-peq-cppemu.dat" \ + i 0 using 1:2 title columnheader(1) with linespoints lt rgb "red" pt 2 ps 1 lw 1, \ + '' i 1 using 1:2 title columnheader(1) with linespoints lt rgb "red" pt 3 ps 1 lw 1, \ + '' i 2 using 1:2 title columnheader(1) with linespoints lt rgb "blue" pt 6 ps 1 lw 1, \ + '' i 3 using 1:2 title columnheader(1) with linespoints lt rgb "blue" pt 8 ps 1 lw 1 Index: doc/theses/mike_brooks_MMath/plot-peq-sharing.gp =================================================================== --- doc/theses/mike_brooks_MMath/plot-peq-sharing.gp (revision b1c220a2399317045242cbfc0393a483f0424241) +++ doc/theses/mike_brooks_MMath/plot-peq-sharing.gp (revision b1c220a2399317045242cbfc0393a483f0424241) @@ -0,0 +1,23 @@ +set terminal pdf color enhanced size 6.0in,3.0in font "Times,17" +#set terminal postscript portrait enhanced size 7.5, 10. color solid 9.5; +#set terminal wxt size 950,1250 + +DIR="pictures" + +set macros +set output "build/string-graph-peq-sharing.pdf" +#set pointsize 2.0 +set grid +set key top left +set xtics (1,2,5,10,20,50,100,200,500) +set logscale x +#set logscale y 2 +set xlabel "String Length being appended (mean, geo. dist.), log scale" offset 2,0 +set ylabel "Time per append (ns, mean)" +set linetype 2 dashtype 2 +set linetype 4 dashtype 2 +plot DIR."/string-graph-peq-sharing.dat" \ + i 0 using 1:2 title columnheader(1) with linespoints lt rgb "red" pt 2 ps 1 lw 1, \ + '' i 1 using 1:2 title columnheader(1) with linespoints lt rgb "red" pt 3 ps 1 lw 1, \ + '' i 2 using 1:2 title columnheader(1) with linespoints lt rgb "blue" pt 6 ps 1 lw 1, \ + '' i 3 using 1:2 title columnheader(1) with linespoints lt rgb "blue" pt 8 ps 1 lw 1 Index: doc/theses/mike_brooks_MMath/plot-pta-sharing.gp =================================================================== --- doc/theses/mike_brooks_MMath/plot-pta-sharing.gp (revision 379b6ea2877f786ddcc4f854aef2c757966b114d) +++ doc/theses/mike_brooks_MMath/plot-pta-sharing.gp (revision b1c220a2399317045242cbfc0393a483f0424241) @@ -15,10 +15,10 @@ set xlabel "String Length being appended (mean, geo. dist.), log scale" offset 2,0 set ylabel "Time per append (ns, mean), log_{2} scale" -set linetype 3 dashtype 2 -set linetype 4 dashtype 2 +set linetype 5 dashtype 2 +#show colornames plot DIR."/string-graph-pta-sharing.dat" \ - i 0 using 1:2 title columnheader(1) with linespoints lt rgb "blue" pt 2 ps 1 lw 1, \ - '' i 1 using 1:2 title columnheader(1) with linespoints lt rgb "red" pt 3 ps 1 lw 1, \ + i 0 using 1:2 title columnheader(1) with linespoints lt rgb "red" pt 2 ps 1 lw 1, \ + '' i 1 using 1:2 title columnheader(1) with linespoints lt rgb "dark-green" pt 4 ps 1 lw 1, \ '' i 2 using 1:2 title columnheader(1) with linespoints lt rgb "blue" pt 6 ps 1 lw 1, \ - '' i 3 using 1:2 title columnheader(1) with linespoints lt rgb "red" pt 8 ps 1 lw 1, \ - '' i 4 using 1:2 title columnheader(1) with linespoints lt rgb "black" pt 10 ps 1 lw 1 + '' i 3 using 1:2 title columnheader(1) with linespoints lt rgb "dark-green" pt 12 ps 1 lw 1, \ + '' i 4 using 1:2 title columnheader(1) with linespoints lt rgb "blue" pt 8 ps 1 lw 1 Index: doc/theses/mike_brooks_MMath/string.tex =================================================================== --- doc/theses/mike_brooks_MMath/string.tex (revision 379b6ea2877f786ddcc4f854aef2c757966b114d) +++ doc/theses/mike_brooks_MMath/string.tex (revision b1c220a2399317045242cbfc0393a483f0424241) @@ -459,10 +459,12 @@ There are tradeoffs associated with the copy-on-write mechanism. -Several qualitative matters are detailed in the \VRef{s:PerformanceAssessment} and the qualitative issue of multi-threaded support is introduced here. -The \CFA sting library provides a switch to disable the sharing mechanism for situations where it is inappropriate. - -Because of the inter-linked string handles, any participant managing one string is also managing, directly, the neighbouring strings, and from there, a data structure of the ``set of all strings.'' This data structure is intended for sequential access. -A negative consequence of this decision is that multiple threads using strings need to be set up so that they avoid attempting to modify (concurrently) an instance of this structure. -A positive consequence is that a single-threaded program, or a program with several independent threads, can use the sharing context without locking overhead. +Several qualitative matters are detailed in \VRef{s:PerformanceAssessment} and the qualitative issue of multi-threaded support is introduced here. +The \CFA string library provides a switch to disable threads allocating from the string buffer, when string sharing is unsafe. +When toggled, string management is moved to the storage allocator, specifically @malloc@/@free@, where the storage allocator is assumed to be thread-safe. + +In detail, string sharing has inter-linked string handles, so any participant managing one string is also managing, directly, the neighbouring strings, and from there, a data structure of the ``set of all strings.'' +This string structure is intended for sequential access. +Hence, multiple threads using shared strings need to avoid modifying (concurrently) an instance of this structure (like Java immutable strings). +A positive consequence of this approach is that independent threads can use the sharing buffer without locking overhead. When the string library is running with sharing disabled, it runs without implicit thread-safety challenges, which is the same as the \CC STL, and with performance goals similar to the STL. @@ -470,5 +472,5 @@ Hence, concurrent users of string objects must still bring their own mutual exclusion, but the string library does not add any cross thread uses that are not apparent in a user's code. -The \CFA string library provides the type @string_sharectx@to control an ambient sharing context for the current thread. +The \CFA string library provides the type @string_sharectx@ to control an ambient sharing context for a current thread. It allows two adjustments: to opt out of sharing entirely or to begin sharing within a private context. Either way, the chosen mode applies only to the current thread, for the duration of the lifetime of the created @string_sharectx@ object, up to being suspended by child lifetimes of different contexts. @@ -492,5 +494,5 @@ \lstinputlisting[language=CFA, firstline=10, lastline=55]{sharectx.run.cfa} & - \includegraphics{string-sharectx.pdf} + \raisebox{-0.17\totalheight}{\includegraphics{string-sharectx.pdf}} % lower \end{tabular} \caption{Controlling copying vs sharing of strings using \lstinline{string_sharectx}.} @@ -519,5 +521,5 @@ To discuss: general goal of ... -while STL makes you think about memory management, all the time, and if you do your performance can be great ... +while STL makes you think about memory management, all the time, and if you do, your performance can be great ... \CFA sacrifices this advantage modestly in exchange for big wins when you're not thinking about memory management. [Does this position cover all of it?] @@ -530,5 +532,5 @@ \subsection{Methodology} -These tests use randomly generated text fragments of varying lengths. +These tests use randomly generated varying-length strings (string content is immaterial). A collection of such fragments is a \emph{corpus}. The mean length of a fragment from a corpus is a typical explanatory variable. @@ -540,6 +542,6 @@ \end{description} The geometric distribution implies that lengths much longer than the mean occur frequently. -The special treatment of length 16 deals with comparison to STL, given that STL has short-string optimization (see [TODO: write and cross-ref future-work SSO]), currently not implemented in \CFA. -When success, notwithstanding SSO, is illustrated, a fixed-size or from-16 distribution ensures that extra-optimized cases are not part of the mix on the STL side. +The special treatment of length 16 deals with comparison to STL, given that STL has a short-string optimization (see [TODO: write and cross-ref future-work SSO]), currently not implemented in \CFA. +When success is illustrated, notwithstanding SSO, a fixed-size or from-16 distribution ensures that extra-optimized cases are not part of the mix on the STL side. In all experiments that use a corpus, its text is generated and loaded into the SUT before the timed phase begins. @@ -564,12 +566,13 @@ Another experimental variable is whether the user's logical allocation is fresh \vs reused. -Here, \emph{reusing a logical allocation}, means that the program variable, into which the user is concatenating, previously held a long string:\\ +Here, \emph{reusing a logical allocation}, means that the program variable, into which the user is concatenating, previously held a long string: \begin{cquote} \setlength{\tabcolsep}{20pt} \begin{tabular}{@{}ll@{}} +\multicolumn{1}{c}{\textbf{fresh}} & \multicolumn{1}{c}{\textbf{reuse}} \\ \begin{cfa} for ( ... ) { - @string x;@ // fresh + @string x;@ for ( ... ) x += ... @@ -580,5 +583,5 @@ string x; for ( ... ) { - @x = "";@ // reused + @x = "";@ for ( ... ) x += ... @@ -587,5 +590,6 @@ \end{tabular} \end{cquote} -These benchmark drivers have an outer loop for ``until a sample-worthy amount of execution has happened'' and an inner loop for ``build up the desired-length string.'' + +All benchmark drivers have an outer loop for ``until a sample-worthy amount of execution has happened'' and an inner loop for ``building up the desired-length string.'' In general, a user should not have to care about this difference, yet the STL performs differently in these cases. Furthermore, if a routine takes a string by reference, if cannot use the fresh approach. @@ -593,11 +597,4 @@ For the STL, this cost includes obtaining a fresh buffer from the memory allocator and copying older characters into the new buffer, while \CFA-sharing hides such a cost entirely. The fresh \vs reuse distinction is only relevant in the \emph{append} tests. - -The \emph{append} tests use the varying-from-1 corpus construction, \ie they do not assume away the STL's advantage for small-string optimization. -\PAB{To discuss: any other case variables introduced in the performance intro} -\VRef[Figure]{fig:string-graph-peq-cppemu} shows this behaviour, by the STL and by \CFA in STL emulation mode. -\CFA reproduces STL's performance, up to a 15\% penalty averaged over the cases shown, diminishing with larger strings, and 50\% in the worst case. -This penalty characterizes the amount of implementation fine tuning done with STL and not done with \CFA in present state. -The larger inherent penalty, for a user mismanaging reuse, is 40\% averaged over the cases shown, is minimally 24\%, shows up consistently between the STL and \CFA implementations, and increases with larger strings. \begin{figure} @@ -609,4 +606,11 @@ \end{figure} +The \emph{append} tests use the varying-from-1 corpus construction, \ie they assume the STL's advantage of small-string optimization. +\PAB{To discuss: any other case variables introduced in the performance intro} +\VRef[Figure]{fig:string-graph-peq-cppemu} shows this behaviour, by the STL and by \CFA in STL emulation mode. +\CFA reproduces STL's performance, up to a 15\% penalty averaged over the cases shown, diminishing with larger strings, and 50\% in the worst case. +This penalty characterizes the amount of implementation fine tuning done with STL and not done with \CFA in present state. +\PAB{The larger inherent penalty, for a user mismanaging reuse, is 40\% averaged over the cases shown, is minimally 24\%, shows up consistently between the STL and \CFA implementations, and increases with larger strings.} + \begin{figure} \centering @@ -624,5 +628,5 @@ \includegraphics{string-graph-pta-sharing.pdf} % \includegraphics[width=\textwidth]{string-graph-pta-sharing.png} - \caption{Average time per iteration (lower is better) with one \lstinline{x = x + y} invocation (new, purple bands), comparing \CFA (having implicit sharing activated) with STL. + \caption{Average time per iteration (lower is better) with one \lstinline{x = x + y} invocation, comparing \CFA (having implicit sharing activated) with STL. For context, the results from \VRef[Figure]{fig:string-graph-peq-sharing} are repeated as the bottom bands. While not a design goal, and not graphed out, \CFA in STL-emulation mode outperformed STL in this case; user-managed allocation reuse did not affect any of the implementations in this case.} @@ -637,5 +641,9 @@ To have introduced: STL string library forces users to think about memory management when communicating values across a function call - +\begin{cfa} +void foo( string s ); +string s = "abc"; +foo( s ); +\end{cfa} STL charges a prohibitive penalty for passing a string by value. With implicit sharing active, \CFA treats this operation as normal and supported. @@ -657,5 +665,5 @@ STL's performance worsens as string length increases, while \CFA has the same performance at all sizes. -The \CFA cost to pass is nontrivial. +The \CFA cost to pass a string is nontrivial. The contributor is adding and removing the callee's string handle from the global list. This cost is $1.5 \times$ to $2 \times$ over STL's when small-string optimization applies, though this cost should be avoidable in the same case, given a \CFA realization of this optimization.