| 1 | \chapter{String}
|
|---|
| 2 |
|
|---|
| 3 | \vspace*{-20pt}
|
|---|
| 4 | This chapter presents my work on designing and building a modern string type in \CFA.
|
|---|
| 5 | The discussion starts with examples of interesting string problems, followed by examples of how these issues are resolved in my design.
|
|---|
| 6 |
|
|---|
| 7 |
|
|---|
| 8 | \section{String Operations}
|
|---|
| 9 |
|
|---|
| 10 | To prepare for the following discussion, comparisons among C, \CC, Java and \CFA strings are presented, beginning in \VRef[Figure]{f:StrApiCompare}.
|
|---|
| 11 | It provides a classic ``cheat sheet'' presentation, summarizing the names of the most-common closely-equivalent operations.
|
|---|
| 12 | The over-arching commonality is that operations work on groups of characters for assigning, copying, scanning, and updating.
|
|---|
| 13 |
|
|---|
| 14 | \begin{figure}[h]
|
|---|
| 15 | \begin{cquote}
|
|---|
| 16 | \begin{tabular}{@{}l|l|l|l@{}}
|
|---|
| 17 | C @char [ ]@ & \CC @string@ & Java @String@ & \CFA @string@ \\
|
|---|
| 18 | \hline
|
|---|
| 19 | @strcpy@, @strncpy@ & @=@ & @=@ & @=@ \\
|
|---|
| 20 | @strcat@, @strncat@ & @+@ & @+@ & @+@ \\
|
|---|
| 21 | @strcmp@, @strncmp@ & @==@, @!=@, @<@, @<=@, @>@, @>=@
|
|---|
| 22 | & @equals@, @compareTo@ & @==@, @!=@, @<@, @<=@, @>@, @>=@ \\
|
|---|
| 23 | @strlen@ & @length@, @size@ & @length@ & @size@ \\
|
|---|
| 24 | @[ ]@ & @[ ]@ & @charAt@ & @[ ]@ \\
|
|---|
| 25 | @strncpy@ & @substr@ & @substring@ & @( )@ \\
|
|---|
| 26 | @strncpy@ & @replace@ & @replace@ & @=@ \emph{(on a substring)}\\
|
|---|
| 27 | @strstr@ & @find@ & @indexOf@ & @find@ \\
|
|---|
| 28 | @strcspn@ & @find_first_of@ & @matches@ & @include@ \\
|
|---|
| 29 | @strspn@ & @find_first_not_of@ & @matches@ & @exclude@ \\
|
|---|
| 30 | n/a & @c_str@, @data@ & n/a & @strcpy@, @strncpy@ \\
|
|---|
| 31 | \end{tabular}
|
|---|
| 32 | \end{cquote}
|
|---|
| 33 | \caption{Comparison of languages' strings, API/``cheat-sheet'' perspective.}
|
|---|
| 34 | \label{f:StrApiCompare}
|
|---|
| 35 | \end{figure}
|
|---|
| 36 |
|
|---|
| 37 | As mentioned in \VRef{s:String}, a C string differs from other string types as it uses null termination rather than a length, which leads to explicit storage management;
|
|---|
| 38 | hence, most of its group operations are error prone and expensive.
|
|---|
| 39 | Most high-level string libraries use a separate length field and specialized storage management to implement group operations.
|
|---|
| 40 | Interestingly, \CC strings retain null termination in case it is needed to interface with C library functions.
|
|---|
| 41 | \begin{cfa}
|
|---|
| 42 | int open( @const char * pathname@, int flags );
|
|---|
| 43 | string fname{ "test.cc" );
|
|---|
| 44 | open( fname.@c_str()@, O_RDONLY );
|
|---|
| 45 | \end{cfa}
|
|---|
| 46 | 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{
|
|---|
| 47 | C functions like \lstinline{strdup} do return allocated storage that must be freed by the caller.}
|
|---|
| 48 | % Instead, each \CC string is null terminated just in case it might be needed for this purpose.
|
|---|
| 49 | Providing this backwards compatibility with C has a ubiquitous performance and storage cost.
|
|---|
| 50 |
|
|---|
| 51 |
|
|---|
| 52 | \section{\CFA \lstinline{string} type}
|
|---|
| 53 | \label{s:stringType}
|
|---|
| 54 |
|
|---|
| 55 | 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.
|
|---|
| 56 | Hence, 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.
|
|---|
| 57 | As a result, a @string@ declaration does not specify a maximum length, where a C string must.
|
|---|
| 58 | The maximum storage for a \CFA @string@ value is @size_t@ characters, which is $2^{32}$ or $2^{64}$ respectively.
|
|---|
| 59 | 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.
|
|---|
| 60 | Hence, a \CFA string cannot be passed to a C string manipulation routine, such as @strcat@.
|
|---|
| 61 | Like C strings, the characters in a @string@ are numbered starting from 0.
|
|---|
| 62 |
|
|---|
| 63 | The following operations have been defined to manipulate an instance of type @string@.
|
|---|
| 64 | The discussion assumes the following declarations and assignment statements are executed.
|
|---|
| 65 | \begin{cfa}
|
|---|
| 66 | #include @<string.hfa>@
|
|---|
| 67 | @string@ s, name, digit, alpha, punctuation, ifstmt;
|
|---|
| 68 | int i;
|
|---|
| 69 | name = "MIKE";
|
|---|
| 70 | digit = "0123456789";
|
|---|
| 71 | punctuation = "().,";
|
|---|
| 72 | ifstmt = "IF (A > B) {";
|
|---|
| 73 | \end{cfa}
|
|---|
| 74 | Note, the include file @string.hfa@ to access type @string@.
|
|---|
| 75 |
|
|---|
| 76 |
|
|---|
| 77 | \subsection{Implicit String Conversions}
|
|---|
| 78 |
|
|---|
| 79 | The ability to convert from internal (machine) to external (human) format is useful in situations other than I/O.
|
|---|
| 80 | Hence, the basic types @char@, @char *@, @int@, @double@, @_Complex@, including any signness and size variations, implicitly convert to type @string@.
|
|---|
| 81 | \VRef[Figure]{f:ImplicitConversionsString} shows examples of implicit conversions.
|
|---|
| 82 | Conversions can be explicitly specified using a compound literal:
|
|---|
| 83 | \begin{cfa}
|
|---|
| 84 | s = (string){ "abc" }; $\C{// converts char * to string}$
|
|---|
| 85 | s = (string){ 5 }; $\C{// converts int to string}$
|
|---|
| 86 | s = (string){ 5.5 }; $\C{// converts double to string}$
|
|---|
| 87 | \end{cfa}
|
|---|
| 88 | Conversions from @string@ to @char *@, attempt to be safe:
|
|---|
| 89 | either by requiring the maximum length of the @char *@ storage (@strncpy@) or allocating the @char *@ storage for the string characters (ownership), meaning the programmer must free the storage.
|
|---|
| 90 | As well, a C string is always null terminates, implying a minimum size of 1 character.
|
|---|
| 91 | \begin{cquote}
|
|---|
| 92 | \setlength{\tabcolsep}{15pt}
|
|---|
| 93 | \begin{tabular}{@{}l|l@{}}
|
|---|
| 94 | \begin{cfa}
|
|---|
| 95 | string s = "abcde";
|
|---|
| 96 | char cs[3];
|
|---|
| 97 | strncpy( cs, s, sizeof(cs) );
|
|---|
| 98 | char * cp = s;
|
|---|
| 99 | delete( cp );
|
|---|
| 100 | cp = s + ' ' + s;
|
|---|
| 101 | delete( cp );
|
|---|
| 102 | \end{cfa}
|
|---|
| 103 | &
|
|---|
| 104 | \begin{cfa}
|
|---|
| 105 | "abcde"
|
|---|
| 106 |
|
|---|
| 107 | "ab\0", in place
|
|---|
| 108 | "abcde\0", malloc
|
|---|
| 109 |
|
|---|
| 110 | "abcde abcde\0", malloc
|
|---|
| 111 |
|
|---|
| 112 | \end{cfa}
|
|---|
| 113 | \end{tabular}
|
|---|
| 114 | \end{cquote}
|
|---|
| 115 |
|
|---|
| 116 | \begin{figure}
|
|---|
| 117 | \begin{tabular}{@{}l|l@{}}
|
|---|
| 118 | \setlength{\tabcolsep}{15pt}
|
|---|
| 119 | \begin{cfa}
|
|---|
| 120 | // string s = 5;
|
|---|
| 121 | string s;
|
|---|
| 122 | // conversion of char and char * to string
|
|---|
| 123 | s = 'x';
|
|---|
| 124 | s = "abc";
|
|---|
| 125 | char cs[5] = "abc";
|
|---|
| 126 | s = cs;
|
|---|
| 127 | // conversion of integral, floating-point, and complex to string
|
|---|
| 128 | s = 45hh;
|
|---|
| 129 | s = 45h;
|
|---|
| 130 | s = -(ssize_t)MAX - 1;
|
|---|
| 131 | s = (size_t)MAX;
|
|---|
| 132 | s = 5.5;
|
|---|
| 133 | s = 5.5L;
|
|---|
| 134 | s = 5.5+3.4i;
|
|---|
| 135 | s = 5.5L+3.4Li;
|
|---|
| 136 | \end{cfa}
|
|---|
| 137 | &
|
|---|
| 138 | \begin{cfa}
|
|---|
| 139 |
|
|---|
| 140 |
|
|---|
| 141 |
|
|---|
| 142 | "x"
|
|---|
| 143 | "abc"
|
|---|
| 144 |
|
|---|
| 145 | "abc"
|
|---|
| 146 |
|
|---|
| 147 | "45"
|
|---|
| 148 | "45"
|
|---|
| 149 | "-9223372036854775808"
|
|---|
| 150 | "18446744073709551615"
|
|---|
| 151 | "5.5"
|
|---|
| 152 | "5.5"
|
|---|
| 153 | "5.5+3.4i"
|
|---|
| 154 | "5.5+3.4i"
|
|---|
| 155 | \end{cfa}
|
|---|
| 156 | \end{tabular}
|
|---|
| 157 | \caption{Implicit Conversions to String}
|
|---|
| 158 | \label{f:ImplicitConversionsString}
|
|---|
| 159 | \end{figure}
|
|---|
| 160 |
|
|---|
| 161 |
|
|---|
| 162 | \subsection{Length}
|
|---|
| 163 |
|
|---|
| 164 | The @len@ operation returns the length of a string using prefix call.
|
|---|
| 165 | \begin{cquote}
|
|---|
| 166 | \setlength{\tabcolsep}{15pt}
|
|---|
| 167 | \begin{tabular}{@{}l|l@{}}
|
|---|
| 168 | \begin{cfa}
|
|---|
| 169 | const char * cs = "abc";
|
|---|
| 170 | i = ""`len;
|
|---|
| 171 | i = "abc"`len;
|
|---|
| 172 | i = cs`len;
|
|---|
| 173 | i = name`len;
|
|---|
| 174 | \end{cfa}
|
|---|
| 175 | &
|
|---|
| 176 | \begin{cfa}
|
|---|
| 177 |
|
|---|
| 178 | 0
|
|---|
| 179 | 3
|
|---|
| 180 | 3
|
|---|
| 181 | 4
|
|---|
| 182 | \end{cfa}
|
|---|
| 183 | \end{tabular}
|
|---|
| 184 | \end{cquote}
|
|---|
| 185 |
|
|---|
| 186 |
|
|---|
| 187 | \subsection{Comparison Operators}
|
|---|
| 188 |
|
|---|
| 189 | The binary relational, @<@, @<=@, @>@, @>=@, and equality, @==@, @!=@, operators compare strings using lexicographical ordering, where longer strings are greater than shorter strings.
|
|---|
| 190 | C strings use function @strcmp@, as the relational/equality operators compare C string pointers not their values, which does not match normal programmer expectation.
|
|---|
| 191 |
|
|---|
| 192 |
|
|---|
| 193 | \subsection{Concatenation}
|
|---|
| 194 |
|
|---|
| 195 | The binary operators @+@ and @+=@ concatenate two strings, creating the sum of the strings.
|
|---|
| 196 | \begin{cquote}
|
|---|
| 197 | \setlength{\tabcolsep}{15pt}
|
|---|
| 198 | \begin{tabular}{@{}l|l@{}}
|
|---|
| 199 | \begin{cfa}
|
|---|
| 200 | s = name + ' ' + digit;
|
|---|
| 201 | s += name;
|
|---|
| 202 | s = s + 'a' + 'b';
|
|---|
| 203 | s = s + "a" + "abc";
|
|---|
| 204 | s = 'a' + 'b' + s;
|
|---|
| 205 | s = "a" + "abc" + s;
|
|---|
| 206 | \end{cfa}
|
|---|
| 207 | &
|
|---|
| 208 | \begin{cfa}
|
|---|
| 209 | "MIKE 0123456789"
|
|---|
| 210 | "MIKE 0123456789MIKE"
|
|---|
| 211 |
|
|---|
| 212 |
|
|---|
| 213 | $\CC$ unsupported
|
|---|
| 214 | $\CC$ unsupported
|
|---|
| 215 | \end{cfa}
|
|---|
| 216 | \end{tabular}
|
|---|
| 217 | \end{cquote}
|
|---|
| 218 | The \CFA type-system allows full commutativity with character and C strings;
|
|---|
| 219 | \CC does not.
|
|---|
| 220 |
|
|---|
| 221 |
|
|---|
| 222 | \subsection{Repetition}
|
|---|
| 223 |
|
|---|
| 224 | The binary operators @*@ and @*=@ repeat a string $N$ times.
|
|---|
| 225 | If $N = 0$, a zero length string, @""@ is returned.
|
|---|
| 226 | \begin{cquote}
|
|---|
| 227 | \setlength{\tabcolsep}{15pt}
|
|---|
| 228 | \begin{tabular}{@{}l|l@{}}
|
|---|
| 229 | \begin{cfa}
|
|---|
| 230 | s = 'x' * 3;
|
|---|
| 231 | s = "abc" * 3;
|
|---|
| 232 | s = (name + ' ') * 3;
|
|---|
| 233 | \end{cfa}
|
|---|
| 234 | &
|
|---|
| 235 | \begin{cfa}
|
|---|
| 236 | xxx
|
|---|
| 237 | abcabcabc
|
|---|
| 238 | MIKE MIKE MIKE
|
|---|
| 239 | \end{cfa}
|
|---|
| 240 | \end{tabular}
|
|---|
| 241 | \end{cquote}
|
|---|
| 242 |
|
|---|
| 243 |
|
|---|
| 244 | \subsection{Substring}
|
|---|
| 245 | The substring operation returns a subset of the string starting at a position in the string and traversing a length.
|
|---|
| 246 | \begin{cquote}
|
|---|
| 247 | \setlength{\tabcolsep}{15pt}
|
|---|
| 248 | \begin{tabular}{@{}l|l@{}}
|
|---|
| 249 | \begin{cfa}
|
|---|
| 250 | s = name( 2, 2 );
|
|---|
| 251 | s = name( 3, -2 );
|
|---|
| 252 | s = name( 2, 8 );
|
|---|
| 253 | s = name( 0, -1 );
|
|---|
| 254 | s = name( -1, -1 );
|
|---|
| 255 | s = name( -3 );
|
|---|
| 256 | \end{cfa}
|
|---|
| 257 | &
|
|---|
| 258 | \begin{cfa}
|
|---|
| 259 | "KE"
|
|---|
| 260 | "IK", length is opposite direction
|
|---|
| 261 | "KE", length is clipped to 2
|
|---|
| 262 | "", beyond string so clipped to null
|
|---|
| 263 | "K", start $and$ length are negative
|
|---|
| 264 | "IKE", to end of string
|
|---|
| 265 | \end{cfa}
|
|---|
| 266 | \end{tabular}
|
|---|
| 267 | \end{cquote}
|
|---|
| 268 | A negative starting position is a specification from the right end of the string.
|
|---|
| 269 | A negative length means that characters are selected in the opposite (right to left) direction from the starting position.
|
|---|
| 270 | If the substring request extends beyond the beginning or end of the string, it is clipped (shortened) to the bounds of the string.
|
|---|
| 271 | If the substring request is completely outside of the original string, a null string located at the end of the original string is returned.
|
|---|
| 272 |
|
|---|
| 273 | The substring operation can also appear on the left hand side of the assignment operator.
|
|---|
| 274 | The substring is replaced by the value on the right hand side of the assignment.
|
|---|
| 275 | The length of the right-hand-side value may be shorter, the same length, or longer than the length of the substring that is selected on the left hand side of the assignment.
|
|---|
| 276 | \begin{cfa}
|
|---|
| 277 | digit( 3, 3 ) = ""; $\C{// digit is assigned "0156789"}$
|
|---|
| 278 | digit( 4, 3 ) = "xyz"; $\C{// digit is assigned "015xyz9"}$
|
|---|
| 279 | digit( 7, 0 ) = "***"; $\C{// digit is assigned "015xyz***9"}$
|
|---|
| 280 | digit(-4, 3 ) = "$\tt\$\$\$$"; $\C{// digit is assigned "015xyz\$\$\$9"}$
|
|---|
| 281 | \end{cfa}
|
|---|
| 282 | A substring is treated as a pointer into the base (substringed) string rather than creating a copy of the subtext.
|
|---|
| 283 | As with all pointers, if the item they are pointing at is changed, then the pointer is referring to the changed item.
|
|---|
| 284 | Pointers to the result value of a substring operation are defined to always start at the same location in their base string as long as that starting location exists, independent of changes to themselves or the base string.
|
|---|
| 285 | However, if the base string value changes, this may affect the values of one or more of the substrings to that base string.
|
|---|
| 286 | If the base string value shortens so that its end is before the starting location of a substring, resulting in the substring starting location disappearing, the substring becomes a null string located at the end of the base string.
|
|---|
| 287 |
|
|---|
| 288 | The following example illustrates passing the results of substring operations by reference and by value to a subprogram.
|
|---|
| 289 | Notice the side-effects to other reference parameters as one is modified.
|
|---|
| 290 | \begin{cfa}
|
|---|
| 291 | main() {
|
|---|
| 292 | string x = "xxxxxxxxxxxxx";
|
|---|
| 293 | test( x, x(1,3), x(3,3), x(5,5), x(9,5), x(9,5) );
|
|---|
| 294 | }
|
|---|
| 295 |
|
|---|
| 296 | // x, a, b, c, & d are substring results passed by reference
|
|---|
| 297 | // e is a substring result passed by value
|
|---|
| 298 | void test(string &x, string &a, string &b, string &c, string &d, string e) {
|
|---|
| 299 | $\C{// x a b c d e}$
|
|---|
| 300 | a( 1, 2 ) = "aaa"; $\C{// aaaxxxxxxxxxxx aaax axx xxxxx xxxxx xxxxx}$
|
|---|
| 301 | b( 2, 12 ) = "bbb"; $\C{// aaabbbxxxxxxxxx aaab abbb bbxxx xxxxx xxxxx}$
|
|---|
| 302 | c( 4, 5 ) = "ccc"; $\C{// aaabbbxcccxxxxxx aaab abbb bbxccc ccxxx xxxxx}$
|
|---|
| 303 | c = "yyy"; $\C{// aaabyyyxxxxxx aaab abyy yyy xxxxx xxxxx}$
|
|---|
| 304 | d( 1, 3 ) = "ddd"; $\C{// aaabyyyxdddxx aaab abyy yyy dddxx xxxxx}$
|
|---|
| 305 | e( 1, 3 ) = "eee"; $\C{// aaabyyyxdddxx aaab abyy yyy dddxx eeexx}$
|
|---|
| 306 | x = e; $\C{// eeexx eeex exx x eeexx}$
|
|---|
| 307 | }
|
|---|
| 308 | \end{cfa}
|
|---|
| 309 |
|
|---|
| 310 | There is an assignment form of substring in which only the starting position is specified and the length is assumed to be the remainder of the string.
|
|---|
| 311 | \begin{cfa}
|
|---|
| 312 | string operator () (int start);
|
|---|
| 313 | \end{cfa}
|
|---|
| 314 | For example:
|
|---|
| 315 | \begin{cfa}
|
|---|
| 316 | s = name( 2 ); $\C{// s is assigned "ETER"}$
|
|---|
| 317 | name( 2 ) = "IPER"; $\C{// name is assigned "PIPER"}$
|
|---|
| 318 | \end{cfa}
|
|---|
| 319 | It is also possible to substring using a string as the index for selecting the substring portion of the string.
|
|---|
| 320 | \begin{cfa}
|
|---|
| 321 | string operator () (const string &index);
|
|---|
| 322 | \end{cfa}
|
|---|
| 323 | For example:
|
|---|
| 324 | \begin{cfa}[mathescape=false]
|
|---|
| 325 | digit( "xyz$\$\$\$$" ) = "678"; $\C{// digit is assigned "0156789"}$
|
|---|
| 326 | digit( "234") = "***"; $\C{// digit is assigned "0156789***"}$
|
|---|
| 327 | \end{cfa}
|
|---|
| 328 |
|
|---|
| 329 |
|
|---|
| 330 | \subsection{Searching}
|
|---|
| 331 |
|
|---|
| 332 | The @index@ operation
|
|---|
| 333 | \begin{cfa}
|
|---|
| 334 | int index( const string &key, int start = 1, occurrence occ = first );
|
|---|
| 335 | \end{cfa}
|
|---|
| 336 | returns the position of the first or last occurrence of the @key@ (depending on the occurrence indicator @occ@ that is either @first@ or @last@) in the current string starting the search at position @start@.
|
|---|
| 337 | If the @key@ does not appear in the current string, the length of the current string plus one is returned.
|
|---|
| 338 | %If the @key@ has zero length, the value 1 is returned regardless of what the current string contains.
|
|---|
| 339 | A negative starting position is a specification from the right end of the string.
|
|---|
| 340 | \begin{cfa}
|
|---|
| 341 | i = digit.index( "567" ); $\C{// i is assigned 3}$
|
|---|
| 342 | i = digit.index( "567", 7 ); $\C{// i is assigned 11}$
|
|---|
| 343 | i = digit.index( "567", -1, last ); $\C{// i is assigned 3}$
|
|---|
| 344 | i = name.index( "E", 5, last ); $\C{// i is assigned 4}$
|
|---|
| 345 | \end{cfa}
|
|---|
| 346 |
|
|---|
| 347 | The next two string operations test a string to see if it is or is not composed completely of a particular class of characters.
|
|---|
| 348 | For example, are the characters of a string all alphabetic or all numeric?
|
|---|
| 349 | Use of these operations involves a two step operation.
|
|---|
| 350 | First, it is necessary to create an instance of type @strmask@ and initialize it to a string containing the characters of the particular character class, as in:
|
|---|
| 351 | \begin{cfa}
|
|---|
| 352 | strmask digitmask = digit;
|
|---|
| 353 | strmask alphamask = string( "abcdefghijklmnopqrstuvwxyz" );
|
|---|
| 354 | \end{cfa}
|
|---|
| 355 | Second, the character mask is used in the functions @include@ and @exclude@ to check a string for compliance of its characters with the characters indicated by the mask.
|
|---|
| 356 |
|
|---|
| 357 | The @include@ operation
|
|---|
| 358 | \begin{cfa}
|
|---|
| 359 | int include( const strmask &, int = 1, occurrence occ = first );
|
|---|
| 360 | \end{cfa}
|
|---|
| 361 | returns the position of the first or last character (depending on the occurrence indicator, which is either @first@ or @last@) in the current string that does not appear in the @mask@ starting the search at position @start@;
|
|---|
| 362 | hence it skips over characters in the current string that are included (in) the @mask@.
|
|---|
| 363 | The characters in the current string do not have to be in the same order as the @mask@.
|
|---|
| 364 | If all the characters in the current string appear in the @mask@, the length of the current string plus one is returned, regardless of which occurrence is being searched for.
|
|---|
| 365 | A negative starting position is a specification from the right end of the string.
|
|---|
| 366 | \begin{cfa}
|
|---|
| 367 | i = name.include( digitmask ); $\C{// i is assigned 1}$
|
|---|
| 368 | i = name.include( alphamask ); $\C{// i is assigned 6}$
|
|---|
| 369 | \end{cfa}
|
|---|
| 370 |
|
|---|
| 371 | The @exclude@ operation
|
|---|
| 372 | \begin{cfa}
|
|---|
| 373 | int exclude( string &mask, int start = 1, occurrence occ = first )
|
|---|
| 374 | \end{cfa}
|
|---|
| 375 | returns the position of the first or last character (depending on the occurrence indicator, which is either @first@ or @last@) in the current string that does appear in the @mask@ string starting the search at position @start@;
|
|---|
| 376 | hence it skips over characters in the current string that are excluded from (not in) in the @mask@ string.
|
|---|
| 377 | The characters in the current string do not have to be in the same order as the @mask@ string.
|
|---|
| 378 | If all the characters in the current string do NOT appear in the @mask@ string, the length of the current string plus one is returned, regardless of which occurrence is being searched for.
|
|---|
| 379 | A negative starting position is a specification from the right end of the string.
|
|---|
| 380 | \begin{cfa}
|
|---|
| 381 | i = name.exclude( digitmask ); $\C{// i is assigned 6}$
|
|---|
| 382 | i = ifstmt.exclude( strmask( punctuation ) ); $\C{// i is assigned 4}$
|
|---|
| 383 | \end{cfa}
|
|---|
| 384 |
|
|---|
| 385 | The @includeStr@ operation:
|
|---|
| 386 | \begin{cfa}
|
|---|
| 387 | string includeStr( strmask &mask, int start = 1, occurrence occ = first )
|
|---|
| 388 | \end{cfa}
|
|---|
| 389 | returns the longest substring of leading or trailing characters (depending on the occurrence indicator, which is either @first@ or @last@) of the current string that ARE included in the @mask@ string starting the search at position @start@.
|
|---|
| 390 | A negative starting position is a specification from the right end of the string.
|
|---|
| 391 | \begin{cfa}
|
|---|
| 392 | s = name.includeStr( alphamask ); $\C{// s is assigned "MIKE"}$
|
|---|
| 393 | s = ifstmt.includeStr( alphamask ); $\C{// s is assigned "IF"}$
|
|---|
| 394 | s = name.includeStr( digitmask ); $\C{// s is assigned ""}$
|
|---|
| 395 | \end{cfa}
|
|---|
| 396 |
|
|---|
| 397 | The @excludeStr@ operation:
|
|---|
| 398 | \begin{cfa}
|
|---|
| 399 | string excludeStr( strmask &mask, int start = 1, occurrence = first )
|
|---|
| 400 | \end{cfa}
|
|---|
| 401 | returns the longest substring of leading or trailing characters (depending on the occurrence indicator, which is either @first@ or @last@) of the current string that are excluded (NOT) in the @mask@ string starting the search at position @start@.
|
|---|
| 402 | A negative starting position is a specification from the right end of the string.
|
|---|
| 403 | \begin{cfa}
|
|---|
| 404 | s = name.excludeStr( digitmask); $\C{// s is assigned "MIKE"}$
|
|---|
| 405 | s = ifstmt.excludeStr( strmask( punctuation ) ); $\C{// s is assigned "IF "}$
|
|---|
| 406 | s = name.excludeStr( alphamask); $\C{// s is assigned ""}$
|
|---|
| 407 | \end{cfa}
|
|---|
| 408 |
|
|---|
| 409 |
|
|---|
| 410 | \subsection{Miscellaneous}
|
|---|
| 411 |
|
|---|
| 412 | The @trim@ operation
|
|---|
| 413 | \begin{cfa}
|
|---|
| 414 | string trim( string &mask, occurrence occ = first )
|
|---|
| 415 | \end{cfa}
|
|---|
| 416 | returns a string in that is the longest substring of leading or trailing characters (depending on the occurrence indicator, which is either @first@ or @last@) which ARE included in the @mask@ are removed.
|
|---|
| 417 | \begin{cfa}
|
|---|
| 418 | // remove leading blanks
|
|---|
| 419 | s = string( " ABC" ).trim( " " ); $\C{// s is assigned "ABC",}$
|
|---|
| 420 | // remove trailing blanks
|
|---|
| 421 | s = string( "ABC " ).trim( " ", last ); $\C{// s is assigned "ABC",}$
|
|---|
| 422 | \end{cfa}
|
|---|
| 423 |
|
|---|
| 424 | The @translate@ operation
|
|---|
| 425 | \begin{cfa}
|
|---|
| 426 | string translate( string &from, string &to )
|
|---|
| 427 | \end{cfa}
|
|---|
| 428 | returns a string that is the same length as the original string in which all occurrences of the characters that appear in the @from@ string have been translated into their corresponding character in the @to@ string.
|
|---|
| 429 | Translation is done on a character by character basis between the @from@ and @to@ strings; hence these two strings must be the same length.
|
|---|
| 430 | If a character in the original string does not appear in the @from@ string, then it simply appears as is in the resulting string.
|
|---|
| 431 | \begin{cfa}
|
|---|
| 432 | // upper to lower case
|
|---|
| 433 | name = name.translate( "ABCDEFGHIJKLMNOPQRSTUVWXYZ", "abcdefghijklmnopqrstuvwxyz" );
|
|---|
| 434 | // name is assigned "name"
|
|---|
| 435 | s = ifstmt.translate( "ABCDEFGHIJKLMNOPQRSTUVWXYZ", "abcdefghijklmnopqrstuvwxyz" );
|
|---|
| 436 | // ifstmt is assigned "if (a > b) {"
|
|---|
| 437 | // lower to upper case
|
|---|
| 438 | name = name.translate( "abcdefghijklmnopqrstuvwxyz", "ABCDEFGHIJKLMNOPQRSTUVWXYZ" );
|
|---|
| 439 | // name is assigned "MIKE"
|
|---|
| 440 | \end{cfa}
|
|---|
| 441 |
|
|---|
| 442 | The @replace@ operation
|
|---|
| 443 | \begin{cfa}
|
|---|
| 444 | string replace( string &from, string &to )
|
|---|
| 445 | \end{cfa}
|
|---|
| 446 | returns a string in which all occurrences of the @from@ string in the current string have been replaced by the @to@ string.
|
|---|
| 447 | \begin{cfa}
|
|---|
| 448 | s = name.replace( "E", "XX" ); $\C{// s is assigned "PXXTXXR"}$
|
|---|
| 449 | \end{cfa}
|
|---|
| 450 | The replacement is done left-to-right.
|
|---|
| 451 | When an instance of the @from@ string is found and changed to the @to@ string, it is NOT examined again for further replacement.
|
|---|
| 452 |
|
|---|
| 453 | \subsection{Returning N+1 on Failure}
|
|---|
| 454 |
|
|---|
| 455 | Any of the string search routines can fail at some point during the search.
|
|---|
| 456 | When this happens it is necessary to return indicating the failure.
|
|---|
| 457 | Many string types in other languages use some special value to indicate the failure.
|
|---|
| 458 | This value is often 0 or -1 (PL/I returns 0).
|
|---|
| 459 | This section argues that a value of N+1, where N is the length of the base string in the search, is a more useful value to return.
|
|---|
| 460 | The index-of function in APL returns N+1.
|
|---|
| 461 | These are the boundary situations and are often overlooked when designing a string type.
|
|---|
| 462 |
|
|---|
| 463 | The situation that can be optimized by returning N+1 is when a search is performed to find the starting location for a substring operation.
|
|---|
| 464 | For example, in a program that is extracting words from a text file, it is necessary to scan from left to right over whitespace until the first alphabetic character is found.
|
|---|
| 465 | \begin{cfa}
|
|---|
| 466 | line = line( line.exclude( alpha ) );
|
|---|
| 467 | \end{cfa}
|
|---|
| 468 | If a text line contains all whitespaces, the exclude operation fails to find an alphabetic character.
|
|---|
| 469 | If @exclude@ returns 0 or -1, the result of the substring operation is unclear.
|
|---|
| 470 | Most string types generate an error, or clip the starting value to 1, resulting in the entire whitespace string being selected.
|
|---|
| 471 | If @exclude@ returns N+1, the starting position for the substring operation is beyond the end of the string leaving a null string.
|
|---|
| 472 |
|
|---|
| 473 | The same situation occurs when scanning off a word.
|
|---|
| 474 | \begin{cfa}
|
|---|
| 475 | start = line.include(alpha);
|
|---|
| 476 | word = line(1, start - 1);
|
|---|
| 477 | \end{cfa}
|
|---|
| 478 | If the entire line is composed of a word, the include operation will fail to find a non-alphabetic character.
|
|---|
| 479 | In general, returning 0 or -1 is not an appropriate starting position for the substring, which must substring off the word leaving a null string.
|
|---|
| 480 | However, returning N+1 will substring off the word leaving a null string.
|
|---|
| 481 |
|
|---|
| 482 |
|
|---|
| 483 | \subsection{C Compatibility}
|
|---|
| 484 |
|
|---|
| 485 | To ease conversion from C to \CFA, there are companion @string@ routines for C strings.
|
|---|
| 486 | \VRef[Table]{t:CompanionStringRoutines} shows the C routines on the left that also work with @string@ and the rough equivalent @string@ opeation of the right.
|
|---|
| 487 | Hence, it is possible to directly convert a block of C string operations into @string@ just by changing the
|
|---|
| 488 |
|
|---|
| 489 | \begin{table}
|
|---|
| 490 | \begin{cquote}
|
|---|
| 491 | \begin{tabular}{@{}l|l@{}}
|
|---|
| 492 | \multicolumn{1}{c|}{\lstinline{char []}} & \multicolumn{1}{c}{\lstinline{string}} \\
|
|---|
| 493 | \hline
|
|---|
| 494 | @strcpy@, @strncpy@ & @=@ \\
|
|---|
| 495 | @strcat@, @strncat@ & @+@ \\
|
|---|
| 496 | @strcmp@, @strncmp@ & @==@, @!=@, @<@, @<=@, @>@, @>=@ \\
|
|---|
| 497 | @strlen@ & @size@ \\
|
|---|
| 498 | @[]@ & @[]@ \\
|
|---|
| 499 | @strstr@ & @find@ \\
|
|---|
| 500 | @strcspn@ & @find_first_of@, @find_last_of@ \\
|
|---|
| 501 | @strspc@ & @find_fist_not_of@, @find_last_not_of@
|
|---|
| 502 | \end{tabular}
|
|---|
| 503 | \end{cquote}
|
|---|
| 504 | \caption{Companion Routines for \CFA \lstinline{string} to C Strings}
|
|---|
| 505 | \label{t:CompanionStringRoutines}
|
|---|
| 506 | \end{table}
|
|---|
| 507 |
|
|---|
| 508 | For example, this block of C code can be converted to \CFA by simply changing the type of variable @s@ from @char []@ to @string@.
|
|---|
| 509 | \begin{cfa}
|
|---|
| 510 | char s[32];
|
|---|
| 511 | //string s;
|
|---|
| 512 | strcpy( s, "abc" ); PRINT( %s, s );
|
|---|
| 513 | strncpy( s, "abcdef", 3 ); PRINT( %s, s );
|
|---|
| 514 | strcat( s, "xyz" ); PRINT( %s, s );
|
|---|
| 515 | strncat( s, "uvwxyz", 3 ); PRINT( %s, s );
|
|---|
| 516 | PRINT( %zd, strlen( s ) );
|
|---|
| 517 | PRINT( %c, s[3] );
|
|---|
| 518 | PRINT( %s, strstr( s, "yzu" ) ) ;
|
|---|
| 519 | PRINT( %s, strstr( s, 'y' ) ) ;
|
|---|
| 520 | \end{cfa}
|
|---|
| 521 | However, the conversion fails with I/O because @printf@ cannot print a @string@ using format code @%s@ because \CFA strings are not null terminated.
|
|---|
| 522 |
|
|---|
| 523 |
|
|---|
| 524 | \subsection{Input/Output Operators}
|
|---|
| 525 |
|
|---|
| 526 | Both the \CC operators @<<@ and @>>@ are defined on type @string@.
|
|---|
| 527 | However, input of a string value is different from input of a @char *@ value.
|
|---|
| 528 | When a string value is read, \emph{all} input characters from the current point in the input stream to either the end of line (@'\n'@) or the end of file are read.
|
|---|
| 529 |
|
|---|
| 530 |
|
|---|
| 531 | \section{Implementation Details}
|
|---|
| 532 |
|
|---|
| 533 | While \VRef[Figure]{f:StrApiCompare} emphasizes cross-language similarities, it elides many specific operational differences.
|
|---|
| 534 | For example, the @replace@ function selects a substring in the target and substitutes it with the source string, which can be smaller or larger than the substring.
|
|---|
| 535 | \CC performs the modification on the mutable receiver object
|
|---|
| 536 | \begin{cfa}
|
|---|
| 537 | string s1 = "abcde";
|
|---|
| 538 | s1.replace( 2, 3, "xy" ); $\C[2.25in]{// replace by position (zero origin) and length, mutable}\CRT$
|
|---|
| 539 | cout << s1 << endl;
|
|---|
| 540 | $\texttt{\small abxy}$
|
|---|
| 541 | \end{cfa}
|
|---|
| 542 | while Java allocates and returns a new string with the result, leaving the receiver unmodified.
|
|---|
| 543 | \label{p:JavaReplace}
|
|---|
| 544 | \begin{java}
|
|---|
| 545 | String s = "abcde";
|
|---|
| 546 | String r = s.replace( "cde", "xy" ); $\C[2.25in]{// replace by text, immutable}$
|
|---|
| 547 | System.out.println( s + ' ' + r );
|
|---|
| 548 | $\texttt{\small abcde abxy}$
|
|---|
| 549 | \end{java}
|
|---|
| 550 | % Generally, Java's @String@ type is immutable.
|
|---|
| 551 | Java provides a @StringBuffer@ near-analog that is mutable.
|
|---|
| 552 | \begin{java}
|
|---|
| 553 | StringBuffer sb = new StringBuffer( "abcde" );
|
|---|
| 554 | sb.replace( 2, 5, "xy" ); $\C[2.25in]{// replace by position, mutable}\CRT$
|
|---|
| 555 | System.out.println( sb );
|
|---|
| 556 | $\texttt{\small abxy}$
|
|---|
| 557 | \end{java}
|
|---|
| 558 | However, there are significant differences;
|
|---|
| 559 | \eg, @StringBuffer@'s @substring@ function returns a @String@ copy that is immutable.
|
|---|
| 560 | Finally, the operations between these type are asymmetric, \eg @String@ has @replace@ by text but not replace by position and vice versa for @StringBuffer@.
|
|---|
| 561 |
|
|---|
| 562 | More significant operational differences relate to storage management, often appearing through assignment (@target = source@), and are summarized in \VRef[Figure]{f:StrSemanticCompare}.
|
|---|
| 563 | % It calls out the consequences of each language taking a different approach on ``internal'' storage management.
|
|---|
| 564 | The following discussion justifies the figure's yes/no entries per language.
|
|---|
| 565 |
|
|---|
| 566 | \begin{figure}
|
|---|
| 567 | \setlength{\extrarowheight}{2pt}
|
|---|
| 568 | \begin{tabularx}{\textwidth}{@{}p{0.6in}XXcccc@{}}
|
|---|
| 569 | & & & \multicolumn{4}{@{}c@{}}{\underline{Supports Helpful?}} \\
|
|---|
| 570 | & Required & Helpful & C & \CC & Java & \CFA \\
|
|---|
| 571 | \hline
|
|---|
| 572 | Type abst'n
|
|---|
| 573 | & Low-level: The string type is a varying amount of text communicated via a parameter or return.
|
|---|
| 574 | & High-level: The string-typed relieves the user of managing memory for the text.
|
|---|
| 575 | & no & yes & yes & yes \\
|
|---|
| 576 | \hline
|
|---|
| 577 | State
|
|---|
| 578 | & \multirow{2}{2in}
|
|---|
| 579 | {Fast Initialize: The target receives the characters of the source without copying the characters, resulting in an Alias or Snapshot.}
|
|---|
| 580 | & Alias: The target name is within the source text; changes made in either variable are visible in both.
|
|---|
| 581 | & yes & yes & no & yes \\
|
|---|
| 582 | \cline{3-7}
|
|---|
| 583 | &
|
|---|
| 584 | & Snapshot: The target is an alias within the source until the target changes (copy on write).
|
|---|
| 585 | & no & no & yes & yes \\
|
|---|
| 586 | \hline
|
|---|
| 587 | Symmetry
|
|---|
| 588 | & Laxed: The target's type is anything string-like; it may have a different status concerning ownership.
|
|---|
| 589 | & Strict: The target's type is the same as the source; both strings are equivalent peers concerning ownership.
|
|---|
| 590 | & -- & no & yes & yes \\
|
|---|
| 591 | \hline
|
|---|
| 592 | Referent
|
|---|
| 593 | & Variable-Constrained: The target can accept the entire text of the source.
|
|---|
| 594 | & Fragment: The target can accept an arbitrary substring of the source.
|
|---|
| 595 | & no & no & yes & yes
|
|---|
| 596 | \end{tabularx}
|
|---|
| 597 |
|
|---|
| 598 | \noindent
|
|---|
| 599 | Notes
|
|---|
| 600 | \begin{itemize}[parsep=0pt]
|
|---|
| 601 | \item
|
|---|
| 602 | All languages support Required in all criteria.
|
|---|
| 603 | \item
|
|---|
| 604 | A language gets ``Supports Helpful'' in one criterion if it can do so without sacrificing the Required achievement on all other criteria.
|
|---|
| 605 | \item
|
|---|
| 606 | The C ``string'' is actually @char []@, under the conventions that @<string.h>@ requires. Hence, there is no actual string type in C, so symmetry does not apply.
|
|---|
| 607 | \item
|
|---|
| 608 | The Java @String@ class is analyzed; its @StringBuffer@ class behaves similarly to @C++@.
|
|---|
| 609 | \end{itemize}
|
|---|
| 610 | \caption{Comparison of languages' strings, storage management perspective.}
|
|---|
| 611 | \label{f:StrSemanticCompare}
|
|---|
| 612 | \end{figure}
|
|---|
| 613 |
|
|---|
| 614 | In C, the declaration
|
|---|
| 615 | \begin{cfa}
|
|---|
| 616 | char s[$\,$] = "abcde";
|
|---|
| 617 | \end{cfa}
|
|---|
| 618 | creates a second-class fixed-sized string-variable, as it can only be used in its lexical context;
|
|---|
| 619 | it cannot be passed by value to string operations or user functions as C array's cannot be copied because there is no string-length information passed to the function.
|
|---|
| 620 | Therefore, only pointers to strings are first-class, and discussed further.
|
|---|
| 621 | \begin{cfa}
|
|---|
| 622 | (const) char * s = "abcde"; $\C[2.25in]{// alias state, n/a symmetry, variable-constrained referent}$
|
|---|
| 623 | char * s1 = s; $\C{// alias state, n/a symmetry, variable-constrained referent}$
|
|---|
| 624 | char * s2 = s; $\C{// alias state, n/a symmetry, variable-constrained referent}$
|
|---|
| 625 | char * s3 = &s[1]; $\C{// alias state, n/a symmetry, variable-constrained referent}$
|
|---|
| 626 | char * s4 = &s3[1]; $\C{// alias state, n/a symmetry, variable-constrained referent}\CRT$
|
|---|
| 627 | printf( "%s %s %s %s %s\n", s, s1, s2, s3, s4 );
|
|---|
| 628 | $\texttt{\small abcde abcde abcde bcde cde}$
|
|---|
| 629 | \end{cfa}
|
|---|
| 630 | Note, all of these aliased strings rely on the single null termination character at the end of @s@.
|
|---|
| 631 | The issue of symmetry does not apply to C strings because the value and pointer strings are essentially different types, and so this feature is scored as not applicable for C.
|
|---|
| 632 | With the type not managing the text storage, there is no ownership question, \ie operations on @s1@ or @s2@ never leads to their memory becoming reusable.
|
|---|
| 633 | 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.
|
|---|
| 634 |
|
|---|
| 635 | In \CC, @string@ offers a high-level abstraction.
|
|---|
| 636 | \begin{cfa}
|
|---|
| 637 | string s = "abcde";
|
|---|
| 638 | string & s1 = s; $\C[2.25in]{// alias state, lax symmetry, variable-constrained referent}$
|
|---|
| 639 | string s2 = s; $\C{// copy (strict symmetry, variable-constrained referent)}$
|
|---|
| 640 | string s3 = s.substr( 1, 2 ); $\C{// copy (strict symmetry, fragment referent)}$
|
|---|
| 641 | string s4 = s3.substr( 1, 1 ); $\C{// copy (strict symmetry, fragment referent)}$
|
|---|
| 642 | cout << s << ' ' << s1 << ' ' << s2 << ' ' << s3 << ' ' << s4 << endl;
|
|---|
| 643 | $\texttt{\small abcde abcde abcde bc c}$
|
|---|
| 644 | string & s5 = s.substr(2,4); $\C{// error: cannot point to temporary}\CRT$
|
|---|
| 645 | \end{cfa}
|
|---|
| 646 | The lax symmetry reflects how the validity of @s1@ depends on the content and lifetime of @s@.
|
|---|
| 647 | It is common practice in \CC to use the @s1@-style pass by reference, with the understanding that the callee only uses the referenced string for the duration of the call, \ie no side-effect using the parameter.
|
|---|
| 648 | So, when the called function is a constructor, it is typical to use an @s2@-style copy-initialization to string-object-typed member.
|
|---|
| 649 | Exceptions to this pattern are possible, but require the programmer to assure safety where the type system does not.
|
|---|
| 650 | The @s3@ initialization is constrained to copy the substring because @c_str@ always provides a null-terminated character, which may be different from the source string.
|
|---|
| 651 | @s3@ assignment could be fast by reference counting the text area and using copy-on-write, but would require an implementation upgrade.
|
|---|
| 652 |
|
|---|
| 653 | In Java, @String@ also offers a high-level abstraction:
|
|---|
| 654 | \begin{java}
|
|---|
| 655 | String s = "abcde";
|
|---|
| 656 | String s1 = s; $\C[2.25in]{// snapshot state, strict symmetry, variable-constrained referent}$
|
|---|
| 657 | String s2 = s.substring( 1, 3 ); $\C{// snapshot state (possible), strict symmetry, fragment referent}$
|
|---|
| 658 | String s3 = s2.substring( 1, 2 ); $\C{// snapshot state (possible), strict symmetry, fragment referent}\CRT$
|
|---|
| 659 | System.out.println( s + ' ' + s1 + ' ' + s2 + ' ' + s3 );
|
|---|
| 660 | System.out.println( (s == s1) + " " + (s == s2) + " " + (s2 == s3) );
|
|---|
| 661 | $\texttt{\small abcde abcde bc c}$
|
|---|
| 662 | $\texttt{\small true false false}$
|
|---|
| 663 | \end{java}
|
|---|
| 664 | Note, @substring@ takes a start and end position, rather than a start position and length.
|
|---|
| 665 | Here, facts about Java's implicit pointers and pointer equality can over complicate the picture, and so are ignored.
|
|---|
| 666 | Furthermore, Java's string immutability means string variables behave as simple values.
|
|---|
| 667 | The result in @s1@ is the pointer in @s@, and their pointer equality confirm no time is spent copying characters.
|
|---|
| 668 | With @s2@, the case for fast-copy is more subtle.
|
|---|
| 669 | Certainly, its value is not pointer-equal to @s@, implying at least a further allocation.
|
|---|
| 670 | \PAB{TODO: finish the fast-copy case.}
|
|---|
| 671 | Java does not meet the aliasing requirement because immutability make it impossible to modify.
|
|---|
| 672 | 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@;
|
|---|
| 673 | as a result, @StringBuffer@ scores as \CC.
|
|---|
| 674 | The easy symmetry that the Java string enjoys is aided by Java's garbage collection; Java's @s2@ is doing effectively the operation of \CC's @s3@, though without the consequence of complicating memory management.
|
|---|
| 675 | \PAB{What complex storage management is going on here?}
|
|---|
| 676 |
|
|---|
| 677 | Finally, in \CFA, @string@ also offers a high-level abstraction:
|
|---|
| 678 | \begin{cfa}
|
|---|
| 679 | string s = "abcde";
|
|---|
| 680 | string & s1 = s; $\C[2.25in]{// alias state, strict symmetry, variable-constrained referent}$
|
|---|
| 681 | string s2 = s; $\C{// snapshot state, strict symmetry, variable-constrained referent}$
|
|---|
| 682 | string s3 = s`share; $\C{// alias state, strict symmetry, variable-constrained referent}\CRT$
|
|---|
| 683 | string s4 = s( 1, 2 );
|
|---|
| 684 | string s5 = s4( 1, 1 );
|
|---|
| 685 | sout | s | s1 | s2 | s3 | s4 | s5;
|
|---|
| 686 | $\texttt{\small abcde abcde abcde abcde bc c}$
|
|---|
| 687 | \end{cfa}
|
|---|
| 688 | % all helpful criteria of \VRef[Figure]{f:StrSemanticCompare} are satisfied.
|
|---|
| 689 | 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).
|
|---|
| 690 | The intended metaphor for \CFA stings is similar to a GUI text-editor or web browser.
|
|---|
| 691 | Select a consecutive block of text using the mouse generates an aliased substring in the file/dialog-box.
|
|---|
| 692 | Typing into the selected area is like assigning to an aliased substring, where the highlighted text is replaced with more or less text;
|
|---|
| 693 | depending on the text entered, the file/dialog-box content grows or shrinks.
|
|---|
| 694 | \PAB{Need to discuss the example, as for the other languages.}
|
|---|
| 695 |
|
|---|
| 696 | The remainder of this chapter explains how the \CFA string achieves this usage style.
|
|---|
| 697 |
|
|---|
| 698 |
|
|---|
| 699 | \section{Storage Management}
|
|---|
| 700 |
|
|---|
| 701 | This section discusses issues related to storage management of strings.
|
|---|
| 702 | Specifically, it is common for strings to logically overlap partially or completely.
|
|---|
| 703 | \begin{cfa}
|
|---|
| 704 | string s1 = "abcdef";
|
|---|
| 705 | string s2 = s1; $\C{// complete overlap, s2 == "abcdef"}$
|
|---|
| 706 | string s3 = s1.substr( 0, 3 ); $\C{// partial overlap, s3 == "abc"}$
|
|---|
| 707 | \end{cfa}
|
|---|
| 708 | This raises the question of how strings behave when an overlapping component is changed,
|
|---|
| 709 | \begin{cfa}
|
|---|
| 710 | s3[1] = 'w'; $\C{// what happens to s1 and s2?}$
|
|---|
| 711 | \end{cfa}
|
|---|
| 712 | which is restricted by a string's mutable or immutable property.
|
|---|
| 713 | For example, Java's immutable strings require copy-on-write when any overlapping string changes.
|
|---|
| 714 | Note, the notion of underlying string mutability is not specified by @const@; \eg in \CC:
|
|---|
| 715 | \begin{cfa}
|
|---|
| 716 | const string s1 = "abc";
|
|---|
| 717 | \end{cfa}
|
|---|
| 718 | the @const@ applies to the @s1@ pointer to @"abc"@, and @"abc"@ is an immutable constant that is \emph{copied} into the string's storage.
|
|---|
| 719 | Hence, @s1@ is not pointing at an immutable constant, meaning its underlying string can be mutable, unless some other designation is specified, such as Java's global immutable rule.
|
|---|
| 720 |
|
|---|
| 721 |
|
|---|
| 722 | \subsection{Logical overlap}
|
|---|
| 723 |
|
|---|
| 724 | \CFA provides a dynamic mechanism to indicate mutable or immutable using the attribute @`share@.
|
|---|
| 725 | This aliasing relationship is a sticky-property established at initialization.
|
|---|
| 726 | For example, here strings @s1@ and @s1a@ are in an aliasing relationship, while @s2@ is in a copy relationship.
|
|---|
| 727 | \input{sharing1.tex}
|
|---|
| 728 | Here, the aliasing (@`share@) causes partial changes (subscripting) to flow in both directions.
|
|---|
| 729 | \input{sharing2.tex}
|
|---|
| 730 | Similarly for complete changes.
|
|---|
| 731 | \input{sharing3.tex}
|
|---|
| 732 |
|
|---|
| 733 | Because string assignment copies the value, RHS aliasing is irrelevant.
|
|---|
| 734 | Hence, aliasing of the LHS is unaffected.
|
|---|
| 735 | \input{sharing4.tex}
|
|---|
| 736 |
|
|---|
| 737 | Now, consider string @s1_mid@ being an alias in the middle of @s1@, along with @s2@, made by a simple copy from the middle of @s1@.
|
|---|
| 738 | \input{sharing5.tex}
|
|---|
| 739 | Again, @`share@ passes changes in both directions; copy does not.
|
|---|
| 740 | 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"@.
|
|---|
| 741 | This alternate positioning also applies to subscripting.
|
|---|
| 742 | \input{sharing6.tex}
|
|---|
| 743 |
|
|---|
| 744 | Finally, assignment flows through the aliasing relationship without affecting its structure.
|
|---|
| 745 | \input{sharing7.tex}
|
|---|
| 746 | In the @"ff"@ assignment, the result is straightforward to accept because the flow direction is from contained (small) to containing (large).
|
|---|
| 747 | The following rules explain aliasing substrings that flow in the opposite direction, large to small.
|
|---|
| 748 |
|
|---|
| 749 | Growth and shrinkage are natural extensions, as for the text-editor example mentioned earlier, where an empty substring is as real real as an empty string.
|
|---|
| 750 | \input{sharing8.tex}
|
|---|
| 751 |
|
|---|
| 752 | Multiple portions of a string can be aliased.
|
|---|
| 753 | % When there are several aliasing substrings at once, the text editor analogy becomes an online multi-user editor.
|
|---|
| 754 | %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.
|
|---|
| 755 | \input{sharing9.tex}
|
|---|
| 756 | 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,
|
|---|
| 757 |
|
|---|
| 758 | When changes happens on an aliasing substring that overlap.
|
|---|
| 759 | \input{sharing10.tex}
|
|---|
| 760 | Strings @s1_crs@ and @s1_mid@ overlap at character 4, @j@ because the substrings are 3,2 and 4,2.
|
|---|
| 761 | 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 @'+'@.
|
|---|
| 762 |
|
|---|
| 763 | \PAB{TODO: finish typesetting the demo}
|
|---|
| 764 |
|
|---|
| 765 | %\input{sharing-demo.tex}
|
|---|
| 766 |
|
|---|
| 767 |
|
|---|
| 768 | \subsection{RAII limitations}
|
|---|
| 769 |
|
|---|
| 770 | Earlier work on \CFA~\cite[ch.~2]{Schluntz17} implemented object constructors and destructors for all types (basic and user defined).
|
|---|
| 771 | A constructor is a user-defined function run implicitly \emph{after} an object's declaration-storage is created, and a destructor is a user-defined function run \emph{before} an object's declaration-storage is deleted.
|
|---|
| 772 | This feature, called RAII~\cite[p.~389]{Stroustrup94}, guarantees pre-invariants for users before accessing an object and post invariants for the programming environment after an object terminates.
|
|---|
| 773 |
|
|---|
| 774 | The purposes of these invariants goes beyond ensuring authentic values inside an object.
|
|---|
| 775 | Invariants can also track occurrences of managed objects in other data structures.
|
|---|
| 776 | For example, reference counting is a typical application of an invariant outside of the data values.
|
|---|
| 777 | With a reference-counting smart-pointer, the constructor and destructor \emph{of a pointer type} tracks the life cycle of the object it points to.
|
|---|
| 778 | Both \CC and \CFA RAII systems are powerful enough to achieve reference counting.
|
|---|
| 779 |
|
|---|
| 780 | In general, a lifecycle function has access to an object by location, \ie constructors and destructors receive a @this@ parameter providing an object's memory address.
|
|---|
| 781 | \begin{cfa}
|
|---|
| 782 | struct S { int * ip; };
|
|---|
| 783 | void ?{}( S & @this@ ) { this.ip = new(); } $\C[3in]{// default constructor}$
|
|---|
| 784 | void ?{}( S & @this@, int i ) { ?{}(this); *this.ip = i; } $\C{// initializing constructor}$
|
|---|
| 785 | void ?{}( S & @this@, S s ) { this = s; } $\C{// copy constructor}$
|
|---|
| 786 | void ^?{}( S & @this@ ) { delete( this.ip ); } $\C{// destructor}\CRT$
|
|---|
| 787 | \end{cfa}
|
|---|
| 788 | The lifecycle implementation can then add this object to a collection at creation and remove it at destruction.
|
|---|
| 789 | A module providing lifecycle semantics can traverse the collection at relevant times to keep the objects ``good.''
|
|---|
| 790 | Hence, declaring such an object not only ensures ``good'' authentic values, but also an implicit subscription to a service that keeps the value ``good'' across its lifetime.
|
|---|
| 791 |
|
|---|
| 792 | In many cases, the relationship between memory location and lifecycle is straightforward.
|
|---|
| 793 | For example, stack-allocated objects being used as parameters and returns, with a sender version in one stack frame and a receiver version in another, as opposed to assignment where sender and receiver are in the same stack frame.
|
|---|
| 794 | 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.
|
|---|
| 795 | To provide this knowledge, languages differentiate between initialization and assignment to a left-hand side.
|
|---|
| 796 | \begin{cfa}
|
|---|
| 797 | Obj obj2 = obj1; $\C[1.5in]{// initialization, obj2 is initialized}$
|
|---|
| 798 | obj2 = obj1; $\C{// assignment, obj2 must be initialized for management to work}\CRT$
|
|---|
| 799 | \end{cfa}
|
|---|
| 800 | Initialization occurs at declaration by value, parameter by argument, return temporary by function call.
|
|---|
| 801 | Hence, it is necessary to have two kinds of constructors: by value or object.
|
|---|
| 802 | \begin{cfa}
|
|---|
| 803 | Obj obj1{ 1, 2, 3 }; $\C[1.5in]{// by value, management is initialized}$
|
|---|
| 804 | Obj obj2 = obj1; $\C{// by obj, management is updated}\CRT$
|
|---|
| 805 | \end{cfa}
|
|---|
| 806 | When no object management is required, initialization copies the right-hand value.
|
|---|
| 807 | Hence, the calling convention remains uniform, where the unmanaged case uses @memcpy@ as the initialization constructor and managed uses the specified initialization constructor.
|
|---|
| 808 |
|
|---|
| 809 | The \CFA RAII system supports lifecycle functions, except for returning a value from a function to a temporary.
|
|---|
| 810 | For example, in \CC:
|
|---|
| 811 | \begin{c++}
|
|---|
| 812 | struct S {...};
|
|---|
| 813 | S identity( S s ) { return s; }
|
|---|
| 814 | S s;
|
|---|
| 815 | s = identity( s ); // S temp = identity( s ); s = temp;
|
|---|
| 816 | \end{c++}
|
|---|
| 817 | the generated code for the function call created a temporary with initialization from the function call, and then assigns the temporary to the object.
|
|---|
| 818 | This two step approach means extra storage for the temporary and two copies to get the result into the object variable.
|
|---|
| 819 | \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''.
|
|---|
| 820 | \CFA uses C semantics for function return giving direct value-assignment, which eliminates unnecessary code, but skips an essential feature needed by lifetime management.
|
|---|
| 821 | The following discusses the consequences of this semantics with respect to lifetime management of \CFA strings.
|
|---|
| 822 |
|
|---|
| 823 | The present string-API contribution provides lifetime management with initialization semantics on function return.
|
|---|
| 824 | The workaround to achieve the full lifetime semantics does have a runtime performance penalty.
|
|---|
| 825 | An alternative API sacrifices return initialization semantics to recover full runtime performance.
|
|---|
| 826 | These APIs are layered, with the slower, friendlier High Level API (HL) wrapping the faster, more primitive Low Level API (LL).
|
|---|
| 827 | Both API present the same features, up to lifecycle management, with return initialization being disabled in LL and implemented with the workaround in HL.
|
|---|
| 828 | The intention is for most future code to target HL.
|
|---|
| 829 | When \CFA becomes a full compiler, it can provide return initialization with RVO optimizations.
|
|---|
| 830 | Then, programs written with the HL API will simply run faster.
|
|---|
| 831 | In the meantime, performance-critical sections of applications use LL.
|
|---|
| 832 | Subsequent performance experiments \see{\VRef{s:PerformanceAssessment}} with other string libraries has \CFA strings using the LL API.
|
|---|
| 833 | These measurement gives a fair estimate of the goal state for \CFA.
|
|---|
| 834 |
|
|---|
| 835 |
|
|---|
| 836 | \subsection{Memory management}
|
|---|
| 837 |
|
|---|
| 838 | A centrepiece of the string module is its memory manager.
|
|---|
| 839 | The management scheme defines a shared buffer for string text.
|
|---|
| 840 | Allocation in this buffer is via a bump-pointer;
|
|---|
| 841 | the buffer is compacted and/or relocated with growth when it fills.
|
|---|
| 842 | A string is a smart pointer into this buffer.
|
|---|
| 843 |
|
|---|
| 844 | 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).
|
|---|
| 845 | A few differences are noteworthy.
|
|---|
| 846 | 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.
|
|---|
| 847 | Here, the allocations are text, so one allocation never keeps another alive.
|
|---|
| 848 | Second, in a general purpose manager, the handle that keeps an allocation alive is just a lean pointer.
|
|---|
| 849 | For strings, a fatter representation is acceptable because there are fewer string head pointers versus chained pointers within nodes as for linked containers.
|
|---|
| 850 |
|
|---|
| 851 | \begin{figure}
|
|---|
| 852 | \includegraphics{memmgr-basic.pdf}
|
|---|
| 853 | \caption{String memory-management data structures}
|
|---|
| 854 | \label{f:memmgr-basic}
|
|---|
| 855 | \end{figure}
|
|---|
| 856 |
|
|---|
| 857 | \VRef[Figure]{f:memmgr-basic} shows the representation.
|
|---|
| 858 | The heap header and text buffer define a sharing context.
|
|---|
| 859 | Normally, one global sharing context is appropriate for an entire program;
|
|---|
| 860 | concurrent exceptions are discussed in \VRef{s:AvoidingImplicitSharing}.
|
|---|
| 861 | A string is a handle into the buffer and linked into a list.
|
|---|
| 862 | The list is doubly linked for $O(1)$ insertion and removal at any location.
|
|---|
| 863 | Strings are orders in the list by string-text address, where there is no overlapping, and approximately, where there is.
|
|---|
| 864 | The header maintains a next-allocation pointer, @alloc@, pointing to the last live allocation in the buffer.
|
|---|
| 865 | No external references point into the buffer and the management procedure relocates the text allocations as needed.
|
|---|
| 866 | A string handle references a containing string, while its string is contiguous and not null terminated.
|
|---|
| 867 | The length sets an upper limit on the string size, but is large (4 or 8 bytes).
|
|---|
| 868 | String handles can be allocated in the stack or heap, and represent the string variables in a program.
|
|---|
| 869 | Normal C life-time rules apply to guarantee correctness of the string linked-list.
|
|---|
| 870 | The text buffer is large enough with good management so that often only one dynamic allocation is necessary during program execution.
|
|---|
| 871 | % During this period, strings can vary in size dynamically.
|
|---|
| 872 |
|
|---|
| 873 | 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.
|
|---|
| 874 | The linked handles define all live strings in the buffer, which indirectly defines the allocated and free space in the buffer.
|
|---|
| 875 | Since the string handles are in (roughly) sorted order, the handle list can be traversed copying the first text to the start of the buffer and subsequent strings after each over.
|
|---|
| 876 | After compaction, if the amount of free storage is still less than the new string allocation, a larger text buffer is heap allocated, the current buffer is copies into the new buffer, and the original buffer is freed.
|
|---|
| 877 | Note, the list of string handles is unaffected during a compaction;
|
|---|
| 878 | only the string pointers in the handles are modified to new buffer locations.
|
|---|
| 879 |
|
|---|
| 880 | Object lifecycle events are the \emph{subscription-management} triggers in such a service.
|
|---|
| 881 | There are two fundamental string-creation routines: importing external text like a C-string or reading a string, and initialization from an existing \CFA string.
|
|---|
| 882 | When importing, storage comes from the end of the buffer, into which the text is copied.
|
|---|
| 883 | The new string handle is inserted at the end of the handle list because the new text is at the end of the buffer.
|
|---|
| 884 | When initializing from text already in the text buffer, the new handle is a second reference into the original run of characters.
|
|---|
| 885 | In this case, the new handle's linked-list position is after the original handle.
|
|---|
| 886 | Both string initialization styles preserve the string module's internal invariant that the linked-list order matches the buffer order.
|
|---|
| 887 | For string destruction, handles are removed from the list.
|
|---|
| 888 |
|
|---|
| 889 | Certain string operations can results in a subset (substring) of another string.
|
|---|
| 890 | The resulting handle is then placed in the correct sorted position in the list, possible with a short linear search to locate the position.
|
|---|
| 891 | For string operations resulting in a new string, that string is allocated at the end of the buffer.
|
|---|
| 892 | For shared-edit strings, handles that originally referenced containing locations need to see the new value at the new buffer location.
|
|---|
| 893 | These strings are moved to appropriate locations at the end of the list \see{[xref: TBD]}.
|
|---|
| 894 | For nonshared-edit strings, a containing string can be moved and the nonshared strings can remain in the same position.
|
|---|
| 895 | String assignment words similarly to string initialization, maintain the invariant of linked-list order matching buffer order.
|
|---|
| 896 |
|
|---|
| 897 | At the level of the memory manager, these modifications can always be explained as assignments and appendment;
|
|---|
| 898 | for example, an append is an assignment into the empty substring at the end of the buffer.
|
|---|
| 899 | 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.
|
|---|
| 900 | 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.
|
|---|
| 901 |
|
|---|
| 902 |
|
|---|
| 903 | \subsection{Sharing implementation}
|
|---|
| 904 |
|
|---|
| 905 | The \CFA string module has two mechanisms to handle the case when string handles share a string of text.
|
|---|
| 906 |
|
|---|
| 907 | The first type of sharing is the user requests both string handles be views of the same logical, modifiable string.
|
|---|
| 908 | This state is typically produced by the substring operation.
|
|---|
| 909 | \begin{cfa}
|
|---|
| 910 | string s = "abcde";
|
|---|
| 911 | string s1 = s( 1, 2 )@`share@; $\C[2.25in]{// explicit sharing}$
|
|---|
| 912 | s[1] = 'x'; $\C{// change s and s1}\CRT$
|
|---|
| 913 | sout | s | s1;
|
|---|
| 914 | $\texttt{\small axcde xc}$
|
|---|
| 915 | \end{cfa}
|
|---|
| 916 | In a typical substring call, the source string-handle is referencing an entire string, and the resulting, newly made, string handle is referencing a portion of the original.
|
|---|
| 917 | In this state, a subsequent modification made by either is visible in both.
|
|---|
| 918 |
|
|---|
| 919 | 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.
|
|---|
| 920 | This state is typically produced by constructing a new string, using an original string as its initialization source.
|
|---|
| 921 | \begin{cfa}
|
|---|
| 922 | string s = "abcde";
|
|---|
| 923 | string s1 = s( 1, 2 )@@; $\C[2.25in]{// no sharing}$
|
|---|
| 924 | s[1] = 'x'; $\C{// copy-on-write s1}\CRT$
|
|---|
| 925 | sout | s | s1;
|
|---|
| 926 | $\texttt{\small axcde bc}$
|
|---|
| 927 | \end{cfa}
|
|---|
| 928 | 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.
|
|---|
| 929 |
|
|---|
| 930 | A further abstraction, in the string module's implementation, helps distinguish the two senses of sharing.
|
|---|
| 931 | A share-edit set (SES) is an equivalence class over string handles, being the reflexive, symmetric and transitive closure of the relationship of one string being constructed from another, with the ``share'' opt-in given.
|
|---|
| 932 | The SES is represented by a second linked list among the handles.
|
|---|
| 933 | A string that shares edits with no other is in a SES by itself.
|
|---|
| 934 | Inside a SES, a logical modification of one substring portion may change the logical value in another, depending on whether the two actually overlap.
|
|---|
| 935 | Conversely, no logical value change can flow outside of a SES.
|
|---|
| 936 | 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.
|
|---|
| 937 |
|
|---|
| 938 |
|
|---|
| 939 | \subsection{Avoiding implicit sharing}
|
|---|
| 940 | \label{s:AvoidingImplicitSharing}
|
|---|
| 941 |
|
|---|
| 942 | There are tradeoffs associated with the copy-on-write mechanism.
|
|---|
| 943 | Several qualitative matters are detailed in \VRef{s:PerformanceAssessment} and the qualitative issue of multi-threaded support is introduced here.
|
|---|
| 944 | The \CFA string library provides a switch to disable threads allocating from the string buffer, when string sharing is unsafe.
|
|---|
| 945 | When toggled, string management is moved to the storage allocator, specifically @malloc@/@free@, where the storage allocator is assumed to be thread-safe.
|
|---|
| 946 |
|
|---|
| 947 | In detail, string sharing has inter-linked string handles, so any participant managing one string is also managing, directly, the neighbouring strings, and from there, a data structure of the ``set of all strings.''
|
|---|
| 948 | This string structure is intended for sequential access.
|
|---|
| 949 | Hence, multiple threads using shared strings need to avoid modifying (concurrently) an instance of this structure (like Java immutable strings).
|
|---|
| 950 | A positive consequence of this approach is that independent threads can use the sharing buffer without locking overhead.
|
|---|
| 951 |
|
|---|
| 952 | When the string library is running with sharing disabled, it runs without implicit thread-safety challenges, which is the same as the \CC STL, and with performance goals similar to the STL.
|
|---|
| 953 | Running with sharing disabled can be thought of as a STL-emulation mode.
|
|---|
| 954 | Hence, concurrent users of string objects must still bring their own mutual exclusion, but the string library does not add any cross thread uses that are not apparent in a user's code.
|
|---|
| 955 |
|
|---|
| 956 | The \CFA string library provides the type @string_sharectx@ to control an ambient sharing context for a current thread.
|
|---|
| 957 | It allows two adjustments: to opt out of sharing entirely or to begin sharing within a private context.
|
|---|
| 958 | Either way, the chosen mode applies only to the current thread, for the duration of the lifetime of the created @string_sharectx@ object, up to being suspended by child lifetimes of different contexts.
|
|---|
| 959 | \VRef[Figure]{fig:string-sharectx} illustrates its behaviour.
|
|---|
| 960 | Executing the example does not produce an interesting outcome.
|
|---|
| 961 | But the comments indicate when the logical copy operation runs with
|
|---|
| 962 | \begin{description}
|
|---|
| 963 | \item[share:] the copy being deferred, as described through the rest of this section (fast), or
|
|---|
| 964 | \item[copy:] the copy performed eagerly (slow).
|
|---|
| 965 | \end{description}
|
|---|
| 966 | Only eager copies can cross @string_sharectx@ boundaries.
|
|---|
| 967 | 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.
|
|---|
| 968 | In this example, the single-letter functions are called in alphabetic order.
|
|---|
| 969 | The functions @a@, @b@ and @g@ share string character ranges with each other, because they occupy a common sharing-enabled context.
|
|---|
| 970 | 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).
|
|---|
| 971 | The functions @c@, @d@ and @f@ never share anything, because they are in a sharing-disabled context.
|
|---|
| 972 |
|
|---|
| 973 |
|
|---|
| 974 | \begin{figure}
|
|---|
| 975 | \begin{tabular}{ll}
|
|---|
| 976 | \lstinputlisting[language=CFA, firstline=10, lastline=55]{sharectx.run.cfa}
|
|---|
| 977 | &
|
|---|
| 978 | \raisebox{-0.17\totalheight}{\includegraphics{string-sharectx.pdf}} % lower
|
|---|
| 979 | \end{tabular}
|
|---|
| 980 | \caption{Controlling copying vs sharing of strings using \lstinline{string_sharectx}.}
|
|---|
| 981 | \label{fig:string-sharectx}
|
|---|
| 982 | \end{figure}
|
|---|
| 983 |
|
|---|
| 984 |
|
|---|
| 985 | [ TODO: true up with ``is thread local'' (implement that and expand this discussion to give a concurrent example, or adjust this wording) ]
|
|---|
| 986 |
|
|---|
| 987 |
|
|---|
| 988 | \subsection{Future work}
|
|---|
| 989 |
|
|---|
| 990 | To discuss: Unicode
|
|---|
| 991 |
|
|---|
| 992 | To discuss: Small-string optimization
|
|---|
| 993 |
|
|---|
| 994 |
|
|---|
| 995 | \section{Performance assessment}
|
|---|
| 996 | \label{s:PerformanceAssessment}
|
|---|
| 997 |
|
|---|
| 998 | I assessed the \CFA string library's speed and memory usage against strings in \CC STL.
|
|---|
| 999 | The results are presented in even equivalent cases, due to either micro-optimizations foregone, or fundamental costs of the added functionality.
|
|---|
| 1000 | They also show the benefits and tradeoffs, as >100\% effects, of switching to \CFA, with the tradeoff points quantified.
|
|---|
| 1001 | The final test shows the overall win of the \CFA text-sharing mechanism.
|
|---|
| 1002 | It exercises several operations together, showing \CFA enabling clean user code to achieve performance that STL requires less-clean user code to achieve.
|
|---|
| 1003 |
|
|---|
| 1004 | To discuss: general goal of ...
|
|---|
| 1005 | while STL makes you think about memory management, all the time, and if you do, your performance can be great ...
|
|---|
| 1006 | \CFA sacrifices this advantage modestly in exchange for big wins when you're not thinking about memory management.
|
|---|
| 1007 | [Does this position cover all of it?]
|
|---|
| 1008 |
|
|---|
| 1009 | To discuss: revisit HL v LL APIs
|
|---|
| 1010 |
|
|---|
| 1011 | To discuss: revisit no-sharing as STL emulation modes
|
|---|
| 1012 |
|
|---|
| 1013 |
|
|---|
| 1014 | \subsection{Methodology}
|
|---|
| 1015 |
|
|---|
| 1016 | These tests use a \emph{corpus} of strings (string content is immaterial).
|
|---|
| 1017 | For varying-length strings, the mean length comes from a geometric distribution, which implies that lengths much longer than the mean occur frequently.
|
|---|
| 1018 | The string sizes are:
|
|---|
| 1019 | \begin{description}
|
|---|
| 1020 | \item [Fixed-size] all string lengths are of the stated size.
|
|---|
| 1021 | \item [Varying from 1 to N] means the string lengths are drawn from the geometric distribution with a stated mean and all lengths occur.
|
|---|
| 1022 | \item [Varying from 16 to N] means string lengths are drawn from the geometric distribution with the stated mean, but only lengths 16 and above occur; thus, the stated mean is above 16.
|
|---|
| 1023 | \end{description}
|
|---|
| 1024 | The means for the geometric distribution are the X-axis values in experiments.
|
|---|
| 1025 | The special treatment of length 16 deals with the short-string optimization (SSO) in STL @string@, currently not implemented in \CFA.
|
|---|
| 1026 | When an STL string can fit into a heap pointer, the optimization uses the pointer storage to eliminate using the heap.
|
|---|
| 1027 | \begin{c++}
|
|---|
| 1028 | class string {
|
|---|
| 1029 | union {
|
|---|
| 1030 | struct { $\C{// long string, string storage in heap}$
|
|---|
| 1031 | size_t size;
|
|---|
| 1032 | char * strptr;
|
|---|
| 1033 | } lstr;
|
|---|
| 1034 | char sstr[sizeof(lstr)]; $\C{// short string 8-16 characters, in situ}$
|
|---|
| 1035 | };
|
|---|
| 1036 | bool tag; $\C{// string kind, short or long}$
|
|---|
| 1037 | ... $\C{// other storage}$
|
|---|
| 1038 | };
|
|---|
| 1039 | \end{c++}
|
|---|
| 1040 |
|
|---|
| 1041 | When success is illustrated, notwithstanding SSO, a fixed-size or from-16 distribution ensures that extra-optimized cases are not part of the mix on the STL side.
|
|---|
| 1042 | In all experiments that use a corpus, its text is generated and loaded into the system under test before the timed phase begins.
|
|---|
| 1043 |
|
|---|
| 1044 | To discuss: vocabulary for reused case variables
|
|---|
| 1045 |
|
|---|
| 1046 | To discuss: common approach to iteration and quoted rates
|
|---|
| 1047 |
|
|---|
| 1048 | To discuss: hardware and such
|
|---|
| 1049 |
|
|---|
| 1050 | To ensure comparable results, a common memory allocator is used for \CFA and \CC.
|
|---|
| 1051 | The llheap allocator~\cite{Zulfiqar22} is embedded into \CFA and is used standalone with \CC.
|
|---|
| 1052 |
|
|---|
| 1053 |
|
|---|
| 1054 | \subsection{Test: Append}
|
|---|
| 1055 |
|
|---|
| 1056 | This test measures the speed of appending randomly-size text onto a growing string.
|
|---|
| 1057 | \begin{cquote}
|
|---|
| 1058 | \setlength{\tabcolsep}{20pt}
|
|---|
| 1059 | \begin{tabular}{@{}ll@{}}
|
|---|
| 1060 | % \multicolumn{1}{c}{\textbf{fresh}} & \multicolumn{1}{c}{\textbf{reuse}} \\
|
|---|
| 1061 | \begin{cfa}
|
|---|
| 1062 |
|
|---|
| 1063 | for ( ... ) {
|
|---|
| 1064 | @string x;@ // fresh
|
|---|
| 1065 | for ( ... )
|
|---|
| 1066 | x @+=@ ...
|
|---|
| 1067 | }
|
|---|
| 1068 | \end{cfa}
|
|---|
| 1069 | &
|
|---|
| 1070 | \begin{cfa}
|
|---|
| 1071 | string x;
|
|---|
| 1072 | for ( ... ) {
|
|---|
| 1073 | @x = "";@ $\C[1in]{// reuse}$
|
|---|
| 1074 | for ( ... )
|
|---|
| 1075 | x @+=@ ... $\C{// append, alternative x = x + ...}\CRT$
|
|---|
| 1076 | }
|
|---|
| 1077 | \end{cfa}
|
|---|
| 1078 | \end{tabular}
|
|---|
| 1079 | \end{cquote}
|
|---|
| 1080 | The benchmark's outer loop executes ``until a sample-worthy amount of execution has happened'' and an inner loop for ``building up the desired-length string.''
|
|---|
| 1081 | Its subcases include,
|
|---|
| 1082 | \begin{enumerate}[leftmargin=*]
|
|---|
| 1083 | \item
|
|---|
| 1084 | \CFA nosharing/sharing \vs \CC nosharing.
|
|---|
| 1085 | \item
|
|---|
| 1086 | Difference between the logically equivalent operations @x += ...@ \vs @x = x + ...@.
|
|---|
| 1087 | For numeric types, the generated code is equivalence, giving identical performance.
|
|---|
| 1088 | However, for string types there can be a significant difference in performance, especially if this code appears in a loop iterating a large number of times.
|
|---|
| 1089 | This difference might not be intuitive to beginners.
|
|---|
| 1090 | \item
|
|---|
| 1091 | Coding practice where the user's logical allocation is fresh \vs reused.
|
|---|
| 1092 | Here, \emph{reusing a logical allocation}, means that the program variable, into which the user is concatenating, previously held a long string.
|
|---|
| 1093 | In general, a user should not have to care about this difference, yet the STL performs differently in these cases.
|
|---|
| 1094 | Furthermore, if a routine takes a string by reference, if cannot use the fresh approach.
|
|---|
| 1095 | Concretely, both cases incur the cost of copying characters into the target string, but only the allocation-fresh case incurs a further reallocation cost, which is generally paid at points of doubling the length.
|
|---|
| 1096 | For the STL, this cost includes obtaining a fresh buffer from the memory allocator and copying older characters into the new buffer, while \CFA-sharing hides such a cost entirely.
|
|---|
| 1097 | %The fresh \vs reuse distinction is only relevant in the \emph{append} tests.
|
|---|
| 1098 | \end{enumerate}
|
|---|
| 1099 |
|
|---|
| 1100 | \begin{figure}
|
|---|
| 1101 | \centering
|
|---|
| 1102 | \includegraphics{string-graph-peq-cppemu.pdf}
|
|---|
| 1103 | % \includegraphics[width=\textwidth]{string-graph-peq-cppemu.png}
|
|---|
| 1104 | \caption{Average time per iteration (lower is better) with one \lstinline{x += y} invocation, comparing \CFA with STL implementations (given \CFA running in STL emulation mode), and comparing the ``fresh'' with ``reused'' reset styles, at various string sizes.}
|
|---|
| 1105 | \label{fig:string-graph-peq-cppemu}
|
|---|
| 1106 | \end{figure}
|
|---|
| 1107 |
|
|---|
| 1108 | This tests use the varying-from-1 corpus construction, \ie it assumes the STL's advantage of small-string optimization.
|
|---|
| 1109 | \PAB{To discuss: any other case variables introduced in the performance intro}
|
|---|
| 1110 | \VRef[Figure]{fig:string-graph-peq-cppemu} shows this behaviour, by the STL and by \CFA in STL emulation mode.
|
|---|
| 1111 | \CFA reproduces STL's performance, up to a 15\% penalty averaged over the cases shown, diminishing with larger strings, and 50\% in the worst case.
|
|---|
| 1112 | This penalty characterizes the amount of implementation fine tuning done with STL and not done with \CFA in present state.
|
|---|
| 1113 | There is a larger penalty for redeclaring the string each loop iteration (fresh) versus hosting it out of the loop and reseting it to the null string (reuse).
|
|---|
| 1114 | The cost is 40\% averaged over the cases shown and minimally 24\%, and shows up consistently between the \CFA and STL implementations, and increases with larger strings.
|
|---|
| 1115 |
|
|---|
| 1116 | \begin{figure}
|
|---|
| 1117 | \centering
|
|---|
| 1118 | \includegraphics{string-graph-peq-sharing.pdf}
|
|---|
| 1119 | % \includegraphics[width=\textwidth]{string-graph-peq-sharing.png}
|
|---|
| 1120 | \caption{Average time per iteration (lower is better) with one \lstinline{x += y} invocation, comparing \CFA (having implicit sharing activated) with STL, and comparing the ``fresh'' with ``reused'' reset styles, at various string sizes.}
|
|---|
| 1121 | \label{fig:string-graph-peq-sharing}
|
|---|
| 1122 | \end{figure}
|
|---|
| 1123 |
|
|---|
| 1124 | In sharing mode, \CFA makes the fresh/reuse difference disappear, as shown in \VRef[Figure]{fig:string-graph-peq-sharing}.
|
|---|
| 1125 | At append lengths 5 and above, \CFA not only splits the two baseline STL cases, but its slowdown of 16\% over (STL with user-managed reuse) is close to the \CFA-v-STL implementation difference seen with \CFA in STL-emulation mode.
|
|---|
| 1126 |
|
|---|
| 1127 | \begin{figure}
|
|---|
| 1128 | \centering
|
|---|
| 1129 | \includegraphics{string-graph-pta-sharing.pdf}
|
|---|
| 1130 | % \includegraphics[width=\textwidth]{string-graph-pta-sharing.png}
|
|---|
| 1131 | \caption{Average time per iteration (lower is better) with one \lstinline{x = x + y} invocation, comparing \CFA (having implicit sharing activated) with STL.
|
|---|
| 1132 | For context, the results from \VRef[Figure]{fig:string-graph-peq-sharing} are repeated as the bottom bands.
|
|---|
| 1133 | While not a design goal, and not graphed out, \CFA in STL-emulation mode outperformed STL in this case; user-managed allocation reuse did not affect any of the implementations in this case.}
|
|---|
| 1134 | \label{fig:string-graph-pta-sharing}
|
|---|
| 1135 | \end{figure}
|
|---|
| 1136 |
|
|---|
| 1137 | When the user takes a further step beyond the STL's optimal zone, by running @x = x + y@, as in \VRef[Figure]{fig:string-graph-pta-sharing}, the STL's penalty is above $15 \times$ while \CFA's (with sharing) is under $2 \times$, averaged across the cases shown here.
|
|---|
| 1138 | Moreover, the STL's gap increases with string size, while \CFA's converges.
|
|---|
| 1139 |
|
|---|
| 1140 |
|
|---|
| 1141 | \subsubsection{Test: Pass argument}
|
|---|
| 1142 |
|
|---|
| 1143 | STL has a penalty for passing a string by value, which indirectly forces users to think about memory management when communicating values to a function.
|
|---|
| 1144 | \begin{cfa}
|
|---|
| 1145 | void foo( string s );
|
|---|
| 1146 | string s = "abc";
|
|---|
| 1147 | foo( s );
|
|---|
| 1148 | \end{cfa}
|
|---|
| 1149 | With implicit sharing active, \CFA treats this operation as normal and supported.
|
|---|
| 1150 | This test illustrates a main advantage of the \CFA sharing algorithm.
|
|---|
| 1151 | It also has a case in which STL's small-string optimization provides a successful mitigation.
|
|---|
| 1152 |
|
|---|
| 1153 | \begin{figure}
|
|---|
| 1154 | \centering
|
|---|
| 1155 | \includegraphics{string-graph-pbv.pdf}
|
|---|
| 1156 | % \includegraphics[width=\textwidth]{string-graph-pbv.png}
|
|---|
| 1157 | \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.
|
|---|
| 1158 | (a) With \emph{Varying-from-1} corpus construction, in which the STL-only benefit of small-string optimization occurs, in varying degrees, at all string sizes.
|
|---|
| 1159 | (b) With \emph{Fixed-size} corpus construction, in which this benefit applies exactly to strings with length below 16.
|
|---|
| 1160 | [TODO: show version (b)]}
|
|---|
| 1161 | \label{fig:string-graph-pbv}
|
|---|
| 1162 | \end{figure}
|
|---|
| 1163 |
|
|---|
| 1164 | \VRef[Figure]{fig:string-graph-pbv} shows the costs for calling a function that receives a string argument by value.
|
|---|
| 1165 | STL's performance worsens as string length increases, while \CFA has the same performance at all sizes.
|
|---|
| 1166 |
|
|---|
| 1167 | The \CFA cost to pass a string is nontrivial.
|
|---|
| 1168 | The contributor is adding and removing the callee's string handle from the global list.
|
|---|
| 1169 | This cost is $1.5 \times$ to $2 \times$ over STL's when small-string optimization applies, though this cost should be avoidable in the same case, given a \CFA realization of this optimization.
|
|---|
| 1170 | At the larger sizes, when STL has to manage storage for the string, STL runs more than $3 \times$ slower, mainly due to time spent in the general-purpose memory allocator.
|
|---|
| 1171 |
|
|---|
| 1172 |
|
|---|
| 1173 | \subsubsection{Test: Allocate}
|
|---|
| 1174 |
|
|---|
| 1175 | This test directly compares the allocation schemes of the \CFA string with sharing, compared with the STL string.
|
|---|
| 1176 | It treats the \CFA scheme as a form of garbage collection, and the STL scheme as an application of malloc-free.
|
|---|
| 1177 | The test shows that \CFA enables faster speed at a cost in memory usage.
|
|---|
| 1178 |
|
|---|
| 1179 | A garbage collector, afforded the freedom of managed memory, often runs faster than malloc-free (in an amortized analysis, even though it must occasionally stop to collect) because it is able to use its collection time to move objects.
|
|---|
| 1180 | (In the case of the mini-allocator powering the \CFA string library, objects are runs of text.) Moving objects lets fresh allocations consume from a large contiguous store of available memory; the ``bump pointer'' book-keeping for such a scheme is very light.
|
|---|
| 1181 | A malloc-free implementation without the freedom to move objects must, in the general case, allocate in the spaces between existing objects; doing so entails the heavier book-keeping to navigate and maintain a linked structure.
|
|---|
| 1182 |
|
|---|
| 1183 | A garbage collector keeps allocations around for longer than the using program can reach them.
|
|---|
| 1184 | By contrast, a program using malloc-free (correctly) releases allocations exactly when they are no longer reachable.
|
|---|
| 1185 | Therefore, the same harness will use more memory while running under garbage collection.
|
|---|
| 1186 | A garbage collector can minimize the memory overhead by searching for these dead allocations aggressively, that is, by collecting more often.
|
|---|
| 1187 | Tuned in this way, it spends a lot of time collecting, easily so much as to overwhelm its speed advantage from bump-pointer allocation.
|
|---|
| 1188 | If it is tuned to collect rarely, then it leaves a lot of garbage allocated (waiting to be collected) but gains the advantage of little time spent doing collection.
|
|---|
| 1189 |
|
|---|
| 1190 | [TODO: find citations for the above knowledge]
|
|---|
| 1191 |
|
|---|
| 1192 | The speed for memory tradeoff is, therefore, standard for comparisons like \CFA--STL string allocations.
|
|---|
| 1193 | The test verifies that it is so and quantifies the returns available.
|
|---|
| 1194 |
|
|---|
| 1195 | These tests manipulate a tuning knob that controls how much extra space to use.
|
|---|
| 1196 | Specific values of this knob are not user-visible and are not presented in the results here.
|
|---|
| 1197 | Instead, its two effects (amount of space used and time per operation) are shown.
|
|---|
| 1198 | The independent variable is the liveness target, which is the fraction of the text buffer that is in use at the end of a collection.
|
|---|
| 1199 | The allocator will expand its text buffer during a collection if the actual fraction live exceeds this target.
|
|---|
| 1200 |
|
|---|
| 1201 | This experiment's driver allocates strings by constructing a string handle as a local variable then looping over recursive calls.
|
|---|
| 1202 | The time measurement is of nanoseconds per such allocating call.
|
|---|
| 1203 | The arrangement of recursive calls and their fan-out (iterations per recursion level) makes some of the strings long-lived and some of them short-lived.
|
|---|
| 1204 | 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.
|
|---|
| 1205 | The run presented in this section used a call depth of 1000 and a fan-out of 1.006, which means that approximately one call in 167 makes two recursive calls, while the rest make one.
|
|---|
| 1206 | This sizing was chosen to keep the amounts of consumed memory within the machine's last-level cache.
|
|---|
| 1207 |
|
|---|
| 1208 | \begin{figure}
|
|---|
| 1209 | \centering
|
|---|
| 1210 | \includegraphics{string-graph-allocn.pdf}
|
|---|
| 1211 | % \includegraphics[width=\textwidth]{string-graph-allocn.png}
|
|---|
| 1212 | \caption{Space and time performance, under varying fraction-live targets, for the five string lengths shown, at (\emph{Fixed-size} corpus construction.
|
|---|
| 1213 | [MISSING] The identified clusters are for the default fraction-live target, which is 30\%.
|
|---|
| 1214 | MISSING: STL results, typically just below the 0.5--0.9 \CFA segment.
|
|---|
| 1215 | All runs keep an average of 836 strings live, and the median string lifetime is ?? allocations.}
|
|---|
| 1216 | \label{fig:string-graph-allocn}
|
|---|
| 1217 | \end{figure}
|
|---|
| 1218 |
|
|---|
| 1219 | \VRef[Figure]{fig:string-graph-allocn} shows the results of this experiment.
|
|---|
| 1220 | At all string sizes, varying the liveness threshold gives offers speed-for-space tradeoffs relative to STL.
|
|---|
| 1221 | At the default liveness threshold, all measured string sizes see a ??\%--??\% speedup for a ??\%--??\% increase in memory footprint.
|
|---|
| 1222 |
|
|---|
| 1223 |
|
|---|
| 1224 | \subsubsection{Test: Normalize}
|
|---|
| 1225 |
|
|---|
| 1226 | This test is more applied than the earlier ones.
|
|---|
| 1227 | It combines the effects of several operations.
|
|---|
| 1228 | 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.
|
|---|
| 1229 |
|
|---|
| 1230 | To motivate: edits being rare
|
|---|
| 1231 |
|
|---|
| 1232 | The program is doing a specialized find-replace operation on a large body of text.
|
|---|
| 1233 | In the program under test, the replacement is just to erase a magic character.
|
|---|
| 1234 | 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.
|
|---|
| 1235 | The challenge is to apply this packaged function across chunks taken from the large body.
|
|---|
| 1236 | Using the \CFA string library, the most natural way to write the helper module's function also works well in the adapted context.
|
|---|
| 1237 | 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.
|
|---|
| 1238 |
|
|---|
| 1239 | \begin{lstlisting}
|
|---|
| 1240 | void processItem( string & item ) {
|
|---|
| 1241 | // find issues in item and fix them
|
|---|
| 1242 | }
|
|---|
| 1243 | \end{lstlisting}
|
|---|
