| One of Java's strengths lies in its support for multithreading—in both its syntax and its libraries. With thread-safe libraries, however, programmers often get stronger synchronization than they need. For example, string concatenation triggers the unnecessary locking and unlocking of an object that no other thread can access. This locking, which often prohibits optimizations and forces a costly machine-level instruction, can amount to as much as 50% of a single-threaded program's execution on a multiprocessor.; Since programming around oversynchronization is tedious, error-prone, and sometimes infeasible, we suggest using program analysis to alleviate synchronization automatically, allowing programmers to focus on their algorithms rather than on the details of locking. We first develop an efficient, whole-program, flow-insensitive Thread-Escape Analysis—a combination alias, points-to, and escape analysis—that constructs a static picture of the heap and identifies objects local to a thread. An optimizer can remove the locking on these objects; in our study, it can remove over 77% for three of the applications.; We can optimize additional critical sections by inspecting the types of operations within them. Since read-only critical sections may overlap in execution, we can use the results of our second analysis, the Read-Write Analysis, to reduce Java locks to read locks and to automatically implement the multiple-readers/single-writer pattern. Furthermore, if all of a shared object's critical sections are read-only, we can eliminate the lock altogether. Our third analysis, the Protective Analysis, adds flow sensitivity to identify these objects.; To accommodate Java's dynamic loading, we believe that these analyses must execute incrementally as part of the run-time system. As a first step, we make the Thread-Escape Analysis incremental and show how it now faces the possibility of reanalysis and deoptimization. Initial experimental results suggest that the run-time system could delay the analysis, use results of previous executions, and optimistically anticipate optimizations in order to make an on-the-fly approach viable. With analogous changes to the other whole-program analyses, the run-time system can significantly improve the synchronization behavior of mainstream applications without requiring changes to application or library code. |
