Jeff Bogda
Urs Hölzle
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%.
- 1.Ole Agesen, David Detlefs, Alex Garthwaite, Ross Knippel, Y. S. Ramakrishna, and Derek White. An Efficient Meta-Lock for Implementing Ubiquitous Synchronization. In Proceedings of Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA '99), Denver, Colorado, 1-5 November 1999. Google Scholar
Digital Library
- 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. Google ScholarDigital Library
- 3.David E Bacon. Fast and Efficient Optimization of Statically Typed Object-Oriented Languages. Ph.D. thesis, University of California, Berkeley, October 1997. Google ScholarDigital Library
- 4.David F. Bacon, Ravi Konuru, Chet Murthy, and Mauricio Serrano. Thin Locks: Featherweight Synchronization for Java. in Proceedings of the A CM SIGPLAN '98 Conference on Programming Language Design and Implementation (PLDI '98), pages 258-268, Montreal, Canada, May 1998. Google ScholarDigital Library
- 5.Bruno Blanchet. Escape analysis: Correctness Proof, Implementation and Experimental Results. in Conference Record of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '98), pages 25-37, San Diego, California, 19-21 January 1998. Google ScholarDigital Library
- 6.J.-D. Choi, M. Gupta, M. Serrano, V. C. Sreedhar, and S. Midkiff. Escape Analysis for Java. In Proceedings of Object- Oriented Programming, Systems, Languages, and Applications (OOPSLA "99), Denver, Colorado, 1-5 November t999. Google ScholarDigital Library
- 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.Google Scholar
- 8.Pedro Diniz and Martin Rinard. Lock Coarsening: Eliminating Lock Overhead in Automatically Parallelized Object- Based Programs. In Journal of Parallel and Distributed Computing 49(2), March 1998. Google ScholarDigital Library
- 9.Julian Dolby. Automatic Inline Allocation of Objects. In Proceedings of the 1997 A CM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '97), pages 7-17, Las Vegas, Nevada, June 1997. Google ScholarDigital Library
- 10.Julian Dolby and Andrew A. Chien. An Evaluation of Automatic Object lnline Allocation Techniques. In Proceedings of Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA '98), pages 1-20, 1998. Google ScholarDigital Library
- 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.Google Scholar
- 12.Robert Fitzgerald, Todd B. Knoblock, Erik Ruf, Bjame Steensgaard, and David Tarditi. Marmot: an Optimizing Compiler for Java. Microsoft Technical Report, November 1998.Google Scholar
- 13.David Gay and Bjarne Steensgaard. Stack Allocating Objects In Java. Microsoft Technical Report, November 1998.Google Scholar
- 14.Rakesh Ghiya and Laurie J. Hendren. Is it a Tree, a DAG, or a Cyclic Graph? A Shape Analysis for Heap-Directed Pointers in C. In Conference Record of the 23rd ACM SIGPLAN- SIGACT Symposium on Principles of Programming Languages (POPL '96), pages 1-15, St. Petersburg Beach, Florida, 21-24 January 1996. Google ScholarDigital Library
- 15.James Gosling, Bill Joy, and Guy Steele. The java Language Specification. Addison-Wesley: Berkeley, California, 1996. Google ScholarDigital Library
- 16.Allan Heydon and Marc Najork. Performance Limitations of the Java Core Libraries. In Proceedings of the 1999 ACM Java Grande Conference, pages 35-41, June 1999. Google ScholarDigital Library
- 17.Java Generic Library (JGL). http://www.objectspace.corn/ products/jgl.Google Scholar
- 18.JavaClass parsing library, http://www.inf.fu-berlin.de/-dahrn/ JavaClass.Google Scholar
- 19.JavaCUP parser generator, http://www.cs.princeton.edu/ -appel/moderrffj ava/CUP.Google Scholar
- 20.JLex lexieal analyzer generator, http://www.cs.princeton.edu/ -appel/modem/j ava/JLex.Google Scholar
- 21.Holger Kienle and Urs HOlzle. j2s: A SUIF Java compiler. In Proceedings of the Second SUIF Compiler Workshop, pages 8-15, August 1997. Also available as Technical Report TRCS98-18, Department of Computer Science, University of California, Santa Barbara. Google ScholarDigital Library
- 22.Andreas Krall. Efficient Java VM Just-in-Time Compilation. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques (PACT '98), pages 12-18, Paris, France, October 1998. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 24.Tim Lindholm and Frank Yellin. The Java Virtual Machine Specification. Addison-Wesley: Berkeley, California, 1997. Google ScholarDigital Library
- 25.C. E. McDowell. Reducing garbage in Java. In ACM SIG- PLAN Notices 33(9), September 1998. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 27.Cristina Ruggieri and Thomas E Murtagh. Lifetime Analysis of Dynamically Allocated Objects. In Conference Record of the Fifteenth Annual ACM Symposium on Principles of Programming Languages, pages 285-293, San Diego, California, 13-15 January 1988. Google ScholarDigital Library
- 28.Radu Rugina and Martin Rinard. Pointer Analysis for Multithreaded Programs. In Proceedings of the 1999 ACM SIG- PLAN Conference on Programming Language Design and Implementation (PLDI '99), pages 77-90, Atlanta, GA, May, 1999. Google ScholarDigital Library
- 29.Mooly Sagiv, Thomas Reps, and Reinhard Wilhelm. Solving Shape-Analysis Problems in Languages with Destructive Updating. In Conference Record of the 23rd ACM SIGPLAN- SIGACT Symposium on Principles of Programming Languages (POPL '96), pages 16-31, St. Petersburg Beach, Florida, 21-24 January 1996. Google ScholarDigital Library
- 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.Google Scholar
- 31.Robert P. Wilson and Monica S. Lam. Efficient Context-Sensitive Pointer Analysis for C Programs. In Proceedings of the 1995 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '95), pages 1-12, La Jolla, California, 18-21 June 1995. Google ScholarDigital Library
Index Terms
- Removing unnecessary synchronization in Java
Recommendations
Effective synchronization removal for Java
PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementationWe present a new technique for removing unnecessary synchronization operations from statically compiled Java programs. Our approach improves upon current efforts based on escape analysis, as it can eliminate synchronization operations even on objects ...
Removing unnecessary synchronization in Java
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. ...
Comments