The Compressor: concurrent, incremental, and parallel compaction

Abstract

The widely used Mark-and-Sweep garbage collector has a drawback in that it does not move objects during collection. As a result, large long-running realistic applications, such as Web application servers, frequently face the fragmentation problem. To eliminate fragmentation, a heap compaction is run periodically. However, compaction typically imposes very long undesirable pauses in the application. While efficient concurrent collectors are ubiquitous in production runtime systems (such as JVMs), an efficient non-intrusive compactor is still missing.In this paper we present the Compressor, a novel compaction algorithm that is concurrent, parallel, and incremental. The Compressor compacts the entire heap to a single condensed area, while preserving the objects' order, but reduces pause times significantly, thereby allowing acceptable runs on large heaps. Furthermore, the Compressor is the first compactor that requires only a single heap pass. As such, it is the most efficient compactors known today, even when run in a parallel Stop-the-World manner (i.e., when the program threads are halted). Thus, to the best of our knowledge, the Compressor is the most efficient compactor known today. The Compressor was implemented on a Jikes Research RVM and we provide measurements demonstrating its qualities.

References

1. Diab Abuaiadh, Yoav Ossia, Erez Petrank, and Uri Silbershtein. An efficient parallel heap compaction algorithm. In OOPSLA {21}.]]
2. 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.]]
3. Andrew W. Appel, John R. Ellis, and Kai Li. Real-time concurrent collection on stock multiprocessors. ACM SIGPLAN Notices, 23(7):11--20, 1988.]]
4. Andrew W. Appel and Kai Li. Virtual memory primitives for user programs. ACM SIGPLAN Notices, 26(4):96--107, 1991. Also in SIGARCH Computer Architecture News 19 (2) and SIGOPS Operating Systems Review 25.]]
5. Hezi Azatchi, Yossi Levanoni, Harel Paz, and Erez Petrank. An onthe-fly mark and sweep garbage collector based on sliding view. In OOPSLA {20}.]]
6. 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), San Diego, CA, June 2003. ACM Press.]]
7. Henry G. Baker. List processing in real-time on a serial computer. Communications of the ACM, 21(4):280--94, 1978. Also AI Laboratory Working Paper 139, 1977.]]
8. Ori Ben-Yitzhak, Irit Goft, Elliot Kolodner, Kean Kuiper, and Victor Leikehman. An algorithm for parallel incremental compaction. In David Detlefs, editor, ISMM'02 Proceedings of the Third International Symposium on Memory Management, ACM SIGPLAN Notices, pages 100--105, Berlin, June 2002. ACM Press.]]
9. 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, Edinburgh, May 2004.]]
10. Hans-Juergen Boehm, Alan J. Demers, and Scott Shenker. Mostly parallel garbage collection. ACM SIGPLAN Notices, 26(6):157--164, 1991.]]
11. Spec: The Standard Performance Evaluation Corporation. http://www.spec.org/.]]
12. Christine Flood, Dave Detlefs, Nir Shavit, and Catherine Zhang. Parallel garbage collection for shared memory multiprocessors. In Usenix Java Virtual Machine Research and Technology Symposium (JVM '01), Monterey, CA, April 2001.]]
13. Matthew Hertz, Yi Feng, and Emery D. Berger. Garbage collection without paging. In Proceedings of SIGPLAN 2005 Conference on Programming Languages Design and Implementation, ACM SIGPLAN Notices, Chicago, IL, June 2005. ACM Press.]]
14. Richard L. Hudson and J. Eliot B. Moss. Sapphire: Copying GC without stopping the world. In Joint ACM Java Grande - ISCOPE 2001 Conference, Stanford University, CA, June 2001.]]
15. Richard E. Jones. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, Chichester, July 1996. With a chapter on Distributed Garbage Collection by R. Lins.]]
16. H. B. M. Jonkers. A fast garbage compaction algorithm. Information Processing Letters, 9(1):25--30, July 1979.]]
17. Bernard Lang and Francis Dupont. Incremental incrementally compacting garbage collection. In SIGPLAN'87 Symposium on Interpreters and Interpretive Techniques, volume 22(7) of ACM SIGPLAN Notices, pages 253--263. ACM Press, 1987.]]
18. Martin Larose and Marc Feeley. A compacting incremental collector and its performance in a production quality compiler. In Richard Jones, editor, ISMM'98 Proceedings of the First International Symposium on Memory Management, volume 34(3) of ACM SIGPLAN Notices, pages 1--9, Vancouver, October 1998. ACM Press.]]
19. F. Lockwood Morris. A time- and space-efficient garbage compaction algorithm. Communications of the ACM, 21(8):662--5, 1978.]]
20. OOPSLA'03 ACM Conference on Object-Oriented Systems, Languages and Applications, ACM SIGPLAN Notices, Anaheim, CA, November 2003. ACM Press.]]
21. OOPSLA'04 ACM Conference on Object-Oriented Systems, Languages and Applications, ACM SIGPLAN Notices, Vancouver, October 2004. ACM Press.]]
22. Yoav Ossia, Ori Ben-Yitzhak, and Marc Segal. Mostly concurrent compaction for mark-sweep GC. In Amer Diwan, editor, ISMM'04 Proceedings of the Third International Symposium on Memory Management, ACM SIGPLAN Notices, Vancouver, October 2004. ACM Press.]]
23. Narendran Sachindran and Eliot Moss. MarkCopy: Fast copying GC with less space overhead. In OOPSLA {20}.]]
24. Narendran Sachindran, J. Eliot B. Moss, and Emery D. Berger. MC2: High-performance garbage collection for memory-constrained environments. In OOPSLA {21}.]]
25. Dacapo Project: The DaCapo Benchmark Suite. http://wwwali.cs.umass.edu/dacapo/index.html.]]

Index Terms

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

          • Garbage collection