December 04, 2020, 11:45:22 AM

Author Topic: [bb] Garbage collector for Blitz3D/+ by Yasha [ 1+ years ago ]  (Read 527 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
Title : Garbage collector for Blitz3D/+
Author : Yasha
Posted : 1+ years ago

Description : This code requires <a href="http://www.fastlibs.com/index.php" target="_blank">MikhailV's free FastPointer DLL[/url].
Garbage collection for B3D/+, or, "Unlocking what we already had"

Yes really. A "true" GC system for Blitz Classic! Fire and forget: you don't even need <a href="codearcs98f6.html?code=2978" target="_blank">autorelease pools[/url]!

The interesting part, and the reason why it is able to work seamlessly without any extra code on assignments, is that Blitz Classic already has an automatic reference counting system built right into it (it's required for the custom type system to be as simple as it is). All this little library does is use FastPointer to hack our way through to view the actual refcount as maintained by the Blitz runtime, and take appropriate action - i.e. call a destructor function pointer - when it runs out.
Now, although the business of refcounting is handled entirely automatically (by Blitz itself, no less!), there are some forms and limitations that must be observed. Let's start with an example:

Code: [Select]
Include "GC.bb"

Type Foo
Field a, b#, c$
End Type

Function NewFoo.Foo(a_, b_#, c_$)
Local f.Foo = New Foo
fa = a_ : f = b_ : fc = c_

Local freePtr = FunctionPointer() : Goto skip : FreeFoo f
.skip

GC_Track(TypePointer(f), freePtr)
DebugLog "Created new Foo at 0x" + Hex(TypePointer(f))
Return f
End Function

Function FreeFoo(this.Foo)
DebugLog "Ran FreeFoo on 0x" + Hex(TypePointer(this))
;...
Delete this
End Function


Graphics 800, 400, 32, 6
GC_Init
GC_SetAggressiveness 1 ;For the sake of the example, every allocation will trigger a collection

Local i : For i = 1 To 10
Local f.Foo = NewFoo(1, 2.0, "three")
Next

RuntimeStats


WaitKey
End


Run this code and you'll see the old values of f.Foo getting deleted as they get overwritten. Neat. (Example prints all output to the DebugLog.)
Now, there are two requirements, both demonstrated in the code above:

-- An object must still be manually registered as to be tracked by the GC system. You can see this in the constructor function: it's the call to GC_Track. This function accepts the TypePointer of the object (only use the FastPointer function TypePointer here), and the function pointer of its destructor. The function pointer must be valid.

-- There must be a destructor function, which will be called when the object is collected. This is passed to GC_Track as specified above, then forgotten about because the GC will decide when to call it.
...and there are two big limitations:

-- The global list for each type counts as a reference to an object in the Blitz runtime. This means the internal refcount will never reach zero (when using Blitz normally, calling Delete unhooks the object from the global list; it can reach zero after this). As a result, for the purposes of this GC engine, we consider the refcount depleted when it hits one. This means you cannot rely on being able to access objects through the global list, and should ideally structure your code not to use it for GC'd types.

-- The operator Handle takes an object and returns an integer. This integer is not tracked by the runtime (and even a conservative collector like Boehm would have a tough time trying). Therefore, if you try to store objects by Handle and don't keep any "real" typed pointers around to them, the objects will be collected in the meantime! To deal with this, use the GC_LockObject and GC_UnlockObject functions (which accept the TypePointer, like GC_Track): these will increment and decrement a secondary reference count within the GC system. As long as the secondary count is above zero, the object will not be collected.

Using GC_LockObject is basically just bringing back manual memory management though, so better to avoid it where possible.

Any slot that uses a "real" typed pointer is fine, however: local variables, globals, fields of other objects, and arrays; all of these are totally acceptable and will work properly with the system.

Finally, remember that refcounting GC systems are vulnerable to the "circular reference bug" found in BlitzMax: make sure two objects don't form a "loop" that keeps the reference count alive without actually being reachable from the program code (as with the lists issue, in normal usage Blitz can rely on the Delete operator to break cycles).
Two other functions of interest are GC_Init, which must be called before using the GC system to set up the internals; and GC_SetAggressiveness, which sets the number of objects that are Tracked before a collection kicks in (if this number is higher, fewer collections happen, which is better for performance at the expense of memory use). Aggressiveness is set to 1 in the example so a collection happens at every opportunity (aggressiveness of 0 results in no collections). There are also GC_Suspend and GC_Resume, which let you pause the GC during times when you don't want it causing delays; and GC_CollectNow, which forces a collection immediately (if you find yourself calling this, you're probably doing something wrong as it misses the point of having a GC entirely).
By the way, if you're wondering why there are two objects surviving at the end of the example, it's because the old occupant of f.Foo doesn't get its refcount decremented until after the new object returns, which for the last one is after the last possible collection. A collection happening later would clean up this waiting object: it's not going to be a problem for the most part as if there are no further collections, it's because you weren't going to use that space.
The restriction of having to manually manage the interaction with Object and Handle may seem like a nuisance to anyone using heavily-polymorphic code, but you can actually get around it relatively easily by having all your poly-objects <a href="../Community/posts0e3c-2.html?topic=99258#1164466" target="_blank">use pseudo-inheritance to descend from one root type[/url]; use this type instead of Int as the unit of storage in lists and the like, and have the root type's destructor clean up the rest of the object when it's collected. Takes a bit of work, but it should be doable. Keep it up for long enough and you end up with BlitzMax (protip: if you really care about any of this stuff... use BlitzMax). [/i]

Code :
Code: BlitzBasic
  1. ; Garbage collection for Blitz3D/+
  2. ;==================================
  3.  
  4. ; Requires FastPointer DLL (free): http://www.fastlibs.com/index.php
  5.  
  6. Const GC_REFCOUNT_OFFSET = -4, GC_OPTR_OFFSET = -20, GC_CELLSIZE = 12, GC_PTR_OFS = 0, GC_LC_OFS = 4, GC_DTOR_OFS = 8
  7. Const GC_SHRINK_THRESH = 25, GC_LISTSIZE = 128 * GC_CELLSIZE, GC_DEFAULT_AGGRO = 25
  8. Global GC_private_Aggro_, GC_private_ACount_, GC_private_ObjList_, GC_private_ListTop_, GC_private_Active_
  9.  
  10.  
  11. ; Initialize the garbage collector system
  12. Function GC_Init()
  13.         If GC_private_ObjList_ Then RuntimeError "GC already initialized!"
  14.         GC_private_ObjList_ = CreateBank(GC_LISTSIZE * GC_CELLSIZE)
  15.         GC_private_ListTop_ = 0
  16.         GC_private_Aggro_ = GC_DEFAULT_AGGRO
  17.         GC_private_Active_ = True
  18. End Function
  19.  
  20. ; Set an object to be tracked by the collector. This may trigger a GC run
  21. Function GC_Track(ptr, dtor)
  22.         If Not GC_private_ObjList_ Then RuntimeError "GC not initialized!"
  23.         If Not dtor Then RuntimeError "Destructor function must not be null!"
  24.        
  25.         PokeInt GC_private_ObjList_, GC_private_ListTop_ + GC_PTR_OFS, ptr
  26.         PokeInt GC_private_ObjList_, GC_private_ListTop_ + GC_DTOR_OFS, dtor
  27.         PokeInt GC_private_ObjList_, GC_private_ListTop_ + GC_LC_OFS, 0
  28.        
  29.         GC_private_ListTop_ = GC_private_ListTop_ + GC_CELLSIZE         ;Extend the list if necessary
  30.         If GC_private_ListTop_ >= BankSize(GC_private_ObjList_) Then ResizeBank GC_private_ObjList_, GC_private_ListTop_ * 2
  31.        
  32.         GC_private_ACount_ = GC_private_ACount_ + 1
  33.         If GC_private_Active_
  34.                 If GC_private_ACount_ >= GC_private_Aggro_ And GC_private_Aggro_ > 0 Then GC_CollectNow
  35.         EndIf
  36. End Function
  37.  
  38. ; Set the number of objects allowed to be created between GC runs
  39. Function GC_SetAggressiveness(aggro)
  40.         If Not GC_private_ObjList_ Then RuntimeError "GC not initialized!"
  41.         GC_private_Aggro_ = aggro
  42. End Function
  43.  
  44. ; Force a GC run: called automatically for the most part
  45. Function GC_CollectNow()
  46.         If GC_private_Active_
  47.                
  48.                 Local o : For o = GC_private_ListTop_ - GC_CELLSIZE To 0 Step -GC_CELLSIZE      ;Start with most recent
  49.                         If PeekInt(GC_private_ObjList_, o + GC_LC_OFS) < 1
  50.                                 Local rc = MemoryFastPeekInt(PeekInt(GC_private_ObjList_, o + GC_PTR_OFS) + GC_REFCOUNT_OFFSET)
  51.                                 If rc < 2
  52.                                         If rc = 1       ;Only the type list: collect
  53.                                                 Local dtor = PeekInt(GC_private_ObjList_, o + GC_DTOR_OFS)
  54.                                                 CallFunctionVarInt dtor, PeekInt(GC_private_ObjList_, o + GC_PTR_OFS) + GC_OPTR_OFFSET
  55.                                         EndIf           ;Could also have been deleted earlier, in which case just remove
  56.                                         GC_private_ListTop_ = GC_private_ListTop_ - GC_CELLSIZE
  57.                                         If GC_private_ListTop_ >= 0
  58.                                                 CopyBank GC_private_ObjList_, GC_private_ListTop_, GC_private_ObjList_, o, GC_CELLSIZE
  59.                                         EndIf
  60.                                 EndIf
  61.                         EndIf
  62.                 Next
  63.                
  64.                 Local sz = BankSize(GC_private_ObjList_)        ;Shrink the list if it's largely empty
  65.                 If sz > GC_LISTSIZE * GC_CELLSIZE
  66.                         If (GC_private_ListTop_ * 100) / sz < GC_SHRINK_THRESH Then ResizeBank GC_private_ObjList_, sz / 2
  67.                 EndIf
  68.                
  69.                 GC_private_ACount_ = 0
  70.         EndIf
  71. End Function
  72.  
  73. ; Pause garbage collection until GC_Resume is called
  74. Function GC_Suspend()
  75.         If Not GC_private_ObjList_ Then RuntimeError "GC not initialized!"
  76.         GC_private_Active_ = False
  77. End Function
  78.  
  79. ; Resume garbage collection
  80. Function GC_Resume()
  81.         If Not GC_private_ObjList_ Then RuntimeError "GC not initialized!"
  82.         GC_private_Active_ = True
  83.         If GC_private_ACount_ >= GC_private_Aggro_ And GC_private_Aggro_ > 0 Then GC_CollectNow
  84. End Function
  85.  
  86. ; Increment the lock count of an object, protecting it from GC
  87. Function GC_LockObject(ptr)
  88.         Local o = GC_GetOffset_(ptr) : If o >= 0
  89.                 PokeInt GC_private_ObjList_, o + GC_LC_OFS, PeekInt(GC_private_ObjList_, o + GC_LC_OFS) + 1
  90.         Else
  91.                 RuntimeError "Invalid object pointer for GC to lock: 0x" + Hex(ptr)
  92.         EndIf
  93. End Function
  94.  
  95. ; Decrement the lock count of an object, potentially relinquishing it for GC
  96. Function GC_UnlockObject(ptr)
  97.         Local o = GC_GetOffset_(ptr) : If o >= 0
  98.                 PokeInt GC_private_ObjList_, o + GC_LC_OFS, PeekInt(GC_private_ObjList_, o + GC_LC_OFS) - 1
  99.         Else
  100.                 RuntimeError "Invalid object pointer for GC to unlock: 0x" + Hex(ptr)
  101.         EndIf
  102. End Function
  103.  
  104. ; (Internal) Get the position in the object list of the given pointer
  105. Function GC_GetOffset_(ptr)
  106.         Local o : For o = GC_private_ListTop_ - GC_CELLSIZE To 0 Step -GC_CELLSIZE
  107.                 If PeekInt(GC_private_ObjList_, o) = ptr Then Return o
  108.         Next
  109.         Return -1
  110. End Function
  111.  
  112.  
  113. ;~IDEal Editor Parameters:
  114. ;~C#Blitz3D


Comments : none...

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal