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

Stavros Passas, Sven Karlsson

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


    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.
    Original languageEnglish
    Title of host publicationProceedings of Forth Workshop on Programmability Issues for Heterogeneous Multicores
    Publication date2011
    Publication statusPublished - 2011
    Event4th Workshop on Programmability Issues for Heterogeneous Multicores - Heraklion, Greece
    Duration: 23 Jan 2011 → …
    Conference number: 4


    Workshop4th Workshop on Programmability Issues for Heterogeneous Multicores
    Period23/01/2011 → …
    Internet address


    Dive into the research topics of 'Comparing the Overhead of Lock-based and Lock-free Implementations of Priority Queues'. Together they form a unique fingerprint.

    Cite this