skip to main content
10.1145/1028976.1028984acmconferencesArticle/Chapter ViewAbstractPublication PagessplashConference Proceedingsconference-collections
Article

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

Published:01 October 2004Publication History

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<sup>2</sup> (Memory-Constrained Copying), a copying generational garbage collector that meets the needs of memory-constrained devices with soft real-time requirements. MC<sup>2</sup> has low space over-head and tight space bounds, prevents fragmentation, provides good throughput, and yields short pause times. These qualities make MC<sup>2</sup> 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, and Mark Mergen. Implementing Jalapeño in Java. In OOPSLA'99 ACM Conference on Object-Oriented Systems, Languages and Applications, volume 34(10) of ACM SIGPLAN Notices, pages 314--324, Denver, CO, October 1999. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. Bowen Alpern, Dick Attanasio, John J. Barton, M. G. Burke, P. Cheng, J.-D. Choi, Anthony Cocchi, Stephen J. Fink, David Grove, Michael Hind, Susan Flynn Hummel, D. Lieber, V. Litvinov, Mark Mergen, Ton Ngo, J. R. Russell, Vivek Sarkar, Manuel J. Serrano, Janice Shepherd, S. Smith, V. C. Sreedhar, H. Srinivasan, and J. Whaley. The Jalapeño virtual machine. IBM System Journal, 39(1):211--238, February 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. Alain Azagury, Elliot K. Kolodner, Erez Petrank, and Zvi Yehudai. Combining card marking with remembered sets: How to save scanning time. In Richard Jones, editor, ISMM'98 Proceedings of the First International Symposium on Memory Management, volume 34(3) of ACM SIGPLAN Notices, pages 10--19, Vancouver, October 1998. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. David F. Bacon, Perry Cheng, and V.T. Rajan. Controlling fragmentation and space consumption in the Metronome, a real-time garbage collector for Java. In ACM SIGPLAN 2003 Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES'2003), pages 81--92, San Diego, CA, June 2003. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. David F. Bacon, Perry Cheng, and V.T. Rajan. A real-time garbage collecor with low overhead and consistent utilization. In Conference Record of the Thirtieth Annual ACM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices, pages 285--298, New Orleans, LA, January 2003. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. Henry G. Baker. List processing in real-time on a serial computer. Communications of the ACM, 21(4):280--294, 1978. Also AI Laboratory Working Paper 139, 1977. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. Ori Ben-Yitzhak, Irit Goft, Elliot Kolodner, Kean Kuiper, and Victor Leikehman. An algorithm for parallel incremental compaction. In ISMM '02 {17}, pages 100--105. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. Stephen M. Blackburn, Perry Cheng, and Kathryn S. McKinley. Oil and Water? High Performance Garbage Collection in Java with MMTk. In ICSE 2004, 26th International Conference on Software Engineering, pages 137--146, Edinburgh, May 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. Stephen M. Blackburn and Kathryn S. McKinley. In or out? Putting write barriers in their place. In ISMM '02 {17}, pages 175--184. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. Rodney A. Brooks. Trading data space for reduced time and code space in real-time garbage collection on stock hardware. In Guy L. Steele, editor, Conference Record of the 1984 ACM Symposium on Lisp and Functional Programming, pages 256--262, Austin, TX, August 1984. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. C. J. Cheney. A non-recursive list compacting algorithm. Communications of the ACM, 13(11):677--8, November 1970. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. Perry Cheng and Guy Blelloch. A parallel, real-time garbage collector. In Proceedings of SIGPLAN 2001 Conference on Programming Languages Design and Implementation, ACM SIGPLAN Notices, pages 125--136, Snowbird, Utah, June 2001. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. Jacques Cohen and Alexandru Nicolau. Comparison of compacting algorithms for garbage collection. ACM Transactions on Programming Languages and Systems, 5(4):532--553, 1983. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. Edsgar W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. On-the-fly garbage collection: An exercise in cooperation. Communications of the ACM, 21(11):965--975, November 1978. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. B. K. Haddon and W. M. Waite. A compaction procedure for variable length storage elements. Computer Journal, 10:162--165, August 1967.Google ScholarGoogle ScholarCross RefCross Ref
  16. Richard L. Hudson and J. Eliot B. Moss. Incremental garbage collection for mature objects. In Yves Bekkers and Jacques Cohen, editors, Proceedings of International Workshop on Memory Management, volume 637 of Lecture Notes in Computer Science, pages 388--403, University of Massachusetts, USA, 16-18 September 1992. Springer-Verlag. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. ISMM'02 Proceedings of the Third International Symposium on Memory Management, ACM SIGPLAN Notices, Berlin, June 2002. ACM Press.Google ScholarGoogle Scholar
  18. Mark S. Johnstone and Paul R. Wilson. The memory fragmentation problem: Solved? In Peter Dickman and Paul R. Wilson, editors, OOPSLA '97 Workshop on Garbage Collection and Memory Management, pages 26--36, October 1997. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. H. B. M. Jonkers. A fast garbage compaction algorithm. Information Processing Letters, 9(1):25--30, July 1979.Google ScholarGoogle ScholarCross RefCross Ref
  20. Henry Lieberman and Carl E. Hewitt. A real-time garbage collector based on the lifetimes of objects. Communications of the ACM, 26(6):419--429, 1983. Also report TM-184, Laboratory for Computer Science, MIT, Cambridge, MA, July 1980 and AI Lab Memo 569, 1981. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. Johannes J. Martin. An efficient garbage compaction algorithm. Communications of the ACM, 25(8):571--581, August 1982. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. John McCarthy. Recursive functions of symbolic expressions and their computation by machine. Communications of the ACM, 3:184--195, 1960. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. NewMonics Inc., PERC virtual machine. http://www.newmonics.com/perc/info.shtml.Google ScholarGoogle Scholar
  24. Narendran Sachindran and J. Eliot B. Moss. Mark-Copy: Fast copying GC with less space overhead. In OOPSLA'03 ACM Conference on Object-Oriented Systems, Languages and Applications,ACM SIGPLAN Notices, pages 326--343, Anaheim, CA, November 2003. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  25. H. Schorr and W. Waite. An efficient machine independent procedure for garbage collection in various list structures. Communications of the ACM, 10(8):501--506, August 1967. Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. Standard Performance Evaluation Corporation. SPECjvm98 Documentation, release 1.03 edition, March 1999.Google ScholarGoogle Scholar
  27. Standard Performance Evaluation Corporation. SPECjbb2000 (Java Business Benchmark) Documentation, release 1.01 edition, 2001.Google ScholarGoogle Scholar
  28. Guy L. Steele. Multiprocessing compactifying garbage collection. Communications of the ACM, 18(9):495--508, September 1975. Google ScholarGoogle ScholarDigital LibraryDigital Library
  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.Google ScholarGoogle Scholar
  30. David M. Ungar. Generation scavenging: A non-disruptive high performance storage reclamation algorithm. ACM SIGPLAN Notices, 19(5):157--167, April 1984. Also published as ACM Software Engineering Notes 9, 3 (May 1984) - Proceedings of the ACM/SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, 157--167, April 1984. Google ScholarGoogle ScholarDigital LibraryDigital Library
  31. Paul R. Wilson. Uniprocessor garbage collection techniques. Technical report, University of Texas, January 1994. Expanded version of the IWMM92 paper. Google ScholarGoogle ScholarDigital LibraryDigital Library
  32. Taichi Yuasa. Real-time garbage collection on general-purpose machines. Journal of Software and Systems, 11(3):181--198, 1990. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

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

Recommendations

Comments

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Sign in
  • Published in

    cover image ACM Conferences
    OOPSLA '04: Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications
    October 2004
    462 pages
    ISBN:1581138318
    DOI:10.1145/1028976
    • cover image ACM SIGPLAN Notices
      ACM SIGPLAN Notices  Volume 39, Issue 10
      OOPSLA '04
      October 2004
      448 pages
      ISSN:0362-1340
      EISSN:1558-1160
      DOI:10.1145/1035292
      Issue’s Table of Contents

    Copyright © 2004 ACM

    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    • Published: 1 October 2004

    Permissions

    Request permissions about this article.

    Request Permissions

    Check for updates

    Qualifiers

    • Article

    Acceptance Rates

    Overall Acceptance Rate268of1,244submissions,22%

    Upcoming Conference

PDF Format

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader