Ignore:
Timestamp:
May 13, 2025, 1:17:50 PM (6 months ago)
Author:
Mike Brooks <mlbrooks@…>
Branches:
master
Children:
0528d79
Parents:
7d02d35 (diff), 2410424 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:
doc/theses/mike_brooks_MMath
Files:
22 added
17 deleted
11 edited
3 moved

Legend:

Unmodified
Added
Removed

  • doc/theses/mike_brooks_MMath/Makefile

    r7d02d35 rbd72f517  
    1313TeXSRC = ${wildcard *.tex}
    1414PicSRC = ${notdir ${wildcard ${Pictures}/*.png}} ${notdir ${wildcard ${Pictures}/*.fig}}
    15 PicSRC := ${PicSRC:.fig=.pdf}           # substitute ".fig" with ".pdf"
    16 GraphSRC_OLD = ${notdir ${wildcard ${Pictures}/*.dat}}
    17 GraphSRC_OLD := ${GraphSRC_OLD:.dat=.pdf}               # substitute ".dat" with ".pdf"
    18 PlotINPUTS = ${wildcard ${Plots}/*.gp} ${wildcard ${Plots}/*.py}
    19 PlotINPUTS := ${addsuffix .INPUTS,${PlotINPUTS}}
     15PicSRC := ${PicSRC:.fig=.pdf}                   # substitute ".fig" with ".pdf"
    2016PlotSRC = ${notdir ${wildcard ${Plots}/*.gp}}
    21 PlotSRC := ${addprefix ${Build}/plot-,${PlotSRC:.gp=.pdf}}              # substitute ".gp" with ".pdf"
     17PlotSRC := ${addprefix ${Build}/plot-,${PlotSRC:.gp=.pdf}} # substitute ".gp" with ".pdf"
    2218DemoPgmSRC = ${notdir ${wildcard ${Programs}/*-demo.cfa}}
    2319PgmSRC = ${notdir ${wildcard ${Programs}/*}}
    … …  
    4945# Rules and Recipes
    5046
    51 .PHONY : all clean                      # not file names
     47.PHONY : all clean                              # not file names
    5248.SECONDARY:
    5349#.PRECIOUS : ${Build}/%                         # don't delete intermediates
    … …  
    6157# File Dependencies
    6258
    63 ${DOCUMENT}: ${TeXSRC} $(RunPgmOut) ${DemoPgmOut} ${GraphSRC_OLD} ${PlotSRC} ${PicSRC} ${BibSRC} ${BibRep}/pl.bib ${LaTMac}/common.tex Makefile | ${Build}
     59${DOCUMENT}: ${TeXSRC} $(RunPgmOut) ${DemoPgmOut} ${PlotSRC} ${PicSRC} ${BibSRC} ${BibRep}/pl.bib ${LaTMac}/common.tex Makefile | ${Build}
    6460        echo ${PicSRC}
    6561        echo ${GraphSRC_OLD}
    … …  
    8278        ${CFA} $< -o $@
    8379
    84 ${Build}/%: ${Programs}/%.run.cfa | ${Build} # cfa cannot handle pipe
     80${Build}/%: ${Programs}/%.run.cfa | ${Build}    # cfa cannot handle pipe
    8581        sed -f ${Programs}/sedcmd $< > ${Build}/tmp.cfa; ${CFA} ${Build}/tmp.cfa -o $@
    8682
    … …  
    9490        $< > $@
    9591
    96 string-graph-peq-sharing.pdf: string-graph-peq-sharing.dat plot-peq-sharing.gp | ${Build}
    97         gnuplot plot-peq-sharing.gp
    98 
    99 string-graph-pta-sharing.pdf: string-graph-pta-sharing.dat plot-pta-sharing.gp | ${Build}
    100         gnuplot plot-pta-sharing.gp
    101 
    102 string-graph-pbv.pdf: string-graph-pbv.dat plot-pbv.gp | ${Build}
    103         gnuplot plot-pbv.gp
    104 
    105 string-graph-allocn.pdf: string-graph-allocn.dat plot-allocn.gp | ${Build}
    106         gnuplot plot-allocn.gp
    107 
    10892%.pdf: %.fig | ${Build}
    10993        fig2dev -L pdf $< > ${Build}/$@
    11094
    111 -include $(Plots)/string-peq-cppemu.d
     95-include $(Plots)/*.d
    11296
    11397${Build}/plot-%.dat: ${Plots}/%.py ${Plots}/%.py.INPUTS | ${Build}
    114         echo ${PlotINPUTS}     
    11598        python3 $< > $@
    11699

  • doc/theses/mike_brooks_MMath/array.tex

    r7d02d35 rbd72f517  
    1717though using a new style of generic parameter.
    1818\begin{cfa}
    19 @array( float, 99 )@ x;                                 $\C[2.75in]{// x contains 99 floats}$
    20 \end{cfa}
    21 Here, the arguments to the @array@ type are @float@ (element type) and @99@ (length).
    22 When this type is used as a function parameter, the type-system requires that a call's argument is a perfect match.
     19@array( float, 99 )@ x;                                 $\C[2.5in]{// x contains 99 floats}$
     20\end{cfa}
     21Here, the arguments to the @array@ type are @float@ (element type) and @99@ (dimension).
     22When this type is used as a function parameter, the type-system requires the argument is a perfect match.
    2323\begin{cfa}
    2424void f( @array( float, 42 )@ & p ) {}   $\C{// p accepts 42 floats}$
    2525f( x );                                                                 $\C{// statically rejected: type lengths are different, 99 != 42}$
    26 
    2726test2.cfa:3:1 error: Invalid application of existing declaration(s) in expression.
    2827Applying untyped:  Name: f ... to:  Name: x
    2928\end{cfa}
    30 Here, the function @f@'s parameter @p@ is declared with length 42.
    31 However, the call @f( x )@ is invalid, because @x@'s length is @99@, which does not match @42@.
    32 
    33 A function declaration can be polymorphic over these @array@ arguments by using the \CFA @forall@ declaration prefix.
     29Function @f@'s parameter expects an array with dimension 42, but the argument dimension 99 does not match.
     30
     31A function can be polymorphic over @array@ arguments using the \CFA @forall@ declaration prefix.
    3432\begin{cfa}
    3533forall( T, @[N]@ )
    … …  
    3836}
    3937g( x, 0 );                                                              $\C{// T is float, N is 99, dynamic subscript check succeeds}$
    40 g( x, 1000 );                                                   $\C{// T is float, N is 99, dynamic subscript check fails}\CRT$
    41 
     38g( x, 1000 );                                                   $\C{// T is float, N is 99, dynamic subscript check fails}$
    4239Cforall Runtime error: subscript 1000 exceeds dimension range [0,99) $for$ array 0x555555558020.
    4340\end{cfa}
    44 Function @g@ takes an arbitrary type parameter @T@ and a \emph{dimension parameter} @N@.
    45 A dimension parameter represents a to-be-determined count of elements, managed by the type system.
    46 The call @g( x, 0 )@ is valid because @g@ accepts any length of array, where the type system infers @float@ for @T@ and length @99@ for @N@.
    47 Inferring values for @T@ and @N@ is implicit.
    48 Furthermore, in this case, the runtime subscript @x[0]@ (parameter @i@ being @0@) in @g@ is valid because 0 is in the dimension range $[0,99)$ of argument @x@.
    49 However, the call @g( x, 1000 )@ is also accepted through compile time;
    50 however, this case's subscript, @x[1000]@, generates an error, because @1000@ is outside the dimension range $[0,99)$ of argument @x@.
     41Function @g@ takes an arbitrary type parameter @T@ and an unsigned integer \emph{dimension} @N@.
     42The dimension represents a to-be-determined number of elements, managed by the type system, where 0 represents an empty array.
     43The type system implicitly infers @float@ for @T@ and @99@ for @N@.
     44Furthermore, the runtime subscript @x[0]@ (parameter @i@ being @0@) in @g@ is valid because 0 is in the dimension range $[0,99)$ for argument @x@.
     45The call @g( x, 1000 )@ is also accepted at compile time.
     46However, the subscript, @x[1000]@, generates a runtime error, because @1000@ is outside the dimension range $[0,99)$ of argument @x@.
    5147In general, the @forall( ..., [N] )@ participates in the user-relevant declaration of the name @N@, which becomes usable in parameter/return declarations and within a function.
    5248The syntactic form is chosen to parallel other @forall@ forms:
    5349\begin{cfa}
    54 forall( @[N]@ ) ...     $\C[1.5in]{// dimension}$
    55 forall( T ) ...         $\C{// value datatype (formerly, "otype")}$
    56 forall( T & ) ...       $\C{// opaque datatype (formerly, "dtype")}\CRT$
     50forall( @[N]@ ) ...     $\C{// dimension}$
     51forall( T ) ...         $\C{// value datatype}$
     52forall( T & ) ...       $\C{// opaque datatype}$
    5753\end{cfa}
    5854% The notation @array(thing, N)@ is a single-dimensional case, giving a generic type instance.
    … …  
    6359\begin{cfa}
    6460forall( [N] )
    65 void declDemo( ... ) {
    66         float x1[N];                                            $\C{// built-in type ("C array")}$
    67         array(float, N) x2;                                     $\C{// type from library}$
    68 }
    69 \end{cfa}
    70 Both of the locally-declared array variables, @x1@ and @x2@, have 42 elements, each element being a @float@.
    71 The two variables have identical size and layout; they both encapsulate 42-float stack allocations, with no additional ``bookkeeping'' allocations or headers.
     61void f( ... ) {
     62        float x1[@N@];                                          $\C{// C array, no subscript checking}$
     63        array(float, N) x2;                                     $\C{// \CFA array, subscript checking}\CRT$
     64}
     65\end{cfa}
     66Both of the stack declared array variables, @x1@ and @x2@, have 42 elements, each element being a @float@.
     67The two variables have identical size and layout, with no additional ``bookkeeping'' allocations or headers.
     68The C array, @x1@, has no subscript checking, while \CFA array, @x2@, does.
    7269Providing this explicit generic approach requires a significant extension to the \CFA type system to support a full-feature, safe, efficient (space and time) array-type, which forms the foundation for more complex array forms in \CFA.
    73 In all following discussion, ``C array'' means the types like that of @x@ and ``\CFA array'' means the standard-library @array@ type (instantiations), like the type of @x2@.
    74 
    75 Admittedly, the @array@ library type for @x2@ is syntactically different from its C counterpart.
    76 A future goal (TODO xref) is to provide the new @array@ features with syntax approaching C's (declaration style of @x1@).
     70In all following discussion, ``C array'' means types like @x1@ and ``\CFA array'' means types like @x2@.
     71
     72A future goal is to provide the new @array@ features with syntax approaching C's (declaration style of @x1@).
    7773Then, the library @array@ type could be removed, giving \CFA a largely uniform array type.
    78 At present, the C-syntax @array@ is only partially supported, so the generic @array@ is used exclusively in the thesis;
    79 feature support and C compatibility are revisited in Section ? TODO.
     74At present, the C-syntax @array@ is only partially supported, so the generic @array@ is used exclusively in the thesis.
    8075
    8176My contributions in this chapter are:
    82 \begin{enumerate}
     77\begin{enumerate}[leftmargin=*]
    8378\item A type system enhancement that lets polymorphic functions and generic types be parameterized by a numeric value: @forall( [N] )@.
    84 \item Provide a length-checked array-type in the \CFA standard library, where the array's length is statically managed and dynamically valued.
     79\item Provide a dimension/subscript-checked array-type in the \CFA standard library, where the array's length is statically managed and dynamically valued.
    8580\item Provide argument/parameter passing safety for arrays and subscript safety.
    86 \item TODO: general parking...
    8781\item Identify the interesting specific abilities available by the new @array@ type.
    8882\item Where there is a gap concerning this feature's readiness for prime-time, identification of specific workable improvements that are likely to close the gap.
    … …  
    9084
    9185
     86\begin{comment}
    9287\section{Dependent Typing}
    9388
    94 General dependent typing allows the type system to encode arbitrary predicates (\eg behavioural specifications for functions),
    95 which is an anti-goal for my work.
     89General dependent typing allows a type system to encode arbitrary predicates, \eg behavioural specifications for functions, which is an anti-goal for my work.
    9690Firstly, this application is strongly associated with pure functional languages,
    9791where a characterization of the return value (giving it a precise type, generally dependent upon the parameters)
    … …  
    10195Secondly, TODO: bash Rust.
    10296TODO: cite the crap out of these claims.
     97\end{comment}
    10398
    10499
    105100\section{Features Added}
    106101
    107 This section shows more about using the \CFA array and dimension parameters, demonstrating their syntax and semantics by way of motivating examples.
     102This section shows more about using the \CFA array and dimension parameters, demonstrating syntax and semantics by way of motivating examples.
    108103As stated, the core capability of the new array is tracking all dimensions within the type system, where dynamic dimensions are represented using type variables.
    109104
    110105By declaring type variables at the front of object declarations, an array dimension is lexically referenceable where it is needed.
    111 For example, a declaration can share one length, @N@, among a pair of parameters and the return,
    112 meaning that it requires both input arrays to be of the same length, and guarantees that the result is of that length as well.
     106For example, a declaration can share one length, @N@, among a pair of parameters and return type, meaning the input arrays and return array are the same length.
    113107\lstinput{10-17}{hello-array.cfa}
    114108Function @f@ does a pointwise comparison of its two input arrays, checking if each pair of numbers is within half a percent of each other, returning the answers in a newly allocated @bool@ array.
    115 The dynamic allocation of the @ret@ array, by the library @alloc@ function,
     109The dynamic allocation of the @ret@ array uses the library @alloc@ function,
    116110\begin{cfa}
    117111forall( T & | sized(T) )
    … …  
    120114}
    121115\end{cfa}
    122 uses the parameterized dimension information implicitly within its @sizeof@ determination, and casts the return type.
    123 Note that @alloc@ only sees one whole type for its @T@ (which is @f@'s @array(bool, N)@); this type's size is a computation based on @N@.
     116which captures the parameterized dimension information implicitly within its @sizeof@ determination, and casts the return type.
     117Note, @alloc@ only sees the whole type for its @T@, @array(bool, N)@, where this type's size is a computation based on @N@.
    124118This example illustrates how the new @array@ type plugs into existing \CFA behaviour by implementing necessary \emph{sized} assertions needed by other types.
    125119(\emph{sized} implies a concrete \vs abstract type with a runtime-available size, exposed as @sizeof@.)
    … …  
    129123\lstinput{30-43}{hello-array.cfa}
    130124\lstinput{45-48}{hello-array.cfa}
    131 \caption{\lstinline{f} Harness}
    132 \label{f:fHarness}
     125\caption{\lstinline{f} Example}
     126\label{f:fExample}
    133127\end{figure}
    134128
    135 \VRef[Figure]{f:fHarness} shows a harness that uses function @f@, illustrating how dynamic values are fed into the @array@ type.
     129\VRef[Figure]{f:fExample} shows an example using function @f@, illustrating how dynamic values are fed into the @array@ type.
    136130Here, the dimension of arrays @x@, @y@, and @result@ is specified from a command-line value, @dim@, and these arrays are allocated on the stack.
    137131Then the @x@ array is initialized with decreasing values, and the @y@ array with amounts offset by constant @0.005@, giving relative differences within tolerance initially and diverging for later values.
    … …  
    144138
    145139In summary:
    146 \begin{itemize}
     140\begin{itemize}[leftmargin=*]
    147141\item
    148142@[N]@ within a @forall@ declares the type variable @N@ to be a managed length.
    149143\item
    150 @N@ can be used an expression of type @size_t@ within the declared function body.
     144@N@ can be used in an expression with type @size_t@ within the function body.
    151145\item
    152146The value of an @N@-expression is the acquired length, derived from the usage site, \ie generic declaration or function call.
    … …  
    158152\begin{enumerate}[leftmargin=*]
    159153\item
    160 The \CC template @N@ can only be compile-time value, while the \CFA @N@ may be a runtime value.
    161 % agreed, though already said
     154The \CC template @N@ can only be a compile-time value, while the \CFA @N@ may be a runtime value.
    162155\item
    163156\CC does not allow a template function to be nested, while \CFA lets its polymorphic functions to be nested.
    164 % why is this important?
    165 \item
     157Hence, \CC precludes a simple form of information hiding.
     158\item
     159\label{p:DimensionPassing}
    166160The \CC template @N@ must be passed explicitly at the call, unless @N@ has a default value, even when \CC can deduct the type of @T@.
    167161The \CFA @N@ is part of the array type and passed implicitly at the call.
    … …  
    169163% mycode/arrr/thesis-examples/check-peter/cs-cpp.cpp, v2
    170164\item
    171 \CC cannot have an array of references, but can have an array of pointers.
     165\CC cannot have an array of references, but can have an array of @const@ pointers.
    172166\CC has a (mistaken) belief that references are not objects, but pointers are objects.
    173167In the \CC example, the arrays fall back on C arrays, which have a duality with references with respect to automatic dereferencing.
    … …  
    178172% https://stackoverflow.com/questions/922360/why-cant-i-make-a-vector-of-references
    179173\item
     174\label{p:ArrayCopy}
    180175C/\CC arrays cannot be copied, while \CFA arrays can be copied, making them a first-class object (although array copy is often avoided for efficiency).
    181176% fixed by comparing to std::array
    182177% mycode/arrr/thesis-examples/check-peter/cs-cpp.cpp, v10
    183178\end{enumerate}
    184 TODO: settle Mike's concerns with this comparison (perhaps, remove)
     179The \CC template @array@ type mitigates points \VRef[]{p:DimensionPassing} and \VRef[]{p:ArrayCopy}, but it is also trying to accomplish a similar mechanism to \CFA @array@.
    185180
    186181\begin{figure}
    … …  
    226221Just as the first example in \VRef[Section]{s:ArrayIntro} shows a compile-time rejection of a length mismatch,
    227222so are length mismatches stopped when they involve dimension parameters.
    228 While \VRef[Figure]{f:fHarness} shows successfully calling a function @f@ expecting two arrays of the same length,
     223While \VRef[Figure]{f:fExample} shows successfully calling a function @f@ expecting two arrays of the same length,
    229224\begin{cfa}
    230225array( bool, N ) & f( array( float, N ) &, array( float, N ) & );
    … …  
    246241The same argument safety and the associated implicit communication of array length occurs.
    247242Preexisting \CFA allowed aggregate types to be generalized with type parameters, enabling parameterizing of element types.
    248 Now, \CFA also allows parameterizing them by length.
    249 Doing so gives a refinement of C's ``flexible array member'' pattern[TODO: cite ARM 6.7.2.1 pp18]\cite{arr:gnu-flex-mbr}.
    250 While a C flexible array member can only occur at the end of the enclosing structure,
    251 \CFA allows length-parameterized array members to be nested at arbitrary locations.
    252 This flexibility, in turn, allows for multiple array members.
     243This has been extended to allow parameterizing by dimension.
     244Doing so gives a refinement of C's ``flexible array member''~\cite[\S~6.7.2.1.18]{C11}.
     245\begin{cfa}
     246struct S {
     247        ...
     248        double d []; // incomplete array type => flexible array member
     249} * s = malloc( sizeof( struct S ) + sizeof( double [10] ) );
     250\end{cfa}
     251which creates a VLA of size 10 @double@s at the end of the structure.
     252A C flexible array member can only occur at the end of a structure;
     253\CFA allows length-parameterized array members to be nested at arbitrary locations, with intervening member declarations.
    253254\lstinput{10-15}{hello-accordion.cfa}
    254255The structure has course- and student-level metatdata (their respective field names) and a position-based preferences' matrix.
    255256Its layout has the starting offset of @studentIds@ varying according to the generic parameter @C@, and the offset of @preferences@ varying according to both generic parameters.
    256257
    257 \VRef[Figure]{f:checkHarness} shows a program main using @School@ and results with different array sizes.
     258\VRef[Figure]{f:checkExample} shows a program main using @School@ and results with different array sizes.
    258259The @school@ variable holds many students' course-preference forms.
    259260It is on the stack and its initialization does not use any casting or size arithmetic.
    … …  
    285286\end{cquote}
    286287
    287 \caption{\lstinline{School} harness, input and output}
    288 \label{f:checkHarness}
     288\caption{\lstinline{School} Example, Input and Output}
     289\label{f:checkExample}
    289290\end{figure}
    290291
    291292When a function operates on a @School@ structure, the type system handles its memory layout transparently.
    292293\lstinput{30-37}{hello-accordion.cfa}
    293 In the example, this @getPref@ function answers, for the student at position @is@, what is the position of its @pref@\textsuperscript{th}-favoured class?
     294In the example, function @getPref@ returns, for the student at position @is@, what is the position of their @pref@\textsuperscript{th}-favoured class?
    294295
    295296
    … …  
    324325
    325326The repurposed heavy equipment is
    326 \begin{itemize}
     327\begin{itemize}[leftmargin=*]
    327328\item
    328329        Resolver provided values for a used declaration's type-system variables,
    … …  
    348349int main() {
    349350        thing( @10@ ) x;  f( x );  $\C{// prints 10, [4]}$
    350         thing( 100 ) y;  f( y );  $\C{// prints 100}$
    351         return 0;
     351        thing( @100@ ) y;  f( y );  $\C{// prints 100}$
    352352}
    353353\end{cfa}
    354354This example has:
    355 \begin{enumerate}
     355\begin{enumerate}[leftmargin=*]
    356356\item
    357357        The symbol @N@ being declared as a type variable (a variable of the type system).
    … …  
    369369Because the box pass handles a type's size as its main datum, the encoding is chosen to use it.
    370370The production and recovery are then straightforward.
    371 \begin{itemize}
     371\begin{itemize}[leftmargin=*]
    372372\item
    373373        The value $n$ is encoded as a type whose size is $n$.
    374374\item
    375         Given a dimension expression $e$, produce type @char[@$e$@]@ to represent it.
     375        Given a dimension expression $e$, produce an internal type @char[@$e$@]@ to represent it.
    376376        If $e$ evaluates to $n$ then the encoded type has size $n$.
    377377\item
    … …  
    389389}
    390390int main() {
    391         thing( char[@10@] ) x;  f( x );  $\C{// prints 10, [4]}$
    392         thing( char[100] ) y;  f( y );  $\C{// prints 100}$
    393         return 0;
     391        thing( @char[10]@ ) x;  f( x );  $\C{// prints 10, [4]}$
     392        thing( @char[100]@ ) y;  f( y );  $\C{// prints 100}$
    394393}
    395394\end{cfa}
    396395Observe:
    397 \begin{enumerate}
     396\begin{enumerate}[leftmargin=*]
    398397\item
    399398        @N@ is now declared to be a type.
    400         It is declared to be \emph{sized} (by the @*@), meaning that the box pass shall do its @sizeof(N)@--@__sizeof_N@ extra parameter and expression translation.
     399        It is declared to be \emph{sized} (by the @*@), meaning that the box pass shall do its @sizeof(N)@$\rightarrow$@__sizeof_N@ extra parameter and expression translation.
    401400\item
    402401        @thing(N)@ is a type; the argument to the generic @thing@ is a type (type variable).
    … …  
    404403        The @sout...@ expression (being an application of the @?|?@ operator) has a second argument that is an ordinary expression.
    405404\item
    406         The type of variable @x@ is another @thing(-)@ type; the argument to the generic @thing@ is a type (array type of bytes, @char@).
     405        The type of variable @x@ is another @thing(-)@ type; the argument to the generic @thing@ is a type (array type of bytes, @char[@$e$@]@).
    407406\end{enumerate}
    408407
    … …  
    415414        struct __conc_thing_10 {} x;  f( @10@, &x );  $\C{// prints 10, [4]}$
    416415        struct __conc_thing_100 {} y;  f( @100@, &y );  $\C{// prints 100}$
    417         return 0;
    418416}
    419417\end{cfa}
    420418Observe:
    421 \begin{enumerate}
     419\begin{enumerate}[leftmargin=*]
    422420\item
    423421        The type parameter @N@ is gone.
    … …  
    427425        The @sout...@ expression (being an application of the @?|?@ operator) has a regular variable (parameter) usage for its second argument.
    428426\item
    429         Information about the particular @thing@ instantiation (value 10) has moved, from the type, to a regular function-call argument.
     427        Information about the particular @thing@ instantiation (value 10) is moved, from the type, to a regular function-call argument.
    430428\end{enumerate}
    431429At the end of the desugaring and downstream processing, the original C idiom of ``pass both a length parameter and a pointer'' has been reconstructed.
    … …  
    433431The compiler's action produces the more complex form, which if handwritten, would be error-prone.
    434432
    435 Back at the compiler front end, the parsing changes AST schema extensions and validation rules for enabling the sugared user input.
    436 \begin{itemize}
     433At the compiler front end, the parsing changes AST schema extensions and validation rules for enabling the sugared user input.
     434\begin{itemize}[leftmargin=*]
    437435\item
    438436        Recognize the form @[N]@ as a type-variable declaration within a @forall@.
    … …  
    440438        Have the new brand of type-variable, \emph{Dimension}, in the AST form of a type-variable, to represent one parsed from @[-]@.
    441439\item
    442         Allow a type variable to occur in an expression.  Validate (after parsing) that only dimension-branded type variables are used here.
     440        Allow a type variable to occur in an expression.  Validate (after parsing) that only dimension-branded type-variables are used here.
    443441\item
    444442        Allow an expression to occur in type-argument position.  Brand the resulting type argument as a dimension.
    … …  
    457455\label{s:ArrayTypingC}
    458456
    459 Essential in giving a guarantee of accurate length is the compiler's ability
    460 to reject a program that presumes to mishandle length.
    461 By contrast, most discussion so far dealt with communicating length,
    462 from one party who knows it, to another who is willing to work with any given length.
    463 For scenarios where the concern is a mishandled length,
    464 the interaction is between two parties who both claim to know something about it.
    465 Such a scenario occurs in this pure C fragment, which today's C compilers accept:
    466 \begin{cfa}
    467 int n = @42@;
    468 float x[n];
    469 float (*xp)[@999@] = &x;
     457Essential in giving a guarantee of accurate length is the compiler's ability to reject a program that presumes to mishandle length.
     458By contrast, most discussion so far deals with communicating length, from one party who knows it, to another willing to work with any given length.
     459For scenarios where the concern is a mishandled length, the interaction is between two parties who both claim to know something about it.
     460
     461C and \CFA can check when working with two static values.
     462\begin{cfa}
     463enum { n = 42 };
     464float x[@n@];   // or just 42
     465float (*xp1)[@42@] = &x;    // accept
     466float (*xp2)[@999@] = &x;   // reject
     467warning: initialization of 'float (*)[999]' from incompatible pointer type 'float (*)[42]'
     468\end{cfa}
     469When a variable is involved, C and \CFA take two different approaches.
     470Today's C compilers accept the following without warning.
     471\begin{cfa}
     472static const int n = 42;
     473float x[@n@];
     474float (* xp)[@999@] = &x; $\C{// should be static rejection here}$
    470475(*xp)[@500@]; $\C{// in "bound"?}$
    471476\end{cfa}
    472477Here, the array @x@ has length 42, while a pointer to it (@xp@) claims length 999.
    473 So, while the subscript of @xp@ at position 500 is out of bound of its referent @x@,
     478So, while the subscript of @xp@ at position 500 is out of bound with its referent @x@,
    474479the access appears in-bound of the type information available on @xp@.
    475 Truly, length is being mishandled in the previous step,
    476 where the type-carried length information on @x@ is not compatible with that of @xp@.
    477 
    478 The \CFA new-array rejects the analogous case:
    479 \begin{cfa}
    480 int n = @42@;
    481 array(float, n) x;
    482 array(float, 999) * xp = x; $\C{// static rejection here}$
    483 (*xp)[@500@]; $\C{// runtime check vs len 999}$
    484 \end{cfa}
    485 The way the \CFA array is implemented, the type analysis of this case reduces to a case similar to the earlier C version.
     480In fact, length is being mishandled in the previous step, where the type-carried length information on @x@ is not compatible with that of @xp@.
     481
     482In \CFA, I choose to reject this C example at the point where the type-carried length information on @x@ is not compatible with that of @xp@, and correspondingly, its array counterpart at the same location:
     483\begin{cfa}
     484static const int n = 42;
     485array( float, @n@ ) x;
     486array( float, @999@ ) * xp = &x; $\C{// static rejection here}$
     487(*xp)[@500@]; $\C{// runtime check passes}$
     488\end{cfa}
     489The way the \CFA array is implemented, the type analysis for this case reduces to a case similar to the earlier C version.
    486490The \CFA compiler's compatibility analysis proceeds as:
    487491\begin{itemize}[parsep=0pt]
    488492\item
    489         Is @array(float, 999)@ type-compatible with @array(float, n)@?
    490 \item
    491         Is @arrayX(float, char[999])@ type-compatible with @arrayX(float, char[n])@?\footnote{
    492                 Here, \lstinline{arrayX} represents the type that results
    493                 from desugaring the \lstinline{array} type
    494                 into a type whose generic parameters are all types.
    495                 This presentation elides the noisy fact that
    496                 \lstinline{array} is actually a macro for something bigger;
    497                 the reduction to \lstinline{char[-]} still proceeds as sketched.}
    498 \item
    499         Is @char[999]@ type-compatible with @char[n]@?
     493        Is @array( float, 999 )@ type-compatible with @array( float, n )@?
     494\item
     495        Is desugared @array( float, char[999] )@ type-compatible with desugared @array( float, char[n] )@?
     496%               \footnote{
     497%               Here, \lstinline{arrayX} represents the type that results from desugaring the \lstinline{array} type into a type whose generic parameters are all types.
     498%               This presentation elides the noisy fact that \lstinline{array} is actually a macro for something bigger;
     499%               the reduction to \lstinline{char [-]} still proceeds as sketched.}
     500\item
     501        Is internal type @char[999]@ type-compatible with internal type @char[n]@?
    500502\end{itemize}
    501 To achieve the necessary \CFA rejections meant rejecting the corresponding C case, which is not backward compatible.
    502 There are two complementary mitigations for this incompatibility.
    503 
    504 First, a simple recourse is available to a programmer who intends to proceed
    505 with the statically unsound assignment.
    506 This situation might arise if @n@ were known to be 999,
    507 rather than 42, as in the introductory examples.
    508 The programmer can add a cast in the \CFA code.
    509 \begin{cfa}
    510 xp = @(float (*)[999])@ &x;
    511 \end{cfa}
    512 This addition causes \CFA to accept, because now, the programmer has accepted blame.
    513 This addition is benign in plain C, because the cast is valid, just unnecessary there.
    514 Moreover, the addition can even be seen as appropriate ``eye candy,''
    515 marking where the unchecked length knowledge is used.
    516 Therefore, a program being onboarded to \CFA can receive a simple upgrade,
    517 to satisfy the \CFA rules (and arguably become clearer),
    518 without giving up its validity to a plain C compiler.
    519 
    520 Second, the incompatibility only affects types like pointer-to-array,
    521 which are are infrequently used in C.
    522 The more common C idiom for aliasing an array is to use a pointer-to-first-element type,
    523 which does not participate in the \CFA array's length checking.\footnote{
     503The answer is false because, in general, the value of @n@ is unknown at compile time, and hence, an error is raised.
     504For safety, it makes sense to reject the corresponding C case, which is a non-backwards compatible change.
     505There are two mitigations for this incompatibility.
     506
     507First, a simple recourse is available in a situation where @n@ is \emph{known} to be 999 by using a cast.
     508\begin{cfa}
     509float (* xp)[999] = @(float (*)[999])@&x;
     510\end{cfa}
     511The cast means the programmer has accepted blame.
     512Moreover, the cast is ``eye candy'' marking where the unchecked length knowledge is used.
     513Therefore, a program being onboarded to \CFA requires some upgrading to satisfy the \CFA rules (and arguably become clearer), without giving up its validity to a plain C compiler.
     514Second, the incompatibility only affects types like pointer-to-array, which are infrequently used in C.
     515The more common C idiom for aliasing an array is to use a pointer-to-first-element type, which does not participate in the \CFA array's length checking.\footnote{
    524516        Notably, the desugaring of the \lstinline{array} type avoids letting any \lstinline{-[-]} type decay,
    525517        in order to preserve the length information that powers runtime bound-checking.}
    526 Therefore, the frequency of needing to upgrade legacy C code (as discussed in the first mitigation)
    527 is anticipated to be low.
    528 
    529 Because the incompatibility represents a low cost to a \CFA onboarding effort
    530 (with a plausible side benefit of linting the original code for a missing annotation),
    531 no special measures were added to retain the compatibility.
    532 It would be possible to flag occurrences of @-[-]@ types that come from @array@ desugaring,
    533 treating those with stricter \CFA rules, while treating others with classic C rules.
    534 If future lessons from C project onboarding warrant it,
    535 this special compatibility measure can be added.
    536 
    537 Having allowed that both the initial C example's check
    538 \begin{itemize}
    539         \item
    540                 Is @float[999]@ type-compatible with @float[n]@?
    541 \end{itemize}
    542 and the second \CFA example's induced check
    543 \begin{itemize}
    544         \item
    545                 Is @char[999]@ type-compatible with @char[n]@?
    546 \end{itemize}
    547 shall have the same answer, (``no''),
    548 discussion turns to how I got the \CFA compiler to produce this answer.
    549 In its preexisting form, it produced a (buggy) approximation of the C rules.
    550 To implement the new \CFA rules, I took the syntactic recursion a step further, obtaining,
    551 in both cases:
    552 \begin{itemize}
    553         \item
    554                 Is @999@ compatible with @n@?
    555 \end{itemize}
    556 This compatibility question applies to a pair of expressions, where the earlier implementation were to types.
    557 Such an expression-compatibility question is a new addition to the \CFA compiler.
    558 Note, these questions only arise in the context of dimension expressions on (C) array types.
    559 
    560 TODO: ensure these compiler implementation matters are treated under \CFA compiler background:
    561 type unification,
    562 cost calculation,
    563 GenPoly.
    564 
    565 The relevant technical component of the \CFA compiler is the type unification procedure within the type resolver.
    566 I added rules for continuing this unification into expressions that occur within types.
    567 It is still fundamentally doing \emph{type} unification
    568 because it is participating in binding type variables,
    569 and not participating in binding any variables that stand in for expression fragments
    570 (for there is no such sort of variable in \CFA's analysis.)
    571 An unfortunate fact about the \CFA compiler's preexisting implementation is that
    572 type unification suffers from two forms of duplication.
    573 
    574 The first duplication has (many of) the unification rules stated twice.
    575 As a result, my additions for dimension expressions are stated twice.
    576 The extra statement of the rules occurs in the @GenPoly@ module,
    577 where concrete types like @array(int, 5)@\footnote{
    578         Again, the presentation is simplified
    579         by leaving the \lstinline{array} macro unexpanded.}
    580 are lowered into corresponding C types @struct __conc_array_1234@ (the suffix being a generated index).
    581 In this case, the struct's definition contains fields that hardcode the argument values of @float@ and @5@.
    582 The next time an @array(-,-)@ concrete instance is encountered, it checks if the previous @struct __conc_array_1234@ is suitable for it.
    583 Yes, for another occurrence of @array(int, 5)@;
    584 no, for either @array(rational(int), 5)@ or @array(int, 42)@.
    585 By the last example, this phase must ``reject''
    586 the hypothesis that it should reuse the dimension-5 instance's C-lowering for a dimension-42 instance.
    587 
    588 The second duplication has unification (proper) being invoked at two stages of expression resolution.
    589 As a result, my added rule set needs to handle more cases than the preceding discussion motivates.
    590 In the program
    591 \begin{cfa}
    592 void @f@( double );
    593 forall( T & ) void @f@( T & );
    594 void g( int n ) {
    595         array( float, n + 1 ) x;
    596         f(x);   // overloaded
    597 }
    598 \end{cfa}
    599 when resolving the function call, @g@, the first unification stage
    600 compares the type @T@ of the parameter with @array( float, n + 1 )@, of the argument.
    601 TODO: finish.
    602 
    603 The actual rules for comparing two dimension expressions are conservative.
    604 To answer, ``yes, consider this pair of expressions to be matching,''
    605 is to imply, ``all else being equal, allow an array with length calculated by $e_1$
    606 to be passed to a function expecting a length-$e_2$ array.''\footnote{
    607         TODO: Deal with directionality, that I'm doing exact-match, no ``at least as long as,'' no subtyping.
    608         Should it be an earlier scoping principle?  Feels like it should matter in more places than here.}
    609 So, a ``yes'' answer must represent a guarantee that both expressions evaluate the
    610 same result, while a ``no'' can tolerate ``they might, but we're not sure'',
    611 provided that practical recourses are available
    612 to let programmers express better knowledge.
    613 The new rule-set in the current release is, in fact, extremely conservative.
    614 I chose to keep things simple,
    615 and allow future needs to drive adding additional complexity, within the new framework.
    616 
    617 For starters, the original motivating example's rejection
    618 is not based on knowledge that
    619 the @xp@ length of (the literal) 999 is value-unequal to
    620 the (obvious) runtime value of the variable @n@, which is the @x@ length.
    621 Rather, the analysis assumes a variable's value can be anything,
    622 and so there can be no guarantee that its value is 999.
    623 So, a variable and a literal can never match.
    624 
    625 Two occurrences of the same literal value are obviously a fine match.
    626 For two occurrences of the same variable, more information is needed.
    627 For example, this one is fine
    628 \begin{cfa}
    629 void f( const int n ) {
    630         float x[n];
    631         float (*xp)[n] = x;   // accept
    632 }
    633 \end{cfa}
    634 while this one is not:
    635 \begin{cfa}
     518Therefore, the need to upgrade legacy C code is low.
     519Finally, if this incompatibility is a problem onboarding C programs to \CFA, it is should be possible to change the C type check to a warning rather than an error, acting as a \emph{lint} of the original code for a missing type annotation.
     520
     521To handle two occurrences of the same variable, more information is needed, \eg, this is fine,
     522\begin{cfa}
     523int n = 42;
     524float x[@n@];
     525float (*xp)[@n@] = x;   // accept
     526\end{cfa}
     527where @n@ remains fixed across a contiguous declaration context.
     528However, intervening dynamic statement cause failures.
     529\begin{cfa}
     530int n = 42;
     531float x[@n@];
     532@n@ = 999; // dynamic change
     533float (*xp)[@n@] = x;   // reject
     534\end{cfa}
     535However, side-effects can occur in a contiguous declaration context.
     536\begin{cquote}
     537\setlength{\tabcolsep}{20pt}
     538\begin{tabular}{@{}ll@{}}
     539\begin{cfa}
     540// compile unit 1
     541extern int @n@;
     542extern float g();
    636543void f() {
    637         int n = 42;
    638         float x[n];
    639         n = 999;
    640         float (*xp)[n] = x;   // reject
    641 }
    642 \end{cfa}
    643 Furthermore, the fact that the first example sees @n@ as @const@
    644 is not actually sufficient.
    645 In this example, @f@'s length expression's declaration is as @const@ as it can be,
    646 yet its value still changes between the two invocations:
    647 \begin{cquote}
    648 \setlength{\tabcolsep}{15pt}
    649 \begin{tabular}{@{}ll@{}}
    650 \begin{cfa}
    651 // compile unit 1
    652 void g();
    653 void f( const int & const nr ) {
    654         float x[nr];
    655         g();    // change n
    656         @float (*xp)[nr] = x;@   // reject
     544        float x[@n@] = { g() };
     545        float (*xp)[@n@] = x;   // reject
    657546}
    658547\end{cfa}
    … …  
    660549\begin{cfa}
    661550// compile unit 2
    662 static int n = 42;
     551int @n@ = 42;
    663552void g() {
    664         n = 99;
    665 }
    666 
    667 f( n );
     553        @n@ = 99;
     554}
     555
     556
    668557\end{cfa}
    669558\end{tabular}
    … …  
    671560The issue here is that knowledge needed to make a correct decision is hidden by separate compilation.
    672561Even within a translation unit, static analysis might not be able to provide all the information.
    673 
    674 My rule set also respects a traditional C feature: In spite of the several limitations of the C rules
    675 accepting cases that produce different values, there are a few mismatches that C stops.
    676 C is quite precise when working with two static values.
    677 \begin{cfa}
    678 enum { fortytwo = 42 };
    679 float x[fortytwo];
    680 float (*xp1)[42] = &x;    // accept
    681 float (*xp2)[999] = &x;   // reject
    682 \end{cfa}
    683 My \CFA rules agree with C's on these cases.
     562However, if the example uses @const@, the check is possible.
     563\begin{cquote}
     564\setlength{\tabcolsep}{20pt}
     565\begin{tabular}{@{}ll@{}}
     566\begin{cfa}
     567// compile unit 1
     568extern @const@ int n;
     569extern float g();
     570void f() {
     571        float x[n] = { g() };
     572        float (*xp)[n] = x;   // reject
     573}
     574\end{cfa}
     575&
     576\begin{cfa}
     577// compile unit 2
     578@const@ int n = 42;
     579void g() {
     580        @n = 99@; // allowed
     581}
     582
     583
     584\end{cfa}
     585\end{tabular}
     586\end{cquote}
    684587
    685588In summary, the new rules classify expressions into three groups:
    686589\begin{description}
    687590\item[Statically Evaluable]
    688         Expressions for which a specific value can be calculated (conservatively)
    689         at compile-time.
    690         A preexisting \CFA compiler module defines which literals, enumerators, and expressions qualify,
    691         and evaluates them.
     591        Expressions for which a specific value can be calculated (conservatively) at compile-time.
     592        A preexisting \CFA compiler module defines which literals, enumerators, and expressions qualify and evaluates them.
    692593\item[Dynamic but Stable]
    693594        The value of a variable declared as @const@, including a @const@ parameter.
    694595\item[Potentially Unstable]
    695596        The catch-all category.  Notable examples include:
    696         any function-call result, @float x[foo()];@,
    697         the particular function-call result that is a pointer dereference, @void f(const int * n)@ @{ float x[*n]; }@, and
    698         any use of a reference-typed variable.
     597        any function-call result, @float x[foo()]@, the particular function-call result that is a pointer dereference, @void f(const int * n)@ @{ float x[*n]; }@, and any use of a reference-typed variable.
    699598\end{description}
    700599Within these groups, my \CFA rules are:
    701 \begin{itemize}
     600\begin{itemize}[leftmargin=*]
    702601\item
    703602        Accept a Statically Evaluable pair, if both expressions have the same value.
    … …  
    710609\end{itemize}
    711610The traditional C rules are:
    712 \begin{itemize}
     611\begin{itemize}[leftmargin=*]
    713612\item
    714613        Reject a Statically Evaluable pair, if the expressions have two different values.
    … …  
    716615        Otherwise, accept.
    717616\end{itemize}
     617\VRef[Figure]{f:DimexprRuleCompare} gives a case-by-case comparison of the consequences of these rule sets.
     618It demonstrates that the \CFA false alarms occur in the same cases as C treats unsafe.
     619It also shows that C-incompatibilities only occur in cases that C treats unsafe.
    718620
    719621\begin{figure}
    … …  
    746648                where \lstinline{expr1} and \lstinline{expr2} are meta-variables varying according to the row's Case.
    747649                Each row's claim applies to other harnesses too, including,
    748                 \begin{itemize}
     650                \begin{itemize}[leftmargin=*]
    749651                \item
    750652                        calling a function with a parameter like \lstinline{x} and an argument of the \lstinline{xp} type,
    … …  
    762664                The table treats symbolic identity (Same/Different on rows)
    763665                apart from value equality (Equal/Unequal on columns).
    764                 \begin{itemize}
     666                \begin{itemize}[leftmargin=*]
    765667                \item
    766668                        The expressions \lstinline{1}, \lstinline{0+1} and \lstinline{n}
    … …  
    781683\end{figure}
    782684
    783 
    784 \VRef[Figure]{f:DimexprRuleCompare} gives a case-by-case comparison of the consequences of these rule sets.
    785 It demonstrates that the \CFA false alarms occur in the same cases as C treats unsafe.
    786 It also shows that C-incompatibilities only occur in cases that C treats unsafe.
    787 
    788 
    789 The conservatism of the new rule set can leave a programmer needing a recourse,
    790 when needing to use a dimension expression whose stability argument
    791 is more subtle than current-state analysis.
     685\begin{comment}
     686Given that the above check
     687\begin{itemize}
     688        \item
     689        Is internal type @char[999]@ type-compatible with internal type @char[n]@?
     690\end{itemize}
     691answers false, discussion turns to how I got the \CFA compiler to produce this answer.
     692In its preexisting form, the type system had a buggy approximation of the C rules.
     693To implement the new \CFA rules, I added one further step.
     694\begin{itemize}
     695        \item
     696                Is @999@ compatible with @n@?
     697\end{itemize}
     698This question applies to a pair of expressions, where the earlier question applies to types.
     699An expression-compatibility question is a new addition to the \CFA compiler, and occurs in the context of dimension expressions, and possibly enumerations assigns, which must be unique.
     700
     701% TODO: ensure these compiler implementation matters are treated under \CFA compiler background: type unification, cost calculation, GenPoly.
     702
     703The relevant technical component of the \CFA compiler is the standard type-unification within the type resolver.
     704\begin{cfa}
     705example
     706\end{cfa}
     707I added rules for continuing this unification into expressions that occur within types.
     708It is still fundamentally doing \emph{type} unification because it is participating in binding type variables, and not participating in binding any variables that stand in for expression fragments (for there is no such sort of variable in \CFA's analysis.)
     709An unfortunate fact about the \CFA compiler's preexisting implementation is that type unification suffers from two forms of duplication.
     710
     711In detail, the first duplication has (many of) the unification rules stated twice.
     712As a result, my additions for dimension expressions are stated twice.
     713The extra statement of the rules occurs in the @GenPoly@ module, where concrete types like @array( int, 5 )@\footnote{
     714        Again, the presentation is simplified
     715        by leaving the \lstinline{array} macro unexpanded.}
     716are lowered into corresponding C types @struct __conc_array_1234@ (the suffix being a generated index).
     717In this case, the struct's definition contains fields that hardcode the argument values of @float@ and @5@.
     718The next time an @array( -, - )@ concrete instance is encountered, it checks if the previous @struct __conc_array_1234@ is suitable for it.
     719Yes, for another occurrence of @array( int, 5 )@;
     720no, for examples like @array( int, 42 )@ or @array( rational(int), 5 )@.
     721In the first example, it must reject the reuse hypothesis for a dimension-@5@ and a dimension-@42@ instance.
     722
     723The second duplication has unification (proper) being invoked at two stages of expression resolution.
     724As a result, my added rule set needs to handle more cases than the preceding discussion motivates.
     725In the program
     726\begin{cfa}
     727void @f@( double ); // overload
     728forall( T & ) void @f@( T & ); // overload
     729void g( int n ) {
     730        array( float, n + 1 ) x;
     731        f(x);   // overloaded
     732}
     733\end{cfa}
     734when resolving a function call to @g@, the first unification stage compares the type @T@ of the parameter with @array( float, n + 1 )@, of the argument.
     735\PAB{TODO: finish.}
     736
     737The actual rules for comparing two dimension expressions are conservative.
     738To answer, ``yes, consider this pair of expressions to be matching,''
     739is to imply, ``all else being equal, allow an array with length calculated by $e_1$
     740to be passed to a function expecting a length-$e_2$ array.''\footnote{
     741        TODO: Deal with directionality, that I'm doing exact-match, no ``at least as long as,'' no subtyping.
     742        Should it be an earlier scoping principle?  Feels like it should matter in more places than here.}
     743So, a ``yes'' answer must represent a guarantee that both expressions evaluate the
     744same result, while a ``no'' can tolerate ``they might, but we're not sure'',
     745provided that practical recourses are available
     746to let programmers express better knowledge.
     747The new rule-set in the current release is, in fact, extremely conservative.
     748I chose to keep things simple,
     749and allow future needs to drive adding additional complexity, within the new framework.
     750
     751For starters, the original motivating example's rejection is not based on knowledge that the @xp@ length of (the literal) 999 is value-unequal to the (obvious) runtime value of the variable @n@, which is the @x@ length.
     752Rather, the analysis assumes a variable's value can be anything, and so there can be no guarantee that its value is 999.
     753So, a variable and a literal can never match.
     754
     755TODO: Discuss the interaction of this dimension hoisting with the challenge of extra unification for cost calculation
     756\end{comment}
     757
     758The conservatism of the new rule set can leave a programmer needing a recourse, when needing to use a dimension expression whose stability argument is more subtle than current-state analysis.
    792759This recourse is to declare an explicit constant for the dimension value.
    793 Consider these two dimension expressions,
    794 whose reuses are rejected by the blunt current-state rules:
    795 \begin{cfa}
    796 void f( int & nr, const int nv ) {
    797         float x[nr];
    798         float (*xp)[nr] = &x;   // reject: nr varying (no references)
    799         float y[nv + 1];
    800         float (*yp)[nv + 1] = &y;   // reject: ?+? unpredictable (no functions)
     760Consider these two dimension expressions, whose uses are rejected by the blunt current-state rules:
     761\begin{cfa}
     762void f( int @&@ nr, @const@ int nv ) {
     763        float x[@nr@];
     764        float (*xp)[@nr@] = &x;   // reject: nr varying (no references)
     765        float y[@nv + 1@];
     766        float (*yp)[@nv + 1@] = &y;   // reject: ?+? unpredictable (no functions)
    801767}
    802768\end{cfa}
    803769Yet, both dimension expressions are reused safely.
    804 The @nr@ reference is never written, not volatile
    805 and control does not leave the function between the uses.
    806 The name @?+?@ resolves to a function that is quite predictable.
    807 Here, the programmer can add the constant declarations (cast does not work):
     770The @nr@ reference is never written, not volatile meaning no implicit code (load) between declarations, and control does not leave the function between the uses.
     771As well, the build-in @?+?@ function is predictable.
     772To make these cases work, the programmer must add the follow constant declarations (cast does not work):
    808773\begin{cfa}
    809774void f( int & nr, const int nv ) {
    … …  
    819784achieved by adding a superfluous ``snapshot it as of now'' directive.
    820785
    821 The snapshotting trick is also used by the translation, though to achieve a different outcome.
     786The snapshot trick is also used by the \CFA translation, though to achieve a different outcome.
    822787Rather obviously, every array must be subscriptable, even a bizarre one:
    823788\begin{cfa}
    824 array( float, rand(10) ) x;
    825 x[0];  // 10% chance of bound-check failure
    826 \end{cfa}
    827 Less obvious is that the mechanism of subscripting is a function call,
    828 which must communicate length accurately.
    829 The bound-check above (callee logic) must use the actual allocated length of @x@,
    830 without mistakenly reevaluating the dimension expression, @rand(10)@.
     789array( float, @rand(10)@ ) x;
     790x[@0@];  // 10% chance of bound-check failure
     791\end{cfa}
     792Less obvious is that the mechanism of subscripting is a function call, which must communicate length accurately.
     793The bound-check above (callee logic) must use the actual allocated length of @x@, without mistakenly reevaluating the dimension expression, @rand(10)@.
    831794Adjusting the example to make the function's use of length more explicit:
    832795\begin{cfa}
    833 forall ( T * )
    834 void f( T * x ) { sout | sizeof(*x); }
     796forall( T * )
     797void f( T * x ) { sout | sizeof( *x ); }
    835798float x[ rand(10) ];
    836799f( x );
    … …  
    840803void f( size_t __sizeof_T, void * x ) { sout | __sizeof_T; }
    841804\end{cfa}
    842 the translation must call the dimension argument twice:
     805the translation calls the dimension argument twice:
    843806\begin{cfa}
    844807float x[ rand(10) ];
    845808f( rand(10), &x );
    846809\end{cfa}
    847 Rather, the translation is:
     810The correct form is:
    848811\begin{cfa}
    849812size_t __dim_x = rand(10);
    … …  
    851814f( __dim_x, &x );
    852815\end{cfa}
    853 The occurrence of this dimension hoisting during translation was in the preexisting \CFA compiler.
    854 But its cases were buggy, particularly with determining, ``Can hoisting the expression be skipped here?'', for skipping this hoisting is clearly desirable in some cases.
    855 For example, when the programmer has already done so manually. \PAB{I don't know what this means.}
     816Dimension hoisting already existed in the \CFA compiler.
     817But its was buggy, particularly with determining, ``Can hoisting the expression be skipped here?'', for skipping this hoisting is clearly desirable in some cases.
     818For example, when a programmer has already hoisted to perform an optimiation to prelude duplicate code (expression) and/or expression evaluation.
    856819In the new implementation, these cases are correct, harmonized with the accept/reject criteria.
    857 
    858 TODO: Discuss the interaction of this dimension hoisting with the challenge of extra unification for cost calculation
    859820
    860821
    … …  
    863824
    864825A multidimensional array implementation has three relevant levels of abstraction, from highest to lowest, where the array occupies \emph{contiguous memory}.
    865 \begin{enumerate}
     826\begin{enumerate}[leftmargin=*]
    866827\item
    867828Flexible-stride memory:
    … …  
    11001061Preexisting \CFA mechanisms achieve this requirement, but with poor performance.
    11011062Furthermore, advanced array users need an exception to the basic mechanism, which does not occur with other aggregates.
    1102 Hence, arrays introduce subleties in supporting an element's lifecycle.
     1063Hence, arrays introduce subtleties in supporting an element's lifecycle.
    11031064
    11041065The preexisting \CFA support for contained-element lifecycle is based on recursive occurrences of the object-type (@otype@) pseudo-trait.
    … …  
    13191280The @worker@ type is designed this way to work with the threading system.
    13201281A thread type forks a thread at the end of each constructor and joins with it at the start of each destructor.
    1321 But a @worker@ cannot begin its forked-thead work without knowing its @id@.
     1282But a @worker@ cannot begin its forked-thread work without knowing its @id@.
    13221283Therefore, there is a conflict between the implicit actions of the builtin @thread@ type and a user's desire to defer these actions.
    13231284
    … …  
    14601421
    14611422The \CFA array and the field of ``array language'' comparators all leverage dependent types to improve on the expressiveness over C and Java, accommodating examples such as:
    1462 \begin{itemize}
     1423\begin{itemize}[leftmargin=*]
    14631424\item a \emph{zip}-style operation that consumes two arrays of equal length
    14641425\item a \emph{map}-style operation whose produced length matches the consumed length
    … …  
    15441505The details in this presentation aren't meant to be taken too precisely as suggestions for how it should look in \CFA.
    15451506But the example shows these abilities:
    1546 \begin{itemize}
     1507\begin{itemize}[leftmargin=*]
    15471508\item a built-in way (the @is_enum@ trait) for a generic routine to require enumeration-like information about its instantiating type
    15481509\item an implicit implementation of the trait whenever a user-written enum occurs (@weekday@'s declaration implies @is_enum@)

  • doc/theses/mike_brooks_MMath/background.tex

    r7d02d35 rbd72f517  
    995995                Illustrated by pseudocode implementation of an STL-compatible API fragment using LQ as the underlying implementation.
    996996                The gap that makes it pseudocode is that
    997                 the LQ C macros do not expand to valid C++ when instantiated with template parameters---there is no \lstinline{struct El}.
     997                the LQ C macros do not expand to valid \CC when instantiated with template parameters---there is no \lstinline{struct El}.
    998998                When using a custom-patched version of LQ to work around this issue,
    999999                the programs of \VRef[Figure]{f:WrappedRef} and wrapped value work with this shim in place of real STL.

  • doc/theses/mike_brooks_MMath/benchmarks/string/result-append-pbv.csv

    r7d02d35 rbd72f517  
    1 perfexp-cfa-pta-ll-share-reuse,corpus-100-1-1.txt,100,100,1.000000,219460000,10.000260
    2 perfexp-cfa-pta-ll-share-reuse,corpus-100-10-1.txt,100,100,9.500000,180250000,10.000486
    3 perfexp-cfa-pta-ll-share-reuse,corpus-100-100-1.txt,100,100,106.370000,152790000,10.000441
    4 perfexp-cfa-pta-ll-share-reuse,corpus-100-2-1.txt,100,100,2.030000,206090000,10.000311
    5 perfexp-cfa-pta-ll-share-reuse,corpus-100-20-1.txt,100,100,22.960000,184330000,10.000328
    6 perfexp-cfa-pta-ll-share-reuse,corpus-100-200-1.txt,100,100,177.280000,125090000,10.000138
    7 perfexp-cfa-pta-ll-share-reuse,corpus-100-5-1.txt,100,100,5.270000,199130000,10.000180
    8 perfexp-cfa-pta-ll-share-reuse,corpus-100-50-1.txt,100,100,43.320000,167720000,10.000327
    9 perfexp-cfa-pta-ll-share-reuse,corpus-100-500-1.txt,100,100,557.260000,93560000,10.001058
    10 perfexp-cfa-pta-ll-share-fresh,corpus-100-1-1.txt,100,100,1.000000,225090000,10.000393
    11 perfexp-cfa-pta-ll-share-fresh,corpus-100-10-1.txt,100,100,9.500000,196300000,10.000221
    12 perfexp-cfa-pta-ll-share-fresh,corpus-100-100-1.txt,100,100,106.370000,150670000,10.000337
    13 perfexp-cfa-pta-ll-share-fresh,corpus-100-2-1.txt,100,100,2.030000,206600000,10.000182
    14 perfexp-cfa-pta-ll-share-fresh,corpus-100-20-1.txt,100,100,22.960000,188400000,10.000199
    15 perfexp-cfa-pta-ll-share-fresh,corpus-100-200-1.txt,100,100,177.280000,125880000,10.000489
    16 perfexp-cfa-pta-ll-share-fresh,corpus-100-5-1.txt,100,100,5.270000,185930000,10.000231
    17 perfexp-cfa-pta-ll-share-fresh,corpus-100-50-1.txt,100,100,43.320000,170660000,10.000491
    18 perfexp-cfa-pta-ll-share-fresh,corpus-100-500-1.txt,100,100,557.260000,91520000,10.000640
    19 perfexp-cfa-pta-ll-noshare-reuse,corpus-100-1-1.txt,100,100,1.000000,146200000,10.000520
    20 perfexp-cfa-pta-ll-noshare-reuse,corpus-100-10-1.txt,100,100,9.500000,114140000,10.000734
    21 perfexp-cfa-pta-ll-noshare-reuse,corpus-100-100-1.txt,100,100,106.370000,17630000,10.000889
    22 perfexp-cfa-pta-ll-noshare-reuse,corpus-100-2-1.txt,100,100,2.030000,139700000,10.000460
    23 perfexp-cfa-pta-ll-noshare-reuse,corpus-100-20-1.txt,100,100,22.960000,71910000,10.000768
    24 perfexp-cfa-pta-ll-noshare-reuse,corpus-100-200-1.txt,100,100,177.280000,8540000,10.009186
    25 perfexp-cfa-pta-ll-noshare-reuse,corpus-100-5-1.txt,100,100,5.270000,129810000,10.000379
    26 perfexp-cfa-pta-ll-noshare-reuse,corpus-100-50-1.txt,100,100,43.320000,45280000,10.000006
    27 perfexp-cfa-pta-ll-noshare-reuse,corpus-100-500-1.txt,100,100,557.260000,3300000,10.021088
    28 perfexp-cfa-pta-ll-noshare-fresh,corpus-100-1-1.txt,100,100,1.000000,146050000,10.000551
    29 perfexp-cfa-pta-ll-noshare-fresh,corpus-100-10-1.txt,100,100,9.500000,102800000,10.000490
    30 perfexp-cfa-pta-ll-noshare-fresh,corpus-100-100-1.txt,100,100,106.370000,17060000,10.001677
    31 perfexp-cfa-pta-ll-noshare-fresh,corpus-100-2-1.txt,100,100,2.030000,137470000,10.000361
    32 perfexp-cfa-pta-ll-noshare-fresh,corpus-100-20-1.txt,100,100,22.960000,69520000,10.001142
    33 perfexp-cfa-pta-ll-noshare-fresh,corpus-100-200-1.txt,100,100,177.280000,8830000,10.010528
    34 perfexp-cfa-pta-ll-noshare-fresh,corpus-100-5-1.txt,100,100,5.270000,117120000,10.000681
    35 perfexp-cfa-pta-ll-noshare-fresh,corpus-100-50-1.txt,100,100,43.320000,42960000,10.001950
    36 perfexp-cfa-pta-ll-noshare-fresh,corpus-100-500-1.txt,100,100,557.260000,3220000,10.010203
    37 perfexp-cfa-peq-ll-share-reuse,corpus-100-1-1.txt,100,100,1.000000,583560000,10.000070
    38 perfexp-cfa-peq-ll-share-reuse,corpus-100-10-1.txt,100,100,9.500000,451400000,10.000013
    39 perfexp-cfa-peq-ll-share-reuse,corpus-100-100-1.txt,100,100,106.370000,253260000,10.000275
    40 perfexp-cfa-peq-ll-share-reuse,corpus-100-2-1.txt,100,100,2.030000,483580000,10.000140
    41 perfexp-cfa-peq-ll-share-reuse,corpus-100-20-1.txt,100,100,22.960000,396550000,10.000060
    42 perfexp-cfa-peq-ll-share-reuse,corpus-100-200-1.txt,100,100,177.280000,199760000,10.000416
    43 perfexp-cfa-peq-ll-share-reuse,corpus-100-5-1.txt,100,100,5.270000,454790000,10.000069
    44 perfexp-cfa-peq-ll-share-reuse,corpus-100-50-1.txt,100,100,43.320000,339690000,10.000243
    45 perfexp-cfa-peq-ll-share-reuse,corpus-100-500-1.txt,100,100,557.260000,123840000,10.000724
    46 perfexp-cfa-peq-ll-share-fresh,corpus-100-1-1.txt,100,100,1.000000,577650000,10.000157
    47 perfexp-cfa-peq-ll-share-fresh,corpus-100-10-1.txt,100,100,9.500000,445260000,10.000186
    48 perfexp-cfa-peq-ll-share-fresh,corpus-100-100-1.txt,100,100,106.370000,259650000,10.000273
    49 perfexp-cfa-peq-ll-share-fresh,corpus-100-2-1.txt,100,100,2.030000,485650000,10.000026
    50 perfexp-cfa-peq-ll-share-fresh,corpus-100-20-1.txt,100,100,22.960000,386150000,10.000120
    51 perfexp-cfa-peq-ll-share-fresh,corpus-100-200-1.txt,100,100,177.280000,197690000,10.000077
    52 perfexp-cfa-peq-ll-share-fresh,corpus-100-5-1.txt,100,100,5.270000,443650000,10.000006
    53 perfexp-cfa-peq-ll-share-fresh,corpus-100-50-1.txt,100,100,43.320000,339190000,10.000037
    54 perfexp-cfa-peq-ll-share-fresh,corpus-100-500-1.txt,100,100,557.260000,122740000,10.000753
    55 perfexp-cfa-peq-ll-noshare-reuse,corpus-100-1-1.txt,100,100,1.000000,595700000,10.000119
    56 perfexp-cfa-peq-ll-noshare-reuse,corpus-100-10-1.txt,100,100,9.500000,452000000,10.000055
    57 perfexp-cfa-peq-ll-noshare-reuse,corpus-100-100-1.txt,100,100,106.370000,280570000,10.000281
    58 perfexp-cfa-peq-ll-noshare-reuse,corpus-100-2-1.txt,100,100,2.030000,501040000,10.000073
    59 perfexp-cfa-peq-ll-noshare-reuse,corpus-100-20-1.txt,100,100,22.960000,422280000,10.000131
    60 perfexp-cfa-peq-ll-noshare-reuse,corpus-100-200-1.txt,100,100,177.280000,235640000,10.000126
    61 perfexp-cfa-peq-ll-noshare-reuse,corpus-100-5-1.txt,100,100,5.270000,461250000,10.000197
    62 perfexp-cfa-peq-ll-noshare-reuse,corpus-100-50-1.txt,100,100,43.320000,369020000,10.000057
    63 perfexp-cfa-peq-ll-noshare-reuse,corpus-100-500-1.txt,100,100,557.260000,135050000,10.000682
    64 perfexp-cfa-peq-ll-noshare-fresh,corpus-100-1-1.txt,100,100,1.000000,529900000,10.000150
    65 perfexp-cfa-peq-ll-noshare-fresh,corpus-100-10-1.txt,100,100,9.500000,408530000,10.000108
    66 perfexp-cfa-peq-ll-noshare-fresh,corpus-100-100-1.txt,100,100,106.370000,217530000,10.000334
    67 perfexp-cfa-peq-ll-noshare-fresh,corpus-100-2-1.txt,100,100,2.030000,463860000,10.000166
    68 perfexp-cfa-peq-ll-noshare-fresh,corpus-100-20-1.txt,100,100,22.960000,360110000,10.000008
    69 perfexp-cfa-peq-ll-noshare-fresh,corpus-100-200-1.txt,100,100,177.280000,176490000,10.000131
    70 perfexp-cfa-peq-ll-noshare-fresh,corpus-100-5-1.txt,100,100,5.270000,424710000,10.000106
    71 perfexp-cfa-peq-ll-noshare-fresh,corpus-100-50-1.txt,100,100,43.320000,290930000,10.000172
    72 perfexp-cfa-peq-ll-noshare-fresh,corpus-100-500-1.txt,100,100,557.260000,90430000,10.000065
    73 perfexp-cfa-pbv-ll-share-na,corpus-100-1-1.txt,xxx,100,1.000000,578040000,10.000159
    74 perfexp-cfa-pbv-ll-share-na,corpus-100-10-1.txt,xxx,100,9.500000,573200000,10.000098
    75 perfexp-cfa-pbv-ll-share-na,corpus-100-100-1.txt,xxx,100,106.370000,575160000,10.000149
    76 perfexp-cfa-pbv-ll-share-na,corpus-100-2-1.txt,xxx,100,2.030000,573780000,10.000134
    77 perfexp-cfa-pbv-ll-share-na,corpus-100-20-1.txt,xxx,100,22.960000,574500000,10.000156
    78 perfexp-cfa-pbv-ll-share-na,corpus-100-200-1.txt,xxx,100,177.280000,577170000,10.000125
    79 perfexp-cfa-pbv-ll-share-na,corpus-100-5-1.txt,xxx,100,5.270000,577820000,10.000046
    80 perfexp-cfa-pbv-ll-share-na,corpus-100-50-1.txt,xxx,100,43.320000,578770000,10.000033
    81 perfexp-cfa-pbv-ll-share-na,corpus-100-500-1.txt,xxx,100,557.260000,579540000,10.000128
    82 perfexp-cfa-pbv-ll-noshare-na,corpus-100-1-1.txt,xxx,100,1.000000,191420000,10.000232
    83 perfexp-cfa-pbv-ll-noshare-na,corpus-100-10-1.txt,xxx,100,9.500000,186330000,10.000046
    84 perfexp-cfa-pbv-ll-noshare-na,corpus-100-100-1.txt,xxx,100,106.370000,164610000,10.000463
    85 perfexp-cfa-pbv-ll-noshare-na,corpus-100-2-1.txt,xxx,100,2.030000,182390000,10.000409
    86 perfexp-cfa-pbv-ll-noshare-na,corpus-100-20-1.txt,xxx,100,22.960000,182280000,10.000252
    87 perfexp-cfa-pbv-ll-noshare-na,corpus-100-200-1.txt,xxx,100,177.280000,149840000,10.000281
    88 perfexp-cfa-pbv-ll-noshare-na,corpus-100-5-1.txt,xxx,100,5.270000,152370000,10.000284
    89 perfexp-cfa-pbv-ll-noshare-na,corpus-100-50-1.txt,xxx,100,43.320000,177430000,10.000397
    90 perfexp-cfa-pbv-ll-noshare-na,corpus-100-500-1.txt,xxx,100,557.260000,113440000,10.000150
    91 perfexp-stl-pta-na-na-reuse,corpus-100-1-1.txt,100,100,1.000000,152870000,10.000280
    92 perfexp-stl-pta-na-na-reuse,corpus-100-10-1.txt,100,100,9.500000,98530000,10.000299
    93 perfexp-stl-pta-na-na-reuse,corpus-100-100-1.txt,100,100,106.370000,16690000,10.005783
    94 perfexp-stl-pta-na-na-reuse,corpus-100-2-1.txt,100,100,2.030000,136230000,10.000196
    95 perfexp-stl-pta-na-na-reuse,corpus-100-20-1.txt,100,100,22.960000,62110000,10.001423
    96 perfexp-stl-pta-na-na-reuse,corpus-100-200-1.txt,100,100,177.280000,8960000,10.005548
    97 perfexp-stl-pta-na-na-reuse,corpus-100-5-1.txt,100,100,5.270000,104790000,10.000889
    98 perfexp-stl-pta-na-na-reuse,corpus-100-50-1.txt,100,100,43.320000,39170000,10.000011
    99 perfexp-stl-pta-na-na-reuse,corpus-100-500-1.txt,100,100,557.260000,3100000,10.015093
    100 perfexp-stl-pta-na-na-fresh,corpus-100-1-1.txt,100,100,1.000000,154450000,10.000054
    101 perfexp-stl-pta-na-na-fresh,corpus-100-10-1.txt,100,100,9.500000,96570000,10.000834
    102 perfexp-stl-pta-na-na-fresh,corpus-100-100-1.txt,100,100,106.370000,16400000,10.000697
    103 perfexp-stl-pta-na-na-fresh,corpus-100-2-1.txt,100,100,2.030000,133450000,10.000440
    104 perfexp-stl-pta-na-na-fresh,corpus-100-20-1.txt,100,100,22.960000,62540000,10.001476
    105 perfexp-stl-pta-na-na-fresh,corpus-100-200-1.txt,100,100,177.280000,8960000,10.006817
    106 perfexp-stl-pta-na-na-fresh,corpus-100-5-1.txt,100,100,5.270000,106470000,10.000109
    107 perfexp-stl-pta-na-na-fresh,corpus-100-50-1.txt,100,100,43.320000,37460000,10.000100
    108 perfexp-stl-pta-na-na-fresh,corpus-100-500-1.txt,100,100,557.260000,3090000,10.000541
    109 perfexp-stl-peq-na-na-reuse,corpus-100-1-1.txt,100,100,1.000000,863350000,10.000092
    110 perfexp-stl-peq-na-na-reuse,corpus-100-10-1.txt,100,100,9.500000,471070000,10.000189
    111 perfexp-stl-peq-na-na-reuse,corpus-100-100-1.txt,100,100,106.370000,287660000,10.000105
    112 perfexp-stl-peq-na-na-reuse,corpus-100-2-1.txt,100,100,2.030000,669380000,10.000082
    113 perfexp-stl-peq-na-na-reuse,corpus-100-20-1.txt,100,100,22.960000,432290000,10.000131
    114 perfexp-stl-peq-na-na-reuse,corpus-100-200-1.txt,100,100,177.280000,241690000,10.000290
    115 perfexp-stl-peq-na-na-reuse,corpus-100-5-1.txt,100,100,5.270000,510990000,10.000082
    116 perfexp-stl-peq-na-na-reuse,corpus-100-50-1.txt,100,100,43.320000,396380000,10.000235
    117 perfexp-stl-peq-na-na-reuse,corpus-100-500-1.txt,100,100,557.260000,135830000,10.000603
    118 perfexp-stl-peq-na-na-fresh,corpus-100-1-1.txt,100,100,1.000000,785420000,10.000062
    119 perfexp-stl-peq-na-na-fresh,corpus-100-10-1.txt,100,100,9.500000,418030000,10.000094
    120 perfexp-stl-peq-na-na-fresh,corpus-100-100-1.txt,100,100,106.370000,225290000,10.000237
    121 perfexp-stl-peq-na-na-fresh,corpus-100-2-1.txt,100,100,2.030000,550120000,10.000151
    122 perfexp-stl-peq-na-na-fresh,corpus-100-20-1.txt,100,100,22.960000,386080000,10.000206
    123 perfexp-stl-peq-na-na-fresh,corpus-100-200-1.txt,100,100,177.280000,176890000,10.000155
    124 perfexp-stl-peq-na-na-fresh,corpus-100-5-1.txt,100,100,5.270000,441830000,10.000135
    125 perfexp-stl-peq-na-na-fresh,corpus-100-50-1.txt,100,100,43.320000,310200000,10.000299
    126 perfexp-stl-peq-na-na-fresh,corpus-100-500-1.txt,100,100,557.260000,90360000,10.000474
    127 perfexp-stl-pbv-na-na-na,corpus-100-1-1.txt,xxx,100,1.000000,1267670000,10.000039
    128 perfexp-stl-pbv-na-na-na,corpus-100-10-1.txt,xxx,100,9.500000,482210000,10.000013
    129 perfexp-stl-pbv-na-na-na,corpus-100-100-1.txt,xxx,100,106.370000,268680000,10.000097
    130 perfexp-stl-pbv-na-na-na,corpus-100-2-1.txt,xxx,100,2.030000,806650000,10.000104
    131 perfexp-stl-pbv-na-na-na,corpus-100-20-1.txt,xxx,100,22.960000,369490000,10.000159
    132 perfexp-stl-pbv-na-na-na,corpus-100-200-1.txt,xxx,100,177.280000,227020000,10.000244
    133 perfexp-stl-pbv-na-na-na,corpus-100-5-1.txt,xxx,100,5.270000,534150000,10.000061
    134 perfexp-stl-pbv-na-na-na,corpus-100-50-1.txt,xxx,100,43.320000,298950000,10.000190
    135 perfexp-stl-pbv-na-na-na,corpus-100-500-1.txt,xxx,100,557.260000,158310000,10.000104
     1perfexp-cfa-pta-ll-share-reuse,corpus-100-1-1.txt,100,100,1.000000,220120000,10.000178
     2perfexp-cfa-pta-ll-share-reuse,corpus-100-10-1.txt,100,100,9.500000,177430000,10.000414
     3perfexp-cfa-pta-ll-share-reuse,corpus-100-100-1.txt,100,100,106.370000,142410000,10.000162
     4perfexp-cfa-pta-ll-share-reuse,corpus-100-2-1.txt,100,100,2.030000,195500000,10.000161
     5perfexp-cfa-pta-ll-share-reuse,corpus-100-20-1.txt,100,100,22.960000,164560000,10.000548
     6perfexp-cfa-pta-ll-share-reuse,corpus-100-200-1.txt,100,100,177.280000,122260000,10.000279
     7perfexp-cfa-pta-ll-share-reuse,corpus-100-5-1.txt,100,100,5.270000,193960000,10.000071
     8perfexp-cfa-pta-ll-share-reuse,corpus-100-50-1.txt,100,100,43.320000,163430000,10.000175
     9perfexp-cfa-pta-ll-share-reuse,corpus-100-500-1.txt,100,100,557.260000,87960000,10.001073
     10perfexp-cfa-pta-ll-share-reuse,corpus-1-1-1.txt,100,1,1.000000,224420000,10.000135
     11perfexp-cfa-pta-ll-share-reuse,corpus-1-10-1.txt,100,1,10.000000,223740000,10.000014
     12perfexp-cfa-pta-ll-share-reuse,corpus-1-100-1.txt,100,1,100.000000,153300000,10.000091
     13perfexp-cfa-pta-ll-share-reuse,corpus-1-2-1.txt,100,1,2.000000,223430000,10.000120
     14perfexp-cfa-pta-ll-share-reuse,corpus-1-20-1.txt,100,1,20.000000,210640000,10.000385
     15perfexp-cfa-pta-ll-share-reuse,corpus-1-200-1.txt,100,1,200.000000,129790000,10.000596
     16perfexp-cfa-pta-ll-share-reuse,corpus-1-5-1.txt,100,1,5.000000,222850000,10.000361
     17perfexp-cfa-pta-ll-share-reuse,corpus-1-50-1.txt,100,1,50.000000,201700000,10.000220
     18perfexp-cfa-pta-ll-share-reuse,corpus-1-500-1.txt,100,1,500.000000,110000000,10.000407
     19perfexp-cfa-pta-ll-share-fresh,corpus-100-1-1.txt,100,100,1.000000,225030000,10.000360
     20perfexp-cfa-pta-ll-share-fresh,corpus-100-10-1.txt,100,100,9.500000,192640000,10.000254
     21perfexp-cfa-pta-ll-share-fresh,corpus-100-100-1.txt,100,100,106.370000,143960000,10.000633
     22perfexp-cfa-pta-ll-share-fresh,corpus-100-2-1.txt,100,100,2.030000,204500000,10.000450
     23perfexp-cfa-pta-ll-share-fresh,corpus-100-20-1.txt,100,100,22.960000,185400000,10.000274
     24perfexp-cfa-pta-ll-share-fresh,corpus-100-200-1.txt,100,100,177.280000,126420000,10.000791
     25perfexp-cfa-pta-ll-share-fresh,corpus-100-5-1.txt,100,100,5.270000,194450000,10.000396
     26perfexp-cfa-pta-ll-share-fresh,corpus-100-50-1.txt,100,100,43.320000,173140000,10.000364
     27perfexp-cfa-pta-ll-share-fresh,corpus-100-500-1.txt,100,100,557.260000,92390000,10.000098
     28perfexp-cfa-pta-ll-share-fresh,corpus-1-1-1.txt,100,1,1.000000,222210000,10.000426
     29perfexp-cfa-pta-ll-share-fresh,corpus-1-10-1.txt,100,1,10.000000,209110000,10.000235
     30perfexp-cfa-pta-ll-share-fresh,corpus-1-100-1.txt,100,1,100.000000,154750000,10.000076
     31perfexp-cfa-pta-ll-share-fresh,corpus-1-2-1.txt,100,1,2.000000,222030000,10.000114
     32perfexp-cfa-pta-ll-share-fresh,corpus-1-20-1.txt,100,1,20.000000,208680000,10.000050
     33perfexp-cfa-pta-ll-share-fresh,corpus-1-200-1.txt,100,1,200.000000,133490000,10.000231
     34perfexp-cfa-pta-ll-share-fresh,corpus-1-5-1.txt,100,1,5.000000,217740000,10.000425
     35perfexp-cfa-pta-ll-share-fresh,corpus-1-50-1.txt,100,1,50.000000,200340000,10.000126
     36perfexp-cfa-pta-ll-share-fresh,corpus-1-500-1.txt,100,1,500.000000,109570000,10.000365
     37perfexp-cfa-pta-ll-noshare-reuse,corpus-100-1-1.txt,100,100,1.000000,146130000,10.000557
     38perfexp-cfa-pta-ll-noshare-reuse,corpus-100-10-1.txt,100,100,9.500000,110430000,10.000456
     39perfexp-cfa-pta-ll-noshare-reuse,corpus-100-100-1.txt,100,100,106.370000,17440000,10.003114
     40perfexp-cfa-pta-ll-noshare-reuse,corpus-100-2-1.txt,100,100,2.030000,139540000,10.000128
     41perfexp-cfa-pta-ll-noshare-reuse,corpus-100-20-1.txt,100,100,22.960000,70380000,10.000395
     42perfexp-cfa-pta-ll-noshare-reuse,corpus-100-200-1.txt,100,100,177.280000,8670000,10.001712
     43perfexp-cfa-pta-ll-noshare-reuse,corpus-100-5-1.txt,100,100,5.270000,127040000,10.000370
     44perfexp-cfa-pta-ll-noshare-reuse,corpus-100-50-1.txt,100,100,43.320000,44250000,10.002214
     45perfexp-cfa-pta-ll-noshare-reuse,corpus-100-500-1.txt,100,100,557.260000,3290000,10.007370
     46perfexp-cfa-pta-ll-noshare-reuse,corpus-1-1-1.txt,100,1,1.000000,139870000,10.000356
     47perfexp-cfa-pta-ll-noshare-reuse,corpus-1-10-1.txt,100,1,10.000000,115500000,10.000281
     48perfexp-cfa-pta-ll-noshare-reuse,corpus-1-100-1.txt,100,1,100.000000,18830000,10.003277
     49perfexp-cfa-pta-ll-noshare-reuse,corpus-1-2-1.txt,100,1,2.000000,144880000,10.000426
     50perfexp-cfa-pta-ll-noshare-reuse,corpus-1-20-1.txt,100,1,20.000000,82050000,10.001071
     51perfexp-cfa-pta-ll-noshare-reuse,corpus-1-200-1.txt,100,1,200.000000,8870000,10.002904
     52perfexp-cfa-pta-ll-noshare-reuse,corpus-1-5-1.txt,100,1,5.000000,138400000,10.000130
     53perfexp-cfa-pta-ll-noshare-reuse,corpus-1-50-1.txt,100,1,50.000000,38130000,10.002351
     54perfexp-cfa-pta-ll-noshare-reuse,corpus-1-500-1.txt,100,1,500.000000,3890000,10.003849
     55perfexp-cfa-pta-ll-noshare-fresh,corpus-100-1-1.txt,100,100,1.000000,143100000,10.000056
     56perfexp-cfa-pta-ll-noshare-fresh,corpus-100-10-1.txt,100,100,9.500000,97990000,10.000081
     57perfexp-cfa-pta-ll-noshare-fresh,corpus-100-100-1.txt,100,100,106.370000,16950000,10.004190
     58perfexp-cfa-pta-ll-noshare-fresh,corpus-100-2-1.txt,100,100,2.030000,135210000,10.000137
     59perfexp-cfa-pta-ll-noshare-fresh,corpus-100-20-1.txt,100,100,22.960000,69270000,10.000092
     60perfexp-cfa-pta-ll-noshare-fresh,corpus-100-200-1.txt,100,100,177.280000,8840000,10.000491
     61perfexp-cfa-pta-ll-noshare-fresh,corpus-100-5-1.txt,100,100,5.270000,112610000,10.000397
     62perfexp-cfa-pta-ll-noshare-fresh,corpus-100-50-1.txt,100,100,43.320000,42480000,10.001402
     63perfexp-cfa-pta-ll-noshare-fresh,corpus-100-500-1.txt,100,100,557.260000,3250000,10.027871
     64perfexp-cfa-pta-ll-noshare-fresh,corpus-1-1-1.txt,100,1,1.000000,139830000,10.000681
     65perfexp-cfa-pta-ll-noshare-fresh,corpus-1-10-1.txt,100,1,10.000000,102320000,10.000624
     66perfexp-cfa-pta-ll-noshare-fresh,corpus-1-100-1.txt,100,1,100.000000,17610000,10.000917
     67perfexp-cfa-pta-ll-noshare-fresh,corpus-1-2-1.txt,100,1,2.000000,134520000,10.000287
     68perfexp-cfa-pta-ll-noshare-fresh,corpus-1-20-1.txt,100,1,20.000000,78150000,10.000982
     69perfexp-cfa-pta-ll-noshare-fresh,corpus-1-200-1.txt,100,1,200.000000,8930000,10.010066
     70perfexp-cfa-pta-ll-noshare-fresh,corpus-1-5-1.txt,100,1,5.000000,119920000,10.000537
     71perfexp-cfa-pta-ll-noshare-fresh,corpus-1-50-1.txt,100,1,50.000000,38540000,10.001545
     72perfexp-cfa-pta-ll-noshare-fresh,corpus-1-500-1.txt,100,1,500.000000,3900000,10.024468
     73perfexp-cfa-peq-ll-share-reuse,corpus-100-1-1.txt,100,100,1.000000,580710000,10.000065
     74perfexp-cfa-peq-ll-share-reuse,corpus-100-10-1.txt,100,100,9.500000,430790000,10.000116
     75perfexp-cfa-peq-ll-share-reuse,corpus-100-100-1.txt,100,100,106.370000,247640000,10.000266
     76perfexp-cfa-peq-ll-share-reuse,corpus-100-2-1.txt,100,100,2.030000,464050000,10.000189
     77perfexp-cfa-peq-ll-share-reuse,corpus-100-20-1.txt,100,100,22.960000,377820000,10.000065
     78perfexp-cfa-peq-ll-share-reuse,corpus-100-200-1.txt,100,100,177.280000,195030000,10.000477
     79perfexp-cfa-peq-ll-share-reuse,corpus-100-5-1.txt,100,100,5.270000,430190000,10.000121
     80perfexp-cfa-peq-ll-share-reuse,corpus-100-50-1.txt,100,100,43.320000,331580000,10.000295
     81perfexp-cfa-peq-ll-share-reuse,corpus-100-500-1.txt,100,100,557.260000,123230000,10.000186
     82perfexp-cfa-peq-ll-share-reuse,corpus-1-1-1.txt,100,1,1.000000,572750000,10.000172
     83perfexp-cfa-peq-ll-share-reuse,corpus-1-10-1.txt,100,1,10.000000,558790000,10.000101
     84perfexp-cfa-peq-ll-share-reuse,corpus-1-100-1.txt,100,1,100.000000,291780000,10.000230
     85perfexp-cfa-peq-ll-share-reuse,corpus-1-2-1.txt,100,1,2.000000,571220000,10.000023
     86perfexp-cfa-peq-ll-share-reuse,corpus-1-20-1.txt,100,1,20.000000,461020000,10.000045
     87perfexp-cfa-peq-ll-share-reuse,corpus-1-200-1.txt,100,1,200.000000,220880000,10.000260
     88perfexp-cfa-peq-ll-share-reuse,corpus-1-5-1.txt,100,1,5.000000,555180000,10.000153
     89perfexp-cfa-peq-ll-share-reuse,corpus-1-50-1.txt,100,1,50.000000,433290000,10.000123
     90perfexp-cfa-peq-ll-share-reuse,corpus-1-500-1.txt,100,1,500.000000,165210000,10.000260
     91perfexp-cfa-peq-ll-share-fresh,corpus-100-1-1.txt,100,100,1.000000,591360000,10.000013
     92perfexp-cfa-peq-ll-share-fresh,corpus-100-10-1.txt,100,100,9.500000,432580000,10.000103
     93perfexp-cfa-peq-ll-share-fresh,corpus-100-100-1.txt,100,100,106.370000,253100000,10.000162
     94perfexp-cfa-peq-ll-share-fresh,corpus-100-2-1.txt,100,100,2.030000,470710000,10.000018
     95perfexp-cfa-peq-ll-share-fresh,corpus-100-20-1.txt,100,100,22.960000,381580000,10.000172
     96perfexp-cfa-peq-ll-share-fresh,corpus-100-200-1.txt,100,100,177.280000,197910000,10.000400
     97perfexp-cfa-peq-ll-share-fresh,corpus-100-5-1.txt,100,100,5.270000,437470000,10.000123
     98perfexp-cfa-peq-ll-share-fresh,corpus-100-50-1.txt,100,100,43.320000,337150000,10.000065
     99perfexp-cfa-peq-ll-share-fresh,corpus-100-500-1.txt,100,100,557.260000,127310000,10.000685
     100perfexp-cfa-peq-ll-share-fresh,corpus-1-1-1.txt,100,1,1.000000,581300000,10.000103
     101perfexp-cfa-peq-ll-share-fresh,corpus-1-10-1.txt,100,1,10.000000,566650000,10.000166
     102perfexp-cfa-peq-ll-share-fresh,corpus-1-100-1.txt,100,1,100.000000,295340000,10.000202
     103perfexp-cfa-peq-ll-share-fresh,corpus-1-2-1.txt,100,1,2.000000,579220000,10.000012
     104perfexp-cfa-peq-ll-share-fresh,corpus-1-20-1.txt,100,1,20.000000,470040000,10.000180
     105perfexp-cfa-peq-ll-share-fresh,corpus-1-200-1.txt,100,1,200.000000,223060000,10.000188
     106perfexp-cfa-peq-ll-share-fresh,corpus-1-5-1.txt,100,1,5.000000,563440000,10.000100
     107perfexp-cfa-peq-ll-share-fresh,corpus-1-50-1.txt,100,1,50.000000,438260000,10.000200
     108perfexp-cfa-peq-ll-share-fresh,corpus-1-500-1.txt,100,1,500.000000,166830000,10.000225
     109perfexp-cfa-peq-ll-noshare-reuse,corpus-100-1-1.txt,100,100,1.000000,603080000,10.000107
     110perfexp-cfa-peq-ll-noshare-reuse,corpus-100-10-1.txt,100,100,9.500000,439540000,10.000078
     111perfexp-cfa-peq-ll-noshare-reuse,corpus-100-100-1.txt,100,100,106.370000,279990000,10.000309
     112perfexp-cfa-peq-ll-noshare-reuse,corpus-100-2-1.txt,100,100,2.030000,509720000,10.000099
     113perfexp-cfa-peq-ll-noshare-reuse,corpus-100-20-1.txt,100,100,22.960000,405590000,10.000206
     114perfexp-cfa-peq-ll-noshare-reuse,corpus-100-200-1.txt,100,100,177.280000,230400000,10.000124
     115perfexp-cfa-peq-ll-noshare-reuse,corpus-100-5-1.txt,100,100,5.270000,454270000,10.000057
     116perfexp-cfa-peq-ll-noshare-reuse,corpus-100-50-1.txt,100,100,43.320000,375090000,10.000225
     117perfexp-cfa-peq-ll-noshare-reuse,corpus-100-500-1.txt,100,100,557.260000,134440000,10.000290
     118perfexp-cfa-peq-ll-noshare-reuse,corpus-1-1-1.txt,100,1,1.000000,588100000,10.000124
     119perfexp-cfa-peq-ll-noshare-reuse,corpus-1-10-1.txt,100,1,10.000000,577110000,10.000002
     120perfexp-cfa-peq-ll-noshare-reuse,corpus-1-100-1.txt,100,1,100.000000,319990000,10.000151
     121perfexp-cfa-peq-ll-noshare-reuse,corpus-1-2-1.txt,100,1,2.000000,586540000,10.000010
     122perfexp-cfa-peq-ll-noshare-reuse,corpus-1-20-1.txt,100,1,20.000000,480940000,10.000047
     123perfexp-cfa-peq-ll-noshare-reuse,corpus-1-200-1.txt,100,1,200.000000,300590000,10.000162
     124perfexp-cfa-peq-ll-noshare-reuse,corpus-1-5-1.txt,100,1,5.000000,577530000,10.000120
     125perfexp-cfa-peq-ll-noshare-reuse,corpus-1-50-1.txt,100,1,50.000000,454950000,10.000114
     126perfexp-cfa-peq-ll-noshare-reuse,corpus-1-500-1.txt,100,1,500.000000,186210000,10.000221
     127perfexp-cfa-peq-ll-noshare-fresh,corpus-100-1-1.txt,100,100,1.000000,546170000,10.000079
     128perfexp-cfa-peq-ll-noshare-fresh,corpus-100-10-1.txt,100,100,9.500000,403120000,10.000222
     129perfexp-cfa-peq-ll-noshare-fresh,corpus-100-100-1.txt,100,100,106.370000,214740000,10.000444
     130perfexp-cfa-peq-ll-noshare-fresh,corpus-100-2-1.txt,100,100,2.030000,449080000,10.000157
     131perfexp-cfa-peq-ll-noshare-fresh,corpus-100-20-1.txt,100,100,22.960000,351690000,10.000146
     132perfexp-cfa-peq-ll-noshare-fresh,corpus-100-200-1.txt,100,100,177.280000,174630000,10.000540
     133perfexp-cfa-peq-ll-noshare-fresh,corpus-100-5-1.txt,100,100,5.270000,419160000,10.000085
     134perfexp-cfa-peq-ll-noshare-fresh,corpus-100-50-1.txt,100,100,43.320000,296590000,10.000200
     135perfexp-cfa-peq-ll-noshare-fresh,corpus-100-500-1.txt,100,100,557.260000,78000000,10.000539
     136perfexp-cfa-peq-ll-noshare-fresh,corpus-1-1-1.txt,100,1,1.000000,541890000,10.000021
     137perfexp-cfa-peq-ll-noshare-fresh,corpus-1-10-1.txt,100,1,10.000000,511140000,10.000142
     138perfexp-cfa-peq-ll-noshare-fresh,corpus-1-100-1.txt,100,1,100.000000,243680000,10.000252
     139perfexp-cfa-peq-ll-noshare-fresh,corpus-1-2-1.txt,100,1,2.000000,532730000,10.000135
     140perfexp-cfa-peq-ll-noshare-fresh,corpus-1-20-1.txt,100,1,20.000000,413610000,10.000113
     141perfexp-cfa-peq-ll-noshare-fresh,corpus-1-200-1.txt,100,1,200.000000,192770000,10.000185
     142perfexp-cfa-peq-ll-noshare-fresh,corpus-1-5-1.txt,100,1,5.000000,495980000,10.000162
     143perfexp-cfa-peq-ll-noshare-fresh,corpus-1-50-1.txt,100,1,50.000000,367590000,10.000269
     144perfexp-cfa-peq-ll-noshare-fresh,corpus-1-500-1.txt,100,1,500.000000,111560000,10.000455
     145perfexp-cfa-pbv-ll-share-na,corpus-100-1-1.txt,xxx,100,1.000000,638780000,10.000008
     146perfexp-cfa-pbv-ll-share-na,corpus-100-10-1.txt,xxx,100,9.500000,637840000,10.000004
     147perfexp-cfa-pbv-ll-share-na,corpus-100-100-1.txt,xxx,100,106.370000,635130000,10.000003
     148perfexp-cfa-pbv-ll-share-na,corpus-100-2-1.txt,xxx,100,2.030000,639810000,10.000140
     149perfexp-cfa-pbv-ll-share-na,corpus-100-20-1.txt,xxx,100,22.960000,552670000,10.000089
     150perfexp-cfa-pbv-ll-share-na,corpus-100-200-1.txt,xxx,100,177.280000,639550000,10.000019
     151perfexp-cfa-pbv-ll-share-na,corpus-100-5-1.txt,xxx,100,5.270000,636230000,10.000044
     152perfexp-cfa-pbv-ll-share-na,corpus-100-50-1.txt,xxx,100,43.320000,631470000,10.000125
     153perfexp-cfa-pbv-ll-share-na,corpus-100-500-1.txt,xxx,100,557.260000,628330000,10.000127
     154perfexp-cfa-pbv-ll-share-na,corpus-1-1-1.txt,xxx,1,1.000000,589760000,10.000044
     155perfexp-cfa-pbv-ll-share-na,corpus-1-10-1.txt,xxx,1,10.000000,589790000,10.000151
     156perfexp-cfa-pbv-ll-share-na,corpus-1-100-1.txt,xxx,1,100.000000,587540000,10.000128
     157perfexp-cfa-pbv-ll-share-na,corpus-1-2-1.txt,xxx,1,2.000000,580790000,10.000102
     158perfexp-cfa-pbv-ll-share-na,corpus-1-20-1.txt,xxx,1,20.000000,586470000,10.000154
     159perfexp-cfa-pbv-ll-share-na,corpus-1-200-1.txt,xxx,1,200.000000,587510000,10.000005
     160perfexp-cfa-pbv-ll-share-na,corpus-1-5-1.txt,xxx,1,5.000000,582120000,10.000163
     161perfexp-cfa-pbv-ll-share-na,corpus-1-50-1.txt,xxx,1,50.000000,587990000,10.000127
     162perfexp-cfa-pbv-ll-share-na,corpus-1-500-1.txt,xxx,1,500.000000,587590000,10.000046
     163perfexp-cfa-pbv-ll-noshare-na,corpus-100-1-1.txt,xxx,100,1.000000,218340000,10.000321
     164perfexp-cfa-pbv-ll-noshare-na,corpus-100-10-1.txt,xxx,100,9.500000,189550000,10.000174
     165perfexp-cfa-pbv-ll-noshare-na,corpus-100-100-1.txt,xxx,100,106.370000,169280000,10.000141
     166perfexp-cfa-pbv-ll-noshare-na,corpus-100-2-1.txt,xxx,100,2.030000,197840000,10.000383
     167perfexp-cfa-pbv-ll-noshare-na,corpus-100-20-1.txt,xxx,100,22.960000,182700000,10.000041
     168perfexp-cfa-pbv-ll-noshare-na,corpus-100-200-1.txt,xxx,100,177.280000,157120000,10.000522
     169perfexp-cfa-pbv-ll-noshare-na,corpus-100-5-1.txt,xxx,100,5.270000,155160000,10.000322
     170perfexp-cfa-pbv-ll-noshare-na,corpus-100-50-1.txt,xxx,100,43.320000,179110000,10.000218
     171perfexp-cfa-pbv-ll-noshare-na,corpus-100-500-1.txt,xxx,100,557.260000,113620000,10.000140
     172perfexp-cfa-pbv-ll-noshare-na,corpus-1-1-1.txt,xxx,1,1.000000,216270000,10.000367
     173perfexp-cfa-pbv-ll-noshare-na,corpus-1-10-1.txt,xxx,1,10.000000,214390000,10.000157
     174perfexp-cfa-pbv-ll-noshare-na,corpus-1-100-1.txt,xxx,1,100.000000,165440000,10.000095
     175perfexp-cfa-pbv-ll-noshare-na,corpus-1-2-1.txt,xxx,1,2.000000,217150000,10.000044
     176perfexp-cfa-pbv-ll-noshare-na,corpus-1-20-1.txt,xxx,1,20.000000,216760000,10.000321
     177perfexp-cfa-pbv-ll-noshare-na,corpus-1-200-1.txt,xxx,1,200.000000,176930000,10.000100
     178perfexp-cfa-pbv-ll-noshare-na,corpus-1-5-1.txt,xxx,1,5.000000,200840000,10.000229
     179perfexp-cfa-pbv-ll-noshare-na,corpus-1-50-1.txt,xxx,1,50.000000,212960000,10.000273
     180perfexp-cfa-pbv-ll-noshare-na,corpus-1-500-1.txt,xxx,1,500.000000,163340000,10.000196
     181perfexp-stl-pta-na-na-reuse,corpus-100-1-1.txt,100,100,1.000000,151210000,10.000032
     182perfexp-stl-pta-na-na-reuse,corpus-100-10-1.txt,100,100,9.500000,92400000,10.000662
     183perfexp-stl-pta-na-na-reuse,corpus-100-100-1.txt,100,100,106.370000,16700000,10.003595
     184perfexp-stl-pta-na-na-reuse,corpus-100-2-1.txt,100,100,2.030000,132700000,10.000666
     185perfexp-stl-pta-na-na-reuse,corpus-100-20-1.txt,100,100,22.960000,61670000,10.001135
     186perfexp-stl-pta-na-na-reuse,corpus-100-200-1.txt,100,100,177.280000,8950000,10.005903
     187perfexp-stl-pta-na-na-reuse,corpus-100-5-1.txt,100,100,5.270000,105760000,10.000126
     188perfexp-stl-pta-na-na-reuse,corpus-100-50-1.txt,100,100,43.320000,38020000,10.001290
     189perfexp-stl-pta-na-na-reuse,corpus-100-500-1.txt,100,100,557.260000,3080000,10.009583
     190perfexp-stl-pta-na-na-reuse,corpus-1-1-1.txt,100,1,1.000000,150070000,10.000505
     191perfexp-stl-pta-na-na-reuse,corpus-1-10-1.txt,100,1,10.000000,96240000,10.000747
     192perfexp-stl-pta-na-na-reuse,corpus-1-100-1.txt,100,1,100.000000,17380000,10.005677
     193perfexp-stl-pta-na-na-reuse,corpus-1-2-1.txt,100,1,2.000000,136340000,10.000556
     194perfexp-stl-pta-na-na-reuse,corpus-1-20-1.txt,100,1,20.000000,69290000,10.000979
     195perfexp-stl-pta-na-na-reuse,corpus-1-200-1.txt,100,1,200.000000,9140000,10.005445
     196perfexp-stl-pta-na-na-reuse,corpus-1-5-1.txt,100,1,5.000000,114030000,10.000605
     197perfexp-stl-pta-na-na-reuse,corpus-1-50-1.txt,100,1,50.000000,33470000,10.000871
     198perfexp-stl-pta-na-na-reuse,corpus-1-500-1.txt,100,1,500.000000,3760000,10.021431
     199perfexp-stl-pta-na-na-fresh,corpus-100-1-1.txt,100,100,1.000000,151890000,10.000693
     200perfexp-stl-pta-na-na-fresh,corpus-100-10-1.txt,100,100,9.500000,97910000,10.000289
     201perfexp-stl-pta-na-na-fresh,corpus-100-100-1.txt,100,100,106.370000,16740000,10.000756
     202perfexp-stl-pta-na-na-fresh,corpus-100-2-1.txt,100,100,2.030000,134890000,10.000666
     203perfexp-stl-pta-na-na-fresh,corpus-100-20-1.txt,100,100,22.960000,61040000,10.000514
     204perfexp-stl-pta-na-na-fresh,corpus-100-200-1.txt,100,100,177.280000,8950000,10.004888
     205perfexp-stl-pta-na-na-fresh,corpus-100-5-1.txt,100,100,5.270000,101780000,10.000043
     206perfexp-stl-pta-na-na-fresh,corpus-100-50-1.txt,100,100,43.320000,38440000,10.000510
     207perfexp-stl-pta-na-na-fresh,corpus-100-500-1.txt,100,100,557.260000,3060000,10.007733
     208perfexp-stl-pta-na-na-fresh,corpus-1-1-1.txt,100,1,1.000000,149360000,10.000168
     209perfexp-stl-pta-na-na-fresh,corpus-1-10-1.txt,100,1,10.000000,98400000,10.000118
     210perfexp-stl-pta-na-na-fresh,corpus-1-100-1.txt,100,1,100.000000,17440000,10.004379
     211perfexp-stl-pta-na-na-fresh,corpus-1-2-1.txt,100,1,2.000000,130340000,10.000520
     212perfexp-stl-pta-na-na-fresh,corpus-1-20-1.txt,100,1,20.000000,69280000,10.001377
     213perfexp-stl-pta-na-na-fresh,corpus-1-200-1.txt,100,1,200.000000,9070000,10.004963
     214perfexp-stl-pta-na-na-fresh,corpus-1-5-1.txt,100,1,5.000000,114390000,10.000315
     215perfexp-stl-pta-na-na-fresh,corpus-1-50-1.txt,100,1,50.000000,34350000,10.001033
     216perfexp-stl-pta-na-na-fresh,corpus-1-500-1.txt,100,1,500.000000,3720000,10.009015
     217perfexp-stl-peq-na-na-reuse,corpus-100-1-1.txt,100,100,1.000000,867730000,10.000040
     218perfexp-stl-peq-na-na-reuse,corpus-100-10-1.txt,100,100,9.500000,470370000,10.000155
     219perfexp-stl-peq-na-na-reuse,corpus-100-100-1.txt,100,100,106.370000,287440000,10.000190
     220perfexp-stl-peq-na-na-reuse,corpus-100-2-1.txt,100,100,2.030000,667180000,10.000145
     221perfexp-stl-peq-na-na-reuse,corpus-100-20-1.txt,100,100,22.960000,430260000,10.000102
     222perfexp-stl-peq-na-na-reuse,corpus-100-200-1.txt,100,100,177.280000,232720000,10.000418
     223perfexp-stl-peq-na-na-reuse,corpus-100-5-1.txt,100,100,5.270000,515130000,10.000118
     224perfexp-stl-peq-na-na-reuse,corpus-100-50-1.txt,100,100,43.320000,401280000,10.000122
     225perfexp-stl-peq-na-na-reuse,corpus-100-500-1.txt,100,100,557.260000,135350000,10.000692
     226perfexp-stl-peq-na-na-reuse,corpus-1-1-1.txt,100,1,1.000000,847560000,10.000010
     227perfexp-stl-peq-na-na-reuse,corpus-1-10-1.txt,100,1,10.000000,641250000,10.000095
     228perfexp-stl-peq-na-na-reuse,corpus-1-100-1.txt,100,1,100.000000,300130000,10.000199
     229perfexp-stl-peq-na-na-reuse,corpus-1-2-1.txt,100,1,2.000000,680950000,10.000050
     230perfexp-stl-peq-na-na-reuse,corpus-1-20-1.txt,100,1,20.000000,515190000,10.000051
     231perfexp-stl-peq-na-na-reuse,corpus-1-200-1.txt,100,1,200.000000,271800000,10.000194
     232perfexp-stl-peq-na-na-reuse,corpus-1-5-1.txt,100,1,5.000000,611640000,10.000133
     233perfexp-stl-peq-na-na-reuse,corpus-1-50-1.txt,100,1,50.000000,483780000,10.000084
     234perfexp-stl-peq-na-na-reuse,corpus-1-500-1.txt,100,1,500.000000,191470000,10.000243
     235perfexp-stl-peq-na-na-fresh,corpus-100-1-1.txt,100,100,1.000000,779650000,10.000085
     236perfexp-stl-peq-na-na-fresh,corpus-100-10-1.txt,100,100,9.500000,419300000,10.000184
     237perfexp-stl-peq-na-na-fresh,corpus-100-100-1.txt,100,100,106.370000,224270000,10.000410
     238perfexp-stl-peq-na-na-fresh,corpus-100-2-1.txt,100,100,2.030000,545330000,10.000073
     239perfexp-stl-peq-na-na-fresh,corpus-100-20-1.txt,100,100,22.960000,385000000,10.000210
     240perfexp-stl-peq-na-na-fresh,corpus-100-200-1.txt,100,100,177.280000,174520000,10.000360
     241perfexp-stl-peq-na-na-fresh,corpus-100-5-1.txt,100,100,5.270000,443460000,10.000165
     242perfexp-stl-peq-na-na-fresh,corpus-100-50-1.txt,100,100,43.320000,310460000,10.000174
     243perfexp-stl-peq-na-na-fresh,corpus-100-500-1.txt,100,100,557.260000,92820000,10.000352
     244perfexp-stl-peq-na-na-fresh,corpus-1-1-1.txt,100,1,1.000000,774230000,10.000110
     245perfexp-stl-peq-na-na-fresh,corpus-1-10-1.txt,100,1,10.000000,554850000,10.000064
     246perfexp-stl-peq-na-na-fresh,corpus-1-100-1.txt,100,1,100.000000,227540000,10.000041
     247perfexp-stl-peq-na-na-fresh,corpus-1-2-1.txt,100,1,2.000000,616830000,10.000134
     248perfexp-stl-peq-na-na-fresh,corpus-1-20-1.txt,100,1,20.000000,436800000,10.000038
     249perfexp-stl-peq-na-na-fresh,corpus-1-200-1.txt,100,1,200.000000,185050000,10.000439
     250perfexp-stl-peq-na-na-fresh,corpus-1-5-1.txt,100,1,5.000000,569030000,10.000125
     251perfexp-stl-peq-na-na-fresh,corpus-1-50-1.txt,100,1,50.000000,387710000,10.000249
     252perfexp-stl-peq-na-na-fresh,corpus-1-500-1.txt,100,1,500.000000,113890000,10.000075
     253perfexp-stl-pbv-na-na-na,corpus-100-1-1.txt,xxx,100,1.000000,1267570000,10.000072
     254perfexp-stl-pbv-na-na-na,corpus-100-10-1.txt,xxx,100,9.500000,476260000,10.000192
     255perfexp-stl-pbv-na-na-na,corpus-100-100-1.txt,xxx,100,106.370000,271870000,10.000171
     256perfexp-stl-pbv-na-na-na,corpus-100-2-1.txt,xxx,100,2.030000,807830000,10.000110
     257perfexp-stl-pbv-na-na-na,corpus-100-20-1.txt,xxx,100,22.960000,373160000,10.000221
     258perfexp-stl-pbv-na-na-na,corpus-100-200-1.txt,xxx,100,177.280000,233700000,10.000081
     259perfexp-stl-pbv-na-na-na,corpus-100-5-1.txt,xxx,100,5.270000,536240000,10.000165
     260perfexp-stl-pbv-na-na-na,corpus-100-50-1.txt,xxx,100,43.320000,297400000,10.000317
     261perfexp-stl-pbv-na-na-na,corpus-100-500-1.txt,xxx,100,557.260000,159500000,10.000290
     262perfexp-stl-pbv-na-na-na,corpus-1-1-1.txt,xxx,1,1.000000,1089370000,10.000024
     263perfexp-stl-pbv-na-na-na,corpus-1-10-1.txt,xxx,1,10.000000,722490000,10.000040
     264perfexp-stl-pbv-na-na-na,corpus-1-100-1.txt,xxx,1,100.000000,311250000,10.000116
     265perfexp-stl-pbv-na-na-na,corpus-1-2-1.txt,xxx,1,2.000000,747630000,10.000103
     266perfexp-stl-pbv-na-na-na,corpus-1-20-1.txt,xxx,1,20.000000,348820000,10.000149
     267perfexp-stl-pbv-na-na-na,corpus-1-200-1.txt,xxx,1,200.000000,302220000,10.000223
     268perfexp-stl-pbv-na-na-na,corpus-1-5-1.txt,xxx,1,5.000000,725430000,10.000110
     269perfexp-stl-pbv-na-na-na,corpus-1-50-1.txt,xxx,1,50.000000,335730000,10.000280
     270perfexp-stl-pbv-na-na-na,corpus-1-500-1.txt,xxx,1,500.000000,258380000,10.000052

  • doc/theses/mike_brooks_MMath/plots/string-pbv.gp

    r7d02d35 rbd72f517  
    33#set terminal wxt size 950,1250
    44
    5 DIR="pictures"
     5INDIR="build"
     6OUTDIR="build"
    67
    78set macros
    8 set output "build/string-graph-pbv.pdf"
     9set output OUTDIR."/plot-string-pbv.pdf"
     10
     11set multiplot layout 1, 2 ;
     12
     13
    914#set pointsize 2.0
    1015set grid
    … …  
    1419set logscale x
    1520set logscale y 2
    16 set xlabel "String Length being passed (interp. varies)" offset 2,0
    17 set ylabel "Time per append (ns, mean), log_{2} scale"
     21set xlabel "String length passed, varying (mean)"
     22set ylabel "Time per pass (ns, mean), log_{2} scale"
     23set yrange [4:64]
    1824set linetype 3 dashtype 2
    1925set linetype 4 dashtype 2
    20 plot DIR."/string-graph-pbv.dat" \
    21            i 0 using 1:2 title columnheader(1) with linespoints lt rgb "blue"   pt  2  ps 1 lw 1, \
    22         '' i 1 using 1:2 title columnheader(1) with linespoints lt rgb "red"    pt  3  ps 1 lw 1, \
    23         '' i 2 using 1:2 title columnheader(1) with linespoints lt rgb "blue"   pt  6  ps 1 lw 1
     26plot INDIR."/plot-string-pbv-varcorp.dat" \
     27           i 0 using 1:2 title columnheader(1) with linespoints lt rgb "red"    pt  3  ps 1 lw 1, \
     28        '' i 1 using 1:2 title columnheader(1) with linespoints lt rgb "blue"   pt  6  ps 1 lw 1
     29
     30set xlabel "String length passed, fixed"
     31set ylabel
     32plot INDIR."/plot-string-pbv-fixcorp.dat"  \
     33           i 0 using 1:2 title columnheader(1) with linespoints lt rgb "red"    pt  3  ps 1 lw 1, \
     34        '' i 1 using 1:2 title columnheader(1) with linespoints lt rgb "blue"   pt  6  ps 1 lw 1
     35
     36unset multiplot

  • doc/theses/mike_brooks_MMath/plots/string-peq-cppemu.gp

    r7d02d35 rbd72f517  
    1313set xtics (1,2,5,10,20,50,100,200,500)
    1414set logscale x
    15 set logscale y
    16 set yrange [10:200]
     15#set logscale y
     16set yrange [0:115]
    1717set xlabel "String Length being appended (mean, geo. dist.), log scale" offset 2,0
    1818set ylabel "Time per append (ns, mean)"

  • doc/theses/mike_brooks_MMath/plots/string-peq-cppemu.py

    r7d02d35 rbd72f517  
    1212import pandas as pd
    1313import numpy as np
     14import sys
    1415import os
    1516
    16 infile = os.path.dirname(os.path.abspath(__file__)) + '/../benchmarks/string/result-append-pbv.csv'
     17sys.path.insert(0, os.path.dirname(__file__))
     18from common import *
    1719
    1820prettyFieldNames = {
    … …  
    2325}
    2426
    25 timings = pd.read_csv(
    26     infile,
    27     names=['test', 'corpus', 'concatsPerReset', 'corpusItemCount', 'corpusMeanLenChars', 'concatDoneActualCount', 'execTimeActualSec'],
    28     dtype={'test':                  str,
    29            'corpus':                str,
    30            'concatsPerReset':       'Int64', # allows missing; https://stackoverflow.com/a/70626154
    31            'corpusItemCount':       np.int64,
    32            'corpusMeanLenChars':    np.float64,
    33            'concatDoneActualCount': np.int64,
    34            'execTimeActualSec':     np.float64},
    35     na_values=['xxx'],
    36 )
    37 # print(timings.head())
     27timings = loadParseTimingData('result-append-pbv.csv')
    3828
     29# Filter operation=peq, corpus=100-*-1
    3930
    40 # project: parse executable and corpus names
    41 
    42 timings[['test-slug',
    43      'sut-platform',
    44      'operation',
    45      'sut-cfa-level',
    46      'sut-cfa-sharing',
    47      'op-alloc']] = timings['test'].str.strip().str.split('-', expand=True)
    48 timings['sut'] = timings[['sut-platform',
    49                     'sut-cfa-level',
    50                     'sut-cfa-sharing',
    51                     'op-alloc']].agg('-'.join, axis=1)
    52 
    53 timings[['corpus-basename',
    54      'corpus-ext']] = timings['corpus'].str.strip().str.split('.', expand=True)
    55 timings[['corpus-slug',
    56      'corpus-nstrs',
    57      'corpus-meanlen',
    58      'corpus-runid']] = timings['corpus-basename'].str.strip().str.split('-', expand=True)
    59 timings["corpus-nstrs"] = pd.to_numeric(timings["corpus-nstrs"])
    60 timings["corpus-meanlen"] = pd.to_numeric(timings["corpus-meanlen"])
    61 timings["corpus-runid"] = pd.to_numeric(timings["corpus-runid"])
    62 
    63 
    64 # project: calculate fact
    65 
    66 timings['op-duration-s'] = timings['execTimeActualSec'] / timings['concatDoneActualCount']
    67 timings['op-duration-ns'] = timings['op-duration-s'] * 1000 * 1000 * 1000
    68 
    69 
    70 # Filter operation=peq
    71 
    72 groupedOp = timings.groupby('operation')
    73 tgtOpTimings = groupedOp.get_group('peq')
    74 
     31timings = timings.groupby('operation').get_group('peq')
     32timings = timings.groupby('corpus-nstrs').get_group(100)
     33timings = timings.groupby('corpus-runid').get_group(1)
    7534
    7635# Emit in groups
    7736
    78 groupedSut = tgtOpTimings.groupby('sut')
     37groupedSut = timings.groupby('sut')
    7938
    8039for sut, sgroup in groupedSut:

  • doc/theses/mike_brooks_MMath/plots/string-peq-sharing.gp

    r7d02d35 rbd72f517  
    33#set terminal wxt size 950,1250
    44
    5 DIR="pictures"
     5INDIR="build"
     6OUTDIR="build"
    67
    78set macros
    8 set output "build/string-graph-peq-sharing.pdf"
     9set output OUTDIR."/plot-string-peq-sharing.pdf"
    910#set pointsize 2.0
    1011set grid
    … …  
    1213set xtics (1,2,5,10,20,50,100,200,500)
    1314set logscale x
    14 #set logscale y 2
     15#set logscale y
     16set yrange [10:115]
    1517set xlabel "String Length being appended (mean, geo. dist.), log scale" offset 2,0
    1618set ylabel "Time per append (ns, mean)"
    1719set linetype 2 dashtype 2
    1820set linetype 4 dashtype 2
    19 plot DIR."/string-graph-peq-sharing.dat" \
     21plot INDIR."/plot-string-peq-sharing.dat" \
    2022           i 0 using 1:2 title columnheader(1) with linespoints lt rgb "red"    pt  2  ps 1 lw 1, \
    2123        '' i 1 using 1:2 title columnheader(1) with linespoints lt rgb "red"    pt  3  ps 1 lw 1, \

  • doc/theses/mike_brooks_MMath/plots/string-pta-sharing.gp

    r7d02d35 rbd72f517  
    33#set terminal wxt size 950,1250
    44
    5 DIR="pictures"
     5INDIR="build"
     6OUTDIR="build"
    67
    78set macros
    8 set output "build/string-graph-pta-sharing.pdf"
     9set output OUTDIR."/plot-string-pta-sharing.pdf"
    910#set pointsize 2.0
    1011set grid
    … …  
    1213set xtics (1,2,5,10,20,50,100,200,500)
    1314set logscale x
     15set yrange [8:4096]
    1416set logscale y 2
    1517set xlabel "String Length being appended (mean, geo. dist.), log scale" offset 2,0
    1618set ylabel "Time per append (ns, mean), log_{2} scale"
    17 set linetype 5 dashtype 2
    1819#show colornames
    19 plot DIR."/string-graph-pta-sharing.dat" \
     20plot INDIR."/plot-string-pta-sharing.dat" \
    2021           i 0 using 1:2 title columnheader(1) with linespoints lt rgb "red"    pt  2  ps 1 lw 1, \
    2122        '' i 1 using 1:2 title columnheader(1) with linespoints lt rgb "dark-green" pt  4  ps 1 lw 1, \
    2223        '' i 2 using 1:2 title columnheader(1) with linespoints lt rgb "blue"   pt  6  ps 1 lw 1, \
    23         '' i 3  using 1:2 title columnheader(1) with linespoints lt rgb "dark-green" pt  12  ps 1 lw 1, \
    24         '' i 4  using 1:2 title columnheader(1) with linespoints lt rgb "blue"  pt  8  ps 1 lw 1
     24        '' i 3  using 1:2 title columnheader(1) with linespoints lt rgb "dark-green" pt  12  ps 1 lw 1

  • doc/theses/mike_brooks_MMath/programs/bkgd-cfa-arrayinteract.cfa

    r7d02d35 rbd72f517  
    33
    44struct tm { int x; };
    5 forall (T*) T* alloc();
     5forall( T * ) T * alloc();
    66
    77int main () {

  • doc/theses/mike_brooks_MMath/programs/hello-accordion.cfa

    r7d02d35 rbd72f517  
    3131int getPref( @School( C, S ) & school@, int is, int pref ) {
    3232        for ( ic; C ) {
    33                 int curPref = @school.preferences@[ic][is];   $\C{// offset calculation implicit}$
    34                 if ( curPref == pref ) return ic;
     33                if ( pref == @school.preferences@[ic][is]; ) return ic; $\C{// offset calculation implicit}$
    3534        }
    3635        assert( false );
    3736}
     37
    3838
    3939
    … …  
    9191                sout | school.student_ids[is] | ": " | nonl;
    9292                for ( pref; 1 ~= nc ) {
    93                         int ic = getPref(school, is, pref);
     93                        int ic = getPref( school, is, pref );
    9494                        sout | school.course_codes[ ic ] | nonl;
    9595                }

  • doc/theses/mike_brooks_MMath/string.tex

    r7d02d35 rbd72f517  
    1717\begin{cquote}
    1818\begin{tabular}{@{}l|l|l|l@{}}
    19 C @char [ ]@                    &  \CC @string@                 & Java @String@     & \CFA @string@     \\
     19C @char [ ]@                    &  \CC @string@                 & Java @String@ & \CFA @string@ \\
    2020\hline
    21 @strcpy@, @strncpy@             & @=@                                   & @=@               & @=@       \\
    22 @strcat@, @strncat@             & @+@, @+=@                             & @+@, @+=@         & @+@, @+=@ \\
     21@strcpy@, @strncpy@             & @=@                                   & @=@                   & @=@   \\
     22@strcat@, @strncat@             & @+@, @+=@                             & @+@, @+=@             & @+@, @+=@     \\
    2323@strcmp@, @strncmp@             & @==@, @!=@, @<@, @<=@, @>@, @>=@
    24                                                 & @equals@, @compareTo@
    25                                                                                                                                         & @==@, @!=@, @<@, @<=@, @>@, @>=@ \\
    26 @strlen@                                & @length@, @size@              & @length@                      & @size@        \\
    27 @[ ]@                                   & @[ ]@                                 & @charAt@          & @[ ]@     \\
    28 @strncpy@                               & @substr@                              & @substring@       & @( )@, on RHS of @=@      \\
    29 @strncpy@                               & @replace@                             & @replace@         & @( )@, on LHS of @=@ \\
    30 @strstr@                                & @find@                                & @indexOf@         & @find@ \\
    31 @strcspn@                               & @find_first_of@               & @matches@         & @include@ \\
    32 @strspn@                                & @find_first_not_of@   & @matches@         & @exclude@ \\
    33 n/a                                             & @c_str@, @data@               & n/a               & @strcpy@, @strncpy@ \\
     24                                                                                                & @equals@, @compareTo@
     25                                                                                                                                & @==@, @!=@, @<@, @<=@, @>@, @>=@ \\
     26@strlen@                                & @length@, @size@              & @length@              & @size@        \\
     27@[ ]@                                   & @[ ]@                                 & @charAt@              & @[ ]@ \\
     28@strncpy@                               & @substr@                              & @substring@   & @( )@, on RHS of @=@  \\
     29@strncpy@                               & @replace@                             & @replace@             & @( )@, on LHS of @=@ \\
     30@strstr@                                & @find@                                & @indexOf@             & @find@ \\
     31@strcspn@                               & @find_first_of@               & @matches@             & @include@ \\
     32@strspn@                                & @find_first_not_of@   & @matches@             & @exclude@ \\
     33N/A                                             & @c_str@, @data@               & N/A                   & @strcpy@, @strncpy@ \\
    3434\end{tabular}
    3535\end{cquote}
    … …  
    5353
    5454
    55 \section{\CFA \lstinline{string} type}
     55\section{\CFA \lstinline{string} Type}
    5656\label{s:stringType}
    5757
    … …  
    272272ch = ch + 'b'; $\C[2in]{// LHS disambiguate, add character values}$
    273273s = 'a' + 'b'; $\C{// LHS disambiguate, concatenate characters}$
    274 printf( "%c\n", @'a' + 'b'@ ); $\C[2in]{// no LHS information, ambiguous}$
    275 printf( "%c\n", @(return char)@('a' + 'b') ); $\C{// disambiguate with ascription cast}$
     274printf( "%c\n", @'a' + 'b'@ ); $\C{// no LHS information, ambiguous}$
     275printf( "%c\n", @(return char)@('a' + 'b') ); $\C{// disambiguate with ascription cast}\CRT$
    276276\end{cfa}
    277277The ascription cast, @(return T)@, disambiguates by stating a (LHS) type to use during expression resolution (not a conversion).
    … …  
    319319ch = ch * 3; $\C[2in]{// LHS disambiguate, multiply character values}$
    320320s = 'a' * 3; $\C{// LHS disambiguate, concatenate characters}$
    321 printf( "%c\n", @'a' * 3@ ); $\C[2in]{// no LHS information, ambiguous}$
    322 printf( "%c\n", @(return char)@('a' * 3) ); $\C{// disambiguate with ascription cast}$
     321printf( "%c\n", @'a' * 3@ ); $\C{// no LHS information, ambiguous}$
     322printf( "%c\n", @(return char)@('a' * 3) ); $\C{// disambiguate with ascription cast}\CRT$
    323323\end{cfa}
    324324Fortunately, character multiplication without LHS information is even rarer than addition, so repurposing the operator @*@ for @string@ types is not a problem.
    … …  
    600600&
    601601\begin{cfa}
    602 for ( ;; ) {
     602for () {
    603603        size_t posn = exclude( line, alpha );
    604604  if ( posn == len( line ) ) break;
    … …  
    722722\end{tabular}
    723723\end{cquote}
    724 Input text can be gulped, including whitespace, from the current point to an arbitrary delimiter character using @getline@.
     724Input text can be \emph{gulped}, including whitespace, from the current point to an arbitrary delimiter character using @getline@.
    725725
    726726The \CFA philosophy for input is that, for every constant type in C, these constants should be usable as input.
    … …  
    760760\end{tabular}
    761761\end{cquote}
    762 Note, the ability to read in quoted strings to match with program string constants.
     762Note, the ability to read in quoted strings with whitespace to match with program string constants.
    763763The @nl@ at the end of an input ignores the rest of the line.
    764764
    … …  
    845845                                        & Laxed: The target's type is anything string-like; it may have a different status concerning ownership.
    846846                                                                & Strict: The target's type is the same as the source; both strings are equivalent peers concerning ownership.
    847                                                                                         & n/a           & no    & yes   & yes \\
     847                                                                                        & N/A           & no    & yes   & yes \\
    848848\hline
    849849Referent
    … …  
    863863        The C ``string'' is @char *@, under the conventions of @<string.h>@. Because this type does not manage a text allocation, symmetry does not apply.
    864864\item
    865         The Java @String@ class is analyzed; its @StringBuffer@ class behaves similarly to @C++@.
     865        The Java @String@ class is analyzed; its @StringBuffer@ class behaves similarly to \CC.
    866866\end{itemize}
    867867\caption{Comparison of languages' strings, storage management perspective.}
    … …  
    869869\end{figure}
    870870
    871 In C, these declarations give very different things.
     871In C, these declarations are very different.
    872872\begin{cfa}
    873873char x[$\,$] = "abcde";
    874874char * y = "abcde";
    875875\end{cfa}
    876 Both associate the declared name with fixed-six contiguous bytes, filled as @{'a', 'b', 'c', 'd', 'e', 0}@.
    877 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.
     876Both associate the declared name with the fixed, six contiguous bytes: @{'a', 'b', 'c', 'd', 'e', 0}@.
     877But @x@ is allocated on the stack (with values filled at the declaration), while @y@ refers to the executable's read-only data-section.
    878878With @x@ representing an allocation, it offers information in @sizeof(x)@ that @y@ does not.
    879 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.
     879But this extra information is second-class, as it can only be used in the immediate lexical context, \ie it cannot be passed to string operations or user functions.
    880880Only pointers to text buffers are first-class, and discussed further.
    881 
    882881\begin{cfa}
    883882char * s = "abcde";
    884 char * s1 = s;  $\C{// alias state, n/a symmetry, variable-constrained referent}$
    885 char * s2 = &s[1];  $\C{// alias state, n/a symmetry, variable-constrained referent}\CRT$
    886 char * s3 = &s2[1];  $\C{// alias state, n/a symmetry, variable-constrained referent}
     883char * s1 = s;  $\C[2.25in]{// alias state, N/A symmetry, variable-constrained referent}$
     884char * s2 = &s[1];  $\C{// alias state, N/A symmetry, variable-constrained referent}$
     885char * s3 = &s2[1];  $\C{// alias state, N/A symmetry, variable-constrained referent}\CRT$
    887886printf( "%s %s %s %s\n", s, s1, s2, s3 );
    888887$\texttt{\small abcde abcde bcde cde}$
    … …  
    904903string & s5 = s.substr(2,4);  $\C{// error: cannot point to temporary}\CRT$
    905904\end{cfa}
    906 The @s1@ lax symmetry reflects how its validity of depends on the lifetime of @s@.
     905The @s1@ lax symmetry reflects how its validity depends on the lifetime of @s@.
    907906It is common practice in \CC to use the @s1@-style for a by-reference function parameter.
    908907Doing 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.
    909908So, when the called function is a constructor, its definition typically uses an @s2@-style copy-initialization.
    910909Exceptions to this pattern are possible, but require the programmer to assure safety where the type system does not.
    911 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.
     910The @s3@ initialization must copy the substring to support a subsequent @c_str@ call, which provides null-termination, generally at a different position than the source string's.
    912911@s2@ assignment could be made fast, by reference-counting the text area and using copy-on-write, but would require an implementation upgrade.
    913912
    … …  
    929928With @s2@, the case for fast-copy is more subtle.
    930929Certainly, its value is not pointer-equal to @s@, implying at least a further allocation.
    931 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.
     930But because Java is \emph{not} constrained to use a null-terminated representation, a standard-library implementation is free to refer to the source characters in-place.
    932931Java does not meet the aliasing requirement because immutability makes it impossible to modify.
    933932Java'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@;
    … …  
    960959
    961960
    962 
    963 \subsection{Logical overlap}
     961\subsection{Logical Overlap}
    964962
    965963It may be unfamiliar to combine \VRef[Figure]{f:StrSemanticCompare}'s alias state and fragment referent in one API, or at the same time.
    966964This section shows the capability in action.
    967965
    968 In summary, the metaphor of a GUI text editor is intended.
    969 Selecting a consecutive block of text using the mouse defines an aliased substring within the file.
    970 Typing in this state overwrites what was there before, replacing the originally selected text with more or less text.
    971 But the \emph{whole file} grows or shrinks as a result, not just the selection.
    972 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.
    973 
    974 Now extend the metaphor to a multi-user online editor.
    975 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.
    976 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.
    977 
    978 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.
    979 But, departing from the document analogy, it is not necessary to keep a such a third string:
    980 no one has to resource-manage ``the document.''
    981 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.
    982 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.
    983 
    984 Edge cases, notably ``Venn-diagram overlap,'' had to have handlings chosen.
    985 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.
    986 The remainder of this section shows the resulting decisions, played out at the API level.
    987 
    988 \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).
     966\begin{comment}
     967The metaphor of a GUI text-editor is used to illustrate combining these features.
     968Most editors allow selecting a consecutive block of text (highlighted) to define an aliased substring within a document.
     969Typing in this area overwrites the prior text, replacing the selected text with less, same, or more text.
     970Importantly, the document also changes size, not just the selection.
     971%This alias model is assigning to an aliased substring for two strings overlapping by total containment: one is the selected string, the other is the document.
     972Extend the metaphor to two selected areas, where one area can be drag-and-dropped into another, changing the text in the drop area and correspondingly changing the document.
     973When the selected areas are indenpendent, the semantics of the drag-and-drop are straightforward.
     974However, for overlapping selections, either partial or full, there are multiple useful semantics.
     975For example, two areas overlap at the top, or bottom, or a block at a corner, where one areas is dropped into the other.
     976For selecting a smaller area within a larger, and dropping the smaller area into the larger to replace it.
     977In both cases, meaningful semantics must be constructed or the operation precluded.
     978However, without this advanced capability, certain operations become multi-step, possible requiring explicit temporaries.
     979\end{comment}
     980
     981A GUI text-editor provides a metaphor.
     982Selecting a block of text using the mouse defines an aliased substring within a document.
     983Typing in this area overwrites what was there, replacing the originally selected text with more or less text.
     984But the \emph{containing document} also grows or shrinks, not just the selection.
     985This action models assigning to an aliased substring when one string is completely contained in the other.
     986
     987Extend the metaphor to a multi-user editor.
     988If Alice selects a range of text at the bottom, while Bob is rewriting a paragraph at the top, Alice's selection holds onto the characters initially selected, unaffected by Bob making the document grow/shrink even though Alice's start index in the document is changing.
     989This action models assigning to an aliased substring when the two strings do not overlap.
     990
     991Logically, Alice's and Bob's actions on the whole document are like two single-user-edit cases, giving the semantics of the individual edits flowing into a whole.
     992But, there is no need to have two separate document strings.
     993Even if a third selection removes all the text, both Alice's and Bob's strings remain.
     994The independence of their selections assumes that the editor API does not allow the selection to be enlarged, \ie adding text from the containing environment, which may have disappeared.
     995
     996This leaves the ``Venn-diagram overlap'' cases, where Alice's and Bob's selections overlap at the top, bottom, or corner.
     997In this case, the selection areas are dependent, and so, changes in content and size in one may have an affect in the other.
     998There are multiple possible semantics for this case.
     999The remainder of this section shows the chosen semantics for all of the cases.
     1000
     1001String sharing is expressed using the @`share@ marker to indicate aliasing (mutations shared) \vs snapshot (not quite an immutable result, but one with subsequent mutations isolated).
    9891002This aliasing relationship is a sticky property established at initialization.
    9901003For example, here strings @s1@ and @s1a@ are in an aliasing relationship, while @s2@ is in a copy relationship.
    9911004\input{sharing1.tex}
    9921005Here, the aliasing (@`share@) causes partial changes (subscripting) to flow in both directions.
    993 (In the following examples, watch how @s1@ and @s1a@ change together, and @s2@ is independent.)
     1006(In the following examples, note how @s1@ and @s1a@ change together, and @s2@ is independent.)
    9941007\input{sharing2.tex}
    9951008Similarly for complete changes.
    … …  
    9991012\input{sharing4.tex}
    10001013
    1001 Now, consider string @s1_mid@ being an alias in the middle of @s1@, along with @s2@, made by a simple copy from the middle of @s1@.
     1014Now, consider string @s1_mid@ being an alias in the middle of @s1@, along with @s2@, made by a copy from the middle of @s1@.
    10021015\input{sharing5.tex}
    10031016Again, @`share@ passes changes in both directions; copy does not.
    … …  
    10201033When @s1_bgn@'s size increases by 3, @s1_mid@'s starting location moves from 1 to 4 and @s1_end@'s from 3 to 6,
    10211034
    1022 When changes happens on an aliasing substring that overlap.
     1035When changes happen on an aliasing substring that overlap.
    10231036\input{sharing10.tex}
    1024 Strings @s1_crs@ and @s1_mid@ overlap at character 4, @j@ because the substrings are 3,2 and 4,2.
     1037Strings @s1_crs@ and @s1_mid@ overlap at character 4, @j@, because the substrings are 3,2 and 4,2.
    10251038When @s1_crs@'s size increases by 1, @s1_mid@'s starting location moves from 4 to 5, but the overlapping character remains, changing to @'+'@.
    10261039
    … …  
    10791092
    10801093
    1081 
    1082 \section{Storage management}
     1094\section{Storage Management}
    10831095
    10841096This section discusses issues related to storage management of strings.
    … …  
    10991111const string s1 = "abc";
    11001112\end{cfa}
    1101 the @const@ applies to the @s1@ pointer to @"abc"@, and @"abc"@ is an immutable constant that is \emph{copied} into the string's storage.
    1102 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.
    1103 
    1104 
    1105 
    1106 \subsection{General implementation}
     1113@const@ applies to the @s1@ pointer to @"abc"@, and @"abc"@ is an immutable constant that is \emph{copied} into the string's storage.
     1114Hence, @s1@ is not pointing at an immutable constant and its underlying string is mutable, unless some other designation is specified, such as Java's global immutable rule.
     1115
     1116
     1117\subsection{General Implementation}
    11071118\label{string-general-impl}
    11081119
    … …  
    11131124A string is a smart pointer into this buffer.
    11141125
    1115 This cycle of frequent cheap allocations, interspersed with infrequent expensive compactions, has obvious similarities to a general-purpose memory manager based on garbage collection (GC).
     1126This cycle of frequent cheap allocations, interspersed with infrequent expensive compactions, has obvious similarities to a general-purpose memory-manager based on garbage collection (GC).
    11161127A few differences are noteworthy.
    11171128First, in a general purpose manager, the allocated objects may contain pointers to other objects, making the transitive reachability of these objects a crucial property.
    11181129Here, the allocations are text, so one allocation never keeps another alive.
    11191130Second, in a general purpose manager, the handle that keeps an allocation alive is a bare pointer.
    1120 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.
     1131For strings, a fatter representation is acceptable because this pseudo-pointer is only used for entry into the string-heap, not for general data-substructure linking around the general heap.
    11211132
    11221133\begin{figure}
    … …  
    11281139\VRef[Figure]{f:memmgr-basic} shows the representation.
    11291140The heap header and text buffer define a sharing context.
    1130 Normally, one global sharing context is appropriate for an entire program;
    1131 concurrent exceptions are discussed in \VRef{s:ControllingImplicitSharing}.
    1132 A string is a handle into the buffer and node within a linked list.
     1141Normally, one global context is appropriate for an entire program;
     1142concurrency is discussed in \VRef{s:ControllingImplicitSharing}.
     1143A string is a handle to a node in a linked list containing a information about a string text in the buffer.
    11331144The list is doubly linked for $O(1)$ insertion and removal at any location.
    11341145Strings are ordered in the list by text start address.
    1135 The header maintains a next-allocation pointer, @alloc@, pointing to the last live allocation in the buffer.
     1146The heap header maintains a next-allocation pointer, @alloc@, pointing to the last live allocation in the buffer.
    11361147No external references point into the buffer and the management procedure relocates the text allocations as needed.
    11371148A string handle references a containing string, while its string is contiguous and not null terminated.
    … …  
    11391150String handles can be allocated in the stack or heap, and represent the string variables in a program.
    11401151Normal C life-time rules apply to guarantee correctness of the string linked-list.
    1141 The text buffer is large enough with good management so that often only one dynamic allocation is necessary during program execution.
     1152The text buffer is large enough with good management so that often only one dynamic allocation is necessary during program execution, but not so large as to cause program bloat.
    11421153% During this period, strings can vary in size dynamically.
    11431154
    11441155When the text buffer fills, \ie the next new string allocation causes @alloc@ to point beyond the end of the buffer, the strings are compacted.
    11451156The linked handles define all live strings in the buffer, which indirectly defines the allocated and free space in the buffer.
    1146 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.
    1147 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.
     1157The string handles are maintained in sorted order, so the handle list can be traversed, copying the first live text to the start of the buffer, and subsequent strings after each other.
     1158After compaction, if free storage is 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.
    11481159Note, the list of string handles is structurally unaffected during a compaction;
    11491160only the text pointers in the handles are modified to new buffer locations.
    … …  
    11571168Both string initialization styles preserve the string module's internal invariant that the linked-list order matches the buffer order.
    11581169For string destruction, handles are removed from the list.
    1159 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.
    1160 
    1161 Certain string operations can result in a substring of another string.
    1162 The resulting handle is then placed in the correct sorted position in the list, possible with a short linear search to locate the position.
     1170Once the last handle using a run of buffer characters is destroyed, that buffer space is excluded from use until the next compaction.
     1171
     1172Certain string operations result in a substring of another string.
     1173The resulting handle is then placed in the correct sorted position in the list, possible requiring a short linear search to locate the position.
    11631174For string operations resulting in a new string, that string is allocated at the end of the buffer.
    11641175For shared-edit strings, handles that originally referenced containing locations need to see the new value at the new buffer location.
    … …  
    11751186
    11761187
    1177 \subsection{RAII limitations}
     1188\subsection{RAII Limitations}
    11781189\label{string-raii-limit}
    11791190
    11801191Earlier work on \CFA~\cite[ch.~2]{Schluntz17} implemented object constructors and destructors for all types (basic and user defined).
    1181 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.
     1192A 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 deallocated.
    11821193This 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.
    11831194
    … …  
    12131224\end{cfa}
    12141225A module providing the @T@ type can traverse @all_T@ at relevant times, to keep the objects ``good.''
    1215 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.
     1226Hence, 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'' during its lifetime.
    12161227Again, both \CFA and \CC support this usage style.
    12171228
    12181229A third capability concerns \emph{implicitly} requested copies.
    12191230When 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.
    1220 In the parameter direction, the language's function-call handling must arrange for a copy-constructor call to happen\footnote{
    1221         \CC also offers move constructors and return-value optimization~\cite{RVO20}.
    1222         These features help reduce unhelpful copy-constructor calls, which, for types like the example \lstinline{S}, would lead to extra memory allocations.
    1223         \CFA does not currently have these features; adding similarly-intended features to \CFA is desirable.
    1224         However, this section is about a problem in the realization of features that \CFA already supports.
    1225         To understand the problem presented, the appropriate comparison is with classic versions of \CC that treated such copy-constructor calls as necessary.}
    1226 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.
    1227 (In the return direction, the roles are reversed and the copy-constructor call happens near the return of control.)
    1228 \CC supports this capability without qualification.
    1229 \CFA offers limited support here; simple examples work, but implicit copying does not combine successfully with the other RAII capabilities discussed.
     1231In the parameter direction, the language's function-call handling must arrange for a copy-constructor call to happen, 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.
     1232In the return direction, the roles are reversed and the copy-constructor call happens near the return of control.
     1233\CC supports this capability.% without qualification.
     1234\CFA offers limited support;
     1235simple examples work, but implicit copying does not combine successfully with the other RAII capabilities discussed.
     1236
     1237\CC also offers move constructors and return-value optimization~\cite{RVO20}.
     1238These features help reduce unhelpful copy-constructor calls, which, for types like the @S@ example, would lead to extra memory allocations.
     1239\CFA does not currently have these features; adding similarly-intended features to \CFA is desirable.
     1240However, this section is about a problem in the realization of features that \CFA already supports.
     1241Hence, the comparison continues with the classic version of \CC that treated such copy-constructor calls as necessary.
    12301242
    12311243To summarize the unsupported combinations, the relevant features are:
    … …  
    12431255At that time, adhering to a principal of minimal intervention, this code could always be treated as passthrough:
    12441256\begin{cfa}
    1245 struct U {...};
     1257struct U { ... };
    12461258// RAII to go here
    12471259void f( U u ) { F_BODY(u) }
    … …  
    12491261f( x );
    12501262\end{cfa}
    1251 But adding custom RAII (at ``...here'') changes things.
    1252 The common C++ lowering~\cite[Sec. 3.1.2.3]{cxx:raii-abi} proceeds differently than the present CFA lowering.
    1253 
    1254 \noindent
    1255 \begin{tabular}{l|l}
    1256 \begin{cfa}
    1257 // C++, likely CFA to be
     1263But adding custom RAII (at ``...go here'') changes things.
     1264The common \CC lowering~\cite[Sec. 3.1.2.3]{cxx:raii-abi} proceeds differently than the present \CFA lowering.
     1265\begin{cquote}
     1266\setlength{\tabcolsep}{15pt}
     1267\begin{tabular}{@{}l|l@{}}
     1268\begin{cfa}
     1269$\C[0.0in]{// \CC, \CFA future}\CRT$
    12581270struct U {...};
    12591271// RAII elided
    12601272void f( U * __u_orig ) {
    12611273        U u = * __u_orig;  // call copy ctor
    1262         F_BODY(u)
     1274        F_BODY( u );
    12631275        // call dtor, u
    12641276}
    12651277U x; // call default ctor
    1266 f( & x ) ;
     1278
     1279
     1280f( &x ) ;
     1281
     1282
    12671283// call dtor, x
    12681284\end{cfa}
    12691285&
    12701286\begin{cfa}
    1271 // CFA today
     1287$\C[0.0in]{// \CFA today}\CRT$
    12721288struct U {...};
    12731289// RAII elided
    12741290void f( U u ) {
    1275         F_BODY(u)
     1291
     1292        F_BODY( u );
     1293
    12761294}
    12771295U x; // call default ctor
    … …  
    12841302\end{cfa}
    12851303\end{tabular}
    1286 
    1287 In the CFA-today scheme, the lowered form is still using a by-value C call.
    1288 C does a @memcpy@ on structs passed by value.
    1289 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.
    1290 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@.
    1291 The \CC scheme does not have this problem because it constructs the for-@f@ copy in the correct location.
    1292 
    1293 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.
     1304\end{cquote}
     1305The current \CFA scheme is still using a by-value C call.
     1306C does a @memcpy@ on structures passed by value.
     1307And so, @F_BODY@ sees the bits of @__u_for_f@ occurring at an address that has never been presented to the @U@ lifecycle functions.
     1308If @U@ is trying to have a style-\#2 invariant, it shows up broken in @F_BODY@: references supposedly to @u@ are actually to @__u_for_f@.
     1309The \CC scheme does not have this problem because it constructs the for @f@ copy in the correct location within @f@.
     1310
     1311Yet, the current \CFA 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.
     1312So, reference-counting or simple ownership applications get their invariants respected under call/return-by-value.
    12941313
    12951314% [Mike is not currently seeing how distinguishing initialization from assignment is relevant]
    … …  
    13251344% The following discusses the consequences of this semantics with respect to lifetime management of \CFA strings.
    13261345
    1327 
    1328 The string API offers style \#3's pass-by-value in, for example, in the return of @"a" + "b"@.
     1346The string API offers style \#3's pass-by-value in, \eg in the return of @"a" + "b"@.
    13291347Its implementation uses the style-\#2 invariant of the string handles being linked to each other, helping to achieve high performance.
    1330 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.
     1348Since these two RAII styles cannot coexist, a workaround splits the API into two layers: one that provides pass-by-value, built upon the other with inter-linked handles.
    13311349The layer with pass-by-value incurs a performance penalty, while the layer without delivers the desired runtime performance.
    1332 The slower, friendlier High Level API (HL, type @string@) wrapps the faster, more primitive Low Level API (LL, type @string_res@, abbreviating ``resource'').
     1350The slower, friendlier High Level API (HL, type @string@) wraps the faster, more primitive Low Level API (LL, type @string_res@, abbreviating ``resource'').
    13331351Both APIs present the same features, up to return-by-value operations being unavailable in LL and implemented via the workaround in HL.
    13341352The intention is for most future code to target HL.
    1335 When the RAII issue is fixed, the full HL feature set will be acheivable using the LL-style lifetime management.
    1336 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.
     1353When the RAII issue is fixed, the full HL feature set will be achievable using the LL-style lifetime management.
     1354Then, HL will be removed;
     1355LL's type will be renamed @string@ and programs written for current HL will run faster.
    13371356In the meantime, performance-critical sections of applications must use LL.
    13381357Subsequent performance experiments \see{\VRef{s:PerformanceAssessment}} use the LL API when comparing \CFA to other languages.
    13391358This measurement gives a fair estimate of the goal state for \CFA.
    13401359A separate measure of the HL overhead is also included.
    1341 
    1342 \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.
    1343 
    1344 To use LL, a programmer rewrites invocations that used pass-by-value APIs into invocations where the resourcing is more explicit.
    1345 Many invocations are unaffected, notably including assignment and comparison.
    1346 Of the capabilities listed in \VRef[Figure]{f:StrApiCompare}, only the following three cases have revisions.
    1347 
    1348 \noindent
     1360hence, \VRef[Section]{string-general-impl} us describing the goal state for \CFA.
     1361In present state, the type @string_res@ replaces its mention of @string@ as inter-linked handle.
     1362
     1363To use LL, a programmer rewrites invocations using pass-by-value APIs into invocations where resourcing is more explicit.
     1364Many invocations are unaffected, notably assignment and comparison.
     1365Of the capabilities listed in \VRef[Figure]{f:StrApiCompare}, only the following three cases need revisions.
     1366\begin{cquote}
     1367\setlength{\tabcolsep}{15pt}
    13491368\begin{tabular}{ll}
    13501369HL & LL \\
    13511370\hline
    13521371\begin{cfa}
     1372
    13531373string s = "a" + "b";
    13541374\end{cfa}
    … …  
    13631383string s = "abcde";
    13641384string s2 = s(2, 3); // s2 == "cde"
     1385
    13651386s(2,3) = "x"; // s == "abx" && s2 == "cde"
    13661387\end{cfa}
    … …  
    13761397\begin{cfa}
    13771398string s = "abcde";
     1399
    13781400s[2] = "xxx";  // s == "abxxxde"
    13791401\end{cfa}
    … …  
    13851407\end{cfa}
    13861408\end{tabular}
    1387 
     1409\end{cquote}
    13881410The 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.
    13891411
    13901412
    1391 
    1392 \subsection{Sharing implementation}
     1413\subsection{Sharing Implementation}
    13931414\label{sharing-impl}
    13941415
    1395 The \CFA string module has two mechanisms to handle the case when string handles share a run of text.
    1396 
     1416The \CFA string module has two mechanisms to deal with string handles sharing text.
    13971417In the first type of sharing, the user requests that both string handles be views of the same logical, modifiable string.
    13981418This state is typically produced by the substring operation.
    … …  
    14041424$\texttt{\small axcde xc}$
    14051425\end{cfa}
    1406 In a typical substring call, the source string-handle is referencing an entire string, and the resulting, newly made, string handle is referencing a portion of the original.
    1407 In this state, a subsequent modification made by either is visible in both.
     1426Here, the source string-handle is referencing an entire string, and the resulting, newly made, string handle is referencing a contained portion of the original.
     1427In this state, a modification made in the overlapping area is visible in both strings.
    14081428
    14091429The second type of sharing happens when the system implicitly delays the physical execution of a logical \emph{copy} operation, as part of its copy-on-write optimization.
    … …  
    14181438In this state, a subsequent modification done on one handle triggers the deferred copy action, leaving the handles referencing different text within the buffer, holding distinct values.
    14191439
    1420 A further abstraction, in the string module's implementation, helps distinguish the two senses of sharing.
     1440A further abstraction helps distinguish the two senses of sharing.
    14211441A 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.
    14221442The SES is represented by a second linked list among the handles.
    … …  
    14271447
    14281448
    1429 \subsection{Controlling implicit sharing}
     1449\subsection{Controlling Implicit Sharing}
    14301450\label{s:ControllingImplicitSharing}
    14311451
    … …  
    14341454In detail, string sharing has inter-linked string handles, so managing one string is also managing the neighbouring strings, and from there, a data structure of the ``set of all strings.''
    14351455Therefore, it is useful to toggle this capability on or off when it is not providing any application benefit.
    1436 
    1437 \begin{figure}
    1438     \begin{tabular}{ll}
    1439         \lstinputlisting[language=CFA, firstline=10, lastline=55]{sharectx.run.cfa}
    1440         &
    1441         \raisebox{-0.17\totalheight}{\includegraphics{string-sharectx.pdf}} % lower
    1442     \end{tabular}
    1443         \caption{Controlling copying vs sharing of strings using \lstinline{string_sharectx}.}
    1444         \label{fig:string-sharectx}
    1445 \end{figure}
    14461456
    14471457The \CFA string library provides the type @string_sharectx@ to control an ambient sharing context.
    … …  
    14561466Executing the example does not produce an interesting outcome, but the comments in the picture indicate when the logical copy operation runs with
    14571467\begin{description}
    1458     \item[share:] the copy being deferred, as described through the rest of this section (fast), or
    1459     \item[copy:] the copy performed eagerly (slow).
     1468        \item[share:] the copy being deferred, as described through the rest of this section (fast), or
     1469        \item[copy:] the copy performed eagerly (slow).
    14601470\end{description}
    14611471Only eager copies can cross @string_sharectx@ boundaries.
    14621472The intended use is with stack-managed lifetimes, in which the established context lasts until the current function returns, and affects all functions called that do not create their own contexts.
    14631473
    1464 [ TODO: true up with ``is thread local'' (implement that and expand this discussion to give a concurrent example, or adjust this wording) ]
    1465 
    1466 
    1467 \subsection{Sharing and threading}
     1474\begin{figure}
     1475        \begin{tabular}{ll}
     1476                \lstinputlisting[language=CFA, firstline=10, lastline=55]{sharectx.run.cfa}
     1477                &
     1478                \raisebox{-0.17\totalheight}{\includegraphics{string-sharectx.pdf}} % lower
     1479        \end{tabular}
     1480        \caption{Controlling copying vs sharing of strings using \lstinline{string_sharectx}.}
     1481        \label{fig:string-sharectx}
     1482\end{figure}
     1483
     1484
     1485\subsection{Sharing and Threading}
    14681486
    14691487The \CFA string library provides no thread safety, the same as \CC string, providing similar performance goals.
    … …  
    14741492
    14751493
    1476 \subsection{Future work}
    1477 
    1478 Implementing the small-string optimization is straightforward, as a string header contains a pointer to the string text in the buffer.
    1479 This pointer could be marked with a flag and contain a small string.
    1480 However, there is now a conditional check required on the fast-path to switch between small and large string operations.
    1481 
    1482 It might be possible to pack 16- or 32-bit Unicode characters within the same string buffer as 8-bit characters.
    1483 Again, locations for identification flags must be found and checked along the fast path to select the correct actions.
    1484 Handling utf8 (variable length), is more problematic because simple pointer arithmetic cannot be used to stride through the variable-length characters.
    1485 Trying to use a secondary array of fixed-sized pointers/offsets to the characters is possible, but raises the question of storage management for the utf8 characters themselves.
    1486 
    1487 
    1488 \section{Performance assessment}
    1489 \label{s:PerformanceAssessment}
    1490 
    1491 I assessed the \CFA string library's speed and memory usage against strings in \CC STL.
    1492 
    1493 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.
    1494 
    1495 Moreover, the results support the \CFA string's position as a high-level enabler of simplified text processing.
    1496 STL makes its user think about memory management.
    1497 When the user does, and is successful, STL's performance can be very good.
    1498 But when the user fails to think through the consequences of the STL representation, performance becomes poor.
    1499 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.
    1500 
    1501 % The final test shows the overall win of the \CFA text-sharing mechanism.
    1502 % It exercises several operations together, showing \CFA enabling clean user code to achieve performance that STL requires less-clean user code to achieve.
    1503 
    1504 
    1505 \subsection{Methodology}
    1506 
    1507 These tests use a \emph{corpus} of strings.
    1508 Their lengths are important; the specific characters occurring in them are immaterial.
    1509 In a result graph, a corpus's mean string length is often the independent variable shown on the X axis.
    1510 
    1511 When a corpus contains strings of different lenghths, the lengths are drawn from a geometric distribution.
    1512 Therefore, strings much longer than the mean occur nontrivially and strings slightly shorter than the mean occur most often.
    1513 A corpus's string sizes are one of:
    1514 \begin{description}
    1515         \item [Fixed-size] all string lengths are of the stated size.
    1516         \item [Varying 1 and up] the string lengths are drawn from the geometric distribution with a stated mean and all lengths occur.
    1517         \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.''}
    1518 \end{description}
    1519 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.
    1520 In the general case, an STL string handle is a pointer (to separately allocated text) and a length.
    1521 But when the text is shorter than this representation, the optimization repurposes the handle's storage to eliminate using the heap.
     1494\subsection{Short-String Optimization}
     1495
     1496\CC implements a short-string ($\le$16) optimization (SSO).
     1497As a string header contains a pointer to the string text, this pointer can be tagged and used to contain a short string, removing a dynamic memory allocation/deallocation.
    15221498\begin{c++}
    15231499class string {
    … …  
    15291505                char sstr[sizeof(lstr)]; $\C{// short string <16 characters, text in situ}$
    15301506        };
    1531         $\C{// tagging for kind (short or long) elided}$
     1507        // some tagging for short or long strings
    15321508};
    15331509\end{c++}
    1534 
     1510However, there is now a conditional check required on the fast-path to switch between short and long string operations.
     1511
     1512It might be possible to pack 16- or 32-bit Unicode characters within the same string buffer as 8-bit characters.
     1513Again, locations for identification flags must be found and checked along the fast path to select the correct actions.
     1514Handling utf8 (variable length), is more problematic because simple pointer arithmetic cannot be used to stride through the variable-length characters.
     1515Trying to use a secondary array of fixed-sized pointers/offsets to the characters is possible, but raises the question of storage management for the utf8 characters themselves.
     1516
     1517
     1518\section{Performance Assessment}
     1519\label{s:PerformanceAssessment}
     1520
     1521I assessed the \CFA string library's speed and memory usage against strings in \CC STL.
     1522Overall, this analysis shows that adding support for the features shown earlier in the chapter comes at no substantial cost in the performance of features common to both APIs.
     1523
     1524Moreover, the results support the \CFA string's position as a high-level enabler of simplified text processing.
     1525STL makes its user think about memory management.
     1526When the user does, and is successful, STL's performance can be very good.
     1527But when the user fails to think through the consequences of the STL representation, performance becomes poor.
     1528The \CFA string lets the user work at the level of just putting the right text into the right variables, with corresponding performance degradations reduced or eliminated.
     1529
     1530% The final test shows the overall win of the \CFA text-sharing mechanism.
     1531% It exercises several operations together, showing \CFA enabling clean user code to achieve performance that STL requires less-clean user code to achieve.
     1532
     1533
     1534\subsection{Methodology}
     1535
     1536These tests use a \emph{corpus} of strings.
     1537Their lengths are important; the specific characters occurring in them are immaterial.
     1538In a result graph, a corpus's mean string length is often the independent variable shown on the X axis.
     1539
     1540When a corpus contains strings of different lengths, the lengths are drawn from a geometric distribution.
     1541Therefore, strings much longer than the mean occur less often and strings slightly shorter than the mean occur most often.
     1542A corpus's string sizes are one of:
     1543\begin{description}
     1544        \item [Fixed-size] all string lengths are of the stated size.
     1545        \item [Varying 1 and up] the string lengths are drawn from the geometric distribution with a stated mean and all lengths occur.
     1546        \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.
     1547\end{description}
     1548The special treatment of length 16 deals with the SSO in STL @string@, currently not implemented in \CFA.
    15351549A fixed-size or from-16 distribution ensures that \CC's extra-optimized cases are isolated within, or removed from, the comparison.
    1536 
    15371550In all experiments that use a corpus, its text is generated and loaded into the system under test before the timed phase begins.
    1538 
    15391551To ensure comparable results, a common memory allocator is used for \CFA and \CC.
    1540 \CFA runs the llheap allocator~\cite{Zulfiqar22}; the test rig plugs this same allocator into \CC.
     1552\CFA runs the llheap allocator~\cite{Zulfiqar22}, which is also plugged into \CC.
    15411553
    15421554The operations being measured take dozens of nanoseconds, so a succession of many invocations is run and timed as a group.
    1543 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.
    1544 Timing outcomes reprt mean nanoseconds per invocation, which includes harness overhead and the targeted string API execution.
     1555The experiments run for a fixed duration (5 seconds), as determined by re-checking @clock()@ every 10,000 invocations, which is never more often than once per 80 ms.
     1556Timing outcomes report mean nanoseconds per invocation, which includes harness overhead and the targeted string API execution.
    15451557
    15461558\PAB{To discuss: hardware and such}
    15471559
    1548 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@.
    1549 
    1550 \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.
    1551 Some experiments include measurements in this mode for baselining purposes.
    1552 It is called ``\CC emulation mode'' or ``nosharing'' here.
    1553 
     1560As discussed in \VRef[Section]{string-raii-limit}, general performance comparisons are made using \CFA's faster, low-level string API, named @string_res@.
     1561\VRef{s:ControllingImplicitSharing} presents an operational mode where \CFA string sharing is turned off.
     1562In this mode, the \CFA string operates similarly to \CC's, by using a heap allocation for string text.
     1563Some experiments include measurements in this mode for baselining purposes, called ``\CC emulation mode'' or ``nosharing''.
    15541564
    15551565
    15561566\subsection{Test: Append}
    15571567
    1558 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.
    1559 
     1568These tests measure the speed of appending strings from the corpus onto a larger, growing string.
     1569They show \CFA performing comparably to \CC overall, though with penalties for simple API misuses.
    15601570The basic harness is:
    1561 \begin{cquote}
    1562 \setlength{\tabcolsep}{20pt}
    1563 \begin{cfa}
    1564 START_TIMER
    1565 for ( ... ) {
    1566         string_res accum;
    1567         for ( i; 100 ) {
    1568                 accum += corpus[ f(i) ]; // importing from char * here
    1569                 COUNT_ONE_OP_DONE
     1571\begin{cfa}
     1572// set alarm duration
     1573for ( ... ) { $\C[1.5in]{// loop for duration}$
     1574        for ( i; N ) { $\C{// perform multiple appends (concatenations)}$
     1575                accum += corpus[ f( i ) ];
    15701576        }
     1577        count += N; $\C{// count number of appends}\CRT$
    15711578}
    1572 STOP_TIMER
    1573 \end{cfa}
    1574 \end{cquote}
    1575 The harness's outer loop executes until a sample-worthy amount of execution has happened.
    1576 The inner loop builds up the desired-length string with successive appends, before the outer makes it start over from a blank accumulator.
    1577 Each harness run targets a specific (mean) corpus string length and produces one data point on the result graph.
    1578 
     1579\end{cfa}
     1580The harness's outer loop executes for the experiment duration.
     1581The string is reset to empty before appending (not shown).
     1582The inner loop builds up a growing-length string with successive appends.
     1583Each run targets a specific (mean) corpus string length and produces one data point on the result graph.
    15791584Three specific comparisons are made with this harness.
    15801585Each picks its own independent-variable basis of comparison.
    1581 
    1582 All three comparisons use the varying-from-1 corpus construction, \ie they allow the STL to show its advantage from small-string optimization.
     1586All three comparisons use the varying-from-1 corpus construction, \ie they allow the STL to show its advantage for SSO.
    15831587
    15841588
    15851589\subsubsection{Fresh vs Reuse in \CC, Emulation Baseline}
    15861590
    1587 The first experiment compares \CFA with \CC, with \CFA operating in nosharing mode (and \CC having no other mode).
    1588 This experiment simply baselines how \CFA modestly lags \CC's optimization/tuning level generally, yet reproduces a coarser phenomenon.
    1589 
    1590 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.
    1591 
    1592 \begin{cquote}
    1593 \setlength{\tabcolsep}{20pt}
     1591The first experiment compares \CFA with \CC, with \CFA operating in nosharing mode and \CC having no other mode, hence both string package are using @malloc@/@free@.
     1592% This experiment establishes a baseline for other experiments.
     1593This experiment also introduces the first \CC coding pitfall, which the next experiment shows is helped by turning on \CFA sharing.
     1594% This pitfall shows, a \CC programmer must pay attention to string variable reuse.
     1595In the following, both programs are doing the same thing: start with @accum@ empty and build it up by appending @N@ strings (type @string@ in \CC and the faster @string_res@ in \CFA).
     1596\begin{cquote}
     1597\setlength{\tabcolsep}{40pt}
    15941598\begin{tabular}{@{}ll@{}}
    15951599% \multicolumn{1}{c}{\textbf{fresh}} & \multicolumn{1}{c}{\textbf{reuse}} \\
    … …  
    15971601
    15981602for ( ... ) {
    1599         @string_res accum;@       // fresh
    1600         for ( ... )
    1601                 accum @+=@ ...
     1603        @string_res accum;@     $\C[1.5in]{// fresh}$
     1604        for ( N )
     1605                accum @+=@ ...  $\C{// append}\CRT$
    16021606}
    16031607\end{cfa}
    … …  
    16061610string_res accum;
    16071611for ( ... ) {
    1608         @accum = "";@  $\C[1in]{// reuse\CRT}$
    1609         for ( ... )
    1610                 accum @+=@ ...
     1612        @accum = "";@  $\C[1.5in]{// reuse}$
     1613        for ( N )
     1614                accum @+=@ ...  $\C{// append}\CRT$
    16111615}
    16121616\end{cfa}
    16131617\end{tabular}
    16141618\end{cquote}
    1615 
    1616 Both programs are doing the same thing: start with @x@ empty and build it up by appending the same chunks.
    1617 A programmer should not have to consider this difference.
    1618 But from under the covers, each string being an individual allocation leaks through.
    1619 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.
    1620 This capacity stretching is a sticky property that survives assigning a (short, empty-string) value into an existing initialization.
    1621 So, the ``reuse'' version benefits from not growing the allocation on subsequent runs of the inner loop.
    1622 Yet, the ``fresh'' version is constantly restarting from a small buffer.
     1619The difference is creating a new or reusing an existing string variable.
     1620The pitfall is that most programmers do not consider this difference.
     1621However, creating a new variable implies deallocating the previous string storage and allocating new empty storage.
     1622As the string grows, further deallocations/allocations are required to release the previous and extend the current string storage.
     1623So, the fresh version is constantly restarting with zero string storage, while the reuse version benefits from having its prior large storage from the last append sequence.
    16231624
    16241625\begin{figure}
    … …  
    16261627        \includegraphics{plot-string-peq-cppemu.pdf}
    16271628%       \includegraphics[width=\textwidth]{string-graph-peq-cppemu.png}
    1628         \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.}
     1629        \caption{Fresh vs Reuse in \CC, Emulation Baseline.
     1630        Average time per iteration with one \lstinline{x += y} invocation (lower is better).
     1631        Comparing \CFA's STL emulation mode with STL implementations, and comparing the fresh with reused reset styles.}
    16291632        \label{fig:string-graph-peq-cppemu}
    1630 \end{figure}
    1631 
    1632 \VRef[Figure]{fig:string-graph-peq-cppemu} shows the resulting performance.
    1633 The fresh \vs reuse penalty is the dominant difference.
    1634 The cost is 40\% averaged over the cases shown and minimally 24\%.
    1635 It shows up consistently on both the \CFA and STL implementations, and this cost is more prominent with larger strings.
    1636 
    1637 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.
    1638 This penalty characterizes implementation fine tuning done with STL and not done yet done with \CFA.
    1639 
    1640 
    1641 \subsubsection{\CFA's Fresh-Reuse Compromise}
    1642 
    1643 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.
    1644 
    1645 \begin{figure}
    1646 \centering
    1647         \includegraphics{string-graph-peq-sharing.pdf}
     1633        \bigskip
     1634        \bigskip
     1635        \includegraphics{plot-string-peq-sharing.pdf}
    16481636%       \includegraphics[width=\textwidth]{string-graph-peq-sharing.png}
    1649         \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}.}
     1637        \caption{\CFA Compromise for Fresh \vs Reuse.
     1638        Average time per iteration with one \lstinline{x += y} invocation (lower is better).
     1639        Comparing \CFA's sharing mode with STL, and comparing the fresh with reused reset styles.
     1640        The \CC results are repeated from \VRef[Figure]{fig:string-graph-peq-cppemu}.}
    16501641        \label{fig:string-graph-peq-sharing}
    16511642\end{figure}
    16521643
    1653 \VRef[Figure]{fig:string-graph-peq-sharing} has the result.
    1654 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.
    1655 
    1656 
    1657 \subsubsection{\CFA's low overhead for misusing \lstinline{+}}
    1658 
    1659 A further pitfall occurs when the user writes @x = x + y@, rather than @x += y@.  Again, they are logically equivalent.
     1644\VRef[Figure]{fig:string-graph-peq-cppemu} shows the resulting performance.
     1645The two fresh (solid) lines and the two reuse (dash) lines are identical, except for lengths $\le$10, where the \CC SSO has a 40\% average and minimally 24\% advantage.
     1646The gap between the fresh and reuse lines is the removal of the dynamic memory allocates and reuse of prior storage, \eg 100M allocations for fresh \vs 100 allocations for reuse across all experiments.
     1647While allocation reduction is huge, data copying dominates the cost, so the lines are still reasonably close together.
     1648
     1649
     1650\subsubsection{\CFA's Sharing Mode}
     1651
     1652This comparison is the same as the last one, except the \CFA implementation is using sharing mode.
     1653Hence, both \CFA's fresh and reuse versions have no memory allocations, and as before, only for reuse does \CC have no memory allocations.
     1654\VRef[Figure]{fig:string-graph-peq-sharing} shows the resulting performance.
     1655For fresh at append lengths 5 and above, \CFA is now closer to the \CC reuse performance, because of removing the dynamic allocations.
     1656However, for reuse, \CFA has slowed down slightly, to performance matching the new fresh version, as the two versions are now implemented virtually the same.
     1657The reason for the \CFA reuse slow-down is the overhead of managing the sharing scheme (primarily maintaining the list of handles), without gaining any benefit.
     1658
     1659\begin{comment}
     1660FIND A HOME!!!
     1661The potential benefits of the sharing scheme do not give \CFA an edge over \CC when appending onto a reused string, though the first one helps \CFA win at going onto a fresh string.  These abilities are:
     1662\begin{itemize}
     1663\item
     1664To grow a text allocation repeatedly without copying it elsewhere.
     1665This ability is enabled by \CFA's most-recently modified string being located immediately before the text buffer's \emph{shared} bump-pointer area, \ie often a very large greenfield, relative to the \emph{individual} string being grown.
     1666With \CC-reuse, this benefit is already reaped by the user's reuse of a pre-stretched allocation.
     1667Yet \CC-fresh pays the higher cost because its room to grow for free is at most a constant times the original string's length.
     1668\item
     1669To share an individual text allocation across multiple related strings.
     1670This ability is not applicable to appending with @+=@.
     1671It in play in [xref sub-experiment pta] and [xref experiment pbv].
     1672\item
     1673To share a text arena across unrelated strings, sourcing disparate allocations from a common place.
     1674That is, always allocating from a bump pointer, and never maintaining free lists.
     1675This ability is not relevant to running any append scenario on \CFA with sharing, because appending modifies an existing allocation and is not driving several allocations.
     1676This ability is assessed in [xref experiment allocn].
     1677\end{itemize}
     1678This cost, of slowing down append-with-reuse, is \CFA paying the piper for other scenarios done well.
     1679\CFA prioritizes the fresh use case because it is more natural.
     1680The \emph{user-invoked} reuse scheme is an unnatural programming act because it deliberately misuses lexical scope: a variable (@accum@) gets its lifetime extended beyond the scope in which it is used.
     1681
     1682A \CFA user needing the best performance on an append scenario can still access the \CC-like speed by invoking noshare.
     1683This (indirect) resource management is memory-safe, as compared to that required in \CC to use @string&@, where knowledge of another string's lifetime comes into play.
     1684This abstraction opt-out is also different from invoking the LL API-level option.
     1685In fact, these considerations are orthogonal.
     1686But the key difference is that invoking the LL API would be a temporary measure, to use a workaround of a known \CFA language issue; choosing to exempt a string from sharing is a permanent act of program tuning.
     1687Beyond these comparisons, opting for noshare actually provides program ``eye candy,'' indicating that under-the-hood thinking is becoming relevant here.
     1688\end{comment}
     1689
     1690
     1691\subsubsection{Misusing Concatenation}
     1692
     1693A further pitfall occurs writing the apparently equivalent @x = x + y@ \vs @x += y@.
    16601694For numeric types, the generated code is equivalent, giving identical performance.
    16611695However, for string types there can be a significant difference.
    1662 This pitfall is a particularly likely hazard for beginners.
     1696This pitfall is a particularly likely for beginners.
    16631697
    16641698In earlier experiments, the choice of \CFA API among HL and LL had no impact on the functionality being tested.
    … …  
    17081742\end{tabular}
    17091743\end{cquote}
    1710 Note that this ``Goal'' code functions today in HL.
     1744Note, the goal code functions today in HL but with slower performance.
    17111745
    17121746\begin{figure}
    17131747\centering
    1714         \includegraphics{string-graph-pta-sharing.pdf}
     1748        \includegraphics{plot-string-pta-sharing.pdf}
    17151749%       \includegraphics[width=\textwidth]{string-graph-pta-sharing.png}
    1716         \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}.}
     1750        \caption{CFA's low overhead for misusing concatenation.  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}.}
    17171751        \label{fig:string-graph-pta-sharing}
    17181752\end{figure}
    17191753
    1720 \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.
     1754\VRef[Figure]{fig:string-graph-pta-sharing} gives the outcome, where the Y-axis is log scale because of the large differences.
     1755The STL's penalty is $8 \times$ while \CFA's is only $2 \times$, averaged across the cases shown here.
    17211756Moreover, the STL's gap increases with string size, while \CFA's converges.
    17221757So again, \CFA helps users who just want to treat strings as values, and not think about the resource management under the covers.
    17231758
    1724 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.
    1725 
    1726 
    1727 \subsection{Test: Pass argument}
     1759While not a design goal, and not graphed, \CFA in STL-emulation mode outperformed STL in this case.
     1760User-managed allocation reuse did not affect either implementation in this case; only ``fresh'' results are shown.
     1761
     1762
     1763\subsection{Test: Pass Argument}
    17281764
    17291765STL has a penalty for passing a string by value, which forces users to think about memory management when communicating values with a function.
    1730 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.
     1766The 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 thinking this way, while \CFA does not.
    17311767This test illustrates a main advantage of the \CFA sharing algorithm (in one case).
    1732 It shows STL's small-string optimization providing a successful mitigation (in the other case).
     1768It shows STL's SSO providing a successful mitigation (in the other case).
    17331769
    17341770The basic operation considered is:
    … …  
    17491785
    17501786}
    1751 START_TIMER
    1752 for ( i; ... ) {
    1753         helper( corpus[ f(i) ] ); // imported from char * previously
    1754         COUNT_ONE_OP_DONE
     1787for ( ... ) { // loop for duration
     1788        helper( corpus[ f( i ) ] );
     1789        count += 1;
    17551790}
    1756 STOP_TIMER
    17571791\end{cfa}
    17581792&
    … …  
    17611795        string_res q = { qref, COPY_VALUE };
    17621796}
    1763 // rest same, elided
    1764 
    1765 
    1766 
    1767 
    1768 
    1769 \end{cfa}
    1770 \end{tabular}
    1771 \end{cquote}
    1772 The Goal (HL) version gives the simplest sketch of the test harness.
    1773 It uses a single level of looping.
    1774 Each iteration uses a corpus item as the argument to a function call.
     1797
     1798
     1799
     1800
     1801\end{cfa}
     1802\end{tabular}
     1803\end{cquote}
     1804The goal (HL) version gives the modified test harness, with a single loop.
     1805Each iteration uses a corpus item as the argument to the function call.
    17751806These corpus items were imported to the string heap before beginning the timed run.
    1776 
    17771807
    17781808\begin{figure}
    17791809\centering
    1780         \includegraphics{string-graph-pbv.pdf}
     1810        \includegraphics{plot-string-pbv.pdf}
    17811811%       \includegraphics[width=\textwidth]{string-graph-pbv.png}
     1812        \begin{tabularx}{\linewidth}{>{\centering\arraybackslash}X >{\centering\arraybackslash}X} (a) & (b) \end{tabularx}
    17821813        \caption{Average time per iteration (lower is better) with one call to a function that takes a by-value string argument, comparing \CFA (having implicit sharing activated) with STL.
    1783 (a) With \emph{Varying-from-1} corpus construction, in which the STL-only benefit of small-string optimization occurs, in varying degrees, at all string sizes.
    1784 (b) With \emph{Fixed-size} corpus construction, in which this benefit applies exactly to strings with length below 16.
    1785 [TODO: show version (b)]}
     1814(a) With \emph{Varying-from-1} corpus construction, in which the STL-only benefit of SSO optimization occurs, in varying degrees, at all string sizes.
     1815(b) With \emph{Fixed-size} corpus construction, in which this benefit applies exactly to strings with length below 16.}
    17861816        \label{fig:string-graph-pbv}
    17871817\end{figure}
    17881818
    1789 
    17901819\VRef[Figure]{fig:string-graph-pbv} shows the costs for calling a function that receives a string argument by value.
    1791 STL's performance worsens as string length increases, while \CFA has the same performance at all sizes.
    1792 
     1820STL's performance worsens uniformly as string length increases, while \CFA has the same performance at all sizes.
     1821Although the STL is better than \CFA until string length 10 because of the SSO.
    17931822While improved, the \CFA cost to pass a string is still nontrivial.
    17941823The contributor is adding and removing the callee's string handle from the global list.
    1795 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.
    1796 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.
    1797 \PAB{Need to check that.  Expecting copying to dominate.}
     1824This cost is $1.5 \times$ to $2 \times$ over STL's when SSO applies, but is avoidable once \CFA realizes this optimization.
     1825At the larger sizes, the STL runs more than $3 \times$ slower, because it has to allocation/deallocate storage for the parameter and copy the argument string to the parameter.
     1826If the \CC string is passed by reference, the results are better and flat across string lengths like \CFA.
    17981827
    17991828
    … …  
    18051834
    18061835A 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.
    1807 The sppedup happens because GC is able to use its collection time to move objects.
    1808 (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.
     1836The speedup happens because GC is able to use its collection time to move objects.
     1837(In the case of the mini-allocator powering the \CFA string library, objects are runs of text.)
     1838Moving objects lets fresh allocations consume from a large contiguous store of available memory; the ``bump pointer'' bookkeeping for such a scheme is very light.
    18091839A 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.
    18101840
    … …  
    18621892\begin{figure}
    18631893\centering
    1864   \includegraphics{string-graph-allocn.pdf}
     1894  \includegraphics{plot-string-allocn.pdf}
    18651895% \includegraphics[width=\textwidth]{string-graph-allocn.png}
    18661896  \caption{Space and time performance, under varying fraction-live targets, for the five string lengths shown, at \emph{Fixed-size} corpus construction.
Note: See TracChangeset for help on using the changeset viewer.