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