Most Garbage Collectors are tracing. Instead of using Reference Counting, they trace down unused objects (garbage) by tracing from the root set of objects and mark all objects found. Those who weren’t marked have to garbage.
The Root-set
The root-set are all objects that are definitely live objects. The root set typically consists out of the objects linked from the stack and registers of each thread. Also object vital to the Gc and globals are in the root-set.
Tri-Color algorithm
An easy way to represent tracing through objects is the tri-color method. There are three colors an object can have: white, gray and black. All white objects haven’t seem to be referenced yet from black objects which are sure to be non-garbage. The gray objects are those that are referenced by black objects but didn’t have all of their references checked. Sounds confusing? A more practical explanation:
- Colour all objects white.
- Colour the root-set objects gray.
- (Repeat this as long as there are gray coloured objects) Pick a gray object. Colour all objects referenced to from that gray object gray too. (Except those who are black). And colour itself black.
- All black objects are now reachable, and all white objects are unreachable. Free those that are white!
Pop-mark-push referenced
An implementation of the Tri-Color algorithm can be accomplished by putting a mark on each object which either can be 1 or 0. 1 representing a black object, and 0 representing a white object. A stack list can be used to keep track of the gray objects:
NB do not confuse this stack, which is a normal Last In First Out list with the call stack.
- Mark all objects 0 (white).
- Push all objects in the root-set on the gray-stack.
- (while there are objects in the gray-stack) Pop an object from the gray-stack. Mark it 1 (black) and push all referenced objects from that object on the gray-stack that aren’t marked 1 (thus white).
- All objects still marked 0 (white) can be freed rid of.
Generations
Studies have shown that in almost all applications most allocations have a lifetime less than a few miliseconds, although the rest of the allocations would have a far greater lifespan. When collecting every few miliseconds would cause unnesessary tracing through the long living objects which would still take up most of the memory, and when collecting every few seconds the uncollected short-lifed objects would have spammed the heap and would make the garbage collector locality-of-reference unfriendly (everything worked on wouldn’t fit in one l2-cache load and therefore would be a lot slower).
The older objects which are in comparison with the newer objects highly unlikely to be garbage could be searched less frequently. This could be done by seperating the heap into generations. Each generation is basicly a piece of the heap. A typical garbage collection would only target the youngest few generation. Everytime an object survives a garbage collection it’s moved into an older generation, and finally becomes part of the oldest generation that is only garbage collected very infrequently.
Unpredictable garbage collection duration
The duration of the garbage collections would be hard to predict and could vary a lot. Although generation based gc’s could increase the amount of garbage collections and decrease the total time in comparison with one big, applications that use a garbage collection can not guarentee (practically) uninterupted execution.
Advantages
- No extra fields required to keep track of the reference count.
- There hasn’t got to be registration of references to objects, cause the gc keeps traces those down.
- Hasn’t got any problem with circular references.
- Outperforms reference Gc. The registration for each reference in the reference counter Gc takes more time than tracing down that reference. And it doesn’t do unnesessary checking of older objects when generations are kept in mind.
Disadvantages
- Way harder to implement.
- All pointers inside an object should be known.
- Worse latency than reference counter. Although it outperforms refcounter, a garbage collects usually requires the whole program to be halted, which is a really bad thing for some applications.
Conclusion
Tracing gc‘s have shown to easily outperform reference counter gc‘s. The prerequeste to know all pointers in an object can be solved easily for interpreted and jit-ted languages using the gc and can also be managed even in C with effort. The real problem remains the arbitrary and unpredictable length of garbage collections. There are ways to make tracing gc’s have a better latency, which I`ll discuss in coming posts.