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