Beltway: getting around garbage collection gridlock

ABSTRACT

We present the design and implementation of a new garbage collection framework that significantly generalizes existing copying collectors. The Beltway framework exploits and separates object age and incrementality. It groups objects in one or more increments on queues called belts, collects belts independently, and collects increments on a belt in first-in-first-out order. We show that Beltway configurations, selected by command line options, act and perform the same as semi-space, generational, and older-first collectors, and encompass all previous copying collectors of which we are aware. The increasing reliance on garbage collected languages such as Java requires that the collector perform well. We show that the generality of Beltway enables us to design and implement new collectors that are robust to variations in heap size and improve total execution time over the best generational copying collectors of which we are aware by up to 40%, and on average by 5 to 10%, for small to moderate heap sizes. New garbage collection algorithms are rare, and yet we define not just one, but a new family of collectors that subsumes previous work. This generality enables us to explore a larger design space and build better 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: B. Alpern , C. R. Attanasio , J. J. Barton , M. G. Burke , P. Cheng , J.-D. Choi , A. Cocchi , S. J. Fink , D. Grove , M. Hind , S. F. Hummel , D. Lieber , V. Litvinov , M. F. Mergen , T. Ngo , J. R. Russell , V. Sarkar , M. J. Serrano , J. C. Shepherd , S. E. Smith , V. C. Sreedhar , H. Srinivasan , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
• 3: A. W. Appel, Simple generational garbage collection and fast allocation, Software—Practice & Experience, v.19 n.2, p.171-183, February 1989 [doi>10.1002/spe.4380190206]
• 4: A. W. Appel , J. R. Ellis , K. Li, Real-time concurrent collection on stock multiprocessors, ACM SIGPLAN Notices, v.23 n.7, p.11-20, July 1988
• 5: David A. Barrett and Benjamin Zorn. Garbage collection using a dynamic threatening boundary. Computer Science Technical Report CU-CS-659-93, University of Colorado, July 1993
• 6: Peter B. Bishop. Computer Systems with a Very Large Address Space and Garbage Collection. PhD thesis, MIT Laboratory for Computer Science, May 1977. Technical report MIT/LCS/TR--178
• 7: Stephen M Blackburn , Kathryn S. McKinley, In or out?: putting write barriers in their place, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
• 8: Stephen M. Blackburn , Sharad Singhai , Matthew Hertz , Kathryn S. McKinely , J. Eliot B. Moss, Pretenuring for Java, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.342-352, October 14-18, 2001, Tampa Bay, FL, USA
• 9: Hans-J. Boehm , Alan J. Demers , Scott Shenker, Mostly parallel garbage collection, ACM SIGPLAN Notices, v.26 n.6, p.157-164, June 1991
• 10: Tim Brecht , Eshrat Arjomandi , Chang Li , Hang Pham, Controlling garbage collection and heap growth to reduce the execution time of Java applications, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.353-366, October 14-18, 2001, Tampa Bay, FL, USA
• 11: Dante J. Cannarozzi , Michael P. Plezbert , Ron K. Cytron, Contaminated garbage collection, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.264-273, June 18-21, 2000, Vancouver, British Columbia, Canada
• 12: C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
• 13: Perry Cheng , Guy E. Blelloch, A parallel, real-time garbage collector, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.125-136, June 2001, Snowbird, Utah, United States
• 14: Perry Cheng , Robert Harper , Peter Lee, Generational stack collection and profile-driven pretenuring, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.162-173, June 17-19, 1998, Montreal, Quebec, Canada
• 15: William D. Clinger , Lars T. Hansen, Generational garbage collection and the radioactive decay model, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.97-108, June 16-18, 1997, Las Vegas, Nevada, United States
• 16: Robert Courts, Improving locality of reference in a garbage-collecting memory management system, Communications of the ACM, v.31 n.9, p.1128-1138, Sept. 1988 [doi>10.1145/48529.48536]
• 17: Sylvia Dieckmann , Urs Hölzle, A Study of the Allocation Behavior of the SPECjvm98 Java Benchmark, Proceedings of the 13th European Conference on Object-Oriented Programming, p.92-115, June 14-18, 1999
• 18: David Gay , Alex Aiken, Memory management with explicit regions, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.313-323, June 17-19, 1998, Montreal, Quebec, Canada
• 19: Lars Thomas Hansen. Older-first garbage collection in practice. PhD thesis, North-eastern University, November 2000
• 20: Barry Hayes, Using key object opportunism to collect old objects, Conference proceedings on Object-oriented programming systems, languages, and applications, p.33-46, October 06-11, 1991, Phoenix, Arizona, United States
• 21: Michael Hicks , Luke Hornof , Jonathan T. Moore , Scott M. Nettles, A study of large object spaces, ACM SIGPLAN Notices, v.34 n.3, p.138-145, March 1999
• 22: Urs Hölzle , David Ungar, A third-generation SELF implementation: reconciling responsiveness with performance, Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications, p.229-243, October 23-28, 1994, Portland, Oregon, United States
• 23: Antony L. Hosking , J. Eliot B. Moss , Darko Stefanovic, A comparative performance evaluation of write barrier implementation, conference proceedings on Object-oriented programming systems, languages, and applications, p.92-109, October 18-22, 1992, Vancouver, British Columbia, Canada
• 24: 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
• 25: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 26: 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]
• 27: John H. Reppy. A high-performance garbage collector for Standard ML. Technical memorandum, AT&T Bell Laboratories, Murray Hill, NJ, December 1993
• 28: Standard Performance Evaluation Corporation. SPECjvm98 Documentation, release 1.03 edition, March 1999
• 29: Standard Performance Evaluation Corporation. SPECjbb2000 (Java Business Benchmark) Documentation, release 1.01 edition, 2001
• 30: Bjarne Steensgaard, Thread-specific heaps for multi-threaded programs, ACM SIGPLAN Notices, v.36 n.1, p.18-24, Jan 2001
• 31: Darko Stefanovic , J. Eliot Moss, Properties of age-based automatic memory reclamation algorithms, 1999
• 32: Darko Stefanović , Kathryn S. McKinley , J. Eliot B. Moss, Age-based garbage collection, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.370-381, November 01-05, 1999, Denver, Colorado, United States
• 33: Mads Tofte , Jean-Pierre Talpin, Region-based memory management, Information and Computation, v.132 n.2, p.109-176, Feb. 1, 1997 [doi>10.1006/inco.1996.2613]
• 34: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, ACM SIGPLAN Notices, v.19 n.5, p.157-167, May 1984
• 35: David Ungar , Frank Jackson, An adaptive tenuring policy for generation scavengers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.14 n.1, p.1-27, Jan. 1992 [doi>10.1145/111186.116734]
• 36: Alex Garthwaite , Derek White, The GC Interface in the EVM¹, Sun Microsystems, Inc., Mountain View, CA, 1998
• 37: P. R. Wilson, A simple bucket-brigade advancement mechanism for generation-bases garbage collection, ACM SIGPLAN Notices, v.24 n.5, p.38-46, May 1989 [doi>10.1145/66068.66070]
• 38: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992
• 39: P. R. Wilson , T. G. Moher, A “card-marking” scheme for controlling intergenerational references in generation-based garbage collection on stock hardware, ACM SIGPLAN Notices, v.24 n.5, p.87-92, May 1989 [doi>10.1145/66068.66077]
• 40: Benjamin Goth Zorn, Comparative performance evaluation of garbage collection algorithms, 1989

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

General Terms:
Algorithms, Design, Performance

Keywords:
Java, beltway, copying collection, generational collection