Lock reservation: Java locks can mostly do without atomic operations

ABSTRACT

Because of the built-in support for multi-threaded programming, Java programs perform many lock operations. Although the overhead has been significantly reduced in the recent virtual machines, One or more atomic operations are required for acquiring and releasing an object's lock even in the fastest cases.This paper presents a novel algorithm called lock reservation. It exploits thread locality of Java locks, which claims that the locking sequence of a Java lock contains a very long repetition of a specific thread. The algorithm allows locks to be reserved for threads. When a thread attempts to acquire a lock, it can do without any atomic operation if the lock is reserved for the thread. Otherwise, it cancels the reservation and falls back to a conventional locking algorithm.We have evaluated an implementation of lock reservation in IBM's production virtual machine and compiler. The results show that it achieved performance improvements up to 53% in real Java programs.

REFERENCES

• 1: Sarita V. Adve , Kourosh Gharachorloo, Shared Memory Consistency Models: A Tutorial, Computer, v.29 n.12, p.66-76, December 1996 [doi>10.1109/2.546611]
• 2: 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
• 3: 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
• 4: E. Armstrong. HotSpot: A New Breed of Virtual Machine.
• 5: David Francis Bacon , Susan L. Graham, Fast and effective optimization of statically typed object-oriented languages, 1997
• 6: 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
• 7: D. F. Bacon and S. Fink. Personal Communication.
• 8: Brian N. Bershad , David D. Redell , John R. Ellis, Fast mutual exclusion for uniprocessors, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.223-233, October 12-15, 1992, Boston, Massachusetts, United States
• 9: 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
• 10: 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
• 11: Peter A. Buhr , Michel Fortier , Michael H. Coffin, Monitor classification, ACM Computing Surveys (CSUR), v.27 n.1, p.63-107, March 1995 [doi>10.1145/214037.214100]
• 12: 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
• 13: D. Dice. Implementing Fast Java Monitors with Relaxed-Locks. Proceedings of USENIX JVM '01, 79--90, 2001.
• 14: E. W. Dijkstra, Solution of a problem in concurrent programming control, Communications of the ACM, v.8 n.9, p.569, Sept. 1965 [doi>10.1145/365559.365617]
• 15: R. Eckstein, D. Collier-Brown, and P. Kelly. Using Samba. O'Reilly, 1999. http://www.oreilly.com/catalog/samba/chapter/book/ch05_05.html.
• 16: E. M. Gagnon and L. J. Hendren. SableVM: A Research Framework for the Efficient Execution of Java Bytecode Proceedings of USENIX JVM '01, 27--39, 2001.
• 17: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 18: C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]
• 19: Richard L. Hudson , J. Elliot Moss , Sreenivas Subramoney , Weldon Washburn, Cycles to recycle: garbage collection to the IA-64, Proceedings of the 2nd international symposium on Memory management, p.101-110, October 15-16, 2000, Minneapolis, Minnesota, United States
• 20: IBM developerWorks Java Technology Zone. http://www.ibm.com/developerworks/java/.
• 21: Intel Corporation. IA-32 Intel Architecture Software Developer's Manual Vol. 1--3. http://developer.intel.com/design/Pentium4/manuals/.
• 22: Intel Corporation. Intel Itanium Architecture Software Developer's Manual Vol. 1--3. http://developer.intel.com/design/itanium/manuals/.
• 23: Kazuaki Ishizaki , Motohiro Kawahito , Toshiaki Yasue , Mikio Takeuchi , Takeshi Ogasawara , Toshio Suganuma , Tamiya Onodera , Hideaki Komatsu , Toshio Nakatani, Design, implementation, and evaluation of optimizations in a just-in-time compiler, Proceedings of the ACM 1999 conference on Java Grande, p.119-128, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304111]
• 24: Java Community Process. JSR 133: Java Memory Model and Thread Specification Revision. http://jcp.org/jsr/detail/133.jsp.
• 25: T. Johnson and K. Harathi. Interruptible Critical Sections. Technical Report TR94007, University of Florida, 1994.
• 26: Kaffe.org. Developing Kaffe. http://www.kaffe.org/develop.html.
• 27: M. Kawahito. Personal Communication.
• 28: A. Krall and M. Probst. Monitors and Exceptions: How to Implement Java Efficiently. Proceedings of ACM Workshop on Java for High-Performance Network Computing, 15--24, 1998.
• 29: H. T. Kung , John T. Robinson, On optimistic methods for concurrency control, ACM Transactions on Database Systems (TODS), v.6 n.2, p.213-226, June 1981 [doi>10.1145/319566.319567]
• 30: Leslie Lamport, A fast mutual exclusion algorithm, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.1-11, Feb. 1987 [doi>10.1145/7351.7352]
• 31: P. Leach and D. Perry. CIFS: A Common Internet File System. http://www.microsoft.com/mind/1196/cifs.asp|, 1996.
• 32: G. Muller, B. Moura, F. Bellard, and C. Consel. Harissa: A Flexible and Efficient Java Environment Mixing Bytecode and Compiled Code. Proceedings of the 3rd USENIX Conference on Object Oriented Technologies and Systems (COOTS '97), 1--20, 1997.
• 33: T. Onodera. A Simple and Space-Efficient Monitor Optimization for Java. IBM Research Report RT0259, IBM, 1998.
• 34: Tamiya Onodera , Kiyokuni Kawachiya, A study of locking objects with bimodal fields, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.223-237, November 01-05, 1999, Denver, Colorado, United States
• 35: Young Gil Park , Benjamin Goldberg, Escape analysis on lists, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.116-127, June 15-19, 1992, San Francisco, California, United States
• 36: William Pugh, Fixing the Java memory model, Proceedings of the ACM 1999 conference on Java Grande, p.89-98, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304106]
• 37: Ravi Rajwar , James R. Goodman, Speculative lock elision: enabling highly concurrent multithreaded execution, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 38: Erik Ruf, Effective synchronization removal for Java, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.208-218, June 18-21, 2000, Vancouver, British Columbia, Canada
• 39: Standard Performance Evaluation Corporation. SPEC JBB2000. http://www.spec.org/osg/jbb2000/.
• 40: Standard Performance Evaluation Corporation. SPEC JVM98 Benchmarks. http://www.spec.org/osg/jvm98/.
• 41: T. Suganuma , T. Ogasawara , M. Takeuchi , T. Yasue , M. Kawahito , K. Ishizaki , H. Komatsu , T. Nakatani, Overview of the IBM Java just-in-time compiler, IBM Systems Journal, v.39 n.1, p.175-193, January 2000
• 42: Alexander Thomasian, Concurrency control: methods, performance, and analysis, ACM Computing Surveys (CSUR), v.30 n.1, p.70-119, March 1998 [doi>10.1145/274440.274443]
• 43: Volano LLC. Volano Benchmarks. http://www.volano.com/benchmarks.html.
• 44: 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
• 45: John Whaley, Partial method compilation using dynamic profile information, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.166-179, October 14-18, 2001, Tampa Bay, FL, USA
• 46: Byung-Sun Yang , Junpyo Lee , Jinpyo Park , Soo-Mook Moon , Kemal Ebcioğlu , Erik Altman, Lightweight monitor for Java VM, ACM SIGARCH Computer Architecture News, v.27 n.1, p.35-38, March 1999 [doi>10.1145/309758.309773]
• 47: F. Yellin and T. Lindholm. Java Runtime Internals. Presentation in JavaOne '96,

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

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

Keywords:
Java, atomic operation, lock, monitor, reservation, synchronization, thread locality