description | simple coopertive garbage collector |
homepage URL | http://www.pipapo.org/pipawiki/Acogc |
repository URL | git://git.pipapo.org/acogc |
owner | ct@pipapo.org |
last change | Mon, 30 Jul 2007 16:56:42 +0000 (30 18:56 +0200) |
last refresh | Mon, 23 Sep 2024 20:32:51 +0000 (23 22:32 +0200) |
mirror URL | git://repo.or.cz/acogc.git |
| https://repo.or.cz/acogc.git |
| ssh://git@repo.or.cz/acogc.git |
bundle info | acogc.git downloadable bundles |
content tags
|
|
README
Acogc (accurate cooperative garbage collector) is the garbage collector used for the MaLa extension langauge.
Features:
* simple optimized mark is sweep (stop© without copying)
* can coexist with other allocation strategies, implemented on top of malloc/free
* main goal is beeing small and embeddable, not performance
* accurate collection (not conservative), might ideally lead
to better performance (not proofed) but does never keep garbagge around
* cooperative, the user has to supply custom marker functions for his objects
* NOT intrusive the GC descriptor is opaqe, it's blocks are before the user data
* swept objects are not destroyed and pooled in free-queue and for faster reallocation,
real freeing is done on utilization policies.
* supports weak references
* weak references to swept but not yet freed objects can be reinstantiated
for efficent caching strategies
* non-collectable objects can coexist with garbage collected objects
* collects statistics and let the GC tune itself dynamically
* Proactive collection, the user can provide callback functions which invalidate
referenced objects at collect time if they are not useful anymore
Algorithm:
Marking is Sweeping or Stop&Copy without copying
marking moves objects to a live objects list,
dead objects are left in a freelist so we don't need an explicit
sweep cycle and the algorithm runs in O(LifeObjects) instead in O(AllObjects)
Cells:
* all cells are kept in double linked lists.
* we use a monotonic incrementing counter as mark value (with some values reserved at the beginning for special marks)
Global:
* we have a list for root objects
* a list of live objects
* a list of free objects
* a global mark counter
Allocation:
* if there is a object in the freelist then move it to the live list
* if not malloc() a new object and/or do a collection
Collection:
* Increment the global mark counter value
* resnap all objects of the live list to a temporary list
* for all root objects mark their referenced objects recursively, by setting their mark to the new counter value and moving them to the live list.
* when finished all remaining objects in the temporary are free and append them to the freelist.
Caution:
* we need to reset all marks in all objects before the counter overflows and then reinitialize the counter
Future:
* implement block pooling which keeps some objects in biggier blocks
* since we have this counting mark we can easily extend the scheme to a generational algorithm