Trace-Based garbage collection

In this article, we discuss trace-based garbage collection, a type of garbage collection whereby garbage is collected at intervals triggered by conditions during program execution.

Table of contents.

1. Introduction.
2. Mark-and-sweep algorithm.
3. Baker's mark-and-sweep algorithm.
4. Mark-and-compact algorithm.
5. Cheney's copying collectors algorithm.
6. Summary.
7. References.

Prerequisite.

Heap management

Introduction.

Garbage collection involves collecting garbage as it is being created, trace-based collection involves periodically collecting garbage.
Trace-based collectors will run at intervals to find unreachable objects(garbage) and reclaim their space.
These intervals run whenever the free space goes below a set threshold or it is depleted.
We shall first discuss mark-and-sweep garbage collection algorithm then transition into trace-based collection algorithms.

Mark-and-sweep algorithm.

Mark-and-sweep algorithm works by finding unreachable objects and places them in the list of free space.

An example
As input we have a root set of objects, a heap and a free list(Free) with all unallocated chunks of the heap.
For output we expect a modified free list after all garbage has been removed.

The algorithm

//Marking
1. Add each object referenced by the root set to Unscanned and set its reached-bit to 1;
2. while(Unscanned != empty set){
3.     remove some object o from Unscanned;
4.     for(each object o' referenced in o){
5.         if(o' is unreached; i.e, reached-bit is 0){
6              set the reached-bit of o' to 1;
7.             place o' in Unscanned;
        }
    }

//Sweeping
8. Free = empty set;
9. for(each chunk of memory o in heap){
10.    if(o is unreached, i.e, its reached-bit is 0) add o to Free;
11.    else set reached-bit of o to 0;
}

List Free will hold objects unknown to be free.
UnscannedList is initially empty, It will hold objects considered reached, but whose successors have not yet been considered i.e, their successors have not been scanned so as to see which objects are reachable through them.
Each object includes a bit(reached-bit) to indicate whether it has been reached.

1. Line (1); Initialization of UnscannedList by placing all objects referenced by the root set. reached-bit for these objects is set to 1.
2. Line(2) - Line(7); looping while examining each object o ever placed in the UnscannedList.
3. Line(4) - Lines(7); for-loop implementing scanning of object o by examining o' for which we find reference within o. If o' has been reached(reached-bit of 1) nothing is done, otherwise we set its reached-bit to 1, Line(6) and add o' to UnscannedList Line(7).

Relationship among objects during marking phase.

The above shows an UnscannedList with four objects, the first corresponding to object o.
The dashed lines correspond to the three kind of objects reachable from o.

• A previously scanned object.
• An object in the UnscannedList
• An item reachable that was previously thought unreachable.

4. Line(8) - Line(11); the sweeping phase reclaims space of all remaining unreached by the end of marking. This includes objects on the free list. Since the unreached objects set cannot be enumerated directly, the algorithm sweeps through the entire heap.
5. Line(10); placing free and unreached objects on the free list one-by-one.
6. Line(11); set reachable objects reached-bits to 0 to maintain proper preconditions for next execution of garbage collection.

Baker's mark-and-sweep algorithm.

The sweeping phase in the mark-and-sweep algorithm is expensive since there is no easy way to find unreachable objects without having to examine the whole heap.
We optimize this by keeping a list of allocated objects and therefore to find the set of unreachable objects, we take the difference of the allocated objects and reached objects.

Baker's mark-and-sweep algorithm
The inputs and expected outputs are the same as in the previous algorithm.

The algorithm

//Marking
1. Scanned = Unscanned = empty set;
2. move objects referenced by root set from Unreached to Unscanned
3. while(Unscanned != empty set){
4.     move some object o from Unscanned to Scanned;
5.     for(each object o' referenced in o){
6.         if(o' is Unreached; i.e, reached-bit is 0){
7.             move o' from Unreached to Unscanned;
        }
    }
}

//Sweeping
8. Free = Free U(union) Unreached;
9. Unreached = Scanned;

We use four lists, Free, Unreached, Unscanned and Scanned each holding objects in a state of the same name.
Line(1) and (2) initializes Scanned to an empty list and Unscanned to contain objects reached from the root set.
Line(3) - Line(7); is an implementation of the basic marking algorithm whereby in Line(5) - Line(7) we use a for-loop to examine references on one unscanned object o, if any of o' s references have not yet been reached.
Line(7) changes o' to the Unscanned state
Line(8); we take objects in the Unreached list and deallocate their chunks by moving them into the Free list.
Line(9); takes objects in Scanned state and resets them to Unreached.
It is advantageous to combine adjacent free chunks into larger chunks as discussed in the prerequisite article, in this case, every time we return a chunk to the free list at line(8) of baker's algorithm or (10) of the basic algorithm, we examine the chunks(left and right) then merge if one is free.

Mark-and-compact algorithm.

Relocating collectors move reachable objects around the heap in order to eliminate memory fragmentation.
Usually space occupied by a reachable object is smaller than the freed space and therefore after identifying holes instead of freeing them individually, we can relocate all reachable objects into one end of the heap leaving the entire heap as one free chunk.
At this point the garbage collector has already analyzed every reference within the reachable objects and updating them to point to new locations is not alot of work.
This reduces fragmentation and memory is able to store large objects, also since data occupies a few cache lines and pages, relocation improves a program's spatial and temporal locality since newly created objects at the same time are allocated to nearby chunks.

Prefetching is an added benefit for nearby chunks.
The data structure for maintaining free space is simplified since instead of a free list, we just need a pointer free at the beginning of the one free block.

Mark-and-compact algorithm.

The algorithm has the following three phases.

1. Marking similar to that of mark-and-sweep.
2. In the second phase, the algorithm scans allocated section of the heap and computes a new address for each of the reachable objects which are assigned from the low end of the head so that there are no holes between reachable objects. These addresses are recorded in a NewLocation structure.
3. Copying objects are copied to their new locations and their references are updated to point to their corresponding new locations whose addresses are found in the NewLocation structure.

Algorithm
The inputs and expected outputs are the same as before.

// marking.
1. Unscanned = set of objects referenced by root set;
2. while(Unscanned != empty set){
3.     remove object o from Unscanned;
4.     for(each object o' referenced in o){
5.         if(o' is unreached){
6.             mark o' as reached;
7.             put o' on list Unscanned;
           }
       }
   }
// compute new locations
8. free = starting location of heap storage.
9. for(each chunk o in heap, from low end){
10.     if(i is reached){
11.         newLocation(o) = free;
12.         free = free + sizeof(o);
       }
    }
// retarget references and move reached objects
13. for(each chunk o in heap, from low end){
14.     if(o is reached){
15.         for(each reference o.r in o)
16.             o.r = NewLocation(o.r);
17.         copy o to NewLocation(o);
        }
    }
18. for(each reference r in root set)
19.     r = NewLocation(r);

Line(1) - Line(7) is similar to the first algorithm.
Line(8) - Line(12) represents the second phase. It visits each chunk and as a result chunks are assigned new addresses that increase in the same order as their old addresses.
Line(13) - Line(17) represent the third phase where we visit reached objects and replace internal pointers of a reached object o by the proper values using the NewLocation table(Line(15) and (16)).
Line(17) we move object o with the revised internal references to its new location.
Line(18) and (19) retargets pointers in the elements of the root set which are not themselves heap objects.

Data structures used include;

1. UnscannedList.
2. Reached bits in all objects(reached and unreached).
3. The free pointer marking the beginning of an unallocated space in the heap.
4. The table New Location (hash table, search tree) to implement setting new location(NewLocation(o)) and getting value of NewLocation(o) given an object o both at O(1) time.

Cheney's copying collector algorithm.

A copying collector reserves ahead of time space, to which objects can move and therefore breaks dependency between tracing and finding free space.
Memory is partitioned into two semi-spaces A, B.
The mutator allocates memory in one semi-space, e.g A, until it fills up then stops and then the garbage collector copies the reachable objects to the other space e.g B, after which the roles of the two semi-spaces are reversed.
The mutator is then allowed to resume and allocate objects in space B, in the next cycle of garbage collection, reachable objects are moved to space A.

Algorithm
The input is a root set of objects and a heap constituting of From semi-space containing allocated objects and the To semi-space which is free.
The output expected is the semi-space holding allocated objects, a free pointer indicating the start of the free space remaining in the To semi-space and the From space completely free.

1. CopyingCollector(){
2.     for(all objects o in From Space) NewLocation(o) = NULL;
3.     unscanned = free = starting address of To space;
4.     for(each reference r in the root set)
5.         replace r with LookupNewLocation(r);
6.     while(unscanned != Free){
7.         o = object at location unscanned;
8.         for(each reference o.r within o)
9.             or = LookupNewLocation(o.r);
10.         unscanned = unscanned + sizeof(o);
        }
    }
// Look up the new location if it has moved
// Place object in Unscanned state if not moved
11. LookupNewLocation(o){
12.     if(NewLocation(o) == NULL){
13.         NewLocation(o) = Free;
14.         free = free + sizeof(o);
15.         copy o to NewLocation(o);
        }
16.     return NewLocation(o);
    }

Line(2) makes sure none of objects in the From space have new addresses.
Line(3) initializes two pointers unscanned and free to the beginning of To semi-space.
Line(4) and Line(5) handle objects reached from the root set.
Line(6) - Line(10) are arrived at the first time it is reached unless there are no referenced objects by the root set in which case the entire heap is garbage.
Line(7) takes the unscanned object o and at Line(8) and Line(9) each reference within o is translated from its value in the From semi-space to the To semi-space.
Line(9) creates space for the object in the To space and moves it there.
Line(10) increments unscanned to point to next object beyond o in the To space.
Line(11) - Line(16); The function takes an object o and finds a new location for it in the To space if it has no location there yet, this new location is recorded in the NewLocation table and a NULL value indicates that o doesn't have an assigned location.
Line(12) if it doesn't have a location it is assigned at the beginning of the free space within To space semi-space(Line(13)).
Line(14) increments the free pointer by the amount of space occupied by o.
Line(15) we copy o from the From space to the To space, copying occurs as a side-effect.
Line(16) will return the location of o in the To space regardless of whether o's location was previously established or not.

An advantage with this algorithm is that is doesn't touch any unreachable objects, however, a copying garbage collector moves contents of all reachable objects and this is expensive when we are dealing with large objects which survive multiple cycles.

Summary.

A mark-and-compact collector compacts objects in place.
The copying collector moves objects from one region to another thereby reserving extra space for relocation, this allows reachable objects to be moved as they are discovered.

• Basic mark-and-sweep's algorithm complexity is proportional to the number of heap chunks.
• Baker's mark-and-sweep algorithm complexity is proportional to the number of reached objects.
• Basic mark-and-compact algorithm complexity is proportional to the number of chunks in the heap plus the total size of reached objects.
• Cheney's copying collector's algorithm complexity is proportional to the size of reached objects.

References.

1. Compilers, principles, techniques and tools, 2nd edition Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman.
2. Garbage collection notes