Changeset 7b0e8b7

Timestamp:

Oct 18, 2021, 4:31:04 PM (3 years ago)

Author:

Michael Brooks <mlbrooks@…>

Branches:

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

Children:

6f7aff3

Parents:

804bf677

Message:

String heap growth implemented

Files:

• libcfa/src/containers/string_res.cfa (modified) (9 diffs)
• libcfa/src/containers/string_res.hfa (modified) (1 diff)
• tests/collections/.expect/string-ctx-manage.txt (modified) (1 diff)
• tests/collections/.expect/string-gc.txt (modified) (1 diff)
• tests/collections/string-ctx-manage.cfa (modified) (1 diff)
• tests/collections/string-gc.cfa (modified) (1 diff)

libcfa/src/containers/string_res.cfa

@@ -44 +44 @@
     
 static inline void compaction( VbyteHeap & );                           // compaction of the byte area
-static inline void garbage( VbyteHeap & );                              // garbage collect the byte area
+static inline void garbage( VbyteHeap &, int );                         // garbage collect the byte area
 static inline void extend( VbyteHeap &, int );                  // extend the size of the byte area
 static inline void reduce( VbyteHeap &, int );                  // reduce the size of the byte area
@@ -179 +179 @@
 }
 
+size_t DEBUG_string_bytes_in_heap( VbyteHeap * heap ) {
+    return heap->CurrSize;
+}
+
 const char * DEBUG_string_heap_start( VbyteHeap * heap ) {
     return heap->StartVbyte;
 }
-
 
 // Returns the size of the string in bytes
@@ -759 +762 @@
     NoBytes = ( uintptr_t )EndVbyte + size;
     if ( NoBytes > ( uintptr_t )ExtVbyte ) {            // enough room for new byte-string ?
-                garbage( this );                                        // firer up the garbage collector
+                garbage( this, size );                                  // firer up the garbage collector
                 NoBytes = ( uintptr_t )EndVbyte + size;         // try again
                 if ( NoBytes > ( uintptr_t )ExtVbyte ) {        // enough room for new byte-string ?
-// unimplemented feature - assert, not verify
-assert( 0 && "need to implement actual growth" );
-                        // extend( size );                              // extend the byte-string area
+            assert( 0 && "garbage run did not free up required space" );
                 } // if
     } // if
@@ -925 +926 @@
 // the heap.  The heap is then compacted in the existing heap or into the newly allocated heap.
 
-void garbage(VbyteHeap & this ) with(this) {
+void garbage(VbyteHeap & this, int minreq ) with(this) {
 #ifdef VbyteDebug
     serr | "enter:garbage";
@@ -949 +950 @@
     AmountFree = ( uintptr_t )ExtVbyte - ( uintptr_t )StartVbyte - AmountUsed;
     
-    if ( AmountFree < ( int )( CurrSize * 0.1 )) {      // free space less than 10% ?
-
-// unimplemented feature - assert, not verify
-assert( 0 && "need to implement actual growth" );
-//              extend( CurrSize );                             // extend the heap
+    if ( ( double ) AmountFree < ( CurrSize * 0.1 ) || AmountFree < minreq ) {  // free space less than 10%  or not enough to serve cur request
+
+                extend( this, max( CurrSize, minreq ) );                                // extend the heap
 
                         //  Peter says, "This needs work before it should be used."
@@ -980 +979 @@
 #undef VbyteDebug
 
-//WIP
-#if 0
 
 
@@ -987 +984 @@
 // area is deleted.
 
-void VbyteHeap::extend( int size ) {
+void extend( VbyteHeap & this, int size ) with (this) {
 #ifdef VbyteDebug
     serr | "enter:extend, size:" | size;
@@ -997 +994 @@
     
     CurrSize += size > InitSize ? size : InitSize;      // minimum extension, initial size
-    StartVbyte = EndVbyte = new char[CurrSize];
+    StartVbyte = EndVbyte = alloc(CurrSize);
     ExtVbyte = (void *)( StartVbyte + CurrSize );
-    compaction();                                       // copy from old heap to new & adjust pointers to new heap
-    delete OldStartVbyte;                               // release old heap
+    compaction(this);                                   // copy from old heap to new & adjust pointers to new heap
+    free( OldStartVbyte );                              // release old heap
 #ifdef VbyteDebug
     serr | "exit:extend, CurrSize:" | CurrSize;
@@ -1006 +1003 @@
 } // extend
 
+//WIP
+#if 0
 
 // Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string

libcfa/src/containers/string_res.hfa

@@ -34 +34 @@
 
 VbyteHeap * DEBUG_string_heap();
+size_t DEBUG_string_bytes_in_heap( VbyteHeap * heap );
 size_t DEBUG_string_bytes_avail_until_gc( VbyteHeap * heap );
 const char * DEBUG_string_heap_start( VbyteHeap * heap );

tests/collections/.expect/string-ctx-manage.txt

@@ -4 +4 @@
 bye
 hi
+bye
 done

tests/collections/.expect/string-gc.txt

@@ -38 +38 @@
 x from 5 to 15
 y from 5 to 15
+======================== fillNoCompact
+about to expand, a = aaa
+expanded, a = aaa
+about to expand, a = aaa
+expanded, a = aaa
+about to expand, a = aaa
+expanded, a = aaa
+about to expand, a = aaa
+expanded, a = aaa
+about to expand, a = aaa
+expanded, a = aaa

tests/collections/string-ctx-manage.cfa

@@ -36 +36 @@
     string y = x; // y allocates into private pad, implying eager copy
     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
 
-    // -- following hits "need to implement actual growth"
-    //    and it passes if I modify string_res.cfa to oversize the owned heaps
-
-    // x = "bye";
-    // y = x; // into private y => eager copy
-    // assert( y.inner->Handle.s != x.inner->Handle.s);
-    // sout | y; // bye
+    x = "bye";
+    y = x; // into private y => eager copy
+    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
 }
 

tests/collections/string-gc.cfa

@@ -120 +120 @@
 }
 
+void fillNoCompact() {
+    // show that allocating in a heap filled with mostly live strings (no collectable garbage) causes heap growth
+
+    sout | "======================== fillNoCompact";
+
+    size_t lastTimeBytesAvail = bytesRemaining();
+    assert( lastTimeBytesAvail >= 200 ); // starting this test with nontrivial room
+
+    // mostly fill the pad
+    string_res a = "aaa";  // will have to be moved
+    string_res z = "zzz";
+    for (i; 5) {
+        while ( bytesRemaining() > 10 ) {
+            z += ".";
+        }
+        sout | "about to expand, a = " | a;
+        while ( bytesRemaining() <= 10 ) {
+            z += ".";
+        }
+        sout | "expanded, a = " | a;
+
+        // each growth gives more usable space than the last
+        assert( bytesRemaining() > lastTimeBytesAvail );
+        lastTimeBytesAvail = bytesRemaining();
+    }
+}
+
 int main() {
     basicFillCompact();
     fillCompact_withSharedEdits();
+    fillNoCompact();
 }