School of Computing

Accurate garbage collection in uncooperative environments revisited

Jason Baker, Antonio Cunei, Tomas Kalibera, Filip Pizlo, and Jan Vitek

Concurrency and Computation: Practice and Experience, 21(12):182-196, August 2009 [doi].


Implementing a concurrent programming language such as Java by means of a translator to an existing language is attractive as it provides portability over all platforms supported by the host language and reduces development time - as many low-level tasks can be delegated to the host compiler. The C and C++ programming languages are popular choices for many language implementations due to the availability of efficient compilers on a wide range of platforms. For garbage-collected languages, however, they are not a perfect match as no support is provided for accurately discovering pointers to heap-allocated data on thread stacks. We evaluate several previously published techniques and propose a new mechanism, lazy pointer stacks, for performing accurate garbage collection in such uncooperative environments. We implemented the new technique in the Ovm Java virtual machine with our own Java-to-C/C++ compiler using GCC as a back-end compiler. Our extensive experimental results confirm that lazy pointer stacks outperform existing approaches: we provide a speedup of 4.5% over Henderson's accurate collector with a 17% increase in code size. Accurate collection is essential in the context of real-time systems, we thus validate our approach with the implementation of a real-time concurrent garbage collection algorithm.

Download publication 824 kbytes (PDF)

Bibtex Record

author = {Jason Baker and Antonio Cunei and Tomas Kalibera and Filip Pizlo and Jan Vitek},
title = {Accurate garbage collection in uncooperative environments revisited},
month = {August},
year = {2009},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {10.1002/cpe.1391},
url = {},
    publication_type = {article},
    submission_id = {2548_1308856225},
    journal = {Concurrency and Computation: Practice and Experience},
    volume = {21},
    number = {12},
    publisher = {Wiley},

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014