Ignore:
Timestamp:
Nov 23, 2024, 8:28:37 PM (11 months ago)
Author:
JiadaL <j82liang@…>
Branches:
master
Children:
956b389
Parents:
b006c51e (diff), de7b7a5 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/mike_brooks_MMath/string.tex

    rb006c51e r10a9479d  
    55
    66
    7 \section{Logical overlap}
    8 
    9 \input{sharing-demo.tex}
     7\section{String Operations}
     8
     9To prepare for the following discussion, a simple comparison among C, \CC, and \CFA basic string operation is presented.
     10\begin{cquote}
     11\begin{tabular}{@{}l|l|l@{}}
     12C @char [ ]@                    &  \CC @string@                 & \CFA @string@ \\
     13\hline
     14@strcpy@, @strncpy@             & @=@                                   & @=@   \\
     15@strcat@, @strncat@             & @+@                                   & @+@   \\
     16@strcmp@, @strncmp@             & @==@, @!=@, @<@, @<=@, @>@, @>=@ & @==@, @!=@, @<@, @<=@, @>@, @>=@ \\
     17@strlen@                                & @length@                              & @size@        \\
     18@[ ]@                                   & @[ ]@                                 & @[ ]@ \\
     19                                                & @substr@                              & @substr@      \\
     20                                                & @replace@                             & @=@ \emph{(on a substring)}\\
     21@strstr@                                & @find@, @rfind@               & @find@, MISSING \\
     22@strcspn@                               & @find_first_of@, @find_last_of@ & @include@, MISSING \\
     23@strspn@                                & @find_first_not_of@, @find_last_not_of@ & @exclude@, MISSING \\
     24                                                & @c_str@                               & MISSING \\
     25\end{tabular}
     26\end{cquote}
     27The key commonality is that operations work on groups of characters for assigning. copying, scanning, and updating.
     28Because a C string is null terminated and requires explicit storage management \see{\VRef{s:String}}, most of its group operations are error prone and expensive.
     29Most high-level string libraries use a separate length field and specialized storage management to support group operations.
     30\CC strings retain null termination to interface with library functions requiring C strings.
     31\begin{cfa}
     32int open( const char * pathname, int flags );
     33string fname{ "test.cc" );
     34open( fname.@c_str()@ );
     35\end{cfa}
     36The function @c_str@ does not create a new null-terminated C string from the \CC string, as that requires passing ownership of the C string to the caller for eventual deletion.\footnote{
     37C functions like \lstinline{strdup} do return allocated storage that must be freed by the caller.}
     38Instead, each \CC string is null terminator just in case it might be needed for this purpose.
     39Providing this backwards compatibility with C has a ubiquitous performance and storage cost.
     40
     41
     42\section{Storage Management}
     43
     44This section discusses issues related to storage management of strings.
     45Specifically, it is common for strings to logically overlap completely or partially.
     46\begin{cfa}
     47string s1 = "abcdef";
     48string s2 = s1; $\C{// complete overlap, s2 == "abcdef"}$
     49string s3 = s1.substr( 0, 3 ); $\C{// partial overlap, s3 == "abc"}$
     50\end{cfa}
     51This raises the question of how strings behave when an overlapping component is changed,
     52\begin{cfa}
     53s3[1] = 'w'; $\C{// what happens to s1 and s2?}$
     54\end{cfa}
     55This question is the notion of mutable or immutable strings.
     56For example, Java has immutable strings that are copied when any overlapping string changes.
     57Note, the notion of underlying string mutability is not specified by @const@, \eg:
     58\begin{cfa}
     59const string s1 = "abc";
     60\end{cfa}
     61Here, @const@ applies to the @s1@ pointer to @"abc"@, and @"abc"@ is an immutable constant that is \emph{copied} into the string's storage.
     62Hence, @s1@ is not pointing at an immutable constant, meaning its underlying string is always mutable, unless some other designation is specified, such as Java's global rule.
     63
     64
     65\subsection{Logical overlap}
     66
     67\CFA provides a dynamic mechanism to indicate mutable or immutable as an assignment attribute: @`shareEdits@.
    1068
    1169Consider two strings @s1@ and @s1a@ that are in an aliasing relationship, and a third, @s2@, made by a simple copy from @s1@.
    12 \par\noindent
    13 \begin{tabular}{llll}
    14                                 & @s1@  & @s1a@ & @s2@  \\
    15 %\input{sharing-demo1.tex}
    16 \end{tabular}
    17 \par\noindent
     70Aliasing (@`shareEdits@) means that changes flow in both directions; with a simple copy, they do not.
     71\input{sharing1.tex}
     72
     73Aliasing (@`shareEdits@) means that changes flow in both directions; with a simple copy, they do not.
     74\input{sharing2.tex}
     75
     76Assignment of a value is just a modification.
     77The aliasing relationship is established at construction and is unaffected by assignment of a value.
     78\input{sharing3.tex}
     79
     80Assignment from a string is just assignment of a value.
     81Whether of not the RHS participates in aliasing is irrelevant.  Any aliasing of the LHS is unaffected.
     82\input{sharing4.tex}
     83
     84Consider new strings @s1_mid@ being an alias for a run in the middle of @s1@, along with @s2@, made by a simple copy from the middle of @s1@.
     85\input{sharing5.tex}
     86
     87Again, @`shareEdits@ passes changes in both directions; copy does not.
     88Note the difference in index values, with the \emph{b} position being 1 in the longer string and 0 in the shorter strings.
     89In the case of s1 aliasing with @s1_mid@, the very same character is being accessed by different positions.
     90\input{sharing6.tex}
     91
     92Once again, assignment of a value is a modification that flows through the aliasing relationship, without affecting its structure.
     93\input{sharing7.tex}
     94
     95In the \emph{ff} step, which is a positive example of flow across an aliasing relationship, the result is straightforward to accept because the flow direction is from contained (small) to containing (large).
     96The following rules for edits through aliasing substrings will guide how to flow in the opposite direction.
     97
     98Growth and shrinkage are natural extensions.
     99An empty substring is a real thing, at a well-defined location, whose meaning is extrapolated from the examples so far.
     100The intended metaphor is to operating a GUI text editor.
     101Having an aliasing substring is like using the mouse to select a few words.
     102Assigning onto an aliasing substring is like typing from having a few words selected: depending how much you type, the file being edited can get shorter or longer.
     103\input{sharing8.tex}
     104
     105Multiple portions can be aliased.
     106When there are several aliasing substrings at once, the text editor analogy becomes an online multi-user editor.
     107I should be able to edit a paragraph in one place (changing the document's length), without my edits affecting which letters are within a mouse-selection that you had made previously, somewhere else.
     108\input{sharing9.tex}
     109
     110When an edit happens on an aliasing substring that overlaps another, an effect is unavoidable.
     111Here, the passive party sees its selection shortened, to exclude the characters that were not part of the original selection.
     112\input{sharing10.tex}
     113
     114TODO: finish typesetting the demo
     115
     116%\input{sharing-demo.tex}
    18117
    19118
    20119\subsection{RAII limitations}
    21120
    22 Earlier work on \CFA [to cite Schluntz] implemented the feature of constructors and destructors.  A constructor is a user-defined function that runs implicitly, when control passes an object's declaration, while a destructor runs at the exit of the declaration's lexical scope.  The feature allows programmers to assume that, whenever a runtime object of a certain type is accessible, the system called one of the programmer's constructor functions on that object, and a matching destructor call will happen in the future.  The feature helps programmers know that their programs' invariants obtain.
    23 
    24 The purposes of such invariants go beyond ensuring authentic values for the bits inside the object.   These invariants can track occurrences of the managed objects in other data structures.  Reference counting is a typical application of the latter invariant type.  With a reference-counting smart pointer, the constructor and destructor \emph{of the pointer type} track the life cycles of occurrences of these pointers, by incrementing and decrementing a counter (usually) on the referent object, that is, they maintain a that is state separate from the objects to whose life cycles they are attached.  Both the \CC and \CFA RAII systems ares powerful enough to achieve such reference counting.
    25 
    26 The \CC RAII system supports a more advanced application.  A life cycle function has access to the object under management, by location; constructors and destuctors receive a @this@ parameter providing its memory address.  A lifecycle-function implementation can then add its objects to a collection upon creation, and remove them at destruction.  A modulue that provides such objects, by using and encapsulating such a collection, can traverse the collection at relevant times, to keep the objects ``good.''  Then, if you are the user of such an module, declaring an object of its type means not only receiving an authentically ``good'' value at initialization, but receiving a subscription to a service that will keep the value ``good'' until you are done with it.
    27 
    28 In many cases, the relationship between memory location and lifecycle is simple.  But with stack-allocated objects being used as parameters and returns, there is a sender version in one stack frame and a receiver version in another.  \CC is able to treat those versions as distinct objects and guarantee a copy-constructor call for communicating the value from one to the other.  This ability has implications on the language's calling convention.  Consider an ordinary function @void f( Vehicle x )@, which receives an aggregate by value.  If the type @Vehicle@ has custom lifecycle functions, then a call to a user-provided copy constructor occurs, after the caller evaluates its argument expression, after the callee's stack frame exists, with room for its variable @x@ (which is the location that the copy-constructor must target), but before the user-provided body of @f@ begins executing.  \CC achieves this ordering by changing the function signature, in the compiled form, to pass-by-reference and having the callee invoke the copy constructor in its preamble.  On the other hand, if @Vehicle@ is a simple structure then the C calling convention is applied as the code originally appeared, that is, the callsite implementation code performs a bitwise copy from the caller's expression result, into the callee's x.
    29 
    30 TODO: learn correction to fix inconcsistency: this discussion says the callee invokes the copy constructor, but only the caller knows which copy constructor to use!
    31 
    32 TODO: discuss the return-value piece of this pattern
    33 
    34 The \CFA RAII system has limited support for using lifecycle functions to provide a ``stay good'' service.  It works in restricted settings, including on dynamically allocated objects.  It does not work for communicating arguments and returns by value because the system does not produce a constructor call that tracks the implied move from a sender frame to a reciver frame.  This limitation does not prevent a typical reference-counting design from using call-with-value/return-of-value, because the constructor--destructor calls are correctly balanced.  But it impedes a ``stay-good'' service from supporting call-with-value/return-of-value, because the lifecycles presented to the constructor/destor calls do not keep stable locations.  A ``stay-good'' service is acheivable so long as call-with-value/return-of-value do not occur.  The original presentation [to cite Schluntz section] acknoweledges this limitiation; the present discussion makes its consequences more apparent.
    35 
    36 The \CFA team sees this limitation as part of a tactical interem state that should some day be improved.  The \CFA compiler is currently a source-to-source translator that targets relativly portable C.  Several details of its features are provisionally awkward or under-performant until finer control of its code generation is feasible.  In the present state, all calls that appear in \CFA source code as call-with-value/return-of-value are emitted this way to the underlying C calling convention.  SO WHAT?
    37 
    38 The present string-API contribution has both the ``stay good'' promise and call-with-value/return-of-value being essential.  The main string API uses a work-around to acheive the full feature set, at a runtime performance penalty.  An alternative API sacrifices call-with-value/return-of-value functionality to recover full runtime performance.  These APIs are layered, with the slower, friendlier High Level API (HL) wrapping the faster, more primitive Low Level API (LL).  They present the same features, up to lifecycle management, with call-with-value/return-of-value being disabled in LL and implemented with the workaround in HL.  The intention is for most future code to target HL.  In a more distant future state, where \CFA has an RAII system that can handle the problematic quadrant, the HL layer can be abolished, the LL can be renamed to match today's HL, and LL can have its call-with-value/return-of-value permission reenabled.  Then, programs written originally against HL will simply run faster.  In the meantime, two use cases of LL exist.  Performance-critical sections of applications have LL as an option.  Within [Xref perf experiments], though HL-v-LL penalties are measured, typcial comparisons of the contributed string libary vs similar systems are made using LL.  This measurement gives a fair estimate of the goal state for \CFA while it is an evloving work in progress.
    39 
     121Earlier work on \CFA~\cite[ch.~2]{Schluntz17} implemented object constructors and destructors for all types (basic and user defined).
     122A constructor is a user-defined function run implicitly \emph{after} an object's declaration-storage is created, and a destructor is a user-defined function run \emph{before} an object's declaration-storage is deleted.
     123This feature, called RAII~\cite[p.~389]{Stroustrup94}, guarantees pre invariants for users before accessing an object and post invariants for the programming environment after an object terminates.
     124
     125The purposes of these invariants goes beyond ensuring authentic values inside an object.
     126Invariants can also track occurrences of managed objects in other data structures.
     127For example, reference counting is a typical application of an invariant outside of the data values.
     128With a reference-counting smart-pointer, the constructor and destructor \emph{of a pointer type} tracks the life cycle of the object it points to.
     129Both \CC and \CFA RAII systems are powerful enough to achieve reference counting.
     130
     131In 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.
     132The lifecycle implementation can then add this object to a collection at creation and remove it at destruction.
     133A module providing lifecycle semantics can traverse the collection at relevant times to keep the objects ``good.''
     134Hence, declaring such an object not only ensures ``good'' authentic values, but also an implicit subscription to a service that keeps the value ``good'' across its lifetime.
     135
     136In many cases, the relationship between memory location and lifecycle is straightforward.
     137For example, stack-allocated objects being used as parameters and returns, with a sender version in one stack frame and a receiver version in another, as opposed to assignment where sender and receiver are in the same stack frame.
     138What is crucial for lifecycle management is knowing if the receiver is initialized or uninitialized, \ie an object is or is not currently associated with management.
     139To provide this knowledge, languages differentiate between initialization and assignment to a left-hand side.
     140\begin{cfa}
     141Obj obj2 = obj1;  // initialization, obj2 is uninitialized
     142obj2 = obj1;        // assignment, obj2 must be initialized for management to work
     143\end{cfa}
     144Initialization occurs at declaration by value, parameter by argument, return temporary by function call.
     145Hence, it is necessary to have two kinds of constructors: by value or object.
     146\begin{cfa}
     147Obj obj1{ 1, 2, 3 };  // by value, management is initialized
     148Obj obj2 = obj1;     // by obj, management is updated
     149\end{cfa}
     150When no object management is required, initialization copies the right-hand value.
     151Hence, the calling convention remains uniform, where the unmanaged case uses @memcpy@ as the initialization constructor and managed uses the specified initialization constructor.
     152
     153The \CFA RAII system supports lifecycle functions, except for returning a value from a function to a temporary.
     154For example, in \CC:
     155\begin{cfa}
     156struct S {...};
     157S identity( S s ) { return s; }
     158S s;
     159s = identity( s ); // S temp = identity( s ); s = temp;
     160\end{cfa}
     161the generated code for the function call created a temporary with initialization from the function call, and then assigns the temporary to the receiver.
     162This two step approach means extra storage for the temporary and two copies to get the result into the receiver variable.
     163\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''.
     164\CFA uses C semantics for function return giving direct value-assignment, which eliminates unnecessary code, but skips an essential feature needed by lifetime management.
     165The following discusses the consequences of this semantics with respect to lifetime management of \CFA strings.
     166
     167The present string-API contribution provides lifetime management with initialization semantics on function return.
     168The workaround to achieve the full lifetime semantics does have a runtime performance penalty.
     169An alternative API sacrifices return initialization semantics to recover full runtime performance.
     170These APIs are layered, with the slower, friendlier High Level API (HL) wrapping the faster, more primitive Low Level API (LL).
     171Both API present the same features, up to lifecycle management, with return initialization being disabled in LL and implemented with the workaround in HL.
     172The intention is for most future code to target HL.
     173When \CFA becomes a full compiler, it can provide return initialization with RVO optimizations.
     174Then, programs written with the HL API will simply run faster.
     175In the meantime, performance-critical sections of applications use LL.
     176Subsequent performance experiments~\VRef{s:PerformanceAssessment} with other string libraries has \CFA strings using the LL API.
     177These measurement gives a fair estimate of the goal state for \CFA.
    40178
    41179
    42180\subsection{Memory management}
    43181
    44 A centrepriece of the string module is its memory manager.  The managment scheme defines a large shared buffer for strings' text.  Allocation in this buffer is always bump-pointer; the buffer is compacted and/or relocated with growth when it fills.  A string is a smart pointer into this buffer.
    45 
    46 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.  Here, the allocations are of buffers of text, never pointers, so one allocation never keeps another one alive.  Second, in a general purpose manager, where the handle that keeps an allocation alive is the same as the program's general-purpose inter-object reference, an extremely lean representation of this reference is required.  Here, a fatter representation is acceptable because [why??].
    47 
    48 
    49 Figure [memmgr-basix.vsdx] shows the representation.  A heap header, with its text buffer, defines a sharing context.  Often, one global sharing context is appropriate for an entire program; exceptions are discussed in [xref TBD].  Strings are handles into the buffer.  They are members of a linked list whose order matches the order of their buffer fragments (exactly, where there is no overlapping, and approximately, where there is).  The header maintains a next-allocation pointer (alloc, in the figure) after the last live allocation of the buffer.  No external references into the buffer are allowed and the management procedure relocates the text allocations as needed.  The string handles contain explicit length fields, null termination characters are not used and all string text is kept in contiguous storage.  When strings (the inter-linked hanldes) are allocated on the program's call stack, a sustained period with no use of the program's dynamic memory allocator can ensue, during which the program nonetheless creates strings, destroys them, and runs length-increasing modifications on existing ones. 
    50 
    51 Compaction happens when the heap fills.  It is the first of two uses of the linked list.  The list allows discovering all live string handles, and from them, the ranges of the character buffer that are in use.  With these ranges known, their total character count gives the amount of space in use.  When that amount is small, compared with the current buffer size, an in-place compaction occurs, which enatils copying the in-use ranges, to be adjacent, at the font of the buffer.  When the in-use amount is large, a larger buffer is allocated (using the program's general-purpose dynamic allcator), the in-use strings are copied to be adjacent at the front of it, and the original buffer is freed back to the program's general allocator.  Either way, navigating the links between the handles provides the pointers into the buffer, first read, to find the source fragment, then written with the location of the resultant fragment.  This linkage across the structure is unaffected during a compaction; only the pointers from the handles to the buffer are modified.  This modification, along with the grooming/provisioning of the text storage resouce that it represents, is an example, in the language of [xref RAII limitations] of the string module providing a ``stay good'' service.
    52 
    53 Object lifecycle events are the subscription-management triggers in such a service.  There are two fundamental string-creation routines:  importing from external text like a C-string, and initialization from an existing \CFA string.  When importing, a fresh allocation at the free end fo the buffer occurs, into which the text is copied.  The resultant handle is therefore inserted into the list at the position after the incumbent last handle, a position given by the heap manager's ``last handle'' pointer.  When initializing from text already on the \CFA heap, the resultant handle is a second reference onto the original run of characters.  In this case, the resultant handle's linked-list position is beside the original handle.  Both string initialization styles preserve the string module's internal invriant that the linked-list order match the buffer order.  For string destruction, the list being doubly linked provides for easy removal of the disappearing handle.
    54 
    55 While a string handle is live, it accepts modification operations, some of which make it reference a different portion of the underlying buffer, and accordingly, move the handle to a different position in the inter-handle list.   While special cases have more optimal handling, the general case requires a fresh buffer run.  In this case, the new run is allocated at the bump-pointer end and filled with the required value.  Then, handles that originally referenced the old location and need to see the new value are pointed at the new buffer location, unlinked from their original positions in the handles' list, and linked in at the end of the list.  An optimal case, when the target is not a substring of something larger, and the source is text from elsewhere in the managed buffer, allows the target to be re-pointed at the source characters, and accordingly, move list position to be beside the source.  Cases where in-place editing happens, addressed further in [xref: TBD], leave affected handles in their original list positions.  In analogy to the two cases of string initialization, the two cases of realizing assignment by moving either to a fresh buffer run, or to overlap references with the source, maintain the invariant of linked list order matching buffer order.
    56 
    57 
    58 To explain: GCing allocator doing bump-pointer with compaction
    59 
    60 
    61 
    62 At the level of the memory manager, these modifications can aways be explained as assignments; for example, an append is an assignemnt into the empty substring at the end.
    63 
    64 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.
     182A centrepiece of the string module is its memory manager.
     183The management scheme defines a shared buffer for string text.
     184Allocation in this buffer is via a bump-pointer;
     185the buffer is compacted and/or relocated with growth when it fills.
     186A string is a smart pointer into this buffer.
     187
     188This cycle of frequent cheap allocations, interspersed with infrequent expensive compactions, has obvious similarities to a general-purpose memory manager based on garbage collection (GC).
     189A few differences are noteworthy.
     190First, 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.
     191Here, the allocations are text, so one allocation never keeps another alive.
     192Second, in a general purpose manager, the handle that keeps an allocation alive is just a lean pointer.
     193For strings, a fatter representation is acceptable because there are fewer string head pointers versus chained pointers within nodes as for linked containers.
     194
     195\begin{figure}
     196\includegraphics{memmgr-basic}
     197\caption{String memory-management data structures}
     198\label{f:memmgr-basic}
     199\end{figure}
     200
     201\VRef[Figure]{f:memmgr-basic} shows the representation.
     202A heap header and its text buffer, defines a sharing context.
     203Normally, one global sharing context is appropriate for an entire program;
     204exceptions are discussed in [xref TBD].
     205A string is a handle into the buffer and linked into a list.
     206The list is doubly linked for $O(1)$ insertion and removal at any location.
     207Strings are orders n the list by text-buffer address, where there is no overlapping, and approximately, where there is.
     208The header maintains a next-allocation pointer, @alloc@, pointing to the last live allocation of the buffer.
     209No external references point into the buffer and the management procedure relocates the text allocations as needed.
     210A string handle contains an explicit string, while its string is contiguous and not null terminated.
     211The length sets an upper limit on the string size, but is large (4 or 8 bytes).
     212String 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.
     213During this period strings can vary in size dynamically.
     214
     215When the text buffer fills, \ie the next new string allocation causes @alloc@ to point beyond the end of the buffer, the strings are compacted.
     216The linked handles define all live strings in the buffer, which indirectly defines the allocated and free space in the buffer.
     217Since the string handles are in (roughly) sorted order, the handle list can be traversed copying the first text to the start of the buffer and subsequent strings after each over.
     218After 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.
     219Note, the list of string handles is unaffected during a compaction;
     220only the string pointers are modified to new buffer locations.
     221
     222Object lifecycle events are the subscription-management triggers in such a service.
     223There are two fundamental string-creation routines: importing external text like a C-string or reading a string, and initialization from an existing \CFA string.
     224When importing, storage comes from the end of the buffer, into which the text is copied.
     225The resultant handle is inserted at the end of the handle list to maintain ordering.
     226When initializing from text already in the text buffer, the new handle is a second reference into the original run of characters.
     227In this case, the new handle's linked-list position is after the original handle.
     228Both string initialization styles preserve the string module's internal invariant that the linked-list order matches the buffer order.
     229For string destruction, handles are removed from the list.
     230
     231Certain string operations can results in a subset (substring) of another string.
     232The resulting handle is then place in the correct sorted position in the list, possible with a short linear search to locate the position.
     233For string operations resulting in a new string, that string is allocated at the end of the buffer.
     234For shared-edit strings, handles that originally referenced containing locations need to see the new value at the new buffer location.
     235These strings are moved to appropriate locations at the end of the list (addressed further in [xref: TBD].
     236For nonshared-edit strings, a containing string can be moved and the nonshared strings can remain in the same position.
     237String assignment words similarly to string initialization, maintain the invariant of linked list order matching buffer order.
     238
     239At 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.
     240
     241While favourable conditions allow for in-place editing, the general case requires a fresh buffer run.
     242For 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.
    65243
    66244where 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,
    67245
    68 
    69 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
    70 
     246always boiled down to assignment and appendment.
     247Assignment 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.
     248(The sequence has multiple steps when the assignment target is a substring: old before, new middle, old after.)
     249Similarly, an append request can be serviced in-place when there is room, or as a pair of appends.
    71250
    72251
    73252\subsection{Sharing implementation}
    74253
    75 The \CFA string module has two manners in which serveral string handles can share an unerlying run of characters. 
    76 
    77 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 prodecd by the substring operation.  In a typical substring call, the source string-handle is referencing an entire string, and the resluting, newly made, string handle is referencing a portion of the orignal.  In this state, a subsequent modification made by either is visible in both.
    78 
    79 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 intialization 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.
     254The \CFA string module has two manners in which several string handles can share an underlying run of characters. 
     255
     256The 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.
     257
     258The 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.
    80259
    81260A 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.
    … …  
    84263\subsection{Avoiding implicit sharing}
    85264
    86 There are tradeoffs associated with the copy-on-write mechanism.  Several quatitative matters are detailed in the [xref: Performance Assessment] section and the qualitiative issue of multi-threaded support is introduced here.  The \CFA sting library provides a switch to disable the sharing mechanism for situtations where it is inappropriate.
     265There 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.
    87266
    88267Because 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.
    89268
    90 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 liftimes of different contexts.  The indended 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.
    91 \lstinputlisting[language=CFA, firstline=20, lastline=34]{sharectx-demo.cfa}
     269The \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.
     270\lstinputlisting[language=CFA, firstline=20, lastline=34]{sharectx.run.cfa}
    92271In 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.
    93272
    94273[ TODO: true up with ``is thread local'' (implement that and expand this discussion to give a concurrent example, or adjust this wording) ]
    95274
    96 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 exlusion, but the string libary will not add any cross thread uses that were not apparent in the user's code.
     275When 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.
    97276
    98277Running with sharing disabled can be thought of as STL-emulation mode.
    … …  
    107286
    108287
    109 \subsection{Performance assessment}
    110 
    111 I assessed the CFA string library's speed and memory usage.  I present these results ineven quivalent 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.
    112 
    113 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 mamangement.  [Does this position cover all of it?]
     288\section{Performance assessment}
     289\label{s:PerformanceAssessment}
     290
     291I 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.
     292
     293To 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?]
    114294
    115295To discuss: revisit HL v LL APIs
    116296
    117 To discuss: revisit nosharing as STL emulation modes
     297To discuss: revisit no-sharing as STL emulation modes
    118298
    119299These 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:
    … …  
    121301    \item [Fixed-size] means all string fragments are of the stated size
    122302    \item [Varying from 1] means string lengths are drawn from a geometric distribution with the stated mean, and all lengths occur
    123     \item [Varying from 16] means string lengths are drawn from a geometric distribution with the stated mean, but only lengths 16 and obove occur; thus, the stated mean will be above 16.
     303    \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.
    124304\end{description}
    125 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 implmented 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.
     305The 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.
    126306
    127307To discuss: vocabulary for reused case variables
    … …  
    136316\subsubsection{Test: Append}
    137317
    138 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.
    139 
    140 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,'' controling the penatly 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.
    141 
    142 Another experimental variable is whether the user's logical allocation is fresh vs reused.  Here, \emph{reusing a logical allocation}, means that the prgram variable, into which the user is concatenating, previously held a long string:\\
     318This 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.
     319
     320One 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.
     321
     322Another 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:\\
    143323\begin{tabular}{ll}
    144324    Logical allocation fresh                   & Logical allocation reused                  \\
    … …  
    150330    @ } @                                      & @ } @
    151331\end{tabular}\\
    152 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.  Concretly, 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 currrent \emph{append} tests.
    153 
    154 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 opitimization.
    155 
    156 To discuss: any other case variables intruduced in the performance intro
     332These 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.
     333
     334The \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.
     335
     336To discuss: any other case variables introduced in the performance intro
    157337
    158338\begin{figure}
    … …  
    162342\end{figure}
    163343
    164 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 penatly 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.
     344Figure \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.
    165345
    166346\begin{figure}
    … …  
    170350\end{figure}
    171351
    172 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.
     352In 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.
    173353
    174354\begin{figure}
    … …  
    178358\end{figure}
    179359
    180 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.
     360When 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.
    181361
    182362\subsubsection{Test: Pass argument}
    … …  
    184364To have introduced:  STL string library forces users to think about memory management when communicating values across a function call
    185365
    186 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 adjantage of the \CFA sharing algorithm.  It also has a case in which STL's small-string optimization provides a successful mitigation.
     366STL 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.
    187367
    188368\begin{figure}
    … …  
    201381This 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.
    202382
    203 A garbage collector, afforded the freedom of managed memory, often runs faster than malloc-free (in an ammortized 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.
     383A 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.
    204384
    205385A 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.
    … …  
    215395\begin{figure}
    216396    \includegraphics[width=\textwidth]{string-graph-allocn.png}
    217     \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.}
     397    \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.}
    218398    \label{fig:string-graph-allocn}
    219399\end{figure}
    220400
    221 Figure \ref{fig:string-graph-allocn} shows the results of this experiemnt.  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.
     401Figure \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.
    222402
    223403
    … …  
    225405\subsubsection{Test: Normalize}
    226406
    227 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.
     407This 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.
    228408
    229409To motivate: edits being rare
Note: See TracChangeset for help on using the changeset viewer.