  Two key synchronization paradigms for the construction of scalable concurrent
data-structures are software combining and elimination. Elimination-based
concurrent data-structures allow operations with reverse semantics (such as
push and pop stack operations) to "collide" and exchange values without having
to access a central location. Software combining, on the other hand, is
effective when colliding operations have identical semantics: when a pair of
threads performing operations with identical semantics collide, the task of
performing the combined set of operations is delegated to one of the threads
and the other thread waits for its operation(s) to be performed. Applying this
mechanism iteratively can reduce memory contention and increase throughput. The
most highly scalable prior concurrent stack algorithm is the
elimination-backoff stack. The elimination-backoff stack provides high
parallelism for symmetric workloads in which the numbers of push and pop
operations are roughly equal, but its performance deteriorates when workloads
are asymmetric. We present DECS, a novel Dynamic Elimination-Combining Stack
algorithm, that scales well for all workload types. While maintaining the
simplicity and low-overhead of the elimination-bakcoff stack, DECS manages to
benefit from collisions of both identical- and reverse-semantics operations.
Our empirical evaluation shows that DECS scales significantly better than both
blocking and non-blocking best prior stack algorithms.
