Work in progress

Before you consider using this ask yourself the following questions:

• Is my workload running on a machine > 8 cores?

  If not you likely won't see enough contention that an elimination back-off stack outperforms a classic Treiber stack or even an Arc<Mutex<Vec<T>>>.

• Do I trust the author's use of atomics?

  If yes, take a look at all grep -r -E "compare_and_set" anyways.

• Do I need a single coordination point through a stack to solve my problem?

  Think about how you could solve your problem in a parallel fashion requiring less coordination.

A normal lock-free Treiber stack [1] linearizes concurrent access through a single atomic head pointer on which push and pop operations loop trying to compare-and-swap it. Usually one uses exponential backoff to circumvent contention. This results in a single sequential bottleneck and a lot of cache coherence traffic.

A lock-free elimination back-off stack wraps such a lock-free Treiber stack, but instead of simply exponentially backing off on compare-and-swap failures, it uses something called an EliminationArray. Each slot within such an EliminationArray enables a thread executing a push operation to hand its item over to a thread executing a pop operation. On contention a thread tries to exchange on a randomly chosen slot within the EliminationArray. On failure of such an exchange it loops to the beginning retrying on the stack again.

The result is a lock-free stack that is both linearizable and parallel.

Criterion test comparing:

• Arc<Mutex<Vec<_>>>

• TreiberStack

• EliminationBackoffStack - Simply switching back and forth between stack and elimination array.

• EliminationBackoffStack - Exponentially backing off from the stack to the elimination array both in space and time.

X-Axis: Number of competing threads.

Y-Axis: Average time it took all threads to push and pop 1000 items each.

[1] Treiber, R. Kent. Systems programming: Coping with parallelism. New York: International Business Machines Incorporated, Thomas J. Watson Research Center, 1986.