Barriers: friend or foe?

ABSTRACT

Modern garbage collectors rely on read and write barriers imposed on heap accesses by the mutator, to keep track of references between different regions of the garbage collected heap, and to synchronize actions of the mutator with those of the collector. It has been a long-standing untested assumption that barriers impose significant overhead to garbage-collected applications. As a result, researchers have devoted effort to development of optimization approaches for elimination of unnecessary barriers, or proposed new algorithms for garbage collection that avoid the need for barriers while retaining the capability for independent collection of heap partitions. On the basis of the results presented here, we dispel the assumption that barrier overhead should be a primary motivator for such efforts.

We present a methodology for precise measurement of mutator overheads for barriers associated with mutator heap accesses. We provide a taxonomy of different styles of barrier and measure the cost of a range of popular barriers used for different garbage collectors within Jikes RVM. Our results demonstrate that barriers impose surprisingly low cost on the mutator, though results vary by architecture. We found that the average overhead for a reasonable generational write barrier was less than 2% on average, and less than 6% in the worst case. Furthermore, we found that the average overhead of a read barrier consisting of just an unconditional mask of the low order bits read on the PowerPC was only 0.85%, while on the AMD it was 8.05%. With both read and write barriers, we found that second order locality effects were sometimes more important than the overhead of the barriers themselves, leading to counter-intuitive speedups in a number of situations.

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, 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
• 2: 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]
• 3: Matthew Arnold , Stephen Fink , David Grove , Michael Hind , Peter F. Sweeney, Adaptive optimization in the Jalapeño JVM, ACM SIGPLAN Notices, v.35 n.10, p.47-65, Oct. 2000
• 4: 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
• 5: David F. Bacon , Perry Cheng , V. T. Rajan, A real-time garbage collector with low overhead and consistent utilization, ACM SIGPLAN Notices, v.38 n.1, p.285-298, January 2003
• 6: Stephen M Blackburn , Kathryn S. McKinley, In or out?: putting write barriers in their place, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
• 7: Stephen M. Blackburn , Kathryn S. McKinley, Ulterior reference counting: fast garbage collection without a long wait, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 8: 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
• 9: Stephen M Blackburn , Richard Jones , Kathryn S. McKinley , J Eliot B Moss, Beltway: getting around garbage collection gridlock, ACM SIGPLAN Notices, v.37 n.5, May 2002
• 10: Kumar Brahnmath , Nathaniel Nystrom , Antony L. Hosking , Quintin I. Cutts, Swizzle Barrier Optimizations for Orthogonal Persistence in Java, Proceedings of the 8th International Workshop on Persistent Object Systems (POS8) and Proceedings of the 3rd International Workshop on Persistence and Java (PJW3): Advances in Persistent Object Systems, p.268-278, January 1999
• 11: 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]
• 12: Patrick J. Caudill , Allen Wirfs-Brock, A third generation Smalltalk-80 implementation, ACM SIGPLAN Notices, v.21 n.11, p.119-130, Nov. 1986
• 13: Hirzel, M., Diwan, A., and Hertz, M. Connectivity-based garbage collection. In pp. 359--373.
• 14: Hosking, A. L., and Hudson, R. L. Remembered sets can also play cards. In Proceedings of the OOPSLA Workshop on Memory Management and Garbage Collection (Washington, DC, Sept.). 1993.
• 15: Antony L. Hosking , J. Eliot B. Moss, Protection traps and alternatives for memory management of an object-oriented language, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.106-119, December 05-08, 1993, Asheville, North Carolina, United States
• 16: Antony L. Hosking , J. Eliot B. Moss , Darko Stefanovic, A comparative performance evaluation of write barrier implementation, conference proceedings on Object-oriented programming systems, languages, and applications, p.92-109, October 18-22, 1992, Vancouver, British Columbia, Canada
• 17: Antony L. Hosking , Nathaniel Nystrom , Quintin I. Cutts , Kumar Brahnmath, Optimizing the Read and Write Barriers for Orthogonal Persistence, Proceedings of the 8th International Workshop on Persistent Object Systems (POS8) and Proceedings of the 3rd International Workshop on Persistence and Java (PJW3): Advances in Persistent Object Systems, p.149-159, January 1999
• 18: 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
• 19: Proceedings of the ACM International Symposium on Memory Management (Vancouver, Canada, Oct., 1998). ACM SIGPLAN Notices 34, 3 (Mar. 1999).
• 20: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 21: Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (Anaheim, California, Nov.). ACM SIGPLAN Notices 38, 11 (Nov. 2003).
• 22: Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (Denver, Colorado, Nov.). ACM SIGPLAN Notices 34, 10 (Oct. 1999).
• 23: Pettersson, M. Linux Intel/x86 performance counters, 2003 http://user.it.uu.se/mikpe/linux/perfctr/.
• 24: David J. Roth , David S. Wise, One-bit counts between unique and sticky, Proceedings of the 1st international symposium on Memory management, p.49-56, October 17-19, 1998, Vancouver, British Columbia, Canada
• 25: Jacob Seligmann , Steffen Grarup, Incremental Mature Garbage Collection Using the Train Algorithm, Proceedings of the 9th European Conference on Object-Oriented Programming, p.235-252, August 07-11, 1995
• 26: Patrick Sobalvarro, A Lifetime-based Garbage Collector for LISP Systems on General- Purpose Computers, Massachusetts Institute of Technology, Cambridge, MA, 1988
• 27: SPECjvm98 benchmarks, 1998.http://www.spec.org/osg/jvm98.
• 28: SPECjbb2000 benchmarks, 2000.http://www.spec.org/jbb2000.
• 29: 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
• 30: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.157-167, April 1984
• 31: P. R. Wilson , T. G. Moher, A “card-marking” scheme for controlling intergenerational references in generation-based garbage collection on stock hardware, ACM SIGPLAN Notices, v.24 n.5, p.87-92, May 1989 [doi>10.1145/66068.66077]
• 32: P. R. Wilson , T. G. Moher, Design of the opportunistic garbage collector, ACM SIGPLAN Notices, v.24 n.10, p.23-35, Oct. 1989
• 33: Karen Zee , Martin Rinard, Write barrier removal by static analysis, ACM SIGPLAN Notices, v.37 n.11, November 2002
• 34: Zorn, B. Barrier methods for garbage collection. Tech. Rep. CU-CS-494-90, University of Colorado at Boulder, Nov. 1990.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments

General Terms:
Algorithms, Design, Languages, Performance

Keywords:
garbage collection, java, memory management, write barriers