Index: doc/theses/mike_brooks_MMath/plots/string-pbv.gp =================================================================== --- doc/theses/mike_brooks_MMath/plots/string-pbv.gp (revision c1f17aa49ffc892b8b212597405b9283b71889a1) +++ doc/theses/mike_brooks_MMath/plots/string-pbv.gp (revision e78d9696cdf69e1bc5f317be2b6c9f1e1c21146e) @@ -1,3 +1,3 @@ -set terminal pdf color enhanced size 6.0in,3.0in font "Times,17" +set terminal pdf color enhanced size 6.5in,3.0in font "Times,17" #set terminal postscript portrait enhanced size 7.5, 10. color solid 9.5; #set terminal wxt size 950,1250 Index: doc/theses/mike_brooks_MMath/string.tex =================================================================== --- doc/theses/mike_brooks_MMath/string.tex (revision c1f17aa49ffc892b8b212597405b9283b71889a1) +++ doc/theses/mike_brooks_MMath/string.tex (revision e78d9696cdf69e1bc5f317be2b6c9f1e1c21146e) @@ -47,5 +47,5 @@ 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{ +Here, the \CC @c_str@ member 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. @@ -94,6 +94,6 @@ s = 'x'; s = "abc"; -s = 42hh; /* signed char */ -s = 42h; /* short int */ +s = 42hh; // signed char +s = 42h; // short int s = 0xff; \end{cfa} @@ -134,5 +134,5 @@ 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. +The assignment operator and constructor both allocate storage 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} @@ -284,5 +284,5 @@ 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: +While it can special-case some combinations: \begin{c++} s = 'a' + s; $\C[2in]{// compiles in C++}$ @@ -299,5 +299,5 @@ The binary operators @*@ and @*=@ repeat a string $N$ times. -If $N = 0$, a zero length string, @""@, is returned. +If $N = 0$, a zero-length string results, @""@. \begin{cquote} \begin{tabular}{@{}ll@{}} @@ -460,5 +460,5 @@ 3 4 -10 +10 // not found, string length \end{cfa} \end{tabular} @@ -470,17 +470,17 @@ \begin{cfa} charclass vowels{ "aeiouy" }; +i = include( "aabiuyoo", vowels ); i = include( "aaeiuyoo", vowels ); -i = include( "aabiuyoo", vowels ); -\end{cfa} -& -\begin{cfa} - -8 // compliant +\end{cfa} +& +\begin{cfa} + 2 // b non-compliant +8 // compliant, string length \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. +The position of the first non-compliant character is returned or the position of the last character if the string is compliant. 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). @@ -493,5 +493,5 @@ & \begin{cfa} -8 // compliant +8 // compliant, string length 2 // y non-compliant \end{cfa} @@ -502,6 +502,6 @@ \begin{tabular}{@{}ll@{}} \begin{cfa} +s = include( "aabiuyoo", vowels ); s = include( "aaeiuyoo", vowels ); -s = include( "aabiuyoo", vowels ); s = exclude( "cdbfghmk", vowels ); s = exclude( "cdyfghmk", vowels ); @@ -534,5 +534,5 @@ \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 position of the first non-compliant character is returned or the position of the last character if the string is compliant (and vice versa for @exclude@). The translate operation returns a string with each character transformed by one of the C character transformation functions. @@ -1028,16 +1028,9 @@ 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. +Changes can happen on an aliasing substring that overlaps. \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} @@ -1053,5 +1046,5 @@ a( 0, 2 ) = "aaa"; b( 1, 12 ) = "bbb"; - c( 4, 5 ) = "ccc"; + c( 3, 5 ) = "ccc"; c = "yyy"; d( 0, 3 ) = "ddd"; @@ -1064,13 +1057,14 @@ \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"@ \\ - & \\ +x & a & b & c & d & e \\ +@"ssttttuuuww"@ & @"sst"@ & @"ttt"@ & @"ttuuu"@ & @"uww"@ & @"uww"@ \\ +@"aaattttuuuww"@ & @"aaat"@ & @"ttt"@ & @"ttuuu"@ & @"uww"@ & @"uww"@ \\ +@"aaatbbbtuuuww"@ & @"aaat"@ & @"tbbb"@ & @"tuuu"@ & @"uww"@ & @"uww"@ \\ +@"aaatbbbtuucccww"@ & @"aaat"@ & @"tbbb"@ & @"tuuccc"@& @"cccww"@ & @"uww"@ \\ +@"aaatbbbyyyww"@ & @"aaat"@ & @"tbbb"@ & @"yyy"@ & @"ww"@ & @"uww"@ \\ +@"aaatbbbyyyddd"@ & @"aaat"@ & @"tbbb"@ & @"yyy"@ & @"ddd"@ & @"uww"@ \\ +@"aaatbbbyyyddd"@ & @"aaat"@ & @"tbbb"@ & @"yyy"@ & @"ddd"@ & @"uww"@ \\ +@"eee"@ & @""@ & @""@ & @""@ & @""@ & @"eee"@ \\ + & \end{tabular} \end{tabular} @@ -1086,26 +1080,287 @@ \end{figure} +\begin{figure} +\vspace*{-5pt} +\setlength{\tabcolsep}{1.5pt} +\setlength{\columnsep}{60pt} +\setlength{\columnseprule}{0.2pt} +\setlength{\extrarowheight}{-1pt} + +\begin{multicols}{2} +\sf +\begin{tabular}{@{}l@{\hspace{10pt}}l@{}} +\begin{tabular}{@{}*{12}{c}@{}} +\multicolumn{12}{@{}l@{}}{function entry} \\ +x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ + & {\tt s} & {\tt s} & {\tt t} & {\tt t} & {\tt t} & {\tt t} & {\tt u} & {\tt u} & {\tt u} & {\tt w} & {\tt w} \\ +a & 0 & 1 & 2 \\ + & {\tt s} & {\tt s} & {\tt t} \\ +b & & & 0 & 1 & 2 \\ + & & & {\tt t} & {\tt t} & {\tt t} \\ +c & & & & & 0 & 1 & 2 & 3 & 4 \\ + & & & & & {\tt t} & {\tt t} & {\tt u} & {\tt u} & {\tt u} \\ +d & & & & & & & & & 0 & 1 & 2 \\ + & & & & & & & & & {\tt u} & {\tt w} & {\tt w} +\end{tabular} +& +\begin{tabular}{@{}*{5}{c}@{}} + & \\ + & e & 0 & 1 & 2 \\ + & & {\tt u} & {\tt w} & {\tt w} \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & +\end{tabular} +\end{tabular} + +\bigskip +@a( 0, 2 ) = "aaa";@ \\ +\begin{tabular}{@{}l@{\hspace{10pt}}l@{}} +\begin{tabular}{@{}*{13}{c}@{}} +x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ + & {\tt a} & {\tt a} & {\tt a} & {\tt t} & {\tt t} & {\tt t} & {\tt t} & {\tt u} & {\tt u} & {\tt u} & {\tt w} & {\tt w} \\ +a & 0 & 1 & 2 & 3 \\ + & {\tt a} & {\tt a} & {\tt a} & {\tt t} \\ +b & & & & 0 & 1 & 2 \\ + & & & & {\tt t} & {\tt t} & {\tt t} \\ +c & & & & & & 0 & 1 & 2 & 3 & 4 \\ + & & & & & & {\tt t} & {\tt t} & {\tt u} & {\tt u} & {\tt u} \\ +d & & & & & & & & & & 0 & 1 & 2 \\ + & & & & & & & & & & {\tt u} & {\tt w} & {\tt w} +\end{tabular} +& +\begin{tabular}{@{}*{5}{c}@{}} + & e & 0 & 1 & 2 \\ + & & {\tt u} & {\tt w} & {\tt w} \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & +\end{tabular} +\end{tabular} + +\bigskip + +@b( 1, 12 ) = "bbb";@ \\ +\begin{tabular}{@{}l@{\hspace{10pt}}l@{}} +\begin{tabular}{@{}*{14}{c}@{}} +x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ + & {\tt a} & {\tt a} & {\tt a} & {\tt t} & {\tt b} & {\tt b} & {\tt b} & {\tt t} & {\tt u} & {\tt u} & {\tt u} & {\tt w} & {\tt w} \\ +a & 0 & 1 & 2 & 3 \\ + & {\tt a} & {\tt a} & {\tt a} & {\tt t} \\ +b & & & & 0 & 1 & 2 & 3 \\ + & & & & {\tt t} & {\tt b} & {\tt b} & {\tt b} \\ +c & & & & & & & & 0 & 1 & 2 & 3 \\ + & & & & & & & & {\tt t} & {\tt u} & {\tt u} & {\tt u} \\ +d & & & & & & & & & & & 0 & 1 & 2 \\ + & & & & & & & & & & & {\tt u} & {\tt w} & {\tt w} +\end{tabular} +& +\begin{tabular}{@{}*{5}{c}@{}} + & e & 0 & 1 & 2 \\ + & & {\tt u} & {\tt w} & {\tt w} \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & +\end{tabular} +\end{tabular} + +\bigskip + +@c( 3, 5 ) = "ccc";@ \\ +\begin{tabular}{@{}l@{\hspace{10pt}}l@{}} +\begin{tabular}{@{}*{16}{c}@{}} +x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ + & {\tt a} & {\tt a} & {\tt a} & {\tt t} & {\tt b} & {\tt b} & {\tt b} & {\tt t} & {\tt u} & {\tt u} & {\tt c} & {\tt c} & {\tt c} & {\tt w} & {\tt w} \\ +a & 0 & 1 & 2 & 3 \\ + & {\tt a} & {\tt a} & {\tt a} & {\tt t} \\ +b & & & & 0 & 1 & 2 & 3 \\ + & & & & {\tt t} & {\tt b} & {\tt b} & {\tt b} \\ +c & & & & & & & & 0 & 1 & 2 & 3 & 4 & 5 \\ + & & & & & & & & {\tt t} & {\tt u} & {\tt u} & {\tt c} & {\tt c} & {\tt c} \\ +d & & & & & & & & & & & 0 & 1 & 2 & 3 & 4 \\ + & & & & & & & & & & & {\tt c} & {\tt c} & {\tt c} & {\tt w} & {\tt w} +\end{tabular} +& +\begin{tabular}{@{}*{5}{c}@{}} + & e & 0 & 1 & 2 \\ + & & {\tt u} & {\tt w} & {\tt w} \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & +\end{tabular} +\end{tabular} + +@c = "yyy";@ \\ +\begin{tabular}{@{}l@{\hspace{10pt}}l@{}} +\begin{tabular}{@{}*{13}{c}@{}} +x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ + & {\tt a} & {\tt a} & {\tt a} & {\tt t} & {\tt b} & {\tt b} & {\tt b} & {\tt y} & {\tt y} & {\tt y} & {\tt w} & {\tt w} \\ +a & 0 & 1 & 2 & 3 \\ + & {\tt a} & {\tt a} & {\tt a} & {\tt t} \\ +b & & & & 0 & 1 & 2 & 3 \\ + & & & & {\tt t} & {\tt b} & {\tt b} & {\tt b} \\ +c & & & & & & & & 0 & 1 & 2 \\ + & & & & & & & & {\tt y} & {\tt y} & {\tt y} \\ +d & & & & & & & & & & & 0 & 1 \\ + & & & & & & & & & & & {\tt w} & {\tt w} +\end{tabular} +& +\begin{tabular}{@{}*{5}{c}@{}} + & e & 0 & 1 & 2 \\ + & & {\tt u} & {\tt w} & {\tt w} \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & +\end{tabular} +\end{tabular} + +\bigskip +@d( 0, 3 ) = "ddd";@ \\ +\begin{tabular}{@{}l@{\hspace{10pt}}l@{}} +\begin{tabular}{@{}*{14}{c}@{}} +x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ + & {\tt a} & {\tt a} & {\tt a} & {\tt t} & {\tt b} & {\tt b} & {\tt b} & {\tt y} & {\tt y} & {\tt y} & {\tt d} & {\tt d} & {\tt d} \\ +a & 0 & 1 & 2 & 3 \\ + & {\tt a} & {\tt a} & {\tt a} & {\tt t} \\ +b & & & & 0 & 1 & 2 & 3 \\ + & & & & {\tt t} & {\tt b} & {\tt b} & {\tt b} \\ +c & & & & & & & & 0 & 1 & 2 \\ + & & & & & & & & {\tt y} & {\tt y} & {\tt y} \\ +d & & & & & & & & & & & 0 & 1 & 2 \\ + & & & & & & & & & & & {\tt d} & {\tt d} & {\tt d} +\end{tabular} +& +\begin{tabular}{@{}*{5}{c}@{}} + & e & 0 & 1 & 2 \\ + & & {\tt u} & {\tt w} & {\tt w} \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & +\end{tabular} +\end{tabular} + +\bigskip + +@e( 0, 3 ) = "eee";@ \\ +\begin{tabular}{@{}l@{\hspace{10pt}}l@{}} +\begin{tabular}{@{}*{14}{c}@{}} +x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ + & {\tt a} & {\tt a} & {\tt a} & {\tt t} & {\tt b} & {\tt b} & {\tt b} & {\tt y} & {\tt y} & {\tt y} & {\tt d} & {\tt d} & {\tt d} \\ +a & 0 & 1 & 2 & 3 \\ + & {\tt a} & {\tt a} & {\tt a} & {\tt t} \\ +b & & & & 0 & 1 & 2 & 3 \\ + & & & & {\tt t} & {\tt b} & {\tt b} & {\tt b} \\ +c & & & & & & & & 0 & 1 & 2 \\ + & & & & & & & & {\tt y} & {\tt y} & {\tt y} \\ +d & & & & & & & & & & & 0 & 1 & 2 \\ + & & & & & & & & & & & {\tt d} & {\tt d} & {\tt d} +\end{tabular} +& +\begin{tabular}{@{}*{5}{c}@{}} + & e & 0 & 1 & 2 \\ + & & {\tt e} & {\tt e} & {\tt e} \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & +\end{tabular} +\end{tabular} + +\bigskip + +@x = e;@ \\ +\begin{tabular}{@{}l@{\hspace{10pt}}l@{}} +\begin{tabular}{@{}*{16}{c}@{}} +x & 0 & 1 & 2 \\ + & {\tt e} & {\tt e} & {\tt e} \\ +a & \\ + & "" \\ +b & \\ + & "" \\ +c & \\ + & "" \\ +d & \\ + & "" +\end{tabular} +& +\begin{tabular}{@{}*{5}{c}@{}} + & e & 0 & 1 & 2 \\ + & & {\tt e} & {\tt e} & {\tt e} \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & \\ + & & & & +\end{tabular} +\end{tabular} +\end{multicols} + +\caption{Execution of Function \lstinline{test}} +\label{f:ParametersPassingResults} +\end{figure} + +\VRef[Figure]{f:ParameterPassing} shows similar relationships when passing the results of substring operations by reference and by value to a subprogram. +Because this example is complex, \VRef[Figure]{f:ParametersPassingResults} shows line-by-line changes to the reference parameters @x@, @a@, @b@, @c@, @d@, and value parameter @e@ as function @test@ executes (read top to bottom, left to right). +The assignment to variable @a@ changes its substring @"ss"@ to @"aaa"@ increasing @a@ to @"aaat"@ (3 to 4 characters), increasing @x@ from 11 to 12 characters, and pushing @b@, @c@ and @d@ right one character in @x@ because there is no overlap with the changed characters. +Similarly, the assignment to variable @b@ changes its substring @"tt"@ to @"bbb"@ increasing @b@ to @"tbbb"@ (3 to 4 characters), increasing @x@ from 12 to 13 characters, and pushing @c@ and @d@ right one character in @x@ because there is no overlap with the changed characters. +The assignment to variable @c@ changes its substring @"u"@ (at the end) to @"ccc"@ increasing @c@ to @"tuuccc"@ (4 to 6 characters), increasing @x@ from 13 to 15 characters, and @d@ remains in the same position because it overlaps with the changed characters and its @"u"@ grows to @"ccc"@ giving @"cccww"@. +The second assignment to variable @c@ changes its substring @"tuuccc"@ to @"yyy"@ decreasing @c@ to @"yyy"@ (6 to 3 characters), decreasing @x@ from 15 to 12 characters, and the 3 character overlapping with @d@ are removed leaving @"ww"@. +The assignment to variable @d@ changes its substring @"ww"@ to @"ddd"@ increasing @d@ from 2 to 3 characters, increasing @x@ from 11 to 12 characters. +The assignment to variable @e@ changes its substring @"uww"@ to @"eee"@ with no change in length. +Finally, the assignment to @x@ sets it pointing at @e@, and all prior overlapping strings with @x@ become empty (null) strings. + \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. +This section discusses the implementation of the prior string semantics, specifically, when strings overlap partially or completely. +% First, the issue of a string's mutable or immutable property is clarified. +% Java's immutable strings require copy-on-write when any overlapping string changes. +% However, \CFA/\CC strings are always mutability, even if specified with @const@. +% \begin{cfa} +% const string s1 = "abc"; +% \end{cfa} +% Here, @const@ applies to the implicit @s1@ pointer to @"abc"@, and @"abc"@ is an immutable constant that is \emph{copied} into the string's storage. +% Hence, @s1@ is never pointing at an immutable constant and its underlying string is always mutable, without some addition mechanism as for explicit pointers/references. +% \begin{cfa} +% const int * const cip; // pointer and its referent are const +% const string s1 @const@ = "abc"; // second const applies to implicit referent +% \end{cfa} @@ -1113,5 +1368,5 @@ \label{string-general-impl} -A centrepiece of the string module is its memory manager. +The 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; @@ -1136,5 +1391,5 @@ 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. +A string is a handle to a node in a linked list containing information about 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. @@ -1168,5 +1423,5 @@ 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. +For shared-edit strings, handles that originally reference 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. @@ -1205,26 +1460,22 @@ \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}$ +But lifecycle logic can use the \emph{address}, too, \eg add the @this@ object to a collection at creation and remove it at destruction. +\begin{cfa} +struct Thread { $\C[3in]{// list node}$ // private - inline dlink( N ); + inline dlink( Thread ); }; -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. +static dlist( Thread ) @ready_queue@; +void ?{}( Thread & this ) { /* initialize thread */ insert_last( ready_queue, @this@ ); } +void ^?{}( Thread & this ) { remove( @this@ ); /* de-initialize thread */ } $\C{// implicitly use ready\_queue}\CRT$ +\end{cfa} +A module providing the @Thread@ (node) type can traverse @ready_queue@ to manipulate the objects. +Hence, declaring a @Thread@ not only ensures that it begins with an initially ``good'' value, but it also provides an implicit subscription to a service (scheduler) 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. +A third capability concerns \emph{implicit} copying. +For passing and returning by value in function call, the parameters and return results do not require construction because after allocation the argument or return value is copied into the corresponding object. +In the parameter direction, the language's function-call arranges copy-constructor calls at the control transfer into the callee. +In the return direction, the roles are reversed and the copy-constructor calls happen at the return to the caller. \CC supports this capability. % without qualification. \CFA offers limited support; @@ -1232,8 +1483,9 @@ \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. +These features help reduce unhelpful copy-constructor calls, which, for types like the initial @S@ example, 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. +Hence, the comparison continues with the classic version of \CC that treats such copy-constructor calls as necessary. To summarize the unsupported combinations, the relevant features are: @@ -1257,16 +1509,16 @@ \begin{cfa} struct U { ... }; -// RAII to go here -void f( U u ) { F_BODY( u ) } +// add RAII ctor/dtor function +void f( U u ) { ... /* access fields of u */ ... } U x; f( x ); \end{cfa} -However, adding custom RAII (at ``...go here'') changes things. +However, adding RAII constructors/destructor 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@. +And so, the body of @f@ 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@: 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. @@ -1282,5 +1534,5 @@ void f( U u ) { - F_BODY( u ); + ... /* access fields of u */ ... } @@ -1299,5 +1551,5 @@ void f( U * __u_orig ) { @U u = * __u_orig;@ // call copy ctor - F_BODY( u ); + ... /* access fields of u */ ... // call dtor, u } @@ -1447,10 +1699,10 @@ 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. +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, when the ``share'' option is 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. +A string with no sharing is in a SES by itself. +Inside a SES, a modification of one substring portion may change the value in another substring portion, depending on whether the two overlap. +Conversely, no value change can flow outside of a SES. +Even if a modification on one string handle does not reveal itself \emph{logically} to another 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. @@ -1473,5 +1725,5 @@ 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} +\begin{description}[itemsep=0pt,parsep=0pt] \item[share:] the copy being deferred, as described through the rest of this section (fast), or \item[copy:] the copy performed eagerly (slow). @@ -1518,5 +1770,5 @@ 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. +It might be possible to pack 16- or 32-bit Unicode characters within the same string buffer as for 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. @@ -1527,6 +1779,6 @@ \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. +I assessed the \CFA string library's speed and memory usage against strings in the \CC STL. +Overall, this analysis shows common features in both APIs comes at no substantial cost in 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. @@ -1541,5 +1793,5 @@ These tests use a \emph{corpus} of strings. -Their lengths are important; the specific characters occurring in them are immaterial. +The lengths are important not the contents. 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. @@ -1553,10 +1805,10 @@ 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. +In all experiments that use a corpus, text is generated and loaded before the timing 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 operations being measured take only 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. @@ -1566,5 +1818,4 @@ 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. @@ -1578,4 +1829,5 @@ // set alarm duration for ( ... ) { $\C[1.5in]{// loop for duration}$ + // reset accum to empty for ( i; N ) { $\C{// perform multiple appends (concatenations)}$ accum += corpus[ f( i ) ]; @@ -1585,19 +1837,19 @@ \end{cfa} The harness's outer loop executes for the experiment duration. -The string is reset to empty before appending (not shown). +The string is reset to empty before appending (see below). 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. +All three comparisons use the varying-from-1 corpus construction, \ie they allow the STL to show its SSO advantage. \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@. +The first experiment compares \CFA with \CC in nosharing mode 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). +In the following, both programs 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} @@ -1649,5 +1901,5 @@ \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 two fresh (solid lines) and the two reuse (dash lines) are identical, except for lengths $\le$10, where the \CC SSO has a 40\% average and minimally 24\% advantage. 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. @@ -1919,5 +2171,5 @@ 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. +At len-500 (top line in plot (a)), the amount of space needed to achieve 20\% liveness is so much ($>$~4M) 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). @@ -1942,5 +2194,5 @@ 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. +This overhead figure is 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. @@ -1982,2 +2234,18 @@ } \end{lstlisting} + + +\section{Future Work} + +\CFA strings provide an interesting set of operations for manipulating sets of characters. +However, experience is needed to determine which operations are superfluous and which are missing. +It is hard to find a strong string API in other general-purpose programming-languages to compare with, as most have simple string APIs, especially I/O. +Supporting regular-expressions, as in text-editors and specialize string languages, \eg AWK~\cite{AWK}, Ruby~\cite{Ruby}, SNOBOL~\cite{SNOBOL}, is an important extension. +String sharing also needs experience to determine if the rules for overlapping behaviour provide the right features for complex editing applications. + +Extending \CFA strings to non-ASCII characters is also a significant upgrade required for non-Latin languages. +Working with fixed-size 16 and 32-bit characters should be a straightforward extension from 8-bit characters. +Variable-sized UTF-8/16/32 characters require a significant rethink for implementation. +For example, high-performance manipulation may require a companion array of pointers to the variable-sized characters. + +Finally, adding the \CC SSO trick and merging the two-part string-implementation, once the RAII problem in \CFA is fixed, will provide even better performance.