Cache‐aware design of general‐purpose Single‐Producer–Single‐Consumer queues. (26th December 2018)

• Record Type: Journal Article
• Authors: Maffione, Vincenzo; Lettieri, Giuseppe; Rizzo, Luigi
• Is Part Of: Software, practice & experience. Volume 49:Number 5(2019)
• Page Start: 748
• Page End: 779
• Publication Date: 2018-12-26
• Subjects: cache‐aware design -- FastForward -- Lamport lock‐free queue -- SPSC; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2675
• Languages: English
• ISSNs: 0038-0644

Abstract

Summary: Data processing pipelines normally use lockless Single‐Producer–Single‐Consumer (SPSC) queues to efficiently decouple their processing threads and achieve high throughput, minimizing the cost of synchronization. SPSC queues have been widely studied, mostly for applications such as streaming data or network monitoring, where the main goal is maximizing throughput. There are now many applications, such as virtual‐machine–virtual‐machine communication, software‐defined networking, and message‐based kernels, where low latency is also important, and the tradeoffs between high‐throughput and low‐latency algorithms have not been studied equally well. Furthermore, at high or variable transaction rates, the effect of memory hierarchies and cache coherence subsystems may be dominant and yield surprising results. In this paper, we make two contributions. First, we provide a comprehensive study of the two main families of SPSC queues, namely, "Lamport" and "FastForward" queues, with a detailed analytical and experimental characterization of their behavior in terms of operating regimes, throughput, latency, and cache misses. Second, we propose two new queue variants, namely, improved FastForward and batched improved FastForward, which have better worst‐case behavior than other variants in terms of cache misses, which is an important feature for a number of applications. Together, these two contributions provide practical guidelines to choose the best solution depending on the application requirements.