Index: doc/theses/mike_brooks_MMath/memmgr-basic.fig =================================================================== --- doc/theses/mike_brooks_MMath/memmgr-basic.fig (revision 8f250e00516ac41efae8e46c24bb5f3772c06d0f) +++ doc/theses/mike_brooks_MMath/memmgr-basic.fig (revision 8f250e00516ac41efae8e46c24bb5f3772c06d0f) @@ -0,0 +1,84 @@ +#FIG 3.2 Produced by xfig version 3.2.7b +Landscape +Center +Inches +Letter +100.00 +Single +-2 +1200 2 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 4 + 1 1 1.00 45.00 90.00 + 2700 1500 7125 1500 7125 2175 6750 2175 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 4 + 1 1 1.00 45.00 90.00 + 6750 2325 7275 2325 7275 1350 2700 1350 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 2400 2100 3150 +2 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3000 2400 3600 3150 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 6000 2400 6600 3150 +2 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 6300 2400 7350 3150 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 1500 1575 1500 2925 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 4 + 1 1 1.00 45.00 90.00 + 1350 1575 1350 3750 7500 3750 7800 3450 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 3 + 1 1 1.00 45.00 90.00 + 2550 2175 2400 2175 2400 1575 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 3 + 1 1 1.00 45.00 90.00 + 2250 1575 2250 2325 2550 2325 +2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 + 2550 2100 3450 2100 3450 2400 2550 2400 2550 2100 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3450 2325 4200 2325 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 4200 2175 3450 2175 +2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 + 4200 2100 5100 2100 5100 2400 4200 2400 4200 2100 +2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 + 5850 2100 6750 2100 6750 2400 5850 2400 5850 2100 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5850 2175 5100 2175 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 2325 5850 2325 +2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 + 2100 3150 3600 3150 3600 3300 2100 3300 2100 3150 +2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 + 6600 3150 7350 3150 7350 3300 6600 3300 6600 3150 +2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 + 1200 1275 2700 1275 2700 1575 1200 1575 1200 1275 +2 2 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 + 1500 3000 8100 3000 8100 3600 1500 3600 1500 3000 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 4350 2400 4350 3150 +2 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 4650 2400 5250 3150 +2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 + 4350 3150 5250 3150 5250 3300 4350 3300 4350 3150 +4 0 0 50 -1 4 11 0.0000 2 135 465 1575 1875 buffer\001 +4 2 0 50 -1 4 11 0.0000 2 135 390 1275 1875 alloc\001 +4 1 0 50 -1 0 12 0.0000 2 180 645 3000 2325 String 1\001 +4 1 0 50 -1 0 12 0.0000 2 180 645 4650 2325 String 2\001 +4 1 0 50 -1 0 12 0.0000 2 180 645 6300 2325 String 3\001 +4 1 0 50 -1 0 12 0.0000 2 180 1005 1950 1500 Heap header\001 +4 0 0 50 -1 0 12 0.0000 2 135 900 1575 3525 Text buffer\001 +4 2 0 50 -1 0 12 0.0000 2 135 360 5775 2100 prev\001 +4 0 0 50 -1 0 12 0.0000 2 120 315 2550 2775 text\001 +4 0 0 50 -1 0 12 0.0000 2 135 675 3375 2775 text+len\001 +4 0 0 50 -1 0 12 0.0000 2 120 360 5175 2475 next\001 Index: doc/theses/mike_brooks_MMath/string.tex =================================================================== --- doc/theses/mike_brooks_MMath/string.tex (revision 06ffa958c2cbd678e3ccc85025b02513968da3d4) +++ doc/theses/mike_brooks_MMath/string.tex (revision 8f250e00516ac41efae8e46c24bb5f3772c06d0f) @@ -57,5 +57,5 @@ s1.replace( 2, 3, "xy" ); $\C[2.25in]{// replace by position (zero origin) and length, mutable}\CRT$ cout << s1 << endl; -$\texttt{abxy}$ +$\texttt{\small abxy}$ \end{cfa} while Java allocates and returns a new string with the result, leaving the receiver unmodified. @@ -65,5 +65,5 @@ String r = s.replace( "cde", "xy" ); $\C[2.25in]{// replace by text, immutable}$ System.out.println( s + ' ' + r ); -$\texttt{abcde abxy}$ +$\texttt{\small abcde abxy}$ \end{java} % Generally, Java's @String@ type is immutable. @@ -73,5 +73,5 @@ sb.replace( 2, 5, "xy" ); $\C[2.25in]{// replace by position, mutable}\CRT$ System.out.println( sb ); -$\texttt{abxy}$ +$\texttt{\small abxy}$ \end{java} However, there are significant differences; @@ -278,5 +278,5 @@ \input{sharing10.tex} Strings @s1_crs@ and @s1_mid@ overlap at character 4, @j@ because the substrings are 3,2 and 4,2. -When @s1_crs@'s size increases by 1, @s1_mid@'s starting location moves from 4 to 5, but the overlaping character remains, changing to @'+'@. +When @s1_crs@'s size increases by 1, @s1_mid@'s starting location moves from 4 to 5, but the overlapping character remains, changing to @'+'@. \PAB{TODO: finish typesetting the demo} @@ -298,4 +298,11 @@ In general, a lifecycle function has access to an object by location, \ie constructors and destructors receive a @this@ parameter providing an object's memory address. +\begin{cfa} +struct S { int * ip; }; +void ?{}( S & @this@ ) { this.ip = new(); } $\C[3in]{// default constructor}$ +void ?{}( S & @this@, int i ) { ?{}(this); *this.ip = i; } $\C{// initializing constructor}$ +void ?{}( S & @this@, S s ) { this = s; } $\C{// copy constructor}$ +void ^?{}( S & @this@ ) { delete( this.ip ); } $\C{// destructor}\CRT$ +\end{cfa} The lifecycle implementation can then add this object to a collection at creation and remove it at destruction. A module providing lifecycle semantics can traverse the collection at relevant times to keep the objects ``good.'' @@ -307,12 +314,12 @@ To provide this knowledge, languages differentiate between initialization and assignment to a left-hand side. \begin{cfa} -Obj obj2 = obj1; // initialization, obj2 is uninitialized -obj2 = obj1; // assignment, obj2 must be initialized for management to work +Obj obj2 = obj1; $\C[1.5in]{// initialization, obj2 is initialized}$ +obj2 = obj1; $\C{// assignment, obj2 must be initialized for management to work}\CRT$ \end{cfa} Initialization occurs at declaration by value, parameter by argument, return temporary by function call. Hence, it is necessary to have two kinds of constructors: by value or object. \begin{cfa} -Obj obj1{ 1, 2, 3 }; // by value, management is initialized -Obj obj2 = obj1; // by obj, management is updated +Obj obj1{ 1, 2, 3 }; $\C[1.5in]{// by value, management is initialized}$ +Obj obj2 = obj1; $\C{// by obj, management is updated}\CRT$ \end{cfa} When no object management is required, initialization copies the right-hand value. @@ -321,12 +328,12 @@ The \CFA RAII system supports lifecycle functions, except for returning a value from a function to a temporary. For example, in \CC: -\begin{cfa} +\begin{c++} struct S {...}; S identity( S s ) { return s; } S s; s = identity( s ); // S temp = identity( s ); s = temp; -\end{cfa} -the generated code for the function call created a temporary with initialization from the function call, and then assigns the temporary to the receiver. -This two step approach means extra storage for the temporary and two copies to get the result into the receiver variable. +\end{c++} +the generated code for the function call created a temporary with initialization from the function call, and then assigns the temporary to the object. +This two step approach means extra storage for the temporary and two copies to get the result into the object variable. \CC{17} introduced return value-optimization (RVO)~\cite{RVO20} to ``avoid copying an object that a function returns as its value, including avoiding creation of a temporary object''. \CFA uses C semantics for function return giving direct value-assignment, which eliminates unnecessary code, but skips an essential feature needed by lifetime management. @@ -342,5 +349,5 @@ Then, programs written with the HL API will simply run faster. In the meantime, performance-critical sections of applications use LL. -Subsequent performance experiments~\VRef{s:PerformanceAssessment} with other string libraries has \CFA strings using the LL API. +Subsequent performance experiments \see{\VRef{s:PerformanceAssessment}} with other string libraries has \CFA strings using the LL API. These measurement gives a fair estimate of the goal state for \CFA. @@ -356,5 +363,5 @@ This cycle of frequent cheap allocations, interspersed with infrequent expensive compactions, has obvious similarities to a general-purpose memory manager based on garbage collection (GC). A few differences are noteworthy. -First, in a general purpose manager, the objects of allocation contain pointers to other such objects, making the transitive reachability of these objects be a critical property. +First, in a general purpose manager, the allocated objects may contain pointers to other objects, making the transitive reachability of these objects a crucial property. Here, the allocations are text, so one allocation never keeps another alive. Second, in a general purpose manager, the handle that keeps an allocation alive is just a lean pointer. @@ -368,16 +375,18 @@ \VRef[Figure]{f:memmgr-basic} shows the representation. -A heap header and its text buffer, defines a sharing context. +The heap header and text buffer define a sharing context. Normally, one global sharing context is appropriate for an entire program; -exceptions are discussed in [xref TBD]. +concurrent exceptions are discussed in \VRef{s:AvoidingImplicitSharing}. A string is a handle into the buffer and linked into a list. The list is doubly linked for $O(1)$ insertion and removal at any location. -Strings are orders n the list by text-buffer address, where there is no overlapping, and approximately, where there is. -The header maintains a next-allocation pointer, @alloc@, pointing to the last live allocation of the buffer. +Strings are orders in the list by string-text address, where there is no overlapping, and approximately, where there is. +The header maintains a next-allocation pointer, @alloc@, pointing to the last live allocation in the buffer. No external references point into the buffer and the management procedure relocates the text allocations as needed. -A string handle contains an explicit string, while its string is contiguous and not null terminated. +A string handle references a containing string, while its string is contiguous and not null terminated. The length sets an upper limit on the string size, but is large (4 or 8 bytes). -String handles can be allocated in the stack or heap, while the text buffer is large enough with good management so that only one dynamic allocation is necessary for it during program execution. -During this period strings can vary in size dynamically. +String handles can be allocated in the stack or heap, and represent the string variables in a program. +Normal C life-time rules apply to guarantee correctness of the string linked-list. +The text buffer is large enough with good management so that often only one dynamic allocation is necessary during program execution. +% During this period, strings can vary in size dynamically. When the text buffer fills, \ie the next new string allocation causes @alloc@ to point beyond the end of the buffer, the strings are compacted. @@ -386,10 +395,10 @@ After compaction, if the amount of free storage is still less than the new string allocation, a larger text buffer is heap allocated, the current buffer is copies into the new buffer, and the original buffer is freed. Note, the list of string handles is unaffected during a compaction; -only the string pointers are modified to new buffer locations. - -Object lifecycle events are the subscription-management triggers in such a service. +only the string pointers in the handles are modified to new buffer locations. + +Object lifecycle events are the \emph{subscription-management} triggers in such a service. There are two fundamental string-creation routines: importing external text like a C-string or reading a string, and initialization from an existing \CFA string. When importing, storage comes from the end of the buffer, into which the text is copied. -The resultant handle is inserted at the end of the handle list to maintain ordering. +The new string handle is inserted at the end of the handle list because the new text is at the end of the buffer. When initializing from text already in the text buffer, the new handle is a second reference into the original run of characters. In this case, the new handle's linked-list position is after the original handle. @@ -398,51 +407,79 @@ Certain string operations can results in a subset (substring) of another string. -The resulting handle is then place in the correct sorted position in the list, possible with a short linear search to locate the position. +The resulting handle is then placed in the correct sorted position in the list, possible with a short linear search to locate the position. For string operations resulting in a new string, that string is allocated at the end of the buffer. For shared-edit strings, handles that originally referenced containing locations need to see the new value at the new buffer location. -These strings are moved to appropriate locations at the end of the list (addressed further in [xref: TBD]. +These strings are moved to appropriate locations at the end of the list \see{[xref: TBD]}. For nonshared-edit strings, a containing string can be moved and the nonshared strings can remain in the same position. -String assignment words similarly to string initialization, maintain the invariant of linked list order matching buffer order. - -At the level of the memory manager, these modifications can always be explained as assignments; for example, an append is an assignment into the empty substring at the end. - -While favourable conditions allow for in-place editing, the general case requires a fresh buffer run. -For example, if the new value does not fit in the old place, or if other handles are still using the old value, then the new value will use a fresh buffer run. - -where there is room for the resulting value in the original buffer location, and where all handles referring to the original buffer location should see the new value, - -always boiled down to assignment and appendment. -Assignment has special cases that happen in-place, but in the general case, it is implemented as a sequence of appends onto a fresh allocation at the end of the buffer. -(The sequence has multiple steps when the assignment target is a substring: old before, new middle, old after.) -Similarly, an append request can be serviced in-place when there is room, or as a pair of appends. +String assignment words similarly to string initialization, maintain the invariant of linked-list order matching buffer order. + +At the level of the memory manager, these modifications can always be explained as assignments and appendment; +for example, an append is an assignment into the empty substring at the end of the buffer. +Favourable conditions allow for in-place editing: where there is room for the resulting value in the original buffer location, and where all handles referring to the original buffer location see the new value. +However, the general case requires a new buffer allocation: where the new value does not fit in the old place, or if other handles are still using the old value. \subsection{Sharing implementation} -The \CFA string module has two manners in which several string handles can share an underlying run of characters. - -The first type of sharing is user-requested, following the [xref Logical Overlap]. Here, the user requests, explicitly, that both handles be views of the same logical, modifiable string. This state is typically produced by the substring operation. In a typical substring call, the source string-handle is referencing an entire string, and the resulting, newly made, string handle is referencing a portion of the original. In this state, a subsequent modification made by either is visible in both. - -The second type of sharing happens when the system implicitly delays the physical execution of a logical \emph{copy} operation, as part of its copy-on-write optimization. This state is typically produced by constructing a new string, using an original string as its initialization source. In this state, a subsequent modification done on one handle triggers the deferred copy action, leaving the handles referencing different runs within the buffer, holding distinct values. - -A further abstraction, in the string module's implementation, helps distinguish the two senses of sharing. A share-edit set (SES) is an equivalence class over string handles, being the reflexive, symmetric and transitive closure of the relationship of one being constructed from the other, with the ``share edits'' opt-in given. It is represented by a second linked list among the handles. A string that shares edits with no other is in a SES by itself. Inside a SES, a logical modification of one substring portion may change the logical value in another, depending on whether the two actually overlap. Conversely, no logical value change can flow outside of a SES. Even if a modification on one string handle does not reveal itself \emph{logically} to anther handle in the same SES (because they don't overlap), if the modification is length-changing, completing the modification requires visiting the second handle to adjust its location in the sliding text. +The \CFA string module has two mechanisms to handle the case when string handles share a string of text. + +The first type of sharing is the user requests both string handles be views of the same logical, modifiable string. +This state is typically produced by the substring operation. +\begin{cfa} +string s = "abcde"; +string s1 = s( 1, 2 )@`share@; $\C[2.25in]{// explicit sharing}$ +s[1] = 'x'; $\C{// change s and s1}\CRT$ +sout | s | s1; +$\texttt{\small axcde xc}$ +\end{cfa} +In a typical substring call, the source string-handle is referencing an entire string, and the resulting, newly made, string handle is referencing a portion of the original. +In this state, a subsequent modification made by either is visible in both. + +The second type of sharing happens when the system implicitly delays the physical execution of a logical \emph{copy} operation, as part of its copy-on-write optimization. +This state is typically produced by constructing a new string, using an original string as its initialization source. +\begin{cfa} +string s = "abcde"; +string s1 = s( 1, 2 )@@; $\C[2.25in]{// no sharing}$ +s[1] = 'x'; $\C{// copy-on-write s1}\CRT$ +sout | s | s1; +$\texttt{\small axcde bc}$ +\end{cfa} +In this state, a subsequent modification done on one handle triggers the deferred copy action, leaving the handles referencing different text within the buffer, holding distinct values. + +A further abstraction, in the string module's implementation, helps distinguish the two senses of sharing. +A share-edit set (SES) is an equivalence class over string handles, being the reflexive, symmetric and transitive closure of the relationship of one string being constructed from another, with the ``share'' opt-in given. +The SES is represented by a second linked list among the handles. +A string that shares edits with no other is in a SES by itself. +Inside a SES, a logical modification of one substring portion may change the logical value in another, depending on whether the two actually overlap. +Conversely, no logical value change can flow outside of a SES. +Even if a modification on one string handle does not reveal itself \emph{logically} to anther handle in the same SES (because they do not overlap), if the modification is length-changing, completing the modification requires visiting the second handle to adjust its location in the sliding text. \subsection{Avoiding implicit sharing} - -There are tradeoffs associated with the copy-on-write mechanism. Several qualitative matters are detailed in the [xref: Performance Assessment] section and the qualitative issue of multi-threaded support is introduced here. The \CFA sting library provides a switch to disable the sharing mechanism for situations where it is inappropriate. - -Because of the inter-linked string handles, any participant managing one string is also managing, directly, the neighbouring strings, and from there, a data structure of the ``set of all strings.'' This data structure is intended for sequential access. A negative consequence of this decision is that multiple threads using strings need to be set up so that they avoid attempting to modify (concurrently) an instance of this structure. A positive consequence is that a single-threaded program, or a program with several independent threads, can use the sharing context without an overhead from locking. - -The \CFA sting library provides the @string_sharectx@ type to control an ambient sharing context for the current thread. It allows two adjustments: to opt out of sharing entirely, or to begin sharing within a private context. Either way, the chosen mode applies to the current thread, for the duration of the lifetime of the created @string_sharectx@ object, up to being suspended by child lifetimes of different contexts. The indented use is with stack-managed lifetimes, in which the established context lasts until the current function returns, and affects all functions called that don't create their own contexts. +\label{s:AvoidingImplicitSharing} + +There are tradeoffs associated with the copy-on-write mechanism. +Several qualitative matters are detailed in the \VRef{s:PerformanceAssessment} and the qualitative issue of multi-threaded support is introduced here. +The \CFA sting library provides a switch to disable the sharing mechanism for situations where it is inappropriate. + +Because of the inter-linked string handles, any participant managing one string is also managing, directly, the neighbouring strings, and from there, a data structure of the ``set of all strings.'' This data structure is intended for sequential access. +A negative consequence of this decision is that multiple threads using strings need to be set up so that they avoid attempting to modify (concurrently) an instance of this structure. +A positive consequence is that a single-threaded program, or a program with several independent threads, can use the sharing context without locking overhead. + +When the string library is running with sharing disabled, it runs without implicit thread-safety challenges, which is the same as the \CC STL, and with performance goals similar to the STL. +Running with sharing disabled can be thought of as a STL-emulation mode. +Hence, concurrent users of string objects must still bring their own mutual exclusion, but the string library does not add any cross thread uses that are not apparent in a user's code. + +\PAB{I could not get this to do anything.} +The \CFA string library does provides a @string_sharectx@ type to control an ambient sharing context for the current thread. +It allows two adjustments: to opt out of sharing entirely or to begin sharing within a private context. +Either way, the chosen mode applies only to the current thread, for the duration of the lifetime of the created @string_sharectx@ object, up to being suspended by child lifetimes of different contexts. +The intended use is with stack-managed lifetimes, in which the established context lasts until the current function returns, and affects all functions called that do not create their own contexts. \lstinputlisting[language=CFA, firstline=20, lastline=34]{sharectx.run.cfa} -In this example, the single-letter functions are called in alphabetic order. The functions @a@ and @d@ share string character ranges within themselves, but not with each other. The functions @b@, @c@ and @e@ never share anything. +In this example, the single-letter functions are called in alphabetic order. +The functions @a@ and @d@ share string character ranges within themselves, but not with each other. +The functions @b@, @c@ and @e@ never share anything. [ TODO: true up with ``is thread local'' (implement that and expand this discussion to give a concurrent example, or adjust this wording) ] - -When the string library is running with sharing disabled, it runs without implicit thread-safety challenges (which same as the STL) and with performance goals similar to the STL's. This thread-safety quality means concurrent users of one string object must still bring their own mutual exclusion, but the string library will not add any cross thread uses that were not apparent in the user's code. - -Running with sharing disabled can be thought of as STL-emulation mode. - @@ -457,7 +494,14 @@ \label{s:PerformanceAssessment} -I assessed the \CFA string library's speed and memory usage. I present these results in even equivalent cases, due to either micro-optimizations foregone, or fundamental costs of the added functionality. They also show the benefits and tradeoffs, as >100\% effects, of switching to \CFA, with the tradeoff points quantified. The final test shows the overall win of the \CFA text-sharing mechanism. It exercises several operations together, showing \CFA enabling clean user code to achieve performance that STL requires less-clean user code to achieve. - -To discuss: general goal of ... while STL makes you think about memory management, all the time, and if you do your performance can be great ... \CFA sacrifices this advantage modestly in exchange for big wins when you're not thinking about memory management. [Does this position cover all of it?] +I assessed the \CFA string library's speed and memory usage against strings in \CC STL. +The results are presented in even equivalent cases, due to either micro-optimizations foregone, or fundamental costs of the added functionality. +They also show the benefits and tradeoffs, as >100\% effects, of switching to \CFA, with the tradeoff points quantified. +The final test shows the overall win of the \CFA text-sharing mechanism. +It exercises several operations together, showing \CFA enabling clean user code to achieve performance that STL requires less-clean user code to achieve. + +To discuss: general goal of ... +while STL makes you think about memory management, all the time, and if you do your performance can be great ... +\CFA sacrifices this advantage modestly in exchange for big wins when you're not thinking about memory management. +[Does this position cover all of it?] To discuss: revisit HL v LL APIs @@ -465,11 +509,20 @@ To discuss: revisit no-sharing as STL emulation modes -These tests use randomly generated text fragments of varying lengths. A collection of such fragments is a \emph{corpus}. The mean length of a fragment from corpus is a typical explanatory variable. Such a length is used in one of three modes: + +\subsection{Methodology} + +These tests use randomly generated text fragments of varying lengths. +A collection of such fragments is a \emph{corpus}. +The mean length of a fragment from a corpus is a typical explanatory variable. +Such a length is used in one of three modes: \begin{description} - \item [Fixed-size] means all string fragments are of the stated size - \item [Varying from 1] means string lengths are drawn from a geometric distribution with the stated mean, and all lengths occur - \item [Varying from 16] means string lengths are drawn from a geometric distribution with the stated mean, but only lengths 16 and above occur; thus, the stated mean will be above 16. + \item [Fixed-size] means all string fragments are of the stated size. + \item [Varying from 1] means string lengths are drawn from a geometric distribution with the stated mean, and all lengths occur. + \item [Varying from 16] means string lengths are drawn from a geometric distribution with the stated mean, but only lengths 16 and above occur; thus, the stated mean is above 16. \end{description} -The geometric distribution implies that lengths much longer than the mean occur frequently. The special treatment of length 16 deals with comparison to STL, given that STL has short-string optimization (see [TODO: write and cross-ref future-work SSO]), currently not implemented in \CFA. When success notwithstanding SSO is illustrated, a fixed-size or from-16 distribution ensures that extra-optimized cases are not part of the mix on the STL side. In all experiments that use a corpus, its text is generated and loaded into the SUT before the timed phase begins. +The geometric distribution implies that lengths much longer than the mean occur frequently. +The special treatment of length 16 deals with comparison to STL, given that STL has short-string optimization (see [TODO: write and cross-ref future-work SSO]), currently not implemented in \CFA. +When success, notwithstanding SSO, is illustrated, a fixed-size or from-16 distribution ensures that extra-optimized cases are not part of the mix on the STL side. +In all experiments that use a corpus, its text is generated and loaded into the SUT before the timed phase begins. To discuss: vocabulary for reused case variables @@ -482,49 +535,79 @@ -\subsubsection{Test: Append} - -This test measures the speed of appending fragments of text onto a growing string. Its subcases include both \CFA being similar to STL, and their designs offering a tradeoff. - -One experimental variable is the user's operation being @a = a + b@ vs. @a += b@. While experienced programmers expect the latter to be ``what you obviously should do,'' controlling the penalty of the former both helps the API be accessible to beginners and also helps offer confidence that when a user tries to compose operations, the forms that are most natural to the user's composition are viable. - -Another experimental variable is whether the user's logical allocation is fresh vs reused. Here, \emph{reusing a logical allocation}, means that the program variable, into which the user is concatenating, previously held a long string:\\ -\begin{tabular}{ll} - Logical allocation fresh & Logical allocation reused \\ - & @ string x; @ \\ - @ for( ... ) { @ & @ for( ... ) { @ \\ - @ string x; @ & @ x = ""; @ \\ - @ for( ... ) @ & @ for( ... ) @ \\ - @ x += ... @ & @ x += ... @ \\ - @ } @ & @ } @ -\end{tabular}\\ -These benchmark drivers have an outer loop for ``until a sample-worthy amount of execution has happened'' and an inner loop for ``build up the desired-length string.'' It is sensible to doubt that a user should have to care about this difference, yet the STL performs differently in these cases. Concretely, both cases incur the cost of copying characters into the target string, but only the allocation-fresh case incurs a further reallocation cost, which is generally paid at points of doubling the length. For the STL, this cost includes obtaining a fresh buffer from the memory allocator and copying older characters into the new buffer, while \CFA-sharing hides such a cost entirely. The reuse-vs-fresh distinction is only relevant in the current \emph{append} tests. - -The \emph{append} tests use the varying-from-1 corpus construction; that is they do not assume away the STL's advantage from small-string optimization. - -To discuss: any other case variables introduced in the performance intro +\subsection{Test: Append} + +This test measures the speed of appending fragments of text onto a growing string. +Its subcases include both \CFA being similar to STL and their designs offering a tradeoff. + +One experimental variable is logically equivalent operations such as @a = a + b@ \vs @a += b@. +For numeric types, the generated code is equivalence, giving identical performance. +However, for string types there can be a significant difference in performance, especially if this code appears in a loop iterating a large number of times. +This difference might not be intuitive to beginners. + +Another experimental variable is whether the user's logical allocation is fresh \vs reused. +Here, \emph{reusing a logical allocation}, means that the program variable, into which the user is concatenating, previously held a long string:\\ +\begin{cquote} +\setlength{\tabcolsep}{20pt} +\begin{tabular}{@{}ll@{}} +\begin{cfa} + +for ( ... ) { + @string x;@ // fresh + for ( ... ) + x += ... +} +\end{cfa} +& +\begin{cfa} +string x; +for ( ... ) { + @x = "";@ // reused + for ( ... ) + x += ... +} +\end{cfa} +\end{tabular} +\end{cquote} +These benchmark drivers have an outer loop for ``until a sample-worthy amount of execution has happened'' and an inner loop for ``build up the desired-length string.'' +In general, a user should not have to care about this difference, yet the STL performs differently in these cases. +Furthermore, if a routine takes a string by reference, if cannot use the fresh approach. +Concretely, both cases incur the cost of copying characters into the target string, but only the allocation-fresh case incurs a further reallocation cost, which is generally paid at points of doubling the length. +For the STL, this cost includes obtaining a fresh buffer from the memory allocator and copying older characters into the new buffer, while \CFA-sharing hides such a cost entirely. +The fresh \vs reuse distinction is only relevant in the \emph{append} tests. + +The \emph{append} tests use the varying-from-1 corpus construction, \ie they do not assume away the STL's advantage for small-string optimization. +\PAB{To discuss: any other case variables introduced in the performance intro} +Figure \ref{fig:string-graph-peq-cppemu} shows this behaviour, by the STL and by \CFA in STL emulation mode. +\CFA reproduces STL's performance, up to a 15\% penalty averaged over the cases shown, diminishing with larger strings, and 50\% in the worst case. +This penalty characterizes the amount of implementation fine tuning done with STL and not done with \CFA in present state. +The larger inherent penalty, for a user mismanaging reuse, is 40\% averaged over the cases shown, is minimally 24\%, shows up consistently between the STL and \CFA implementations, and increases with larger strings. + +\PAB{Most of your graphs are unreadable. gnuplot is a good tool for generating high quality graphs.} \begin{figure} - \includegraphics[width=\textwidth]{string-graph-peq-cppemu.png} - \caption{Average time per iteration with one \lstinline{x += y} invocation, comparing \CFA with STL implementations (given \CFA running in STL emulation mode), and comparing the ``fresh'' with ``reused'' reset styles, at various string sizes.} - \label{fig:string-graph-peq-cppemu} + \includegraphics[width=\textwidth]{string-graph-peq-cppemu.png} + \caption{Average time per iteration with one \lstinline{x += y} invocation, comparing \CFA with STL implementations (given \CFA running in STL emulation mode), and comparing the ``fresh'' with ``reused'' reset styles, at various string sizes.} + \label{fig:string-graph-peq-cppemu} \end{figure} -Figure \ref{fig:string-graph-peq-cppemu} shows this behaviour, by the STL and by \CFA in STL emulation mode. \CFA reproduces STL's performance, up to a 15\% penalty averaged over the cases shown, diminishing with larger strings, and 50\% in the worst case. This penalty characterizes the amount of implementation fine tuning done with STL and not done with \CFA in present state. The larger inherent penalty, for a user mismanaging reuse, is 40\% averaged over the cases shown, is minimally 24\%, shows up consistently between the STL and \CFA implementations, and increases with larger strings. - \begin{figure} - \includegraphics[width=\textwidth]{string-graph-peq-sharing.png} - \caption{Average time per iteration with one \lstinline{x += y} invocation, comparing \CFA (having implicit sharing activated) with STL, and comparing the ``fresh'' with ``reused'' reset styles, at various string sizes.} - \label{fig:string-graph-peq-sharing} + \includegraphics[width=\textwidth]{string-graph-peq-sharing.png} + \caption{Average time per iteration with one \lstinline{x += y} invocation, comparing \CFA (having implicit sharing activated) with STL, and comparing the ``fresh'' with ``reused'' reset styles, at various string sizes.} + \label{fig:string-graph-peq-sharing} \end{figure} -In sharing mode, \CFA makes the fresh/reuse difference disappear, as shown in Figure \ref{fig:string-graph-peq-sharing}. At append lengths 5 and above, \CFA not only splits the two baseline STL cases, but its slowdown of 16\% over (STL with user-managed reuse) is close to the \CFA-v-STL implementation difference seen with \CFA in STL-emulation mode. +In sharing mode, \CFA makes the fresh/reuse difference disappear, as shown in Figure \ref{fig:string-graph-peq-sharing}. +At append lengths 5 and above, \CFA not only splits the two baseline STL cases, but its slowdown of 16\% over (STL with user-managed reuse) is close to the \CFA-v-STL implementation difference seen with \CFA in STL-emulation mode. \begin{figure} - \includegraphics[width=\textwidth]{string-graph-pta-sharing.png} - \caption{Average time per iteration with one \lstinline{x = x + y} invocation (new, purple bands), comparing \CFA (having implicit sharing activated) with STL. For context, the results from Figure \ref{fig:string-graph-peq-sharing} are repeated as the bottom bands. While not a design goal, and not graphed out, \CFA in STL-emulation mode outperformed STL in this case; user-managed allocation reuse did not affect any of the implementations in this case.} - \label{fig:string-graph-pta-sharing} + \includegraphics[width=\textwidth]{string-graph-pta-sharing.png} + \caption{Average time per iteration with one \lstinline{x = x + y} invocation (new, purple bands), comparing \CFA (having implicit sharing activated) with STL. +For context, the results from Figure \ref{fig:string-graph-peq-sharing} are repeated as the bottom bands. +While not a design goal, and not graphed out, \CFA in STL-emulation mode outperformed STL in this case; user-managed allocation reuse did not affect any of the implementations in this case.} + \label{fig:string-graph-pta-sharing} \end{figure} -When the user takes a further step beyond the STL's optimal zone, by running @x = x + y@, as in Figure \ref{fig:string-graph-pta-sharing}, the STL's penalty is above $15 \times$ while \CFA's (with sharing) is under $2 \times$, averaged across the cases shown here. Moreover, the STL's gap increases with string size, while \CFA's converges. +When the user takes a further step beyond the STL's optimal zone, by running @x = x + y@, as in Figure \ref{fig:string-graph-pta-sharing}, the STL's penalty is above $15 \times$ while \CFA's (with sharing) is under $2 \times$, averaged across the cases shown here. +Moreover, the STL's gap increases with string size, while \CFA's converges. \subsubsection{Test: Pass argument} @@ -532,54 +615,94 @@ To have introduced: STL string library forces users to think about memory management when communicating values across a function call -STL charges a prohibitive penalty for passing a string by value. With implicit sharing active, \CFA treats this operation as normal and supported. This test illustrates a main advantage of the \CFA sharing algorithm. It also has a case in which STL's small-string optimization provides a successful mitigation. +STL charges a prohibitive penalty for passing a string by value. +With implicit sharing active, \CFA treats this operation as normal and supported. +This test illustrates a main advantage of the \CFA sharing algorithm. +It also has a case in which STL's small-string optimization provides a successful mitigation. \begin{figure} - \includegraphics[width=\textwidth]{string-graph-pbv.png} - \caption{Average time per iteration 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-from-1} corpus construction, in which the STL-only benefit of small-string 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. [TODO: show version (b)]} - \label{fig:string-graph-pbv} + \includegraphics[width=\textwidth]{string-graph-pbv.png} + \caption{Average time per iteration 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-from-1} corpus construction, in which the STL-only benefit of small-string 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. +[TODO: show version (b)]} + \label{fig:string-graph-pbv} \end{figure} -Figure \ref{fig:string-graph-pbv} shows the costs for calling a function that receives a string argument by value. STL's performance worsens as string length increases, while \CFA has the same performance at all sizes. - -The \CFA cost to pass is nontrivial. The contributor is adding and removing the callee's string handle from the global list. This cost is $1.5 \times$ to $2 \times$ over STL's when small-string optimization applies, though this cost should be avoidable in the same case, given a \CFA realization of this optimization. At the larger sizes, when STL has to manage storage for the string, STL runs more than $3 \times$ slower, mainly due to time spent in the general-purpose memory allocator. +Figure \ref{fig:string-graph-pbv} shows the costs for calling a function that receives a string argument by value. +STL's performance worsens as string length increases, while \CFA has the same performance at all sizes. + +The \CFA cost to pass is nontrivial. +The contributor is adding and removing the callee's string handle from the global list. +This cost is $1.5 \times$ to $2 \times$ over STL's when small-string optimization applies, though this cost should be avoidable in the same case, given a \CFA realization of this optimization. +At the larger sizes, when STL has to manage storage for the string, STL runs more than $3 \times$ slower, mainly due to time spent in the general-purpose memory allocator. \subsubsection{Test: Allocate} -This test directly compares the allocation schemes of the \CFA string with sharing, compared with the STL string. It treats the \CFA scheme as a form of garbage collection, and the STL scheme as an application of malloc-free. The test shows that \CFA enables faster speed at a cost in memory usage. - -A garbage collector, afforded the freedom of managed memory, often runs faster than malloc-free (in an amortized analysis, even though it must occasionally stop to collect) because it is able to use its collection time to move objects. (In the case of the mini-allocator powering the \CFA string library, objects are runs of text.) Moving objects lets fresh allocations consume from a large contiguous store of available memory; the ``bump pointer'' book-keeping for such a scheme is very light. A malloc-free implementation without the freedom to move objects must, in the general case, allocate in the spaces between existing objects; doing so entails the heavier book-keeping to navigate and maintain a linked structure. - -A garbage collector keeps allocations around for longer than the using program can reach them. By contrast, a program using malloc-free (correctly) releases allocations exactly when they are no longer reachable. Therefore, the same harness will use more memory while running under garbage collection. A garbage collector can minimize the memory overhead by searching for these dead allocations aggressively, that is, by collecting more often. Tuned in this way, it spends a lot of time collecting, easily so much as to overwhelm its speed advantage from bump-pointer allocation. If it is tuned to collect rarely, then it leaves a lot of garbage allocated (waiting to be collected) but gains the advantage of little time spent doing collection. +This test directly compares the allocation schemes of the \CFA string with sharing, compared with the STL string. +It treats the \CFA scheme as a form of garbage collection, and the STL scheme as an application of malloc-free. +The test shows that \CFA enables faster speed at a cost in memory usage. + +A garbage collector, afforded the freedom of managed memory, often runs faster than malloc-free (in an amortized analysis, even though it must occasionally stop to collect) because it is able to use its collection time to move objects. +(In the case of the mini-allocator powering the \CFA string library, objects are runs of text.) Moving objects lets fresh allocations consume from a large contiguous store of available memory; the ``bump pointer'' book-keeping for such a scheme is very light. +A malloc-free implementation without the freedom to move objects must, in the general case, allocate in the spaces between existing objects; doing so entails the heavier book-keeping to navigate and maintain a linked structure. + +A garbage collector keeps allocations around for longer than the using program can reach them. +By contrast, a program using malloc-free (correctly) releases allocations exactly when they are no longer reachable. +Therefore, the same harness will use more memory while running under garbage collection. +A garbage collector can minimize the memory overhead by searching for these dead allocations aggressively, that is, by collecting more often. +Tuned in this way, it spends a lot of time collecting, easily so much as to overwhelm its speed advantage from bump-pointer allocation. +If it is tuned to collect rarely, then it leaves a lot of garbage allocated (waiting to be collected) but gains the advantage of little time spent doing collection. [TODO: find citations for the above knowledge] -The speed for memory tradeoff is, therefore, standard for comparisons like \CFA--STL string allocations. The test verifies that it is so and quantifies the returns available. - -These tests manipulate a tuning knob that controls how much extra space to use. Specific values of this knob are not user-visible and are not presented in the results here. Instead, its two effects (amount of space used and time per operation) are shown. The independent variable is the liveness target, which is the fraction of the text buffer that is in use at the end of a collection. The allocator will expand its text buffer during a collection if the actual fraction live exceeds this target. - -This experiment's driver allocates strings by constructing a string handle as a local variable then looping over recursive calls. The time measurement is of nanoseconds per such allocating call. The arrangement of recursive calls and their fan-out (iterations per recursion level) makes some of the strings long-lived and some of them short-lived. String lifetime (measured in number of subsequent string allocations) is ?? distributed, because each node in the call tree survives as long as its descendent calls. The run presented in this section used a call depth of 1000 and a fan-out of 1.006, which means that approximately one call in 167 makes two recursive calls, while the rest make one. This sizing was chosen to keep the amounts of consumed memory within the machine's last-level cache. +The speed for memory tradeoff is, therefore, standard for comparisons like \CFA--STL string allocations. +The test verifies that it is so and quantifies the returns available. + +These tests manipulate a tuning knob that controls how much extra space to use. +Specific values of this knob are not user-visible and are not presented in the results here. +Instead, its two effects (amount of space used and time per operation) are shown. +The independent variable is the liveness target, which is the fraction of the text buffer that is in use at the end of a collection. +The allocator will expand its text buffer during a collection if the actual fraction live exceeds this target. + +This experiment's driver allocates strings by constructing a string handle as a local variable then looping over recursive calls. +The time measurement is of nanoseconds per such allocating call. +The arrangement of recursive calls and their fan-out (iterations per recursion level) makes some of the strings long-lived and some of them short-lived. +String lifetime (measured in number of subsequent string allocations) is ?? distributed, because each node in the call tree survives as long as its descendent calls. +The run presented in this section used a call depth of 1000 and a fan-out of 1.006, which means that approximately one call in 167 makes two recursive calls, while the rest make one. +This sizing was chosen to keep the amounts of consumed memory within the machine's last-level cache. \begin{figure} - \includegraphics[width=\textwidth]{string-graph-allocn.png} - \caption{Space and time performance, under varying fraction-live targets, for the five string lengths shown, at (\emph{Fixed-size} corpus construction. [MISSING] The identified clusters are for the default fraction-live target, which is 30\%. MISSING: STL results, typically just below the 0.5--0.9 \CFA segment. All runs keep an average of 836 strings live, and the median string lifetime is ?? allocations.} - \label{fig:string-graph-allocn} + \includegraphics[width=\textwidth]{string-graph-allocn.png} + \caption{Space and time performance, under varying fraction-live targets, for the five string lengths shown, at (\emph{Fixed-size} corpus construction. +[MISSING] The identified clusters are for the default fraction-live target, which is 30\%. +MISSING: STL results, typically just below the 0.5--0.9 \CFA segment. +All runs keep an average of 836 strings live, and the median string lifetime is ?? allocations.} + \label{fig:string-graph-allocn} \end{figure} -Figure \ref{fig:string-graph-allocn} shows the results of this experiment. At all string sizes, varying the liveness threshold gives offers speed-for-space tradeoffs relative to STL. At the default liveness threshold, all measured string sizes see a ??\%--??\% speedup for a ??\%--??\% increase in memory footprint. - +Figure \ref{fig:string-graph-allocn} shows the results of this experiment. +At all string sizes, varying the liveness threshold gives offers speed-for-space tradeoffs relative to STL. +At the default liveness threshold, all measured string sizes see a ??\%--??\% speedup for a ??\%--??\% increase in memory footprint. \subsubsection{Test: Normalize} -This test is more applied than the earlier ones. It combines the effects of several operations. It also demonstrates a case of the \CFA API allowing user code to perform well, while being written without overt memory management, while achieving similar performance in STL requires adding memory-management complexity. +This test is more applied than the earlier ones. +It combines the effects of several operations. +It also demonstrates a case of the \CFA API allowing user code to perform well, while being written without overt memory management, while achieving similar performance in STL requires adding memory-management complexity. To motivate: edits being rare -The program is doing a specialized find-replace operation on a large body of text. In the program under test, the replacement is just to erase a magic character. But in the larger software problem represented, the rewrite logic belongs to a module that was originally intended to operate on simple, modest-length strings. The challenge is to apply this packaged function across chunks taken from the large body. Using the \CFA string library, the most natural way to write the helper module's function also works well in the adapted context. Using the STL string, the most natural ways to write the helper module's function, given its requirements in isolation, slow down when it is driven in the adapted context. +The program is doing a specialized find-replace operation on a large body of text. +In the program under test, the replacement is just to erase a magic character. +But in the larger software problem represented, the rewrite logic belongs to a module that was originally intended to operate on simple, modest-length strings. +The challenge is to apply this packaged function across chunks taken from the large body. +Using the \CFA string library, the most natural way to write the helper module's function also works well in the adapted context. +Using the STL string, the most natural ways to write the helper module's function, given its requirements in isolation, slow down when it is driven in the adapted context. \begin{lstlisting} void processItem( string & item ) { - // find issues in item and fix them + // find issues in item and fix them } \end{lstlisting}