Derivation and Evaluation of Concurrent Collectors

Derivation and Evaluation of Concurrent Collectors, Martin T. Vechev, David F. Bacon, Perry Cheng, and David Grove. ECOOP 2005.

There are many algorithms for concurrent garbage collection, but they are complex to describe, verify, and implement. This has resulted in a poor understanding of the relationships between the algorithms, and has precluded systematic study and comparative evaluation. We present a single high-level, abstract concurrent garbage collection algorithm, and show how existing snapshot and incremental update collectors, can be derived from the abstract algorithm by reducing precision. We also derive a new hybrid algorithm that reduces floating garbage while terminating quickly. We have implemented a concurrent collector framework and the resulting algorithms in IBM’s J9 Java virtual machine product and compared their performance in terms of space, time, and incrementality. The results show that incremental update algorithms sometimes reduce memory requirements (on 3 of 5 benchmarks) but they also sometimes take longer due to recomputation in the termination phase (on 4 of 5 benchmarks). Our new hybrid algorithm has memory requirements similar to the incremental update collectors while avoiding recomputation in the termination phase.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

follow up paper

An interesting follow up paper is "CGCExplorer: a semi-automated search procedure for provably correct concurrent collectors", where they turn it into a search (or synthesis) problem. I don't think sketching nor more general search has been mentioned in LtU recently, but it's an interesting approach, esp. in these parallel days.

What existing language systems use concurrent GC?

None of these: Perl, Python, Ruby, Erlang, OCaml. I haven't seen a Lisp or Scheme with concurrent GC, but that doesn't mean there isn't one.

Just Java?

C# has a concurrent GC.

C#/.NET has a concurrent GC.

Concurrent Caml Light

1993: Doligez and Leroy, “A concurrent, generational garbage collector for a multithreaded implementation of ML.”

The “Extensions” section discusses a simplified version for uniprocessors, featuring an incremental major collection, which appears to be a direct ancestor of the one now in OCaml.

Also, the Haskell community might have some ideas; I note that the Concurrent Caml Light collector exploited immutability where it could.