Garbology: a study of how Java objects die

ABSTRACT

In this paper we present a study of how Java programs dispose of objects. Unlike prior work on object demographics and lifetime patterns, our goal is to precisely characterize the actions that cause objects to become unreachable. We use a recently-developed tracing tool, called Elephant Tracks, which can localize object deaths within a specific method and tell us the proximal cause. Our analysis centers around garbage clusters: groups of connected objects that become unreachable at precisely the same time due to a single program action. We classify these clusters using traditional features, such as size, allocation site, and lifetime, and using new ones, such as death site and cause of death. We then use this knowledge about garbage clusters in a new GC algorithm: the Cluster Aware Garbage Collection (CAGC) algorithm.

We present results for a set of standard benchmarks including SPECJVM98, SPECjbb, and DaCapo. We identify several patterns that could inform the design of new collectors or tuning of existing systems. Most garbage clusters are small, suggesting that these programs almost always dispose of large structures in a piecemeal fashion. In addition, most clusters die in one of only a dozen or so places in the program. Furthermore, these death sites are much more stable and predictable than object lifetimes. Finally we show that the CAGC algorithm can in certain cases improve GC performance.

References

1. 1998. SPECjvm 1998 benchmark. http://www.spec.org/jvm98 . (1998).
2. 2005. SPECjbb 2005 benchmark. http://www.spec.org/jbb2005 . (2005).
3. 2016. Java Platform, Standard Edition Troubleshooting Guide. https://docs.oracle.com/javase/8/docs/technotes/guides/troubleshoot/ memleaks002.html . (2016). [Online; accessed 22-April-2017].
4. Stephen M. Blackburn, John Cavazos, Sharad Singhai, Asjad Khan, Kathryn S. Mckinley, J. Eliot, B. Moss, and Sara Smolensky. 2001. Pretenuring for Java. In In Proceedings of SIGPLAN 2001 Conference on Object-Oriented Programming, Languages, and Applications . ACM Press, 342–352.
5. Stephen M Blackburn, Perry Cheng, and Kathryn S McKinley. 2004. Myths and realities: The performance impact of garbage collection. ACM SIG-METRICS Performance Evaluation Review 32, 1 (2004), 25–36.
6. Stephen M Blackburn, Robin Garner, Chris Hoffmann, Asjad M Khang, Kathryn S McKinley, Rotem Bentzur, Amer Diwan, Daniel Feinberg, Daniel Frampton, Samuel Z Guyer, and others. 2006. The DaCapo benchmarks: Java benchmarking development and analysis. In ACM Sigplan Notices , Vol. 41. ACM, 169–190.
7. Nachshon Cohen and Erez Petrank. 2015. Data structure aware garbage collector. In Proceedings of the 2015 ACM SIGPLAN International Symposium on Memory Management . ACM, 28–40.
8. Cody Cutler and Robert Morris. 2015. Reducing Pause Times with Clustered Collection. In Proceedings of the 2015 International Symposium on Memory Management . 131–142.
9. Sylvia Dieckmann and Urs Hölzle. 1999. A study of the allocation behavior of the SPECjvm98 Java benchmarks. In ECOOPâĂŹ99âĂŤObject-Oriented Programming . Springer, 92–115.
10. Barry Hayes. 1991. Using Key Object Opportunism to Collect Old Objects. SIGPLAN Not. 26, 11 (Nov. 1991), 33–46.
11. Matthew Hertz, Stephen M. Blackburn, J. Eliot B. Moss, Kathryn S. McKinley, and Darko Stefanović. 2006. Generating Object Lifetime Traces with Merlin. ACM Transactions on Programming Languages and Systems 28, 3 (May 2006), 476–516.
12. Martin Hirzel, Amer Diwan, and Matthew Hertz. 2003. Connectivity-Based Garbage Collection. In OOPSLA. ACM Press, 359–373.
13. Martin Hirzel, Johannes Henkel, Amer Diwan, and Michael Hind. 2002. Understanding the connectivity of heap objects. In Proceedings of the 3rd International Symposium on Memory Management . 36–49.
14. Richard Jones, Antony Hosking, and Eliot Moss. 2011. The Garbage Collection Handbook: The Art of Automatic Memory Management (1st ed.). Chapman & Hall/CRC.
15. Richard E Jones and Chris Ryder. 2008. A study of Java object demographics. In Proceedings of the 7th international symposium on Memory management. ACM, 121–130.
16. Nathan P Ricci, Samuel Z Guyer, and J Eliot B Moss. 2013. Elephant tracks: portable production of complete and precise gc traces. ACM SIGPLAN Notices 48, 11 (2013), 109–118.
17. Darko Stefanovic. 1999. Properties of age -based automatic memory reclamation algorithms . Ph.D. Dissertation. The University of Massachusetts Amherst.
18. Darko Stefanović, Kathryn S. McKinley, and J. Eliot B. Moss. 1999. Age-based Garbage Collection. SIGPLAN Not. 34, 10 (Oct. 1999), 370–381.
19. Robert Tarjan. 1972. Depth-first search and linear graph algorithms. SIAM journal on computing 1, 2 (1972), 146–160.
20. David Ungar. 1984. Generation Scavenging: A Non-disruptive High Performance Storage Reclamation Algorithm. SIGPLAN Not. 19, 5 (April 1984), 157–167.

Index Terms

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

          • Garbage collection

    • Software functional properties

      • Formal methods

        • Dynamic analysis