Changeset 6f7aff3

Timestamp:

Oct 19, 2021, 10:31:53 AM (3 years ago)

Author:

Michael Brooks <mlbrooks@…>

Branches:

ADT, ast-experimental, enum, master, pthread-emulation, qualifiedEnum

Children:

fe18b46

Parents:

7b0e8b7

Message:

String hybrid assignment to unshared now optimizes to overwrite instead of copy.

Files:

• libcfa/src/containers/string_res.cfa (modified) (9 diffs)
• tests/collections/string-api-coverage.cfa (modified) (2 diffs)
• tests/collections/string-ctx-manage.cfa (modified) (3 diffs)

libcfa/src/containers/string_res.cfa

@@ -53 +53 @@
 static inline int ByteCmp( char *, int, int, char *, int, int );        // compare 2 blocks of bytes
 static inline char *VbyteAlloc( VbyteHeap &, int );                     // allocate a block bytes in the heap
-
+static inline char *VbyteTryAdjustLast( VbyteHeap &, int );
 
 static inline void AddThisAfter( HandleNode &, HandleNode & );
@@ -313 +313 @@
     this.Handle.s = resultSesStart + beforeLen;
     this.Handle.lnth = bsize;
-    MoveThisAfter( this.Handle, *resultPadPosition );
+    if (resultPadPosition)
+        MoveThisAfter( this.Handle, *resultPadPosition );
 
     // adjust all substring string and handle locations, and check if any substring strings are outside the new base string
@@ -365 +366 @@
             }
         }
-        MoveThisAfter( p->Handle, *resultPadPosition ); // move substring handle to maintain sorted order by string position
+        if (resultPadPosition)
+            MoveThisAfter( p->Handle, *resultPadPosition );     // move substring handle to maintain sorted order by string position
     }
 }
@@ -387 +389 @@
     verify( editSetLength >= this.Handle.lnth );
 
-
-    if ( this.Handle.lnth == editSetLength                // the entire run of the share-edit set is being overwritten: SES's result will only use characters from the source string
-        && & valSrc                                       // sourcing from a managed string
-        && valSrc.Handle.ulink == this.Handle.ulink  ) {  // sourcing from same heap
-
+    if ( this.shareEditSet_owns_ulink ) {                 // assigning to private context
+        // ok to overwrite old value within LHS
+        char * prefixStartOrig = shareEditSetStartPeer->Handle.s;
+        int prefixLen = this.Handle.s - prefixStartOrig;
+        char * suffixStartOrig = this.Handle.s + this.Handle.lnth;
+        int suffixLen = shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - suffixStartOrig;
+
+        int delta = bsize - this.Handle.lnth;
+        if ( char * oldBytes = VbyteTryAdjustLast( *this.Handle.ulink, delta ) ) {
+            // growing: copy from old to new
+            char * dest = VbyteAlloc( *this.Handle.ulink, editSetLength );
+            char *destCursor = dest;        memcpy(destCursor, prefixStartOrig, prefixLen);
+            destCursor += prefixLen;        memcpy(destCursor, buffer         , bsize    );
+            destCursor += this.Handle.lnth; memcpy(destCursor, suffixStartOrig, suffixLen);
+            assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer, 
+                dest,
+                editSetLength,
+                0p, bsize);
+            free( oldBytes );
+        } else {
+            // room is already allocated in-place: bubble suffix and overwite middle
+            memmove( suffixStartOrig + delta, suffixStartOrig, suffixLen );
+            memcpy( this.Handle.s, buffer, bsize );
+
+            assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer, 
+                shareEditSetStartPeer->Handle.s,
+                editSetLength,
+                0p, bsize);
+        }
+
+    } else if (                                           // assigning to shared context
+        this.Handle.lnth == editSetLength &&              // overwriting entire run of SES
+        & valSrc &&                                       // sourcing from a managed string
+        valSrc.Handle.ulink == this.Handle.ulink  ) {     // sourcing from same heap
+
+        // SES's result will only use characters from the source string => reuse source
         assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer, 
             valSrc.Handle.s,
@@ -398 +431 @@
         
     } else {
+        // overwriting a proper substring of some string: mash characters from old and new together (copy on write)
+        // OR we are importing characters: need to copy eagerly (can't refer to source)
 
         // full string is from start of shareEditSetStartPeer thru end of shareEditSetEndPeer
@@ -416 +451 @@
         }
 
-        // we are only overwriting a proper substring of some string: need to mash characters from old and new together
-        // OR we are importing characters: need to copy eagerly
         string_res pasting = {
             * this.Handle.ulink,                               // maintain same heap, regardless of context
@@ -439 +472 @@
             &pasting.Handle, bsize);
     }
-
-    // So now, capture their values for use in the overlap cases, below.
-    // Do not factor these definitions with the arguments used in string building above.
-
 }
 
@@ -750 +779 @@
 
 // Allocates specified storage for a string from byte-string area. If not enough space remains to perform the
-// allocation, the garbage collection routine is called and a second attempt is made to allocate the space. If the
-// second attempt fails, a further attempt is made to create a new, larger byte-string area.
+// allocation, the garbage collection routine is called.
 
 static inline char * VbyteAlloc( VbyteHeap & this, int size ) with(this) {
@@ -775 +803 @@
     return r;
 } // VbyteAlloc
+
+
+// Adjusts the last allocation in this heap by delta bytes, or resets this heap to be able to offer
+// new allocations of its original size + delta bytes. Positive delta means bigger;
+// negative means smaller.  A null return indicates that the original heap location has room for
+// the requested growth.  A non-null return indicates that copying to a new location is required
+// but has not been done; the returned value is the old heap storage location; `this` heap is
+// modified to reference the new location.  In the copy-requred case, the caller should use
+// VbyteAlloc to claim the new space, while doing optimal copying from old to new, then free old.
+
+static inline char * VbyteTryAdjustLast( VbyteHeap & this, int delta ) with(this) {
+
+    if ( ( uintptr_t )EndVbyte + delta <= ( uintptr_t )ExtVbyte ) {
+        // room available
+        EndVbyte += delta;
+        return 0p;
+    }
+
+    char *oldBytes = StartVbyte;
+
+    NoOfExtensions += 1;
+    CurrSize *= 2;
+    StartVbyte = EndVbyte = alloc(CurrSize);
+    ExtVbyte = StartVbyte + CurrSize;
+
+    return oldBytes;
+}
 
 

tests/collections/string-api-coverage.cfa

@@ -1 +1 @@
 #include <containers/string.hfa>
+#include <string_sharectx.hfa>
 
 void assertWellFormedHandleList( int maxLen ) { // with(HeapArea)
@@ -25 +26 @@
 
 int main () {
+
+    #ifdef STRING_SHARING_OFF
+    sout | "string sharing disabled";
+    string_sharectx c = { NO_SHARING };
+    #endif
+
     string s = "hello";
     string s2 = "hello";

tests/collections/string-ctx-manage.cfa

@@ -3 +3 @@
 #include <string_res.hfa>
 
+// In these tests, shared heaps are never remotely full and string sizes are tiny.
+// So here, the SUT should put a yes-sharing string in a heap with lots of spare room.
+// The SUT should always keep a no-sharing string's buffer 1x--2x the string's size.
+// This check uses 3x as a heuristic split between those cases.
+void assertSpareRoomInHeap( string & s, bool expectOversized ) {
+    double bytesInHeap = DEBUG_string_bytes_in_heap(s.inner->Handle.ulink);
+    double bytesUsed =  s.inner->Handle.lnth;
+    double overhead = bytesInHeap / bytesUsed;
+    assert (overhead >= 1);
+    if ( expectOversized )
+        assert( overhead >= 3.0 );
+    else 
+        assert( overhead < 3.0 );
+}
+
 void baseline() {
     string x = "hi";
+    assertSpareRoomInHeap( x, true );
 
     string y = x; // construct y in same context, no write yet => no copy yet
+    assertSpareRoomInHeap( y, true );
     assert( y.inner->Handle.s == x.inner->Handle.s);
     sout | y; // hi
 
     x = "bye";
+    assertSpareRoomInHeap( x, true );
     y = x; // y in same context, no write yet => no copy yet
+    assertSpareRoomInHeap( y, true );
     assert( y.inner->Handle.s == x.inner->Handle.s);
     sout | y; // bye
@@ -18 +37 @@
 void eagerCopy() {
     string x = "hi";
+    assertSpareRoomInHeap( x, true );
     string_sharectx c = { NEW_SHARING };
 
     string y = x; // construct y in different context => eager copy
+    assertSpareRoomInHeap( y, true );
     assert( y.inner->Handle.s != x.inner->Handle.s);
     sout | y; // hi
 
     x = "bye";
+    assertSpareRoomInHeap( x, true );
     y = x; // y was already in different context => eager copy
+    assertSpareRoomInHeap( y, true );
     assert( y.inner->Handle.s != x.inner->Handle.s);
     sout | y; // bye
@@ -32 +55 @@
 void soloAlloc() {
     string x = "hi";
+    assertSpareRoomInHeap( x, true );
     string_sharectx c = { NO_SHARING };
     
     string y = x; // y allocates into private pad, implying eager copy
+    assertSpareRoomInHeap( y, false );
     assert( y.inner->Handle.s != x.inner->Handle.s);
-    assert( DEBUG_string_bytes_in_heap(y.inner->Handle.ulink) == y.inner->Handle.lnth );  // y is in a perfectly fitting heap
     sout | y; // hi
 
     x = "bye";
+    assertSpareRoomInHeap( x, true );
     y = x; // into private y => eager copy
+    assertSpareRoomInHeap( y, false );
     assert( y.inner->Handle.s != x.inner->Handle.s);
-//    assert( DEBUG_string_bytes_in_heap(y.inner->Handle.ulink) == y.inner->Handle.lnth );  // optimization required
     sout | y; // bye
 }