Static Analyses for Eliminating UnnecessarySynchronization from Java ProgramsJonathan Aldrich, Craig Chambers, Emin Gun Sirer, and Susan EggersDepartment of Computer Science and EngineeringUniversity of WashingtonBox 352350Seattle, WA 98195 USA{jonal, chambers, egs, eggers}@cs.washington.eduAbstract. This paper presents and evaluates a set of analyses designed toreduce synchronization overhead in Java programs. Monitor-basedsynchronization in Java often causes significant overhead, accounting for5-10% of total execution time in our benchmark applications. To reduce thisoverhead, programmers often try to eliminate unnecessary lock operations byhand. Such manual optimizations are tedious, error-prone, and often result inpoorly structured and less reusable programs. Our approach replaces manualoptimizations with static analyses that automatically find and removeunnecessary synchronization from Java programs. These analyses optimizecases where a monitor is entered multiple times by a single thread, where onemonitor is nested within another, and where a monitor is accessible by only onethread. A partial implementation of our analyses eliminates up to 70% ofsynchronization overhead and improves running time by up to 5% for severalalready hand-optimized benchmarks. Thus, our automated analyses have thepotential to significantly improve the performance of Java applications whileenabling programmers to design simpler and more reusable multithreaded code.1. IntroductionMonitors [LR80] are appealing constructs for synchronization because they promotereusable code and present a simple model to the programmer. Many modern programminglanguages, such as Java [GJS96] and Modula-3, directly support monitors. While theseconstructs enable programmers to easily write multithreaded programs and reusablecomponents, they can incur significant run time overhead. Reusable code modules may containsynchronization for the most general case of concurrent access, even though particularprograms often use these modules in a context that is already protected from concurrency. Forinstance, a synchronized data structure may be accessed by only one thread at run time, oraccess to a synchronized data structure may be protected by another monitor in the program. Inboth cases, unnecessary synchronization increases execution overhead. As described in section2, even singlethreaded Java programs typically spend 5-10% of their execution time onunnecessary synchronization operations.Synchronization overhead can be reduced by manually restructuring programs [SNR+97],but this typically involves trading off program performance against simplicity, maintainability,and reusability. To improve performance, synchronization annotations can be omitted wherethey are not needed for correctness in the current version of the program, or synchronizedmethods can be modified to provide specialized, fast entry points for threads that already hold amonitor lock. Such specialized functions make the program more complex, and using themsafely may require careful reasoning about object-oriented dispatch to ensure that the protectinglock is acquired on all paths to the function call. The assumption that a lock is held at aparticular program point may be unintentionally violated by a change in some other part of theprogram, making program evolution and maintenance error-prone. Hand optimizations makecode less reusable, because they make assumptions about synchronization that may not be validwhen a component is reused in another setting. In general, complex manual optimizationsmake programs harder to understand, make program evolution more difficult, reduce thereusability of components, and create an opportunity for subtle concurrency bugs to arise.In this paper, we present and evaluate static analyses that reduce synchronization overheadby automatically detecting and removing unnecessary synchronization. A synchronizationoperation is unnecessary if there can be no contention between threads for the synchronizationoperation. For example, if a monitor is only accessible by a single thread throughout thelifetime of the program, there can be no contention for the monitor, and thus all operations onthat monitor can safely be eliminated. Similarly, if threads always acquire one monitor andhold it while acquiring another monitor, there can be no contention for the second monitor, andthis unnecessary synchronization can safely be removed. Finally, when a monitor is acquiredby the same thread multiple times in a nested fashion, the first monitor acquisition protects theothers from contention and therefore all nested synchronization operations may be optimizedaway. In order to reason statically about synchronization, we assume the compiler hasknowledge of the whole program at analysis time; future work may extend our techniques tohandle Java’s dynamic code loading and reflection features.There are three main contributions of this paper. First, we describe several synchronizationoptimization opportunities and measure their frequency of occurrence in several Java programs.Second, we provide precise definitions for a family of analyses designed to detect unnecessarysynchronization. Finally, we present a preliminary empirical evaluation of these analyses on asuite of benchmarks. Our partial implementation eliminates up to 70% of synchronizationoverhead and improves running time by up to 5% for typical Java benchmarks on a highlyoptimized platform.The rest of the paper is structured as follows. The next section describes the Javasynchronization model, and provides measurements of synchronization overhead for typicalbenchmarks. Section 3 identifies opportunities for optimizations. Section 4 provides a precisedescription for a set of analyses that detect and eliminate unnecessary synchronizationoperations. Section 5 summarizes the performance impact of these analyses on a set ofbenchmarks, section 6 discusses related work, and section 7 concludes.2. Java SynchronizationJava provides a monitor construct to protect access to shared data structures in a multithreadedenvironment.2.1 SemanticsThe semantics of monitors in Java are derived from Mesa [GMS77]. Each object is implicitlyassociated with a monitor, and any method