Changeset 6f7aff3


Ignore:
Timestamp:
Oct 19, 2021, 10:31:53 AM (2 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:
3 edited

Legend:

Unmodified
Added
Removed
  • libcfa/src/containers/string_res.cfa

    r7b0e8b7 r6f7aff3  
    5353static inline int ByteCmp( char *, int, int, char *, int, int );        // compare 2 blocks of bytes
    5454static inline char *VbyteAlloc( VbyteHeap &, int );                     // allocate a block bytes in the heap
    55 
     55static inline char *VbyteTryAdjustLast( VbyteHeap &, int );
    5656
    5757static inline void AddThisAfter( HandleNode &, HandleNode & );
     
    313313    this.Handle.s = resultSesStart + beforeLen;
    314314    this.Handle.lnth = bsize;
    315     MoveThisAfter( this.Handle, *resultPadPosition );
     315    if (resultPadPosition)
     316        MoveThisAfter( this.Handle, *resultPadPosition );
    316317
    317318    // adjust all substring string and handle locations, and check if any substring strings are outside the new base string
     
    365366            }
    366367        }
    367         MoveThisAfter( p->Handle, *resultPadPosition ); // move substring handle to maintain sorted order by string position
     368        if (resultPadPosition)
     369            MoveThisAfter( p->Handle, *resultPadPosition );     // move substring handle to maintain sorted order by string position
    368370    }
    369371}
     
    387389    verify( editSetLength >= this.Handle.lnth );
    388390
    389 
    390     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
    391         && & valSrc                                       // sourcing from a managed string
    392         && valSrc.Handle.ulink == this.Handle.ulink  ) {  // sourcing from same heap
    393 
     391    if ( this.shareEditSet_owns_ulink ) {                 // assigning to private context
     392        // ok to overwrite old value within LHS
     393        char * prefixStartOrig = shareEditSetStartPeer->Handle.s;
     394        int prefixLen = this.Handle.s - prefixStartOrig;
     395        char * suffixStartOrig = this.Handle.s + this.Handle.lnth;
     396        int suffixLen = shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - suffixStartOrig;
     397
     398        int delta = bsize - this.Handle.lnth;
     399        if ( char * oldBytes = VbyteTryAdjustLast( *this.Handle.ulink, delta ) ) {
     400            // growing: copy from old to new
     401            char * dest = VbyteAlloc( *this.Handle.ulink, editSetLength );
     402            char *destCursor = dest;        memcpy(destCursor, prefixStartOrig, prefixLen);
     403            destCursor += prefixLen;        memcpy(destCursor, buffer         , bsize    );
     404            destCursor += this.Handle.lnth; memcpy(destCursor, suffixStartOrig, suffixLen);
     405            assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer,
     406                dest,
     407                editSetLength,
     408                0p, bsize);
     409            free( oldBytes );
     410        } else {
     411            // room is already allocated in-place: bubble suffix and overwite middle
     412            memmove( suffixStartOrig + delta, suffixStartOrig, suffixLen );
     413            memcpy( this.Handle.s, buffer, bsize );
     414
     415            assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer,
     416                shareEditSetStartPeer->Handle.s,
     417                editSetLength,
     418                0p, bsize);
     419        }
     420
     421    } else if (                                           // assigning to shared context
     422        this.Handle.lnth == editSetLength &&              // overwriting entire run of SES
     423        & valSrc &&                                       // sourcing from a managed string
     424        valSrc.Handle.ulink == this.Handle.ulink  ) {     // sourcing from same heap
     425
     426        // SES's result will only use characters from the source string => reuse source
    394427        assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer,
    395428            valSrc.Handle.s,
     
    398431       
    399432    } else {
     433        // overwriting a proper substring of some string: mash characters from old and new together (copy on write)
     434        // OR we are importing characters: need to copy eagerly (can't refer to source)
    400435
    401436        // full string is from start of shareEditSetStartPeer thru end of shareEditSetEndPeer
     
    416451        }
    417452
    418         // we are only overwriting a proper substring of some string: need to mash characters from old and new together
    419         // OR we are importing characters: need to copy eagerly
    420453        string_res pasting = {
    421454            * this.Handle.ulink,                               // maintain same heap, regardless of context
     
    439472            &pasting.Handle, bsize);
    440473    }
    441 
    442     // So now, capture their values for use in the overlap cases, below.
    443     // Do not factor these definitions with the arguments used in string building above.
    444 
    445474}
    446475
     
    750779
    751780// Allocates specified storage for a string from byte-string area. If not enough space remains to perform the
    752 // allocation, the garbage collection routine is called and a second attempt is made to allocate the space. If the
    753 // second attempt fails, a further attempt is made to create a new, larger byte-string area.
     781// allocation, the garbage collection routine is called.
    754782
    755783static inline char * VbyteAlloc( VbyteHeap & this, int size ) with(this) {
     
    775803    return r;
    776804} // VbyteAlloc
     805
     806
     807// Adjusts the last allocation in this heap by delta bytes, or resets this heap to be able to offer
     808// new allocations of its original size + delta bytes. Positive delta means bigger;
     809// negative means smaller.  A null return indicates that the original heap location has room for
     810// the requested growth.  A non-null return indicates that copying to a new location is required
     811// but has not been done; the returned value is the old heap storage location; `this` heap is
     812// modified to reference the new location.  In the copy-requred case, the caller should use
     813// VbyteAlloc to claim the new space, while doing optimal copying from old to new, then free old.
     814
     815static inline char * VbyteTryAdjustLast( VbyteHeap & this, int delta ) with(this) {
     816
     817    if ( ( uintptr_t )EndVbyte + delta <= ( uintptr_t )ExtVbyte ) {
     818        // room available
     819        EndVbyte += delta;
     820        return 0p;
     821    }
     822
     823    char *oldBytes = StartVbyte;
     824
     825    NoOfExtensions += 1;
     826    CurrSize *= 2;
     827    StartVbyte = EndVbyte = alloc(CurrSize);
     828    ExtVbyte = StartVbyte + CurrSize;
     829
     830    return oldBytes;
     831}
    777832
    778833
  • tests/collections/string-api-coverage.cfa

    r7b0e8b7 r6f7aff3  
    11#include <containers/string.hfa>
     2#include <string_sharectx.hfa>
    23
    34void assertWellFormedHandleList( int maxLen ) { // with(HeapArea)
     
    2526
    2627int main () {
     28
     29    #ifdef STRING_SHARING_OFF
     30    sout | "string sharing disabled";
     31    string_sharectx c = { NO_SHARING };
     32    #endif
     33
    2734    string s = "hello";
    2835    string s2 = "hello";
  • tests/collections/string-ctx-manage.cfa

    r7b0e8b7 r6f7aff3  
    33#include <string_res.hfa>
    44
     5// In these tests, shared heaps are never remotely full and string sizes are tiny.
     6// So here, the SUT should put a yes-sharing string in a heap with lots of spare room.
     7// The SUT should always keep a no-sharing string's buffer 1x--2x the string's size.
     8// This check uses 3x as a heuristic split between those cases.
     9void assertSpareRoomInHeap( string & s, bool expectOversized ) {
     10    double bytesInHeap = DEBUG_string_bytes_in_heap(s.inner->Handle.ulink);
     11    double bytesUsed =  s.inner->Handle.lnth;
     12    double overhead = bytesInHeap / bytesUsed;
     13    assert (overhead >= 1);
     14    if ( expectOversized )
     15        assert( overhead >= 3.0 );
     16    else
     17        assert( overhead < 3.0 );
     18}
     19
    520void baseline() {
    621    string x = "hi";
     22    assertSpareRoomInHeap( x, true );
    723
    824    string y = x; // construct y in same context, no write yet => no copy yet
     25    assertSpareRoomInHeap( y, true );
    926    assert( y.inner->Handle.s == x.inner->Handle.s);
    1027    sout | y; // hi
    1128
    1229    x = "bye";
     30    assertSpareRoomInHeap( x, true );
    1331    y = x; // y in same context, no write yet => no copy yet
     32    assertSpareRoomInHeap( y, true );
    1433    assert( y.inner->Handle.s == x.inner->Handle.s);
    1534    sout | y; // bye
     
    1837void eagerCopy() {
    1938    string x = "hi";
     39    assertSpareRoomInHeap( x, true );
    2040    string_sharectx c = { NEW_SHARING };
    2141
    2242    string y = x; // construct y in different context => eager copy
     43    assertSpareRoomInHeap( y, true );
    2344    assert( y.inner->Handle.s != x.inner->Handle.s);
    2445    sout | y; // hi
    2546
    2647    x = "bye";
     48    assertSpareRoomInHeap( x, true );
    2749    y = x; // y was already in different context => eager copy
     50    assertSpareRoomInHeap( y, true );
    2851    assert( y.inner->Handle.s != x.inner->Handle.s);
    2952    sout | y; // bye
     
    3255void soloAlloc() {
    3356    string x = "hi";
     57    assertSpareRoomInHeap( x, true );
    3458    string_sharectx c = { NO_SHARING };
    3559   
    3660    string y = x; // y allocates into private pad, implying eager copy
     61    assertSpareRoomInHeap( y, false );
    3762    assert( y.inner->Handle.s != x.inner->Handle.s);
    38     assert( DEBUG_string_bytes_in_heap(y.inner->Handle.ulink) == y.inner->Handle.lnth );  // y is in a perfectly fitting heap
    3963    sout | y; // hi
    4064
    4165    x = "bye";
     66    assertSpareRoomInHeap( x, true );
    4267    y = x; // into private y => eager copy
     68    assertSpareRoomInHeap( y, false );
    4369    assert( y.inner->Handle.s != x.inner->Handle.s);
    44 //    assert( DEBUG_string_bytes_in_heap(y.inner->Handle.ulink) == y.inner->Handle.lnth );  // optimization required
    4570    sout | y; // bye
    4671}
Note: See TracChangeset for help on using the changeset viewer.