optimizes later accesses to x. The last read in the trace then
sets Rx to a nonminimal epoch.
4. eVaLuation
To validate Fast Track, we implemented it as a component
of the RoadRunner dynamic analysis framework for multithreaded Java programs. 10 RoadRunner takes as input a
compiled Java target program and inserts instrumentation
code into the target to generate an event stream of memory
and synchronization operations. Back-end checking tools
process these events as the target executes. The Fast Track
implementation extends the algorithm described so far
to handle additional Java primitives, such as volatile
variables and wait(), as outlined previously. 8 Some of the
benchmarks contain faulty implementations of barrier
synchronization. 9 Fast Track contains a specialized analysis to compensate for these bugs.
We compare Fast Track’s precision and performance
to six other analyses implemented in the same framework:
– Empty, a trivial checker that performs no analysis
and is used to measure the overhead of RoadRunner
– Goldilocks, a precise race detector based on an
extended notion of LockSets7
– Eraser, 18 an imprecise race detector based on the
LockSet algorithm described in Section 1
– MultiRace, a hybrid LockSet/Djit+ race detector16
4. 1. Performance and precision
Table 1 lists the size, number of threads, and uninstrumented running times for a variety of benchmark programs
drawn from the Java Grande Forum, 12 Standard Performance
Evaluation Corporation, 19 and elsewhere. 2, 7, 11, 21 All timing
measurements are the average of 10 test runs. Variability
across runs was typically less than 10%.
The “Instrumented Time” columns show the running
times of each program under each of the tools, reported as
the ratio to the uninstrumented running time. Thus, target programs ran 4. 1 times slower, on average, under the
Empty tool. Most of this overhead is due to communicating all target program operations to the back-end checker.
The variations in slowdowns for different programs
are not uncommon for dynamic race condition checkers.
Different programs exhibit different memory access and
synchronization patterns, some of which impact analysis
performance more than others. In addition, instrumentation can impact cache performance, class loading time, and
other low-level JVM operations. These differences can sometimes even make an instrumented program run slightly
faster than the uninstrumented (as in colt).
The last six columns show the number of warnings produced by each checker. The tools report at most one race
for each field of each class, and at most one race for each
array access in the program source code. All eight warnings from Fast Track reflect real race conditions. Some
of these are benign (as in tsp, mtrt, and jbb) but others can impact program behavior (as in raytracer and
hedc). 15, 20, 21
table 1. Benchmark results. Programs marked with ‘*’ are not compute-bound and are excluded from average slowdowns.
instrumented time (slowdown)
Warnings
eraser
Program
colt
crypt
lufact
moldyn
montecarlo
mtrt
raja
raytracer
sparse
series
sor
tsp
elevator*
philo*
hedc*
jbb*
Goldilocks
1. 8
77. 4
–
17. 5
6. 3
6. 7
2. 7
32. 8
64. 1
1.0
63. 2
74. 2
1. 1
7. 2
1. 1
2. 1
31. 6
BasicVc
0.9
84. 4
95. 1
111. 7
49. 4
8. 3
3. 5
250.2
57. 5
1.0
24. 6
390.7
1. 1
1. 1
1. 1
1. 6
89. 8
Djit+
0.9
54.0
36. 3
39. 6
30. 5
7. 1
3. 4
18. 1
27. 8
1.0
15. 8
8. 2
1. 1
1. 1
1. 1
1. 6
20. 2
Goldilocks
multiRace
fasttrack
eraser
0.9 3 0 0
14. 3 0 0 0
13. 5 4 0 –
10. 6 0 0 0
6. 4 0 0 0
6.0 1 1 1
2. 8 0 0 0
13. 1 1 1 1
14. 8 0 0 0
1.0 1 0 0
9. 3 3 0 0
8. 9 9 1 1
1. 1 0 0 0
1. 1 0 0 0
1. 1 2 1 0
1. 4 3 1 –
8. 5 27 5 3
BasicVc
0
0
0
0
0
1
0
1
0
0
0
1
0
0
3
2
8
Djit+
0
0
0
0
0
1
0
1
0
0
0
1
0
0
3
2
8
fasttrack
0
0
0
0
0
1
0
1
0
0
0
1
0
0
3
2
8
