Mon 20 - Fri 24 October 2014 Portland, Oregon, United States

Garbage collectors for managed languages are exact or conservative. An exact collector identifies references precisely and may move referents and update references. A conservative collector is constrained by ambiguous references in two ways. (1) Since they may be pointers, the collectors must retain referents. (2) Since they may be values, the collectors cannot modify them, pinning their referents. This paper is the first to show that retaining dead objects and pinning objects affects remarkably few heap objects: for Java benchmarks, < 0.01% are falsely retained and 0.03% are pinned.

The larger effect is collector design. Prior conservative collectors either (1) use mark-sweep and forgo moving all objects, or (2) use mostly copying and pin entire pages. This paper shows this overhead is substantial: 12% and 45% respectively, compared to generational collection in a Java VM. We introduce high performance conservative Immix and reference counting (RC). Immix is a mark-region collector that combines fine line-grain pinning and opportunistic copying of unambiguous referents. Deferred RC simply needs an object map to deliver the first conservative RC in the literature. We implement six exact collectors and their conservative counterparts. Conservative Immix variants and RC come within 2 to 3% of their exact counterparts. In particular, conservative RC Immix is slightly faster than a well-tuned exact generational collector. For managed languages, these findings show conservative collection is compatible with high performance.