eraser Comparison: Our reimplementation of Eraser incurs an overhead of 8.7x, which is competitive with similar Eraser implementations built on top of unmodified JVMs. 15 Surprisingly, Fast Track is slightly faster than Eraser on some programs, even though it performs a precise analysis that traditionally has been considered more expensive.

More significantly, Eraser reported many spurious warnings that do not correspond to actual races. Augmenting our Eraser implementation to reason about additional synchronization constructs, such as fork/join or wait/ notify operations, 16, 22 would eliminate some of these spurious warnings, but not all. On hedc, Eraser reported a spurious warning but also missed two of the real race conditions reported by Fast Track, due to an (intentional) unsoundness in how the Eraser algorithm reasons about thread-local and read-shared data. 18

BasicVC and Djit+ Comparison: Djit+ and BasicVC reported exactly the same race conditions as FastTrack. That is, all three checkers provide identical precision. However, Fast Track outperforms the other checkers. It is roughly 10x faster than BasicVC and 2.3x faster than Djit+. These performance improvements are due primarily to the reduction in the allocation and use of VCs. Across all benchmarks, Djit+ allocated more over 790 million VCs, whereas FastTrack allocated only 5. 1 million. Djit+ performed over 5. 1 billion O(n)-time VC operations, while Fast Track performed only 17 million. The memory overhead for storing the extra VCs leads to significant cache performance degradation in some programs, particularly those that randomly access large arrays. These tools are likely to incur even greater overhead when checking programs with larger numbers of threads.

Multirace Comparison: MultiRace maintains Djit+’s instrumentation state, as well as a lock set for each memory location. 16 The checker updates the lock set for a location on the first access in an epoch, and full VC comparisons are performed only after this lock set becomes empty. This synthesis substantially reduces the number of VC operations, but introduces the overhead of storing and updating lock sets. In addition, the use of Eraser’s unsound state machine for thread-local and read-shared data leads to imprecision.

Our reimplementation of the MultiRace algorithm exhibited performance comparable to Djit+. Performance of MultiRace (and, in fact, all of our other checkers) can be improved by adopting a coarse-grain analysis in which all fields of an object are represented as a single “logical location” in the instrumentation state. 16, 22

goldilocks Comparison: Goldilocks7 is a precise race detector that does not use VCs to capture the happens-before relation. Instead, it maintains, for each memory location, a set of “synchronization devices” and threads. A thread in that set can safely access the memory location, and a thread can add itself to the set (and possibly remove others) by performing any of the operations described by the synchronization devices in the set.

Goldilocks is a complicated algorithm to optimize, and ideally requires tight integration with the underlying virtual machine and garbage collector, which is not possible under

RoadRunner. Because of these difficulties, Goldilocks reimplemented in RoadRunner incurred a slowdown of 31.6x across our benchmarks, but ran out of memory on lufact. Our Goldilocks reimplementation missed three races in hedc, due to an unsound performance optimization for handling thread-local data efficiently. 7 We believe some performance improvements are possible, for both Goldilocks and the other tools, by integration into the virtual machine.

4. 2. checking eclipse for race conditions To validate Fast Track in a more realistic setting, we also applied it to five common operations in the Eclipse development environment. 6 These include launching Eclipse, importing a project, rebuilding small and large workspaces, and starting the debugger. The checking overhead for these operations is as follows:

operation
startup
import
Clean small
Clean large
debug
base
time (s)

instrumented time (slowdown)

empty eraser djit+ Fasttrack 13.0 16.0 17. 3 16.0 7. 6 14. 9 17. 1 13. 1 14. 1 16. 7 24. 4 15. 2 17. 1 17. 9 38. 5 15. 4 1. 6 1. 7 1. 7 1. 6

Eraser reported potential races on 960 distinct field and array accesses for these five tests, largely because Eclipse uses many synchronization idioms that Eraser cannot handle, such as wait()and notify(), semaphores, and readers-writer locks. Fast Track reported 27 distinct warnings, 4 of which were subsequently verified to be potentially destructive. 9 Djit+ reported 28 warnings, which overlapped heavily with those reported by FastTrack, but scheduling differences led to several being missed and several new (benign) races being identified. Although our exploration of Eclipse is far from complete, these preliminary observations are quite promising. Fast Track is able to scale to precisely check large applications with lower run-time and memory overheads than existing tools.

5. concLusion

Race conditions are difficult to find and fix. Precise race detectors avoid the programmer-overhead of identifying and eliminating spurious warnings, which are particularly problematic when using imprecise checkers on large programs with complex synchronization. Our Fast Track analysis is a new precise race detection algorithm that achieves better performance than existing algorithms by tracking less information and dynamically adapting its representation of the happens-before relation based on memory access patterns. We have used Fast Track to identify data races in programs as large as the Eclipse programming environment, and also to improve the performance of other analyses that rely on precise data race information, such as serializability checkers. 8 The Fast Track algorithm and adaptive epoch representation is straightforward to implement and may be useful in other dynamic analyses for