descriptionsimple coopertive garbage collector
homepage URLhttp://www.pipapo.org/pipawiki/Acogc
repository URLgit://git.pipapo.org/acogc
ownerct@pipapo.org
last changeMon, 30 Jul 2007 16:56:42 +0000 (30 18:56 +0200)
last refreshThu, 25 Apr 2024 08:02:06 +0000 (25 10:02 +0200)
content tags
add:
README
Acogc (accurate cooperative garbage collector) is the garbage collector used for the MaLa extension langauge.

Features:
    * simple optimized mark is sweep (stop&copy 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
shortlog
2007-07-30 Christian Thaeterupdate for compatibility with recent nobugmaster
2007-02-20 Christian Thaeterfix for new nobugmaster_signature
2007-02-15 Christian Thaeternobug levels on configure
2007-02-15 Christian Thaeteradd typecheck by string literal
2007-02-02 Christian Thaeterbuild system enhancements, add --enable-nobug=LEVEL...
2007-01-17 Christian Thaeteradded nobug check for stack corruptionrelease0.1release0.1_signature
2007-01-17 Christian Thaeteradded more nobug instrumentation
2007-01-09 Christian Thaeternew collection policy again, much better nowexperimental_signature
2007-01-08 Christian Thaeternew collection policy
2007-01-07 Christian Thaeterweakref fix
2007-01-06 Christian Thaeterdebug improvement
2007-01-06 Christian Thaetertest improvement
2007-01-06 Christian Thaetermaintaince/config changes
2006-12-20 Christian Thaeterrevert to allowing NULL in alloc/reallocsignature
2006-12-20 Christian Thaeteradded REQUIRE checks
2006-12-20 Christian Thaeterless spooky mark logging
...
tags
17 years ago master_signature automatic generated on last commit
17 years ago release0.1_signature automatic generated on last commit
17 years ago experimental_signature automatic generated on last commit
17 years ago signature automatic generated on last commit
heads
12 years ago devel
13 years ago new_brainstorm_devel
16 years ago master
17 years ago release0.1
17 years ago experimental