Removing unnecessary synchronization in Java

ABSTRACT

Java programs perform many synchronization operations on data structures. Some of these synchronization are unnecessary; in particular, if an object is reachable only by a single thread, concurrent access is impossible and no synchronization is needed. We describe an interprocedural, flow- and context-insensitive dataflow analysis that finds such situations. A global optimizing transformation then eliminates synchronizations on these objects. For every program in our suite of ten Java benchmarks consisting of SPECjvm98 and others, our system optimizes over 90% of the alias sets containing at least one synchronized object. As a result, the dynamic frequency of synchronizations is reduced by up to 99%. For two benchmarks that perform synchronizations very frequently, this optimization leads to speedups of 36% and 20%.

REFERENCES

• 1: Ole Agesen , David Detlefs , Alex Garthwaite , Ross Knippel , Y. S. Ramakrishna , Derek White, An efficient meta-lock for implementing ubiquitous synchronization, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.207-222, November 01-05, 1999, Denver, Colorado, United States
• 2: Jonathan Aldrich, Craig Chambers, Emin Gun Sirer, and Susan Eggers. Static Analyses for Eliminating Unnecessary Synchronization from Java Programs. in Proceedings of Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA '99), Denver, Colorado, 1-5 November 1999.
• 3: David Francis Bacon , Susan L. Graham, Fast and effective optimization of statically typed object-oriented languages, 1997
• 4: David F. Bacon , Ravi Konuru , Chet Murthy , Mauricio Serrano, Thin locks: featherweight synchronization for Java, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.258-268, June 17-19, 1998, Montreal, Quebec, Canada
• 5: Bruno Blanchet, Escape analysis: correctness proof, implementation and experimental results, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-37, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268949]
• 6: Jong-Deok Choi , Manish Gupta , Mauricio Serrano , Vugranam C. Sreedhar , Sam Midkiff, Escape analysis for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-19, November 01-05, 1999, Denver, Colorado, United States
• 7: James C. Corbett. Using Shape Analysis to Reduce Finite- State Models of Concurrent Java Programs. Technical Report ICS-TR-98-20, Department of Information and Computer Science, University of Hawaii, October 14, 1998.
• 8: Pedro C. Diniz , Martin C. Rinard, Lock coarsening: eliminating lock overhead in automatically parallelized object-based programs, Journal of Parallel and Distributed Computing, v.49 n.2, p.218-244, March 15, 1998 [doi>10.1006/jpdc.1998.1441]
• 9: Julian Dolby, Automatic inline allocation of objects, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.7-17, June 16-18, 1997, Las Vegas, Nevada, United States
• 10: Julian Dolby , Andrew A. Chien, An evaluation of automatic object inline allocation techniques, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-20, October 18-22, 1998, Vancouver, British Columbia, Canada
• 11: Andrew Duncan, Bogdan Cocosel, Costin lancu, Holger Kiente, Radu P, ugina, Urs H61zle, and Martin Rinard. OSUIF: SUIF 2.0 With Objects. Overview paper from the SUIF Workshop at Stanford University, August 1997.
• 12: Robert Fitzgerald, Todd B. Knoblock, Erik Ruf, Bjame Steensgaard, and David Tarditi. Marmot: an Optimizing Compiler for Java. Microsoft Technical Report, November 1998.
• 13: David Gay and Bjarne Steensgaard. Stack Allocating Objects In Java. Microsoft Technical Report, November 1998.
• 14: Rakesh Ghiya , Laurie J. Hendren, Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-15, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237724]
• 15: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 16: Allan Heydon , Marc Najork, Performance limitations of the Java core libraries, Proceedings of the ACM 1999 conference on Java Grande, p.35-41, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304092]
• 17: Java Generic Library (JGL). http://www.objectspace.corn/ products/jgl.
• 18: JavaClass parsing library, http://www.inf.fu-berlin.de/-dahrn/ JavaClass.
• 19: JavaCUP parser generator, http://www.cs.princeton.edu/ -appel/moderrffj ava/CUP.
• 20: JLex lexieal analyzer generator, http://www.cs.princeton.edu/ -appel/modem/j ava/JLex.
• 21: Holger Kienle , Urs Holzle, j2s: A SUIF Java Compiler, University of California at Santa Barbara, Santa Barbara, CA, 1997
• 22: A. Krall, Efficient JavaVM Just-in-Time Compilation, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.205, October 12-18, 1998
• 23: Andreas Krall and Mark Probst. Monitors and Exceptions: How to implement Java efficiently. In S. Hassanzadeh and K. Schauser, editors, ACM 1998 Workshop on Java for High-Performance Network Computing, pages 15-24, Palo Alto, March 1998. ACM.
• 24: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 25: C. E. McDowell, Reducing garbage in Java, ACM SIGPLAN Notices, v.33 n.9, p.84-86, Sept. 1, 1998 [doi>10.1145/290229.290239]
• 26: Gilles Muller, BArbara Moura, Fabrice Bellard, and Charles Consel. Harissa: a Flexible and Efficient Java Environment Mixing Bytecode and Compiled Code. In Proceedings of the Third Conference on Object-Oriented Technologies and Systems (COOTS '97), pages 1-20, Berkeley, California, June 1997.
• 27: C. Ruggieri , T. P. Murtagh, Lifetime analysis of dynamically allocated objects, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.285-293, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73585]
• 28: Radu Rugina , Martin Rinard, Pointer analysis for multithreaded programs, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.77-90, May 01-04, 1999, Atlanta, Georgia, United States
• 29: Mooly Sagiv , Thomas Reps , Reinhard Wilhelm, Solving shape-analysis problems in languages with destructive updating, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.16-31, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237725]
• 30: SPEC Java virtual machine benchmark suite. Standard Performance Evaluation Corporation. SPECjvm98 Documentation, Release 1.0. August 1998. http:llwww.spec.org/osgljvm981 j vm98/doc/index.html.
• 31: Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.1-12, June 18-21, 1995, La Jolla, California, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Java

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

General Terms:
Design, Experimentation, Languages, Measurement, Performance, Standardization, Theory