Chase-Lev deque

also: deque, chase lev

The lock-free double-ended queue that work stealing is normally built on. The owner pushes and pops at the bottom with no atomic operation at all in the common case; thieves take from the top with a compare-and-swap; the two only contend when the deque is nearly empty, which is exactly the case the algorithm handles carefully.

Work stealing needs a queue with a lopsided access pattern: the owner touches it constantly and thieves touch it rarely. The Chase-Lev deque is built around that asymmetry. The owner pushes and pops at the bottom; thieves take from the top; the two ends only meet when the deque is nearly empty.

let push_bottom d v =
  let b = Atomic.get d.bottom in
  d.buffer.(b land (Array.length d.buffer - 1)) <- v;
  Atomic.set d.bottom (b + 1)

Popping is where it gets delicate. The owner speculatively decrements bottom, then reads top. If more than one element remains the race is impossible and the pop is free. If exactly one remains, the owner and a thief are contending for the same slot, and the owner resolves it with the same compare-and-swap a thief would use, so exactly one of them wins.

let pop_bottom d =
  let b = Atomic.get d.bottom - 1 in
  Atomic.set d.bottom b;
  let t = Atomic.get d.top in
  if t > b then (Atomic.set d.bottom (b + 1); None)          (* empty *)
  else begin
    let v = d.buffer.(b land (Array.length d.buffer - 1)) in
    if t < b then Some v                                      (* uncontended *)
    else begin                                                (* last element *)
      let won = Atomic.compare_and_set d.top t (t + 1) in
      Atomic.set d.bottom (b + 1);
      if won then Some v else None
    end
  end

Taking from opposite ends is not only about contention. The bottom is the most recently pushed work, which is the hottest in cache and the smallest remaining subtree; the top is the oldest, which is usually the largest. So the owner gets locality and the thief gets a big enough piece to be worth the trip.