Index: doc/theses/mike_brooks_MMath/list.tex =================================================================== --- doc/theses/mike_brooks_MMath/list.tex (revision cd477ca4b4fa70760b071f79006f06fedadef62c) +++ doc/theses/mike_brooks_MMath/list.tex (revision d800676cf9dcb4402f8b91c21cf9befd9330b2f0) @@ -13,5 +13,4 @@ - \section{Design Issues} \label{toc:lst:issue} @@ -20,5 +19,5 @@ All design-issue discussions assume the following invariants. -They are stated here to clarify that none of the discussed design issues refers to one of these. +\PAB{They are stated here to clarify that none of the discussed design issues refers to one of these.} Alternatives to the assumptions are discussed under Future Work (Section~\ref{toc:lst:futwork}). \begin{itemize} @@ -30,14 +29,14 @@ The system has freedom over how to represent these links. The library is not providing applied wrapper operations that consume a user's hand-implemented list primitives. - \item These issues are compared at a requirement/functional level. + \item \PAB{These issues are compared at a requirement/functional level.} \end{itemize} Two preexisting linked-list libraries are used throughout, to show examples of the concepts being defined, and further libraries are introduced as needed. -A general comparison of libraries' abilities is given under Related Work (Section~\ref{toc:lst:relwork}). \begin{description} \item[LQ] Linux Queue library\cite{lst:linuxq} of @@. \item[STL] C++ Standard Template Library's @std::list@\cite{lst:stl} \end{description} +A general comparison of libraries' abilities is given under Related Work (Section~\ref{toc:lst:relwork}). The fictional type @req@ (request) is the user's payload in examples. @@ -58,8 +57,10 @@ The wrapped style admits the further distinction between wrapping a reference and wrapping a value. -This distinction is pervasive in all STL collections; @list@ wraps a reference; @list@ wraps a value. -(For this discussion, @list@ is similar to @list@.) +This distinction is pervasive in all STL collections; @list@ wraps a reference; @list@ wraps a value. +(For this discussion, @list@ is similar to @list@.) This difference is one of user style, not framework capability. - +Figure~\ref{fig:lst-issues-attach} compares the three styles. + +\begin{comment} \begin{figure} \begin{tabularx}{\textwidth}{Y|Y|Y}\lstinputlisting[language=C , firstline=20, lastline=39]{lst-issues-intrusive.run.c} @@ -77,5 +78,5 @@ (a) & (b) & (c) \end{tabularx} - \caption{ +\caption{ Three styles of link attachment: (a)~intrusive, (b)~wrapped reference, and (c)~wrapped value. The diagrams show the memory layouts that result after the code runs, eliding the head object \lstinline{reqs}; @@ -87,9 +88,61 @@ (TODO: cite? found in /usr/include/c++/7/bits/stl\_list.h ) } + \label{fig:lst-issues-attach} +\end{figure} +\end{comment} + +\begin{figure} +\centering +\newsavebox{\myboxA} % used with subfigure +\newsavebox{\myboxB} +\newsavebox{\myboxC} + +\begin{lrbox}{\myboxA} +\begin{tabular}{@{}l@{}} +\lstinputlisting[language=C, firstline=20, lastline=39]{lst-issues-intrusive.run.c} \\ +\ \\ +\includegraphics[page=1]{lst-issues-attach.pdf} +\end{tabular} +\end{lrbox} + +\begin{lrbox}{\myboxB} +\begin{tabular}{@{}l@{}} +\lstinputlisting[language=C++, firstline=20, lastline=39]{lst-issues-wrapped-byref.run.cpp} \\ +\ \\ +\includegraphics[page=2]{lst-issues-attach.pdf} +\end{tabular} +\end{lrbox} + +\begin{lrbox}{\myboxC} +\begin{tabular}{@{}l@{}} +\lstinputlisting[language=C++, firstline=20, lastline=39]{lst-issues-wrapped-emplaced.run.cpp} \\ +\ \\ +\includegraphics[page=3]{lst-issues-attach.pdf} +\end{tabular} +\end{lrbox} + +\subfloat[Intrusive]{\label{f:Intrusive}\usebox\myboxA} +\hspace{10pt} +\vrule +\hspace{10pt} +\subfloat[Wrapped reference]{\label{f:WrappedRef}\usebox\myboxB} +\hspace{10pt} +\vrule +\hspace{10pt} +\subfloat[Wrapped value]{\label{f:WrappedValue}\usebox\myboxC} + +\caption{ + Three styles of link attachment: \protect\subref*{f:Intrusive}~intrusive, \protect\subref*{f:WrappedRef}~wrapped + reference, and \protect\subref*{f:WrappedValue}~wrapped value. + The diagrams show the memory layouts that result after the code runs, eliding the head object \lstinline{reqs}; + head objects are discussed in Section~\ref{toc:lst:issue:ident}. + In \protect\subref*{f:Intrusive}, the field \lstinline{req.x} names a list direction; + these are discussed in Section~\ref{toc:lst:issue:derection}. + In \protect\subref*{f:WrappedRef} and \protect\subref*{f:WrappedValue}, the type \lstinline{node} represents a + system-internal type, which is \lstinline{std::_List_node} in the GNU implementation. + (TODO: cite? found in /usr/include/c++/7/bits/stl\_list.h ) + } \label{fig:lst-issues-attach} \end{figure} - - -Figure~\ref{fig:lst-issues-attach} compares the three styles. The advantage of intrusive attachment is the control that it gives the user over memory layout. @@ -97,6 +150,6 @@ Both wrapped attachment styles imply system-induced heap allocations. Such an allocation has a lifetime that matches the item's membership in the list. -In (a) and (b), one @req@ object can enter and leave a list many times. -In (b), doing do implies a dynamic allocation for each time joining; in (a), it does not. +In \subref*{f:Intrusive} and \subref*{f:WrappedRef}, one @req@ object can enter and leave a list many times. +In \subref*{f:WrappedRef}, it implies a dynamic allocation/deallocation for each enter/leave; in \subref*{f:Intrusive}, it does not. A further aspect of layout control is allowing the user to specify the location of the link fields within the @req@ object. @@ -110,18 +163,19 @@ 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. -In LQ, (a), a @req@ pointer is the right argument type for operations @LIST_NEXT@ or @LIST_REMOVE@; +In LQ, \subref*{f:Intrusive}, a @req@ pointer is the right argument type for operations @LIST_NEXT@ or @LIST_REMOVE@; there is no distinguishing a @req@ from ``a @req@ in a list.'' -The same is not true of STL, (b) or (c). +The same is not true of STL, \subref*{f:WrappedRef} or \subref*{f:WrappedValue}. There, the analogous operations work on a parameter of type @list::iterator@; they are @iterator::operator++()@, @iterator::operator*()@, and @list::erase(iterator)@. -There is no mapping from @req&@ to @list::iterator@, except for linear search. +There is no mapping from @req &@ to @list::iterator@, except for linear search. The advantage of wrapped attachment is the abstraction of a data item from its list membership(s). In the wrapped style, the @req@ type can come from a library that serves many independent uses, which generally have no need for listing. -Then, a novel use can still put @req@ in a (further) list, without requiring any upstream change in the @re@ library. +Then, a novel use can still put @req@ in a (further) list, without requiring any upstream change in the @req@ library. In intrusive attachment, the ability to be listed must be planned during the definition of @req@. -Similarly, style (b) allows for one @req@ to occur at several positions in one list. -Styles (a) and (c) do not support this ability. +Similarly, style \subref*{f:WrappedRef} allows for one @req@ to occur at several positions in one list. +Styles \subref*{f:Intrusive} and \subref*{f:WrappedValue} do not support this ability. +\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.} \begin{figure} @@ -135,5 +189,5 @@ the LQ C macros do not expand to valid C++ when instantiated with template parameters---there is no \lstinline{struct El}. When using a custom-patched version of LQ to work around this issue, - the programs of Figure~\ref{fig:lst-issues-attach}~(b) and (c) work with this shim in place of real STL. + the programs of Figure~\ref{f:WrappedRef} and \protect\subref*{f:WrappedValue} work with this shim in place of real STL. Their executions lead to the same memory layouts. } @@ -147,5 +201,5 @@ So intrusion is a lower-level listing primitive. -And so, the system design choice is not between forcing users to use intrusion and forcing them to use wrapping. +And so, the system design choice is not between forcing users to use intrusion or wrapping. The choice is whether or not to provide access to an allocation-free layer of functionality. A wrapped-primitive library like STL forces users to incur the costs of wrapping, whether or not they access its benefits. @@ -153,17 +207,17 @@ - - \subsection{Directionality: Single vs.\ Multi-Static vs.\ Dynamic} \label{toc:lst:issue:derection} +\PAB{I'm not sure about the term \newterm{Directionality}. Directionality to me, means going forward or backwards through a list. +Would \newterm{dimensionality} work? Think of each list containing the node as a different dimension in which the node sits.} + Directionality deals with the question: In how many different lists can an item be stored, at a given time? - -Consider STL in the wrapped-value arrangement of Figure~\ref{fig:lst-issues-attach}~(c). +Consider STL in the wrapped-value arrangement of Figure~\ref{f:WrappedValue}. The STL API completely hides its @node@ type from a user; the user cannot configure this choice or impose a custom one. STL's @node@ type offers the sole set of links shown in the diagram. -Therefore, every @req@ in existence was allocated either to belong to an occurrence of the diagrammed arrangement, +Therefore, every @req@ in existence is allocated either to belong to an occurrence of the diagrammed arrangement, or to be apart from all occurrences of it. In the first case, the @req@ belongs to exactly one list (of the style in question). @@ -171,5 +225,4 @@ \begin{figure} - \label{fig:lst-issues-multi-static} \parbox[t]{3.5in} { \lstinputlisting[language=C++, firstline=20, lastline=60]{lst-issues-multi-static.run.c} @@ -187,4 +240,5 @@ The zoomed-in diagram portion shows the field-level state that results from running the LQ code. } + \label{fig:lst-issues-multi-static} \end{figure} @@ -205,26 +259,25 @@ The corresponding flexibility of wrapped attachment means the STL wrapped-reference arrangement supports an item being a member of arbitrarily many lists. -This support also applies to the hybrid in which an item's allocation is within a wrapped-value list, +This support also applies to the wrapped-value list because the @req@ is copied, but wrapped-reference lists provide further link directions. +\PAB{Explain how} STL with wrapped references supports dynamic link directions. - -When allowing multiple static directions,frameworks differ in their ergonomics for -the typical case, when the user needs only one direction, vs.\ the atypical case, when the user needs several. - +\PAB{Expand} + +When allowing multiple static directions, frameworks differ in their ergonomics for +the typical case: when the user needs only one direction, vs.\ the atypical case, when the user needs several. LQ's ergonomics are well-suited to the uncommon case of multiple list directions. Its intrusion declaration and insertion operation both use a mandatory explicit parameter naming the direction. This decision works well in Figure~\ref{fig:lst-issues-multi-static}, where the names @by_pri@ and @by_rqr@ work well, -but it clutters Figure~\ref{fig:lst-issues-attach}~(a), where a contrived name must be invented and used. -The example uses @x@; @reqs@ would be a more readily ignored choice. +but it clutters Figure~\ref{f:Intrusive}, where a contrived name must be invented and used. +The example uses @x@; @reqs@ would be a more readily ignored choice. \PAB{wording?} \uCpp offers an intrusive list that makes the opposite choice. TODO: elaborate on inheritance for first direction and acrobatics for subsequent directions. - - \subsection{User integration: Preprocessed vs.\ Type-System Mediated} % example of poor error message due to LQ's preprocessed integration -% programs/lst-issues-multi-static.run.c:46:1: error: expected identifier or ‘(’ before ‘do’ +% programs/lst-issues-multi-static.run.c:46:1: error: expected identifier or '(' before 'do' % 46 | LIST_INSERT_HEAD(&reqs_rtr_42, &r42b, by_rqr); % | ^~~~~~~~~~~~~~~~ @@ -239,5 +292,6 @@ an item found in a list (type @req@, of variables like @r1@), and a list (type @reql@ or @list@, of variables like @reqs@ or @reqs_rqr_42@). -The latter type is a head, and these examples are of are headed lists. +\see{Figure~\ref{fig:lst-issues-attach} and Figure~\ref{fig:lst-issues-multi-static}} +The latter type is a head, and these examples are of headed lists. A bespoke ``pointer to next @req@'' implementation often omits the latter type. @@ -246,4 +300,5 @@ In headed thinking, there are length-zero lists (heads with no elements), and an element can be listed or not listed. In ad-hoc thinking, there are no length-zero lists and every element belongs to a list of length at least one. +\PAB{Create a figure for this.} By omitting the head, elements can enter into an adjacency relationship, @@ -283,54 +338,60 @@ identifies a list using an explicit head. - -\begin{figure} - \label{fig:lst-features-intro} - \lstinputlisting[language=CFA, firstline=20, lastline=32]{lst-features-intro.run.cfa} - \caption[Multiple link directions in \CFA list library]{ - Demonstration of the running \lstinline{req} example, done using the \CFA list library\protect\footnotemark. - This example does the same job that Figure~\ref{fig:lst-issues-attach} shows three ways. - } -\end{figure} -\footnotetext{ +The \CFA list library's version of the running @req@ example is in Figure~\ref{fig:lst-features-intro}. +Its link attachment is intrusive and the resulting memory layout is pure-stack, just as for the LQ version of Figure~\ref{f:Intrusive}. +The framework-provided type @dlink(...)@ provides the links. +The user inserts the links into the @req@ structure by using \CFA inline-inheritance (TODO: reference introduction). +Inline 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{ The \CFA list examples elide the \lstinline{P9_EMBEDDED} annotations that (TODO: xref P9E future work) proposes to obviate. Thus, these examples illustrate a to-be state, free of what is to be historic clutter. The elided portions are immaterial to the discussion and the examples work with the annotations provided. - The \CFA test suite (TODO:cite?) includes equivalent demonstrations, with the annotations included. -}. - -My \CFA list library's version of the running @req@ example is in Figure~\ref{fig:lst-features-intro}. -Its link attachment is intrusive and the resulting memory layout is pure-stack, just as for the LQ version of Figure~\ref{fig:lst-issues-attach}-(a). -The framework-provided type @dlink(-)@ provides the links. -The user puts links into the @req@ structure by inline-inheriting (TODO: reference introduction) this type. -Which means: the type of the field is @dlink(req)@; the field is unnamed; a reference to a @req@ is implicitly convertible to @dlink@. -As these links have a nontrivial, user-specified location within the @req@ structure, this conversion also encapsulates the implied pointer arithmetic safely. - -\begin{figure} - \label{fig:lst-features-multidir} - \lstinputlisting[language=CFA, firstline=20, lastline=25]{lst-features-multidir.run.cfa} + The \CFA test suite (TODO:cite?) includes equivalent demonstrations, with the annotations included.} +These links have a nontrivial, user-specified location within the @req@ structure; +this convention encapsulates the implied pointer arithmetic safely. + +\begin{figure} + \lstinputlisting[language=CFA, firstline=20, lastline=32]{lst-features-intro.run.cfa} + \caption[Multiple link directions in \CFA list library]{ + Demonstration of the running \lstinline{req} example, done using the \CFA list library. + This example does the same job that Figure~\ref{fig:lst-issues-attach} shows three ways. + } + \label{fig:lst-features-intro} +\end{figure} + +\begin{figure} +\centering +\begin{tabular}{@{}ll@{}} +\begin{tabular}{@{}l@{}} + \lstinputlisting[language=CFA, firstline=20, lastline=25]{lst-features-multidir.run.cfa} \\ \lstinputlisting[language=CFA, firstline=40, lastline=67]{lst-features-multidir.run.cfa} - \caption{ + \end{tabular} + & + \lstinputlisting[language=C++, firstline=20, lastline=60]{lst-issues-multi-static.run.c} + \end{tabular} + +\caption{ Demonstration of multiple static link directions done in the \CFA list library. This example does the same job as Figure~\ref{fig:lst-issues-multi-static}. } -\end{figure} - -The \CFA library supports multi-static link directionality. Figure~\ref{fig:lst-features-multidir} illustrates how. + \label{fig:lst-features-multidir} +\end{figure} + +Figure~\ref{fig:lst-features-multidir} shows how the \CFA library supports multi-static link directionality. The declaration of @req@ now has two inline-inheriting @dlink@ occurrences. -The first of these lines gives a type named @req.by_pri@; @req@ inherits from it; it inherits from @dlink@. -The second line gives a similar @req.by_rqr@. +The first of these lines gives a type named @req.by_pri@, @req@ inherits from it, and it inherits from @dlink@. +The second line @req.by_rqr@ is similar to @req.by_pri@. Thus, there is a diamond, non-virtual, inheritance from @req@ to @dlink@, with @by_pri@ and @by_rqr@ being the mid-level types. Disambiguation occurs in the declarations of the list-head objects. The type of the variable @reqs_pri_global@ is @dlist(req, req.by_pri)@, meaning operations called on @reqs_pri_global@ are implicitly disambiguated. -In the example, the calls @insert_first(reqs_pri_global, ...)@ imply, ``here, we're working by priority.'' +In the example, the calls @insert_first(reqs_pri_global, ...)@ imply, ``here, we are working by priority.'' The \CFA library also supports the common case, of single directionality, more naturally than LQ. Figure~\ref{fig:lst-features-intro} shows a single-direction list done with no contrived name for the link direction, -where Figure~\ref{fig:lst-issues-attach}-(a) adds the unnecessary name, @x@. +where Figure~\ref{f:Intrusive} adds the unnecessary name, @x@. In \CFA, a user doing a single direction (Figure~\ref{fig:lst-features-intro}) -sets up a simple inheritance with @dlink@, and declares a list head to have the simpler type @dlist(-)@. +sets up a simple inheritance with @dlink@, and declares a list head to have the simpler type @dlist(...)@. While a user doing multiple link directions (Figure~\ref{fig:lst-features-multidir}) -sets up a diamond inheritance with @dlink@, and declares a list head to have the more-informed type @dlist(-, DIR)@. +sets up a diamond inheritance with @dlink@, and declares a list head to have the more-informed type @dlist(..., DIR)@. The \CFA library offers a type-system mediated integration with user code. @@ -348,7 +409,4 @@ - - - \subsection{Iteration} Index: doc/theses/mike_brooks_MMath/uw-ethesis.tex =================================================================== --- doc/theses/mike_brooks_MMath/uw-ethesis.tex (revision cd477ca4b4fa70760b071f79006f06fedadef62c) +++ doc/theses/mike_brooks_MMath/uw-ethesis.tex (revision d800676cf9dcb4402f8b91c21cf9befd9330b2f0) @@ -60,4 +60,5 @@ % For hyperlinked PDF, suitable for viewing on a computer, use this: \documentclass[letterpaper,12pt,titlepage,oneside,final]{book} +\usepackage{times} \usepackage[T1]{fontenc} % Latin-1 => 256-bit characters, => | not dash, <> not Spanish question marks @@ -87,10 +88,9 @@ \usepackage{comment} % Removes large sections of the document. \usepackage{tabularx} -\usepackage{subfigure} +\usepackage[labelformat=simple,aboveskip=0pt,farskip=0pt,font=normalsize]{subfig} +\renewcommand\thesubfigure{(\alph{subfigure})} \usepackage{algorithm} \usepackage{algpseudocode} - -\usepackage{pbox} % Hyperlinks make it very easy to navigate an electronic document. @@ -117,5 +117,6 @@ citecolor=blue, % color of links to bibliography filecolor=magenta, % color of file links - urlcolor=blue % color of external links + urlcolor=blue, % color of external links + breaklinks=true } \ifthenelse{\boolean{PrintVersion}}{ % for improved print quality, change some hyperref options @@ -180,10 +181,9 @@ \CFAStyle % CFA code-style \lstset{language=CFA} % default language -\lstset{basicstyle=\linespread{0.9}\tt} % CFA typewriter font +\lstset{basicstyle=\linespread{0.9}\sf} % CFA typewriter font \lstset{inputpath={programs}} \newcommand{\PAB}[1]{{\color{red}PAB: #1}} - -\newcommand{\uCpp}{$\mu${C}{\kern-.1em\hbox{\large\texttt{+\kern-.25em+}}}} +\newcommand{\uCpp}{$\mu$\CC} %======================================================================