source: doc/theses/mike_brooks_MMath/string.tex@ c824afd

\chapter{String}

\vspace*{-20pt}
This chapter presents my work on designing and building a modern string type in \CFA.
The discussion starts with an overview of the string API, then a number of interesting string problems, followed by how these issues are resolved in this work.


\section{String Operations}

% https://en.wikipedia.org/wiki/Comparison_of_programming_languages_(string_functions)

\VRef[Figure]{f:StrApiCompare} shows a general comparison of string APIs for C, \CC, Java and \CFA.
It provides a classic ``cheat sheet'', summarizing the names of the most-common closely-equivalent operations.
The over-arching commonality is that operations work on groups of characters for assigning, copying, scanning, and updating.

\begin{figure}[h]
\begin{cquote}
\begin{tabular}{@{}l|l|l|l@{}}
C @char [ ]@                    & \CC @string@                  & Java @String@ & \CFA @string@ \\
\hline
@strcpy@, @strncpy@             & @=@                                   & @=@                   & @=@   \\
@strcat@, @strncat@             & @+@, @+=@                             & @+@, @+=@             & @+@, @+=@     \\
@strcmp@, @strncmp@             & @==@, @!=@, @<@, @<=@, @>@, @>=@
                                                                                                & @equals@, @compareTo@
                                                                                                                                & @==@, @!=@, @<@, @<=@, @>@, @>=@ \\
@strlen@                                & @length@, @size@              & @length@              & @size@        \\
@[ ]@                                   & @[ ]@                                 & @charAt@              & @[ ]@ \\
@strncpy@                               & @substr@                              & @substring@   & @( )@, on RHS of @=@  \\
@strncpy@                               & @replace@                             & @replace@             & @( )@, on LHS of @=@ \\
@strstr@                                & @find@                                & @indexOf@             & @find@ \\
@strcspn@                               & @find_first_of@               & @matches@             & @exclude@ \\
@strspn@                                & @find_first_not_of@   & @matches@             & @include@ \\
N/A                                             & @c_str@, @data@               & N/A                   & @strcpy@, @strncpy@ \\
\end{tabular}
\end{cquote}
\caption{Language comparison of string API}
\label{f:StrApiCompare}
\end{figure}

As mentioned in \VRef{s:String}, a C string uses null termination rather than a length, which leads to explicit storage management;
hence, most of its group operations are error prone and expensive due to copying.
Most high-level string libraries use a separate length field and specialized storage management to implement group operations.
Interestingly, \CC strings retain null termination in case it is needed to interface with C library functions.
\begin{cfa}
int open( @const char * pathname@, int flags );
string fname{ "test.cc" );
open( fname.@c_str()@, O_RDONLY );              // null terminated value of string
\end{cfa}
Here, the \CC @c_str@ function does not create a new null-terminated C string from the \CC string, as that requires passing ownership of the C string to the caller for eventual deletion.\footnote{
C functions like \lstinline{strdup} do return allocated storage that must be freed by the caller.}
% Instead, each \CC string is null terminated just in case it might be needed for this purpose.
Providing this backwards compatibility with C has a ubiquitous performance and storage cost.


\section{\CFA \lstinline{string} Type}
\label{s:stringType}

The \CFA string type is for manipulation of dynamically-sized character-strings versus C @char *@ type for manipulation of statically-sized null-terminated character-strings.
Therefore, the amount of storage for a \CFA string changes dynamically at runtime to fit the string size, whereas the amount of storage for a C string is fixed at compile time.
As a result, a @string@ declaration does not specify a maximum length, where a C string array does.
For \CFA, as a @string@ dynamically grows and shrinks in size, so does its underlying storage.
For C, as a string dynamically grows and shrinks in size, its underlying storage does not.
The maximum storage for a \CFA @string@ value is @size_t@ characters, which is $2^{32}$ or $2^{64}$ respectively.
A \CFA string manages its length separately from the string, so there is no null (@'\0'@) terminating value at the end of a string value.
Hence, a \CFA string cannot be passed to a C string manipulation function, such as @strcat@.
Like C strings, characters in a @string@ are numbered from the left starting at 0 (because subscripting is zero-origin), and in \CFA numbered from the right starting at -1.
\begin{cquote}
\rm
\begin{tabular}{@{}rrrrll@{}}
\small\tt "a & \small\tt b & \small\tt c & \small\tt d & \small\tt e" \\
0 & 1 & 2 & 3 & 4 & left to right index \\
-5 & -4 & -3 & -2 & -1 & right to left index
\end{tabular}
\end{cquote}
The following operations manipulate an instance of type @string@, where the discussion assumes the following declarations.
\begin{cfa}
#include @<string.hfa>@
@string@ s = "abcde", name = "MIKE", digit = "0123456789";
const char cs[$\,$] = "abc";
int i;
\end{cfa}
Note, the include file @<string.hfa>@ to access type @string@.


\subsection{Implicit String Conversions}

The ability to convert from internal (machine) to external (human) format is useful in situations other than I/O.
Hence, the basic types @char@, @char *@, @int@, @double@, @_Complex@, including any signness and size variations, implicitly convert to type @string@ (as in Java).
\begin{cquote}
\setlength{\tabcolsep}{10pt}
\begin{tabular}{@{}llll@{}}
\begin{cfa}
string s = 5;
s = 'x';
s = "abc";
s = 42hh;               /* signed char */
s = 42h;                /* short int */
s = 0xff;
\end{cfa}
&
\begin{cfa}
"5"
"x"
"abc"
"42"
"42"
"255"
\end{cfa}
&
\begin{cfa}
s = (ssize_t)MIN;
s = (size_t)MAX;
s = 5.5;
s = 5.5L;
s = 5.5+3.4i;
s = 5.5L+3.4Li;
\end{cfa}
&
\begin{cfa}
"-9223372036854775808"
"18446744073709551615"
"5.5"
"5.5"
"5.5+3.4i"
"5.5+3.4i"
\end{cfa}
\end{tabular}
\end{cquote}
Conversions can be explicitly specified using a compound literal.
\begin{cfa}
s = (string){ 5 };    s = (string){ "abc" };    s = (string){ 5.5 };
\end{cfa}

Conversions from @string@ to @char *@ attempt to be safe.
The overloaded @strncpy@ function is safe, if the length of the C string is correct.
The assignment operator and constructor both allocate the buffer and return its address, meaning the programmer must free it.
Note, a C string is always null terminated, implying storage is always necessary for the null.
\begin{cquote}
\begin{tabular}{@{}ll@{}}
\begin{cfa}
string s = "abcde";
char cs[4];
strncpy( cs, s, sizeof(cs) );
char * cp = s;            // ownership
delete( cp );
cp = s + ' ' + s;       // ownership
delete( cp );
\end{cfa}
&
\begin{cfa}


"abc\0", in place
"abcde\0", malloc

"abcde abcde\0", malloc

\end{cfa}
\end{tabular}
\end{cquote}


\subsection{Length}

The @len@ operation (short for @strlen@) returns the length of a C (not including the terminating null) or \CFA string.
For compatibility, an overloaded @strlen@ works with \CFA strings.
\begin{cquote}
\begin{tabular}{@{}ll@{}}
\begin{cfa}
i = len( "" );
i = len( "abc" );
i = len( cs );
i = strlen( cs );
i = len( name );
i = strlen( name );
\end{cfa}
&
\begin{cfa}
0
3
3
3
4
4
\end{cfa}
\end{tabular}
\end{cquote}


\subsection{Comparison Operators}

The binary relational, @<@, @<=@, @>@, @>=@, and equality, @==@, @!=@, operators compare \CFA strings using lexicographical ordering, where longer strings are greater than shorter strings.
In C, these operators compare the C string pointer not its value, which does not match programmer expectation.
C strings use function @strcmp@ to lexicographically compare the string value.
Java has the same issue with @==@ (reference) and @.equals@ (value) comparison.


\subsection{Concatenation}

The binary operators @+@ and @+=@ concatenate C @char@, @char *@ and \CFA strings, creating the sum of the characters.
\begin{cquote}
\setlength{\tabcolsep}{5pt}
\begin{tabular}{@{}ll|ll|ll@{}}
\begin{cfa}
s = "";
s = 'a' + 'b';
s = 'a' + "b";
s = "a" + 'b';
s = "a" + "b";
\end{cfa}
&
\begin{cfa}

"ab"
"ab"
"ab"
"ab"
\end{cfa}
&
\begin{cfa}
s = "";
s = 'a' + 'b' + s;
s = 'a' + 'b' + s;
s = 'a' + "b" + s;
s = "a" + 'b' + s;
\end{cfa}
&
\begin{cfa}

"ab"
"abab"
"ababab"
"abababab"
\end{cfa}
&
\begin{cfa}
s = "";
s = s + 'a' + 'b';
s = s + 'a' + "b";
s = s + "a" + 'b';
s = s + "a" + "b";
\end{cfa}
&
\begin{cfa}

"ab"
"abab"
"ababab"
"abababab"
\end{cfa}
\end{tabular}
\end{cquote}
However, including @<string.hfa>@ can result in ambiguous uses of the overloaded @+@ operator.\footnote{Combining multiple packages in any programming language can result in name clashes or ambiguities.}
For example, subtracting characters or pointers has valid use-cases:
\begin{cfa}
ch - '0'        $\C[2in]{// find character offset}$
cs - cs2;       $\C{// find pointer offset}\CRT$
\end{cfa}
addition is less obvious
\begin{cfa}
ch + 'b'        $\C[2in]{// add character values}$
cs + 'a';       $\C{// move pointer cs['a']}\CRT$
\end{cfa}
There are legitimate use cases for arithmetic with @signed@/@unsigned@ characters (bytes), and these types are treated differently from @char@ in \CC and \CFA.
However, backwards compatibility makes it impossible to restrict or remove addition on type @char@.
Similarly, it is impossible to restrict or remove addition on type @char *@ because (unfortunately) it is subscripting: @cs + 'a'@ implies @cs['a']@ or @'a'[cs]@.

The prior \CFA concatenation examples show complex mixed-mode interactions among @char@, @char *@, and @string@ constants work correctly (@string@ variables are the same).
The reason is that the \CFA type-system handles this kind of overloading well using the left-hand assignment-type and complex conversion costs.
Hence, the type system correctly handles all uses of addition (explicit or implicit) for @char *@.
\begin{cfa}
printf( "%s %s %s %c %c\n", "abc", cs, cs + 3, cs['a'], 'a'[cs] );
\end{cfa}
Only @char@ addition can result in ambiguities, and only when there is no left-hand information.
\begin{cfa}
ch = ch + 'b';          $\C[2in]{// LHS disambiguate, add character values}$
s = 'a' + 'b';          $\C{// LHS disambiguate, concatenate characters}$
printf( "%c\n", @'a' + 'b'@ ); $\C{// no LHS information, ambiguous}$
printf( "%c\n", @(return char)@('a' + 'b') ); $\C{// disambiguate with ascription cast}\CRT$
\end{cfa}
The ascription cast, @(return T)@, disambiguates by stating a (LHS) type to use during expression resolution (not a conversion).
Fortunately, character addition without LHS information is rare in C/\CFA programs, so repurposing the operator @+@ for @string@ types is not a problem.
Note, other programming languages that repurpose @+@ for concatenation, can have similar ambiguity issues.

Interestingly, \CC cannot support this generality because it does not use the left-hand side of assignment in expression resolution.
While it can special case some combinations:
\begin{c++}
s = 'a' + s; $\C[2in]{// compiles in C++}$
s = "a" + s;
\end{c++}
it cannot generalize to any number of steps:
\begin{c++}
s = 'a' + 'b' + s; $\C{// does not compile in C++}\CRT$
s = "a" + "b" + s;
\end{c++}


\subsection{Repetition}

The binary operators @*@ and @*=@ repeat a string $N$ times.
If $N = 0$, a zero length string, @""@, is returned.
\begin{cquote}
\begin{tabular}{@{}ll@{}}
\begin{cfa}
s = 'x' * 0;
s = 'x' * 3;
s = "abc" * 3;
s = ("MIKE" + ' ') * 3;
\end{cfa}
&
\begin{cfa}
""
"xxx"
"abcabcabc"
"MIKE MIKE MIKE "
\end{cfa}
\end{tabular}
\end{cquote}
Like concatenation, there is a potential ambiguity with multiplication of characters;
multiplication of pointers does not exist in C.
\begin{cfa}
ch = ch * 3;            $\C[2in]{// LHS disambiguate, multiply character value}$
s = 'a' * 3;            $\C{// LHS disambiguate, concatenate characters}$
printf( "%c\n", @'a' * 3@ ); $\C{// no LHS information, ambiguous}$
printf( "%c\n", @(return char)@('a' * 3) ); $\C{// disambiguate with ascription cast}\CRT$
\end{cfa}
Fortunately, character multiplication without LHS information is even rarer than addition, so repurposing the operator @*@ for @string@ types is not a problem.


\subsection{Substring}

The substring operation returns a subset of a string starting at a position in the string and traversing a length, or matching a pattern string.
\begin{cquote}
\setlength{\tabcolsep}{8pt}
\begin{tabular}{@{}ll|ll@{}}
\multicolumn{2}{@{}c}{\textbf{length}} & \multicolumn{2}{c@{}}{\textbf{pattern}} \\
\multicolumn{4}{@{}l}{\lstinline{string name = "PETER"}} \\
\begin{cfa}
s = name( 0, 4 );
s = name( 1, 4 );
s = name( 2, 4 );
s = name( 4, -2 );
s = name( 8, 2 );
s = name( 0, -2 );
s = name( -1, -2 );
s = name( -3 );
\end{cfa}
&
\begin{cfa}
"PETE"
"ETER"
"TER"   // clip length to 3
"ER"
""                 // clip, beyond right
""                 // clip, beyond left
"ER"
"TER"   // to end of string
\end{cfa}
&
\begin{cfa}
s = name( "ET" );
s = name( "WW" );






\end{cfa}
&
\begin{cfa}
"ET"
""  // does not occur






\end{cfa}
\end{tabular}
\end{cquote}
For the length form, a negative starting position is a specification from the right end of the string.
A negative length means that characters are selected in the opposite (right to left) direction from the starting position.
If the substring request extends beyond the beginning or end of the string, it is clipped (shortened) to the bounds of the string.
If the substring request is completely outside of the original string, a null string is returned.
For the pattern-form, it returns the pattern string if the pattern matches or a null string if the pattern does not match.
The usefulness of this mechanism is discussed next.

The substring operation can appear on the left side of assignment, where it defines a replacement substring.
The length of the right string may be shorter, the same, or longer than the length of left string.
Hence, the left string may decrease, stay the same, or increase in length.
\begin{cquote}
\begin{tabular}{@{}ll@{}}
\begin{cfa}[escapechar={}]
digit( 3, 3 ) = "";
digit( 4, 3 ) = "xyz";
digit( 7, 0 ) = "***";
digit(-4, 3 ) = "$$$";
digit( 5 ) = "LLL";
\end{cfa}
&
\begin{cfa}[escapechar={}]
"0126789"
"0126xyz"
"0126xyz"
"012$$$z"
"012$$LLL"
\end{cfa}
\end{tabular}
\end{cquote}
Here, substring pattern matching is useful on the left-hand side of assignment.
\begin{cquote}
\begin{tabular}{@{}ll@{}}
\begin{cfa}[escapechar={}]
digit( "$$" ) = "345";
digit( "LLL") = "6789";
\end{cfa}
&
\begin{cfa}
"012345LLL"
"0123456789"
\end{cfa}
\end{tabular}
\end{cquote}
Supporting a regular-expression pattern is a possible extension.

The replace operation extends substring to substitute all occurrences.
\begin{cquote}
\begin{tabular}{@{}ll@{}}
\begin{cfa}
s = replace( "PETER", "E", "XX" );
s = replace( "PETER", "ET", "XX" );
s = replace( "PETER", "W", "XX" );
\end{cfa}
&
\begin{cfa}
"PXXTXXR"
"PXXER"
"PETER"
\end{cfa}
\end{tabular}
\end{cquote}
The replacement is done left-to-right and substituted text is not examined for replacement.


\subsection{Searching}

The @find@ operation returns the position of the first occurrence of a key in a string.
If the key does not appear in the string, the length of the string is returned.
\begin{cquote}
\begin{tabular}{@{}ll@{}}
\begin{cfa}
i = find( digit, '3' );
i = find( digit, "45" );
i = find( digit, "abc" );
\end{cfa}
&
\begin{cfa}
3
4
10
\end{cfa}
\end{tabular}
\end{cquote}

A character-class operation indicates if a string is composed completely of a particular class of characters, \eg, alphabetic, numeric, vowels, \etc.
\begin{cquote}
\begin{tabular}{@{}ll@{}}
\begin{cfa}
charclass vowels{ "aeiouy" };
i = include( "aaeiuyoo", vowels );
i = include( "aabiuyoo", vowels );
\end{cfa}
&
\begin{cfa}

8  // compliant
2  // b non-compliant
\end{cfa}
\end{tabular}
\end{cquote}
@vowels@ defines a character class and function @include@ checks if all characters in the string appear in the class (compliance).
The position of the last character is returned if the string is compliant or the position of the first non-compliant character.
There is no relationship between the order of characters in the two strings.
Function @exclude@ is the reverse of @include@, checking if all characters in the string are excluded from the class (compliance).
\begin{cquote}
\begin{tabular}{@{}ll@{}}
\begin{cfa}
i = exclude( "cdbfghmk", vowels );
i = exclude( "cdyfghmk", vowels );
\end{cfa}
&
\begin{cfa}
8  // compliant
2  // y non-compliant
\end{cfa}
\end{tabular}
\end{cquote}
Both forms can return the longest substring of compliant characters.
\begin{cquote}
\begin{tabular}{@{}ll@{}}
\begin{cfa}
s = include( "aaeiuyoo", vowels );
s = include( "aabiuyoo", vowels );
s = exclude( "cdbfghmk", vowels );
s = exclude( "cdyfghmk", vowels );
\end{cfa}
&
\begin{cfa}
"aaeiuyoo"
"aa"
"cdbfghmk"
"cd"
\end{cfa}
\end{tabular}
\end{cquote}

There are also versions of @include@ and @exclude@, returning a position or string, taking a validation function, like one of the C character-class functions.\footnote{It is part of the hereditary of C that these function take and return an \lstinline{int} rather than a \lstinline{bool}, which affects the function type.}
\begin{cquote}
\begin{tabular}{@{}ll@{}}
\begin{cfa}
i = include( "1FeC34aB", @isxdigit@ );
i = include( ".,;'!\"", @ispunct@ );
i = include( "XXXx", @isupper@ );
\end{cfa}
&
\begin{cfa}
8   // compliant
6   // compliant
3   // non-compliant
\end{cfa}
\end{tabular}
\end{cquote}
These operations perform an \emph{apply} of the validation function to each character, where the function returns a boolean indicating a stopping condition for the search.
The position of the last character is returned if the string is compliant or the position of the first non-compliant character.

The translate operation returns a string with each character transformed by one of the C character transformation functions.
\begin{cquote}
\begin{tabular}{@{}ll@{}}
\begin{cfa}
s = translate( "abc", @toupper@ );
s = translate( "ABC", @tolower@ );
int tospace( int c ) { return isspace( c ) ? ' ' : c; }
s = translate( "X X\tX\nX", @tospace@ );
\end{cfa}
&
\begin{cfa}
"ABC"
"abc"

"X X X X"
\end{cfa}
\end{tabular}
\end{cquote}


\subsection{Returning N on Search Failure}

Some of the prior string operations are composite, \eg string operations returning the longest substring of compliant characters (@include@) are built using a search and then substring the appropriate text.
However, string search can fail, which is reported as an alternate search outcome, possibly an exception.
Many string libraries use a return code to indicate search failure, with a failure value of @0@ or @-1@ (PL/I~\cite{PLI} returns @0@).
This semantics leads to an awkward pattern, which can appear many times in a string library or user code.
\begin{cfa}
i = exclude( s, alpha );
if ( i != -1 ) return s( 0, i );
else return "";
\end{cfa}
The problem is that substring does the wrong thing or fails with the failure return-code in most string libraries, so it has to be special cased.

\CFA adopts a return code but the failure value is taken from the index-of function in APL~\cite{apl}, which returns the length of the target string $N$ (or $N+1$ for 1 origin).
This semantics allows many search and substring functions to be written without conditions, \eg:
\begin{cfa}
string include( const string & s, int (*f)( int ) ) { return @s( 0, include( s, f ) )@; }
string exclude( const string & s, int (*f)( int ) ) { return @s( 0, exclude( s, f ) )@; }
\end{cfa}
In string systems with an $O(1)$ length operator, checking for failure is low cost.
\begin{cfa}
if ( include( line, alpha ) == len( line ) ) ... // not found, 0 origin
\end{cfa}
\VRef[Figure]{f:ExtractingWordsText} compares \CC and \CFA string code for extracting words from a line of text, repeatedly removing non-word text and then a word until the line is empty.
The \CFA code is simpler solely because of the choice for indicating search failure.
(A simplification of the \CC version is to concatenate a sentinel character at the end of the line so the call to @find_first_not_of@ does not fail.)

\begin{figure}
\begin{cquote}
\begin{tabular}{@{}ll@{}}
\multicolumn{1}{c}{\textbf{\CC}} & \multicolumn{1}{c}{\textbf{\CFA}} \\
\begin{cfa}
for ( ;; ) {
        string::size_type posn = line.find_first_of( alpha );
  if ( posn == string::npos ) break;
        line = line.substr( posn );
        posn = line.find_first_not_of( alpha );
        if ( posn != string::npos ) {
                cout << line.substr( 0, posn ) << endl;
                line = line.substr( posn );
        } else {
                cout << line << endl;
                line = "";
        }
}
\end{cfa}
&
\begin{cfa}
for () {
        size_t posn = exclude( line, alpha );
  if ( posn == len( line ) ) break;
        line = line( posn );
        posn = include( line, alpha );

        sout | line( 0, posn );
        line = line( posn );




}
\end{cfa}
\end{tabular}
\end{cquote}
\caption{Extracting Words from Line of Text}
\label{f:ExtractingWordsText}
\end{figure}


\subsection{C Compatibility}

To ease conversion from C to \CFA, \CFA provides companion C @string@ functions.
Hence, it is possible to convert a block of C string operations to \CFA strings just by changing the type @char *@ to @string@.
\begin{cquote}
\begin{tabular}{@{}ll@{}}
\multicolumn{2}{@{}l@{}}{\lstinline{char s[32];   // changing s's type to string works}} \\
\begin{cfa}
strlen( s );
strnlen( s, 3 );
strcmp( s, "abc" );
strncmp( s, "abc", 3 );
\end{cfa}
&
\begin{cfa}
strcpy( s, "abc" );
strncpy( s, "abcdef", 3 );
strcat( s, "xyz" );
strncat( s, "uvwxyz", 3 );
\end{cfa}
\end{tabular}
\end{cquote}
However, the conversion fails with I/O because @printf@ cannot print a @string@ using format code @%s@ because \CFA strings are not null terminated.
Nevertheless, this capability does provide a useful starting point for conversion to safer \CFA strings.


\subsection{I/O Operators}

The ability to input and output a string is as essential as for any other type.
The goal for character I/O is to work with groups rather than individual characters.
A comparison with \CC string I/O is presented as a counterpoint to \CFA string I/O.

The \CC output @<<@ and input @>>@ operators are defined on type @string@.
\CC output for @char@, @char *@, and @string@ are similar.
The \CC manipulators are @setw@, and its associated width controls @left@, @right@ and @setfill@.
\begin{cquote}
\begin{tabular}{@{}ll@{}}
\begin{c++}
string s = "abc";
cout << setw(10) << left << setfill( 'x' ) << s << endl;
\end{c++}
&
\begin{c++}

"abcxxxxxxx"
\end{c++}
\end{tabular}
\end{cquote}

The \CFA input/output operator @|@ is defined on type @string@.
\CFA output for @char@, @char *@, and @string@ are similar.
The \CFA manipulators are @bin@, @oct@, @hex@, @wd@, and its associated width control and @left@.
\begin{cquote}
\begin{tabular}{@{}ll@{}}
\begin{cfa}
string s = "abc";
sout | bin( s ) | nl
           | oct( s ) | nl
           | hex( s ) | nl
           | wd( 10, s ) | nl
           | wd( 10, 2, s ) | nl
           | left( wd( 10, s ) );
\end{cfa}
&
\begin{cfa}

"0b1100001 0b1100010 0b1100011"
"0141 0142 0143"
"0x61 0x62 0x63"
"       abc"
"        ab"
"abc       "
\end{cfa}
\end{tabular}
\end{cquote}
\CC @setfill@ is not considered an important string manipulator.

\CC input matching for @char@, @char *@, and @string@ are similar, where \emph{all} input characters are read from the current point in the input stream to the end of the type size, format width, whitespace, end of line (@'\n'@), or end of file.
The \CC manipulator is @setw@ to restrict the size.
Reading into a @char@ is safe as the size is 1, @char *@ is unsafe without using @setw@ to constraint the length (which includes @'\0'@), @string@ is safe as its grows dynamically as characters are read.
\begin{cquote}
\begin{tabular}{@{}ll@{}}
\begin{c++}
char ch, c[10];
string s;
cin >> ch >> setw( 5 ) >> c  >> s;
@abcde   fg@
\end{c++}
&
\begin{c++}


'a' "bcde" "fg"

\end{c++}
\end{tabular}
\end{cquote}
Input text can be \emph{gulped}, including whitespace, from the current point to an arbitrary delimiter character using @getline@.
\begin{cquote}
\setlength{\tabcolsep}{10pt}
\begin{tabular}{@{}ll@{}}
\multicolumn{1}{c}{\textbf{\CC}} & \multicolumn{1}{c}{\textbf{\CFA}} \\
\begin{cfa}
string s1, s2, s3;
getline( cin, s1, 'a' );
getline( cin, s2, 'w' );
getline( cin, s3 );
cout << s1 << ' ' << s2 << ' ' << s3 << endl;
@bbbad ddwxyz@
\end{cfa}
&
\begin{cfa}

sin | getline( s1, 'a' )
        | getline( s2, 'w' )
        | getline( s3 );
sout | s1 | s2 | s3;       "bbb" "d dd" "xyz"

\end{cfa}
\end{tabular}

\end{cquote}

The \CFA philosophy for input is that, for every constant type in C, these constants should be usable as input.
For example, the complex constant @3.5+4.1i@ can appear as input to a complex variable.
\CFA input matching for @char@, @char *@, and @string@ are similar.
C-strings may only be read with a width field, which should match the string size.
Certain input manipulators support a scanset, which is a simple regular expression from @printf@.
The \CFA manipulators for these types are @wdi@,\footnote{Due to an overloading issue in the type-resolver, the input width name must be temporarily different from the output, \lstinline{wdi} versus \lstinline{wd}.} and its associated width control and @left@, @quote@, @incl@, @excl@, and @getline@.
\begin{cquote}
\setlength{\tabcolsep}{10pt}
\begin{tabular}{@{}ll@{}}
\begin{c++}
char ch, c[10];
string s;
sin | ch | wdi( 5, c ) | s;
@abcde fg@
sin | @quote@( ch ) | @quote@( wdi( sizeof(c), c ) ) | @quote@( s, '[', ']' ) | nl;
@'a'   "bcde"      [fg]@
sin | incl( "a-zA-Z0-9 ?!&\n", s ) | nl;
@x?&000xyz TOM !.@
sin | excl( "a-zA-Z0-9 ?!&\n", s );
@<>{}{}STOP@
\end{c++}
&
\begin{c++}


'a' "bcde" "fg"

'a' "bcde" "fg"

"x?&000xyz TOM !"

"<>{}{}"

\end{c++}
\end{tabular}
\end{cquote}
Note, the ability to read in quoted strings with whitespace to match with program string constants.
The @nl@ at the end of an input ignores the rest of the line.


\subsection{Assignment}

While \VRef[Figure]{f:StrApiCompare} emphasizes cross-language similarities, it elides many specific operational differences.
For example, the \CC @replace@ function selects a substring in the target and substitutes it with the source string, which can be smaller or larger than the substring.
\CC modifies the mutable receiver object, replacing by position (zero origin) and length.
\begin{c++}
string s1 = "abcde";
s1.replace( 2, 3, "xy" );                        "abxy"
\end{c++}
Java cannot modify the receiver (immutable strings) so it returns a new string, replacing by text.
\label{p:JavaReplace}
\begin{java}
String s = "abcde";
String r = s.replace( "cde", "xy" );      "abxy"
\end{java}
Java also provides a mutable @StringBuffer@, replacing by position (zero origin) and length.
\begin{java}
StringBuffer sb = new StringBuffer( "abcde" );
sb.replace( 2, 5, "xy" );                         "abxy"
\end{java}
However, there are anomalies.
@StringBuffer@'s @substring@ returns a @String@ copy that is immutable rather than modifying the receiver.
As well, the operations are asymmetric, \eg @String@ has @replace@ by text but not replace by position and vice versa for @StringBuffer@.

More significant operational differences relate to storage management, often appearing through assignment (@target = source@), and are summarized in \VRef[Figure]{f:StrSemanticCompare}, which defines properties type abstraction, state, symmetry, and referent.
The following discussion justifies the figure's yes/no entries per language.

\begin{figure}
\setlength{\extrarowheight}{2pt}
\setlength{\tabcolsep}{5pt}
\begin{tabularx}{\textwidth}{@{}p{0.8in}XXcccc@{}}
                                        &                       &                       & \multicolumn{4}{@{}c@{}}{\underline{Supports Helpful?}} \\
                                        & Required      & Helpful       & C                     & \CC           & Java          & \CFA \\
\hline
Type Abstraction
                                        & Low-level: The string type is a varying amount of text communicated via a parameter or return.
                                                                & High-level: The string-typed relieves the user of managing memory for the text.
                                                                                        & no    & yes   & yes   & yes \\
\hline
State
                                        & \multirow{2}{2in}
                                        {Fast Initialize: The target receives the characters of the source without copying the characters, resulting in an Alias or Snapshot.}
                                                                & Alias: The target variable names the source text; changes made in either variable are visible in both.
                                                                                        & yes   & yes   & no    & yes \\
\cline{3-7}
                                        &
                                                                & Snapshot: Subsequent operations on either the source or target variable do not affect the other.
                                                                                        & no    & no    & yes   & yes \\
\hline
Symmetry
                                        & Laxed: The target's type is anything string-like; it may have a different status concerning ownership.
                                                                & Strict: The target's type is the same as the source; both strings are equivalent peers concerning ownership.
                                                                                        & N/A           & no    & yes   & yes \\
\hline
Referent
                                        & Variable-Constrained: The target can accept the entire text of the source.
                                                                & Fragment: The target can accept an arbitrary substring of the source.
                                                                                        & no    & no    & yes   & yes
\end{tabularx}

\noindent
Notes
\begin{itemize}[parsep=0pt]
\item
        All languages support Required in all criteria.
\item
        A language gets ``Supports Helpful'' in one criterion if it can do so without sacrificing the Required achievement on all other criteria.
\item
        The C ``string'' is @char *@, under the conventions of @<string.h>@. Because this type does not manage a text allocation, symmetry does not apply.
\item
        The Java @String@ class is analyzed; its @StringBuffer@ class behaves similarly to \CC.
\end{itemize}
\caption{Comparison of languages' strings, storage management perspective.}
\label{f:StrSemanticCompare}
\end{figure}

In C, these declarations are very different.
\begin{cfa}
char x[$\,$] = "abcde";
char * y = "abcde";
\end{cfa}
Both associate the declared name with the fixed, six contiguous bytes: @{'a', 'b', 'c', 'd', 'e', 0}@.
But @x@ is allocated on the stack (with values filled at the declaration), while @y@ refers to the executable's read-only data-section.
With @x@ representing an allocation, it offers information in @sizeof(x)@ that @y@ does not.
But this extra information is second-class, as it can only be used in the immediate lexical context, \ie it cannot be passed to string operations or user functions.
Only pointers to text buffers are first-class, and discussed further.
\begin{cfa}
char * s = "abcde";
char * s1 = s;  $\C[2.25in]{// alias state, N/A symmetry, variable-constrained referent}$
char * s2 = &s[1];  $\C{// alias state, N/A symmetry, variable-constrained referent}$
char * s3 = &s2[1];  $\C{// alias state, N/A symmetry, variable-constrained referent}\CRT$
printf( "%s %s %s %s\n", s, s1, s2, s3 );
$\texttt{\small abcde abcde bcde cde}$
\end{cfa}
Note, all of these aliased strings rely on the single null termination character at the end of @s@.
The issue of symmetry does not apply to a low-level API because no management of a text buffer is provided.
With the @char *@ type not managing the text storage, there is no ownership question, \ie operations on @s1@ or @s2@ never lead to their memory becoming reusable.
While @s3@ is a valid C-string that contains a proper substring of @s1@, the @s3@ technique does not constitute having a fragment referent because null termination implies the substring cannot be chosen arbitrarily; the technique works only for suffixes.

In \CC, @string@ offers a high-level abstraction.
\begin{cfa}
string s = "abcde";
string & s1 = s;  $\C[2.25in]{// alias state, lax symmetry, variable-constrained referent}$
string s2 = s;  $\C{// no fast-initialize (strict symmetry, variable-constrained referent)}$
string s3 = s.substr( 1, 2 );  $\C{// no fast-initialize (strict symmetry, fragment referent)}$
string s4 = s3.substr( 1, 1 );  $\C{// no fast-initialize (strict symmetry, fragment referent)}$
cout << s << ' ' << s1 << ' ' << s2 << ' ' << s3 << ' ' << s4 << endl;
$\texttt{\small abcde abcde abcde bc c}$
string & s5 = s.substr(2,4);  $\C{// error: cannot point to temporary}\CRT$
\end{cfa}
The @s1@ lax symmetry reflects how its validity depends on the lifetime of @s@.
It is common practice in \CC to use the @s1@-style for a by-reference function parameter.
Doing so assumes that the callee only uses the referenced string for the duration of the call, \ie no storing the parameter (as a reference) for later.
So, when the called function is a constructor, its definition typically uses an @s2@-style copy-initialization.
Exceptions to this pattern are possible, but require the programmer to assure safety where the type system does not.
The @s3@ initialization 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.
@s2@ assignment could be made fast, by reference-counting the text area and using copy-on-write, but would require an implementation upgrade.

In Java, @String@ also offers a high-level abstraction:
\begin{java}
String s = "abcde";
String s1 = s;  $\C[2.25in]{// snapshot state, strict symmetry, variable-constrained referent}$
String s2 = s.substring( 1, 3 );  $\C{// snapshot state (possible), strict symmetry, fragment referent}$
String s3 = s2.substring( 1, 2 );  $\C{// snapshot state (possible), strict symmetry, fragment referent}\CRT$
System.out.println( s + ' ' + s1 + ' ' + s2 + ' ' + s3 );
$\texttt{\small abcde abcde bc c}$
System.out.println( (s == s1) + " " + (s == s2) + " " + (s2 == s3) );
$\texttt{\small true false false}$
\end{java}
Note, Java's @substring@ takes a start and end position, rather than a start position and length.
Here, facts about Java's implicit pointers and pointer equality can over complicate the picture, and so are ignored.
Furthermore, Java's string immutability means string variables behave as simple values.
The result in @s1@ is the pointer in @s@, and their pointer equality confirm no time is spent copying characters.
With @s2@, the case for fast-copy is more subtle.
Certainly, its value is not pointer-equal to @s@, implying at least a further allocation.
But 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.
Java does not meet the aliasing requirement because immutability makes it impossible to modify.
Java's @StringBuffer@ provides aliasing (see @replace@ example on \VPageref{p:JavaReplace}), though without supporting symmetric treatment of a fragment referent, \eg @substring@ of a @StringBuffer@ is a @String@;
as a result, @StringBuffer@ scores as \CC.
The easy symmetry that the Java string enjoys is aided by Java's garbage collection; Java's @s1@ is doing effectively the operation of \CC's @s1@, though without the consequence of complicating memory management.

% former \PAB{What complex storage management is going on here?}
% answer: the variable names in the sentence were out of date; fixed

Finally, in \CFA, @string@ also offers a high-level abstraction:
\begin{cfa}
string s = "abcde";
string & s1 = s; $\C[2.25in]{// alias state, lax symmetry, variable-constrained referent}$
string s2 = s; $\C{// snapshot state, strict symmetry, variable-constrained referent}$
string s3 = s`share; $\C{// alias state, strict symmetry, variable-constrained referent}$
string s4 = s( 1, 2 ); $\C{// snapshot state, strict symmetry, fragment referent}$
string s5 = s4( 1, 1 )`share; $\C{// alias state, strict symmetry, fragment referent}\CRT$
sout | s | s1 | s2 | s3 | s4 | s5;
$\texttt{\small abcde abcde abcde abcde bc c}$
\end{cfa}
% all helpful criteria of \VRef[Figure]{f:StrSemanticCompare} are satisfied.
The \CFA string manages storage, handles all assignments, including those of fragment referents with fast initialization, provides the choice between snapshot and alias semantics, and does so symmetrically with one type (which assures text validity according to the lifecycles of the string variables).
The @s1@ case is the same in \CFA as in \CC.
But the \CFA @s2@ delivers a fast snapshot, while the \CC @s2@ does not.
\CFA offers the snapshot-vs-alias choice in @s2@-vs-@s3@ and @s4@-vs-@s5@.
Regardless of snapshot-vs-alias and fragment-vs-whole, the target is always of the same @string@ type.

% former \PAB{Need to discuss the example, as for the other languages.}
% answer: done


\subsection{Logical Overlap}

It may be unfamiliar to combine \VRef[Figure]{f:StrSemanticCompare}'s alias state and fragment referent in one API, or at the same time.
This section shows the capability in action.

\begin{comment}
The metaphor of a GUI text-editor is used to illustrate combining these features.
Most editors allow selecting a consecutive block of text (highlighted) to define an aliased substring within a document.
Typing in this area overwrites the prior text, replacing the selected text with less, same, or more text.
Importantly, the document also changes size, not just the selection.
%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.
Extend 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.
When the selected areas are independent, the semantics of the drag-and-drop are straightforward.
However, for overlapping selections, either partial or full, there are multiple useful semantics.
For example, two areas overlap at the top, or bottom, or a block at a corner, where one areas is dropped into the other.
For selecting a smaller area within a larger, and dropping the smaller area into the larger to replace it.
In both cases, meaningful semantics must be constructed or the operation precluded.
However, without this advanced capability, certain operations become multi-step, possible requiring explicit temporaries.
\end{comment}

A GUI text-editor provides a metaphor.
Selecting a block of text using the mouse defines an aliased substring within a document.
Typing in this area overwrites what was there, replacing the originally selected text with more or less text.
But the \emph{containing document} also grows or shrinks, not just the selection.
This action models assigning to an aliased substring when one string is completely contained in the other.

Extend the metaphor to a multi-user editor.
If 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.
This action models assigning to an aliased substring when the two strings do not overlap.

Logically, 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.
But, there is no need to have two separate document strings.
Even if a third selection removes all the text, both Alice's and Bob's strings remain.
The 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.

This leaves the ``Venn-diagram overlap'' cases, where Alice's and Bob's selections overlap at the top, bottom, or corner.
In this case, the selection areas are dependent, and so, changes in content and size in one may have an affect in the other.
There are multiple possible semantics for this case.
The remainder of this section shows the chosen semantics for all of the cases.

String 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).
This aliasing relationship is a \newterm{sticky property} established at initialization.
For example, here strings @s1@ and @s1a@ are in an aliasing relationship, while @s2@ is in a copy relationship.
\input{sharing1.tex}
Here, the aliasing (@`share@) causes partial changes (subscripting) to flow in both directions.
(In the following examples, note how @s1@ and @s1a@ change together, and @s2@ is independent.)
\input{sharing2.tex}
Similarly for complete changes.
\input{sharing3.tex}
Because string assignment copies the value, RHS aliasing is irrelevant.
Hence, aliasing of the LHS is unaffected.
\input{sharing4.tex}

Now, consider string @s1_mid@ being an alias in the middle of @s1@, along with @s2@, made by a copy from the middle of @s1@.
\input{sharing5.tex}
Again, @`share@ passes changes in both directions; copy does not.
As a result, the index values for the position of @b@ are 1 in the longer string @"abcd"@ and 0 in the shorter aliased string @"bc"@.
This alternate positioning also applies to subscripting.
\input{sharing6.tex}

Finally, assignment flows through the aliasing relationship without affecting its structure.
\input{sharing7.tex}
In the @"ff"@ assignment, the result is straightforward to accept because the flow direction is from contained (small) to containing (large).
The following rules explain aliasing substrings that flow in the opposite direction, large to small.

Growth and shrinkage are natural extensions, as for the text-editor analogy, where an empty substring is as real as an empty string.
\input{sharing8.tex}

Multiple portions of a string can be aliased.
% When there are several aliasing substrings at once, the text editor analogy becomes an online multi-user editor.
%I should be able to edit a paragraph in one place (changing the document's length), without my edits affecting which letters are within a mouse-selection that you had made previously, somewhere else.
\input{sharing9.tex}
When @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,

When changes happen on an aliasing substring that overlap.
\input{sharing10.tex}
Strings @s1_crs@ and @s1_mid@ overlap at character 4, @'j'@, because the substrings are 3,2 and 4,2.
When @s1_crs@'s size increases by 1, @s1_mid@'s starting location moves from 4 to 5, but the overlapping character remains, changing to @'+'@.

\PAB{TODO: finish typesetting the demo}

%\input{sharing-demo.tex}

\VRef[Figure]{f:ParameterPassing} shows similar relationships when passing the results of substring operations by reference and by value to a subprogram.
Again, notice the side-effects to other reference parameters as one is modified.

\begin{figure}
\begin{cfa}
// x, a, b, c, & d are substring results passed by reference
// e is a substring result passed by value
void test( string & x, string & a, string & b, string & c, string & d, string e ) {
\end{cfa}
\begin{cquote}
\setlength{\tabcolsep}{2pt}
\begin{tabular}{@{}ll@{}}
\begin{cfa}

        a( 0, 2 ) = "aaa";
        b( 1, 12 ) = "bbb";
        c( 4, 5 ) = "ccc";
        c = "yyy";
        d( 0, 3 ) = "ddd";
        e( 0, 3 ) = "eee";
        x = e;
}
\end{cfa}
&
\sf
\setlength{\extrarowheight}{-0.5pt}
\begin{tabular}{@{}llllll@{}}
x                                       & a             & b             & c             & d             & e             \\
@"aaaxxxxxxxxx"@        & @"aaax"@      & @"xxx"@       & @"xxxxx"@     & @"xxx"@       & @"xxx"@       \\
@"aaaxbbbxxxxxx"@       & @"aaax"@      & @"xbbb"@      & @"xxxx"@      & @"xxx"@       & @"xxx"@       \\
@"aaaxbbbxxxcccxx"@     & @"aaax"@      & @"xbbb"@      & @"xxxccc"@& @"cccxx"@ & @"xxx"@       \\
@"aaaxbbbyyyxx"@        & @"aaax"@      & @"aaab"@      & @"yyy"@       & @"xx"@        & @"xxx"@       \\
@"aaaxbbbyyyddd"@       & @"aaax"@      & @"xbbb"@      & @"yyy"@       & @"ddd"@       & @"xxx"@       \\
@"aaaxbbbyyyddd"@       & @"aaax"@      & @"xbbb"@      & @"yyy"@       & @"ddd"@       & @"eee"@       \\
@"eee"@                         & @""@  & @""@  & @""@          & @"eee"@ \\
 & \\
\end{tabular}
\end{tabular}
\end{cquote}
\begin{cfa}
int main() {
        string x = "xxxxxxxxxxx";
        test( x, x(0, 3), x(2, 3), x(4, 5), x(8, 5), x(8, 5) );
}
\end{cfa}
\caption{Parameter Passing}
\label{f:ParameterPassing}
\end{figure}


\section{Storage Management}

This section discusses issues related to storage management of strings.
Specifically, it is common for strings to logically overlap partially or completely.
\begin{cfa}
string s1 = "abcdef";
string s2 = s1; $\C{// complete overlap, s2 == "abcdef"}$
string s3 = s1.substr( 0, 3 ); $\C{// partial overlap, s3 == "abc"}$
\end{cfa}
This raises the question of how strings behave when an overlapping component is changed,
\begin{cfa}
s3[1] = 'w'; $\C{// what happens to s1 and s2?}$
\end{cfa}
which is restricted by a string's mutable or immutable property.
For example, Java's immutable strings require copy-on-write when any overlapping string changes.
Note, the notion of underlying string mutability is not specified by @const@; \eg in \CC:
\begin{cfa}
const string s1 = "abc";
\end{cfa}
@const@ applies to the @s1@ pointer to @"abc"@, and @"abc"@ is an immutable constant that is \emph{copied} into the string's storage.
Hence, @s1@ is not pointing at an immutable constant and its underlying string is mutable, unless some other designation is specified, such as Java's global immutable rule.


\subsection{General Implementation}
\label{string-general-impl}

A centrepiece of the string module is its memory manager.
The management scheme defines a shared buffer for string text.
Allocation in this buffer is always via a bump-pointer;
the buffer is compacted and/or relocated (to grow) when it fills.
A string is a smart pointer into this buffer.

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).
A few differences are noteworthy.
First, in a general purpose manager, the allocated objects may contain pointers to other objects, making the transitive reachability of these objects a crucial property.
Here, the allocations are text, so one allocation never keeps another alive.
Second, in a general purpose manager, the handle that keeps an allocation alive is a bare pointer.
For 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.

\begin{figure}
\includegraphics{memmgr-basic.pdf}
\caption{String memory-management data structures}
\label{f:memmgr-basic}
\end{figure}

\VRef[Figure]{f:memmgr-basic} shows the representation.
The heap header and text buffer define a sharing context.
Normally, one global context is appropriate for an entire program;
concurrency is discussed in \VRef{s:ControllingImplicitSharing}.
A string is a handle to a node in a linked list containing information about a string text in the buffer.
The list is doubly linked for $O(1)$ insertion and removal at any location.
Strings are ordered in the list by text start address.
The heap header maintains a next-allocation pointer, @alloc@, pointing to the last live allocation in the buffer.
No external references point into the buffer and the management procedure relocates the text allocations as needed.
A string handle references a containing string, while its string is contiguous and not null terminated.
The length sets an upper limit on the string size, but is large (4 or 8 bytes).
String handles can be allocated in the stack or heap, and represent the string variables in a program.
Normal C life-time rules apply to guarantee correctness of the string linked-list.
The 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.
% During this period, strings can vary in size dynamically.

When the text buffer fills, \ie the next new string allocation causes @alloc@ to point beyond the end of the buffer, the strings are compacted.
The linked handles define all live strings in the buffer, which indirectly defines the allocated and free space in the buffer.
The 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.
After compaction, if free storage is still less than the new string allocation, a larger text buffer is heap-allocated, the current buffer is copied into the new buffer, and the original buffer is freed.
Note, the list of string handles is structurally unaffected during a compaction;
only the text pointers in the handles are modified to new buffer locations.

Object lifecycle events are the \emph{subscription-management} triggers in such a service.
There are two fundamental string-creation functions: importing external text like a C-string or reading a string, and initialization from an existing \CFA string.
When importing, storage comes from the end of the buffer, into which the text is copied.
To maintain sorted order, the new string handle is inserted at the end of the handle list because the new text is at the end of the buffer.
When initializing from text already in the buffer, the new handle is a second reference into the original run of characters.
To maintain sorted order, the new handle's linked-list position is after the original handle.
Both string initialization styles preserve the string module's internal invariant that the linked-list order matches the buffer order.
For string destruction, handles are removed from the list.
Once the last handle using a run of buffer characters is destroyed, that buffer space is excluded from use until the next compaction.

Certain string operations result in a substring of another string.
The resulting handle is then placed in the correct sorted position in the list, possible requiring a short linear search to locate the position.
For string operations resulting in a new string, that string is allocated at the end of the buffer.
For shared-edit strings, handles that originally referenced containing locations need to see the new value at the new buffer location.
These strings are moved to appropriate locations at the end of the list \see{details in \VRef{sharing-impl}}.
For nonshared-edit strings, a containing string can be moved and the other strings can remain in the same position.
String assignment works similarly to string initialization, maintaining the invariant of linked-list order matching buffer order.

At the level of the memory manager, these modifications can always be explained as assignment and appendment.
For example, an append is an assignment into the empty substring at the end of the buffer. 
Favourable conditions allow for in-place editing: where there is room for the resulting value in the original buffer location, and where all handles referring to the original buffer location see the new value.
One notable example of favourable conditions occurs because the most recently written string is often the last in the buffer, after which a large amount of free space occurs.
Now, repeated appends (reading) can occur without copying previously accumulated characters.
However, the general case requires a new buffer allocation: where the new value does not fit in the old place, or if other handles are still using the old value.


\subsection{RAII Limitations}
\label{string-raii-limit}

Earlier work on \CFA~\cite[ch.~2]{Schluntz17} implemented object constructors and destructors for all types (basic and user defined).
A constructor is a user-defined function run implicitly \emph{after} an object's storage is allocated, and a destructor is a user-defined function run \emph{before} an object's storage is deallocated.
This feature, called Resource Acquisition Is Initialization (RAII)~\cite[p.~389]{Stroustrup94}, helps guarantee invariants for users before accessing an object and for the programming environment after an object terminates.

The purposes of these invariants goes beyond ensuring authentic values inside an object.
Invariants can also track data about managed objects in other data structures.
Reference counting is an example application of an invariant outside of the immediate data value.
With a reference-counting smart-pointer, the constructor and destructor \emph{of a pointer type} track the lifecycle of the object it points to.
Both \CC and \CFA RAII systems are powerful enough to achieve reference counting.

In general, a lifecycle function has access to an object by location, \ie constructors and destructors receive a parameter providing an object's memory address.\footnote{
Historically in \CC, the type of \lstinline[language=C++]{this} is a pointer versus a reference;
in \CFA, the first parameter of a constructor or destructor must be a reference.}
\begin{cfa}
struct S { int * ip; };
void ?{}( S & @this@ ) { this.ip = new(); } $\C[3in]{// default constructor}$
void ?{}( S & @this@, int i ) { this{}; *this.ip = i; } $\C{// initializing constructor}$
void ?{}( S & @this@, S s ) { this{ *s.ip }; } $\C{// copy constructor}$
void ^?{}( S & @this@ ) { delete( this.ip ); } $\C{// destructor}\CRT$
\end{cfa}
Such basic examples use the @this@ address only to gain access to the values being managed.
But lifecycle logic can use the address, too, \eg add the @this@ object to a collection at creation and remove it at destruction.
\begin{cfa}
// header (.hfa)
struct N { $\C[3in]{// list node}$
        // private
        inline dlink( N );
};
void ?{}( N & ); $\C{// default constructor}$
void ^?{}( N & ); $\C{// destructor}\CRT$
// implementation (.cfa)
static dlist( N ) @list_N@;
void ?{}( N & this ) { insert_last( list_N, @this@ ) }
void ^?{}( N & this ) { remove( this ); }
\end{cfa}
A module providing the @N@ (node) type can traverse @list_N@ to manipulate the objects.
Hence, declaring a @N@ 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.
Again, both \CFA and \CC support this usage style.

A third capability concerns \emph{implicitly} requested copies.
When stack-allocated objects are used as parameter and return values, a sender's version exists in one stack frame and a receiver's version exists in another.
In the parameter direction, the language's function-call handling must arrange for a copy-constructor call to happen, at a time near the control transfer into the callee. %, with the source as the caller's (sender's) version and the target as the callee's (receiver's) version.
In the return direction, the roles are reversed and the copy-constructor call happens near the return of control.
\CC supports this capability. % without qualification.
\CFA offers limited support;
simple examples work, but implicit copying does not combine successfully with other RAII capabilities.

\CC also offers move constructors and return-value optimization~\cite{RVO20}.
These features help reduce unhelpful copy-constructor calls, which, for types like the @S@ example, would lead to extra memory allocations.
\CFA does not currently have these features; adding similarly-intended features to \CFA is desirable.
However, this section is about a problem in the realization of features that \CFA already supports.
Hence, the comparison continues with the classic version of \CC that treated such copy-constructor calls as necessary.

To summarize the unsupported combinations, the relevant features are:
\begin{enumerate}
\item
\label{p:feature1}
        Object provider implements lifecycle functions to manage a resource outside of the object.
\item
\label{p:feature2}
        Object provider implements lifecycle functions to store references to the object, often originating from outside of it.
\item
\label{p:feature3}
        Object user expects to pass (in either direction) an object by value for function calls.
\end{enumerate}
\CC supports all three simultaneously.
\CFA does not currently support \ref{p:feature2} and \ref{p:feature3} on the same object, though \ref{p:feature1} works along with either one of \ref{p:feature2} or \ref{p:feature3}.
\CFA needs to be fixed to support all three simultaneously.

The reason \CFA does not support \ref{p:feature2} with \ref{p:feature3} is a holdover from how \CFA lowered function calls to C, before \CFA got references and RAII.
At that time, adhering to a principal of minimal intervention, this code was treated as a passthrough:
\begin{cfa}
struct U { ... };
// RAII to go here
void f( U u ) { F_BODY( u ) }
U x;
f( x );
\end{cfa}
However, adding custom RAII (at ``...go here'') changes things.

\VRef[Figure]{f:CodeLoweringRAII} shows the common \CC lowering~\cite[Sec. 3.1.2.3]{cxx:raii-abi} (right) proceeds differently than the present \CFA lowering (left).
The current \CFA scheme is still using a by-value C call.
C does a @memcpy@ on structures passed by value.
And so, @F_BODY@ sees the bits of @__u_for_f@ occurring at an address that has never been presented to the @U@ lifecycle functions.
If @U@ is trying to have a style- \ref{p:feature2} invariant, it shows up broken in @F_BODY@: references supposedly to @u@ are actually to @__u_for_f@.
The \CC scheme does not have this problem because it constructs the @u@ copy in the correct location within @f@.
Yet, the current \CFA scheme is sufficient to deliver style-\ref{p:feature1} invariants (in this style-\ref{p:feature3} 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.

\begin{figure}
\centering
\begin{tabular}{@{}l|l@{}}
\multicolumn{1}{@{}c|}{\CFA today} & \multicolumn{1}{c@{}}{\CC, \CFA future} \\
\begin{cfa}
struct U {...};
// RAII elided
void f( U u ) {

        F_BODY( u );

}
U x; // call default ctor
{
        @U __u_for_f = x;@  // call copy ctor
        f( __u_for_f );
        // call dtor, __u_for_f
}
// call dtor, x
\end{cfa}
&
\begin{cfa}
struct U {...};
// RAII elided
void f( U * __u_orig ) {
        @U u = * __u_orig;@  // call copy ctor
        F_BODY( u );
        // call dtor, u
}
U x; // call default ctor


f( &x ) ;


// call dtor, x
\end{cfa}
\end{tabular}

\caption{Code Lowering for RAII}
\label{f:CodeLoweringRAII}
\end{figure}

% [Mike is not currently seeing how distinguishing initialization from assignment is relevant]
% as opposed to assignment where sender and receiver are in the same stack frame.
% What is crucial for lifecycle management is knowing if the receiver is initialized or uninitialized, \ie an object is or is not currently associated with management.
% To provide this knowledge, languages differentiate between initialization and assignment to a left-hand side.
% \begin{cfa}
% Obj obj2 = obj1;  $\C[1.5in]{// initialization, obj2 is initialized}$
% obj2 = obj1;      $\C{// assignment, obj2 must be initialized for management to work}\CRT$
% \end{cfa}
% Initialization occurs at declaration by value, parameter by argument, return temporary by function call.
% Hence, it is necessary to have two kinds of constructors: by value or object.
% \begin{cfa}
% Obj obj1{ 1, 2, 3 }; $\C[1.5in]{// by value, management is initialized}$
% Obj obj2 = obj1;     $\C{// by obj, management is updated}\CRT$
% \end{cfa}
% When no object management is required, initialization copies the right-hand value.
% Hence, the calling convention remains uniform, where the unmanaged case uses @memcpy@ as the initialization constructor and managed uses the specified initialization constructor.

% [Mike is currently seeing RVO as orthogonal, addressed with the footnote]
% to a temporary.
% For example, in \CC:
% \begin{c++}
% struct S {...};
% S identity( S s ) { return s; }
% S s;
% s = identity( s ); // S temp = identity( s ); s = temp;
% \end{c++}
% the generated code for the function call created a temporary with initialization from the function call, and then assigns the temporary to the object.
% This two step approach means extra storage for the temporary and two copies to get the result into the object variable.
% \CC{17} introduced return value-optimization (RVO)~\cite{RVO20} to ``avoid copying an object that a function returns as its value, including avoiding creation of a temporary object''.
% \CFA uses C semantics for function return giving direct value-assignment, which eliminates unnecessary code, but skips an essential feature needed by lifetime management.
% The following discusses the consequences of this semantics with respect to lifetime management of \CFA strings.

The string API offers style \ref{p:feature3}'s pass-by-value, \eg in the return of @"a" + "b"@.
Its implementation uses the style-\ref{p:feature2} invariant of the string handles being linked to each other, helping to achieve high performance.
Since 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.
The layer with pass-by-value incurs a performance penalty, while the layer without delivers the desired runtime performance.
The slower, friendlier High Level API (HL, type @string@) wraps the faster, more primitive Low Level API (LL, type @string_res@, abbreviating ``resource'').
Both APIs present the same features, up to return-by-value operations being unavailable in LL and implemented via the workaround in HL.
The intention is for most future code to target HL.
When the RAII issue is fixed, the full HL feature set is achievable using the LL-style lifetime management.
Then, HL can be removed, LL's type renamed to @string@, and programs generated with the current HL will run faster.
In the meantime, performance-critical sections of applications must use LL.
Subsequent performance experiments \see{\VRef{s:PerformanceAssessment}} use the LL API when comparing \CFA to other languages.
This measurement gives a fair estimate of the goal state for \CFA.
A separate measure of the HL overhead is also included.
Hence, \VRef[Section]{string-general-impl} is describing the goal state for \CFA.
In present state, the internal type @string_res@ replaces @string@ for an inter-linked handle.

To use LL, a programmer rewrites invocations using pass-by-value APIs into invocations where resourcing is more explicit.
Many invocations are unaffected, notably assignment and comparison.
\VRef[Figure]{f:HL_LL_Lowering} shows, of the capabilities listed in \VRef[Figure]{f:StrApiCompare}, only three cases need revisions.
The actual HL workaround wraps @string@ as a pointer to a uniquely owned, heap-allocated @string_res@.
This arrangement has @string@ using style-\ref{p:feature1} RAII, which is compatible with pass-by-value.

\begin{figure}
\centering
\begin{tabular}{@{}ll@{}}
HL & LL \\
\hline
\begin{cfa}

string s = "a" + "b";
\end{cfa}
&
\begin{cfa}
string_res sr = "a";
sr += b;
\end{cfa}
\\
\hline
\begin{cfa}
string s = "abcde";
string s2 = s(2, 3);   // s2 == "cde"

s(2,3) = "x";   // s == "abx" && s2 == "cde"
\end{cfa}
&
\begin{cfa}
string_res sr = "abcde";
string_res sr2 = {sr, 2, 3};   // sr2 == "cde"
string_res sr_mid = { sr, 2, 3, SHARE };
sr_mid = "x";   // sr == "abx" && sr2 == "cde"
\end{cfa}
\\
\hline
\begin{cfa}
string s = "abcde";

s[2] = "xxx";    // s == "abxxxde"
\end{cfa}
&
\begin{cfa}
string_res sr = "abcde";
string_res sr_mid = { sr, 2, 1, SHARE };
mid = "xxx";   // sr == "abxxxde"
\end{cfa}
\end{tabular}

\caption{HL to LL Lowering}
\label{f:HL_LL_Lowering}
\end{figure}


\subsection{Sharing Implementation}
\label{sharing-impl}

The \CFA string module has two mechanisms to deal with string handles sharing text.
In the first type of sharing, the user requests that both string handles be views of the same logical, modifiable string.
This state is typically produced by the substring operation.
\begin{cfa}
string s = "abcde";
string s1 = s( 1, 2 )@`share@; $\C[2.25in]{// explicit sharing}$
s[1] = 'x'; $\C{// change s and s1}\CRT$
sout | s | s1;
$\texttt{\small axcde xc}$
\end{cfa}
Here, the source string-handle is referencing an entire string, and the resulting, newly made, string handle is referencing a contained portion of the original.
In this state, a modification made in the overlapping area is visible in both strings.

The 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.
This state is typically produced by constructing a new string, using an original string as its initialization source.
\begin{cfa}
string s = "abcde";
string s1 = s( 1, 2 )@@; $\C[2.25in]{// no sharing}$
s[1] = 'x'; $\C{// copy-on-write s1}\CRT$
sout | s | s1;
$\texttt{\small axcde bc}$
\end{cfa}
In 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.

A further abstraction helps distinguish the two senses of sharing.
A share-edit set (SES) is an equivalence class over string handles, being the reflexive, symmetric and transitive closure of the relationship of one string being constructed from another, with the ``share'' option given.
The SES is represented by a second linked list among the handles.
A string that shares edits with no other is in a SES by itself.
Inside a SES, a logical modification of one substring portion may change the logical value in another substring portion, depending on whether the two actually overlap.
Conversely, no logical value change can flow outside of a SES.
Even if a modification on one string handle does not reveal itself \emph{logically} to anther handle in the same SES (because they do not overlap), if the modification is length-changing, completing the modification requires visiting the second handle to adjust its location in the sliding text.


\subsection{Controlling Implicit Sharing}
\label{s:ControllingImplicitSharing}

There are tradeoffs associated with sharing and its implicit copy-on-write mechanism.
Several qualitative matters are detailed in \VRef{s:PerformanceAssessment}.
In 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.''
Therefore, it is useful to toggle this capability on or off when it is not providing any application benefit.

The \CFA string library provides the type @string_sharectx@ to control an ambient sharing context.
It allows two adjustments: to opt out of sharing entirely or to begin sharing within a private context.
Running with sharing disabled can be thought of as a \CC STL-emulation mode, where each string is dynamically allocated.
The chosen mode applies for the duration of the lifetime of the created  @string_sharectx@ object, up to being suspended by child lifetimes of different contexts.
\VRef[Figure]{fig:string-sharectx} illustrates this behaviour by showing the stack frames of a program in execution.
In this example, the single-letter functions are called in alphabetic order.
The functions @a@, @b@ and @g@ share string character ranges with each other, because they occupy a common sharing-enabled context.
The function @e@ shares within itself (because its is in a sharing-enabled context), but not with the rest of the program (because its context is not occupied by any of the rest of the program).
The functions @c@, @d@ and @f@ never share anything, because they are in a sharing-disabled context.
Executing the example does not produce an interesting outcome, but the comments in the picture indicate when the logical copy operation runs with
\begin{description}
        \item[share:] the copy being deferred, as described through the rest of this section (fast), or
        \item[copy:] the copy performed eagerly (slow).
\end{description}
Only eager copies can cross @string_sharectx@ boundaries.
The 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.

\begin{figure}
        \begin{tabular}{ll}
                \lstinputlisting[language=CFA, firstline=10, lastline=55]{sharectx.run.cfa}
                &
                \raisebox{-0.17\totalheight}{\includegraphics{string-sharectx.pdf}} % lower
        \end{tabular}
        \caption{Controlling copying vs sharing of strings using \lstinline{string_sharectx}.}
        \label{fig:string-sharectx}
\end{figure}


\subsection{Sharing and Threading}

The \CFA string library provides no thread safety, the same as \CC string, providing similar performance goals.
Threads can create their own string buffers and avoid passing these strings to other threads, or require that shared strings be immutable, as concurrent reading is safe.
A positive consequence of this approach is that independent threads can use the sharing buffer without locking overhead.
When string sharing amongst threads is required, program-wide string-management can toggled to non-sharing using @malloc@/@free@, where the storage allocator is assumed to be thread-safe.
Finally, concurrent users of string objects can provide their own mutual exclusion.


\subsection{Short-String Optimization}

\CC implements a short-string ($\le$16) optimization (SSO).
As 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.
\begin{c++}
class string {
        union {
                struct { $\C{// long string, text in heap}$
                        size_t size;
                        char * strptr;
                } lstr;
                char sstr[sizeof(lstr)]; $\C{// short string <16 characters, text in situ}$
        };
        // some tagging for short or long strings
};
\end{c++}
However, there is now a conditional check required on the fast-path to switch between short and long string operations.

It might be possible to pack 16- or 32-bit Unicode characters within the same string buffer as 8-bit characters.
Again, locations for identification flags must be found and checked along the fast path to select the correct actions.
Handling utf8 (variable length) is more problematic because simple pointer arithmetic cannot be used to stride through the variable-length characters.
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.


\section{Performance Assessment}
\label{s:PerformanceAssessment}

I assessed the \CFA string library's speed and memory usage against strings in \CC STL.
Overall, this analysis shows that features common to both APIs comes at no substantial cost in the performance.
Moreover, the comparison shows that \CFA's high-level string features simplify text processing because the STL requires users to think more about memory management.
When the user does, and is successful, STL's performance can be very good.
But if a user does understand the consequences of the STL representation, performance becomes poor.
The \CFA string lets the user work at the level of just putting the right text into the right variables, with corresponding performance degradations reduced or eliminated.

% The final test shows the overall win of the \CFA text-sharing mechanism.
% It exercises several operations together, showing \CFA enabling clean user code to achieve performance that STL requires less-clean user code to achieve.


\subsection{Methodology}

These tests use a \emph{corpus} of strings.
Their lengths are important; the specific characters occurring in them are immaterial.
In a result graph, a corpus's mean string-length is often the independent variable on the x-axis.
When a corpus contains strings of different lengths, the lengths are drawn from a lognormal distribution.
Therefore, strings much longer than the mean occur less often and strings slightly shorter than the mean occur most often.
A corpus's string sizes are one of:
\begin{description}
        \item [Fixed-size] all string lengths are of the stated size.
        \item [Varying 1 and up] the string lengths are drawn from the lognormal distribution with a stated mean and all lengths occur.
        \item [Varying 16 and up] string lengths are drawn from the lognormal distribution with the stated mean, but only lengths 16 and above occur; thus, the stated mean is above 16.
\end{description}
The special treatment of length 16 deals with the SSO in STL @string@, currently not implemented in \CFA.
A fixed-size or from-16 distribution ensures that \CC's extra-optimized cases are isolated within, or removed from, the comparison.
In all experiments that use a corpus, its text is generated and loaded into the system under test before the timed phase begins.
To ensure comparable results, a common memory allocator is used for \CFA and \CC.
\CFA runs the llheap allocator~\cite{Zulfiqar22}, which is also plugged into \CC.
The llheap allocator is significantly better than the standard @glibc@ allocator.

The operations being measured take dozens of nanoseconds, so a succession of many invocations is run and timed as a group.
The 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.
Timing outcomes report mean nanoseconds per invocation, which includes harness overhead and the targeted string API execution.

As discussed in \VRef[Section]{string-raii-limit}, general performance comparisons are made using \CFA's faster, low-level string API, named @string_res@.
\VRef{s:ControllingImplicitSharing} presents an operational mode where \CFA string sharing is turned off.
In this mode, the \CFA string operates similarly to \CC's, by using a heap allocation for string text.
Some experiments include measurements in this mode for baselining purposes, called ``\CC emulation mode'' or ``nosharing''.

See~\VRef{s:ExperimentalEnvironment} for a description of the hardware environment.


\subsection{Test: Append}

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 penalties for simple API misuses.
The basic harness is:
\begin{cfa}
// set alarm duration
for ( ... ) { $\C[1.5in]{// loop for duration}$
        for ( i; N ) { $\C{// perform multiple appends (concatenations)}$
                accum += corpus[ f( i ) ];
        }
        count += N; $\C{// count number of appends}\CRT$
}
\end{cfa}
The harness's outer loop executes for the experiment duration.
The string is reset to empty before appending (not shown).
The inner loop builds up a growing-length string with successive appends.
Each run targets a specific (mean) corpus string length and produces one data point on the result graph.
Three specific comparisons are made with this harness.
Each picks its own independent-variable basis of comparison.
All three comparisons use the varying-from-1 corpus construction, \ie they allow the STL to show its advantage for SSO.


\subsubsection{Fresh vs Reuse in \CC, Emulation Baseline}

The first experiment compares \CFA with \CC, with \CFA operating in nosharing mode and \CC having no other mode, hence both string package are using @malloc@/@free@.
% This experiment establishes a baseline for other experiments.
This experiment also introduces the first \CC coding pitfall, which the next experiment shows is helped by turning on \CFA sharing.
% This pitfall shows, a \CC programmer must pay attention to string variable reuse.
In 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).
\begin{cquote}
\setlength{\tabcolsep}{40pt}
\begin{tabular}{@{}ll@{}}
% \multicolumn{1}{c}{\textbf{fresh}} & \multicolumn{1}{c}{\textbf{reuse}} \\
\begin{cfa}

for ( ... ) {
        @string_res accum;@     $\C[1.5in]{// fresh}$
        for ( N )
                accum @+=@ ...  $\C{// append}\CRT$
}
\end{cfa}
&
\begin{cfa}
string_res accum;
for ( ... ) {
        @accum = "";@  $\C[1.5in]{// reuse}$
        for ( N )
                accum @+=@ ...  $\C{// append}\CRT$
}
\end{cfa}
\end{tabular}
\end{cquote}
The difference is creating a new or reusing an existing string variable.
The pitfall is that most programmers do not consider this difference.
However, creating a new variable implies deallocating the previous string storage and allocating new empty storage.
As the string grows, further deallocations/allocations are required to release the previous and extend the current string storage.
So, 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.

\begin{figure}
\centering
        \includegraphics{plot-string-peq-cppemu.pdf}
%       \includegraphics[width=\textwidth]{string-graph-peq-cppemu.png}
        \caption{Fresh vs Reuse in \CC, Emulation Baseline.
        Average time per iteration with one \lstinline{x += y} invocation (lower is better).
        Comparing \CFA's STL emulation mode with STL implementations, and comparing the fresh with reused reset styles.}
        \label{fig:string-graph-peq-cppemu}
        \bigskip
        \bigskip
        \includegraphics{plot-string-peq-sharing.pdf}
%       \includegraphics[width=\textwidth]{string-graph-peq-sharing.png}
        \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 \VRef[Figure]{fig:string-graph-peq-cppemu}.}
        \label{fig:string-graph-peq-sharing}
\end{figure}

\VRef[Figure]{fig:string-graph-peq-cppemu} shows the resulting performance.
The two fresh (solid spline lines) and the two reuse (dash spline lines) are identical, except for lengths $\le$10, where the \CC SSO has a 40\% average and minimally 24\% advantage.
The 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.
While allocation reduction is huge, data copying dominates the cost, so the lines are still reasonably close together.


\subsubsection{\CFA's Sharing Mode}

This comparison is the same as the last one, except the \CFA implementation is using sharing mode.
Hence, both \CFA's fresh and reuse versions have no memory allocations, and as before, only for reuse does \CC have no memory allocations.
\VRef[Figure]{fig:string-graph-peq-sharing} shows the resulting performance.
For fresh at append lengths 5 and above, \CFA is now closer to the \CC reuse performance, because of removing the dynamic allocations.
However, for reuse, \CFA has slowed down slightly, to performance matching the new fresh version, as the two versions are now implemented virtually the same.
The 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.

\begin{comment}
FIND A HOME!!!
The 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:
\begin{itemize}
\item
To grow a text allocation repeatedly without copying it elsewhere.
This 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.
With \CC-reuse, this benefit is already reaped by the user's reuse of a pre-stretched allocation.
Yet \CC-fresh pays the higher cost because its room to grow for free is at most a constant times the original string's length.
\item
To share an individual text allocation across multiple related strings.
This ability is not applicable to appending with @+=@.
It in play in [xref sub-experiment pta] and [xref experiment pbv].
\item
To share a text arena across unrelated strings, sourcing disparate allocations from a common place.
That is, always allocating from a bump pointer, and never maintaining free lists.
This 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.
This ability is assessed in [xref experiment allocn].
\end{itemize}
This cost, of slowing down append-with-reuse, is \CFA paying the piper for other scenarios done well.
\CFA prioritizes the fresh use case because it is more natural.
The \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.

A \CFA user needing the best performance on an append scenario can still access the \CC-like speed by invoking noshare.
This (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.
This abstraction opt-out is also different from invoking the LL API-level option.
In fact, these considerations are orthogonal.
But 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.
Beyond these comparisons, opting for noshare actually provides program ``eye candy,'' indicating that under-the-hood thinking is becoming relevant here.
\end{comment}


\subsubsection{Misusing Concatenation}

A further pitfall occurs writing the apparently equivalent @x = x + y@ \vs @x += y@.
For numeric types, the generated code is equivalent, giving identical performance.
However, for string types there can be a significant difference.
This pitfall is a particularly likely for beginners.

In earlier experiments, the choice of \CFA API among HL and LL had no impact on the functionality being tested.
Here, however, the @+@ operation, which returns its result by value, is only available in HL.
The \CFA @+=@ is obtained by inlining the HL implementation of @+@, which is done using LL's @+=@, into the test harness, while omitting the HL-inherent extra dynamic allocation.  The HL-upon-LL @+@ implementation, is:
\begin{cquote}
\setlength{\tabcolsep}{20pt}
\begin{tabular}{@{}ll@{}}
\begin{cfa}
struct string {   // simple ownership
        string_res * inner;  // RAII manages malloc/free
};
void ?+=?( string & s, string s2 ) {
        (*s.inner) += (*s2.inner);
}
\end{cfa}
&
\begin{cfa}
string @?+?@( string lhs, string rhs ) {
        string ret = lhs;
        ret @+=@ rhs;
        return ret;
}

\end{cfa}
\end{tabular}
\end{cquote}
This @+@ implementation is also the goal implementation of @+@ once the HL/LL workaround is no longer needed.  Inlining the induced LL steps into the test harness gives:
\begin{cquote}
\setlength{\tabcolsep}{20pt}
\begin{tabular}{@{}ll@{}}
\multicolumn{1}{c}{\textbf{Goal}} & \multicolumn{1}{c}{\textbf{Measured}} \\
\begin{cfa}

for ( ... ) {
        string accum;
        for ( ... ) {
                accum = @accum + ...@


        }
}
\end{cfa}
&
\begin{cfa}
string_res pta_ll_temp;
for ( ... ) {
        string_res accum;
        for ( ... ) {
                pta_ll_temp = @accum@;
                pta_ll_temp @+= ...@;
                accum = pta_ll_temp;
        }
}
\end{cfa}
\end{tabular}
\end{cquote}
Note, the goal code functions today in HL but with slower performance.

\begin{figure}
\centering
        \includegraphics{plot-string-pta-sharing.pdf}
%       \includegraphics[width=\textwidth]{string-graph-pta-sharing.png}
        \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}.}
        \label{fig:string-graph-pta-sharing}
\end{figure}

\VRef[Figure]{fig:string-graph-pta-sharing} gives the outcome, where the Y-axis is log scale because of the large differences.
The STL's penalty is $8 \times$ while \CFA's is only $2 \times$, averaged across the cases shown here.
Moreover, the STL's gap increases with string size, while \CFA's converges.
So again, \CFA helps users who just want to treat strings as values, and not think about the resource management under the covers.

\PAB{Something is wrong with these sentences: While not a design goal, and not graphed, \CFA in STL-emulation mode outperformed STL in this case.
User-managed allocation reuse did not affect either implementation in this case; only ``fresh'' results are shown.}


\subsection{Test: Pass Argument}

STL has a penalty for passing a string by value, which forces users to think about memory management when communicating values with a function.
The key \CFA value-add is that a user can think of a string simply as a value; this test shows that \CC charges a stiff penalty for thinking this way, while \CFA does not.
This test illustrates a main advantage of the \CFA sharing algorithm (in one case).
It shows STL's SSO providing a successful mitigation (in the other case).

The basic operation considered is:
\begin{cfa}
void foo( string s );
string s = "abc";
foo( s );
\end{cfa}
With implicit sharing active, \CFA treats this operation as normal and supported.
Again, an HL-LL difference requires a mockup as LL does not directly support pass-by-value.
\begin{cquote}
\setlength{\tabcolsep}{20pt}
\begin{tabular}{@{}ll@{}}
\multicolumn{1}{c}{\textbf{Goal}} & \multicolumn{1}{c}{\textbf{Measured}} \\
\begin{cfa}
void helper( string q ) {

}
for ( ... ) { // loop for duration
        helper( corpus[ f( i ) ] );
        count += 1;
}
\end{cfa}
&
\begin{cfa}
void helper( string_res & qref ) {
        string_res q = { qref, COPY_VALUE };
}




\end{cfa}
\end{tabular}
\end{cquote}
The goal (HL) version gives the modified test harness, with a single loop.
Each iteration uses a corpus item as the argument to the function call.
These corpus items are imported to the string heap before beginning the timed run.

\begin{figure}
\centering
        \includegraphics{plot-string-pbv.pdf}
%       \includegraphics[width=\textwidth]{string-graph-pbv.png}
        \begin{tabularx}{\linewidth}{>{\centering\arraybackslash}X >{\centering\arraybackslash}X} (a) & (b) \end{tabularx}
        \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.
(a) With \emph{Varying 1 and up} corpus construction, in which the STL-only benefit of SSO optimization occurs, in varying degrees, at all string sizes.
(b) With \emph{Fixed-size} corpus construction, in which this benefit applies exactly to strings with length below 16.}
        \label{fig:string-graph-pbv}
\end{figure}

\VRef[Figure]{fig:string-graph-pbv} shows the costs for calling a function that receives a string argument by value.
STL's performance worsens uniformly as string length increases, except for short strings due to SSO, while \CFA has the same performance at all sizes.
While improved, the \CFA cost to pass a string is still nontrivial.
The contributor is adding and removing the callee's string handle from the global list.
This cost is $1.5 \times$ to $2 \times$ over STL's when SSO applies, but is avoidable once \CFA realizes this optimization.
At 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.
If the \CC string is passed by reference, the results are better and flat across string lengths like \CFA.


\subsection{Test: Allocate}

This test directly compares the allocation schemes of the \CFA string (sharing active), with the STL string.
It treats the \CFA scheme as a form of garbage collection (GC), and the STL scheme as an application of malloc-free.
The test shows that \CFA enables faster speed in exchange for greater memory usage.

A precise garbage-collector, which knows all pointers and may modify them, often runs faster than malloc-free in an amortized analysis, even though it must occasionally stop to collect (latency issues).
The speedup happens indirectly because GC is able to move objects.
(In the case of the mini-allocator powering the \CFA string library, objects are runs of text.)
Moving objects creates a large contiguous store of available memory;
fresh allocations consume from this area using light-weight \emph{bump-allocation}.
A malloc-free implementation cannot move objects because the location of allocated objects is unknown;
hence, free-space management is more complex managing linked structures of freed allocations and possibly coalescing freed blocks.

GC occurs lazily, so the lifetime of unreachable allocations is unknown, \eg GC may never be triggered.
A garbage collector can minimize the memory footprint for unreachable allocations by collecting eagerly.
However, this approach can negate GC's speed advantage.
Alternatively, collecting infrequently can consume large amounts of resident and virtual memory.
In contrast, a program using malloc-free tries to release an allocation as soon as it is unreachable.
This approach reduces the memory footprint (depending on the allocator), but has a per allocation cost for each free.
% [TODO: find citations for the above knowledge]
Therefore, a speed \vs memory tradeoff is a good comparator for \CFA--STL string allocations.
%The test verifies that it is so and quantifies the returns available.

These tests manipulate a tuning knob that controls how much extra space to use.
Specific values of this knob are not user-visible and are not presented in the results.
Instead, its two effects (amount of space used and time per operation) are shown.
The independent variable is the liveness target, which is the fraction of the text buffer in use at the end of a collection.
The allocator expands its text buffer during a collection if the actual live fraction exceeds this target.

\begin{figure}
\centering
  \includegraphics{string-perf-alloc.pdf}
  \caption{Memory-allocation test's harness and its resulting pattern of memory usage under a bump-pointer-only scheme.}
  \label{fig:string-perf-alloc}
\end{figure}

\VRef[Figure]{fig:string-perf-alloc} shows the memory-allocation pattern that the test harness drives.
Note how this pattern creates few long-lived strings and many short-lived strings.
To extend this pattern to the scale of a performance test, the harness is actually recursive, to achieve the nesting (three levels in the figure), and iterative, to achieve the fan-out (factor two / binary tree in the figure).
\begin{cfa}
void f( int depth ) {
        if (depth == 0) return;
        string_res x = corpus[...]; // importing from char * here
        COUNT_ONE_OP_DONE
        for ( fanOut ) {
                // elided: terminate fixed-duration experiment
                f( depth - 1 );
        }
}
START_TIMER
f( launchDepth );
STOP_TIMER
\end{cfa}
The runs presented use a call depth of 1000 and a fan-out of 1.006, which means that approximately one call in 167 makes two recursive calls, while the rest make one.
This sizing keeps an average of 836 strings live and keeps the amounts of consumed memory within the machine's last-level cache.
The time measurement is nanoseconds per @f@-call, for internal or leaf strings.  

% String lifetime (measured in number of subsequent string allocations) is ?? distributed, because each node in the call tree survives as long as its descendent calls.


\begin{figure}
\centering
  \includegraphics{plot-string-allocn.pdf}
  \begin{tabularx}{\linewidth}{>{\centering\arraybackslash}X >{\centering\arraybackslash}X} (a) Vertical, Lower is better. \\ Horizontal, leftward is better. & (b) \hspace*{5pt} STL CFA \hspace*{20pt} STL \hspace*{10pt} CFA \hspace*{10pt} \end{tabularx}
  \caption{Space and time performance, under varying fraction-live targets, for the five string lengths shown, at \emph{Varying 16 and up} corpus construction.}
  \label{fig:string-graph-allocn}
\end{figure}

\VRef[Figure]{fig:string-graph-allocn} shows the experimental results.
In plot (a), there is one labeled curve for each of the five chosen string sizes, 20, 50, 100, 200, 500.
A labeled curve shows the \CFA speed and space combinations achievable by varying the fraction-live tuning parameter.
Stepping along the curve from top-left toward bottom-right means the string library has a smaller fraction of its heap remain live after collection, \ie it doubles its size more often.
Hence, memory approximately doubles between points.
The additional memory means less time is spent collecting, so the curve shows lower (better) times per operation (y-axis).
This doubling benefit diminishes, so the curves begin to flatten.

The point chosen as \CFA's default liveness threshold (20\%) is marked with a circle.
For most string lengths, this point occurs as the doubling benefit becomes subjectively negligible.
At len-500, the amount of space needed to achieve 20\% liveness is so much that last-level cache misses begin occurring generating a further slowdown.
This effect is an anomaly of the experimental setup trying to compare such varied sizes in one view;
the len-500 default point is included only to provide a holistic picture of the STL comparisons (discussed next).

Staying within plot (a), each \emph{tradeoff} line (green) connects the default-tuned \CFA performance point with its length-equivalent STL performance point.
STL always uses less memory (occurs to the left of) than its \CFA equivalent.
Ideally, \CFA results would be faster (STL occurs above it);
however, this inversion only occurs for smaller string lengths.
That is, the STL-to-\CFA tradeoff line goes down and to the right for small strings, but for longer strings, it goes up and to the right.

Plot (b) offers insight into why larger lengths are not currently showing the anticipated tradeoff, and suggests possible remedies.
This plot breaks down the time spent, comparing STL--\CFA tradeoffs, at successful len-50 with unsuccessful len-200.
Data are sourced from running the experiment under \emph{perf}, recording samples of the call stack, and imposing a mutually-exclusive classification on these call stacks.
Reading a stacked bar from the top down, \emph{text import} captures samples where a routine like @memcpy@ is running, so that the string library is copying characters from the corpus source into its allocated working space.
\emph{Malloc-free} means literally one of those routines (taking nontrivial time only for STL), while \emph{gc} is the direct \CFA(-only) equivalent.
All of the attributions so far occur while a string is live; further time spent in a string's lifecycle management functions is attributed \emph{ctor-dtor}.
Skipping to the bottom-most attribution, \emph{harness-leaf} represents samples where the youngest live stack frame is simply the recursive @helper@ routine of \VRef[Figure]{fig:string-perf-alloc}.
The skipped attribution \emph{Other} has samples that meet none of the criteria above.

\PAB{From Mike: need to add the sep-comp side bar to the graph.}

Beside \CFA's principal bars, a bar for separate-compilation overhead (\emph{sep.\ comp.}) shows the benefit that STL enjoys by using monolithic compilation.
\CFA currently forgoes this benefit.
This overhead figure was obtained by hacking a version of the \CFA string library to have a header-only implementation and measuring the resulting speed.
The difference between separately compiled (normal) and header-only (hacked) versions is the reported overhead.
It represents how much \CFA could speed up if it switched to a header-only implementation to match STL.
The difference jumps noticeably between the different string sizes, but has little correlation with string size ($r=0.3$).
Associating this potential improvement with the \emph{other} attribution is a stylistic choice.

Analyzing the stacked bars from the bottom up, the first two categories, \emph{harness-leaf} and \emph{other} both give baseline times that should not be matters of STL-\CFA difference.
The \emph{harness-leaf} category is called out as a quality check; this attribution is equal across all four setups, ruling out mysterious ``everything is X\% slower'' effects.
But with the \emph{other} attribution, STL beats \CFA by an amount that matches the STL's benefit from avoiding separate compilation.
In the \emph{ctor-dtor} category, \CFA is spending more time than STL to inter-link its string handles.
Comparing STL's \emph{malloc-free} with \CFA's \emph{gc}, \CFA's is considerably shorter, in spite of its copying, because \emph{gc} only spends time on live strings, while \emph{malloc-free} works on all strings.
Most of the every-string bookkeeping occurs under STL's \emph{malloc-free} and \CFA's \emph{ctor-dtor}.
So the critical comparison is STL's $(\textit{ctor-dtor} + \textit{malloc-free})$ \vs \CFA's $(\textit{ctor-dtor} + \textit{gc})$.
Here, \CFA is a clear winner.
Moreover, the discussion so far holds for both the successful and unsuccessful string lengths, albeit with the length-correlated duration of \emph{gc} (due to copying) encroaching on \CFA's advantage, though not eliminating it.
The total attributions so far see \CFA ahead, possibly by more than is shown, depending on how one views the separate-compilation difference.
Under a \CFA-generous separate-compilation stance, \CFA is equal or ahead in every important category so far.

The remaining attribution, \emph{text-import}, is thus a major reason that \CFA is currently unsuccessful at delivering improved speed with long strings.  \PAB{From Mike: need to finish this point.}

% \subsection{Test: Normalize}

% This test is more applied than the earlier ones.
% It combines the effects of several operations.
% It also demonstrates a case of the \CFA API allowing user code to perform well, while being written without overt memory management, while achieving similar performance in STL requires adding memory-management complexity.

% To motivate: edits being rare

% The program is doing a specialized find-replace operation on a large body of text.
% In the program under test, the replacement is just to erase a magic character.
% But in the larger software problem represented, the rewrite logic belongs to a module that was originally intended to operate on simple, modest-length strings.
% The challenge is to apply this packaged function across chunks taken from the large body.
% Using the \CFA string library, the most natural way to write the helper module's function also works well in the adapted context.
% Using the STL string, the most natural ways to write the helper module's function, given its requirements in isolation, slow down when it is driven in the adapted context.

\begin{lstlisting}
void processItem( string & item ) {
         // find issues in item and fix them
}
\end{lstlisting}