Changeset 7ca6bf1 for doc/theses

Timestamp:

Aug 20, 2025, 12:12:31 PM (6 months ago)

Author:

Michael Brooks <mlbrooks@…>

Branches:

master, stuck-waitfor-destruct

Children:

1dec8f3

Parents:

9989781 (diff), 7ea4073 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:

doc/theses/mike_brooks_MMath

Files:

• array.tex (modified) (1 diff)
• background.tex (modified) (4 diffs)
• conclusion.tex (modified) (1 diff)
• intro.tex (modified) (6 diffs)
• list.tex (modified) (12 diffs)
• string.tex (modified) (2 diffs)
• uw-ethesis-frontpgs.tex (modified) (1 diff)
• uw-ethesis.bib (modified) (1 diff)

doc/theses/mike_brooks_MMath/array.tex

@@ -93 +93 @@
 In an imperative language like C and \CFA, it is also necessary to discuss side effects, for which an even heavier formalism, like separation logic, is required.
 Secondly, TODO: bash Rust.
-TODO: cite the crap out of these claims.
+% TODO: cite the crap out of these claims.
 \end{comment}
 

doc/theses/mike_brooks_MMath/background.tex

@@ -36 +36 @@
 % Yet, the rejection presents as a GCC warning.
 % *1  TAPL-pg1 definition of a type system
-
-% reading C declaration: https://c-faq.com/decl/spiral.anderson.html
 
 
@@ -96 +94 @@
 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}
 \end{quote}
-After all, reading a C array type is easy: just read it from the inside out, and know when to look left and when to look right!
+After all, reading a C array type is easy: just read it from the inside out following the ``clock-wise spiral rule''~\cite{Anderson94}.
 Unfortunately, \CFA cannot correct these operator priority inversions without breaking C compatibility.
-
-TODO: rephrase to acknowledge the "clockwise rule" https://c-faq.com/decl/spiral.anderson.html
 
 The alternative solution is for \CFA to provide its own type, variable and routine declarations, using a more intuitive syntax.
@@ -621 +617 @@
 In fact, the outermost type constructor (syntactically first dimension) is really the one that determines the parameter flavour.
 
-TODO: add examples of mycode/arrr/bugs/c-dependent/x.cfa:v5102,5103,
-which are shocking how much C ignores.
+\PAB{TODO: add examples of mycode/arrr/bugs/c-dependent/x.cfa:v5102,5103,
+which are shocking how much C ignores.}
 
 \begin{figure}
@@ -1261 +1257 @@
 The kind of characters in the string is denoted by a prefix: UTF-8 characters are prefixed by @u8@, wide characters are prefixed by @L@, @u@, or @U@.
 
-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 syllabics Y-Cree OO).
+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).
 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@.
 The value of a wide-character is implementation-defined, usually a UTF-16 character.

doc/theses/mike_brooks_MMath/conclusion.tex

@@ -1 +1 @@
 \chapter{Conclusion}
+
+This thesis performed a detailed examination of the three most important high-level containers in many programming languages: array, linked-list, and string.
+The goal of the work is to make containers easier to use, performant and safer.
+Since some subset of these three containers are used in almost every program in every programming language, this is a laudable goal.
+Accomplishing this goal in C is difficult because these features are poorly designed.
+In contrast, \CFA's advanced type system and language features plus my critical design choices made it possible to provide better support with significant safety.
+The result is application code that is easier to write, understand, maintain, and safer from hacker attach-vectors.
 
 \section{Lists}
 
+The key takeaway for lists is that intrusive lists can be made easy to use, performant by eliminating implicit memory allocation, and able to simulate wrapped lists, whereas wrapped lists cannot simulate intrusive lists.
+
 \section{Arrays}
+
+The key takeaway for arrays is that the type system must be extended to properly manage array bounds (dimensions) to safely pass arrays to (polymorphic) functions.
+By adding a special kind of template constant to \CFA, @[N]@, the type system understands array bounds and implicitly associates these bounds with array instances, statically and dynamically, throughout the programming language.
+Array overruns are no longer possible because all subscripting is checked, as in other modern languages.
+Subscript checking can be implicitly elided when the compiler is given sufficient information to determine the subscript variable is always in bounds, giving performant execution.
+
+Safe, complex VLA's is another important feature because it replaces unsafe explicit dynamic allocation.
+As well, VLA's reduce heap contention in concurrent programs.
+
+Finally, the ability to slice a higher-dimensional array into subarrays is also a powerful and safety critical feature.
+
 
 \section{Strings}
 
+The key takeaway for strings is that providing powerful and safe block operations for manipulating strings is more important than ultra-level performance.
+Manipulating strings is always going to be expensive because of their dynamic variable sizing, as the hardware rarely has string-level operations, possibly only move and compare.
+This work designs an expressive set of safe string operations for composing, comparing, and decomposing arbitrary length strings, include complex reading and printing operations.
+
+Creating bespoke storage management for strings has the advantage of faster, more compact storage management due to string sharing, at the cost of additional external fragmentation between the string and general heaps.
+With the large amounts of available memory, this approach is a viable tradeoff.
+
+
+
 \section{Future Work}
+
+All three forms of containers presented in this work are in their nascence, both in design and implementation.
+This work provides the foundation for future \CFA students to add more functionality along with robust and performant implementations.
+

doc/theses/mike_brooks_MMath/intro.tex

@@ -5 +5 @@
 For all three types, languages and/or their libraries supply varying degrees of high-level mechanisms for manipulating these objects at the bulk and component level, such as copying, slicing, extracting, and iterating among elements.
 
-Unfortunately, these three aspects of C cause a significant number of memory errors~\cite{vanOorschot23}.
+Unfortunately, these three aspects of C cause a significant number of memory errors~\cite{Oorschot23}.
 For operating system and browser vendors, who heavily use systems languages, 60\%--70\% of reported software vulnerabilities involved memory errors~\cite{Kehrer23}.
 For Microsoft, 70\% of vulnerabilities addressed via security updates between 2006--2018 are memory safety issues~\cite[slide 10]{Miller19}.
@@ -21 +21 @@
 
 \section{Array}
-\label{s:ArrayIntro}
 
 An array provides a homogeneous container with $O(1)$ access to elements using subscripting.
@@ -66 +65 @@
 
 
+\begin{comment}
 \section{Iterator}
 
@@ -72 +72 @@
 However, the general iteration work is only a sketch for others as future work.
 Nevertheless, sufficed work was done to write out the ideas that developed and how they should apply in the main context of this work. 
+\end{comment}
 
 
@@ -160 +161 @@
 
 
+\begin{comment}
 \subsection{Iterator}
 
@@ -169 +171 @@
 This design extends a preexisting proposal to adapt the \CFA (fixed) for-each loop to be more user-pluggable, and builds upon preexisting \CFA coroutines.
 Overall, it simplifies the work a programmer must do to leverage the suspended-state abstraction during iteration.
+\end{comment}

doc/theses/mike_brooks_MMath/list.tex

@@ -88 +88 @@
 \subsection{Core Design Issues}
 
-The doubly-linked list attaches links intrusively, supports multiple link directions, integrates with user code via the type system, treats its ends uniformly, and identifies a list using an explicit head.
+The doubly-linked list attaches links intrusively, supports multiple link axes, integrates with user code via the type system, treats its ends uniformly, and identifies a list using an explicit head.
 This design covers system and data management issues stated in \VRef{toc:lst:issue}.
 
@@ -101 +101 @@
 \begin{figure}
     \lstinput{20-30}{lst-features-intro.run.cfa}
-    \caption[Multiple link directions in \CFA list library]{
+    \caption[Multiple link axes in \CFA list library]{
         Demonstration of the running \lstinline{req} example, done using the \CFA list library.
         This example is equivalent to the three approaches in \VRef[Figure]{fig:lst-issues-attach}.
@@ -128 +128 @@
 \end{figure}
 
-\VRef[Figure]{fig:lst-features-multidir} shows how the \CFA library supports multi-inline links, so a node can be on one or more lists simultaneously.
+\VRef[Figure]{fig:lst-features-multidir} shows how the \CFA library supports multi-inline links, so a node can be on one or more lists simultaneously (axes).
 The declaration of @req@ has two inline-inheriting @dlink@ occurrences.
 The first of these gives a type named @req.by_pri@, @req@ inherits from it, and it inherits from @dlink@.
@@ -150 +150 @@
 
 \caption{
-        Demonstration of multiple static link directions done in the \CFA list library.
+        Demonstration of multiple static link axes done in the \CFA list library.
         The right example is from \VRef[Figure]{fig:lst-issues-multi-static}.
                 The left \CFA example does the same job.
@@ -158 +158 @@
 
 The list library also supports the common case of single directionality more naturally than LQ.  
-Returning to \VRef[Figure]{fig:lst-features-intro}, the single-direction list has no contrived name for the link direction as it uses the default type in the definition of @dlist@;
+Returning to \VRef[Figure]{fig:lst-features-intro}, the single-axis list has no contrived name for the link axis as it uses the default type in the definition of @dlist@;
 in contrast, the LQ list in \VRef[Figure]{f:Intrusive} adds the unnecessary field name @d@.
-In \CFA, a single direction list sets up a single inheritance with @dlink@, and the default list axis is to itself.
-
-When operating on a list with several directions and operations that do not take the list head, the list axis can be ambiguous.
+In \CFA, a single axis list sets up a single inheritance with @dlink@, and the default list axis is to itself.
+
+When operating on a list with several axes and operations that do not take the list head, the list axis can be ambiguous.
 For example, a call like @insert_after( r1, r2 )@ does not have enough information to know which axes to select implicitly.
 Is @r2@ supposed to be the next-priority request after @r1@, or is @r2@ supposed to join the same-requester list of @r1@?
@@ -171 +171 @@
 To mitigate this issue, the list library provides a hook for applying the \CFA language's scoping and priority rules.
 \begin{cfa}
-with ( DLINK_VIA(  req, req.pri ) ) insert_after( r1, r2 );
+with ( DLINK_VIA( req, req.pri ) ) insert_after( r1, r2 );
 \end{cfa}
 Here, the @with@ statement opens the scope of the object type for the expression;
-hence, the @DLINK_VIA@ result causes one of the list directions to become a more attractive candidate to \CFA's overload resolution.
+hence, the @DLINK_VIA@ result causes one of the list axes to become a more attractive candidate to \CFA's overload resolution.
 This boost can be applied across multiple statements in a block or an entire function body.
 \begin{cquote}
@@ -192 +192 @@
 \end{tabular}
 \end{cquote}
-Within the @with@, the code acts as if there is only one list direction.
+Within the @with@, the code acts as if there is only one list axis, without explicit casting.
 
 Unlike the \CC template container-types, the \CFA library works completely within the type system;
 both @dlink@ and @dlist@ are ordinary types, not language macros.
 There is no textual expansion other than header-included static-inline function for performance.
-Hence, errors in user code are reported only with mention of the library's declarations.
+Hence, errors in user code are reported only with mention of the library's declarations, versus long template names in error messages.
 Finally, the library is separately compiled from the usage code, modulo inlining.
 
@@ -361 +361 @@
 \end{tabular}
 \end{cquote}
-Iterating forward and reverse through the entire list using the shorthand start at the list head and pick a direction.
+Iterating forward and reverse through the entire list using the shorthand start at the list head and pick a axis.
 In this case, @advance@ and @recede@ return a boolean, like \CC @while ( cin >> i )@.
 \begin{cquote}
@@ -629 +629 @@
 After each round, a counter is incremented by $n$ (for throughput).
 Time is measured outside the loop because a large $n$ can overrun the time duration before the @CONTINUE@ flag is tested.
+Hence, there is minimum of one outer (@CONTINUE@) loop iteration for large lists.
 The loop duration is divided by the counter and this throughput is reported.
 In a scatter-plot, each dot is one throughput, which means insert + remove + harness overhead.
@@ -636 +637 @@
 To test list operations, the experiment performs the inserts/removes in different patterns, \eg insert and remove from front, insert from front and remove from back, random insert and remove, \etc.
 Unfortunately, the @std::list@ does \emph{not} support direct insert/remove from a node without an iterator, \ie no @erase( node )@, even though the list is doubly-linked.
-To eliminate this additional cost in the harness, a trick is used for random insertions without replacement.
-The @i@ fields in each node are initialized from @0..n-1@, these @i@ values are then shuffled in the nodes, and the @i@ value is used to represent an indirection to that node for insertion, so the nodes are inserted in random order, and hence, removed in th same random order.
+To eliminate the iterator, a trick is used for random insertions without replacement.
+The @i@ fields in each node are initialized from @0..n-1@.
+These @i@ values are then shuffled in the nodes, and the @i@ value is used to represent an indirection to that node for insertion.
+hence, the nodes are inserted in random order and removed in the same random order.
 $\label{p:Shuffle}$
 \begin{c++}
@@ -644 +647 @@
 
         while ( CONTINUE ) {
-                for ( i; n ) insert_first( lst, nodes[ @nodes[i].i@ ] ); $\C{// build up}$
+                for ( i; n ) {
+                        node_t & temp = nodes[ nodes[i].i ];
+                        @temp.j = 0;@                           $\C{// touch random node for wrapped nodes}$
+                        insert_first( lst, temp );
+                }
+                insert_first( lst, nodes[ @nodes[i].i@ ] ); $\C{// build up}$
                 for ( i; n ) pass( &remove_first( lst ) );      $\C{// tear down}$
                 totalOpsDone += n;
         }
 \end{c++}
-This approach works across intrusive and wrapped lists.
+Note, insertion is traversing the list of nodes linearly, @node[i]@.
+For intrusive lists, the inserted (random) node is always touched because its link fields are read/written for insertion into the list.
+Hence, the array of nodes is being accessed both linearly and randomly during the traversal.
+For wrapped lists, the wrapped nodes are traversed linearly but the random node is not accessed, only a pointer to it is inserted into the linearly accessed wrapped node.
+Hence, the traversal is the same as the non-random traversal above.
+To level the experiments, an explicit access to the random node is inserted after the insertion, @temp.j = 0@, for the wrapped experiment.
+Furthermore, it is rare to insert/remove nodes and not access them.
 
 % \emph{Interleaving} allows for movements other than pure stack and queue.
@@ -770 +784 @@
 As a result, these memory layouts result in high spatial and temporal locality for both kinds of lists during the linear array traversal.
 With address look-ahead, the hardware does an excellent job of managing the multi-level cache.
-Hence, performance is largely constant for both kinds of lists, until cache and NUMA boundaries are crossed for longer lists and the costs increase consistently for both kinds of lists.
-
-In detail, \VRef[Figure]{f:Shuffled} shows shuffle insertion of all the nodes and then linear removal, both in the same direction.
+Hence, performance is largely constant for both kinds of lists, until L3 cache and NUMA boundaries are crossed for longer lists and the costs increase consistently for both kinds of lists.
+
+In detail, \VRef[Figure]{f:Shuffled} shows shuffle insertion and removal of the nodes.
 As for linear, there are issues with the wrapped list and memory allocation.
 For intrusive lists, it is possible to link the nodes randomly, so consecutive nodes in memory seldom point at adjacent nodes.

doc/theses/mike_brooks_MMath/string.tex

@@ -700 +700 @@
 \end{tabular}
 \end{cquote}
+\CC @setfill@ is not considered an important string manipulator.
 
 \CC input matching for @char@, @char *@, and @string@ are similar, where \emph{all} input characters are read from the current point in the input stream to the end of the type size, format width, whitespace, end of line (@'\n'@), or end of file.
@@ -1556 +1557 @@
 Timing outcomes report mean nanoseconds per invocation, which includes harness overhead and the targeted string API execution.
 
-\PAB{To discuss: hardware and such}
-
 As discussed in \VRef[Section]{string-raii-limit}, general performance comparisons are made using \CFA's faster, low-level string API, named @string_res@.
 \VRef{s:ControllingImplicitSharing} presents an operational mode where \CFA string sharing is turned off.
 In this mode, the \CFA string operates similarly to \CC's, by using a heap allocation for string text.
 Some experiments include measurements in this mode for baselining purposes, called ``\CC emulation mode'' or ``nosharing''.
+
+See~\VRef{s:ExperimentalEnvironment} for a description of the hardware environment.
 
 

doc/theses/mike_brooks_MMath/uw-ethesis-frontpgs.tex

@@ -132 +132 @@
 Often array is part of the programming language, while linked-list is built from (recursive) pointer types, and string from a combination of array and linked-list.
 For all three types, languages and/or their libraries supply varying degrees of high-level mechanisms for manipulating these objects at the bulk and component level, such as copying, slicing, extracting, and iterating among elements.
-Unfortunately, these three aspects of C cause 60\%--70\% of the reported software vulnerabilities involved memory errors, and 70\%-80\% of hacker attack-vectors target these types.
+Unfortunately, these three aspects of C cause 60\%--70\% of the reported software vulnerabilities involved memory errors, and 70\%--80\% of hacker attack-vectors target these types.
 Therefore, hardening these three C types goes a long way to make the majority of C programs safer.
 

doc/theses/mike_brooks_MMath/uw-ethesis.bib

@@ -140 +140 @@
 }
 
+
+@misc{Anderson94,
+    contributer = {pabuhr@plg},
+    title       = {Clockwise/Spiral Rule},
+    author      = {David Anderson},
+    year        = 1994,
+    month       = may,
+    howpublished= {\url{https://c-faq.com/decl/spiral.anderson.html}},
+}