Communications - November 2010

[FT read same epoch] optimizes the case where x was already read in this epoch. This fast path requires only a single epoch comparison and handles over 60% of all reads. We use Et to denote the current epoch c@t of thread t, where c = Ct(t) is t’s current clock. Djit+ incorporates a comparable rule [Djit+ read same epoch].

The remaining three read rules all check for write–read conflicts via the fast epoch-VC comparison Wx  Ct, and then update Rx appropriately. If Rx is already a VC, then [FT read shared] simply updates the appropriate component of that vector. Note that multiple reads of read-shared data from the same epoch are all covered by this rule. We could extend rule [FT read same epoch] to handle same-epoch reads of read-shared data by matching the case that Rx ∈ VC and Rx(t) = Ct(t). The extended rule would cover 78% of all reads (the same as [Djit+ read same epoch]) but does not improve performance perceptibly.

If the current read happens after the previous read epoch (where that previous read may be either by the same thread or by a different thread, presumably with interleaved synchronization), [FT read exclusive] simply updates Rx with the accessing thread’s current epoch. For the more general situation where the current read is concurrent with the previous read, [FT read share] allocates a VC to record the epochs of both reads, since either read could subsequently participate in a read–write race.

Of these three rules, the last rule is the most expensive but is rarely needed (0.1% of reads) and the first three rules provide commonly-executed, constant-time fast paths. In contrast, the corresponding rule [Djit+ read] always executes an O(n)-time VC comparison for these cases.

Write operations: The next three Fast Track rules handle a write operation wr(t, x). Rule [FT write same epoch] optimizes the case where x was already written in this epoch, which applies to 71.0% of write operations, and Djit+ incorporates a comparable rule. [FT write exclusive] provides

Other: 3.3% of all Operations

figure 4. synchronization, threading operations.

When Thread t performs acq(t, m):

Ct := Ct  Lm

When Thread t performs rel(t, m):

Lm := Ct Ct := inct(Ct)

When Thread t performs fork(t, u):

Cu := Cu  Ct Ct := inct(Ct)

When Thread t performs join(t, u):

Ct := Ct  Cu Cu := incu(Cu)

a fast path for the 28.9% of writes for which Rx is an epoch, and this rule checks that the write happens after all previous accesses. In the case where Rx is a VC, [FT write shared] requires a full (slow) VC comparison, but this rule applies only to a tiny fraction (0.1%) of writes. In contrast, the corresponding Djit+ rule [Djit+ write] requires a VC comparison on 29.0% of writes. other operations: Figure 4 shows how FastTrack handles synchronization operations. These operations are rare, and the traditional analysis for these operations in terms of expensive VC operations is perfectly adequate. Thus, these Fast Track rules are similar to those of Djit+ and other VC-based analyses. example: The execution trace in Figure 5 illustrates how FastTrack dynamically adapts the representation for the read history Rx of a variable x. Initially, Rx is ⊥e, indicating that x has not yet been read. After the first read operation rd( 1, x), Rx becomes the epoch 1@ 1 recording both the clock and the thread identifier of that read. The second read rd(0, x) at clock 8 is concurrent with the first read, and so Fast Track switches to the VC representation á8, 1, …ñ for Rx, recording the clocks of the last reads from x by both threads 0 and 1. After the two threads join, the write operation wr(0, x) happens after all reads. Hence, any later operation cannot be in a race with either read without also being in a race on that write operation, and so the rule [FT write shared] discards the read history of x by resetting Rx to ⊥e, which also switches x back into epoch mode and so