Path specialization: reducing phased execution overheads

ABSTRACT

As garbage collected languages become widely used, the quest for reducing collection overheads becomes essential. In this paper, we propose a compiler optimization called path specialization that shrinks the cost of memory barriers for a wide variety of garbage collectors including concurrent, incremental, and real-time collectors. Path specialization provides a non-trivial decrease in write-barrier overheads and a drastic reduction of read-barrier overheads. It is effective when used with collectors that go through various phases each employing a different barrier behavior, and is most effective for collectors that have an idle phase, in which no barrier activity is required. We have implemented path specialization in the Bartok compiler and runtime for C# and tested it with state-of-the-art concurrent and real-time collectors, demonstrating its efficacy.

REFERENCES

• 1: Matthew Arnold , Barbara G. Ryder, A framework for reducing the cost of instrumented code, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.168-179, June 2001, Snowbird, Utah, United States
• 2: Hezi Azatchi , Yossi Levanoni , Harel Paz , Erez Petrank, An on-the-fly mark and sweep garbage collector based on sliding views, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 3: 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
• 4: 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]
• 5: Katherine Barabash , Ori Ben-Yitzhak , Irit Goft , Elliot K. Kolodner , Victor Leikehman , Yoav Ossia , Avi Owshanko , Erez Petrank, A parallel, incremental, mostly concurrent garbage collector for servers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.6, p.1097-1146, November 2005 [doi>10.1145/1108970.1108972]
• 6: Stephen M. Blackburn , Antony L. Hosking, Barriers: friend or foe?, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029891]
• 7: Hans-J. Boehm , Alan J. Demers , Scott Shenker, Mostly parallel garbage collection, ACM SIGPLAN Notices, v.26 n.6, p.157-164, June 1991
• 8: 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]
• 9: 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
• 10: 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]
• 11: Damien Doligez , Georges Gonthier, Portable, unobtrusive garbage collection for multiprocessor systems, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.70-83, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.174673]
• 12: Damien Doligez , Xavier Leroy, A concurrent, generational garbage collector for a multithreaded implementation of ML, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.113-123, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158611]
• 13: Tamar Domani , Elliot K. Kolodner , Erez Petrank, A generational on-the-fly garbage collector for Java, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.274-284, June 18-21, 2000, Vancouver, British Columbia, Canada
• 14: Tamar Domani , Elliot K. Kolodner , Ethan Lewis , Eliot E. Salant , Katherine Barabash , Itai Lahan , Yossi Levanoni , Erez Petrank , Igor Yanorer, Implementing an on-the-fly garbage collector for Java, Proceedings of the 2nd international symposium on Memory management, p.155-166, October 15-16, 2000, Minneapolis, Minnesota, United States
• 15: ECMA. Standard ECMA-335, Common Language Infrastructure (CLI). 2006.
• 16: Martin Hirzel and Trishul Chilimbi. Bursty tracing: A framework for low-overhead temporal profiling. In FDDO 2001.
• 17: Richard L. Hudson , J. Eliot B. Moss, Sapphire: copying GC without stopping the world, Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande, p.48-57, June 2001, Palo Alto, California, United States [doi>10.1145/376656.376810]
• 18: Galen C. Hunt , James R. Larus, Singularity: rethinking the software stack, ACM SIGOPS Operating Systems Review, v.41 n.2, p.37-49, April 2007 [doi>10.1145/1243418.1243424]
• 19: Pramod G. Joisha, Compiler optimizations for nondeferred reference: counting garbage collection, Proceedings of the 5th international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada [doi>10.1145/1133956.1133976]
• 20: H. T. Kung , S. W. Song, An efficient parallel garbage collection system and ITS correctness proof, Proceedings of the 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), p.120-131, September 30-October 31, 1977
• 21: Yossi Levanoni , Erez Petrank, An on-the-fly reference-counting garbage collector for java, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.1, p.1-69, January 2006 [doi>10.1145/1111596.1111597]
• 22: David A. Moon, Garbage collection in a large LISP system, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.235-246, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802040]
• 23: Filip Pizlo , Daniel Frampton , Erez Petrank , Bjarne Steensgaard, Stopless: a real-time garbage collector for multiprocessors, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada [doi>10.1145/1296907.1296927]
• 24: Tony Printezis , David Detlefs, A generational mostly-concurrent garbage collector, Proceedings of the 2nd international symposium on Memory management, p.143-154, October 15-16, 2000, Minneapolis, Minnesota, United States
• 25: 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]
• 26: Martin T. Vechev , David F. Bacon, Write barrier elision for concurrent garbage collectors, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029876]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.5 Object-oriented Programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Dynamic storage management

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
c#, garbage collection, memory management, read barriers, write barriers