Changes between Initial Version and Version 1 of CheneysCopyingCollector

Show
Ignore:
Timestamp:
01/03/10 11:35:45 (5 years ago)
Author:
mikehh
Comment:

Initial version of Cheney's Copying Collector (to be expanded)

Legend:

Unmodified
Added
Removed
Modified
  • CheneysCopyingCollector

    v1 v1  
     1'''Cheney's Copying Collector''' 
     2 
     3The Fenichel-Yochelson collector given in the [wiki:CopyingGarbageCollector] 
     4page has the disadvantage of using a recursive copying algorithm.  Since 
     5Cheney's discovery of an efficient iterative technique for its implementation 
     6copying collection has proved popular with implementors.  Although garbage 
     7collection technology has moved beyond simple stop-and-copy collection, this 
     8technique remains the most widely adopted basis for more sophisticated 
     9techniques, such as generational and incremental collectors. 
     10 
     11 
     12Cheney's algorithm: 
     13{{{ 
     14flip() = 
     15    Fromspace, Tospace = Tospace, Fromspace 
     16    top_of_space = Tospace + space_size 
     17    scan = free = Tospace 
     18 
     19    for R in roots 
     20        R = copy(R) 
     21 
     22    while scan < free 
     23        for P in Children(scan) 
     24            *P = copy(*P) 
     25        scan = scan + size (scan) 
     26 
     27copy(P) = 
     28    if forwarded(P) 
     29        return forwarding_address(P) 
     30    else 
     31        addr = free 
     32        move(P,free) 
     33        free = free + size(P) 
     34        forwarding_address(P) = addr 
     35        return addr 
     36 
     37}}} 
     38 
     39 
     40extracted from:[[BR]] 
     41Garbage Collection: Algorithms for Automatic Dynamic Memory Management[[BR]] 
     42by Richard Jones and Rafael Sims[[BR]] 
     43[http://www.cs.kent.ac.uk/people/staff/rej/gc.html]