Index: doc/theses/mike_brooks_MMath/Makefile =================================================================== --- doc/theses/mike_brooks_MMath/Makefile (revision b195498ca6cf118ea16f39c6f8feaf910d504d33) +++ doc/theses/mike_brooks_MMath/Makefile (revision f85de474d7bae82407a8ea5f1551da282d77d9bd) @@ -2,5 +2,8 @@ Build = build + +Benchmarks = benchmarks Pictures = pictures +Plots = plots Programs = programs @@ -11,6 +14,10 @@ PicSRC = ${notdir ${wildcard ${Pictures}/*.png}} ${notdir ${wildcard ${Pictures}/*.fig}} PicSRC := ${PicSRC:.fig=.pdf} # substitute ".fig" with ".pdf" -GraphSRC = ${notdir ${wildcard ${Pictures}/*.dat}} -GraphSRC := ${GraphSRC:.dat=.pdf} # substitute ".dat" with ".pdf" +GraphSRC_OLD = ${notdir ${wildcard ${Pictures}/*.dat}} +GraphSRC_OLD := ${GraphSRC_OLD:.dat=.pdf} # substitute ".dat" with ".pdf" +PlotINPUTS = ${wildcard ${Plots}/*.gp} ${wildcard ${Plots}/*.py} +PlotINPUTS := ${addsuffix .INPUTS,${PlotINPUTS}} +PlotSRC = ${notdir ${wildcard ${Plots}/*.gp}} +PlotSRC := ${addprefix ${Build}/plot-,${PlotSRC:.gp=.pdf}} # substitute ".gp" with ".pdf" DemoPgmSRC = ${notdir ${wildcard ${Programs}/*-demo.cfa}} PgmSRC = ${notdir ${wildcard ${Programs}/*}} @@ -42,5 +49,5 @@ # Rules and Recipes -.PHONY : all clean # not file names +.PHONY : all clean # not file names .SECONDARY: #.PRECIOUS : ${Build}/% # don't delete intermediates @@ -54,7 +61,7 @@ # File Dependencies -${DOCUMENT}: ${TeXSRC} $(RunPgmOut) ${DemoPgmOut} ${GraphSRC} ${PicSRC} ${BibSRC} ${BibRep}/pl.bib ${LaTMac}/common.tex Makefile | ${Build} +${DOCUMENT}: ${TeXSRC} $(RunPgmOut) ${DemoPgmOut} ${GraphSRC_OLD} ${PlotSRC} ${PicSRC} ${BibSRC} ${BibRep}/pl.bib ${LaTMac}/common.tex Makefile | ${Build} echo ${PicSRC} - echo ${GraphSRC} + echo ${GraphSRC_OLD} ${LaTeX} ${BASE} ${BibTeX} ${Build}/${BASE} @@ -87,7 +94,4 @@ $< > $@ -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-peq-sharing.gp | ${Build} gnuplot plot-peq-sharing.gp @@ -105,3 +109,12 @@ fig2dev -L pdf $< > ${Build}/$@ +-include $(Plots)/string-peq-cppemu.d + +${Build}/plot-%.dat: ${Plots}/%.py ${Plots}/%.py.INPUTS | ${Build} + echo ${PlotINPUTS} + python3 $< > $@ + +${Build}/plot-%.pdf: ${Plots}/%.gp ${Plots}/%.gp.INPUTS | ${Build} + gnuplot $< + #-include ${Build}/*.d Index: doc/theses/mike_brooks_MMath/benchmarks/string/result-append-pbv.csv =================================================================== --- doc/theses/mike_brooks_MMath/benchmarks/string/result-append-pbv.csv (revision f85de474d7bae82407a8ea5f1551da282d77d9bd) +++ doc/theses/mike_brooks_MMath/benchmarks/string/result-append-pbv.csv (revision f85de474d7bae82407a8ea5f1551da282d77d9bd) @@ -0,0 +1,135 @@ +perfexp-cfa-pta-ll-share-reuse,corpus-100-1-1.txt,100,100,1.000000,219460000,10.000260 +perfexp-cfa-pta-ll-share-reuse,corpus-100-10-1.txt,100,100,9.500000,180250000,10.000486 +perfexp-cfa-pta-ll-share-reuse,corpus-100-100-1.txt,100,100,106.370000,152790000,10.000441 +perfexp-cfa-pta-ll-share-reuse,corpus-100-2-1.txt,100,100,2.030000,206090000,10.000311 +perfexp-cfa-pta-ll-share-reuse,corpus-100-20-1.txt,100,100,22.960000,184330000,10.000328 +perfexp-cfa-pta-ll-share-reuse,corpus-100-200-1.txt,100,100,177.280000,125090000,10.000138 +perfexp-cfa-pta-ll-share-reuse,corpus-100-5-1.txt,100,100,5.270000,199130000,10.000180 +perfexp-cfa-pta-ll-share-reuse,corpus-100-50-1.txt,100,100,43.320000,167720000,10.000327 +perfexp-cfa-pta-ll-share-reuse,corpus-100-500-1.txt,100,100,557.260000,93560000,10.001058 +perfexp-cfa-pta-ll-share-fresh,corpus-100-1-1.txt,100,100,1.000000,225090000,10.000393 +perfexp-cfa-pta-ll-share-fresh,corpus-100-10-1.txt,100,100,9.500000,196300000,10.000221 +perfexp-cfa-pta-ll-share-fresh,corpus-100-100-1.txt,100,100,106.370000,150670000,10.000337 +perfexp-cfa-pta-ll-share-fresh,corpus-100-2-1.txt,100,100,2.030000,206600000,10.000182 +perfexp-cfa-pta-ll-share-fresh,corpus-100-20-1.txt,100,100,22.960000,188400000,10.000199 +perfexp-cfa-pta-ll-share-fresh,corpus-100-200-1.txt,100,100,177.280000,125880000,10.000489 +perfexp-cfa-pta-ll-share-fresh,corpus-100-5-1.txt,100,100,5.270000,185930000,10.000231 +perfexp-cfa-pta-ll-share-fresh,corpus-100-50-1.txt,100,100,43.320000,170660000,10.000491 +perfexp-cfa-pta-ll-share-fresh,corpus-100-500-1.txt,100,100,557.260000,91520000,10.000640 +perfexp-cfa-pta-ll-noshare-reuse,corpus-100-1-1.txt,100,100,1.000000,146200000,10.000520 +perfexp-cfa-pta-ll-noshare-reuse,corpus-100-10-1.txt,100,100,9.500000,114140000,10.000734 +perfexp-cfa-pta-ll-noshare-reuse,corpus-100-100-1.txt,100,100,106.370000,17630000,10.000889 +perfexp-cfa-pta-ll-noshare-reuse,corpus-100-2-1.txt,100,100,2.030000,139700000,10.000460 +perfexp-cfa-pta-ll-noshare-reuse,corpus-100-20-1.txt,100,100,22.960000,71910000,10.000768 +perfexp-cfa-pta-ll-noshare-reuse,corpus-100-200-1.txt,100,100,177.280000,8540000,10.009186 +perfexp-cfa-pta-ll-noshare-reuse,corpus-100-5-1.txt,100,100,5.270000,129810000,10.000379 +perfexp-cfa-pta-ll-noshare-reuse,corpus-100-50-1.txt,100,100,43.320000,45280000,10.000006 +perfexp-cfa-pta-ll-noshare-reuse,corpus-100-500-1.txt,100,100,557.260000,3300000,10.021088 +perfexp-cfa-pta-ll-noshare-fresh,corpus-100-1-1.txt,100,100,1.000000,146050000,10.000551 +perfexp-cfa-pta-ll-noshare-fresh,corpus-100-10-1.txt,100,100,9.500000,102800000,10.000490 +perfexp-cfa-pta-ll-noshare-fresh,corpus-100-100-1.txt,100,100,106.370000,17060000,10.001677 +perfexp-cfa-pta-ll-noshare-fresh,corpus-100-2-1.txt,100,100,2.030000,137470000,10.000361 +perfexp-cfa-pta-ll-noshare-fresh,corpus-100-20-1.txt,100,100,22.960000,69520000,10.001142 +perfexp-cfa-pta-ll-noshare-fresh,corpus-100-200-1.txt,100,100,177.280000,8830000,10.010528 +perfexp-cfa-pta-ll-noshare-fresh,corpus-100-5-1.txt,100,100,5.270000,117120000,10.000681 +perfexp-cfa-pta-ll-noshare-fresh,corpus-100-50-1.txt,100,100,43.320000,42960000,10.001950 +perfexp-cfa-pta-ll-noshare-fresh,corpus-100-500-1.txt,100,100,557.260000,3220000,10.010203 +perfexp-cfa-peq-ll-share-reuse,corpus-100-1-1.txt,100,100,1.000000,583560000,10.000070 +perfexp-cfa-peq-ll-share-reuse,corpus-100-10-1.txt,100,100,9.500000,451400000,10.000013 +perfexp-cfa-peq-ll-share-reuse,corpus-100-100-1.txt,100,100,106.370000,253260000,10.000275 +perfexp-cfa-peq-ll-share-reuse,corpus-100-2-1.txt,100,100,2.030000,483580000,10.000140 +perfexp-cfa-peq-ll-share-reuse,corpus-100-20-1.txt,100,100,22.960000,396550000,10.000060 +perfexp-cfa-peq-ll-share-reuse,corpus-100-200-1.txt,100,100,177.280000,199760000,10.000416 +perfexp-cfa-peq-ll-share-reuse,corpus-100-5-1.txt,100,100,5.270000,454790000,10.000069 +perfexp-cfa-peq-ll-share-reuse,corpus-100-50-1.txt,100,100,43.320000,339690000,10.000243 +perfexp-cfa-peq-ll-share-reuse,corpus-100-500-1.txt,100,100,557.260000,123840000,10.000724 +perfexp-cfa-peq-ll-share-fresh,corpus-100-1-1.txt,100,100,1.000000,577650000,10.000157 +perfexp-cfa-peq-ll-share-fresh,corpus-100-10-1.txt,100,100,9.500000,445260000,10.000186 +perfexp-cfa-peq-ll-share-fresh,corpus-100-100-1.txt,100,100,106.370000,259650000,10.000273 +perfexp-cfa-peq-ll-share-fresh,corpus-100-2-1.txt,100,100,2.030000,485650000,10.000026 +perfexp-cfa-peq-ll-share-fresh,corpus-100-20-1.txt,100,100,22.960000,386150000,10.000120 +perfexp-cfa-peq-ll-share-fresh,corpus-100-200-1.txt,100,100,177.280000,197690000,10.000077 +perfexp-cfa-peq-ll-share-fresh,corpus-100-5-1.txt,100,100,5.270000,443650000,10.000006 +perfexp-cfa-peq-ll-share-fresh,corpus-100-50-1.txt,100,100,43.320000,339190000,10.000037 +perfexp-cfa-peq-ll-share-fresh,corpus-100-500-1.txt,100,100,557.260000,122740000,10.000753 +perfexp-cfa-peq-ll-noshare-reuse,corpus-100-1-1.txt,100,100,1.000000,595700000,10.000119 +perfexp-cfa-peq-ll-noshare-reuse,corpus-100-10-1.txt,100,100,9.500000,452000000,10.000055 +perfexp-cfa-peq-ll-noshare-reuse,corpus-100-100-1.txt,100,100,106.370000,280570000,10.000281 +perfexp-cfa-peq-ll-noshare-reuse,corpus-100-2-1.txt,100,100,2.030000,501040000,10.000073 +perfexp-cfa-peq-ll-noshare-reuse,corpus-100-20-1.txt,100,100,22.960000,422280000,10.000131 +perfexp-cfa-peq-ll-noshare-reuse,corpus-100-200-1.txt,100,100,177.280000,235640000,10.000126 +perfexp-cfa-peq-ll-noshare-reuse,corpus-100-5-1.txt,100,100,5.270000,461250000,10.000197 +perfexp-cfa-peq-ll-noshare-reuse,corpus-100-50-1.txt,100,100,43.320000,369020000,10.000057 +perfexp-cfa-peq-ll-noshare-reuse,corpus-100-500-1.txt,100,100,557.260000,135050000,10.000682 +perfexp-cfa-peq-ll-noshare-fresh,corpus-100-1-1.txt,100,100,1.000000,529900000,10.000150 +perfexp-cfa-peq-ll-noshare-fresh,corpus-100-10-1.txt,100,100,9.500000,408530000,10.000108 +perfexp-cfa-peq-ll-noshare-fresh,corpus-100-100-1.txt,100,100,106.370000,217530000,10.000334 +perfexp-cfa-peq-ll-noshare-fresh,corpus-100-2-1.txt,100,100,2.030000,463860000,10.000166 +perfexp-cfa-peq-ll-noshare-fresh,corpus-100-20-1.txt,100,100,22.960000,360110000,10.000008 +perfexp-cfa-peq-ll-noshare-fresh,corpus-100-200-1.txt,100,100,177.280000,176490000,10.000131 +perfexp-cfa-peq-ll-noshare-fresh,corpus-100-5-1.txt,100,100,5.270000,424710000,10.000106 +perfexp-cfa-peq-ll-noshare-fresh,corpus-100-50-1.txt,100,100,43.320000,290930000,10.000172 +perfexp-cfa-peq-ll-noshare-fresh,corpus-100-500-1.txt,100,100,557.260000,90430000,10.000065 +perfexp-cfa-pbv-ll-share-na,corpus-100-1-1.txt,xxx,100,1.000000,578040000,10.000159 +perfexp-cfa-pbv-ll-share-na,corpus-100-10-1.txt,xxx,100,9.500000,573200000,10.000098 +perfexp-cfa-pbv-ll-share-na,corpus-100-100-1.txt,xxx,100,106.370000,575160000,10.000149 +perfexp-cfa-pbv-ll-share-na,corpus-100-2-1.txt,xxx,100,2.030000,573780000,10.000134 +perfexp-cfa-pbv-ll-share-na,corpus-100-20-1.txt,xxx,100,22.960000,574500000,10.000156 +perfexp-cfa-pbv-ll-share-na,corpus-100-200-1.txt,xxx,100,177.280000,577170000,10.000125 +perfexp-cfa-pbv-ll-share-na,corpus-100-5-1.txt,xxx,100,5.270000,577820000,10.000046 +perfexp-cfa-pbv-ll-share-na,corpus-100-50-1.txt,xxx,100,43.320000,578770000,10.000033 +perfexp-cfa-pbv-ll-share-na,corpus-100-500-1.txt,xxx,100,557.260000,579540000,10.000128 +perfexp-cfa-pbv-ll-noshare-na,corpus-100-1-1.txt,xxx,100,1.000000,191420000,10.000232 +perfexp-cfa-pbv-ll-noshare-na,corpus-100-10-1.txt,xxx,100,9.500000,186330000,10.000046 +perfexp-cfa-pbv-ll-noshare-na,corpus-100-100-1.txt,xxx,100,106.370000,164610000,10.000463 +perfexp-cfa-pbv-ll-noshare-na,corpus-100-2-1.txt,xxx,100,2.030000,182390000,10.000409 +perfexp-cfa-pbv-ll-noshare-na,corpus-100-20-1.txt,xxx,100,22.960000,182280000,10.000252 +perfexp-cfa-pbv-ll-noshare-na,corpus-100-200-1.txt,xxx,100,177.280000,149840000,10.000281 +perfexp-cfa-pbv-ll-noshare-na,corpus-100-5-1.txt,xxx,100,5.270000,152370000,10.000284 +perfexp-cfa-pbv-ll-noshare-na,corpus-100-50-1.txt,xxx,100,43.320000,177430000,10.000397 +perfexp-cfa-pbv-ll-noshare-na,corpus-100-500-1.txt,xxx,100,557.260000,113440000,10.000150 +perfexp-stl-pta-na-na-reuse,corpus-100-1-1.txt,100,100,1.000000,152870000,10.000280 +perfexp-stl-pta-na-na-reuse,corpus-100-10-1.txt,100,100,9.500000,98530000,10.000299 +perfexp-stl-pta-na-na-reuse,corpus-100-100-1.txt,100,100,106.370000,16690000,10.005783 +perfexp-stl-pta-na-na-reuse,corpus-100-2-1.txt,100,100,2.030000,136230000,10.000196 +perfexp-stl-pta-na-na-reuse,corpus-100-20-1.txt,100,100,22.960000,62110000,10.001423 +perfexp-stl-pta-na-na-reuse,corpus-100-200-1.txt,100,100,177.280000,8960000,10.005548 +perfexp-stl-pta-na-na-reuse,corpus-100-5-1.txt,100,100,5.270000,104790000,10.000889 +perfexp-stl-pta-na-na-reuse,corpus-100-50-1.txt,100,100,43.320000,39170000,10.000011 +perfexp-stl-pta-na-na-reuse,corpus-100-500-1.txt,100,100,557.260000,3100000,10.015093 +perfexp-stl-pta-na-na-fresh,corpus-100-1-1.txt,100,100,1.000000,154450000,10.000054 +perfexp-stl-pta-na-na-fresh,corpus-100-10-1.txt,100,100,9.500000,96570000,10.000834 +perfexp-stl-pta-na-na-fresh,corpus-100-100-1.txt,100,100,106.370000,16400000,10.000697 +perfexp-stl-pta-na-na-fresh,corpus-100-2-1.txt,100,100,2.030000,133450000,10.000440 +perfexp-stl-pta-na-na-fresh,corpus-100-20-1.txt,100,100,22.960000,62540000,10.001476 +perfexp-stl-pta-na-na-fresh,corpus-100-200-1.txt,100,100,177.280000,8960000,10.006817 +perfexp-stl-pta-na-na-fresh,corpus-100-5-1.txt,100,100,5.270000,106470000,10.000109 +perfexp-stl-pta-na-na-fresh,corpus-100-50-1.txt,100,100,43.320000,37460000,10.000100 +perfexp-stl-pta-na-na-fresh,corpus-100-500-1.txt,100,100,557.260000,3090000,10.000541 +perfexp-stl-peq-na-na-reuse,corpus-100-1-1.txt,100,100,1.000000,863350000,10.000092 +perfexp-stl-peq-na-na-reuse,corpus-100-10-1.txt,100,100,9.500000,471070000,10.000189 +perfexp-stl-peq-na-na-reuse,corpus-100-100-1.txt,100,100,106.370000,287660000,10.000105 +perfexp-stl-peq-na-na-reuse,corpus-100-2-1.txt,100,100,2.030000,669380000,10.000082 +perfexp-stl-peq-na-na-reuse,corpus-100-20-1.txt,100,100,22.960000,432290000,10.000131 +perfexp-stl-peq-na-na-reuse,corpus-100-200-1.txt,100,100,177.280000,241690000,10.000290 +perfexp-stl-peq-na-na-reuse,corpus-100-5-1.txt,100,100,5.270000,510990000,10.000082 +perfexp-stl-peq-na-na-reuse,corpus-100-50-1.txt,100,100,43.320000,396380000,10.000235 +perfexp-stl-peq-na-na-reuse,corpus-100-500-1.txt,100,100,557.260000,135830000,10.000603 +perfexp-stl-peq-na-na-fresh,corpus-100-1-1.txt,100,100,1.000000,785420000,10.000062 +perfexp-stl-peq-na-na-fresh,corpus-100-10-1.txt,100,100,9.500000,418030000,10.000094 +perfexp-stl-peq-na-na-fresh,corpus-100-100-1.txt,100,100,106.370000,225290000,10.000237 +perfexp-stl-peq-na-na-fresh,corpus-100-2-1.txt,100,100,2.030000,550120000,10.000151 +perfexp-stl-peq-na-na-fresh,corpus-100-20-1.txt,100,100,22.960000,386080000,10.000206 +perfexp-stl-peq-na-na-fresh,corpus-100-200-1.txt,100,100,177.280000,176890000,10.000155 +perfexp-stl-peq-na-na-fresh,corpus-100-5-1.txt,100,100,5.270000,441830000,10.000135 +perfexp-stl-peq-na-na-fresh,corpus-100-50-1.txt,100,100,43.320000,310200000,10.000299 +perfexp-stl-peq-na-na-fresh,corpus-100-500-1.txt,100,100,557.260000,90360000,10.000474 +perfexp-stl-pbv-na-na-na,corpus-100-1-1.txt,xxx,100,1.000000,1267670000,10.000039 +perfexp-stl-pbv-na-na-na,corpus-100-10-1.txt,xxx,100,9.500000,482210000,10.000013 +perfexp-stl-pbv-na-na-na,corpus-100-100-1.txt,xxx,100,106.370000,268680000,10.000097 +perfexp-stl-pbv-na-na-na,corpus-100-2-1.txt,xxx,100,2.030000,806650000,10.000104 +perfexp-stl-pbv-na-na-na,corpus-100-20-1.txt,xxx,100,22.960000,369490000,10.000159 +perfexp-stl-pbv-na-na-na,corpus-100-200-1.txt,xxx,100,177.280000,227020000,10.000244 +perfexp-stl-pbv-na-na-na,corpus-100-5-1.txt,xxx,100,5.270000,534150000,10.000061 +perfexp-stl-pbv-na-na-na,corpus-100-50-1.txt,xxx,100,43.320000,298950000,10.000190 +perfexp-stl-pbv-na-na-na,corpus-100-500-1.txt,xxx,100,557.260000,158310000,10.000104 Index: doc/theses/mike_brooks_MMath/pictures/string-graph-peq-cppemu.csv =================================================================== --- doc/theses/mike_brooks_MMath/pictures/string-graph-peq-cppemu.csv (revision b195498ca6cf118ea16f39c6f8feaf910d504d33) +++ (revision ) @@ -1,20 +1,0 @@ -operation,peq,,,,,,,,,, -sut-cfa-level,(Multiple Items),,,,,,,,,, -op-alloc,(All),,,,,,,,,, -sut-cfa-sharing,(All),,,,,,,,,, -sut-platform,(All),,,,,,,,,, -,,,,,,,,,,, -Average of op-duration,Column Labels,,,,,,,,,, -Row Labels,cfa-ll-noshare-reuse,cfa-ll-noshare-fresh,stl-na-na-reuse,stl-na-na-fresh,,,,,,, -1,16.3,21.4,11.6,14.4,,1.4,1.5,,,1.31,1.24 -2,19.2,26.5,14.6,20.2,,1.3,1.3,,,1.38,1.38 -5,22.4,29.8,20.2,25.8,,1.1,1.2,,,1.33,1.27 -10,22.2,31.3,21.6,26.7,,1.0,1.2,,,1.41,1.24 -20,24.6,33.6,23.0,29.9,,1.1,1.1,,,1.37,1.30 -50,27.9,41.3,26.4,37.4,,1.1,1.1,,,1.48,1.42 -100,36.6,55.3,34.9,49.3,,1.1,1.1,,,1.51,1.41 -200,42.2,63.7,39.4,59.6,,1.1,1.1,,,1.51,1.51 -500,75.9,117.4,73.9,114.5,,1.0,1.0,,,1.55,1.55 -,,,,,,,,,,, -,,,,,,,,,,, -,,,,,,1.14,,,,1.424524256,1.365309329 Index: doc/theses/mike_brooks_MMath/pictures/string-graph-peq-cppemu.dat =================================================================== --- doc/theses/mike_brooks_MMath/pictures/string-graph-peq-cppemu.dat (revision b195498ca6cf118ea16f39c6f8feaf910d504d33) +++ (revision ) @@ -1,46 +1,0 @@ -"{/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 -5 22.4 -10 22.2 -20 24.6 -50 27.9 -100 36.6 -200 42.2 -500 75.9 - - -"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 {/Helvetica=15 +=} reuse" -1 11.6 -2 14.6 -5 20.2 -10 21.6 -20 23.0 -50 26.4 -100 34.9 -200 39.4 -500 73.9 Index: doc/theses/mike_brooks_MMath/plot-peq-cppemu.gp =================================================================== --- doc/theses/mike_brooks_MMath/plot-peq-cppemu.gp (revision b195498ca6cf118ea16f39c6f8feaf910d504d33) +++ (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 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/plots/string-peq-cppemu.d =================================================================== --- doc/theses/mike_brooks_MMath/plots/string-peq-cppemu.d (revision f85de474d7bae82407a8ea5f1551da282d77d9bd) +++ doc/theses/mike_brooks_MMath/plots/string-peq-cppemu.d (revision f85de474d7bae82407a8ea5f1551da282d77d9bd) @@ -0,0 +1,2 @@ +plots/string-peq-cppemu.gp.INPUTS: build/plot-string-peq-cppemu.dat | build +plots/string-peq-cppemu.py.INPUTS: benchmarks/string/result-append-pbv.csv Index: doc/theses/mike_brooks_MMath/plots/string-peq-cppemu.gp =================================================================== --- doc/theses/mike_brooks_MMath/plots/string-peq-cppemu.gp (revision f85de474d7bae82407a8ea5f1551da282d77d9bd) +++ doc/theses/mike_brooks_MMath/plots/string-peq-cppemu.gp (revision f85de474d7bae82407a8ea5f1551da282d77d9bd) @@ -0,0 +1,25 @@ +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 + +INDIR="build" +OUTDIR="build" + +set macros +set output OUTDIR."/plot-string-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 +set yrange [10:200] +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 INDIR."/plot-string-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/plots/string-peq-cppemu.py =================================================================== --- doc/theses/mike_brooks_MMath/plots/string-peq-cppemu.py (revision f85de474d7bae82407a8ea5f1551da282d77d9bd) +++ doc/theses/mike_brooks_MMath/plots/string-peq-cppemu.py (revision f85de474d7bae82407a8ea5f1551da282d77d9bd) @@ -0,0 +1,89 @@ +# Read thesis-append-pbv.csv +# Output for string-graph-peq-cppemu.dat + +# Project details +# Filter operation=peq +# Split "series" goups of sut; only those in the "pretty" list +# Assert one row per string-length +# output: +# string-len op-duration +# in chunks, each headed by pertty(sut) + +import pandas as pd +import numpy as np +import os + +infile = os.path.dirname(os.path.abspath(__file__)) + '/../benchmarks/string/result-append-pbv.csv' + +prettyFieldNames = { + "cfa-ll-noshare-fresh": "{/Helvetica=15 C{/Symbol \\42} +=} noshare fresh", + "cfa-ll-noshare-reuse": "{/Helvetica=15 C{/Symbol \\42} +=} noshare reuse", + "stl-na-na-fresh": "STL {/Helvetica=15 +=} fresh", + "stl-na-na-reuse": "STL {/Helvetica=15 +=} reuse", +} + +timings = pd.read_csv( + infile, + names=['test', 'corpus', 'concatsPerReset', 'corpusItemCount', 'corpusMeanLenChars', 'concatDoneActualCount', 'execTimeActualSec'], + dtype={'test': str, + 'corpus': str, + 'concatsPerReset': 'Int64', # allows missing; https://stackoverflow.com/a/70626154 + 'corpusItemCount': np.int64, + 'corpusMeanLenChars': np.float64, + 'concatDoneActualCount': np.int64, + 'execTimeActualSec': np.float64}, + na_values=['xxx'], +) +# print(timings.head()) + + +# project: parse executable and corpus names + +timings[['test-slug', + 'sut-platform', + 'operation', + 'sut-cfa-level', + 'sut-cfa-sharing', + 'op-alloc']] = timings['test'].str.strip().str.split('-', expand=True) +timings['sut'] = timings[['sut-platform', + 'sut-cfa-level', + 'sut-cfa-sharing', + 'op-alloc']].agg('-'.join, axis=1) + +timings[['corpus-basename', + 'corpus-ext']] = timings['corpus'].str.strip().str.split('.', expand=True) +timings[['corpus-slug', + 'corpus-nstrs', + 'corpus-meanlen', + 'corpus-runid']] = timings['corpus-basename'].str.strip().str.split('-', expand=True) +timings["corpus-nstrs"] = pd.to_numeric(timings["corpus-nstrs"]) +timings["corpus-meanlen"] = pd.to_numeric(timings["corpus-meanlen"]) +timings["corpus-runid"] = pd.to_numeric(timings["corpus-runid"]) + + +# project: calculate fact + +timings['op-duration-s'] = timings['execTimeActualSec'] / timings['concatDoneActualCount'] +timings['op-duration-ns'] = timings['op-duration-s'] * 1000 * 1000 * 1000 + + +# Filter operation=peq + +groupedOp = timings.groupby('operation') +tgtOpTimings = groupedOp.get_group('peq') + + +# Emit in groups + +groupedSut = tgtOpTimings.groupby('sut') + +for sut, sgroup in groupedSut: + + if sut in prettyFieldNames: + + sgroup_sorted = sgroup.sort_values(by='corpus-meanlen') + + print('"{header}"'.format(header=prettyFieldNames[sut])) + text = sgroup_sorted[['corpus-meanlen', 'op-duration-ns']].to_csv(header=False, index=False, sep='\t') + print(text) + print() Index: doc/theses/mike_brooks_MMath/programs/sharing-demo.cfa =================================================================== --- doc/theses/mike_brooks_MMath/programs/sharing-demo.cfa (revision b195498ca6cf118ea16f39c6f8feaf910d504d33) +++ doc/theses/mike_brooks_MMath/programs/sharing-demo.cfa (revision f85de474d7bae82407a8ea5f1551da282d77d9bd) @@ -1,5 +1,5 @@ #include +#include #include - #define xstr(s) str(@s;@) #define str(s) #s Index: doc/theses/mike_brooks_MMath/string.tex =================================================================== --- doc/theses/mike_brooks_MMath/string.tex (revision b195498ca6cf118ea16f39c6f8feaf910d504d33) +++ doc/theses/mike_brooks_MMath/string.tex (revision f85de474d7bae82407a8ea5f1551da282d77d9bd) @@ -20,11 +20,12 @@ \hline @strcpy@, @strncpy@ & @=@ & @=@ & @=@ \\ -@strcat@, @strncat@ & @+@ & @+@ & @+@ \\ +@strcat@, @strncat@ & @+@, @+=@ & @+@, @+=@ & @+@, @+=@ \\ @strcmp@, @strncmp@ & @==@, @!=@, @<@, @<=@, @>@, @>=@ - & @equals@, @compareTo@ & @==@, @!=@, @<@, @<=@, @>@, @>=@ \\ + & @equals@, @compareTo@ + & @==@, @!=@, @<@, @<=@, @>@, @>=@ \\ @strlen@ & @length@, @size@ & @length@ & @size@ \\ @[ ]@ & @[ ]@ & @charAt@ & @[ ]@ \\ -@strncpy@ & @substr@ & @substring@ & @( )@ RHS @=@ \\ -@strncpy@ & @replace@ & @replace@ & @( )@ LHS @=@ \\ +@strncpy@ & @substr@ & @substring@ & @( )@, on RHS of @=@ \\ +@strncpy@ & @replace@ & @replace@ & @( )@, on LHS of @=@ \\ @strstr@ & @find@ & @indexOf@ & @find@ \\ @strcspn@ & @find_first_of@ & @matches@ & @include@ \\ @@ -834,9 +835,9 @@ & \multirow{2}{2in} {Fast Initialize: The target receives the characters of the source without copying the characters, resulting in an Alias or Snapshot.} - & Alias: The target name is within the source text; changes made in either variable are visible in both. + & Alias: The target variable names the source text; changes made in either variable are visible in both. & yes & yes & no & yes \\ \cline{3-7} & - & Snapshot: The target is an alias within the source until the target changes (copy on write). + & Snapshot: Subsequent operations on either the source or target variable do not affect the other. & no & no & yes & yes \\ \hline @@ -844,5 +845,5 @@ & Laxed: The target's type is anything string-like; it may have a different status concerning ownership. & Strict: The target's type is the same as the source; both strings are equivalent peers concerning ownership. - & N/A & no & yes & yes \\ + & n/a & no & yes & yes \\ \hline Referent @@ -860,5 +861,5 @@ A language gets ``Supports Helpful'' in one criterion if it can do so without sacrificing the Required achievement on all other criteria. \item - The C ``string'' is actually @char []@, under the conventions that @@ requires. Hence, there is no actual string type in C, so symmetry does not apply. + The C ``string'' is @char *@, under the conventions of @@. Because this type does not manage a text allocation, symmetry does not apply. \item The Java @String@ class is analyzed; its @StringBuffer@ class behaves similarly to @C++@. @@ -868,23 +869,26 @@ \end{figure} -In C, the declaration -\begin{cfa} -char s[$\,$] = "abcde"; -\end{cfa} -creates a second-class fixed-sized string-variable, as it can only be used in its lexical context, \ie it cannot be passed by value to string operations or user functions. -The reason is that there is no implicit mechanism to pass the string-length information to the function. -Therefore, only pointers to strings are first-class, and discussed further. -\begin{cfa} -(const) char * s = "abcde"; $\C[2.25in]{// alias state, n/a symmetry, variable-constrained referent}$ +In C, these declarations give very different things. +\begin{cfa} +char x[$\,$] = "abcde"; +char * y = "abcde"; +\end{cfa} +Both associate the declared name with fixed-six contiguous bytes, filled as @{'a', 'b', 'c', 'd', 'e', 0}@. +But @x@ gets them allocated in the active stack frame (with values filled in as control passes the declaration), while @y@ refers into the executable's read-only data section. +With @x@ representing an allocation, it offers information in @sizeof(x)@ that @y@ does not. +But this extra information is second-class, as it can only be used in the immediate lexical context, \ie it cannot be passed on to string operations or user functions. +Only pointers to text buffers are first-class, and discussed further. + +\begin{cfa} +char * s = "abcde"; char * s1 = s; $\C{// alias state, n/a symmetry, variable-constrained referent}$ -char * s2 = s; $\C{// alias state, n/a symmetry, variable-constrained referent}$ -char * s3 = &s[1]; $\C{// alias state, n/a symmetry, variable-constrained referent}$ -char * s4 = &s3[1]; $\C{// alias state, n/a symmetry, variable-constrained referent}\CRT$ -printf( "%s %s %s %s %s\n", s, s1, s2, s3, s4 ); -$\texttt{\small abcde abcde abcde bcde cde}$ +char * s2 = &s[1]; $\C{// alias state, n/a symmetry, variable-constrained referent}\CRT$ +char * s3 = &s2[1]; $\C{// alias state, n/a symmetry, variable-constrained referent} +printf( "%s %s %s %s\n", s, s1, s2, s3 ); +$\texttt{\small abcde abcde bcde cde}$ \end{cfa} Note, all of these aliased strings rely on the single null termination character at the end of @s@. -The issue of symmetry does not apply to C strings because the value and pointer strings are essentially different types, and so this feature is scored as not applicable for C. -With the type not managing the text storage, there is no ownership question, \ie operations on @s1@ or @s2@ never leads to their memory becoming reusable. +The issue of symmetry does not apply to a low-level API because no management of a text buffer is provided. +With the @char *@ type not managing the text storage, there is no ownership question, \ie operations on @s1@ or @s2@ never lead to their memory becoming reusable. While @s3@ is a valid C-string that contains a proper substring of @s1@, the @s3@ technique does not constitute having a fragment referent because null termination implies the substring cannot be chosen arbitrarily; the technique works only for suffixes. @@ -893,17 +897,18 @@ string s = "abcde"; string & s1 = s; $\C[2.25in]{// alias state, lax symmetry, variable-constrained referent}$ -string s2 = s; $\C{// copy (strict symmetry, variable-constrained referent)}$ -string s3 = s.substr( 1, 2 ); $\C{// copy (strict symmetry, fragment referent)}$ -string s4 = s3.substr( 1, 1 ); $\C{// copy (strict symmetry, fragment referent)}$ +string s2 = s; $\C{// no fast-initialize (strict symmetry, variable-constrained referent)}$ +string s3 = s.substr( 1, 2 ); $\C{// no fast-initialize (strict symmetry, fragment referent)}$ +string s4 = s3.substr( 1, 1 ); $\C{// no fast-initialize (strict symmetry, fragment referent)}$ cout << s << ' ' << s1 << ' ' << s2 << ' ' << s3 << ' ' << s4 << endl; $\texttt{\small abcde abcde abcde bc c}$ string & s5 = s.substr(2,4); $\C{// error: cannot point to temporary}\CRT$ \end{cfa} -The lax symmetry reflects how the validity of @s1@ depends on the content and lifetime of @s@. -It is common practice in \CC to use the @s1@-style pass by reference, with the understanding that the callee only uses the referenced string for the duration of the call, \ie no side-effect using the parameter. -So, when the called function is a constructor, it is typical to use an @s2@-style copy-initialization. +The @s1@ lax symmetry reflects how its validity of depends on the lifetime of @s@. +It is common practice in \CC to use the @s1@-style for a by-reference function parameter. +Doing so assumes that the callee only uses the referenced string for the duration of the call, \ie no storing the parameter (as a reference) for later. +So, when the called function is a constructor, its definition typically uses an @s2@-style copy-initialization. Exceptions to this pattern are possible, but require the programmer to assure safety where the type system does not. -The @s3@ initialization is constrained to copy the substring because @c_str@ always provides a null-terminated character, which may be different from the source string. -@s3@ assignment could be fast by reference counting the text area and using copy-on-write, but would require an implementation upgrade. +The @s3@ initialization must copy the substring because it must support a subsequent @c_str@ call, which provides a null-termination, generally at a different position than the source string's. +@s2@ assignment could be made fast, by reference-counting the text area and using copy-on-write, but would require an implementation upgrade. In Java, @String@ also offers a high-level abstraction: @@ -918,5 +923,5 @@ $\texttt{\small true false false}$ \end{java} -Note, @substring@ takes a start and end position, rather than a start position and length. +Note, Java's @substring@ takes a start and end position, rather than a start position and length. Here, facts about Java's implicit pointers and pointer equality can over complicate the picture, and so are ignored. Furthermore, Java's string immutability means string variables behave as simple values. @@ -924,19 +929,21 @@ With @s2@, the case for fast-copy is more subtle. Certainly, its value is not pointer-equal to @s@, implying at least a further allocation. -\PAB{TODO: finish the fast-copy case.} -Java does not meet the aliasing requirement because immutability make it impossible to modify. +But because Java is not constrained to use a null-terminated representation, a standard-library implementation is free to refer to the source characters in-place. +Java does not meet the aliasing requirement because immutability makes it impossible to modify. Java's @StringBuffer@ provides aliasing (see @replace@ example on \VPageref{p:JavaReplace}), though without supporting symmetric treatment of a fragment referent, \eg @substring@ of a @StringBuffer@ is a @String@; as a result, @StringBuffer@ scores as \CC. -The easy symmetry that the Java string enjoys is aided by Java's garbage collection; Java's @s2@ is doing effectively the operation of \CC's @s3@, though without the consequence of complicating memory management. -\PAB{What complex storage management is going on here?} +The easy symmetry that the Java string enjoys is aided by Java's garbage collection; Java's @s1@ is doing effectively the operation of \CC's @s1@, though without the consequence of complicating memory management. + +% former \PAB{What complex storage management is going on here?} +% answer: the variable names in the sentence were out of date; fixed Finally, in \CFA, @string@ also offers a high-level abstraction: \begin{cfa} string s = "abcde"; -string & s1 = s; $\C[2.25in]{// alias state, strict symmetry, variable-constrained referent}$ +string & s1 = s; $\C[2.25in]{// alias state, lax symmetry, variable-constrained referent}$ string s2 = s; $\C{// snapshot state, strict symmetry, variable-constrained referent}$ -string s3 = s`share; $\C{// alias state, strict symmetry, variable-constrained referent}\CRT$ -string s4 = s( 1, 2 ); -string s5 = s4( 1, 1 ); +string s3 = s`share; $\C{// alias state, strict symmetry, variable-constrained referent}$ +string s4 = s( 1, 2 ); $\C{// snapshot state, strict symmetry, fragment referent}$ +string s5 = s4( 1, 1 )`share'; $\C{// alias state, strict symmetry, fragment referent}\CRT$ sout | s | s1 | s2 | s3 | s4 | s5; $\texttt{\small abcde abcde abcde abcde bc c}$ @@ -944,40 +951,41 @@ % all helpful criteria of \VRef[Figure]{f:StrSemanticCompare} are satisfied. The \CFA string manages storage, handles all assignments, including those of fragment referents with fast initialization, provides the choice between snapshot and alias semantics, and does so symmetrically with one type (which assures text validity according to the lifecycles of the string variables). -The intended metaphor for \CFA stings is similar to a GUI text-editor or web browser. -Select a consecutive block of text using the mouse generates an aliased substring in the file/dialog-box. -Typing into the selected area is like assigning to an aliased substring, where the highlighted text is replaced with more or less text; -depending on the text entered, the file/dialog-box content grows or shrinks. -\PAB{Need to discuss the example, as for the other languages.} - -The remainder of this chapter explains how the \CFA string achieves this usage style. - - -\section{Storage Management} - -This section discusses issues related to storage management of strings. -Specifically, it is common for strings to logically overlap partially or completely. -\begin{cfa} -string s1 = "abcdef"; -string s2 = s1; $\C{// complete overlap, s2 == "abcdef"}$ -string s3 = s1.substr( 0, 3 ); $\C{// partial overlap, s3 == "abc"}$ -\end{cfa} -This raises the question of how strings behave when an overlapping component is changed, -\begin{cfa} -s3[1] = 'w'; $\C{// what happens to s1 and s2?}$ -\end{cfa} -which is restricted by a string's mutable or immutable property. -For example, Java's immutable strings require copy-on-write when any overlapping string changes. -Note, the notion of underlying string mutability is not specified by @const@; \eg in \CC: -\begin{cfa} -const string s1 = "abc"; -\end{cfa} -the @const@ applies to the @s1@ pointer to @"abc"@, and @"abc"@ is an immutable constant that is \emph{copied} into the string's storage. -Hence, @s1@ is not pointing at an immutable constant, meaning its underlying string can be mutable, unless some other designation is specified, such as Java's global immutable rule. +The @s1@ case is the same in \CFA as in \CC. +But the \CFA @s2@ delivers a fast snapshot, while the \CC @s2@ does not. +\CFA offers the snapshot-vs-alias choice in @s2@-vs-@s3@ and @s4@-vs-@s5@. +Regardless of snapshot-vs-alias and fragment-vs-whole, the target is always of the same @string@ type. + +% former \PAB{Need to discuss the example, as for the other languages.} +% answer: done + \subsection{Logical overlap} -\CFA provides a dynamic mechanism to indicate mutable or immutable using the attribute @`share@. -This aliasing relationship is a sticky-property established at initialization. +It may be unfamiliar to combine \VRef[Figure]{f:StrSemanticCompare}'s alias state and fragment referent in one API, or at the same time. +This section shows the capability in action. + +In summary, the metaphor of a GUI text editor is intended. +Selecting a consecutive block of text using the mouse defines an aliased substring within the file. +Typing in this state overwrites what was there before, replacing the originally selected text with more or less text. +But the \emph{whole file} grows or shrinks as a result, not just the selection. +This action models assigning to an aliased substring when the two strings overlap by total containment: one string is the selection, the other is the whole file. + +Now extend the metaphor to a multi-user online editor. +If Alice selects a range of text at the bottom of the file, wile Bob is rewriting a paragraph at the top, Alice's selection holds onto the logical characters initially selected, unaffected by Bob making the total file grow/shrink, and unaffectd by Bob causing the start index of Alice's selction to vary. +This action models assigning to an aliased substring when the two strings do not overlap at all: one string is Alice's selection, the other is Bob's. + +If a third office worker were also watching Alice's and Bob's actions on the whole file (a string with ``all the text'' is kept around), then two further single-user-edit cases give the semantics of the individual edits flowing into the whole. +But, departing from the document analogy, it is not necessary to keep a such a third string: +no one has to resource-manage ``the document.'' +When an original string, from which both the Alice- and Bob-parts came, ceases to exist, Alice and Bob are left with two independent strings. +They are independent because Alice and Bob have no API for growing the bounds of a string to subsume text that may once have been around it. + +Edge cases, notably ``Venn-diagram overlap,'' had to have handlings chosen. +The intent in fleshing out these details was to achieve the above story, with a single API, while keeping the rest as simple as possible. +The remainder of this section shows the resulting decisions, played out at the API level. + +\CFA uses the marker @`share@ as a dynamic mechanism to indicate alias (mutations shared) \vs snapshot (not quite an immutable result, but one with subsequent mutations isolated). +This aliasing relationship is a sticky property established at initialization. For example, here strings @s1@ and @s1a@ are in an aliasing relationship, while @s2@ is in a copy relationship. \input{sharing1.tex} @@ -1003,5 +1011,5 @@ The following rules explain aliasing substrings that flow in the opposite direction, large to small. -Growth and shrinkage are natural extensions, as for the text-editor example mentioned earlier, where an empty substring is as real as an empty string. +Growth and shrinkage are natural extensions, as for the text-editor analogy, where an empty substring is as real as an empty string. \input{sharing8.tex} @@ -1071,78 +1079,36 @@ -\subsection{RAII limitations} - -Earlier work on \CFA~\cite[ch.~2]{Schluntz17} implemented object constructors and destructors for all types (basic and user defined). -A constructor is a user-defined function run implicitly \emph{after} an object's declaration-storage is created, and a destructor is a user-defined function run \emph{before} an object's declaration-storage is deleted. -This feature, called RAII~\cite[p.~389]{Stroustrup94}, guarantees pre-invariants for users before accessing an object and post invariants for the programming environment after an object terminates. - -The purposes of these invariants goes beyond ensuring authentic values inside an object. -Invariants can also track occurrences of managed objects in other data structures. -For example, reference counting is a typical application of an invariant outside of the data values. -With a reference-counting smart-pointer, the constructor and destructor \emph{of a pointer type} tracks the life cycle of the object it points to. -Both \CC and \CFA RAII systems are powerful enough to achieve reference counting. - -In general, a lifecycle function has access to an object by location, \ie constructors and destructors receive a @this@ parameter providing an object's memory address. -\begin{cfa} -struct S { int * ip; }; -void ?{}( S & @this@ ) { this.ip = new(); } $\C[3in]{// default constructor}$ -void ?{}( S & @this@, int i ) { ?{}(this); *this.ip = i; } $\C{// initializing constructor}$ -void ?{}( S & @this@, S s ) { this = s; } $\C{// copy constructor}$ -void ^?{}( S & @this@ ) { delete( this.ip ); } $\C{// destructor}\CRT$ -\end{cfa} -The lifecycle implementation can then add this object to a collection at creation and remove it at destruction. -A module providing lifecycle semantics can traverse the collection at relevant times to keep the objects ``good.'' -Hence, declaring such an object not only ensures ``good'' authentic values, but also an implicit subscription to a service that keeps the value ``good'' across its lifetime. - -In many cases, the relationship between memory location and lifecycle is straightforward. -For example, stack-allocated objects being used as parameters and returns, with a sender version in one stack frame and a receiver version in another, as opposed to assignment where sender and receiver are in the same stack frame. -What is crucial for lifecycle management is knowing if the receiver is initialized or uninitialized, \ie an object is or is not currently associated with management. -To provide this knowledge, languages differentiate between initialization and assignment to a left-hand side. -\begin{cfa} -Obj obj2 = obj1; $\C[1.5in]{// initialization, obj2 is initialized}$ -obj2 = obj1; $\C{// assignment, obj2 must be initialized for management to work}\CRT$ -\end{cfa} -Initialization occurs at declaration by value, parameter by argument, return temporary by function call. -Hence, it is necessary to have two kinds of constructors: by value or object. -\begin{cfa} -Obj obj1{ 1, 2, 3 }; $\C[1.5in]{// by value, management is initialized}$ -Obj obj2 = obj1; $\C{// by obj, management is updated}\CRT$ -\end{cfa} -When no object management is required, initialization copies the right-hand value. -Hence, the calling convention remains uniform, where the unmanaged case uses @memcpy@ as the initialization constructor and managed uses the specified initialization constructor. - -The \CFA RAII system supports lifecycle functions, except for returning a value from a function to a temporary. -For example, in \CC: -\begin{c++} -struct S {...}; -S identity( S s ) { return s; } -S s; -s = identity( s ); // S temp = identity( s ); s = temp; -\end{c++} -the generated code for the function call created a temporary with initialization from the function call, and then assigns the temporary to the object. -This two step approach means extra storage for the temporary and two copies to get the result into the object variable. -\CC{17} introduced return value-optimization (RVO)~\cite{RVO20} to ``avoid copying an object that a function returns as its value, including avoiding creation of a temporary object''. -\CFA uses C semantics for function return giving direct value-assignment, which eliminates unnecessary code, but skips an essential feature needed by lifetime management. -The following discusses the consequences of this semantics with respect to lifetime management of \CFA strings. - -The present string-API contribution provides lifetime management with initialization semantics on function return. -The workaround to achieve the full lifetime semantics does have a runtime performance penalty. -An alternative API sacrifices return initialization semantics to recover full runtime performance. -These APIs are layered, with the slower, friendlier High Level API (HL) wrapping the faster, more primitive Low Level API (LL). -Both API present the same features, up to lifecycle management, with return initialization being disabled in LL and implemented with the workaround in HL. -The intention is for most future code to target HL. -When \CFA becomes a full compiler, it can provide return initialization with RVO optimizations. -Then, programs written with the HL API will simply run faster. -In the meantime, performance-critical sections of applications use LL. -Subsequent performance experiments \see{\VRef{s:PerformanceAssessment}} with other string libraries has \CFA strings using the LL API. -These measurement gives a fair estimate of the goal state for \CFA. - - -\subsection{Memory management} + +\section{Storage management} + +This section discusses issues related to storage management of strings. +Specifically, it is common for strings to logically overlap partially or completely. +\begin{cfa} +string s1 = "abcdef"; +string s2 = s1; $\C{// complete overlap, s2 == "abcdef"}$ +string s3 = s1.substr( 0, 3 ); $\C{// partial overlap, s3 == "abc"}$ +\end{cfa} +This raises the question of how strings behave when an overlapping component is changed, +\begin{cfa} +s3[1] = 'w'; $\C{// what happens to s1 and s2?}$ +\end{cfa} +which is restricted by a string's mutable or immutable property. +For example, Java's immutable strings require copy-on-write when any overlapping string changes. +Note, the notion of underlying string mutability is not specified by @const@; \eg in \CC: +\begin{cfa} +const string s1 = "abc"; +\end{cfa} +the @const@ applies to the @s1@ pointer to @"abc"@, and @"abc"@ is an immutable constant that is \emph{copied} into the string's storage. +Hence, @s1@ is not pointing at an immutable constant, meaning its underlying string can be mutable, unless some other designation is specified, such as Java's global immutable rule. + + + +\subsection{General implementation} +\label{string-general-impl} A centrepiece of the string module is its memory manager. The management scheme defines a shared buffer for string text. -Allocation in this buffer is via a bump-pointer; -the buffer is compacted and/or relocated with growth when it fills. +Allocation in this buffer is always via a bump-pointer; +the buffer is compacted and/or relocated (to grow) when it fills. A string is a smart pointer into this buffer. @@ -1151,6 +1117,6 @@ First, in a general purpose manager, the allocated objects may contain pointers to other objects, making the transitive reachability of these objects a crucial property. Here, the allocations are text, so one allocation never keeps another alive. -Second, in a general purpose manager, the handle that keeps an allocation alive is just a lean pointer. -For strings, a fatter representation is acceptable because there are fewer string head pointers versus chained pointers within nodes as for linked containers. +Second, in a general purpose manager, the handle that keeps an allocation alive is a bare pointer. +For strings, a fatter representation is acceptable because this pseudo-pointer is only used for enty into the string-heap, not for general data-sub-structure linking around the general heap. \begin{figure} @@ -1164,7 +1130,7 @@ Normally, one global sharing context is appropriate for an entire program; concurrent exceptions are discussed in \VRef{s:ControllingImplicitSharing}. -A string is a handle into the buffer and linked into a list. +A string is a handle into the buffer and node within a linked list. The list is doubly linked for $O(1)$ insertion and removal at any location. -Strings are orders in the list by string-text address, where there is no overlapping, and approximately, where there is. +Strings are ordered in the list by text start address. The header maintains a next-allocation pointer, @alloc@, pointing to the last live allocation in the buffer. No external references point into the buffer and the management procedure relocates the text allocations as needed. @@ -1178,8 +1144,8 @@ When the text buffer fills, \ie the next new string allocation causes @alloc@ to point beyond the end of the buffer, the strings are compacted. The linked handles define all live strings in the buffer, which indirectly defines the allocated and free space in the buffer. -Since the string handles are in (roughly) sorted order, the handle list can be traversed copying the first text to the start of the buffer and subsequent strings after each over. -After compaction, if the amount of free storage is still less than the new string allocation, a larger text buffer is heap allocated, the current buffer is copies into the new buffer, and the original buffer is freed. -Note, the list of string handles is unaffected during a compaction; -only the string pointers in the handles are modified to new buffer locations. +Since the string handles are in sorted order, the handle list can be traversed, copying the first live text to the start of the buffer, and subsequent strings after each other. +If, upon compaction, the amount of free storage would still be less than the new string allocation, a larger text buffer is heap-allocated, the current buffer is copied into the new buffer, and the original buffer is freed. +Note, the list of string handles is structurally unaffected during a compaction; +only the text pointers in the handles are modified to new buffer locations. Object lifecycle events are the \emph{subscription-management} triggers in such a service. @@ -1187,28 +1153,247 @@ When importing, storage comes from the end of the buffer, into which the text is copied. The new string handle is inserted at the end of the handle list because the new text is at the end of the buffer. -When initializing from text already in the text buffer, the new handle is a second reference into the original run of characters. +When initializing from text already in the buffer, the new handle is a second reference into the original run of characters. In this case, the new handle's linked-list position is after the original handle. Both string initialization styles preserve the string module's internal invariant that the linked-list order matches the buffer order. For string destruction, handles are removed from the list. - -Certain string operations can results in a subset (substring) of another string. +As a result, once a last handle using a run of buffer characters is destroyed, that buffer space gets excluded from the next compaction, making its character-count available in the compacted buffer. + +Certain string operations can result in a substring of another string. The resulting handle is then placed in the correct sorted position in the list, possible with a short linear search to locate the position. For string operations resulting in a new string, that string is allocated at the end of the buffer. For shared-edit strings, handles that originally referenced containing locations need to see the new value at the new buffer location. -These strings are moved to appropriate locations at the end of the list \see{[xref: TBD]}. -For nonshared-edit strings, a containing string can be moved and the nonshared strings can remain in the same position. -String assignment words similarly to string initialization, maintain the invariant of linked-list order matching buffer order. - -At the level of the memory manager, these modifications can always be explained as assignments and appendment; -for example, an append is an assignment into the empty substring at the end of the buffer. +These strings are moved to appropriate locations at the end of the list \see{details in \VRef{sharing-impl}}. +For nonshared-edit strings, a containing string can be moved and the other strings can remain in the same position. +String assignment works similarly to string initialization, maintaining the invariant of linked-list order matching buffer order. + +At the level of the memory manager, these modifications can always be explained as assignment and appendment. +For example, an append is an assignment into the empty substring at the end of the buffer. Favourable conditions allow for in-place editing: where there is room for the resulting value in the original buffer location, and where all handles referring to the original buffer location see the new value. +One notable example of favourable conditions occurs because the most recently written string is often the last in the buffer, after which a large amount of free space occurs. +So, repeated appends often occur without copying previously accumulated characters. However, the general case requires a new buffer allocation: where the new value does not fit in the old place, or if other handles are still using the old value. +\subsection{RAII limitations} +\label{string-raii-limit} + +Earlier work on \CFA~\cite[ch.~2]{Schluntz17} implemented object constructors and destructors for all types (basic and user defined). +A constructor is a user-defined function run implicitly \emph{after} an object's storage is allocated, and a destructor is a user-defined function run \emph{before} an object's storage is deallcated. +This feature, called Resource Acquisition Is Initialization (RAII)~\cite[p.~389]{Stroustrup94}, helps guarantee invariants for users before accessing an object and for the programming environment after an object terminates. + +The purposes of these invariants goes beyond ensuring authentic values inside an object. +Invariants can also track data about managed objects in other data structures. +Reference counting is an example application of an invariant outside of the immediate data value. +With a reference-counting smart-pointer, the constructor and destructor \emph{of a pointer type} track the lifecycle of the object it points to. +Both \CC and \CFA RAII systems are powerful enough to achieve reference counting. + +In general, a lifecycle function has access to an object by location, \ie constructors and destructors receive a @this@ parameter providing an object's memory address. +\begin{cfa} +struct S { int * ip; }; +void ?{}( S & @this@ ) { this.ip = new(); } $\C[3in]{// default constructor}$ +void ?{}( S & @this@, int i ) { (this){}; *this.ip = i; } $\C{// initializing constructor}$ +void ?{}( S & @this@, S s ) { (this){*s.ip}; } $\C{// copy constructor}$ +void ^?{}( S & @this@ ) { delete( this.ip ); } $\C{// destructor}\CRT$ +\end{cfa} +Such basic examples use the @this@ address only to gain access to the values being managed. +But the lifecycle logic can use the pointer generally, too. +For example, they can add @this@ object to a collection at creation and remove it at destruction. +\begin{cfa} +// header +struct T { + // private + inline dlink(T); +}; +void ?{}( T & ); $\C[3in]{// default constructor}$ +void ^?{}( T & ); $\C{// destructor}\CRT$ +// implementation +static dlist(T) @all_T@; +void ?{}( T & this ) { insert_last(all_T, @this@) } +void ^?{}( T & this ) { remove(this); } +\end{cfa} +A module providing the @T@ type can traverse @all_T@ at relevant times, to keep the objects ``good.'' +Hence, declaring a @T@ not only ensures that it begins with an initially ``good'' value, but it also provides an implicit subscription to a service that keeps the value ``good'' in the future. +Again, both \CFA and \CC support this usage style. + +A third capability concerns \emph{implicitly} requested copies. +When stack-allocated objects are used as parameter and return values, a sender's version exists in one stack frame and a receiver's version exists in another. +In the parameter direction, the language's function-call handling must arrange for a copy-constructor call to happen\footnote{ + \CC also offers move constructors and return-value optimization~\cite{RVO20}. + These features help reduce unhelpful copy-constructor calls, which, for types like the example \lstinline{S}, would lead to extra memory allocations. + \CFA does not currently have these features; adding similarly-intended features to \CFA is desirable. + However, this section is about a problem in the realization of features that \CFA already supports. + To understand the problem presented, the appropriate comparison is with classic versions of \CC that treated such copy-constructor calls as necessary.} +at a time near the control transfer into the callee, with the source as the caller's (sender's) version and the target as the callee's (receiver's) version. +(In the return direction, the roles are reversed and the copy-constructor call happens near the return of control.) +\CC supports this capability without qualification. +\CFA offers limited support here; simple examples work, but implicit copying does not combine successfully with the other RAII capabilities discussed. + +To summarize the unsupported combinations, the relevant features are: +\begin{enumerate} +\item + Object provider implements lifecycle functions to manage a resource outside of the object. +\item + Object provider implements lifecycle functions to store references back to the object, often originating from outside of it. +\item + Object user expects to pass (in either direction) an object by value for function calls. +\end{enumerate} +\CC supports all three simultaneously. \CFA does not currently support \#2 and \#3 on the same object, though \#1 works along with either one of \#2 or \#3. \CFA needs to be fixed to support all three simultaneously. + +The reason that \CFA does not support \#2 with \#3 is a holdover from how \CFA function calls lowered to C, before \CFA got references and RAII. +At that time, adhering to a principal of minimal intervention, this code could always be treated as passthrough: +\begin{cfa} +struct U {...}; +// RAII to go here +void f( U u ) { F_BODY(u) } +U x; +f( x ); +\end{cfa} +But adding custom RAII (at ``...here'') changes things. +The common C++ lowering~\cite[Sec. 3.1.2.3]{cxx:raii-abi} proceeds differently than the present CFA lowering. + +\noindent +\begin{tabular}{l|l} +\begin{cfa} +// C++, likely CFA to be +struct U {...}; +// RAII elided +void f( U * __u_orig ) { + U u = * __u_orig; // call copy ctor + F_BODY(u) + // call dtor, u +} +U x; // call default ctor +f( & x ) ; +// call dtor, x +\end{cfa} +& +\begin{cfa} +// CFA today +struct U {...}; +// RAII elided +void f( U u ) { + F_BODY(u) +} +U x; // call default ctor +{ + U __u_for_f = x; // call copy ctor + f( __u_for_f ); + // call dtor, __u_for_f +} +// call dtor, x +\end{cfa} +\end{tabular} + +In the CFA-today scheme, the lowered form is still using a by-value C call. +C does a @memcpy@ on structs passed by value. +And so, @F_BDY@ sees the bits of @__u_for_f@ occurring at an address that has never been presented to the @U@ lifecycle functions. +If @U@ is trying to have a style-\#2 invariant, it shows up broken in @F_BDY@: references that are supposed to be to @u@ are actually to the different location @__u_for_f@. +The \CC scheme does not have this problem because it constructs the for-@f@ copy in the correct location. + +Yet, the \CFA-today scheme is sufficient to deliver style-\#1 invariants (in this style-\#3 use case) because this scheme still does the correct number of lifecycle calls, using correct values, at correct times. So, reference-counting or simple ownership applications get their invariants respected under call/return-by-value. + +% [Mike is not currently seeing how distinguishing initialization from assignment is relevant] +% as opposed to assignment where sender and receiver are in the same stack frame. +% What is crucial for lifecycle management is knowing if the receiver is initialized or uninitialized, \ie an object is or is not currently associated with management. +% To provide this knowledge, languages differentiate between initialization and assignment to a left-hand side. +% \begin{cfa} +% Obj obj2 = obj1; $\C[1.5in]{// initialization, obj2 is initialized}$ +% obj2 = obj1; $\C{// assignment, obj2 must be initialized for management to work}\CRT$ +% \end{cfa} +% Initialization occurs at declaration by value, parameter by argument, return temporary by function call. +% Hence, it is necessary to have two kinds of constructors: by value or object. +% \begin{cfa} +% Obj obj1{ 1, 2, 3 }; $\C[1.5in]{// by value, management is initialized}$ +% Obj obj2 = obj1; $\C{// by obj, management is updated}\CRT$ +% \end{cfa} +% When no object management is required, initialization copies the right-hand value. +% Hence, the calling convention remains uniform, where the unmanaged case uses @memcpy@ as the initialization constructor and managed uses the specified initialization constructor. + +% [Mike is currently seeing RVO as orthogonal, addressed with the footnote] +% to a temporary. +% For example, in \CC: +% \begin{c++} +% struct S {...}; +% S identity( S s ) { return s; } +% S s; +% s = identity( s ); // S temp = identity( s ); s = temp; +% \end{c++} +% the generated code for the function call created a temporary with initialization from the function call, and then assigns the temporary to the object. +% This two step approach means extra storage for the temporary and two copies to get the result into the object variable. +% \CC{17} introduced return value-optimization (RVO)~\cite{RVO20} to ``avoid copying an object that a function returns as its value, including avoiding creation of a temporary object''. +% \CFA uses C semantics for function return giving direct value-assignment, which eliminates unnecessary code, but skips an essential feature needed by lifetime management. +% The following discusses the consequences of this semantics with respect to lifetime management of \CFA strings. + + +The string API offers style \#3's pass-by-value in, for example, in the return of @"a" + "b"@. +Its implementation uses the style-\#2 invariant of the string handles being linked to each other, helping to achieve high performance. +Since these two RAII styles cannont coexist, a workaround splits the API into two layers: one that provides pass-by-value, built upon the other with inter-linked handles. +The layer with pass-by-value incurs a performance penalty, while the layer without delivers the desired runtime performance. +The slower, friendlier High Level API (HL, type @string@) wrapps the faster, more primitive Low Level API (LL, type @string_res@, abbreviating ``resource''). +Both APIs present the same features, up to return-by-value operations being unavailable in LL and implemented via the workaround in HL. +The intention is for most future code to target HL. +When the RAII issue is fixed, the full HL feature set will be acheivable using the LL-style lifetime management. +So then, there will be no need for two API levels; HL will be removed; LL's type will be renamed to @string@; programs written for current HL will run faster. +In the meantime, performance-critical sections of applications must use LL. +Subsequent performance experiments \see{\VRef{s:PerformanceAssessment}} use the LL API when comparing \CFA to other languages. +This measurement gives a fair estimate of the goal state for \CFA. +A separate measure of the HL overhead is also included. + +\VRef[Section]{string-general-impl} described the goal state for \CFA. In present state, the type @string_res@ replaces its mention of @string@ as inter-linked handle. + +To use LL, a programmer rewrites invocations that used pass-by-value APIs into invocations where the resourcing is more explicit. +Many invocations are unaffected, notably including assignment and comparison. +Of the capabilities listed in \VRef[Figure]{f:StrApiCompare}, only the following three cases have revisions. + +\noindent +\begin{tabular}{ll} +HL & LL \\ +\hline +\begin{cfa} +string s = "a" + "b"; +\end{cfa} +& +\begin{cfa} +string_res sr = "a"; +sr += b; +\end{cfa} +\\ +\hline +\begin{cfa} +string s = "abcde"; +string s2 = s(2, 3); // s2 == "cde" +s(2,3) = "x"; // s == "abx" && s2 == "cde" +\end{cfa} +& +\begin{cfa} +string_res sr = "abcde"; +string_res sr2 = {sr, 2, 3}; // sr2 == "cde" +string_res sr_mid = { sr, 2, 3, SHARE }; +sr_mid = "x"; // sr == "abx" && sr2 == "cde" +\end{cfa} +\\ +\hline +\begin{cfa} +string s = "abcde"; +s[2] = "xxx"; // s == "abxxxde" +\end{cfa} +& +\begin{cfa} +string_res sr = "abcde"; +string_res sr_mid = { sr, 2, 1, SHARE }; +mid = "xxx"; // sr == "abxxxde" +\end{cfa} +\end{tabular} + +The actual HL workaround is having @string@ wrap a pointer to a uniquely owned, heap-allocated @string_res@. This arrangement has @string@ being style-\#1 RAII, which is compatible with pass-by-value. + + + \subsection{Sharing implementation} - -The \CFA string module has two mechanisms to handle the case when string handles share a string of text. - -The first type of sharing is the user requests both string handles be views of the same logical, modifiable string. +\label{sharing-impl} + +The \CFA string module has two mechanisms to handle the case when string handles share a run of text. + +In the first type of sharing, the user requests that both string handles be views of the same logical, modifiable string. This state is typically produced by the substring operation. \begin{cfa} @@ -1234,8 +1419,8 @@ A further abstraction, in the string module's implementation, helps distinguish the two senses of sharing. -A share-edit set (SES) is an equivalence class over string handles, being the reflexive, symmetric and transitive closure of the relationship of one string being constructed from another, with the ``share'' opt-in given. +A share-edit set (SES) is an equivalence class over string handles, being the reflexive, symmetric and transitive closure of the relationship of one string being constructed from another, with the ``share'' option given. The SES is represented by a second linked list among the handles. A string that shares edits with no other is in a SES by itself. -Inside a SES, a logical modification of one substring portion may change the logical value in another, depending on whether the two actually overlap. +Inside a SES, a logical modification of one substring portion may change the logical value in another substring portion, depending on whether the two actually overlap. Conversely, no logical value change can flow outside of a SES. Even if a modification on one string handle does not reveal itself \emph{logically} to anther handle in the same SES (because they do not overlap), if the modification is length-changing, completing the modification requires visiting the second handle to adjust its location in the sliding text. @@ -1305,62 +1490,104 @@ I assessed the \CFA string library's speed and memory usage against strings in \CC STL. -The results are presented in even equivalent cases, due to either micro-optimizations foregone, or fundamental costs of the added functionality. -They also show the benefits and tradeoffs, as >100\% effects, of switching to \CFA, with the tradeoff points quantified. -The final test shows the overall win of the \CFA text-sharing mechanism. -It exercises several operations together, showing \CFA enabling clean user code to achieve performance that STL requires less-clean user code to achieve. - -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 ... -\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?] - -To discuss: revisit HL v LL APIs - -To discuss: revisit no-sharing as STL emulation modes + +Overall, this analysis shows that adding support for the features shown earlier in the chapter comes at no substantial cost in the performance of featrues common to both APIs. + +Moreover, the results support the \CFA string's position as a high-level enabler of simplified text processing. +STL makes its user think about memory management. +When the user does, and is successful, STL's performance can be very good. +But when the user fails to think through the consequences of the STL representation, performance becomes poor. +The \CFA string lets the user work at the level of just putting the right text into right variables, with corresponding performance degradations reduced or eliminated. + +% The final test shows the overall win of the \CFA text-sharing mechanism. +% It exercises several operations together, showing \CFA enabling clean user code to achieve performance that STL requires less-clean user code to achieve. \subsection{Methodology} -These tests use a \emph{corpus} of strings (string content is immaterial). -For varying-length strings, the mean length comes from a geometric distribution, which implies that lengths much longer than the mean occur frequently. -The string sizes are: +These tests use a \emph{corpus} of strings. +Their lengths are important; the specific characters occurring in them are immaterial. +In a result graph, a corpus's mean string length is often the independent variable shown on the X axis. + +When a corpus contains strings of different lenghths, the lengths are drawn from a geometric distribution. +Therefore, strings much longer than the mean occur nontrivially and strings slightly shorter than the mean occur most often. +A corpus's string sizes are one of: \begin{description} \item [Fixed-size] all string lengths are of the stated size. - \item [Varying from 1 to N] means the string lengths are drawn from the geometric distribution with a stated mean and all lengths occur. - \item [Varying from 16 to N] means string lengths are drawn from the geometric distribution with the stated mean, but only lengths 16 and above occur; thus, the stated mean is above 16. + \item [Varying 1 and up] the string lengths are drawn from the geometric distribution with a stated mean and all lengths occur. + \item [Varying 16 and up] string lengths are drawn from the geometric distribution with the stated mean, but only lengths 16 and above occur; thus, the stated mean is above 16. \PAB{Is this one unused? May have just been for ``normalize.''} \end{description} -The means for the geometric distribution are the X-axis values in experiments. -The special treatment of length 16 deals with the short-string optimization (SSO) in STL @string@, currently not implemented in \CFA. -When an STL string can fit into a heap pointer, the optimization uses the pointer storage to eliminate using the heap. +The special treatment of length 16 deals with the short-string optimization (SSO) in STL @string@, currently not implemented in \CFA, though a fine future improvement to \CFA. +In the general case, an STL string handle is a pointer (to separately allocated text) and a length. +But when the text is shorter than this representation, the optimization repurposes the handle's storage to eliminate using the heap. \begin{c++} class string { union { - struct { $\C{// long string, string storage in heap}$ + struct { $\C{// long string, text in heap}$ size_t size; char * strptr; } lstr; - char sstr[sizeof(lstr)]; $\C{// short string 8-16 characters, in situ}$ + char sstr[sizeof(lstr)]; $\C{// short string <16 characters, text in situ}$ }; - bool tag; $\C{// string kind, short or long}$ - ... $\C{// other storage}$ + $\C{// tagging for kind (short or long) elided}$ }; \end{c++} -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. +A fixed-size or from-16 distribution ensures that \CC's extra-optimized cases are isolated within, or removed from, the comparison. + In all experiments that use a corpus, its text is generated and loaded into the system under test before the timed phase begins. -To discuss: vocabulary for reused case variables - -To discuss: common approach to iteration and quoted rates - -To discuss: hardware and such - To ensure comparable results, a common memory allocator is used for \CFA and \CC. -The llheap allocator~\cite{Zulfiqar22} is embedded into \CFA and is used standalone with \CC. +\CFA runs the llheap allocator~\cite{Zulfiqar22}; the test rig plugs this same allocator into \CC. + +The operations being measured take dozens of nanoseconds, so a succession of many invocations is run and timed as a group. +The experiments run with fixed duration (targeting approximately 5 seconds), stopping upon passing a goal time, as determined by re-checking @clock()@ every 10,000 invocations, which is never more often than once per 80 ms. +Timing outcomes reprt mean nanoseconds per invocation, which includes harness overhead and the targeted string API execution. + +\PAB{To discuss: hardware and such} + +As discussed in \VRef[Section]{string-raii-limit}, general performance comparisons are made using \CFA's faster, low-level string API, whose string type is named @string_res@. + +\VRef{s:ControllingImplicitSharing} presents an operational mode where \CFA string sharing is turned off. In this mode, the \CFA string operates similarly to \CC's, by using a distinct heap allocation for each string's text. +Some experiments include measurements in this mode for baselining purposes. +It is called ``\CC emulation mode'' or ``nosharing'' here. + \subsection{Test: Append} -This test measures the speed of appending randomly-size text onto a growing string. +These tests measure the speed of appending strings from the corpus onto a larger, growing string. They show \CFA performing comparably to \CC overall, though with reduced penalties for simple API misuses for which \CC programmers may not know to watch out. + +The basic harness is: +\begin{cquote} +\setlength{\tabcolsep}{20pt} +\begin{cfa} +START_TIMER +for ( ... ) { + string_res accum; + for ( i; 100 ) { + accum += corpus[ f(i) ]; // importing from char * here + COUNT_ONE_OP_DONE + } +} +STOP_TIMER +\end{cfa} +\end{cquote} +The harness's outer loop executes until a sample-worthy amount of execution has happened. +The inner loop builds up the desired-length string with successive appends, before the outer makes it start over from a blank accumulator. +Each harness run targets a specific (mean) corpus string length and produces one data point on the result graph. + +Three specific comparisons are made with this harness. +Each picks its own independent-variable basis of comparison. + +All three comparisons use the varying-from-1 corpus construction, \ie they allow the STL to show its advantage from small-string optimization. + + +\subsubsection{Fresh vs Reuse in \CC, Emulation Baseline} + +The first experiment compares \CFA with \CC, with \CFA operating in nosharing mode (and \CC having no other mode). +This experiment simply baselines how \CFA modestly lags \CC's optimization/tuning level generally, yet reproduces a coarser phenomenon. + +This experiment also introduces the first \CC coding pitfall, which the next experiment will show is helped by turning on \CFA sharing. By this pitfall, a \CC programmer must pay attention to string variable reuse. + \begin{cquote} \setlength{\tabcolsep}{20pt} @@ -1370,55 +1597,49 @@ for ( ... ) { - @string x;@ // fresh + @string_res accum;@ // fresh for ( ... ) - x @+=@ ... -} -\end{cfa} -& -\begin{cfa} -string x; + accum @+=@ ... +} +\end{cfa} +& +\begin{cfa} +string_res accum; for ( ... ) { - @x = "";@ $\C[1in]{// reuse}$ + @accum = "";@ $\C[1in]{// reuse\CRT}$ for ( ... ) - x @+=@ ... $\C{// append, alternative x = x + ...}\CRT$ -} -\end{cfa} -\end{tabular} -\end{cquote} -The benchmark's outer loop executes ``until a sample-worthy amount of execution has happened'' and an inner loop for ``building up the desired-length string.'' -Its subcases include, -\begin{enumerate}[leftmargin=*] -\item -\CFA nosharing/sharing \vs \CC nosharing. -\item -Difference between the logically equivalent operations @x += ...@ \vs @x = x + ...@. -For numeric types, the generated code is equivalence, giving identical performance. -However, for string types there can be a significant difference in performance, especially if this code appears in a loop iterating a large number of times. -This difference might not be intuitive to beginners. -\item -Coding practice where 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. -In general, a user should not have to care about this difference, yet the STL performs differently in these cases. -Furthermore, if a function takes a string by reference, if cannot use the fresh approach. -Concretely, both cases incur the cost of copying characters into the target string, but only the allocation-fresh case incurs a further reallocation cost, which is generally paid at points of doubling the length. -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. -\end{enumerate} + accum @+=@ ... +} +\end{cfa} +\end{tabular} +\end{cquote} + +Both programs are doing the same thing: start with @x@ empty and build it up by appending the same chunks. +A programmer should not have to consider this difference. +But from under the covers, each string being an individual allocation leaks through. +While the inner loop is appending text to an @x@ that had not yet grown to have a large capacity, the program is, naturally, paying to extend the variable-length allocation, occasionally. +This capacity stretching is a sticky property that survives assigning a (short, empty-string) value into an existing initialization. +So, the ``reuse'' version benefits from not growing the allocation on subsequent runs of the inner loop. +Yet, the ``fresh'' version is constantly restarting from a small buffer. \begin{figure} \centering - \includegraphics{string-graph-peq-cppemu.pdf} + \includegraphics{plot-string-peq-cppemu.pdf} % \includegraphics[width=\textwidth]{string-graph-peq-cppemu.png} - \caption{Average time per iteration (lower is better) with one \lstinline{x += y} invocation, comparing \CFA with STL implementations (given \CFA running in STL emulation mode), and comparing the ``fresh'' with ``reused'' reset styles, at various string sizes.} + \caption{Fresh vs Reuse in \CC, Emulation Baseline. Average time per iteration with one \lstinline{x += y} invocation (lower is better). Comparing \CFA's STL emulation mode with STL implementations, and comparing the ``fresh'' with ``reused'' reset styles.} \label{fig:string-graph-peq-cppemu} \end{figure} -This tests use the varying-from-1 corpus construction, \ie it assumes 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. -There is a larger penalty for redeclaring the string each loop iteration (fresh) versus hosting it out of the loop and reseting it to the null string (reuse). -The cost is 40\% averaged over the cases shown and minimally 24\%, and shows up consistently between the \CFA and STL implementations, and increases with larger strings. +\VRef[Figure]{fig:string-graph-peq-cppemu} shows the resulting performance. +The fresh \vs reuse penalty is the dominant difference. +The cost is 40\% averaged over the cases shown and minimally 24\%. +It shows up consistently on both the \CFA and STL implementations, and this cost is more prominent with larger strings. + +The lesser \CFA \vs STL difference shows \CFA reproducing 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 implementation fine tuning done with STL and not done yet done with \CFA. + + +\subsubsection{\CFA's Fresh-Reuse Compromise} + +This comparison has the same setup as the last one, except that the \CFA implementation is switched to use its sharing mode. The outcome is that the fresh/reuse difference vanishes in \CFA, with \CFA consistently delivering performance that compromises between the two \CC cases. \begin{figure} @@ -1426,10 +1647,66 @@ \includegraphics{string-graph-peq-sharing.pdf} % \includegraphics[width=\textwidth]{string-graph-peq-sharing.png} - \caption{Average time per iteration (lower is better) with one \lstinline{x += y} invocation, comparing \CFA (having implicit sharing activated) with STL, and comparing the ``fresh'' with ``reused'' reset styles, at various string sizes.} + \caption{\CFA Compromise for Fresh \vs Reuse. Average time per iteration with one \lstinline{x += y} invocation (lower is better). Comparing \CFA's sharing mode with STL, and comparing the ``fresh'' with ``reused'' reset styles. The \CC results are repeated from \ref{fig:string-graph-peq-cppemu}.} \label{fig:string-graph-peq-sharing} \end{figure} -In sharing mode, \CFA makes the fresh/reuse difference disappear, as shown in \VRef[Figure]{fig:string-graph-peq-sharing}. -At append lengths 5 and above, \CFA not only splits the two baseline STL cases, but its slowdown of 16\% over (STL with user-managed reuse) is close to the \CFA-v-STL implementation difference seen with \CFA in STL-emulation mode. +\VRef[Figure]{fig:string-graph-peq-sharing} has the result. +At append lengths 5 and above, \CFA not only splits the two STL cases, but its slowdown of 16\% over STL with user-managed reuse is close to the baseline \CFA-v-STL implementation difference seen with \CFA in STL-emulation mode. + + +\subsubsection{\CFA's low overhead for misusing \lstinline{+}} + +A further pitfall occurs when the user writes @x = x + y@, rather than @x += y@. Again, they are logically equivalent. +For numeric types, the generated code is equivalent, giving identical performance. +However, for string types there can be a significant difference. +This pitfall is a particularly likely hazard for beginners. + +In earlier experiments, the choice of \CFA API among HL and LL had no impact on the functionality being tested. +Here, however, the @+@ operation, which returns its result by value, is only available in HL. +The \CFA @+@ number was obtained by inlining the HL implementation of @+@, which is done using LL's @+=@, into the test harness, while omitting the HL-inherent extra dynamic allocation. The HL-upon-LL @+@ implementation, is: +\begin{cfa} +struct string { + string_res * inner; // RAII manages malloc/free, simple ownership +}; +void ?+=?( string & s, string s2 ) { + (*s.inner) += (*s2.inner); +} +string @?+?@( string lhs, string rhs ) { + string ret = lhs; + ret @+=@ rhs; + return ret; +} +\end{cfa} +This @+@ implementation is also the goal implementation of @+@ once the HL/LL workaround is no longer needed. Inlining the induced LL steps into the test harness gives: +\begin{cquote} +\setlength{\tabcolsep}{20pt} +\begin{tabular}{@{}ll@{}} +\multicolumn{1}{c}{\textbf{Goal}} & \multicolumn{1}{c}{\textbf{Measured}} \\ +\begin{cfa} + +for ( ... ) { + string accum; + for ( ... ) { + accum = @accum + ...@ + + + } +} +\end{cfa} +& +\begin{cfa} +string_res pta_ll_temp; +for ( ... ) { + string_res accum; + for ( ... ) { + pta_ll_temp = @accum@; + pta_ll_temp @+= ...@; + accum = pta_ll_temp; + } +} +\end{cfa} +\end{tabular} +\end{cquote} +Note that this ``Goal'' code functions today in HL. \begin{figure} @@ -1437,17 +1714,23 @@ \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, 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.} + \caption{CFA's low overhead for misusing \lstinline{+}. Average time per iteration with one \lstinline{x += y} invocation (lower is better). Comparing \CFA (having implicit sharing activated) with STL, and comparing the \lstinline{+}-then-\lstinline{=} with the \lstinline{+=} append styles. The \lstinline{+=} results are repeated from \VRef[Figure]{fig:string-graph-peq-sharing}.} \label{fig:string-graph-pta-sharing} \end{figure} -When the user takes a further step beyond the STL's optimal zone, by running @x = x + y@, as in \VRef[Figure]{fig:string-graph-pta-sharing}, the STL's penalty is above $15 \times$ while \CFA's (with sharing) is under $2 \times$, averaged across the cases shown here. +\VRef[Figure]{fig:string-graph-pta-sharing} gives the outcome. The STL's penalty is $8 \times$ while \CFA's is only $2 \times$, averaged across the cases shown here. Moreover, the STL's gap increases with string size, while \CFA's converges. - - -\subsubsection{Test: Pass argument} - -STL has a penalty for passing a string by value, which indirectly forces users to think about memory management when communicating values to a function. +So again, \CFA helps users who just want to treat strings as values, and not think about the resource management under the covers. + +While not a design goal, and not graphed out, \CFA in STL-emulation mode heppened to outperform STL in this case. User-managed allocation reuse did not affect either implementation in this case; only ``fresh'' results are shown. + + +\subsection{Test: Pass argument} + +STL has a penalty for passing a string by value, which forces users to think about memory management when communicating values with a function. +The key \CFA value-add is that a user can think of a string simply as a value; this test shows that \CC charges a stiff penalty for thining this way, while \CFA does not. +This test illustrates a main advantage of the \CFA sharing algorithm (in one case). +It shows STL's small-string optimization providing a successful mitigation (in the other case). + +The basic operation considered is: \begin{cfa} void foo( string s ); @@ -1456,6 +1739,40 @@ \end{cfa} With implicit sharing active, \CFA treats this operation as normal and supported. -This test illustrates a main advantage of the \CFA sharing algorithm. -It also has a case in which STL's small-string optimization provides a successful mitigation. + +Again, an HL-LL difference requires an LL mockup. This time, the fact to integrate into the test harness is that LL does not directly support pass-by-value. +\begin{cquote} +\setlength{\tabcolsep}{20pt} +\begin{tabular}{@{}ll@{}} +\multicolumn{1}{c}{\textbf{Goal}} & \multicolumn{1}{c}{\textbf{Measured}} \\ +\begin{cfa} +void helper( string q ) { + +} +START_TIMER +for ( i; ... ) { + helper( corpus[ f(i) ] ); // imported from char * previously + COUNT_ONE_OP_DONE +} +STOP_TIMER +\end{cfa} +& +\begin{cfa} +void helper( string_res & qref ) { + string_res q = { qref, COPY_VALUE }; +} +// rest same, elided + + + + + +\end{cfa} +\end{tabular} +\end{cquote} +The Goal (HL) version gives the simplest sketch of the test harness. +It uses a single level of looping. +Each iteration uses a corpus item as the argument to a function call. +These corpus items were imported to the string heap before beginning the timed run. + \begin{figure} @@ -1470,25 +1787,28 @@ \end{figure} + \VRef[Figure]{fig:string-graph-pbv} shows the costs for calling a function that receives a string argument by value. STL's performance worsens as string length increases, while \CFA has the same performance at all sizes. -The \CFA cost to pass a string is nontrivial. +While improved, the \CFA cost to pass a string is still 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. +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, upon a \CFA realization of this optimization. At the larger sizes, when STL has to manage storage for the string, STL runs more than $3 \times$ slower, mainly due to time spent in the general-purpose memory allocator. - - -\subsubsection{Test: Allocate} - -This test directly compares the allocation schemes of the \CFA string with sharing, compared with the STL string. -It treats the \CFA scheme as a form of garbage collection, and the STL scheme as an application of malloc-free. -The test shows that \CFA enables faster speed at a cost in memory usage. - -A garbage collector, afforded the freedom of managed memory, often runs faster than malloc-free (in an amortized analysis, even though it must occasionally stop to collect) because it is able to use its collection time to move objects. -(In the case of the mini-allocator powering the \CFA string library, objects are runs of text.) Moving objects lets fresh allocations consume from a large contiguous store of available memory; the ``bump pointer'' book-keeping for such a scheme is very light. -A malloc-free implementation without the freedom to move objects must, in the general case, allocate in the spaces between existing objects; doing so entails the heavier book-keeping to navigate and maintain a linked structure. +\PAB{Need to check that. Expecting copying to dominate.} + + +\subsection{Test: Allocate} + +This test directly compares the allocation schemes of the \CFA string (sharing active), with the STL string. +It treats the \CFA scheme as a form of garbage collection (GC), and the STL scheme as an application of malloc-free. +The test shows that \CFA enables faster speed in exchange for greater memory usage. + +A garbage collector, afforded the freedom of managed memory (where it knows about all the pointers and is allowed to modify them), often runs faster than malloc-free in an amortized analysis, even though it must occasionally stop to collect. +The sppedup happens because GC is able to use its collection time to move objects. +(In the case of the mini-allocator powering the \CFA string library, objects are runs of text.) Moving objects lets fresh allocations consume from a large contiguous store of available memory; the ``bump pointer'' bookkeeping for such a scheme is very light. +A malloc-free implementation without the freedom to move objects must, in the general case, allocate in the spaces between existing objects; doing so entails the heavier bookkeeping of maintaining a linked structure of freed allocations and/or coalescing freed allocations. A garbage collector keeps allocations around for longer than the using program can reach them. -By contrast, a program using malloc-free (correctly) releases allocations exactly when they are no longer reachable. +By contrast, a program (correctly) using malloc-free releases allocations exactly when they are no longer reachable. Therefore, the same harness will use more memory while running under garbage collection. A garbage collector can minimize the memory overhead by searching for these dead allocations aggressively, that is, by collecting more often. @@ -1507,10 +1827,36 @@ The allocator will expand its text buffer during a collection if the actual fraction live exceeds this target. -This experiment's driver allocates strings by constructing a string handle as a local variable then looping over recursive calls. -The time measurement is of nanoseconds per such allocating call. -The arrangement of recursive calls and their fan-out (iterations per recursion level) makes some of the strings long-lived and some of them short-lived. -String lifetime (measured in number of subsequent string allocations) is ?? distributed, because each node in the call tree survives as long as its descendent calls. -The run presented in this section used a call depth of 1000 and a fan-out of 1.006, which means that approximately one call in 167 makes two recursive calls, while the rest make one. +\begin{figure} +\centering + \includegraphics{string-perf-alloc.pdf} + \caption{} + \label{fig:string-perf-alloc} +\end{figure} + +\VRef[Figure]{fig:string-perf-alloc} shows the memory-allocation pattern that the test harness drives. +Note how this pattern creates few long-lived strings and many short-lived strings. +To extend this pattern to the scale of a performance test, the harness is actually recursive, to achieve the nesting (three levels in the figure), and iterative, to achieve the fan-out (factor two / binary tree in the figure). +\begin{cfa} +void f( int depth ) { + if (depth == 0) return; + string_res x = corpus[...]; // importing from char * here + COUNT_ONE_OP_DONE + for ( fanOut ) { + // elided: terminate fixed-duration experiment + f( depth - 1 ); + } +} +START_TIMER +f( launchDepth ); +STOP_TIMER +\end{cfa} +The runs presented use a call depth of 1000 and a fan-out of 1.006, which means that approximately one call in 167 makes two recursive calls, while the rest make one. +This sizing keeps an average of 836 strings live. This sizing was chosen to keep the amounts of consumed memory within the machine's last-level cache. + +The time measurement is of nanoseconds per such @f@-call, be it internal or leaf. + +% String lifetime (measured in number of subsequent string allocations) is ?? distributed, because each node in the call tree survives as long as its descendent calls. + \begin{figure} @@ -1518,30 +1864,30 @@ \includegraphics{string-graph-allocn.pdf} % \includegraphics[width=\textwidth]{string-graph-allocn.png} - \caption{Space and time performance, under varying fraction-live targets, for the five string lengths shown, at (\emph{Fixed-size} corpus construction. + \caption{Space and time performance, under varying fraction-live targets, for the five string lengths shown, at \emph{Fixed-size} corpus construction. [MISSING] The identified clusters are for the default fraction-live target, which is 30\%. MISSING: STL results, typically just below the 0.5--0.9 \CFA segment. -All runs keep an average of 836 strings live, and the median string lifetime is ?? allocations.} +} \label{fig:string-graph-allocn} \end{figure} \VRef[Figure]{fig:string-graph-allocn} shows the results of this experiment. -At all string sizes, varying the liveness threshold gives offers speed-for-space tradeoffs relative to STL. +At all string sizes, varying the liveness threshold gives speed-for-space tradeoffs relative to STL. At the default liveness threshold, all measured string sizes see a ??\%--??\% speedup for a ??\%--??\% increase in memory footprint. -\subsubsection{Test: Normalize} - -This test is more applied than the earlier ones. -It combines the effects of several operations. -It also demonstrates a case of the \CFA API allowing user code to perform well, while being written without overt memory management, while achieving similar performance in STL requires adding memory-management complexity. - -To motivate: edits being rare - -The program is doing a specialized find-replace operation on a large body of text. -In the program under test, the replacement is just to erase a magic character. -But in the larger software problem represented, the rewrite logic belongs to a module that was originally intended to operate on simple, modest-length strings. -The challenge is to apply this packaged function across chunks taken from the large body. -Using the \CFA string library, the most natural way to write the helper module's function also works well in the adapted context. -Using the STL string, the most natural ways to write the helper module's function, given its requirements in isolation, slow down when it is driven in the adapted context. +% \subsection{Test: Normalize} + +% This test is more applied than the earlier ones. +% It combines the effects of several operations. +% It also demonstrates a case of the \CFA API allowing user code to perform well, while being written without overt memory management, while achieving similar performance in STL requires adding memory-management complexity. + +% To motivate: edits being rare + +% The program is doing a specialized find-replace operation on a large body of text. +% In the program under test, the replacement is just to erase a magic character. +% But in the larger software problem represented, the rewrite logic belongs to a module that was originally intended to operate on simple, modest-length strings. +% The challenge is to apply this packaged function across chunks taken from the large body. +% Using the \CFA string library, the most natural way to write the helper module's function also works well in the adapted context. +% Using the STL string, the most natural ways to write the helper module's function, given its requirements in isolation, slow down when it is driven in the adapted context. \begin{lstlisting} Index: doc/theses/mike_brooks_MMath/uw-ethesis.bib =================================================================== --- doc/theses/mike_brooks_MMath/uw-ethesis.bib (revision b195498ca6cf118ea16f39c6f8feaf910d504d33) +++ doc/theses/mike_brooks_MMath/uw-ethesis.bib (revision f85de474d7bae82407a8ea5f1551da282d77d9bd) @@ -19,9 +19,18 @@ % -------------------------------------------------- -% C Array facts +% C facts @misc{arr:gnu-flex-mbr, title = {Arrays of Length Zero}, howpublished= {\url{https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html}}, +} + + +% -------------------------------------------------- +% C++ facts + +@misc{cxx:raii-abi, + title = {Itanium C++ ABI}, + howpublished= {\url{https://itanium-cxx-abi.github.io/cxx-abi/abi.html}}, }