An efficient parallel heap compaction algorithm

ABSTRACT

We propose a heap compaction algorithm appropriate for modern computing environments. Our algorithm is targeted at SMP platforms. It demonstrates high scalability when running in parallel but is also extremely efficient when running single-threaded on a uniprocessor. Instead of using the standard forwarding pointer mechanism for updating pointers to moved objects, the algorithm saves information for a pack of objects. It then does a small computation to process this information and determine each object's new location. In addition, using a smart parallel moving strategy, the algorithm achieves (almost) perfect compaction in the lower addresses of the heap, whereas previous algorithms achieved parallelism by compacting within several predetermined segments.

Next, we investigate a method that trades compaction quality for a further reduction in time and space overhead. Finally, we propose a modern version of the two-finger compaction algorithm. This algorithm fails, thus, re-validating traditional wisdom asserting that retaining the order of live objects significantly improves the quality of the compaction.

The parallel compaction algorithm was implemented on the IBM production Java Virtual Machine. We provide measurements demonstrating high efficiency and scalability. Subsequently, this algorithm has been incorporated into the IBM production JVM.

REFERENCES

• 1: java.lang class system. http://java.sun.com/j2se/1.3/docs/api/java/lang/System.html.
• 2: 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
• 3: David F. Bacon , Stephen J. Fink , David Grove, Space- and Time-Efficient Implementation of the Java Object Model, Proceedings of the 16th European Conference on Object-Oriented Programming, p.111-132, June 10-14, 2002
• 4: 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
• 5: Sam Borman. Sensible Sanitation - Understanding the IBM Java Garbage Collector (Part 1: Object allocation). http://www.ibm.com/developerworks/ibm/library/i-garbage1.
• 6: Sam Borman. Sensible Sanitation - Understanding the IBM Java Garbage Collector(Part 2: Garbage collection). http://www.ibm.com/developerworks/ibm/library/i-garbage2.
• 7: 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.
• 8: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 9: H. B. M. Jonkers. A fast garbage compaction algorithm. Information Processing Letters, 9(1):25--30, July 1979.
• 10: B. Lang , F. Dupont, Incremental incrementally compacting garbage collection, ACM SIGPLAN Notices, v.22 n.7, p.253-263, July 1987
• 11: Martin Larose , Marc Feeley, A compacting incremental collector and its performance in a production quality compiler, Proceedings of the 1st international symposium on Memory management, p.1-9, October 17-19, 1998, Vancouver, British Columbia, Canada
• 12: F. Lockwood Morris, A time- and space-efficient garbage compaction algorithm, Communications of the ACM, v.21 n.8, p.662-665, Aug. 1978 [doi>10.1145/359576.359583]
• 13: WebSphere Software platform. Ibm software products. http://www.ibm.com/software/info1/websphere/index.jsp.
• 14: SPECjbb2000 Java Business Benchmark. Standard Performance Evaluation Corporation (SPEC), Fairfax, VA, 1998. Available at http://www.spec.org/osg/jbb2000/.
• 15: SPECjvm98 Benchmarks. Standard Performance Evaluation Corporation (SPEC), Fairfax, VA, 1998. Available at http://www.spec.org/osg/jvm98/.
• 16: Trade3 Web Application Server Benchmark. IBM Software. Available at http://www.ibm.com/software/webservers/appserv/-benchmark3.html.

INDEX TERMS

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

General Terms:
Algorithms, Languages, Performance

Keywords:
JVM, compaction, garbage collection, java, parallel compaction, parallel garbage collection