Visualising the train garbage collector

ABSTRACT

This paper presents a novel method for visualising an incremental garbage collector, based on the well-known Train algorithm, that generates concise snapshots of its state and informative graphs of its operation over time. To obtain these visualisations we used GC-spy, a generic heap visualisation framework. We show how this easy-to-use tool provided a visualisation model that was effective in both confirming our pre-existing beliefs about the collector's operation and, more interestingly, highlighting unexpected patterns in its behaviour. Based on this successful experience, we advocate the use of similar visualisation approaches to better understand and ultimately tune, profile, and improve other equally complex garbage collectors.

REFERENCES

• 1: Bowen Alpern , C. R. Attanasio , Anthony Cocchi , Derek Lieber , Stephen Smith , Ton Ngo , John J. Barton , Susan Flynn Hummel , Janice C. Sheperd , Mark Mergen, Implementing jalapeño in Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.314-324, November 01-05, 1999, Denver, Colorado, United States
• 2: P. B. Bishop. Computer Systems with a Very Large Address Space and Garbage Collection. Technical Report MIT/LCS/TR-178, MIT Laboratory for Computer Science, MA, USA, 1977
• 3: L. Cardelli, J. Donahue, L. Glassman, M. J. Jordan, B. Kalsow, and G. Nelson. Modula-3 report. Technical Report~52, Systems Research Center, Digital Equipment Corporation, Palo Alto, CA, September 1989. Revised
• 4: W. De Pauw and G. Sevitski. Visualizing Reference Patterns for Solving Memory Leaks in Java. Concurrency --- Practice and Experience, 12:1431--1454, 2000
• 5: James D. Foley , Andries van Dam , Steven K. Feiner , John F. Hughes, Computer graphics: principles and practice (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 6: Alexander T. Garthwaite , Scott M. Nettles, Making the trains run on time, University of Pennsylvania, Philadelphia, PA, 2005
• 7: Geodesic. Great Circle. http://www.geodesic.com/solutions/ February 7, 2002
• 8: Richard L. Hudson , Ron Morrison , J. Eliot B. Moss , David S. Munro, Garbage collecting the world: one car at a time, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.162-175, October 05-09, 1997, Atlanta, Georgia, United States
• 9: Richard L. Hudson , J. Eliot B. Moss, Incremental Collection of Mature Objects, Proceedings of the International Workshop on Memory Management, p.388-403, September 17-19, 1992
• 10: IBM Research. Jinsight. http://http://www.research.ibm.com/jinsight/November 12, 2001
• 11: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 12: G. N. C. Kirby and R. Morrison. OCB: An Object/Class Browser for Java. In Proceedings of the Second International Workshop on Persistence and Java (PJW2), pages 89--105, Half Moon Bay, CA, USA, August 1997
• 13: Henry Lieberman , Carl Hewitt, A real-time garbage collector based on the lifetimes of objects, Communications of the ACM, v.26 n.6, p.419-429, June 1983 [doi>10.1145/358141.358147]
• 14: David A. Moon, Garbage collection in a large LISP system, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.235-246, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802040]
• 15: J. E. B. Moss, D. S. Munro, and R. L. Hudson. PMOS: a Complete and Coarse-Grained Incremental Garbage Collector for Persistent Object Stores. In R. C. H. Connor and S. Nettles, editors, Persistent Object Systems: Principles and Practice --- Proceedings of the Seventh International Workshop on Persistent Object Systems (POS7), pages 140--150, Cape May, New Jersey, USA, May 1996. Book was published in 1997
• 16: David S. Munro , Alfred L. Brown , Ronald Morrison , J. Eliot B. Moss, Incremental Garbage Collection of a Persistent Object Store using PMOS, Proceedings of the 8th International Workshop on Persistent Object Systems (POS8) and Proceedings of the 3rd International Workshop on Persistence and Java (PJW3): Advances in Persistent Object Systems, p.78-91, January 1999
• 17: ParaSoft. Inuse. http://www.parasoft.com/products/inuse/index.htm. February 7, 2002
• 18: Tony Printezis , David Detlefs, A generational mostly-concurrent garbage collector, Proceedings of the 2nd international symposium on Memory management, p.143-154, October 15-16, 2000, Minneapolis, Minnesota, United States
• 19: T. Printezis and R. E. Jones. GCspy: An Adaptable Heap Visualisation Framework. Technical Report TR-2002-104, Department of Computing Science, University of Glasgow, Scotland, March 2002
• 20: K. Russell and L. Bak. The HotSpot™ Serviceability Agent: An Out-of-Process High-Level Debugger for a Java™ Virtual Machine. In Proceedings of the Usenix Java Virtual Machine Research and Technology Symposium (JVM'01), pages 117--126, Monterey, CA, USA, April 2001
• 21: Jacob Seligmann , Steffen Grarup, Incremental Mature Garbage Collection Using the Train Algorithm, Proceedings of the 9th European Conference on Object-Oriented Programming, p.235-252, August 07-11, 1995
• 22: Sitraka Inc. JProbe. http://www.jprobe.com/November 12, 2001
• 23: Sun Microsystems Inc. Java™ Heap Analysis Tool (HAT). http://java.sun.com/people/billf/heap/November 12, 2001
• 24: Sun Microsystems Inc. The Java HotSpot™ Virtual Machine, 2001. Technical White Paper
• 25: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, ACM SIGPLAN Notices, v.19 n.5, p.157-167, May 1984
• 26: David Ungar , Randall B. Smith, Self: The power of simplicity, Conference proceedings on Object-oriented programming systems, languages and applications, p.227-242, October 04-08, 1987, Orlando, Florida, United States
• 27: VMGEAR. OptimizeIt. http://www.optimizeit.com. November 12, 2001
• 28: David Wakeling, Compiling lazy functional programs for the Java Virtual Machine, Journal of Functional Programming, v.9 n.6, p.579-603, November 1999 [doi>10.1017/S0956796899003603]
• 29: Alex Garthwaite , Derek White, The GC Interface in the EVM¹, Sun Microsystems, Inc., Mountain View, CA, 1998
• 30: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992
• 31: John N. Zigman , Stephen Blackburn , J. Eliot B. Moss, TMOS: A Transactional Garbage Collector, Revised Papers from the 9th International Workshop on Persistent Object Systems, p.138-156, September 06-08, 2000

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

General Terms:
Experimentation, Measurement