Dynamic optimization for efficient strong atomicity

ABSTRACT

Transactional memory (TM) is a promising concurrency control alternative to locks. Recent work has highlighted important memory model issues regarding TM semantics and exposed problems in existing TM implementations. For safe, managed languages such as Java, there is a growing consensus towards strong atomicity semantics as a sound, scalable solution. Strong atomicity has presented a challenge to implement efficiently because it requires instrumentation of non-transactional memory accesses, incurring significant overhead even when a program makes minimal or no use of transactions. To minimize overhead, existing solutions require either a sophisticated type system, specialized hardware, or static whole-program analysis. These techniques do not translate easily into a production setting on existing hardware. In this paper, we present novel dynamic optimizations that significantly reduce strong atomicity overheads and make strong atomicity practical for dynamic language environments. We introduce analyses that optimistically track which non-transactional memory accesses can avoid strong atomicity instrumentation, and we describe a lightweight speculation and recovery mechanism that applies these analyses to generate speculatively-optimized but safe code for strong atomicity in a dynamically-loaded environment. We show how to implement these mechanisms efficiently by leveraging existing dynamic optimization infrastructure in a Java system. Measurements on a set of transactional and non-transactional Java workloads demonstrate that our techniques substantially reduce the overhead of strong atomicity from a factor of 5x down to 10% or less over an efficient weak atomicity baseline.

REFERENCES

• 1: Martín Abadi , Andrew Birrell , Tim Harris , Michael Isard, Semantics of transactional memory and automatic mutual exclusion, Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 07-12, 2008, San Francisco, California, USA
• 2: Ali-Reza Adl-Tabatabai , Brian T. Lewis , Vijay Menon , Brian R. Murphy , Bratin Saha , Tatiana Shpeisman, Compiler and runtime support for efficient software transactional memory, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 3: Milo Martin , Colin Blundell , E. Lewis, Subtleties of Transactional Memory Atomicity Semantics, IEEE Computer Architecture Letters, v.5 n.2, p.17, July 2006 [doi>10.1109/L-CA.2006.18]
• 4: Nikita Borisov , Rob Johnson , Naveen Sastry , David Wagner, Fixing races for fun and profit: how to abuse atime, Proceedings of the 14th conference on USENIX Security Symposium, p.20-20, July 31-August 05, 2005, Baltimore, MD
• 5: Chandrasekhar Boyapati , Robert Lee , Martin Rinard, Ownership types for safe programming: preventing data races and deadlocks, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 6: Chandrasekhar Boyapati , Alexandru Salcianu , William Beebee, Jr. , Martin Rinard, Ownership types for safe region-based memory management in real-time Java, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 7: Jong-Deok Choi , Manish Gupta , Mauricio J. Serrano , Vugranam C. Sreedhar , Samuel P. Midkiff, Stack allocation and synchronization optimizations for Java using escape analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.6, p.876-910, November 2003 [doi>10.1145/945885.945892]
• 8: Jong-Deok Choi , Keunwoo Lee , Alexey Loginov , Robert O'Callahan , Vivek Sarkar , Manu Sridharan, Efficient and precise datarace detection for multithreaded object-oriented programs, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 9: Dave Clarke , Michael Richmond , James Noble, Saving the world from bad beans: deployment-time confinement checking, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 10: David G. Clarke , John M. Potter , James Noble, Ownership types for flexible alias protection, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.48-64, October 18-22, 1998, Vancouver, British Columbia, Canada
• 11: Jeffrey Dean , David Grove , Craig Chambers, Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis, Proceedings of the 9th European Conference on Object-Oriented Programming, p.77-101, August 07-11, 1995
• 12: Julian Dolby , Andrew Chien, An automatic object inlining optimization and its evaluation, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.345-357, June 18-21, 2000, Vancouver, British Columbia, Canada
• 13: Dan Grossman , Jeremy Manson , William Pugh, What do high-level memory models mean for transactions?, Proceedings of the 2006 workshop on Memory system performance and correctness, October 22-22, 2006, San Jose, California [doi>10.1145/1178597.1178609]
• 14: Tim Harris , Keir Fraser, Language support for lightweight transactions, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 15: Tim Harris , Simon Marlow , Simon Peyton-Jones , Maurice Herlihy, Composable memory transactions, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065952]
• 16: Tim Harris , Mark Plesko , Avraham Shinnar , David Tarditi, Optimizing memory transactions, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 17: David L. Heine , Monica S. Lam, A practical flow-sensitive and context-sensitive C and C++ memory leak detector, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 18: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 19: Benjamin Hindman , Dan Grossman, Atomicity via source-to-source translation, Proceedings of the 2006 workshop on Memory system performance and correctness, October 22-22, 2006, San Jose, California [doi>10.1145/1178597.1178611]
• 20: HINDMAN, B., AND GROSSMAN, D. Strong atomicity for Java without virtual-machine support. Tech. Rep. UW-CSE-06-05-01, May 2006.
• 21: INTEL CORPORATION. Intel 64 and IA-32 Architectures Software Developer's Manual Volume 3A: System Programming Guide.
• 22: Kazuaki Ishizaki , Motohiro Kawahito , Toshiaki Yasue , Hideaki Komatsu , Toshio Nakatani, A study of devirtualization techniques for a Java Just-In-Time compiler, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.294-310, October 2000, Minneapolis, Minnesota, United States
• 23: Thomas Kotzmann , Hanspeter Mössenböck, Escape analysis in the context of dynamic compilation and deoptimization, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA [doi>10.1145/1064979.1064996]
• 24: Ondrej Lhoták , Laurie Hendren, Run-time evaluation of opportunities for object inlining in Java, Proceedings of the 2002 joint ACM-ISCOPE conference on Java Grande, p.175-184, November 03-05, 2002, Seattle, Washington, USA [doi>10.1145/583810.583830]
• 25: Vijay Menon , Steven Balensiefer , Tatiana Shpeisman , Ali-Reza Adl-Tabatabai , Richard L. Hudson , Bratin Saha , Adam Welc, Practical weak-atomicity semantics for java stm, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378588]
• 26: Katherine F. Moore , Dan Grossman, High-level small-step operational semantics for transactions, Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 07-12, 2008, San Francisco, California, USA
• 27: Mayur Naik , Alex Aiken , John Whaley, Effective static race detection for Java, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 28: Igor Pechtchanski , Vivek Sarkar, Dynamic optimistic interprocedural analysis: a framework and an application, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.195-210, October 14-18, 2001, Tampa Bay, FL, USA
• 29: Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multi-threaded programs, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.27-37, October 05-08, 1997, Saint Malo, France
• 30: Tatiana Shpeisman , Vijay Menon , Ali-Reza Adl-Tabatabai , Steven Balensiefer , Dan Grossman , Richard L. Hudson , Katherine F. Moore , Bratin Saha, Enforcing isolation and ordering in STM, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 31: STANDARD PERFORMANCE EVALUATION CORPORATION. SPEC JVM98, 1998. See http://www.spec.org/jvm98.
• 32: STANDARD PERFORMANCE EVALUATION CORPORATION. SPEC JBB2000, 2000. See http://www.spec.org/jbb2000.
• 33: Jan Vitek , Boris Bokowski, Confined types, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.82-96, November 01-05, 1999, Denver, Colorado, United States
• 34: Frédéric Vivien , Martin Rinard, Incrementalized pointer and escape analysis, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.35-46, June 2001, Snowbird, Utah, United States
• 35: Christoph von Praun , Thomas R. Gross, Object race detection, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.70-82, October 14-18, 2001, Tampa Bay, FL, USA
• 36: Christoph von Praun , Thomas R. Gross, Static conflict analysis for multi-threaded object-oriented programs, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 37: Christian Wimmer , Hanspeter Mössenböck, Automatic feedback-directed object inlining in the java hotspot™ virtual machine, Proceedings of the 3rd international conference on Virtual execution environments, June 13-15, 2007, San Diego, California, USA [doi>10.1145/1254810.1254813]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

General Terms:
Algorithms, Design, Experimentation, Languages, Measurement, Performance

Keywords:
code generation, compiler optimizations, dynamic optimizations, strong atomicity, transactional memory, virtual machines