Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance

ABSTRACT

Programmers are increasingly choosing managed languages for modern applications, which tend to allocate many short-to-medium lived small objects. The garbage collector therefore directly determines program performance by making a classic space-time tradeoff that seeks to provide space efficiency, fast reclamation, and mutator performance. The three canonical tracing garbage collectors: semi-space, mark-sweep, and mark-compact each sacrifice one objective. This paper describes a collector family, called mark-region, and introduces opportunistic defragmentation, which mixes copying and marking in a single pass. Combining both, we implement immix, a novel high performance garbage collector that achieves all three performance objectives. The key insight is to allocate and reclaim memory in contiguous regions, at a coarse block grain when possible and otherwise in groups of finer grain lines. We show that immix outperforms existing canonical algorithms, improving total application performance by 7 to 25% on average across 20 benchmarks. As the mature space in a generational collector, immix matches or beats a highly tuned generational collector, e.g. it improves jbb2000 by 5%. These innovations and the identification of a new family of collectors open new opportunities for garbage collector design.

REFERENCES

• 1: Diab Abuaiadh , Yoav Ossia , Erez Petrank , Uri Silbershtein, An efficient parallel heap compaction algorithm, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 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: 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
• 4: 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]
• 5: Matthew Arnold , Stephen Fink , David Grove , Michael Hind , Peter F. Sweeney, Adaptive optimization in the Jalapeño JVM, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.47-65, October 2000, Minneapolis, Minnesota, United States
• 6: C. Attanasio, D. Bacon, A. Cocchi, and S. Smith. A comparative evaluation of parallel garbage collectors. In Proceedings of the Workshop on Languages and Compilers for Parallel Computing, Cumberland Falls, KY, Aug. 2001.
• 7: David F. Bacon , Perry Cheng , V. T. Rajan, Controlling fragmentation and space consumption in the metronome, a real-time garbage collector for Java, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 8: David F. Bacon , Perry Cheng , V. T. Rajan, A real-time garbage collector with low overhead and consistent utilization, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.285-298, January 15-17, 2003, New Orleans, Louisiana, USA
• 9: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 10: Katherine Barabash , Ori Ben-Yitzhak , Irit Goft , Elliot K. Kolodner , Victor Leikehman , Yoav Ossia , Avi Owshanko , Erez Petrank, A parallel, incremental, mostly concurrent garbage collector for servers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.6, p.1097-1146, November 2005 [doi>10.1145/1108970.1108972]
• 11: BEA Systems Inc. Using the JRockit runtime analyzer. http://edocs.bea.com/wljrockit/docs142/usingJRA/looking.html, 2007.
• 12: Stephen M. Blackburn , Perry Cheng , Kathryn S. McKinley, Myths and realities: the performance impact of garbage collection, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 13: Stephen M. Blackburn , Perry Cheng , Kathryn S. McKinley, Oil and Water? High Performance Garbage Collection in Java with MMTk, Proceedings of the 26th International Conference on Software Engineering, p.137-146, May 23-28, 2004
• 14: Stephen M. Blackburn , Robin Garner , Chris Hoffmann , Asjad M. Khang , Kathryn S. McKinley , Rotem Bentzur , Amer Diwan , Daniel Feinberg , Daniel Frampton , Samuel Z. Guyer , Martin Hirzel , Antony Hosking , Maria Jump , Han Lee , J. Eliot B. Moss , B. Moss , Aashish Phansalkar , Darko Stefanović , Thomas VanDrunen , Daniel von Dincklage , Ben Wiedermann, The DaCapo benchmarks: java benchmarking development and analysis, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 15: S. M. Blackburn, R. Garner, C. Hoffman, A. M. Khan, K. S. McKinley, R. Bentzur, A. Diwan, D. Feinberg, D. Frampton, S. Z. Guyer, M. Hirzel, A. Hosking, M. Jump, H. Lee, J. E. B. Moss, A. Phansalkar, D. Stefanović, T. VanDrunen, D. von Dincklage, and B. Wiedermann. The DaCapo Benchmarks: Java benchmarking development and analysis (extended version). Technical Report TR-CS-06-01, Dept. of Computer Science, Australian National University, 2006. http://www.dacapobench.org.
• 16: Stephen M. Blackburn , Antony L. Hosking, Barriers: friend or foe?, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029891]
• 17: Stephen M Blackburn , Richard Jones , Kathryn S. McKinley , J Eliot B Moss, Beltway: getting around garbage collection gridlock, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 18: S. Borman. Sensible sanitation ? understanding the IBM Java garbage collector. http://www.ibm.com/developerworks/ibm/library/i-garbage1/, Aug. 2002.
• 19: 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]
• 20: Jacques Cohen , Alexandru Nicolau, Comparison of Compacting Algorithms for Garbage Collection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.4, p.532-553, Oct. 1983 [doi>10.1145/69575.357226]
• 21: Alan Demmers , Mark Weiser , Barry Hayes , Hans Boehm , Daniel Bobrow , Scott Shenker, Combining generational and conservative garbage collection: framework and implementations, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.261-269, December 1989, San Francisco, California, United States [doi>10.1145/96709.96735]
• 22: David Detlefs , Christine Flood , Steve Heller , Tony Printezis, Garbage-first garbage collection, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029879]
• 23: Tamar Domani , Elliot K. Kolodner , Erez Petrank, A generational on-the-fly garbage collector for Java, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.274-284, June 18-21, 2000, Vancouver, British Columbia, Canada
• 24: Yi Feng , Emery D. Berger, A locality-improving dynamic memory allocator, Proceedings of the 2005 workshop on Memory system performance, June 12-12, 2005, Chicago, Illinois [doi>10.1145/1111583.1111594]
• 25: D. Frampton, D. F. Bacon, P. Cheng, and D. Grove. Generational realtime garbage collection: A a three-part invention for young obects. In European Conference on Object-Oriented Programming, pages 101--125, Berlin, Germany, July 2007.
• 26: 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
• 27: Jikes RVMCore Team. VMperformance comparisons. http://jikesrvm.anu.edu.au/~dacapo/index.php?category=release, 2007.
• 28: Haim Kermany , Erez Petrank, The Compressor: concurrent, incremental, and parallel compaction, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 29: D. Lea. A memory allocator. Technical report, SUNY at Oswego, 1996.
• 30: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 31: Phil McGachey , Antony L. Hosking, Reducing generational copy reserve overhead with fallback compaction, Proceedings of the 5th international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada [doi>10.1145/1133956.1133960]
• 32: M. Pettersson. Linux Intel/x86 performance counters, 2003. http://user.it.uu.se/~mikpe/linux/perfctr/.
• 33: Narendran Sachindran , J. Eliot B. Moss , Emery D. Berger, MC²: high-performance garbage collection for memory-constrained environments, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 34: Daniel Spoonhower , Guy Blelloch , Robert Harper, Using page residency to balance tradeoffs in tracing garbage collection, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA [doi>10.1145/1064979.1064989]
• 35: Standard Performance Evaluation Corporation. SPECjbb2000 Documentation, release 1.01 edition, 2001.
• 36: 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
• 37: P. Styger. LISP 2 garbage collector specifications. Technical Report TM-3417/500/00 1, System Development Cooperation, Santa Monica, CA, Apr. 1967.

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:
compaction, fragmentation, free-list, immix, locality, mark-region, mark-sweep, semi-space, sweep-to-free-list, sweep-to-region