Effective synchronization removal for Java

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Effective synchronization removal for Java

Full text

Pdf (820 KB)

Source

Conference on Programming Language Design and Implementation archive
Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation table of contents

Vancouver, British Columbia, Canada

Pages: 208 - 218

Year of Publication: 2000

ISBN:1-58113-199-2

Also published in ...

Author

Erik Ruf

Microsoft Research, Redmond, WA

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 76, Citation Count: 58

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/349299.349327 What is a DOI?

ABSTRACT

We 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 that escape their allocating threads. It makes use of a compact, equivalence-class-based representation that eliminates the need for fixed point operations during the analysis. We describe and evaluate the performance of an implementation in the Marmot native Java compiler. For the benchmark programs examined, the optimization removes 100% of the dynamic synchronization operations in single-threaded programs, and 0-99% in multi-threaded programs, at a low cost in additional compilation time and code growth.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	ACSE99	Jonathan Aldrich , Craig Chambers , Emin Gün Sirer , Susan J. Eggers, Static Analyses for Eliminating Unnecessary Synchronization from Java Programs, Proceedings of the 6th International Symposium on Static Analysis, p.19-38, September 22-24, 1999
	ASU86	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	BH99	Jeff Bogda , Urs Hölzle, Removing unnecessary synchronization in Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.35-46, November 01-05, 1999, Denver, Colorado, United States
	BKMS98	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
	Bla99	Bruno Blanchet, Escape analysis for object-oriented languages: application to Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.20-34, November 01-05, 1999, Denver, Colorado, United States
	BS96	David F. Bacon , Peter F. Sweeney, Fast static analysis of C++ virtual function calls, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.324-341, October 06-10, 1996, San Jose, California, United States
	CFRW91	Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
	CGS+99	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
	CmH00	Ben-Chung Cheng , Wen-Mei W. Hwu, Modular interprocedural pointer analysis using access paths: design, implementation, and evaluation, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.57-69, June 18-21, 2000, Vancouver, British Columbia, Canada
	CRL99	Ramkrishna Chatterjee , Barbara G. Ryder , William A. Landi, Relevant context inference, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.133-146, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292554]
	DR96	Pedro C. Diniz , Martin C. Rinard, Lock Coarsening: Eliminating Lock Overhead in Automatically Parallelized Object-Based Programs, Proceedings of the 9th International Workshop on Languages and Compilers for Parallel Computing, p.285-299, August 08-10, 1996
	DR97	Pedro Diniz , Martin Rinard, Synchronization transformations for parallel computing, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.187-200, January 15-17, 1997, Paris, France [doi>10.1145/263699.263718]
	FKR+00	Robert Fitzgerald , Todd B. Knoblock , Erik Ruf , Bjarne Steensgaard , David Tarditi, Marmot: an optimizing compiler for Java, Software—Practice & Experience, v.30 n.3, p.199-232, Mar.1.2000 [doi>10.1002/(SICI)1097-024X(200003)30:3<199::AID-SPE296>3.0.CO;2-2]
	FRD00	Manuel Fähndrich , Jakob Rehof , Manuvir Das, Scalable context-sensitive flow analysis using instantiation constraints, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.253-263, June 18-21, 2000, Vancouver, British Columbia, Canada
	GJS96	James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
	HH98	Rebecca Hasti , Susan Horwitz, Using static single assignment form to improve flow-insensitive pointer analysis, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.97-105, June 17-19, 1998, Montreal, Quebec, Canada
	Rin99	M. Rinard. Personal communication. 1999.
	SH97	Marc Shapiro , Susan Horwitz, Fast and accurate flow-insensitive points-to analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 15-17, 1997, Paris, France [doi>10.1145/263699.263703]
	SP81	M. Shark and A. Pnueli. Two approaches to interprocedural data flow analysis. In Program Flow Analysis: Theory and Applications, chapter 7, pages 189-284. Prentice-Hall, 1981.
	Ste96a	Bjarne Steensgaard, Points-to Analysis by Type Inference of Programs with Structures and Unions, Proceedings of the 6th International Conference on Compiler Construction, p.136-150, April 24-26, 1996
	Ste96b	Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
	Tse95	Chau-Wen Tseng, Compiler optimizations for eliminating barrier synchronization, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.144-155, July 19-21, 1995, Santa Barbara, California, United States
	WR99	John Whaley , Martin Rinard, Compositional pointer and escape analysis for Java programs, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.187-206, November 01-05, 1999, Denver, Colorado, United States

CITED BY 59

	Michael Hind, Pointer analysis: haven't we solved this problem yet?, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.54-61, June 2001, Snowbird, Utah, United States
	Martin Hirzel , Johannes Henkel , Amer Diwan , Michael Hind, Understanding the connectivity of heap objects, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
	Matthew B. Dwyer , John Hatcliff , Robby , Venkatesh Prasad Ranganath, Exploiting Object Escape and Locking Information in Partial-Order Reductions for Concurrent Object-Oriented Programs, Formal Methods in System Design, v.25 n.2-3, p.199-240, September-November 2004
	Craig Chambers, Staged compilation, ACM SIGPLAN Notices, v.37 n.3, March 2002
	Ana Milanova , Atanas Rountev , Barbara G. Ryder, Parameterized object sensitivity for points-to and side-effect analyses for Java, ACM SIGSOFT Software Engineering Notes, v.27 n.4, July 2002
	Kiyokuni Kawachiya , Akira Koseki , Tamiya Onodera, Lock reservation: Java locks can mostly do without atomic operations, ACM SIGPLAN Notices, v.37 n.11, November 2002
	Alexandru Salcianu , Martin Rinard, Pointer and escape analysis for multithreaded programs, ACM SIGPLAN Notices, v.36 n.7, p.12-23, July 2001
	Jonathan Aldrich , Emin Gün Sirer , Craig Chambers , Susan J. Eggers, Comprehensive synchronization elimination for Java, Science of Computer Programming, v.47 n.2-3, p.91-120, May 2003
	Carlos Varela , Gul Agha, Programming dynamically reconfigurable open systems with SALSA, ACM SIGPLAN Notices, v.36 n.12, December 2001
	Karen Zee , Martin Rinard, Write barrier removal by static analysis, ACM SIGPLAN Notices, v.37 n.11, November 2002
	Radu Rugina , Martin C. Rinard, Pointer analysis for structured parallel programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.1, p.70-116, January 2003
	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
	Atanas Rountev , Ana Milanova , Barbara G. Ryder, Fragment class analysis for testing of polymorphism in Java software, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
	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
	Bruno Blanchet, Escape analysis for Java^TM: Theory and practice, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.6, p.713-775, November 2003
	Atanas Rountev , Ana Milanova , Barbara G. Ryder, Points-to analysis for Java using annotated constraints, ACM SIGPLAN Notices, v.36 n.11, p.43-55, 11/01/2001
	Chandrasekhar Boyapati , Martin Rinard, A parameterized type system for race-free Java programs, ACM SIGPLAN Notices, v.36 n.11, p.56-69, 11/01/2001
	Christoph von Praun , Thomas R. Gross, Static conflict analysis for multi-threaded object-oriented programs, ACM SIGPLAN Notices, v.38 n.5, May 2003
	Frédéric Vivien , Martin Rinard, Incrementalized pointer and escape analysis, ACM SIGPLAN Notices, v.36 n.5, p.35-46, May 2001
	Erik Johansson , Konstantinos Sagonas , Jesper Wilhelmsson, Heap architectures for concurrent languages using message passing, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
	Erik M. Nystrom , Hong-Seok Kim , Wen-mei W. Hwu, Importance of heap specialization in pointer analysis, Proceedings of the ACM-SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, June 07-08, 2004, Washington DC, USA
	Mangala Gowri Nanda , S. Ramesh, Pointer analysis of multithreaded Java programs, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida
	Konstantinos Sagonas , Jesper Wilhelmsson, Message analysis-guided allocation and low-pause incremental garbage collection in a concurrent language, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
	Ana Milanova , Atanas Rountev , Barbara G. Ryder, Parameterized object sensitivity for points-to analysis for Java, ACM Transactions on Software Engineering and Methodology (TOSEM), v.14 n.1, p.1-41, January 2005
	Jong-Deok Choi , Keunwoo Lee , Alexey Loginov , Robert O'Callahan , Vivek Sarkar , Manu Sridharan, Efficient and precise datarace detection for multithreaded object-oriented programs, ACM SIGPLAN Notices, v.37 n.5, May 2002
	Fragment Class Analysis for Testing of Polymorphism in Java Software, IEEE Transactions on Software Engineering, v.30 n.6, p.372-387, June 2004
	Ittai Balaban , Frank Tip , Robert Fuhrer, Refactoring support for class library migration, ACM SIGPLAN Notices, v.40 n.10, October 2005
	Yichen Xie , Alex Aiken, Context- and path-sensitive memory leak detection, ACM SIGSOFT Software Engineering Notes, v.30 n.5, September 2005
	Bruno Dufour , Karel Driesen , Laurie Hendren , Clark Verbrugge, Dynamic metrics for java, ACM SIGPLAN Notices, v.38 n.11, November 2003
	C. Scott Ananian , Martin Rinard, Data size optimizations for java programs, ACM SIGPLAN Notices, v.38 n.7, July 2003
	Mark Christiaens , Koen De Bosschere, TRaDe, a topological approach to on-the-fly race detection in java programs, Proceedings of the Java^TM Virtual Machine Research and Technology Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.15-15, April 23-24, 2001, Monterey, California
	Jeff Bogda , Ambuj Singh, Can a shape analysis work at run-time?, Proceedings of the Java^TM Virtual Machine Research and Technology Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.2-2, April 23-24, 2001, Monterey, California
	Konstantinos Sagonas , Jesper Wilhelmsson, Efficient memory management for concurrent programs that use message passing, Science of Computer Programming, v.62 n.2, p.98-121, 1 October 2006
	Manu Sridharan , Rastislav Bodík, Refinement-based context-sensitive points-to analysis for Java, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Pramod G. Joisha, Compiler optimizations for nondeferred reference: counting garbage collection, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	Erik Corry, Optimistic stack allocation for java-like languages, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	Richard Carlsson , Konstantinos Sagonas , Jesper Wilhelmsson, Message analysis for concurrent programs using message passing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.4, p.715-746, July 2006
	Lei Wang , Xikun Sun, Escape analysis for synchronization removal, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
	Mangala Gowri Nanda , S. Ramesh, Interprocedural slicing of multithreaded programs with applications to Java, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.6, p.1088-1144, November 2006
	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, ACM SIGPLAN Notices, v.42 n.6, June 2007
	Hiroyasu Nishiyama, Detecting data races using dynamic escape analysis based on read barrier, Proceedings of the 3rd conference on Virtual Machine Research And Technology Symposium, p.10-10, May 06-07, 2004, San Jose, California
	Martin Hirzel , Daniel Von Dincklage , Amer Diwan , Michael Hind, Fast online pointer analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.2, p.11-es, April 2007
	Patricia M. Hill , Fausto Spoto, Deriving escape analysis by abstract interpretation, Higher-Order and Symbolic Computation, v.19 n.4, p.415-463, December 2006
	Kyungwoo Lee , Samuel P. Midkiff, A two-phase escape analysis for parallel java programs, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA
	Yichen Xie , Alex Aiken, Saturn: A scalable framework for error detection using Boolean satisfiability, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.3, p.16-es, May 2007
	Chris Lattner , Andrew Lenharth , Vikram Adve, Making context-sensitive points-to analysis with heap cloning practical for the real world, ACM SIGPLAN Notices, v.42 n.6, June 2007
	Kyungwoo Lee , Xing Fang , Samuel P. Midkiff, Practical escape analyses: how good are they?, Proceedings of the 3rd international conference on Virtual execution environments, June 13-15, 2007, San Diego, California, USA
	Kyungwoo Lee , Qasim Ali , Samuel P. Midkiff, Efficient Classloading Strategies for Interprocedural Analyses in the Presence of Dynamic Classloading, Proceedings of the 5th International Workshop on Dynamic Analysis, p.6, May 20-26, 2007
	Mark Stoodley , Vijay Sundaresan, Automatically Reducing Repetitive Synchronization with a Just-in-Time Compiler for Java, Proceedings of the international symposium on Code generation and optimization, p.27-36, March 20-23, 2005
	Thomas Kotzmann , Hanspeter Mossenbock, Run-Time Support for Optimizations Based on Escape Analysis, Proceedings of the International Symposium on Code Generation and Optimization, p.49-60, March 11-14, 2007
	Ana Milanova, Composition inference for UML class diagrams, Automated Software Engineering, v.14 n.2, p.179-213, June 2007
	Guoqing Xu , Atanas Rountev, Merging equivalent contexts for scalable heap-cloning-based context-sensitive points-to analysis, Proceedings of the 2008 international symposium on Software testing and analysis, July 20-24, 2008, Seattle, WA, USA
	Mario Méndez , Jorge Navas , Manuel V. Hermenegildo, An Efficient, Parametric Fixpoint Algorithm for Analysis of Java Bytecode, Electronic Notes in Theoretical Computer Science (ENTCS), v.190 n.1, p.51-66, July, 2007
	Mariana Sharp , Atanas Rountev, Static Analysis of Object References in RMI-Based Java Software, IEEE Transactions on Software Engineering, v.32 n.9, p.664-681, September 2006
	Hyun-Goo Kang , Taisook Han, A bottom-up pointer analysis using the update history, Information and Software Technology, v.51 n.4, p.691-707, April, 2009
	Dennis Giffhorn , Christian Hammer, Precise slicing of concurrent programs, Automated Software Engineering, v.16 n.2, p.197-234, June 2009
	Jonas Lundberg , Tobias Gutzmann , Marcus Edvinsson , Welf Löwe, Fast and precise points-to analysis, Information and Software Technology, v.51 n.10, p.1428-1439, October, 2009
	Charles Zhang, FlexSync: An aspect-oriented approach to Java synchronization, Proceedings of the 2009 IEEE 31st International Conference on Software Engineering, p.375-385, May 16-24, 2009
	Liqiang Wang , Scott D. Stoller, Runtime Analysis of Atomicity for Multithreaded Programs, IEEE Transactions on Software Engineering, v.32 n.2, p.93-110, February 2006