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. PReLiminaRies
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
variable x

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 accesses.

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 . ( ) ( )

. ( ( ), ( ))

.0 V
t
V V tVt Vt
V V tmaxVt Vt
t
∀≤
=λ
⊥ =λ

( ) Vu