the spurious warnings produced by some tools. Even if a code
block looks suspicious, it may still be race-free due to some
subtle synchronization discipline that is not (yet) understood by the current code maintainer. Even worse, additional
real bugs (e.g., deadlocks or performance problems) could
be added while attempting to “fix” a spurious warning produced by these tools. Conversely, real race conditions could
be ignored because they appear to be false alarms.
This paper exploits the insight that, while VCs provide
a general mechanism for representing the happens-before
relation, their full generality is not actually necessary in
most cases. The vast majority of data in multithreaded programs is either thread local, lock protected, or read shared.
Our Fast Track analysis uses an adaptive representation for
the happens-before relation to provide constant-time and
constant-space overhead for these common cases, without
any loss of precision or correctness.
In more detail, a VC-based race detector such as Djit+
records the time of the most recent write to each variable
x by each thread t. By comparison, FastTrack exploits the
observation that all writes to x are totally ordered by the
happens-before relation, assuming no races on x have been
detected so far, and records information only about the very
last write to x. Specifically, Fast Track records the clock and
thread identifier of that write. We refer to this pair of a clock
and a thread identifier as an epoch.
Read operations on thread-local and lock-protected data
are also totally ordered, assuming no races on x have been
detected, and Fast Track records only the epoch of the last
read from such data. FastTrack adaptively switches from
epochs to VCs when necessary (e.g., when data becomes
read-shared) in order to guarantee no loss of precision. It also
switches from VCs back to lightweight epochs when possible
(e.g., when read-shared data is subsequently updated).
Using these representation techniques, FastTrack
reduces the analysis overhead of almost all monitored operations from O(n) time, where n is the number of threads in
the target program, to O( 1) time.
In addition to improving performance, the epoch representation also reduces space overhead. A VC-based race
detector requires O(n) space for each memory location of the
target program and can quickly exhaust memory resources.
By comparison, Fast Track reduces the space overhead for
thread-local and lock-protected data from O(n) to O( 1).
For comparison purposes, we implemented six different dynamic race detectors: Fast Track plus five other race
detectors described in the literature. Experimental results
on Java benchmarks, including the Eclipse programming
environment, show that FastTrack outperforms the other
tools. For example, it provides almost a 10x speedup over a
traditional VC-based race detector and a 2.3x speedup over
the Djit+ algorithm. It also provides a substantial increase in
precision over Eraser, with no loss in performance.
2. 1. multithreaded program traces
We begin with some terminology and definitions regarding multithreaded execution traces. A program consists of
a number of concurrently executing threads, each with a
thread identifier t ∈ Tid. These threads manipulate variables
x ∈ Var and locks m ∈ Lock. A trace a captures an execution
of a multithreaded program by listing the sequence of opera-
tions performed by the various threads. The operations that
a thread t can perform include:
• rd(t, x) and wr(t, x), which read and write a value from a
In addition, the happens-before relation is transitively
closed: that is, if a <a b and b <a c then a <a c.
If a happens before b, then we also say that b happens
after a. If two operations in a trace are not related by the
happens-before relation, then they are considered
concurrent. Two memory access conflict if they both access
(read or write) the same variable, and at least one of the
operations is a write. Using this terminology, a trace
has a race condition if it has two concurrent conflicting
2. 2. Vector clocks and the Djit+ algorithm
Before presenting the FastTrack algorithm, we briefly
review the Djit+ online race detection algorithm, 16 which is
based on VCs. 14 A VC
V : Tid → Nat
records a clock for each thread in the system. Vector
clocks are partially-ordered () in a pointwise manner,
with an associated join operation () and minimal element (⊥V). In addition, the helper function inct
increments the t-component of a VC:
=λ = + () . () 1 incV u ut Vu if then else
12 1 2
12 1 2
iff . ( ) ( )
. ( ( ), ( ))
V V tVt Vt
V V tmaxVt Vt
( ) Vu