Introduction to Trace-Based
Collection
Acknowledgement
• Alfred V Aho, Monica S. Lam, Ravi Sethi, Jeffrey D Ullman-
“Compilers- Principles, Techniques and Tools”
Dr. Girish Kumar Patnaik 2
Introduction
• Trace-based collectors run periodically to find
unreachable objects and reclaim their space
• whenever the free space is exhausted or its
amount drops below some threshold
Dr. Girish Kumar Patnaik 3
A Basic Mark-and-Sweep Collector
• List Free holds objects known to be free
• A list called Unscanned, holds objects that we
have determined are reached, but whose
successors we have not yet considered.
• The Unscanned list is empty initially
• Each object includes a bit to indicate whether it
has been reached (the reached- bit)
Dr. Girish Kumar Patnaik 4
A Basic Mark-and-Sweep Collector
• Initialize the Unscanned list by placing there all
the objects referenced by the root set.
• reached-bit for these objects is also set to 1.
• For each object o in the Unscanned list, Examine
each object o' for which we find a reference
within o.
– If o’ is unreached, set the reached- bit of o’ to 1 and
add to Unscanned list
Dr. Girish Kumar Patnaik 5
A Basic Mark-and-Sweep Collector
• In the sweeping phase, if memory o is
unreached
– then add o to Free list
– else set their reached-bit to ZERO, in order to
maintain the proper preconditions for the next
execution of the garbage-collection algorithm
Dr. Girish Kumar Patnaik 6
A Basic Mark-
and-Sweep
Collector
Dr. Girish Kumar Patnaik 7
Basic
Abstraction
Dr. Girish Kumar Patnaik 8
Optimizing Mark-and-Sweep
• Four lists named Free, Unreached, Unscanned,
and Scanned
• A reached-bit in objects is not used
• Each object contains bits telling which of the four
states it is in
• Initially, Free is the free list maintained by the
memory manager, and all allocated objects are
on the Unreached list
Dr. Girish Kumar Patnaik 9
Optimizing Mark-and-Sweep
Dr. Girish Kumar Patnaik 10
Mark-and-Compact Garbage Collectors
• Relocating collectors move reachable objects around in the heap
to eliminate memory fragmentation.
• A mark-and-compact collector compacts objects in place.
Relocating in place reduces memory usage.
• The algorithm scans the allocated section of the heap and
computes a new address for each of the reachable objects.
• The algorithm copies objects to their new locations, updating all
references in the objects to point to the corresponding new
locations
• The needed addresses are found in NewLocation.
Dr. Girish Kumar Patnaik 11
Mark-and-Compact Garbage Collectors
1. A list called Unscanned, holds objects that we have determined
are reached, but whose successors we have not yet considered.
2. objects are either as "reached" or "unreached,“ i.e. their reached-
bit is 1 or 0, respectively. Initially, all objects are unreached.
3. The pointer free, which marks the beginning of unallocated space
in the heap.
4. The table NewLocation (hash table, search tree, or another
structure) implements the two operations:
a) Set NewLocation(o) to a new address for object o.
b) Given object o, get the value of NewLocation(o) .
,
Dr. Girish Kumar Patnaik 12
Mark-and-Compact
Garbage Collectors
Dr. Girish Kumar Patnaik 13
Copying collectors
• Copying collector moves objects from one region of memory to
another. Reserving extra space for relocation allows reachable
objects to be moved as they are discovered.
• The memory space is partitioned into two semispaces, A and B.
• The mutator allocates memory in one semispace, say A, until it fills
up, at which point the mutator is stopped.
• Then the garbage collector copies the reachable objects to the
other space, say B.
• When garbage collection completes , the roles of the semispaces
are reversed
Dr. Girish Kumar Patnaik 14
Copying
collectors
Dr. Girish Kumar Patnaik 15
Comparing Costs
• Cheney 's Copying Collector has the advantage that it does not
touch any of the unreachable objects but move the contents of all
the reachable objects
• Basic Mark-and-Sweep : Proportional to the number of chunks in
the heap.
• Baker's Mark-and-Sweep : Proportional to the number of reached
objects.
• Basic Mark-and- Compact : Proportional to the number of chunks in
the heap plus the total size of the reached objects.
• Cheney 's Copying Collector : Proportional to the total size of the
reached objects.
Dr. Girish Kumar Patnaik 16
