A comprehensive evaluation of object scanning techniques




Garner, Robin
Blackburn, Stephen
Frampton, Daniel

Journal Title

Journal ISSN

Volume Title


Association for Computing Machinery Inc (ACM)


At the heart of all garbage collectors lies the process of identifying and processing reference fields within an object. Despite its key role, and evidence of many different implementation approaches, to our knowledge no comprehensive quantitative study of this design space exists. The lack of such a study means that implementers must rely on 'conventional wisdom', hearsay, and their own costly analysis. Starting with mechanisms described in the literature and a variety of permutations of these, we explore the impact of a number of dimensions including: a) the choice of data structure, b) levels of indirection from object to metadata, and c) specialization of scanning code. We perform a comprehensive examination of these tradeoffs on four different architectures using eighteen benchmarks and hardware performance counters. We inform the choice of mechanism with a detailed study of heap composition and object structure as seen by the garbage collector on these benchmarks. Our results show that choice of scanning mechanism is important. We find that a careful choice of scanning mechanism alone can improve garbage collection performance by 16% and total time by 2.5%, on average, over a well tuned baseline. We observe substantial variation in performance among architectures, and find that some mechanisms - particularly specialization, layout of reference fields in objects, and encoding metadata in object headers - yield consistent, significant advantages.



Keywords: Comprehensive evaluation; Comprehensive examination; Design spaces; Garbage collection; Garbage collectors; Hardware performance counters; Implementation approach; java; Mark-sweep; Object scanning; Object structure; Quantitative study; Reference field; S java; mark-sweep




Conference paper

Book Title

Entity type

Access Statement

License Rights



Restricted until