Comparing the Overhead of Lock-based and Lock-free Implementations of Priority Queues

With the advent of multi-core processors, concurrent data structures have received a renewed interest. While concurrent data structures where previously used mainly in high-performance computing, now they are found in all types of computer systems. A major challenge when designing such data structures is to allow multiple cores to safely access the data structure.

Traditionally, mutual exclusion using lock primitives has been used to avoid interference between cores. However, lock primitives cause a high synchronization overhead in situations with high contention. More recently, lock-free data structures have been proposed as a solution to decrease the synchronization overhead.

Lock-free data structures are more complex than their lock-based counterparts. It is not evident if the benefits of lower synchronization overhead can offset the higher sequential execution time caused by the complexity. In this paper, we compare a lock-free implementation of a priority queue with a lock-based implementation.

We perform experiments with processors of different generations and observe large performance differences for lock-free data structures depending on the processor generation. The lock-free implementation performs much better on the most recent processor generation. We investigate this performance trend, using a set of micro-benchmarks and show a significant difference in the overhead of atomic operations between processor generations.

The lock-free implementation executes approximately three times as many instructions as the lock-based implementation. However, the lock-free implementation outperforms the lock-based when multiple cores are used and the data structure is contended.