Changeset 0f9c67bf

Timestamp:

Apr 13, 2026, 10:42:12 AM (2 weeks ago)

Author:

Michael Brooks <mlbrooks@…>

Branches:

master

Children:

68af77b

Parents:

5b21636b

Message:

establish and nail down definitions of operations and size zones

File:

• doc/theses/mike_brooks_MMath/list.tex (modified) (5 diffs)

doc/theses/mike_brooks_MMath/list.tex

@@ -2 +2 @@
 
 This chapter presents my work on designing and building a linked-list library for \CFA.
-Due to time limitations and the needs expressed by the \CFA runtime developers, I focussed on providing a doubly-linked list, and its bidirectionally iterators for traversal. 
+Due to time limitations and the needs expressed by the \CFA runtime developers, I focussed on providing a doubly-linked list, and its bidirectional iterators for traversal. 
 Simpler data-structures, like stack and queue, can be built from the doubly-linked mechanism with only a slight storage/performance cost because of the unused link field.
-Reducing to data-structures with a single link follows directly from the more complex doubly-links and its iterators.
+Reducing to data-structures with a single link follows directly from the more complex double links and its iterators.
 
 
@@ -666 +666 @@
 This experiment takes the position that:
 \begin{itemize}[leftmargin=*]
-        \item The total time to add and remove is relevant \vs individual times for add and remove.
+        \item The total time to add and remove is relevant, as opposed to having one individual time for adding and a separate time for removing.
                   Adds without removes quickly fill memory;
                   removes without adds is meaningless.
@@ -673 +673 @@
                 \item[movement]
                   Is the add/remove applied to a stack, queue, or something else?
+                  In these experiments, strict stack and queue shapes are tested (two movements).
                 \item[polarity]
                   In which direction does the action apply?
                   For a queue, do items flow from first to last or last to first?
                   For a stack, is the first or last end used for adding and removing?
+                  In these experiments, both polarities are considered, labelled insert-first and insert-last (two polarities).
                 \item[accessor]
-                  Is an add/remove location given by a list head's first/last, or by a reference to an individual element?
+                  Is an add/remove location given by a list head's first/last (@insertFirst@, @removeLast@), or by a reference to an individual element (@insertAfter@, @remove@ of element)?
+                  In these experiments, the (three) accessors are:
+                  \begin{itemize}
+                  \item
+              inserts and removes both through the head ("all-head")
+                  \item
+          insert by element and remove through the head ("insert-element")
+                  \item
+                  insert through head and remove by element ("remove-element")
+                  \end{itemize}
                 \end{description}
+        \item So, an "operating scenario" is a specific selection of movement, polarity and accessor. These experiments run twelve operating scenarios.
         \item Speed differences caused by the host machine's memory hierarchy need to be identified and explained,
                   but do not represent advantages of one linked-list implementation over another.
@@ -691 +703 @@
 \begin{itemize}
         \item intrusive lists performing (majorly) differently than wrapped lists,
-        \item a space of (minor) performance differences among the intrusive lists.
+        \item a space of (lesser) performance differences among the intrusive lists.
 \end{itemize}
 
+In the result analysis, a where list length is a performance-influencing factor, once truly ``large'' lengths have been dismissed, these zones are identified as representing different patterns:
+\begin{description}
+        \item[size zone ``small''] lists of 4--16 elements
+        \item[size zone ``medium''] lists of 50--200 elements
+\end{description}
+Each zone buckets four specific sizes at which trials are run.
 
 \subsubsection{Experiment setup}
@@ -1170 +1188 @@
 
 In spite of these complex interactions, a couple spots of stability can be analyzed.
-In these examples, the size zones 4--16, ``small,'' and above 48, ``medium,'' covering four specific sizes apiece, each tends to show a simple winner/loser story.
+In these examples, the two defined Size Zones (4--16 being ``small,'' and above 50 being ``medium,'') covering four specific sizes apiece, each tends to show a simple winner/loser story.
 Manual inspection of other such plots (not detailed) showed that this quality is generally upheld.
 So these zones are used for basing comparison.