Index: doc/theses/mike_brooks_MMath/array.tex =================================================================== --- doc/theses/mike_brooks_MMath/array.tex (revision 1037b4c2ce92b15ef88c9e6902e33a1a2a199c88) +++ doc/theses/mike_brooks_MMath/array.tex (revision 9c12dd0d4c6ee7140864345a0fd28f78e9b0400d) @@ -30,4 +30,5 @@ A function can be polymorphic over @array@ arguments using the \CFA @forall@ declaration prefix. +\begin{minipage}{\linewidth} % forbid page splitting, force \begin{cfa} forall( T, @[N]@ ) @@ -40,4 +41,5 @@ Cforall Runtime error: subscript 1000 exceeds dimension range [0,99) $for$ array 0x555555558020. \end{cfa} +\end{minipage} Function @g@ takes an arbitrary type parameter @T@ and an unsigned integer \emph{dimension} @N@. The dimension represents a to-be-determined number of elements, managed by the type system, where 0 represents an empty array. @@ -125,5 +127,5 @@ \lstinput{30-43}{hello-array.cfa} \lstinput{45-48}{hello-array.cfa} -\caption{Example of calling a dimension-generic function.} +\caption{Example of calling a dimension-generic function} \label{f:fExample} \end{figure} @@ -243,35 +245,50 @@ This static check's rules are presented in \VRef[Section]{s:ArrayTypingC}. -Orthogonally, the \CFA array type works within generic \emph{types}, \ie @forall@-on-@struct@. -The same argument safety and the associated implicit communication of array length occurs. +Orthogonally, the \CFA array type also works inside generic \emph{types}. +That is, an @array@ as a generic @struct@'s member and an @[N]@ can parameterize a @struct@. +The same argument safety, and the associated implicit length communication, occur. Preexisting \CFA allowed aggregate types to be generalized with type parameters, enabling parameterizing of element types. -This feature is extended to allow parameterizing by dimension. -Doing so gives a refinement of C's ``flexible array member''~\cite[\S~6.7.2.1.18]{C11}: +As polymorphism on functions was extended to allow parameterizing over dimensions, so is polymorphism on types. +The result has profound consequences for safe memory management. + +C's Flexible Array Member (FAM) pattern~\cite[\S~6.7.2.1.18]{C11} gives an unsafe way to put an array of dynamic length inside a structure. \begin{cfa} struct S { ... - double d []; // incomplete array type => flexible array member -} * s = malloc( sizeof( struct S ) + sizeof( double [10] ) ); -\end{cfa} -which creates a VLA of size 10 @double@s at the end of the structure. -A C flexible array member can only occur at the end of a structure; -\CFA allows length-parameterized array members to be nested at arbitrary locations, with intervening member declarations. -\lstinput{10-15}{hello-accordion.cfa} -The structure has course- and student-level metadata (their respective field names) and a position-based preferences' matrix. -The structure's layout is dynamic; the starting offset of @student_ids@ varies according to the generic parameter @C@; the offset of @preferences@ varies by both. - -\VRef[Figure]{f:checkExample} shows a program main using @School@ and results with different array sizes. + double d[]; // incomplete array type => flexible array member +}; +struct S * s = malloc( sizeof( struct S ) + sizeof( double [10] ) ); +\end{cfa} +This type-@S@ declaration defines a quasi-VLA named @d@ as the last structure member. +The variable-@s@ initialization sizes this particular array at 10 elements. +The choice of @malloc@ here is the common-case FAM idiom, but @alloca@ can be substituted, resulting in stack allocation. +A \CFA @[N]@-parameterized structure improves on this pattern. + +\begin{figure} + \lstinput{10-15}{hello-accordion.cfa} + \caption{\CFA Dynamic Array Member (DAM) declaration} + \label{DAM-declaration} +\end{figure} + +\CFA allows length-parameterized array members to be nested at arbitrary locations, with further member declarations interleaved. +The result is a \newterm{Dynamic Array Member (DAM)} +% \footnote{ +% To keep the names straight, it may help to think of C's flexible array member as ``too flexible,'' where the discussion that follows makes the case that a FAM is weakly typed. +% }, +as illustrated in \VRef[Figure]{DAM-declaration}. The example's @School@ structure has course- and student-level metadata (in the respectively named fields) and a position-based preferences' matrix. +The structure's layout is dynamic; the starting offset of @student_ids@ varies according to the generic parameter @C@, which affects the size of the @course_codes@ field. +Similarly, the offset of @preferences@ varies by both parameters. + +\VRef[Figure]{f:DAM-example} shows a program main using the @School@ type, along with results at different array sizes. The @school@ variable holds many students' course-preference forms. It is on the stack and its initialization does not use any casting or size arithmetic. -Both of these points are impossible with a C flexible array member. -When heap allocation is preferred, the original pattern still applies. +When heap allocation is preferred, the original pattern still applies, with the same qualities. \begin{cfa} School( classes, students ) * sp = alloc(); \end{cfa} -This ability to avoid casting and size arithmetic improves safety and usability over C flexible array members. The example program prints the courses in each student's preferred order, all using the looked-up display names. -When a function operates on a @School@ structure, the type system handles its memory layout transparently. -In the example, function @getPref@ returns, for the student at position @is@, what is the position of their @pref@\textsuperscript{th}-favoured class. -Finally, inputs and outputs are given on the right for different sized schools. +In the example, function @getPref@ returns, for the student at position @is@, the position of their @pref@\textsuperscript{th}-favoured class. +This function helps the program to output each student's ordered preferences. +The program's inputs and outputs are given on the right, for two different school sizes. \begin{figure} @@ -304,7 +321,20 @@ \end{tabular} -\caption{\lstinline{School} Example, Input and Output} -\label{f:checkExample} + +\caption[\CFA Dynamic Array Member (DAM) usage]{ + \CFA Dynamic Array Member (DAM) usage. + Example program (left) with input and output (right).} +\label{f:DAM-example} \end{figure} + +Much of these \CFA DAM features are impossible with a C FAM. +In C, they can only occur at the end of a structure; +\CFA allows them anywhere. +As a consequence, \CFA allows several of them, while C is limited to one. +The \CFA ability to avoid casting and size arithmetic improves safety and usability over C. +While C offers the \emph{VLA} language feature, to eliminate casting and size arithmetic for stack-allocated \emph{simple arrays}, this feature does not extend to stack-allocating a FAM-structure, which makes the user fall back on explicit @alloca@. +The \CFA DAM, by contrast, treats every stack allocation as a simple variable declaration. +When a function operates on a \CFA DAM structure, the type system handles its memory layout transparently. + @@ -343,5 +373,5 @@ The ``resolver'' compiler pass, which provides argument values for a declaration's type-system parameters, gathered from type information in scope at the usage site. \item - The ``box'' compiler pass, which encodes information about type parameters into ``extra'' regular parameters on declarations and and arguments on calls. + The ``box'' compiler pass, which encodes information about type parameters into ``extra'' regular parameters on declarations, and corresponding arguments on calls. Notably, it conveys the size of a type @foo@ as a @__sizeof_foo@ parameter, and rewrites the @sizeof(foo)@ expression as @__sizeof_foo@, \ie a use of the parameter. \end{itemize} @@ -690,5 +720,5 @@ \end{itemize} - \caption{Case comparison for array type compatibility, given pairs of dimension expressions.} + \caption[Case comparison for array type compatibility]{Case comparison for array type compatibility, given pairs of dimension expressions.} \label{f:DimexprRuleCompare} \end{figure} @@ -946,8 +976,11 @@ \begin{figure} \includegraphics{measuring-like-layout} -\caption{Visualization of subscripting by value and by \lstinline[language=CFA]{all}, for \lstinline{x} of type \lstinline{array( float, 5, 7 )} understood as 5 rows by 7 columns. -The horizontal layout represents contiguous memory addresses while the vertical layout is conceptual. -The vertical shaded band highlights the location of the targeted element, 2.3. -Any such vertical slice contains various interpretations of a single address.} +\caption[Visualization of subscripting by value and by `all']{ + Visualization of subscripting by value and by `\lstinline[language=CFA]{all}.' + Uses example variable \lstinline{x} of type \lstinline{array( float, 5, 7 )}, understood as 5 rows by 7 columns. + The horizontal layout represents contiguous memory addresses while the vertical layout is conceptual. + The vertical shaded band highlights the location of the targeted element, 2.3. + Any such vertical slice contains various interpretations of a single address. +} \label{fig:subscr-all} \end{figure} @@ -1007,6 +1040,5 @@ % \noindent END: Paste looking for a home -The new-array library defines types and operations that ensure proper elements are accessed soundly in spite of the overlapping. -The @arpk@ structure and its @-[i]@ operator are defined as: +\begin{figure} \begin{cfa} forall( @@ -1026,4 +1058,10 @@ } \end{cfa} +\caption{Definition of structure `\lstinline{arpk},' which underlies the \CFA array} +\label{f:arpk} +\end{figure} + +The new-array library defines types and operations that ensure proper elements are accessed soundly in spite of the overlapping. +The @arpk@ structure and its @-[i]@ operator are defined in \VRef[Figure]{f:arpk}. The private @arpk@ structure (array with explicit packing) is generic over four types: dimension length, masquerading-as, ... This structure's public interface is hidden behind the @array(...)@ macro and the subscript operator. @@ -1101,7 +1139,9 @@ \multicolumn{1}{c}{(i)} \end{tabular} -\caption{Overhead comparison, control case. -All three programs/compilers generate equally performant code when the programmer ``self-checks'' bounds via a loop's condition. -Yet both \CFA and \CC versions generate code that is slower and safer than C's when the programmer might overrun the bounds.} +\caption[Bound-check overhead comparison, control case]{ + Bound-check overhead comparison, control case. + All three programs/compilers generate equally performant code when the programmer ``self-checks'' bounds via a loop's condition. + Yet both \CFA and \CC versions generate code that is slower and safer than C's when the programmer might overrun the bounds. +} \label{f:ovhd-ctl} \end{figure} @@ -1344,5 +1384,6 @@ \end{cfa} \end{tabular} -\caption{Exponential thunk generation under the otype-recursion pattern. +\caption[Exponential thunk generation under the otype-recursion pattern]{ + Exponential thunk generation under the otype-recursion pattern. Each time one type's function (\eg ctor) uses another type's function, the \CFA compiler generates a thunk, to capture the used function's dependencies, presented according to the using function's need. So, each non-leaf line represents a generated thunk and every line represents a search request for the resolver to find a satisfying function.} @@ -1640,5 +1681,5 @@ \hspace{6pt} -\caption{Triangular Matrix} +\caption{Triangular matrix in Java and C} \label{f:JavaVsCTriangularMatrix} \end{figure} @@ -1684,5 +1725,5 @@ Thus, these options do not offer an allocation with a dynamically given fixed size. -And furthermore, they do not provide any improvement to the C flexible array member pattern, for making a dynamic amount of storage contiguous with its header, as do \CFA's accordions. +And furthermore, they do not provide any improvement to the C flexible array member pattern, for making a dynamic amount of storage contiguous with its header, as do \CFA's new dynamic array members. Index: doc/theses/mike_brooks_MMath/background.tex =================================================================== --- doc/theses/mike_brooks_MMath/background.tex (revision 1037b4c2ce92b15ef88c9e6902e33a1a2a199c88) +++ doc/theses/mike_brooks_MMath/background.tex (revision 9c12dd0d4c6ee7140864345a0fd28f78e9b0400d) @@ -491,5 +491,5 @@ \end{cfa} \end{tabular} -\caption{Pre-VLA Fixed \vs Variable Contiguous Matrix Styles} +\caption{Pre-VLA contiguous matrix styles, fixed \vs variable} \label{f:FixedVariable} \end{figure} @@ -580,5 +580,5 @@ \end{cfa} \end{tabular} -\caption{C99 Contiguous \vs Non-contiguous Matrix Styles} +\caption{C99 matrix styles, contiguous \vs non-contiguous } \label{f:ContiguousNon-contiguous} \end{figure} @@ -672,5 +672,6 @@ \end{cfa} \end{tabular} -\caption{Multiple ways to declare an array parameter. +\caption[Multiple ways to declare an array parameter]{ +Multiple ways to declare an array parameter. Across a valid row, every declaration is equivalent. Each column gives a declaration style, where the style for that column is read from the first row. @@ -955,6 +956,6 @@ \subfloat[Wrapped value]{\label{f:WrappedValue}\usebox\myboxC} -\caption{ - Three styles of link attachment: +\caption[Three styles of link attachment]{ + 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}; @@ -1012,5 +1013,5 @@ \lstinput[language=C++]{100-117}{lst-issues-attach-reduction.hpp} \lstinput[language=C++]{150-150}{lst-issues-attach-reduction.hpp} - \caption{ + \caption[Simulation of wrapped using intrusive]{ Simulation of wrapped using intrusive. Illustrated by pseudocode implementation of an STL-compatible API fragment using LQ as the underlying implementation. @@ -1048,5 +1049,5 @@ \hspace*{1.5in}\includegraphics[page=2]{lst-issues-direct.pdf} } - \caption{ + \caption[Example of simultaneity using LQ lists]{ Example of simultaneity using LQ lists. The zoomed-out diagram (right/top) shows the complete multi-linked data structure. @@ -1214,5 +1215,5 @@ \centering \includegraphics[width=\textwidth]{lst-issues-ident.pdf} - \caption{ + \caption[Comparison of headed and ad-hoc list identities]{ Comparison of headed and ad-hoc list identities, for various list lengths. Pointers are logical, meaning that no claim is intended about which part of an object is being targeted. @@ -1256,6 +1257,6 @@ \centering \includegraphics[width=0.55\textwidth]{lst-issues-end.pdf} - \caption{ - LQ sub-object-level representation of links and ends. + \caption[LQ field-level representation of links and ends]{ + LQ field-level representation of links and ends. Each object's memory is pictured as a vertical strip. The location, within a strip, at which an arrow points, is significant. Index: doc/theses/mike_brooks_MMath/list.tex =================================================================== --- doc/theses/mike_brooks_MMath/list.tex (revision 1037b4c2ce92b15ef88c9e6902e33a1a2a199c88) +++ doc/theses/mike_brooks_MMath/list.tex (revision 9c12dd0d4c6ee7140864345a0fd28f78e9b0400d) @@ -43,5 +43,5 @@ g( s, &s ); $\C{// value, pointer}$ \end{cfa} -\caption{Plan-9 Polymorphism} +\caption{Plan-9 polymorphism} \label{f:Plan9Polymorphism} \end{figure} @@ -79,5 +79,5 @@ \end{cfa} \end{tabular} -\caption{Diamond Non-Virtual Inheritance Pattern} +\caption{Diamond non-virtual inheritance pattern} \label{f:DiamondInheritancePattern} \end{figure} @@ -127,5 +127,5 @@ } \end{cfa} -\caption{\lstinline{dlisk} / \lstinline{dlist} Outline} +\caption[Sketch of the dlink and dlist type definitions]{Sketch of the \lstinline{dlink} and \lstinline{dlist} type definitions } \label{f:dlistOutline} \end{figure} @@ -154,6 +154,6 @@ \end{tabular} -\caption{ - Demonstration of multiple static link axes done in the \CFA list library. +\caption[Demonstration of multiple static link axes in \CFA]{ + Demonstration of multiple static link axes in \CFA. The right example is from \VRef[Figure]{fig:lst-issues-multi-static}. The left \CFA example does the same job. @@ -278,8 +278,8 @@ E & remove_first( dlist( E ) & list ); E & remove_last( dlist( E ) & list ); -void transfer( dlist( E ) & to, dlist( E ) & from ) { -void split( dlist( E ) & to, dlist( E ) & from, E & node ) { -\end{cfa} -\caption{\CFA List API} +void transfer( dlist( E ) & to, dlist( E ) & from ); +void split( dlist( E ) & to, dlist( E ) & from, E & node ); +\end{cfa} +\caption{\CFA list API} \label{f:ListAPI} \end{figure} @@ -309,5 +309,5 @@ } \end{cfa} -\caption{Iterator Driver} +\caption{Iterator driver} \label{f:IteratorDriver} \end{figure} @@ -586,5 +586,5 @@ \end{cfa} \end{tabular} -\caption{\CC \vs \CFA List Issues} +\caption{Obtaining a linked-list iterator in \CC \vs \CFA} \label{f:CCvsCFAListIssues} \end{figure} @@ -627,5 +627,5 @@ \includegraphics[width=\textwidth]{lst-impl-links.pdf} \caption{ - \CFA list library representations for headed and headless lists. + \CFA list library representations for headed and headless lists } \label{fig:lst-impl-links} @@ -717,5 +717,5 @@ \end{tabular} \caption{ - Glossary of terms used in the list performance evaluation. + Glossary of terms used in the list performance evaluation } \label{f:ListPerfGlossary} @@ -969,5 +969,5 @@ all hd & ins-e & rem-e & all hd & ins-e & rem-e \end{tabular} -\caption{Experiment use cases, numbered.} +\caption{Experiment use cases, numbered} \label{f:ExperimentOperations} \end{figure} @@ -1041,5 +1041,5 @@ } \end{tabular} - \caption{Variety of IR duration \vs list length, at small--medium lengths. Two example use cases are shown: I, stack movement with head-only access (plot a); VIII, queue movement with element-oriented removal access (plot b); both use cases have insert-first polarity. One example is run on each machine: UC-I on AMD (ploat a); UC-VIII on Intel (plot b). Lower is better.} + \caption[Variety of IR duration responses to list length, at small--medium lengths]{Variety of IR duration responses to list length, at small--medium lengths. Two example use cases are shown: I, stack movement with head-only access (plot a); VIII, queue movement with element-oriented removal access (plot b); both use cases have insert-first polarity. One example is run on each machine: UC-I on AMD (ploat a); UC-VIII on Intel (plot b). Lower is better.} \label{fig:plot-list-zoomin-abs} \end{figure} @@ -1147,5 +1147,10 @@ } \end{tabular} - \caption{IR duration, transformed for general anaysis. The analysis follows the single example setup of \VRef[Figure]{f:zoomin-abs-i-swift}, \ie Use Case I on AMD, where IR is given as absolute duration. Plot (a) transforms the source dataset by conditioning on specific size. Plot (b) takes the results from only the identified size zones, discards their specific-size information, and shows the resulting distribution. Lower is better.} + \caption[IR duration, transformed for general anaysis]{ + IR duration, transformed for general anaysis. + The analysis follows the single example setup of \VRef[Figure]{f:zoomin-abs-i-swift}, \ie Use Case I on AMD, where IR is given as absolute duration. + Plot (a) transforms the source dataset by conditioning on specific size. + Plot (b) takes the results from only the identified size zones, discards their specific-size information, and shows the resulting distribution. + Lower is better.} \label{fig:plot-list-rel} \end{figure} @@ -1258,5 +1263,5 @@ } % subfigure \end{tabular} - \caption{Insert/remove duration \vs list length. + \caption[IR duration \vs list length, all sizes]{IR duration \vs list length, all sizes. Lengths go as large possible without error. One example use case is shown: stack movement, insert-first polarity and head-mediated access. Lower is better.} @@ -1348,6 +1353,8 @@ \includegraphics{plot-list-1ord.pdf} \small{\textsuperscript{\textdagger} LQ-@list@ is (/48) by its incomplete (25\%) use case coverage. Its bars are scaled to match.} - \caption{Histogram of IR durations, decomposed by all first-order effects. - Each of the three breakdowns divides the entire population of test results into its mutually disjoint constituents. Lower is better. + \caption[IR duration, decomposed by all first-order effects]{ + IR duration, decomposed by all first-order effects. + Each of the three breakdowns divides the entire population of test results into its mutually disjoint constituents. + Lower is better. } \label{fig:plot-list-1ord} @@ -1396,6 +1403,7 @@ \textsuperscript{*} The full population of 192 individual configurations applies (48 for LQ-@list@), but this analysis summarizes pairs of them, giving each histogram's 96 contributions (24 for LQ-@list@). } - \caption{Histogram of IR durations, illustrating interactions with framework. - Higher favours top option; lower favours bottom option. + \caption[IR duration where framework selection interacts with other factors]{ + IR duration where framework selection interacts with other factors. + Higher favours top option; lower favours bottom option. } \label{fig:plot-list-2ord} Index: doc/theses/mike_brooks_MMath/string.tex =================================================================== --- doc/theses/mike_brooks_MMath/string.tex (revision 1037b4c2ce92b15ef88c9e6902e33a1a2a199c88) +++ doc/theses/mike_brooks_MMath/string.tex (revision 9c12dd0d4c6ee7140864345a0fd28f78e9b0400d) @@ -14,5 +14,6 @@ The over-arching commonality is that operations work on groups of characters for assigning, copying, scanning, and updating. -\begin{figure}[h] +%\begin{figure}[h] +\begin{figure} \begin{cquote} \begin{tabular}{@{}l|l|l|l@{}} @@ -34,5 +35,5 @@ \end{tabular} \end{cquote} -\caption{Language comparison of string API} +\caption{Inter-language comparison of string APIs} \label{f:StrApiCompare} \end{figure} @@ -620,5 +621,5 @@ \end{tabular} \end{cquote} -\caption{Extracting Words from Line of Text} +\caption{Simplification by \CFA API for extracting words from a line of text} \label{f:ExtractingWordsText} \end{figure} @@ -812,8 +813,10 @@ As well, the operations are asymmetric, \eg @String@ has @replace@ by text but not replace by position and vice versa for @StringBuffer@. -More significant operational differences relate to storage management, often appearing through assignment (@target = source@), and are summarized in \VRef[Figure]{f:StrSemanticCompare}, which defines properties type abstraction, state, symmetry, and referent. -The following discussion justifies the figure's yes/no entries per language. - -\begin{figure} +More significant operational differences relate to storage management, often appearing through assignment (@target = source@), and are summarized in \VRef[Table]{f:StrSemanticCompare}, which defines properties type abstraction, state, symmetry, and referent. +The following discussion justifies the table's yes/no entries per language. + +\begin{table} +\caption{Comparison of languages' strings, storage management perspective} +\label{f:StrSemanticCompare} \setlength{\extrarowheight}{2pt} \setlength{\tabcolsep}{5pt} @@ -860,7 +863,5 @@ The Java @String@ class is analyzed; its @StringBuffer@ class behaves similarly to \CC. \end{itemize} -\caption{Comparison of languages' strings, storage management perspective.} -\label{f:StrSemanticCompare} -\end{figure} +\end{table} In C, these declarations are very different. @@ -943,5 +944,5 @@ $\texttt{\small abcde abcde abcde abcde bc c}$ \end{cfa} -% all helpful criteria of \VRef[Figure]{f:StrSemanticCompare} are satisfied. +% all helpful criteria of \VRef[Table]{f:StrSemanticCompare} are satisfied. The \CFA string manages storage, handles all assignments, including those of fragment referents with fast initialization, provides the choice between snapshot and alias semantics, and does so symmetrically with one type (which assures text validity according to the lifecycles of the string variables). The @s1@ case is the same in \CFA as in \CC. @@ -956,5 +957,5 @@ \subsection{Logical Overlap} -It may be unfamiliar to combine \VRef[Figure]{f:StrSemanticCompare}'s alias state and fragment referent in one API, or at the same time. +It may be unfamiliar to combine \VRef[Table]{f:StrSemanticCompare}'s alias state and fragment referent in one API, or at the same time. This section shows the capability in action. @@ -1076,5 +1077,5 @@ } \end{cfa} -\caption{Parameter Passing} +\caption{Passing substrings as parameters, program} \label{f:ParameterPassing} \end{figure} @@ -1333,5 +1334,5 @@ \end{multicols} -\caption{Execution of Function \lstinline{test}} +\caption{Passing substrings as parameters, execution} \label{f:ParametersPassingResults} \end{figure} @@ -1564,5 +1565,5 @@ \end{tabular} -\caption{Code Lowering for RAII} +\caption{Code lowering by RAII implementation} \label{f:CodeLoweringRAII} \end{figure} @@ -1618,9 +1619,11 @@ To use LL, a programmer rewrites invocations using pass-by-value APIs into invocations where resourcing is more explicit. Many invocations are unaffected, notably assignment and comparison. -\VRef[Figure]{f:HL_LL_Lowering} shows, of the capabilities listed in \VRef[Figure]{f:StrApiCompare}, only three cases need revisions. +\VRef[Table]{f:HL_LL_Lowering} shows, of the capabilities listed in \VRef[Figure]{f:StrApiCompare}, only three cases need revisions. The actual HL workaround wraps @string@ as a pointer to a uniquely owned, heap-allocated @string_res@. This arrangement has @string@ using style-\ref{p:feature1} RAII, which is compatible with pass-by-value. -\begin{figure} +\begin{table} +\caption{HL to LL \CFA string-API lowering} +\label{f:HL_LL_Lowering} \centering \begin{tabular}{@{}ll@{}} @@ -1666,7 +1669,5 @@ \end{tabular} -\caption{HL to LL Lowering} -\label{f:HL_LL_Lowering} -\end{figure} +\end{table} @@ -1738,5 +1739,5 @@ \raisebox{-0.17\totalheight}{\includegraphics{string-sharectx.pdf}} % lower \end{tabular} - \caption{Controlling copying vs sharing of strings using \lstinline{string_sharectx}.} + \caption[Controlling copying \vs sharing of strings]{Controlling copying \vs sharing of strings using \lstinline{string_sharectx}.} \label{fig:string-sharectx} \end{figure} @@ -1885,7 +1886,8 @@ \includegraphics{plot-string-peq-cppemu.pdf} % \includegraphics[width=\textwidth]{string-graph-peq-cppemu.png} - \caption{Fresh vs Reuse in \CC, Emulation Baseline. - Average time per iteration with one \lstinline{x += y} invocation (lower is better). - Comparing \CFA's STL emulation mode with STL implementations, and comparing the fresh with reused reset styles.} + \caption[Fresh \vs reuse in \CC, emulation baseline]{ + Fresh \vs reuse in \CC, emulation baseline. + Average time per iteration with one \lstinline{x += y} invocation (lower is better). + Comparing \CFA's STL emulation mode with STL implementations, and comparing the fresh with reused reset styles.} \label{fig:string-graph-peq-cppemu} \bigskip @@ -1893,8 +1895,10 @@ \includegraphics{plot-string-peq-sharing.pdf} % \includegraphics[width=\textwidth]{string-graph-peq-sharing.png} - \caption{\CFA Compromise for Fresh \vs Reuse. - Average time per iteration with one \lstinline{x += y} invocation (lower is better). - Comparing \CFA's sharing mode with STL, and comparing the fresh with reused reset styles. - The \CC results are repeated from \VRef[Figure]{fig:string-graph-peq-cppemu}.} + \caption[\CFA compromise for fresh \vs reuse]{ + \CFA compromise for fresh \vs reuse. + Average time per iteration with one \lstinline{x += y} invocation (lower is better). + Comparing \CFA's sharing mode with STL, and comparing the fresh with reused reset styles. + The \CC results are repeated from \VRef[Figure]{fig:string-graph-peq-cppemu}. + } \label{fig:string-graph-peq-sharing} \end{figure} @@ -2015,5 +2019,9 @@ \includegraphics{plot-string-pta-sharing.pdf} % \includegraphics[width=\textwidth]{string-graph-pta-sharing.png} - \caption{CFA's low overhead for misusing concatenation. Average time per iteration with one \lstinline{x += y} invocation (lower is better). Comparing \CFA (having implicit sharing activated) with STL, and comparing the \lstinline{+}-then-\lstinline{=} with the \lstinline{+=} append styles. The \lstinline{+=} results are repeated from \VRef[Figure]{fig:string-graph-peq-sharing}.} + \caption[\CFA's low overhead for misusing concatenation]{ + \CFA's low overhead for misusing concatenation. + Average time per iteration with one \lstinline{x += y} invocation (lower is better). + Comparing \CFA (having implicit sharing activated) with STL, and comparing the \lstinline{+}-then-\lstinline{=} with the \lstinline{+=} append styles. + The \lstinline{+=} results are repeated from \VRef[Figure]{fig:string-graph-peq-sharing}.} \label{fig:string-graph-pta-sharing} \end{figure} @@ -2074,7 +2082,9 @@ % \includegraphics[width=\textwidth]{string-graph-pbv.png} \begin{tabularx}{\linewidth}{>{\centering\arraybackslash}X >{\centering\arraybackslash}X} (a) & (b) \end{tabularx} - \caption{Average time per iteration (lower is better) with one call to a function that takes a by-value string argument, comparing \CFA (having implicit sharing activated) with STL. -(a) With \emph{Varying 1 and up} corpus construction, in which the STL-only benefit of SSO optimization occurs, in varying degrees, at all string sizes. -(b) With \emph{Fixed-size} corpus construction, in which this benefit applies exactly to strings with length below 16.} + \caption[Impact of \CC small-string optimization on experimental timings]{ + Impact of \CC small-string optimization on experimental timings. + Average time per iteration (lower is better) with one call to a function that takes a by-value string argument, comparing \CFA (having implicit sharing activated) with STL. + (a) With \emph{Varying 1 and up} corpus construction, in which the STL-only benefit of SSO optimization occurs, in varying degrees, at all string sizes. + (b) With \emph{Fixed-size} corpus construction, in which this benefit applies exactly to strings with length below 16.} \label{fig:string-graph-pbv} \end{figure} @@ -2122,5 +2132,7 @@ \centering \includegraphics{string-perf-alloc.pdf} - \caption{Memory-allocation test's harness and its resulting pattern of memory usage under a bump-pointer-only scheme.} + \caption[Memory-allocation test harness and its usage pattern]{ + Memory-allocation test harness and its usage pattern. + The pattern is shown early in a test run, when only bump-pointer allocation has occurred so far.} \label{fig:string-perf-alloc} \end{figure} @@ -2154,5 +2166,7 @@ \includegraphics{plot-string-allocn.pdf} \begin{tabularx}{\linewidth}{>{\centering\arraybackslash}X >{\centering\arraybackslash}X} (a) Vertical, Lower is better. \\ Horizontal, leftward is better. & (b) \hspace*{5pt} STL CFA \hspace*{20pt} STL \hspace*{10pt} CFA \hspace*{10pt} \end{tabularx} - \caption{Space and time performance, under varying fraction-live targets, for the five string lengths shown, at \emph{Varying 16 and up} corpus construction.} + \caption[String allocation space and time performance]{ + String allocation space and time performance. + The experiment varies the fraction-live target, at the five string lengths shown, under \emph{Varying 16 and up} corpus construction.} \label{fig:string-graph-allocn} \end{figure} Index: doc/theses/mike_brooks_MMath/uw-ethesis.tex =================================================================== --- doc/theses/mike_brooks_MMath/uw-ethesis.tex (revision 1037b4c2ce92b15ef88c9e6902e33a1a2a199c88) +++ doc/theses/mike_brooks_MMath/uw-ethesis.tex (revision 9c12dd0d4c6ee7140864345a0fd28f78e9b0400d) @@ -93,4 +93,6 @@ \usepackage{multirow} \usepackage[labelformat=simple,aboveskip=0pt,farskip=0pt,font=normalsize]{subfig} +\usepackage{caption} +\usepackage{etoolbox} \renewcommand\thesubfigure{(\alph{subfigure})} @@ -122,4 +124,47 @@ \newcommand{\PAB}[1]{{\color{magenta}PAB: #1}} \newcommand{\MLB}[1]{{\color{red}MLB: #1}} + +% Mike's figure-framing look + +\let\oldfigure\figure +\let\endoldfigure\endfigure + +\renewenvironment{figure} +{% + \oldfigure + \centering + \rule{\linewidth}{0.4pt}\par\vskip4pt +} +{% + \endoldfigure +} + +\DeclareCaptionFormat{ruled}{ + \rule{\linewidth}{0.4pt}\par + #1#2#3\par + \kern-\dp\strutbox + \rule{\linewidth}{0.4pt}% +} +\captionsetup[figure]{ + font=footnotesize, + labelfont=bf, + format=ruled +} +\captionsetup[subfigure]{ + format=plain, + font=normalsize, + labelfont=normalfont +} + +% Mike forbids breaking "equation" style code blocks across pages + +\AtBeginEnvironment{cfa}{% +\interlinepenalty=10000% +\clubpenalty=10000% +\widowpenalty=10000% +\displaywidowpenalty=10000% +} + + % Hyperlinks make it very easy to navigate an electronic document.