MC2: high-performance garbage collection for memory-constrained environments

ABSTRACT

Java is becoming an important platform for memory-constrained consumer devices such as PDAs and cellular phones, because it provides safety and portability. Since Java uses garbage collection, efficient garbage collectors that run in constrained memory are essential. Typical collection techniques used on these devices are mark-sweep and mark-compact. Mark-sweep collectors can provide good throughput and pause times but suffer from fragmentation. Mark-compact collectors prevent fragmentation, have low space overheads, and provide good throughput. However, they can suffer from long pause times. Copying collectors can provide higher throughput than either of these techniques, but because of their high space overhead, they previously were unsuitable for memory-constrained devices. This paper presents MC² (Memory-Constrained Copying), a copying generational garbage collector that meets the needs of memory-constrained devices with soft real-time requirements. MC² has low space over-head and tight space bounds, prevents fragmentation, provides good throughput, and yields short pause times. These qualities make MC² attractive for other environments, including desktops and servers.

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, ACM SIGPLAN Notices, v.34 n.10, p.314-324, Oct. 1999
• 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: Alain Azagury , Elliot K. Kolodner , Erez Petrank , Zvi Yehudai, Combining card marking with remembered sets: how to save scanning time, Proceedings of the 1st international symposium on Memory management, p.10-19, October 17-19, 1998, Vancouver, British Columbia, Canada
• 4: 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
• 5: 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
• 6: 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]
• 7: Ori Ben-Yitzhak , Irit Goft , Elliot K. Kolodner , Kean Kuiper , Victor Leikehman, An algorithm for parallel incremental compaction, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
• 8: 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
• 9: 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
• 10: Rodney A. Brooks, Trading data space for reduced time and code space in real-time garbage collection on stock hardware, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.256-262, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802042]
• 11: 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]
• 12: 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
• 13: 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]
• 14: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , C. S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Communications of the ACM, v.21 n.11, p.966-975, Nov. 1978 [doi>10.1145/359642.359655]
• 15: B. K. Haddon and W. M. Waite. A compaction procedure for variable length storage elements. Computer Journal, 10:162--165, August 1967.
• 16: 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
• 17: ISMM'02 Proceedings of the Third International Symposium on Memory Management, ACM SIGPLAN Notices, Berlin, June 2002. ACM Press.
• 18: Mark S. Johnstone , Paul R. Wilson, The memory fragmentation problem: solved?, Proceedings of the 1st international symposium on Memory management, p.26-36, October 17-19, 1998, Vancouver, British Columbia, Canada
• 19: H. B. M. Jonkers. A fast garbage compaction algorithm. Information Processing Letters, 9(1):25--30, July 1979.
• 20: 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]
• 21: Johannes J. Martin, An efficient garbage compaction algorithm, Communications of the ACM, v.25 n.8, p.571-580, Aug 1982 [doi>10.1145/358589.358625]
• 22: 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]
• 23: NewMonics Inc., PERC virtual machine. http://www.newmonics.com/perc/info.shtml.
• 24: Narendran Sachindran , J. Eliot , B. Moss, Mark-copy: fast copying GC with less space overhead, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 25: H. Schorr , W. M. Waite, An efficient machine-independent procedure for garbage collection in various list structures, Communications of the ACM, v.10 n.8, p.501-506, Aug. 1967 [doi>10.1145/363534.363554]
• 26: Standard Performance Evaluation Corporation. SPECjvm98 Documentation, release 1.03 edition, March 1999.
• 27: Standard Performance Evaluation Corporation. SPECjbb2000 (Java Business Benchmark) Documentation, release 1.01 edition, 2001.
• 28: Guy L. Steele, Jr., Multiprocessing compactifying garbage collection, Communications of the ACM, v.18 n.9, p.495-508, Sept. 1975 [doi>10.1145/361002.361005]
• 29: Sun Microsystems, The CLDC HotSpot Implementation Virtual Machine, Java 2 Platform, Micro Edition J2ME Technology, March 2004. http://java.sun.com/products/cldc/wp/CLDC-HI whitepaper-March2004.pdf.
• 30: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, ACM SIGPLAN Notices, v.19 n.5, p.157-167, May 1984
• 31: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992
• 32: T. Yuasa, Real-time garbage collection on general-purpose machines, Journal of Systems and Software, v.11 n.3, p.181-198, Mar. 1990 [doi>10.1016/0164-1212(90)90084-Y]

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
copying collector, generational collector, java, mark-compact, mark-copy, mark-sweep, memory-constrained copying