source: doc/theses/mike_brooks_MMath/background.tex

Last change on this file was e0350e0, checked in by Michael Brooks <mlbrooks@…>, 9 days ago

Recent rework of string benchmarks

  • Property mode set to 100644
File size: 73.1 KB
Line 
1\chapter{Background}
2
3Since this work builds on C, it is necessary to explain the C mechanisms and their shortcomings for array, linked list, and string.
4
5
6\section{Ill-Typed Expressions}
7
8C reports many ill-typed expressions as warnings.
9For example, these attempts to assign @y@ to @x@ and vice-versa are obviously ill-typed.
10\lstinput{12-15}{bkgd-c-tyerr.c}
11with warnings:
12\begin{cfa}
13warning: assignment to 'float *' from incompatible pointer type 'void (*)(void)'
14warning: assignment to 'void (*)(void)' from incompatible pointer type 'float *'
15\end{cfa}
16Similarly,
17\lstinput{17-19}{bkgd-c-tyerr.c}
18with warning:
19\begin{cfa}
20warning: passing argument 1 of 'f' from incompatible pointer type
21note: expected 'void (*)(void)' but argument is of type 'float *'
22\end{cfa}
23with a segmentation fault at runtime.
24Clearly, @gcc@ understands these ill-typed case, and yet allows the program to compile, which seems inappropriate.
25Compiling with flag @-Werror@, which turns warnings into errors, is often too pervasive, because some warnings are just warnings, \eg an unused variable.
26In the following discussion, \emph{ill-typed} means giving a nonzero @gcc@ exit condition with a message that discusses typing.
27Note, \CFA's type-system rejects all these ill-typed cases as type mismatch errors.
28
29% That @f@'s attempt to call @g@ fails is not due to 3.14 being a particularly unlucky choice of value to put in the variable @pi@.
30% Rather, it is because obtaining a program that includes this essential fragment, yet exhibits a behaviour other than "doomed to crash," is a matter for an obfuscated coding competition.
31
32% A "tractable syntactic method for proving the absence of certain program behaviours by classifying phrases according to the kinds of values they compute"*1 rejected the program.
33% The behaviour (whose absence is unprovable) is neither minor nor unlikely.
34% The rejection shows that the program is ill-typed.
35%
36% Yet, the rejection presents as a GCC warning.
37% *1  TAPL-pg1 definition of a type system
38
39% reading C declaration: https://c-faq.com/decl/spiral.anderson.html
40
41
42\section{Reading Declarations}
43
44A significant area of confusion is reading C declarations, which results from interesting design choices.
45\begin{itemize}[leftmargin=*]
46\item
47In C, it is possible to have a value and a pointer to it.
48\begin{cfa}
49int i = 3, * pi = &i;
50\end{cfa}
51Extending this idea, it should be possible to have an array of values and pointer to it.
52\begin{cfa}
53int a[5] = { 1, 2, 3, 4, 5 },  * pa[5] = &a;
54\end{cfa}
55However, the declaration of @pa@ is incorrect because dimension has higher priority than pointer, so the declaration means an array of 5 pointers to integers.
56The declarations for the two interpretations of @* [5]@ are:
57\begin{cquote}
58\begin{tabular}[t]{@{}ll@{\hspace{15pt}}|@{\hspace{15pt}}ll@{}}
59\begin{cfa}
60int (* pa)[5]
61\end{cfa}
62&
63\raisebox{-0.4\totalheight}{\includegraphics{PtrToArray.pdf}}
64&
65\begin{cfa}
66int * ap[5]
67\end{cfa}
68&
69\raisebox{-0.75\totalheight}{\includegraphics{ArrayOfPtr.pdf}}
70\end{tabular}
71\end{cquote}
72If the priorities of dimension and pointer were reversed, the declarations become more intuitive: @int * pa[5]@ and @int * (ap[5])@.
73\item
74This priority inversion extends into an expression between dereference and subscript, so usage syntax mimics declaration.
75\begin{cquote}
76\setlength{\tabcolsep}{20pt}
77\begin{tabular}{@{}ll@{}}
78\begin{cfa}
79int (* pa)[5]
80      (*pa)[i] += 1;
81\end{cfa}
82&
83\begin{cfa}
84int * ap[5]
85      *ap[i] += 1;
86\end{cfa}
87\end{tabular}
88\end{cquote}
89(\VRef{s:ArraysDecay} shows pointer decay allows the first form to be written @pa[i] += 1@, which is further syntax confusion.)
90Again, if the priorities were reversed, the expressions become more intuitive: @*pa[i] += 1@ and @*(ap[i]) += 1@.
91Note, a similar priority inversion exists between deference @*@ and field selection @.@ (period), so @*ps.f@ means @*(ps.f)@;
92this anomaly is \emph{fixed} with operator @->@, which performs the two operations in the more intuitive order: @sp->f@ $\Rightarrow$ @(*sp).f@.
93\end{itemize}
94While attempting to make the declaration and expression contexts consistent is a laudable goal, it has not worked out in practice, even though Dennis Richie believed otherwise:
95\begin{quote}
96In spite of its difficulties, I believe that the C's approach to declarations remains plausible, and am comfortable with it; it is a useful unifying principle.~\cite[p.~12]{Ritchie93}
97\end{quote}
98After all, reading a C array type is easy: just read it from the inside out, and know when to look left and when to look right!
99Unfortunately, \CFA cannot correct these operator priority inversions without breaking C compatibility.
100
101TODO: rephrase to acknowledge the "clockwise rule" https://c-faq.com/decl/spiral.anderson.html
102
103The alternative solution is for \CFA to provide its own type, variable and routine declarations, using a more intuitive syntax.
104The new declarations place qualifiers to the left of the base type, while C declarations place qualifiers to the right of the base type.
105The qualifiers have the same syntax and semantics in \CFA as in C, so there is nothing to learn.
106Then, a \CFA declaration is read left to right, where a function return-type is enclosed in brackets @[@\,@]@.
107\begin{cquote}
108\begin{tabular}{@{}l@{\hspace{3em}}ll@{}}
109\multicolumn{1}{c@{\hspace{3em}}}{\textbf{C}}   & \multicolumn{1}{c}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{read left to right}}   \\
110\begin{cfa}
111int @*@ x1 @[5]@;
112int @(*@x2@)[5]@;
113int @(*@f( int p )@)[5]@;
114\end{cfa}
115&
116\begin{cfa}
117@[5] *@ int x1;
118@* [5]@ int x2;
119@[ * [5] int ]@ f( int p );
120\end{cfa}
121&
122\begin{cfa}
123// array of 5 pointers to int
124// pointer to array of 5 int
125// function returning pointer to array of 5 ints
126\end{cfa}
127\\
128& &
129\LstCommentStyle{//\ \ \ and taking an int argument}
130\end{tabular}
131\end{cquote}
132As declaration size increases, it becomes corresponding difficult to read and understand the C form, whereas reading and understanding a \CFA declaration has linear complexity.
133Note, writing declarations left to right is common in other programming languages, where the function return-type is often placed after the parameter declarations, \eg \CC \lstinline[language=C++]{auto f( int ) -> int}.
134(Note, putting the return type at the end deviates from where the return value logically appears in an expression, @x = f(...)@ versus @f(...) = x@.)
135Interestingly, programmers normally speak a declaration from left to right, regardless of how it is written.
136(It is unclear if Hebrew or Arabic speakers, say declarations right to left.)
137
138\VRef[Table]{bkgd:ar:usr:avp} introduces the many layers of the C and \CFA array story, where the \CFA story is discussion in \VRef[Chapter]{c:Array}.
139The \CFA-thesis column shows the new array declaration form, which is my contribution to safety and ergonomics.
140The table shows there are multiple yet equivalent forms for the array types under discussion, and subsequent discussion shows interactions with orthogonal (but easily confused) language features.
141Each row of the table shows alternate syntactic forms.
142The simplest occurrences of types distinguished in the preceding discussion are marked with $\triangleright$.
143Removing the declared variable @x@, gives the type used for variable, structure field, cast, or error messages.
144Unfortunately, parameter declarations have more syntactic forms and rules.
145
146\begin{table}
147\centering
148\caption{Syntactic Reference for Array vs Pointer. Includes interaction with \lstinline{const}ness.}
149\label{bkgd:ar:usr:avp}
150\begin{tabular}{ll|l|l|l}
151        & Description & \multicolumn{1}{c|}{C} & \multicolumn{1}{c|}{\CFA}  & \multicolumn{1}{c}{\CFA-thesis} \\
152        \hline
153$\triangleright$ & value & @T x;@ & @T x;@ & \\
154        \hline
155        & immutable value & @const T x;@ & @const T x;@ & \\
156        & & @T const x;@ & @T const x;@ & \\
157        \hline \hline
158$\triangleright$ & pointer to value & @T * x;@ & @* T x;@ & \\
159        \hline
160        & immutable ptr. to val. & @T * const x;@ & @const * T x;@ & \\
161        \hline
162        & ptr. to immutable val. & @const T * x;@ & @* const T x;@ & \\
163        & & @T const * x;@ & @* T const x;@ & \\
164        \hline \hline
165$\triangleright$ & array of value & @T x[10];@ & @[10] T x@ & @array(T, 10) x@ \\
166        \hline
167        & ar.\ of immutable val. & @const T x[10];@ & @[10] const T x@ & @const array(T, 10) x@ \\
168        & & @T const x[10];@ & @[10] T const x@ & @array(T, 10) const x@ \\
169        \hline
170        & ar.\ of ptr.\ to value & @T * x[10];@ & @[10] * T x@ & @array(T *, 10) x@ \\
171        & & & & @array(* T, 10) x@ \\
172        \hline
173        & ar.\ of imm. ptr.\ to val. & @T * const x[10];@ & @[10] const * T x@ & @array(* const T, 10) x@ \\
174        & & & & @array(const * T, 10) x@ \\
175        \hline
176        & ar.\ of ptr.\ to imm. val. & @const T * x[10];@ & @[10] * const T x@ & @array(const T *, 10) x@ \\
177        & & @T const * x[10];@ & @[10] * T const x@ & @array(* const T, 10) x@ \\
178        \hline \hline
179$\triangleright$ & ptr.\ to ar.\ of value & @T (*x)[10];@ & @* [10] T x@ & @* array(T, 10) x@ \\
180        \hline
181        & imm. ptr.\ to ar.\ of val. & @T (* const x)[10];@ & @const * [10] T x@ & @const * array(T, 10) x@ \\
182        \hline
183        & ptr.\ to ar.\ of imm. val. & @const T (*x)[10];@ & @* [10] const T x@ & @* const array(T, 10) x@ \\
184        & & @T const (*x)[10];@ & @* [10] T const x@ & @* array(T, 10) const x@ \\
185        \hline
186        & ptr.\ to ar.\ of ptr.\ to val. & @T *(*x)[10];@ & @* [10] * T x@ & @* array(T *, 10) x@ \\
187        & & & & @* array(* T, 10) x@ \\
188        \hline
189\end{tabular}
190\end{table}
191
192
193\section{Array}
194\label{s:Array}
195
196At the start, the C language designers made a significant design mistake with respect to arrays.
197\begin{quote}
198In C, there is a strong relationship between pointers and arrays, strong enough that pointers and arrays really should be treated simultaneously.
199Any operation which can be achieved by array subscripting can also be done with pointers.~\cite[p.~93]{C:old}
200\end{quote}
201Accessing any storage requires pointer arithmetic, even if it is just base-displacement addressing in an instruction.
202The conjoining of pointers and arrays could also be applied to structures, where a pointer references a structure field like an array element.
203Finally, while subscripting involves pointer arithmetic (as does a field reference @x.y.z@), the computation is complex for multi-dimensional arrays and requires array descriptors to know stride lengths along dimensions.
204Many C errors result from manually performing pointer arithmetic instead of using language subscripting so the compiler performs the arithmetic.
205
206Some modern C textbooks and web sites erroneously suggest manual pointer arithmetic is faster than subscripting.
207When compiler technology was young, this statement might have been true.
208However, a sound and efficient C program coupled with a modern C compiler does not require explicit pointer arithmetic.
209For example, the @gcc@ compiler at @-O3@ generates identical code for the following two summation loops.
210\begin{cquote}
211\vspace*{-10pt}
212\begin{cfa}
213int a[1000], sum;
214\end{cfa}
215\setlength{\tabcolsep}{20pt}
216\begin{tabular}{@{}ll@{}}
217\begin{cfa}
218for ( int i = 0; i < 1000; i += 1 ) {
219        sum += a[i];
220}
221\end{cfa}
222&
223\begin{cfa}
224for ( int * ip = a ; ip < &a[1000]; ip += 1 ) {
225        sum += *ip;
226}
227\end{cfa}
228\end{tabular}
229\end{cquote}
230I believe it is possible to refute any code examples purporting to show pointer arithmetic is faster than subscripting.
231This believe stems from the performance work I did on \CFA arrays, where it is possible to generate equivalent \CFA subscripting and performance to C subscripting.
232
233Unfortunately, C semantics want a programmer to \emph{believe} an array variable is a \emph{pointer to its first element}.
234This desire becomes apparent by a detailed inspection of an array declaration.
235\lstinput{34-34}{bkgd-carray-arrty.c}
236The inspection begins by using @sizeof@ to provide program semantics for the intuition of an expression's type.
237An architecture with 64-bit pointer size is used, to remove irrelevant details.
238\lstinput{35-36}{bkgd-carray-arrty.c}
239Now consider the @sizeof@ expressions derived from @ar@, modified by adding pointer-to and first-element (and including unnecessary parentheses to avoid any confusion about precedence).
240\lstinput{37-40}{bkgd-carray-arrty.c}
241Given that arrays are contiguous and the size of @float@ is 4, then the size of @ar@ with 10 floats being 40 bytes is common reasoning for C programmers.
242Equally, C programmers know the size of a pointer to the first array element is 8.
243% Now, set aside for a moment the claim that this first assertion is giving information about a type.
244Clearly, an array and a pointer to its first element are different.
245
246In fact, the idea that there is such a thing as a pointer to an array may be surprising.
247It it is not the same thing as a pointer to the first element.
248\lstinput{42-45}{bkgd-carray-arrty.c}
249The first assignment generates:
250\begin{cfa}
251warning: assignment to `float (*)[10]' from incompatible pointer type `float *'
252\end{cfa}
253and the second assignment generates the opposite.
254
255The inspection now refutes any suggestion that @sizeof@ is informing about allocation rather than type information.
256Note, @sizeof@ has two forms, one operating on an expression and the other on a type.
257Using the type form yields the same results as the prior expression form.
258\lstinput{46-49}{bkgd-carray-arrty.c}
259The results are also the same when there is no allocation at all.
260This time, starting from a pointer-to-array type:
261\lstinput{51-57}{bkgd-carray-arrty.c}
262Hence, in all cases, @sizeof@ is reporting on type information.
263
264Therefore, thinking of an array as a pointer to its first element is too simplistic an analogue and it is not backed up by the type system.
265This misguided analogue works for a single-dimension array but there is no advantage other than possibly teaching beginner programmers about basic runtime array-access.
266
267Continuing, there is a short form for declaring array variables using length information provided implicitly by an initializer.
268\lstinput{59-62}{bkgd-carray-arrty.c}
269The compiler counts the number of initializer elements and uses this value as the first dimension.
270Unfortunately, the implicit element counting does not extend to dimensions beyond the first.
271\lstinput{64-67}{bkgd-carray-arrty.c}
272
273My observation is recognizing:
274\begin{itemize}[leftmargin=*,itemsep=0pt]
275        \item There is value in using a type that knows its size.
276        \item The type pointer to the (first) element does not.
277        \item C \emph{has} a type that knows the whole picture: array, \eg @T[10]@.
278        \item This type has all the usual derived forms, which also know the whole picture.
279        A noteworthy example is pointer to array, \eg @T (*)[10]@.
280\end{itemize}
281
282
283\subsection{Arrays Decay and Pointers Diffract}
284\label{s:ArraysDecay}
285
286The last section established the difference among these four types:
287\lstinput{3-6}{bkgd-carray-decay.c}
288But the expression used for obtaining the pointer to the first element is pedantic.
289The root of all C programmer experience with arrays is the shortcut
290\lstinput{8-8}{bkgd-carray-decay.c}
291which reproduces @pa0@, in type and value:
292\lstinput{9-9}{bkgd-carray-decay.c}
293The validity of this initialization is unsettling, in the context of the facts established in \VRef{s:Array}.
294Notably, it initializes name @pa0x@ from expression @ar@, when they are not of the same type:
295\lstinput{10-10}{bkgd-carray-decay.c}
296
297So, C provides an implicit conversion from @float[10]@ to @float *@.
298\begin{quote}
299Except when it is the operand of the @sizeof@ operator, or the unary @&@ operator, or is a string literal used to
300initialize an array an expression that has type ``array of \emph{type}'' is converted to an expression with type
301``pointer to \emph{type}'' that points to the initial element of the array object~\cite[\S~6.3.2.1.3]{C11}
302\end{quote}
303This phenomenon is the famous \newterm{pointer decay}, which is a decay of an array-typed expression into a pointer-typed one.
304It is worthy to note that the list of exceptional cases does not feature the occurrence of @ar@ in @ar[i]@.
305Thus, subscripting happens on pointers not arrays.
306
307Subscripting proceeds first with pointer decay, if needed.
308Next, \cite[\S~6.5.2.1.2]{C11} explains that @ar[i]@ is treated as if it were @(*((a)+(i)))@.
309\cite[\S~6.5.6.8]{C11} explains that the addition, of a pointer with an integer type, is defined only when the pointer refers to an element that is in an array, with a meaning of @i@ elements away from, which is valid if @ar@ is big enough and @i@ is small enough.
310Finally, \cite[\S~6.5.3.2.4]{C11} explains that the @*@ operator's result is the referenced element.
311Taken together, these rules illustrate that @ar[i]@ and @i[a]@ mean the same thing!
312
313Subscripting a pointer when the target is standard-inappropriate is still practically well-defined.
314While the standard affords a C compiler freedom about the meaning of an out-of-bound access, or of subscripting a pointer that does not refer to an array element at all,
315the fact that C is famously both generally high-performance, and specifically not bound-checked, leads to an expectation that the runtime handling is uniform across legal and illegal accesses.
316Moreover, consider the common pattern of subscripting on a @malloc@ result:
317\begin{cfa}
318float * fs = malloc( 10 * sizeof(float) );
319fs[5] = 3.14;
320\end{cfa}
321The @malloc@ behaviour is specified as returning a pointer to ``space for an object whose size is'' as requested (\cite[\S~7.22.3.4.2]{C11}).
322But \emph{nothing} more is said about this pointer value, specifically that its referent might \emph{be} an array allowing subscripting.
323
324Under this assumption, a pointer being subscripted (or added to, then dereferenced) by any value (positive, zero, or negative), gives a view of the program's entire address space, centred around the @p@ address, divided into adjacent @sizeof(*p)@ chunks, each potentially (re)interpreted as @typeof(*p)@.
325I call this phenomenon \emph{array diffraction}, which is a diffraction of a single-element pointer into the assumption that its target is in the middle of an array whose size is unlimited in both directions.
326No pointer is exempt from array diffraction.
327No array shows its elements without pointer decay.
328
329A further pointer--array confusion, closely related to decay, occurs in parameter declarations.
330\cite[\S~6.7.6.3.7]{C11} explains that when an array type is written for a parameter,
331the parameter's type becomes a type that can be summarized as the array-decayed type.
332The respective handling of the following two parameter spellings shows that the array and pointer versions are identical.
333\lstinput{12-16}{bkgd-carray-decay.c}
334As the @sizeof(x)@ meaning changed, compared with when run on a similarly-spelled local variable declaration,
335@gcc@ also gives this code the warning for the first assertion:
336\begin{cfa}
337warning: 'sizeof' on array function parameter 'x' will return size of 'float *'
338\end{cfa}
339The caller of such a function is left with the reality that a pointer parameter is a pointer, no matter how it is spelled:
340\lstinput{18-21}{bkgd-carray-decay.c}
341This fragment gives the warning for the first argument, in the second call.
342\begin{cfa}
343warning: 'f' accessing 40 bytes in a region of size 4
344\end{cfa}
345
346The shortened parameter syntax @T x[]@ is a further way to spell \emph{pointer}.
347Note the opposite meaning of this spelling now, compared with its use in local variable declarations.
348This point of confusion is illustrated in:
349\lstinput{23-30}{bkgd-carray-decay.c}
350Note, \CC gives a warning for the initialization of @cp@.
351\begin{cfa}
352warning: ISO C++ forbids converting a string constant to 'char*'
353\end{cfa}
354and C gives a warning at the call of @edit@, if @const@ is added to the declaration of @cp@.
355\begin{cfa}
356warning: passing argument 1 of 'edit' discards 'const' qualifier from pointer target type
357\end{cfa}
358The basic two meanings, with a syntactic difference helping to distinguish, are illustrated in the declarations of @ca@ \vs @cp@, whose subsequent @edit@ calls behave differently.
359The syntax-caused confusion is in the comparison of the first and last lines, both of which use a literal to initialize an object declared with spelling @T x[]@.
360But these initialized declarations get opposite meanings, depending on whether the object is a local variable or a parameter!
361
362In summary, when a function is written with an array-typed parameter,
363\begin{itemize}[leftmargin=*]
364        \item an appearance of passing an array by value is always an incorrect understanding,
365        \item a dimension value, if any is present, is ignored,
366        \item pointer decay is forced at the call site and the callee sees the parameter having the decayed type.
367\end{itemize}
368
369Pointer decay does not affect pointer-to-array types, because these are already pointers, not arrays.
370As a result, a function with a pointer-to-array parameter sees the parameter exactly as the caller does:
371\par\noindent
372\begin{tabular}{@{\hspace*{-0.75\parindentlnth}}l@{}l@{}}
373\lstinput{32-36}{bkgd-carray-decay.c}
374&
375\lstinput{38-42}{bkgd-carray-decay.c}
376\end{tabular}
377\par\noindent
378\VRef[Table]{bkgd:ar:usr:decay-parm} gives the reference for the decay phenomenon seen in parameter declarations.
379
380\begin{table}
381\caption{Syntactic Reference for Decay during Parameter-Passing.
382Includes interaction with \lstinline{const}ness, where \emph{immutable} refers to a restriction on the callee's ability.}
383\label{bkgd:ar:usr:decay-parm}
384\centering
385\begin{tabular}{llllll}
386        & Description & Type & Parameter Declaration & \CFA  \\
387        \hline
388        & & & @T * x,@ & @* T x,@ \\
389$\triangleright$ & pointer to value & @T *@ & @T x[10],@ & @[10] T x,@ \\
390        & & & @T x[],@ & @[] T x,@ \\
391        \hline
392        & & & @T * const x,@ & @const * T x@ \\
393        & immutable ptr.\ to val. & @T * const@ & @T x[const 10],@ & @[const 10] T x,@ \\
394        & & & @T x[const],@ & @[const] T x,@\\
395        \hline
396        & & & @const T * x,@ & @ * const T x,@ \\
397        & &     & @T const * x,@ & @ * T const x,@ \\
398        & ptr.\ to immutable val. & @const T *@ & @const T x[10],@ & @[10] const T x,@ \\
399        & & @T const *@ & @T const x[10],@ &  @[10] T const x,@ \\
400        & & & @const T x[],@ & @[] const T x,@ \\
401        & & & @T const x[],@ & @[] T const x,@ \\
402        \hline \hline
403        & & & @T (*x)[10],@ & @* [10] T x,@ \\
404$\triangleright$ & ptr.\ to ar.\ of val. & @T(*)[10]@ & @T x[3][10],@ & @[3][10] T x,@ \\
405        & & & @T x[][10],@ & @[][10] T x,@ \\
406        \hline
407        & & & @T ** x,@ & @** T x,@ \\
408        & ptr.\ to ptr.\ to val. & @T **@ & @T * x[10],@ & @[10] * T x,@ \\
409        & & & @T * x[],@ & @[] * T x,@ \\
410        \hline
411        & ptr.\ to ptr.\ to imm.\ val. & @const char **@ & @const char * argv[],@ & @[] * const char argv,@ \\
412        & & & \emph{others elided} & \emph{others elided} \\
413        \hline
414\end{tabular}
415\end{table}
416
417
418\subsection{Variable-length Arrays}
419
420As of C99, the C standard supports a \newterm{variable length array} (VLA)~\cite[\S~6.7.5.2.5]{C99}, providing a dynamic-fixed array feature \see{\VRef{s:ArrayIntro}}.
421Note, the \CC standard does not support VLAs, but @g++@ provides them.
422A VLA is used when the desired number of array elements is \emph{unknown} at compile time.
423\begin{cfa}
424size_t  cols;
425scanf( "%d", &cols );
426double ar[cols];
427\end{cfa}
428The array dimension is read from outside the program and used to create an array of size @cols@ on the stack.
429The VLA is implemented by the @alloca@ routine, which bumps the stack pointer.
430Unfortunately, there is significant misinformation about VLAs, \eg the stack size is limited (small), or VLAs cause stack failures or are inefficient.
431VLAs exist as far back as Algol W~\cite[\S~5.2]{AlgolW} and are a sound and efficient data type.
432For types with a dynamic-fixed stack, \eg coroutines or user-level threads, large VLAs can overflow the stack without appropriately sizing the stack, so heap allocation is used when the array size is unbounded.
433
434
435\subsection{Multidimensional Arrays}
436\label{toc:mdimpl}
437
438% TODO: introduce multidimensional array feature and approaches
439
440When working with arrays, \eg linear algebra, array dimensions are referred to as \emph{rows} and \emph{columns} for a matrix, adding \emph{planes} for a cube.
441(There is little terminology for higher dimensional arrays.)
442For example, an acrostic poem\footnote{A type of poetry where the first, last or other letters in a line spell out a particular word or phrase in a vertical column.}
443can be treated as a grid of characters, where the rows are the text and the columns are the embedded keyword(s).
444Within a poem, there is the concept of a \newterm{slice}, \eg a row is a slice for the poem text, a column is a slice for a keyword.
445In general, the dimensioning and subscripting for multidimensional arrays has two syntactic forms: @m[r,c]@ or @m[r][c]@.
446
447Commonly, an array, matrix, or cube, is visualized (especially in mathematics) as a contiguous row, rectangle, or block.
448This conceptualization is reenforced by subscript ordering, \eg $m_{r,c}$ for a matrix and $c_{p,r,c}$ for a cube.
449Few programming languages differ from the mathematical subscript ordering.
450However, computer memory is flat, and hence, array forms are structured in memory as appropriate for the runtime system.
451The closest representation to the conceptual visualization is for an array object to be contiguous, and the language structures this memory using pointer arithmetic to access the values using various subscripts.
452This approach still has degrees of layout freedom, such as row or column major order, \ie juxtaposed rows or columns in memory, even when the subscript order remains fixed.
453For example, programming languages like MATLAB, Fortran, Julia and R store matrices in column-major order since they are commonly used for processing column-vectors in tabular data sets but retain row-major subscripting to match with mathematical notation.
454In general, storage layout is hidden by subscripting, and only appears when passing arrays among different programming languages or accessing specific hardware.
455
456\VRef[Figure]{f:FixedVariable} shows two C90 approaches for manipulating a contiguous matrix.
457Note, C90 does not support VLAs.
458The fixed-dimension approach (left) uses the type system;
459however, it requires all dimensions except the first to be specified at compile time, \eg @m[][6]@, allowing all subscripting stride calculations to be generated with constants.
460Hence, every matrix passed to @fp1@ must have exactly 6 columns but the row size can vary.
461The variable-dimension approach (right) ignores (violates) the type system, \ie argument and parameters types do not match, and subscripting is performed manually using pointer arithmetic in the macro @sub@.
462
463\begin{figure}
464\begin{tabular}{@{}l@{\hspace{40pt}}l@{}}
465\multicolumn{1}{c}{\textbf{Fixed Dimension}} & \multicolumn{1}{c}{\textbf{Variable Dimension}} \\
466\begin{cfa}
467
468void fp1( int rows, int m[][@6@] ) {
469        ...  printf( "%d ", @m[r][c]@ );  ...
470}
471int fm1[4][@6@], fm2[6][@6@]; // no VLA
472// initialize matrixes
473fp1( 4, fm1 ); // implicit 6 columns
474fp1( 6, fm2 );
475\end{cfa}
476&
477\begin{cfa}
478#define sub( m, r, c ) *(m + r * sizeof( m[0] ) + c)
479void fp2( int rows, int cols, int *m ) {
480        ...  printf( "%d ", @sub( m, r, c )@ );  ...
481}
482int vm1[@4@][@4@], vm2[@6@][@8@]; // no VLA
483// initialize matrixes
484fp2( 4, 4, vm1 );
485fp2( 6, 8, vm2 );
486\end{cfa}
487\end{tabular}
488\caption{C90 Fixed \vs Variable Contiguous Matrix Styles}
489\label{f:FixedVariable}
490\end{figure}
491
492Many languages allow multidimensional arrays-of-arrays, \eg in Pascal or \CC.
493\begin{cquote}
494\setlength{\tabcolsep}{15pt}
495\begin{tabular}{@{}ll@{}}
496\begin{pascal}
497var m : array[0..4, 0..4] of Integer;  (* matrix *)
498type AT = array[0..4] of Integer;  (* array type *)
499type MT = array[0..4] of AT;  (* array of array type *)
500var aa : MT;  (* array of array variable *)
501m@[1][2]@ := 1;   aa@[1][2]@ := 1 (* same subscripting *)
502\end{pascal}
503&
504\begin{c++}
505int m[5][5];
506
507typedef vector< vector<int> > MT;
508MT vm( 5, vector<int>( 5 ) );
509m@[1][2]@ = 1;  aa@[1][2]@ = 1;
510\end{c++}
511\end{tabular}
512\end{cquote}
513The language decides if the matrix and array-of-array are laid out the same or differently.
514For example, an array-of-array may be an array of row pointers to arrays of columns, so the rows may not be contiguous in memory nor even the same length (triangular matrix).
515Regardless, there is usually a uniform subscripting syntax masking the memory layout, even though a language could differentiated between the two forms using subscript syntax, \eg @m[1,2]@ \vs @aa[1][2]@.
516Nevertheless, controlling memory layout can make a difference in what operations are allowed and in performance (caching/NUMA effects).
517
518C also provides non-contiguous arrays-of-arrays.
519\begin{cfa}
520int m[5][5];                                                    $\C{// contiguous}$
521int * aa[5];                                                    $\C{// non-contiguous}$
522\end{cfa}
523both with different memory layout using the same subscripting, and both with different degrees of issues.
524The focus of this work is on the contiguous multidimensional arrays in C.
525The reason is that programmers are often forced to use the more complex array-of-array form when a contiguous array would be simpler, faster, and safer.
526Nevertheless, the C array-of-array form is still important for special circumstances.
527
528\VRef[Figure]{f:ContiguousNon-contiguous} shows a powerful extension made in C99 for manipulating contiguous \vs non-contiguous arrays.\footnote{C90 also supported non-contiguous arrays.}
529For contiguous-array arguments (including VLA), C99 conjoins one or more of the parameters as a downstream dimension(s), \eg @cols@, implicitly using this parameter to compute the row stride of @m@.
530There is now sufficient information to support array copying and subscript checking along the columns to prevent changing the argument or buffer-overflow problems, but neither feature is provided.
531If the declaration of @fc@ is changed to:
532\begin{cfa}
533void fc( int rows, int cols, int m[@rows@][@cols@] ) ...
534\end{cfa}
535it is possible for C to perform bound checking across all subscripting.
536While this contiguous-array capability is a step forward, it is still the programmer's responsibility to manually manage the number of dimensions and their sizes, both at the function definition and call sites.
537That is, the array does not automatically carry its structure and sizes for use in computing subscripts.
538While the non-contiguous style in @faa@ looks very similar to @fc@, the compiler only understands the unknown-sized array of row pointers, and it relies on the programmer to traverse the columns in a row correctly with a correctly bounded loop index.
539Specifically, there is no requirement that the rows are the same length, like a poem with different length lines.
540
541\begin{figure}
542\begin{tabular}{@{}ll@{}}
543\multicolumn{1}{c}{\textbf{Contiguous}} & \multicolumn{1}{c}{\textbf{ Non-contiguous}} \\
544\begin{cfa}
545void fc( int rows, @int cols@, int m[ /* rows */ ][@cols@] ) {
546        for ( size_t  r = 0; r < rows; r += 1 ) {
547                for ( size_t  c = 0; c < cols; c += 1 )
548                        ...  @m[r][c]@  ...
549}
550int m@[5][5]@;
551for ( int r = 0; r < 5; r += 1 ) {
552
553        for ( int c = 0; c < 5; c += 1 )
554                m[r][c] = r + c;
555}
556fc( 5, 5, m );
557\end{cfa}
558&
559\begin{cfa}
560void faa( int rows, int cols, int * m[ @/* cols */@ ] ) {
561        for ( size_t  r = 0; r < rows; r += 1 ) {
562                for ( size_t  c = 0; c < cols; c += 1 )
563                        ...  @m[r][c]@  ...
564}
565int @* aa[5]@;  // row pointers
566for ( int r = 0; r < 5; r += 1 ) {
567        @aa[r] = malloc( 5 * sizeof(int) );@ // create rows
568        for ( int c = 0; c < 5; c += 1 )
569                aa[r][c] = r + c;
570}
571faa( 5, 5, aa );
572\end{cfa}
573\end{tabular}
574\caption{C99 Contiguous \vs Non-contiguous Matrix Styles}
575\label{f:ContiguousNon-contiguous}
576\end{figure}
577
578
579\subsection{Multi-Dimensional Arrays Decay and Pointers Diffract}
580
581As for single-dimension, multi-dimensional arrays have similar issues \see{\VRef{s:Array}}.
582Again, the inspection begins by using @sizeof@ to provide program semantics for the intuition of an expression's type.
583\lstinput{16-18}{bkgd-carray-mdim.c}
584There are now three axis for deriving expressions from @mx@: \emph{itself}, \emph{first element}, and \emph{first grand-element} (meaning, first element of first element).
585\lstinput{20-26}{bkgd-carray-mdim.c}
586Given that arrays are contiguous and the size of @float@ is 4, then the size of @mx@ with 3 $\times$ 10 floats is 120 bytes, the size of its first element (row) is 40 bytes, and the size of the first element of the first row is 4.
587Again, an array and a point to each of its axes are different.
588\lstinput{28-36}{bkgd-carray-mdim.c}
589As well, there is pointer decay from each of the matrix axes to pointers, which all have the same address.
590\lstinput{38-44}{bkgd-carray-mdim.c}
591Finally, subscripting on a @malloc@ result, where the referent may or may not allow subscripting or have the right number of subscripts.
592
593
594\subsection{Array Parameter Declaration}
595
596Passing an array as an argument to a function is necessary.
597Assume a parameter is an array where the function intends to subscript it.
598This section asserts that a more satisfactory/formal characterization does not exist in C, then surveys the ways that C API authors communicate @p@ has zero or more dimensions, and finally calls out the minority cases where the C type system is using or verifying such claims.
599
600A C parameter declaration looks different from the caller's and callee's perspectives.
601Both perspectives consist of the text read by a programmer and the semantics enforced by the type system.
602The caller's perspective is available from a function declaration, which allows definition-before-use and separate compilation, but can also be read from (the non-body part of) a function definition.
603The callee's perspective is what is available inside the function.
604\begin{cfa}
605int foo( int, float, char );                            $\C{// declaration, parameter names optional}$
606int bar( int i, float f, char c ) {             $\C{// definition, parameter names mandatory}$
607        // callee's perspective of foo and bar
608}
609// caller's perspectives of foo and bar
610\end{cfa}
611From the caller's perspective, the parameter names (by virtue of being optional) are (useful) comments;
612From the callee's perspective, parameter names are semantically significant.
613Array parameters introduce a further, subtle, semantic difference and considerable freedom to comment.
614
615At the semantic level, there is no such thing as an array parameter, except for one case (@T [static 5]@) discussed shortly.
616Rather, there are only pointer parameters.
617This fact probably shares considerable responsibility for the common sense of \emph{an array is just a pointer}, which has been refuted in non-parameter contexts.
618This fact holds in both the caller's and callee's perspectives.
619However, a parameter's type can include ``array of'', \eg the type ``pointer to array of 5 ints'' (@T (*)[5]@) is a pointer type.
620This type is fully meaningful in the sense that its description does not contain any information that the type system ignores, and the type appears the same in the caller's \vs callee's perspectives.
621In fact, the outermost type constructor (syntactically first dimension) is really the one that determines the parameter flavour.
622
623TODO: add examples of mycode/arrr/bugs/c-dependent/x.cfa:v5102,5103,
624which are shocking how much C ignores.
625
626\begin{figure}
627\begin{tabular}{@{}llll@{}}
628\begin{cfa}
629float sum( float a[5] );
630float sum( float m[5][4] );
631float sum( float a[5][] );
632float sum( float a[5]* );
633float sum( float *a[5] );
634\end{cfa}
635&
636\begin{cfa}
637float sum( float a[] );
638float sum( float m[][4] );
639float sum( float a[][] );
640float sum( float a[]* );
641float sum( float *a[] );
642\end{cfa}
643&
644\begin{cfa}
645float sum( float *a );
646float sum( float (*m)[4] );
647float sum( float (*a)[] );
648float sum( float (*a)* );
649float sum( float **a );
650\end{cfa}
651&
652\begin{cfa}
653// array of float
654// matrix of float
655// invalid
656// invalid
657// array of ptr to float
658\end{cfa}
659\end{tabular}
660\caption{Multiple ways to declare an array parameter.
661Across a valid row, every declaration is equivalent.
662Each column gives a declaration style, where the style for that column is read from the first row.
663The second row begins the style for multiple dimensions, with the rows thereafter providing context for the choice of which second-row \lstinline{[]} receives the column-style variation.}
664\label{f:ArParmEquivDecl}
665\end{figure}
666
667Yet, C allows array syntax for the outermost type constructor, from which comes the freedom to comment.
668An array parameter declaration can specify the outermost dimension with a dimension value, @[10]@ (which is ignored), an empty dimension list, @[ ]@, or a pointer, @*@, as seen in \VRef[Figure]{f:ArParmEquivDecl}.
669The rationale for rejecting the first invalid row follows shortly, while the second invalid row is simple nonsense, included to complete the pattern; its syntax hints at what the final row actually achieves.
670Note, in the leftmost style, the typechecker ignores the actual value even in a dynamic expression.
671\begin{cfa}
672int N;
673void foo( float @a[N] ) ; // N is ignored
674\end{cfa}
675
676
677% To help contextualize the matrix part of this example, the syntaxes @float [5][]@, @float [][]@ and @float (*)[]@ are all rejected, for reasons discussed shortly.
678% So are @float[5]*@, @float[]*@ and @float (*)*@.  These latter ones are simply nonsense, though they hint at ``1d array of pointers'', whose equivalent syntax options are, @float *[5]@, @float *[]@, and @float **@.
679
680It is a matter of taste as to whether a programmer should use a form as far left as possible (getting the most out of possible subscripting and dimension sizes), sticking to the right (avoiding false comfort from suggesting the typechecker is checking more than it is), or compromising in the middle (reducing unchecked information, yet clearly stating, ``I will subscript'').
681
682Note that this equivalence of pointer and array declarations is special to parameters.
683It does not apply to local variables, where true array declarations are possible.
684\begin{cfa}
685void f( float * a ) {
686        float * b = a; // ok
687        float c[] = a; // reject
688        float d[] = { 1.0, 2.0, 3.0 }; // ok
689        static_assert( sizeof(b) == sizeof(float*) );
690        static_assert( sizeof(d) != sizeof(float*) );
691}
692\end{cfa}
693Unfortunately, this equivalence has the consequence that the type system does not help a caller get it right.
694\begin{cfa}
695float sum( float v[] );
696float arg = 3.14;
697sum( &arg );                                                            $\C{// accepted, v = \&arg}$
698\end{cfa}
699
700Given the syntactic dimension forms @[ ]@ or @[5]@, it raises the question of qualifying the implied array pointer rather than the array element type.
701For example, the qualifiers after the @*@ apply to the array pointer.
702\begin{cfa}
703void foo( const volatile int * @const volatile@ );
704void foo( const volatile int [ ] @const volatile@ ); // does not parse
705\end{cfa}
706C instead puts these pointer qualifiers syntactically into the first dimension.
707\begin{cquote}
708@[@ \textit{type-qualifier-list}$_{opt}$ \textit{assignment-expression}$_{opt}$ @]@
709\end{cquote}
710\begin{cfa}
711void foo( int [@const  volatile@] );
712void foo( int [@const  volatile@ 5] );          $\C{// 5 is ignored}$
713\end{cfa}
714To make the first dimension size meaningful, C adds this form.
715\begin{cquote}
716@[@ @static@ \textit{type-qualifier-list}$_{opt}$ \textit{assignment-expression} @]@
717\end{cquote}
718\begin{cfa}
719void foo( int [static @3@] );
720int ar[@10@];
721foo( ar ); // check argument dimension 10 > 3
722\end{cfa}
723Here, the @static@ storage qualifier defines the minimum array size for its argument.
724Earlier versions of @gcc@ ($<$ 11) and possibly @clang@ ignore this dimension qualifier, while later versions implement the check, in accordance with the standard.
725
726
727Note that there are now two different meanings for modifiers in the same position.  In
728\begin{cfa}
729void foo( int x[static const volatile 3] );
730\end{cfa}
731the @static@ applies to the 3, while the @const volatile@ applies to the @x@.
732
733With multidimensional arrays, on dimensions after the first, a size is required and, is not ignored.
734These sizes are required for the callee to be able to subscript.
735\begin{cfa}
736void f( float a[][10], float b[][100] ) {
737    static_assert( ((char*)&a([1])) - ((char*)&a([0])) == 10 * sizeof(float) );
738    static_assert( ((char*)&b([1])) - ((char*)&b([0])) == 100 * sizeof(float) );
739}
740\end{cfa}
741Here, the distance between the first and second elements of each array depends on the inner dimension size.
742
743The significance of an inner dimension's length is a fact of the callee's perspective.
744In the caller's perspective, the type system is quite lax.
745Here, there is (some, but) little checking that what is being passed, matches.
746% void f( float [][10] );
747% int n = 100;
748% float a[100], b[n];
749% f(&a); // reject
750% f(&b); // accept
751\begin{cfa}
752void foo() {
753        void f( float [][10] );
754        int n = 100;
755        float a[100], b[3][12], c[n], d[n][n];
756        f( a );
757        f( b );    $\C{// reject: inner dimension 12 for 10}$
758        f( c );
759        f( @d@ );  $\C{// accept with inner dimension n for 10}$
760        f( &a );   $\C{// reject: inner dimension 100 for 10}$
761        f( &b );
762        f( @&c@ ); $\C{// accept with inner dimension n for 10}$
763        f( &d );
764}
765\end{cfa}
766The cases without comments are rejections, but simply because the array ranks do not match; in the commented cases, the ranks match and the rules being discussed apply.
767The cases @f( b )@ and @f( &a )@ show where some length checking occurs.
768But this checking misses the cases @f( d )@ and @f( &c )@, allowing the calls with mismatched lengths, actually 100 for 10.
769The C checking rule avoids false alarms, at the expense of safety, by allowing any combinations that involve dynamic values.
770Ultimately, an inner dimension's size is a callee's \emph{assumption} because the type system uses declaration details in the callee's perspective that it does not enforce in the caller's perspective.
771
772Finally, to handle higher-dimensional VLAs, C repurposed the @*@ \emph{within} the dimension in a declaration to mean that the callee has make an assumption about the size, but no (checked, possibly wrong) information about this assumption is included for the caller-programmer's benefit/\-over-confidence.
773\begin{cquote}
774@[@ \textit{type-qualifier-list$_{opt}$} @* ]@
775\end{cquote}
776\begin{cfa}
777void foo( float [][@*@] );                                              $\C{// declaration}$ 
778void foo( float a[][10] ) { ... }                               $\C{// definition}$
779\end{cfa}
780Repeating it with the full context of a VLA is useful:
781\begin{cfa}
782void foo( int, float [][@*@] );                                 $\C{// declaration}$ 
783void foo( int n, float a[][n] ) { ... }                 $\C{// definition}$
784\end{cfa}
785Omitting the dimension from the declaration is consistent with omitting parameter names, for the declaration case has no name @n@ in scope.
786The omission is also redacting all information not needed to generate correct caller-side code.
787
788
789\subsection{Arrays Could be Values}
790
791All arrays have a know runtime size at their point of declaration.
792Furthermore, C provides an explicit mechanism to pass an array's dimensions to a function.
793Nevertheless, an array cannot be copied, and hence, not passed by value to a function, even when there is sufficient information to do so.
794
795However, if an array is a structure field (compile-time size), it can be copied and passed by value.
796For example, a C @jmp_buf@ is an array.
797\begin{cfa}
798typedef long int jmp_buf[8];
799\end{cfa}
800A instance of this array can be declared as a structure field.
801\begin{cfa}
802struct Jmp_Buf {
803        @jmp_buf@ jb;
804};
805\end{cfa}
806Now the array can be copied (and passed by value) because structures can be copied.
807\begin{cfa}
808Jmp_Buf jb1, jb2;
809jb1 = jb2;            // copy
810void foo( Jmp_Buf );
811foo( jb2 );           // copy
812\end{cfa}
813
814This same argument applies to returning arrays from functions.
815There can be sufficient information to return an array by value but it is unsupported.
816Again, array wrapping allows an array to be returned from a function and copied into a variable.
817
818
819\section{Linked List}
820
821Linked-lists are blocks of storage connected using one or more pointers.
822The storage block (node) is logically divided into data (user payload) and links (list pointers), where the links are the only component used by the list structure.
823Since the data is opaque, list structures are often polymorphic over the data, which is often homogeneous.
824
825The links organize nodes into a particular format, \eg queue, tree, hash table, \etc, with operations specific to that format.
826Because a node's existence is independent of the data structure that organizes it, all nodes are manipulated by address not value;
827hence, all data structure routines take and return pointers to nodes and not the nodes themselves.
828
829
830\subsection{Design Issues}
831\label{toc:lst:issue}
832
833This thesis focuses on a reduced design space for linked lists that target \emph{system programmers}.
834Within this restricted space, all design-issue discussions assume the following invariants;
835alternatives to the assumptions are discussed under Future Work (\VRef{toc:lst:futwork}).
836\begin{itemize}
837        \item A doubly-linked list is being designed.
838                Generally, the discussed issues apply similarly for singly-linked lists.
839                Circular \vs ordered linking is discussed under List identity (\VRef{toc:lst:issue:ident}).
840        \item Link fields are system-managed.
841                The user works with the system-provided API to query and modify list membership.
842                The system has freedom over how to represent these links.
843        \item The user data must provide storage for the list link-fields.
844                Hence, a list node is \emph{statically} defined as data and links \vs a node that is \emph{dynamically} constructed from data and links \see{\VRef{toc:lst:issue:attach}}.
845\end{itemize}
846
847
848\subsection{Preexisting Linked-List Libraries}
849\label{s:PreexistingLinked-ListLibraries}
850
851Two preexisting linked-list libraries are used throughout, to show examples of the concepts being defined,
852and further libraries are introduced as needed.
853\begin{enumerate}
854        \item Linux Queue library~\cite{lst:linuxq} (LQ) of @<sys/queue.h>@.
855        \item \CC Standard Template Library's (STL)\footnote{The term STL is contentious as some people prefer the term standard library.} @std::list@\cite{lst:stl}
856\end{enumerate}
857%A general comparison of libraries' abilities is given under Related Work (\VRef{toc:lst:relwork}).
858For the discussion, assume the fictional type @req@ (request) is the user's payload in examples.
859As well, the list library is helping the user manage (organize) requests, \eg a request can be work on the level of handling a network arrival-event or scheduling a thread.
860
861
862\subsection{Link Attachment: Intrusive \vs Wrapped}
863\label{toc:lst:issue:attach}
864
865Link attachment deals with the question:
866Where are the libraries' inter-node link-fields stored, in relation to the user's payload data fields?
867\VRef[Figure]{fig:lst-issues-attach} shows three basic styles.
868\VRef[Figure]{f:Intrusive} shows the \newterm{intrusive} style, placing the link fields inside the payload structure.
869\VRef[Figures]{f:WrappedRef} and \subref*{f:WrappedValue} show the two \newterm{wrapped} styles, which place the payload inside a generic library-provided structure that then defines the link fields.
870The wrapped style distinguishes between wrapping a reference and wrapping a value, \eg @list<req *>@ or @list<req>@.
871(For this discussion, @list<req &>@ is similar to @list<req *>@.)
872This difference is one of user style, not framework capability.
873Library LQ is intrusive; STL is wrapped with reference and value.
874
875\begin{comment}
876\begin{figure}
877        \begin{tabularx}{\textwidth}{Y|Y|Y}
878                \lstinput[language=C]{20-39}{lst-issues-intrusive.run.c}
879                &\lstinputlisting[language=C++]{20-39}{lst-issues-wrapped-byref.run.cpp}
880                &\lstinputlisting[language=C++]{20-39}{lst-issues-wrapped-emplaced.run.cpp}
881          \\ & &
882          \\
883                \includegraphics[page=1]{lst-issues-attach.pdf}
884                &
885                \includegraphics[page=2]{lst-issues-attach.pdf}
886                &
887                \includegraphics[page=3]{lst-issues-attach.pdf}
888          \\ & &
889          \\
890                (a) & (b) & (c)
891        \end{tabularx}
892\caption{
893                Three styles of link attachment: (a)~intrusive, (b)~wrapped reference, and (c)~wrapped value.
894                The diagrams show the memory layouts that result after the code runs, eliding the head object \lstinline{reqs};
895                head objects are discussed in \VRef{toc:lst:issue:ident}.
896                In (a), the field \lstinline{req.x} names a list direction;
897                these are discussed in \VRef{toc:lst:issue:simultaneity}.
898                In (b) and (c), the type \lstinline{node} represents a system-internal type,
899                which is \lstinline{std::_List_node} in the GNU implementation.
900                (TODO: cite? found in  /usr/include/c++/7/bits/stl\_list.h )
901        }
902         \label{fig:lst-issues-attach}
903\end{figure}
904\end{comment}
905
906\begin{figure}
907\centering
908\newsavebox{\myboxA}                                    % used with subfigure
909\newsavebox{\myboxB}
910\newsavebox{\myboxC}
911
912\begin{lrbox}{\myboxA}
913\begin{tabular}{@{}l@{}}
914\lstinput[language=C]{20-35}{lst-issues-intrusive.run.c} \\
915\includegraphics[page=1]{lst-issues-attach.pdf}
916\end{tabular}
917\end{lrbox}
918
919\begin{lrbox}{\myboxB}
920\begin{tabular}{@{}l@{}}
921\lstinput[language=C++]{20-35}{lst-issues-wrapped-byref.run.cpp} \\
922\includegraphics[page=2]{lst-issues-attach.pdf}
923\end{tabular}
924\end{lrbox}
925
926\begin{lrbox}{\myboxC}
927\begin{tabular}{@{}l@{}}
928\lstinput[language=C++]{20-35}{lst-issues-wrapped-emplaced.run.cpp} \\
929\includegraphics[page=3]{lst-issues-attach.pdf}
930\end{tabular}
931\end{lrbox}
932
933\subfloat[Intrusive]{\label{f:Intrusive}\usebox\myboxA}
934\hspace{6pt}
935\vrule
936\hspace{6pt}
937\subfloat[Wrapped reference]{\label{f:WrappedRef}\usebox\myboxB}
938\hspace{6pt}
939\vrule
940\hspace{6pt}
941\subfloat[Wrapped value]{\label{f:WrappedValue}\usebox\myboxC}
942
943\caption{
944                Three styles of link attachment:
945                % \protect\subref*{f:Intrusive}~intrusive, \protect\subref*{f:WrappedRef}~wrapped reference, and \protect\subref*{f:WrappedValue}~wrapped value.
946                The diagrams show the memory layouts that result after the code runs, eliding the head object \lstinline{reqs};
947                head objects are discussed in \VRef{toc:lst:issue:ident}.
948                In \protect\subref*{f:Intrusive}, the field \lstinline{req.d} names a list direction;
949                these are discussed in \VRef{toc:lst:issue:simultaneity}.
950                In \protect\subref*{f:WrappedRef} and \protect\subref*{f:WrappedValue}, the type \lstinline{node} represents a
951                library-internal type, which is \lstinline{std::_List_node} in the GNU implementation
952                \see{\lstinline{/usr/include/c++/X/bits/stl_list.h}, where \lstinline{X} is the \lstinline{g++} version number}.
953        }
954        \label{fig:lst-issues-attach}
955\end{figure}
956
957Each diagrammed example is using the fewest dynamic allocations for its respective style:
958in intrusive, here is no dynamic allocation, in wrapped reference only the linked fields are dynamically allocated, and in wrapped value the copied data and linked fields are dynamically allocated.
959The advantage of intrusive is the control in memory layout and storage placement.
960Both wrapped styles have independent storage layout and imply library-induced heap allocations, with lifetime that matches the item's membership in the list.
961In all three cases, a @req@ object can enter and leave a list many times.
962However, in intrusive a @req@ can only be on one list at a time, unless there are separate link-fields for each simultaneous list.
963In wrapped reference, a @req@ can appear multiple times on the same or different lists, but since @req@ is shared via the pointer, care must be taken if updating data also occurs simultaneously, \eg concurrency.
964In wrapped value, the @req@ is copied, which increases storage usage, but allows independent simultaneous changes;
965however, knowing which of the @req@ object is the \emph{true} object becomes complex.
966\see*{\VRef{toc:lst:issue:simultaneity} for further discussion.}
967
968The implementation of @LIST_ENTRY@ uses a trick to find the links and the node containing the links.
969The macro @LIST_INSERT_HEAD( &reqs, &r2, d )@ takes the list header, a pointer to the node, and the offset of the link fields in the node.
970One of the fields generated by @LIST_ENTRY@ is a pointer to the node, which is set to the node address, \eg @r2@.
971Hence, the offset to the link fields provides an access to the entire node, \ie the node points at itself.
972For list traversal, @LIST_FOREACH( cur, &reqs_pri, by_pri )@, there is the node cursor, the list, and the offset of the link fields within the node.
973The traversal actually moves from link fields to link fields within a node and sets the node cursor from the pointer within the link fields back to the node.
974
975A further aspect of layout control is allowing the user to explicitly specify link fields controlling placement and attributes within the @req@ object.
976LQ allows this ability through the @LIST_ENTRY@ macro\footnote{It is possible to have multiple named linked fields allowing a node to appear on multiple lists simultaneously.}, which can be placed anywhere in the node.
977An example of an attribute on the link fields is cache alignment, possibly in conjunction with other @req@ fields, improving locality and/or avoiding false sharing.
978For example, if a list is frequently traversed in the forward direction, and infrequently gets elements removed at random positions, then an ideal layout for cache locality puts the forward links, together with frequently-used payload data on one cache line, leaving the reverse links on a colder cache line.
979Supplying the link fields by inheritance makes them implicit and relies on compiler placement, such as the start or end of @req@, and no explicit attributes.
980Wrapped reference has no control over the link fields, but the separate data allows some control;
981wrapped value has no control over data or links.
982
983Another subtle advantage of intrusive arrangement is that a reference to a user-level item (@req@) is sufficient to navigate or manage the item's membership.
984In LQ, the intrusive @req@ pointer is the right argument type for operations @LIST_NEXT@ or @LIST_REMOVE@;
985there is no distinguishing a @req@ from a @req@ in a list.
986The same is not true of STL, wrapped reference or value.
987There, the analogous operations, @iterator::operator++()@, @iterator::operator*()@, and @list::erase(iterator)@, work on a parameter of type @list<T>::iterator@;
988there is no mapping from @req &@ to @list<req>::iterator@. %, for linear search.
989
990The advantage of wrapped is the abstraction of a data item from its list membership(s).
991In the wrapped style, the @req@ type can come from a library that serves many independent uses,
992which generally have no need for listing.
993Then, a novel use can put a @req@ in a list, without requiring any upstream change in the @req@ library.
994In intrusive, the ability to be listed must be planned during the definition of @req@.
995
996\begin{figure}
997        \lstinput[language=C++]{100-117}{lst-issues-attach-reduction.hpp}
998        \lstinput[language=C++]{150-150}{lst-issues-attach-reduction.hpp}
999        \caption{
1000                Simulation of wrapped using intrusive.
1001                Illustrated by pseudocode implementation of an STL-compatible API fragment using LQ as the underlying implementation.
1002                The gap that makes it pseudocode is that
1003                the LQ C macros do not expand to valid \CC when instantiated with template parameters---there is no \lstinline{struct El}.
1004                When using a custom-patched version of LQ to work around this issue,
1005                the programs of \VRef[Figure]{f:WrappedRef} and wrapped value work with this shim in place of real STL.
1006                Their executions lead to the same memory layouts.
1007        }
1008        \label{fig:lst-issues-attach-reduction}
1009\end{figure}
1010
1011It is possible to simulate wrapped using intrusive, illustrated in \VRef[Figure]{fig:lst-issues-attach-reduction}.
1012This shim layer performs the implicit dynamic allocations that pure intrusion avoids.
1013But there is no reduction going the other way.
1014No shimming can cancel the allocations to which wrapped membership commits.
1015
1016Because intrusion is a lower-level listing primitive, the system design choice is not between forcing users to use intrusion or wrapping.
1017The choice is whether or not to provide access to an allocation-free layer of functionality.
1018An intrusive-primitive library like LQ lets users choose when to make this tradeoff.
1019A wrapped-primitive library like STL forces users to incur the costs of wrapping, whether or not they access its benefits.
1020\CFA is capable of supporting a wrapped library, if need arose.
1021
1022
1023\subsection{Simultaneity: Single \vs Multi-Static \vs Dynamic}
1024\label{toc:lst:issue:simultaneity}
1025
1026\begin{figure}
1027        \parbox[t]{3.5in} {
1028                \lstinput[language=C++]{20-60}{lst-issues-multi-static.run.c}
1029        }\parbox[t]{20in} {
1030                ~\\
1031                \includegraphics[page=1]{lst-issues-direct.pdf} \\
1032                ~\\
1033                \hspace*{1.5in}\includegraphics[page=2]{lst-issues-direct.pdf}
1034        }
1035        \caption{
1036                Example of simultaneity using LQ lists.
1037                The zoomed-out diagram (right/top) shows the complete multi-linked data structure.
1038                This structure can navigate all requests in priority order ({\color{blue}blue}), and navigate among requests with a common request value ({\color{orange}orange}).
1039                The zoomed-in diagram (right/bottom) shows how the link fields connect the nodes on different lists.
1040        }
1041        \label{fig:lst-issues-multi-static}
1042\end{figure}
1043
1044\newterm{Simultaneity} deals with the question:
1045In how many different lists can a node be stored, at the same time?
1046\VRef[Figure]{fig:lst-issues-multi-static} shows an example that can traverse all requests in priority order (field @pri@) or navigate among requests with the same request value (field @rqr@).
1047Each of ``by priority'' and ``by common request value'' is a separate list.
1048For example, there is a single priority-list linked in order [1, 2, 2, 3, 3, 4], where nodes may have the same priority, and there are three common request-value lists combining requests with the same values: [42, 42], [17, 17, 17], and [99], giving four head nodes one for each list.
1049The example shows a list can encompass all the nodes (by-priority) or only a subset of the nodes (three request-value lists).
1050
1051As stated, the limitation of intrusive is knowing apriori how many groups of links are needed for the maximum number of simultaneous lists.
1052Thus, the intrusive LQ example supports multiple, but statically many, link lists.
1053Note, it is possible to reuse links for different purposes, \eg if a list in linked one way at one time and another way at another time, and these times do not overlap, the two different linkings can use the same link fields.
1054This feature is used in the \CFA runtime, where a thread node may be on a blocked or running list, but never on both simultaneously.
1055
1056Now consider the STL in the wrapped-reference arrangement of \VRef[Figure]{f:WrappedRef}.
1057Here it is possible to construct the same simultaneity by creating multiple STL lists, each pointing at the appropriate nodes.
1058Each group of intrusive links become the links for each separate STL list.
1059The upside is the unlimited number of lists a node can be associated with simultaneously, as any number of STL lists can be created dynamically.
1060The downside is the dynamic allocation of the link nodes and managing multiple lists.
1061Note, it might be possible to wrap the multiple lists in another type to hide this implementation issue.
1062
1063Now consider the STL in the wrapped-value arrangement of \VRef[Figure]{f:WrappedValue}.
1064Again, it is possible to construct the same simultaneity by creating multiple STL lists, each copying the appropriate nodes, where the intrusive links become the links for each separate STL list.
1065The upside is the same as for wrapped-reference arrangement with an unlimited number of list bindings.
1066The downside is the dynamic allocation, significant storage usage, and cost of copying nodes.
1067As well, it is unclear how node updates work in this scenario, without some notation of ultimately merging node information.
1068
1069% https://www.geeksforgeeks.org/introduction-to-multi-linked-list/ -- example of building a bespoke multi-linked list out of STL primitives (providing indication that STL doesn't offer one); offers dynamic directionality by embedding `vector<struct node*> pointers;`
1070
1071% When allowing multiple static directions, frameworks differ in their ergonomics for
1072% the typical case: when the user needs only one direction, vs.\ the atypical case, when the user needs several.
1073% LQ's ergonomics are well-suited to the uncommon case of multiple list directions.
1074% Its intrusion declaration and insertion operation both use a mandatory explicit parameter naming the direction.
1075% This decision works well in \VRef[Figure]{fig:lst-issues-multi-static}, where the names @by_pri@ and @by_rqr@ work well,
1076% but it clutters \VRef[Figure]{f:Intrusive}, where a contrived name must be invented and used.
1077% The example uses @x@; @reqs@ would be a more readily ignored choice. \PAB{wording?}
1078
1079An alternative system providing intrusive data-structures is \uCpp, a concurrent extension of \CC.
1080It provides a basic set of intrusive lists~\cite[appx.~F]{uC++}, where the link fields are defined with the data fields using inheritance.
1081\begin{cquote}
1082\setlength{\tabcolsep}{15pt}
1083\begin{tabular}{@{}ll@{}}
1084\multicolumn{1}{c}{singly-linked list} & \multicolumn{1}{c}{doubly-linked list} \\
1085\begin{c++}
1086struct Node : public uColable {
1087        int i;  // data
1088        Node( int i ) : i{ i } {}
1089};
1090\end{c++}
1091&
1092\begin{c++}
1093struct Node : public uSeqable {
1094        int i;  // data
1095        Node( int i ) : i{ i } {}
1096};
1097\end{c++}
1098\end{tabular}
1099\end{cquote}
1100A node can be placed in the following data structures depending on its link fields: @uStack@ and @uQueue@ (singly linked), and @uSequence@ (doubly linked).
1101A node inheriting from @uSeqable@ can appear in a singly or doubly linked structure.
1102Structure operations implicitly know the link-field location through the inheritance.
1103\begin{c++}
1104uStack<Node> stack;
1105Node node;
1106stack.push( node );  // link fields at beginning of node
1107\end{c++}
1108
1109Simultaneity cannot be done with multiple inheritance, because there is no mechanism to either know the order of inheritance fields or name each inheritance.
1110Instead, a special type is require that contains the link fields and points at the node.
1111\begin{cquote}
1112\setlength{\tabcolsep}{10pt}
1113\begin{tabular}{@{}ll@{}}
1114\begin{c++}
1115struct NodeDL : public uSeqable {
1116        @Node & node;@  // node pointer
1117        NodeDL( Node & node ) : node( node ) {}
1118        Node & get() const { return node; }
1119};
1120\end{c++}
1121&
1122\begin{c++}
1123struct Node : public uColable {
1124        int i;  // data
1125        @NodeDL nodeseq;@  // embedded intrusive links
1126        Node( int i ) : i{ i }, @nodeseq{ this }@ {}
1127};
1128\end{c++}
1129\end{tabular}
1130\end{cquote}
1131This node can now be inserted into a doubly-linked list through the embedded intrusive links.
1132\begin{c++}
1133uSequence<NodeDL> sequence;
1134sequence.add_front( @node.nodeseq@ );   $\C{// link fields in embedded type}$
1135NodeDL nodedl = sequence.remove( @node.nodeseq@ );
1136int i = nodedl.@get()@.i;                               $\C{// indirection to node}$
1137\end{c++}
1138Hence, the \uCpp approach optimizes one set of intrusive links through the \CC inheritance mechanism, and falls back onto the LQ approach of explicit declarations for additional intrusive links.
1139However, \uCpp cannot apply the LQ trick for finding the links and node.
1140
1141The major ergonomic difference among the approaches is naming and name usage.
1142The intrusive model requires naming each set of intrusive links, \eg @by_pri@ and @by_rqr@ in \VRef[Figure]{fig:lst-issues-multi-static}.
1143\uCpp cheats by using inheritance for the first intrusive links, after which explicit naming of intrusive links is required.
1144Furthermore, these link names must be used in all list operations, including iterating, whereas wrapped reference and value hide the list names in the implicit dynamically-allocated node-structure.
1145At issue is whether an API for simultaneity can support one \emph{implicit} list, when several are not wanted.
1146\uCpp allows it, LQ does not, and the STL does not have this question.
1147
1148
1149\subsection{User Integration: Preprocessed \vs Type-System Mediated}
1150
1151While the syntax for LQ is reasonably succinct, it comes at the cost of using C preprocessor macros for generics, which are not part of the language type-system, like \CC templates.
1152Hence, small errors in macro arguments can lead to large substitution mistakes, as the arguments maybe textually written in many places and/or concatenated with other arguments/text to create new names and expressions.
1153This can lead to a cascade of error messages that are confusing and difficult to debug.
1154For example, argument errors like @a.b,c@, comma instead of period, or @by-pri@, minus instead of underscore, can produce many error messages.
1155
1156Instead, language function calls (even with inlining) handled argument mistakes locally at the call, giving very specific error message.
1157\CC @concepts@ were introduced in @templates@ to deal with just this problem.
1158
1159% example of poor error message due to LQ's preprocessed integration
1160% programs/lst-issues-multi-static.run.c:46:1: error: expected identifier or '(' before 'do'
1161%    46 | LIST_INSERT_HEAD(&reqs_rtr_42, &r42b, by_rqr);
1162%       | ^~~~~~~~~~~~~~~~
1163%
1164% ... not a wonderful example; it was a missing semicolon on the preceding line; but at least real
1165
1166
1167\subsection{List Identity: Headed \vs Ad-Hoc}
1168\label{toc:lst:issue:ident}
1169
1170All examples so far use two distinct types for:
1171an item found in a list (type @req@ of variable @r1@, see \VRef[Figure]{fig:lst-issues-attach}), and the list (type @reql@ of variable @reqs_pri@, see \VRef[Figure]{fig:lst-issues-ident}).
1172This kind of list is ``headed'', where the empty list is just a head.
1173An alternate ``ad-hoc'' approach omits the header, where the empty list is no nodes.
1174Here, a pointer to any node can traverse its link fields: right or left and around, depending on the data structure.
1175Note, a headed list is superset of an ad-hoc list, and can normally perform all of the ad-hoc operations.
1176\VRef[Figure]{fig:lst-issues-ident} shows both approaches for different list lengths and unlisted elements.
1177For headed, there are length-zero lists (heads with no elements), and an element can be listed or not listed.
1178For ad-hoc, there are no length-zero lists and every element belongs to a list of length at least one.
1179
1180\begin{figure}
1181        \centering
1182        \includegraphics{lst-issues-ident.pdf}
1183        \caption{
1184                Comparison of headed and ad-hoc list identities, for various list lengths.
1185                Pointers are logical, meaning that no claim is intended about which part of an object is being targeted.
1186        }
1187        \label{fig:lst-issues-ident}
1188\end{figure}
1189
1190The purpose of a header is to provide specialized but implicit node access, such as the first/last nodes in the list, where accessing these nodes is deemed a commonly occurring operation and should be $O(1)$ for performance of certain operations.
1191For example, without a last pointer in a singly-linked list, adding to the end of the list is an $O(N)$ operation to traverse the list to find the last node.
1192Without the header, this specialized information must be managed explicitly, where the programmer builds their own external, equivalent header information.
1193However, external management of particular nodes might not be beneficial because the list does not provide operations that can take advantage of them, such as using an external pointer to update an internal link.
1194Clearly, there is a cost maintaining this specialized information, which needs to be amortized across the list operations that use it, \eg rarely adding to the end of a list.
1195A runtime component of this cost is evident in LQ's offering the choice of type generators @LIST@ \vs @TAILQ@.
1196Its @LIST@ maintains a \emph{first}, but not a \emph{last};
1197its @TAILQ@ maintains both roles.
1198(Both types are doubly linked and an analogous choice is available for singly linked.)
1199
1200
1201\subsection{End Treatment: Cased \vs Uniform }
1202
1203All lists must have a logical \emph{beginning/ending}, otherwise list traversal is infinite.
1204\emph{End treatment} refers to how the list represents the lack of a predecessor/successor to demarcate end point(s).
1205For example, in a doubly-linked list containing a single node, the next/prev links have no successor/predecessor nodes.
1206Note, a list does not need to use links to denote its size;
1207it can use a node counter in the header, where $N$ node traversals indicates complete navigation of the list.
1208However, managing the number of nodes is an additional cost, as the links must always be managed.
1209
1210The following discussion refers to the LQ representations, detailed in \VRef[Figure]{fig:lst-issues-end}, using a null pointer to mark end points.
1211LQ uses this representation for its successor/last.
1212For example, consider the operation of inserting after a given element.
1213A doubly-linked list must update the given node's successor, to make its predecessor-pointer refer to the new node.
1214This step must happen when the given node has a successor (when its successor pointer is non-null),
1215and must be skipped when it does not (when its successor pointer cannot be navigated).
1216So this operation contains a branch, to decide which case is happening.
1217All branches have pathological cases where branch prediction's success rate is low and the execution pipeline stalls often.
1218Hence, this issue is relevant to achieving high performance.
1219
1220\begin{figure}
1221        \centering
1222        \includegraphics{lst-issues-end.pdf}
1223        \caption{
1224                LQ sub-object-level representation of links and ends.
1225                Each object's memory is pictured as a vertical strip.
1226                Pointers' target locations, within these strips, are significant.
1227                Uniform treatment of the first-end is evident from an assertion like \lstinline{(**this.pred == this)} holding for all nodes \lstinline{this}, including the first one.
1228                Cased treatment of the last-end is evident from the symmetric proposition, \lstinline{(this.succ.pred == &this.succ)}, failing when \lstinline{this} is the last node.
1229        }
1230        \label{fig:lst-issues-end}
1231\end{figure}
1232
1233Interestingly, this branch is sometimes avoidable, giving a uniform end-treatment in the code.
1234For example, LQ is headed at the front.
1235For predecessor/first navigation, the relevant operation is inserting before a given element.
1236LQ's predecessor representation is not a pointer to a node, but a pointer to a pseudo-successor pointer.
1237When there is a predecessor node, that node contains a real-successor pointer; it is the target of the reference node's predecessor pointer.
1238When there is no predecessor node, the reference node (now known to be first node) acts as the pseudo-successor of the list head.
1239Now, the list head contains a pointer to the first node.
1240When inserting before the first node, the list head's first-pointer is the one that must change.
1241So, the first node's \emph{predecessor} pointer (to a pseudo-successor pointer) is set as the list head's first-pointer.
1242Now, inserting before a given element does the same logic in both cases:
1243follow the guaranteed-non-null predecessor pointer, and update that location to refer to the new node.
1244Applying this trick makes it possible to have list management routines that are completely free of conditional control-flow.
1245Considering a path length of only a few instructions (less than the processor's pipeline length),
1246such list management operations are often practically free,
1247with all the variance being due to the (inevitable) cache status of the nodes being managed.
1248
1249
1250\section{String}
1251\label{s:String}
1252
1253A string is a sequence of symbols, where the form of a symbol can vary significantly: 7/8-bit characters (ASCII/Latin-1), or 2/4/8-byte (UNICODE) characters/symbols or variable length (UTF-8/16/32) characters.
1254A string can be read left-to-right, right-to-left, top-to-bottom, and have stacked elements (Arabic).
1255
1256A C character constant is an ASCII/Latin-1 character enclosed in single-quotes, \eg @'x'@, @'@\textsterling@'@.
1257A wide C character constant is the same, except prefixed by the letter @L@, @u@, or @U@, \eg @u'\u25A0'@ (black square), where the @\u@ identifies a universal character name.
1258A character can be formed from an escape sequence, which expresses a non-typable character @'\f'@ form feed, a delimiter character @'\''@ embedded single quote, or a raw character @'\xa3'@ \textsterling.
1259
1260A C character string is zero or more regular, wide, or escape characters enclosed in double-quotes @"xyz\n"@.
1261The kind of characters in the string is denoted by a prefix: UTF-8 characters are prefixed by @u8@, wide characters are prefixed by @L@, @u@, or @U@.
1262
1263For UTF-8 string literals, the array elements have type @char@ and are initialized with the characters of the multi-byte character sequences, \eg @u8"\xe1\x90\x87"@ (Canadian syllabics Y-Cree OO).
1264For wide string literals prefixed by the letter @L@, the array elements have type @wchar_t@ and are initialized with the wide characters corresponding to the multi-byte character sequence, \eg @L"abc@$\mu$@"@ and are read/printed using @wsanf@/@wprintf@.
1265The value of a wide-character is implementation-defined, usually a UTF-16 character.
1266For wide string literals prefixed by the letter @u@ or @U@, the array elements have type @char16_t@ or @char32_t@, respectively, and are initialized with wide characters corresponding to the multi-byte character sequence, \eg @u"abc@$\mu$@"@, @U"abc@$\mu$@"@.
1267The value of a @"u"@ character is an UTF-16 character;
1268the value of a @"U"@ character is an UTF-32 character.
1269The value of a string literal containing a multi-byte character or escape sequence not represented in the execution character set is implementation-defined.
1270
1271C strings are null-terminated rather than maintaining a separate string length.
1272\begin{quote}
1273Technically, a string is an array whose elements are single characters.
1274The compiler automatically places the null character @\0@ at the end of each such string, so programs can conveniently find the end.
1275This representation means that there is no real limit to how long a string can be, but programs have to scan one completely to determine its length.~\cite[p.~36]{C:old}
1276\end{quote}
1277This property is only preserved by the compiler with respect to character constants, \eg @"abc"@ is actually @"abc\0"@, \ie 4 characters rather than 3.
1278Otherwise, the compiler does not participate, making string operations both unsafe and inefficient.
1279For example, it is common in C to: forget that a character constant is larger than it appears during manipulation, that extra storage is needed in a character array for the terminator, or that the terminator must be preserved during string operations, otherwise there are array overruns.
1280Finally, the need to repeatedly scan an entire string to determine its length can result in significant cost, as it is impossible to cache the length in many cases, \eg when a string is passed into another function.
1281
1282C strings are fixed size because arrays are used for the implementation.
1283However, string manipulation commonly results in dynamically-sized temporary and final string values, \eg @strcpy@, @strcat@, @strcmp@, @strlen@, @strstr@, \etc.
1284As a result, storage management for C strings is a nightmare, quickly resulting in array overruns and incorrect results.
1285
1286Collectively, these design decisions make working with strings in C, awkward, time consuming, and unsafe.
1287While there are companion string routines that take the maximum lengths of strings to prevent array overruns, \eg @strncpy@, @strncat@, @strncpy@, that means the semantics of the operation can fail because strings are truncated.
1288Suffice it to say, C is not a go-to language for string applications, which is why \CC introduced the dynamically-sized @string@ type.
Note: See TracBrowser for help on using the repository browser.