source: doc/theses/mike_brooks_MMath/list.tex @ 40ab446

Last change on this file since 40ab446 was 40ab446, checked in by Michael Brooks <mlbrooks@…>, 4 months ago

Recent thesis writing

  • Property mode set to 100644
File size: 21.9 KB
Line 
1\chapter{Linked List}
2
3I wrote a linked-list library for \CFA.  This chapter describes it.
4
5The library provides a doubly-linked list that
6attaches links intrusively,
7supports multiple link directions,
8integrates with user code via the type system,
9treats its ends uniformly, and
10identifies a list using an explicit head.
11
12TODO: more summary
13
14
15\section{Design Issues}
16\label{toc:lst:issue}
17
18This section introduces the design space for linked lists that target system programmers.
19
20All design-issue discussions assume the following invariants.
21\PAB{They are stated here to clarify that none of the discussed design issues refers to one of these.}
22Alternatives to the assumptions are discussed under Future Work (Section~\ref{toc:lst:futwork}).
23\begin{itemize}
24    \item A doubly-linked list is being designed.
25          Generally, the discussed issues apply similarly for singly-linked lists.
26          Circular vs ordered linking is discussed under List identity (Section~\ref{toc:lst:issue:ident}).
27    \item Link fields are system-managed.
28          The user works with the system-provided API to query and modify list membership.
29          The system has freedom over how to represent these links.
30          The library is not providing applied wrapper operations that consume a user's hand-implemented list primitives.
31    \item \PAB{These issues are compared at a requirement/functional level.}
32\end{itemize}
33
34Two preexisting linked-list libraries are used throughout, to show examples of the concepts being defined,
35and further libraries are introduced as needed.
36\begin{description}
37    \item[LQ] Linux Queue library\cite{lst:linuxq} of @<sys/queue.h>@.
38    \item[STL] C++ Standard Template Library's @std::list@\cite{lst:stl}
39\end{description}
40A general comparison of libraries' abilities is given under Related Work (Section~\ref{toc:lst:relwork}).
41
42The fictional type @req@ (request) is the user's payload in examples.
43The list library is helping the user track requests.
44A request represents work that the user must do but has not done yet.
45This work is on the level of handling a network arrival event or scheduling a thread.
46
47
48
49\subsection{Link attachment: Intrusive vs.\ Wrapped}
50\label{toc:lst:issue:attach}
51
52Link attachment deals with the question:
53Where are the system's inter-element link fields stored, in relation to the user's payload data fields?
54An intrusive list places the link fields inside the payload structure.
55A wrapped list places the payload inside a generic system-provided structure that also defines the link fields.
56LQ is intrusive; STL is wrapped.
57
58The wrapped style admits the further distinction between wrapping a reference and wrapping a value.
59This distinction is pervasive in all STL collections; @list<req *>@ wraps a reference; @list<req>@ wraps a value.
60(For this discussion, @list<req &>@ is similar to @list<req *>@.)
61This difference is one of user style, not framework capability.
62Figure~\ref{fig:lst-issues-attach} compares the three styles.
63
64\begin{comment}
65\begin{figure}
66    \begin{tabularx}{\textwidth}{Y|Y|Y}\lstinputlisting[language=C  , firstline=20, lastline=39]{lst-issues-intrusive.run.c}
67        &\lstinputlisting[language=C++, firstline=20, lastline=39]{lst-issues-wrapped-byref.run.cpp}
68        &\lstinputlisting[language=C++, firstline=20, lastline=39]{lst-issues-wrapped-emplaced.run.cpp}
69      \\ & &
70      \\
71        \includegraphics[page=1]{lst-issues-attach.pdf}
72        &
73        \includegraphics[page=2]{lst-issues-attach.pdf}
74        &
75        \includegraphics[page=3]{lst-issues-attach.pdf}
76      \\ & &
77      \\
78        (a) & (b) & (c)
79    \end{tabularx}
80\caption{
81        Three styles of link attachment: (a)~intrusive, (b)~wrapped reference, and (c)~wrapped value.
82        The diagrams show the memory layouts that result after the code runs, eliding the head object \lstinline{reqs};
83        head objects are discussed in Section~\ref{toc:lst:issue:ident}.
84        In (a), the field \lstinline{req.x} names a list direction;
85        these are discussed in Section~\ref{toc:lst:issue:derection}.
86        In (b) and (c), the type \lstinline{node} represents a system-internal type,
87        which is \lstinline{std::_List_node} in the GNU implementation.
88        (TODO: cite? found in  /usr/include/c++/7/bits/stl\_list.h )
89    }
90     \label{fig:lst-issues-attach}
91\end{figure}
92\end{comment}
93
94\begin{figure}
95\centering
96\newsavebox{\myboxA}                                    % used with subfigure
97\newsavebox{\myboxB}
98\newsavebox{\myboxC}
99
100\begin{lrbox}{\myboxA}
101\begin{tabular}{@{}l@{}}
102\lstinputlisting[language=C, firstline=20, lastline=39]{lst-issues-intrusive.run.c} \\
103\ \\
104\includegraphics[page=1]{lst-issues-attach.pdf}
105\end{tabular}
106\end{lrbox}
107
108\begin{lrbox}{\myboxB}
109\begin{tabular}{@{}l@{}}
110\lstinputlisting[language=C++, firstline=20, lastline=39]{lst-issues-wrapped-byref.run.cpp} \\
111\ \\
112\includegraphics[page=2]{lst-issues-attach.pdf}
113\end{tabular}
114\end{lrbox}
115
116\begin{lrbox}{\myboxC}
117\begin{tabular}{@{}l@{}}
118\lstinputlisting[language=C++, firstline=20, lastline=39]{lst-issues-wrapped-emplaced.run.cpp} \\
119\ \\
120\includegraphics[page=3]{lst-issues-attach.pdf}
121\end{tabular}
122\end{lrbox}
123
124\subfloat[Intrusive]{\label{f:Intrusive}\usebox\myboxA}
125\hspace{10pt}
126\vrule
127\hspace{10pt}
128\subfloat[Wrapped reference]{\label{f:WrappedRef}\usebox\myboxB}
129\hspace{10pt}
130\vrule
131\hspace{10pt}
132\subfloat[Wrapped value]{\label{f:WrappedValue}\usebox\myboxC}
133
134\caption{
135        Three styles of link attachment: \protect\subref*{f:Intrusive}~intrusive, \protect\subref*{f:WrappedRef}~wrapped
136        reference, and \protect\subref*{f:WrappedValue}~wrapped value.
137        The diagrams show the memory layouts that result after the code runs, eliding the head object \lstinline{reqs};
138        head objects are discussed in Section~\ref{toc:lst:issue:ident}.
139        In \protect\subref*{f:Intrusive}, the field \lstinline{req.x} names a list direction;
140        these are discussed in Section~\ref{toc:lst:issue:derection}.
141        In \protect\subref*{f:WrappedRef} and \protect\subref*{f:WrappedValue}, the type \lstinline{node} represents a
142        system-internal type, which is \lstinline{std::_List_node} in the GNU implementation.
143        (TODO: cite? found in  /usr/include/c++/7/bits/stl\_list.h )
144    }
145    \label{fig:lst-issues-attach}
146\end{figure}
147
148The advantage of intrusive attachment is the control that it gives the user over memory layout.
149Each diagrammed example is using the fewest dynamic allocations that its respective style allows.
150Both wrapped attachment styles imply system-induced heap allocations.
151Such an allocation has a lifetime that matches the item's membership in the list.
152In \subref*{f:Intrusive} and \subref*{f:WrappedRef}, one @req@ object can enter and leave a list many times.
153In \subref*{f:WrappedRef}, it implies a dynamic allocation/deallocation for each enter/leave; in \subref*{f:Intrusive}, it does not.
154
155A further aspect of layout control is allowing the user to specify the location of the link fields within the @req@ object.
156LQ allows this ability; a different mechanism of intrusion, such as inheriting from a @linkable@ base type, may not.
157Having this control means the user can allocate the link fields to cache lines along with the other @req@ fields.
158Doing this allocation sensibly can help improve locality or avoid false sharing.
159With an attachment mechanism that does not offer this control,
160a framework design choice or fact of the host language forces the links to be contiguous with either the beginning or end of the @req@.
161All wrapping realizations have this limitation in their wrapped-value configurations.
162
163Another subtle advantage of intrusive arrangement is that
164a reference to a user-level item (@req@) is sufficient to navigate or manage the item's membership.
165In LQ, \subref*{f:Intrusive}, a @req@ pointer is the right argument type for operations @LIST_NEXT@ or @LIST_REMOVE@;
166there is no distinguishing a @req@ from ``a @req@ in a list.''
167The same is not true of STL, \subref*{f:WrappedRef} or \subref*{f:WrappedValue}.
168There, the analogous operations work on a parameter of type @list<T>::iterator@;
169they are @iterator::operator++()@, @iterator::operator*()@, and @list::erase(iterator)@.
170There is no mapping from @req &@ to @list<req>::iterator@, except for linear search.
171
172The advantage of wrapped attachment is the abstraction of a data item from its list membership(s).
173In the wrapped style, the @req@ type can come from a library that serves many independent uses,
174which generally have no need for listing.
175Then, a novel use can still put @req@ in a (further) list, without requiring any upstream change in the @req@ library.
176In intrusive attachment, the ability to be listed must be planned during the definition of @req@.
177Similarly, style \subref*{f:WrappedRef} allows for one @req@ to occur at several positions in one list.
178Styles \subref*{f:Intrusive} and \subref*{f:WrappedValue} do not support this ability.
179\PAB{But style \subref*{f:WrappedValue} can sort of mimic this effect by have multiple copies of \lstinline{req} in the list, modulo changes to the copies are not seen by the original.}
180
181\begin{figure}
182    \lstinputlisting[language=C++, firstline=100, lastline=117]{lst-issues-attach-reduction.hpp}
183    \lstinputlisting[language=C++, firstline=150, lastline=150]{lst-issues-attach-reduction.hpp}
184    \caption{
185        Reduction of wrapped attachment to intrusive attachment.
186        Illustrated by pseudocode implementation of an STL-compatible API fragment
187        using LQ as the underlying implementation.
188        The gap that makes it pseudocode is that
189        the LQ C macros do not expand to valid C++ when instantiated with template parameters---there is no \lstinline{struct El}.
190        When using a custom-patched version of LQ to work around this issue,
191        the programs of Figure~\ref{f:WrappedRef} and \protect\subref*{f:WrappedValue} work with this shim in place of real STL.
192        Their executions lead to the same memory layouts.
193    }
194    \label{fig:lst-issues-attach-reduction}
195\end{figure}
196
197Wrapped attachment has a straightforward reduction to intrusive attachment, illustrated in Figure~\ref{fig:lst-issues-attach-reduction}.
198This shim layer performs the implicit dynamic allocations that pure intrusion avoids.
199But there is no reduction going the other way.
200No shimming can cancel the allocations to which wrapped membership commits.
201
202So intrusion is a lower-level listing primitive.
203And so, the system design choice is not between forcing users to use intrusion or wrapping.
204The choice is whether or not to provide access to an allocation-free layer of functionality.
205A wrapped-primitive library like STL forces users to incur the costs of wrapping, whether or not they access its benefits.
206An intrusive-primitive library like LQ lets users choose when to make this tradeoff.
207
208
209\subsection{Directionality: Single vs.\ Multi-Static vs.\ Dynamic}
210\label{toc:lst:issue:derection}
211
212Axis?
213
214\PAB{I'm not sure about the term \newterm{Directionality}. Directionality to me, means going forward or backwards through a list.
215Would \newterm{dimensionality} work? Think of each list containing the node as a different dimension in which the node sits.}
216
217Directionality deals with the question:
218In how many different lists can an item be stored, at a given time?
219
220Consider STL in the wrapped-value arrangement of Figure~\ref{f:WrappedValue}.
221The STL API completely hides its @node@ type from a user; the user cannot configure this choice or impose a custom one.
222STL's @node@ type offers the sole set of links shown in the diagram.
223Therefore, every @req@ in existence is allocated either to belong to an occurrence of the diagrammed arrangement,
224or to be apart from all occurrences of it.
225In the first case, the @req@ belongs to exactly one list (of the style in question).
226STL with wrapped values supports a single link direction.
227
228\begin{figure}
229    \parbox[t]{3.5in} {
230        \lstinputlisting[language=C++, firstline=20, lastline=60]{lst-issues-multi-static.run.c}
231    }\parbox[t]{20in} {
232        ~\\
233        \includegraphics[page=1]{lst-issues-direct.pdf} \\
234        ~\\
235        \hspace*{1.5in}\includegraphics[page=2]{lst-issues-direct.pdf}
236    }
237    \caption{
238        Example of two link directions, with an LQ realization. 
239        The zoomed-out diagram portion shows the whole example dataset, conceptually.
240        A consumer of this structure can navigate all requests in priority order, and navigate among requests from a common requestor.
241        The code is the LQ implementation.
242        The zoomed-in diagram portion shows the field-level state that results from running the LQ code.
243    }
244    \label{fig:lst-issues-multi-static}
245\end{figure}
246
247
248The user may benefit from a further link direction.
249Suppose the user must both: navigate all requests in priority order, and navigate among requests from a common requestor.
250Figure~\ref{fig:lst-issues-multi-static} shows such a situation.
251Each of its ``by priority'' and ``by requestor'' is a link direction.
252The example shows that a link direction can occur either as one global list (by-priority) or as many lists (there are three by-requestor lists).
253
254The limitation of intrusive attachment presented in Section~\ref{toc:lst:issue:attach}
255has a straightforward extension to multiple directions.
256The set of directions by which an item is to be listed must be planned during the definition of the item.
257Thus, intrusive LQ supports multiple, but statically many, link directions.
258
259% 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;`
260
261The corresponding flexibility of wrapped attachment means
262the STL wrapped-reference arrangement supports an item being a member of arbitrarily many lists.
263This support also applies to the wrapped-value list because the @req@ is copied,
264but wrapped-reference lists provide further link directions.
265\PAB{Explain how}
266STL with wrapped references supports dynamic link directions.
267\PAB{Expand}
268
269When allowing multiple static directions, frameworks differ in their ergonomics for
270the typical case: when the user needs only one direction, vs.\ the atypical case, when the user needs several.
271LQ's ergonomics are well-suited to the uncommon case of multiple list directions.
272Its intrusion declaration and insertion operation both use a mandatory explicit parameter naming the direction.
273This decision works well in Figure~\ref{fig:lst-issues-multi-static}, where the names @by_pri@ and @by_rqr@ work well,
274but it clutters Figure~\ref{f:Intrusive}, where a contrived name must be invented and used.
275The example uses @x@; @reqs@ would be a more readily ignored choice. \PAB{wording?}
276
277\uCpp offers an intrusive list that makes the opposite choice.  TODO: elaborate on inheritance for first direction and acrobatics for subsequent directions.
278
279
280\subsection{User integration: Preprocessed vs.\ Type-System Mediated}
281
282% example of poor error message due to LQ's preprocessed integration
283% programs/lst-issues-multi-static.run.c:46:1: error: expected identifier or '(' before 'do'
284%    46 | LIST_INSERT_HEAD(&reqs_rtr_42, &r42b, by_rqr);
285%       | ^~~~~~~~~~~~~~~~
286%
287% ... not a wonderful example; it was a missing semicolon on the preceding line; but at least real
288
289
290\subsection{List identity: Headed vs.\ Ad-hoc}
291\label{toc:lst:issue:ident}
292
293All examples so far have used distinct user-facing types:
294an item found in a list (type @req@, of variables like @r1@), and
295a list (type @reql@ or @list<req>@, of variables like @reqs@ or @reqs_rqr_42@).
296\see{Figure~\ref{fig:lst-issues-attach} and Figure~\ref{fig:lst-issues-multi-static}}
297The latter type is a head, and these examples are of headed lists.
298
299A bespoke ``pointer to next @req@'' implementation often omits the latter type.
300Such a list model is ad-hoc.
301
302In headed thinking, there are length-zero lists (heads with no elements), and an element can be listed or not listed.
303In ad-hoc thinking, there are no length-zero lists and every element belongs to a list of length at least one.
304\PAB{Create a figure for this.}
305
306By omitting the head, elements can enter into an adjacency relationship,
307without requiring that someone allocate room for the head of the possibly-resulting list,
308or being able to find a correct existing head.
309
310A head defines one or more element roles, among elements that share a transitive adjacency.
311``First'' and ``last'' are element roles.
312One moment's ``first'' need not be the next moment's.
313
314There is a cost to maintaining these roles.
315A runtime component of this cost is evident in LQ's offering the choice of type generators @LIST@ vs.~@TAILQ@.
316Its @LIST@ maintains a ``first,'' but not a ``last;'' its @TAILQ@ maintains both roles.
317(Both types are doubly linked and an analogous choice is available for singly linked.)
318
319TODO: finish making this point
320
321See WIP in lst-issues-adhoc-*.ignore.*.
322
323The code-complexity component of the cost ...
324
325Ability to offer heads is good.  Point: Does maintaining a head mean that the user has to provide more state when manipulating the list?  Requiring the user to do so is bad, because the user may have lots of "list" typed variables in scope, and detecting that the user passed the wrong one requires testing all the listing edge cases.
326
327\subsection{End treatment: Uniform }
328
329
330\section{Features}
331
332\subsection{Core Design Issues}
333
334This section reviews how a user experiences my \CFA list library's position on the issues of Section~\ref{toc:lst:issue}.
335The library provides a doubly-linked list that
336attaches links intrusively,
337supports multiple link directions,
338integrates with user code via the type system,
339treats its ends uniformly, and
340identifies a list using an explicit head.
341
342The \CFA list library's version of the running @req@ example is in Figure~\ref{fig:lst-features-intro}.
343Its link attachment is intrusive and the resulting memory layout is pure-stack, just as for the LQ version of Figure~\ref{f:Intrusive}.
344The framework-provided type @dlink(...)@ provides the links.
345The user inserts the links into the @req@ structure by using \CFA inline-inheritance (TODO: reference introduction).
346Inline inheritance means the type of the field is @dlink(req)@, the field is unnamed, a reference to a @req@ is implicitly convertible to @dlink@.\footnote{
347    The \CFA list examples elide the \lstinline{P9_EMBEDDED} annotations that (TODO: xref P9E future work) proposes to obviate.
348    Thus, these examples illustrate a to-be state, free of what is to be historic clutter.
349    The elided portions are immaterial to the discussion and the examples work with the annotations provided.
350    The \CFA test suite (TODO:cite?) includes equivalent demonstrations, with the annotations included.}
351These links have a nontrivial, user-specified location within the @req@ structure;
352this convention encapsulates the implied pointer arithmetic safely.
353
354\begin{figure}
355    \lstinputlisting[language=CFA, firstline=20, lastline=32]{lst-features-intro.run.cfa}
356    \caption[Multiple link directions in \CFA list library]{
357        Demonstration of the running \lstinline{req} example, done using the \CFA list library.
358        This example does the same job that Figure~\ref{fig:lst-issues-attach} shows three ways.
359    }
360    \label{fig:lst-features-intro}
361\end{figure}
362
363\begin{figure}
364\centering
365\begin{tabular}{@{}ll@{}}
366\begin{tabular}{@{}l@{}}
367    \lstinputlisting[language=CFA, firstline=20, lastline=25]{lst-features-multidir.run.cfa} \\
368    \lstinputlisting[language=CFA, firstline=40, lastline=67]{lst-features-multidir.run.cfa}
369    \end{tabular}
370        &
371        \lstinputlisting[language=C++, firstline=20, lastline=60]{lst-issues-multi-static.run.c}
372        \end{tabular}
373
374\caption{
375        Demonstration of multiple static link directions done in the \CFA list library.
376        This example does the same job as Figure~\ref{fig:lst-issues-multi-static}.
377    }
378    \label{fig:lst-features-multidir}
379\end{figure}
380
381Figure~\ref{fig:lst-features-multidir} shows how the \CFA library supports multi-static link directionality.
382The declaration of @req@ now has two inline-inheriting @dlink@ occurrences.
383The first of these lines gives a type named @req.by_pri@, @req@ inherits from it, and it inherits from @dlink@.
384The second line @req.by_rqr@ is similar to @req.by_pri@.
385Thus, there is a diamond, non-virtual, inheritance from @req@ to @dlink@, with @by_pri@ and @by_rqr@ being the mid-level types.
386Disambiguation occurs in the declarations of the list-head objects.
387The type of the variable @reqs_pri_global@ is @dlist(req, req.by_pri)@,
388meaning operations called on @reqs_pri_global@ are implicitly disambiguated.
389In the example, the calls @insert_first(reqs_pri_global, ...)@ imply, ``here, we are working by priority.''
390
391The \CFA library also supports the common case, of single directionality, more naturally than LQ. 
392Figure~\ref{fig:lst-features-intro} shows a single-direction list done with no contrived name for the link direction,
393where Figure~\ref{f:Intrusive} adds the unnecessary name, @x@.
394In \CFA, a user doing a single direction (Figure~\ref{fig:lst-features-intro})
395sets up a simple inheritance with @dlink@, and declares a list head to have the simpler type @dlist(...)@.
396While a user doing multiple link directions (Figure~\ref{fig:lst-features-multidir})
397sets up a diamond inheritance with @dlink@, and declares a list head to have the more-informed type @dlist(..., DIR)@.
398
399The \CFA library offers a type-system mediated integration with user code.
400The examples presented do not use preprocessor macros.
401The touchpoints @dlink@ and @dlist@ are ordinary types.
402Even though they are delivered as header-included static-inline implementations,
403the \CFA compiler typechecks the list library code separately from user code.
404Errors in user code are reported only with mention of the library's declarations.
405
406The \CFA library works in headed and headless modes.  TODO: elaborate.
407
408\subsection{Iteration-FOUNDATIONS}
409
410TODO: This section should be moved to a Foundations chapter.  The next section stays under Linked List.
411
412
413\subsection{Iteration}
414
415
416\section{Future Work}
417\label{toc:lst:futwork}
418
419
420TODO: deal with: A doubly linked list is being designed.
421
422TODO: deal with: Link fields are system-managed.
423Links in GDB.
424
425\section{Related Work}
426\label{toc:lst:relwork}
Note: See TracBrowser for help on using the repository browser.