HackerPapers

arXiv:1012.1824cs.DS

Single-Producer/Single-Consumer Queues on Shared Cache Multi-Core Systems

Massimo Torquati

Abstract

Using efficient point-to-point communication channels is critical for implementing fine grained parallel program on modern shared cache multi-core architectures. This report discusses in detail several implementations of wait-free Single-Producer/Single-Consumer queue (SPSC), and presents a novel and efficient algorithm for the implementation of an unbounded wait-free SPSC queue (uSPSC). The correctness proof of the new algorithm, and several performance measurements based on simple synthetic benchmark and microbenchmark, are also discussed.

arXiv comments
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms cs.DCDistributed, Parallel, and Cluster Computing

On Hacker News

Linked by 2 identifiable commenters in 2 comments across 2 threads, from Mar 2015 to Dec 2025.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. I've been writing ring buffers wrong all these years (2016) 1 comment

    • Yes. [1] has background, [2] has the implementation (fig 2. pseudocode). Since you understood my comment I trust you can figure out the rest :) it’s a very neat trick. [1]https://www.microsoft.com/en-us/research/publication/concurr... [2]https://arxiv.org/pdf/1012.1824

      mrcode007View on HNParent context

  2. Aeron: High-Performance Open Source Message Transport [video] 1 comment

    • I've read the _The Art of Multiprocessor Programming_ and am happy to read it again. Maybe I have misinterpreted. So if "killed mid-operation" must be supported then I don't see how many algorithms can be said to make progress. Take for example the Lamport SPSC queue[1], if the…

      mjpt777View on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.