MPSC_queue

MPSC_queue: A High-Performance Lock-Free Queue for C++17

The MPSC_queue is an advanced unbounded lock-free queue tailored for the C++17 programming language, specifically designed to accommodate multiple producers and a single consumer (MPSC) scenario. This queue achieves exceptional performance by utilizing innovative structural features that ensure minimal contention and high throughput even under demanding conditions.

Structural Design and Performance Insights

At the core of MPSC_queue is a Thread-Local Node Pool combined with a Lock-Free Global Chunk Stack, which guarantees that data can be pushed and popped at O(1) speed regardless of the size of the thread-local pool. While primarily lock-free, it employs lock-based heap operations only a logarithmic number of times, significantly enhancing overall efficiency.

digraph G {
    classDef THREAD fill:#e1f5fe,stroke:#0277bd,stroke-width:2px;
    classDef GLOBAL fill:#ffecb3,stroke:#ff6f00,stroke-width:2px;
    classDef QUEUE fill:#e8f5e9,stroke:#2e7d32,stroke-width:2px;

    subgraph PRODUCERS [MP]
        P1[P1: Enqueue]
        P2[P2: Enqueue]
    end
    class PRODUCERS THREAD

    subgraph CONSUMER [SC]
        C[SC: Dequeue]
    end
    class CONSUMER THREAD

    subgraph MPSC_QUEUE [Queue Instance]
        direction LR
        Head
        Tail
        Tail --> NodeA[Node]
        NodeA --> NodeB[Node]
        NodeB --> Head
    end
    class MPSC_QUEUE QUEUE

    subgraph THREAD_LOCAL_NODE_POOL [Static Node Pool]
        subgraph THREAD_LOCAL_CACHE [theard_local Dmitry Vyukov]
            direction TB
            LocalChunk_P1
            LocalChunk_P2
            LocalChunk_C
        end

        subgraph GLOBAL_NODE_POOL [global chunk stack]
            GlobalStackTop[Tagged Pointer]
            GlobalMutex[Page]
            NextChunk1
            NextChunk2
        end
    end
    class NODE_ALLOCATOR GLOBAL

    P1 --> Head
    P2 --> Head
    C --> Tail

    P1 -.-> LocalChunk_P1
    LocalChunk_P1 -- "Miss: Pop Chunk O(1)" -->GlobalStackTop
    P2 -.-> LocalChunk_P2
    LocalChunk_P2 -- "Miss: Pop Chunk O(1)" --> GlobalStackTop
    C -.-> LocalChunk_C
    LocalChunk_C -- "Recycle: Push Chunk O(1)" --> GlobalStackTop
    
    GlobalStackTop --> NextChunk1
    NextChunk1 --> NextChunk2
    NextChunk2 -- "Empty: Request Page" --> GlobalMutex
}

This design allows for efficient reuse of chunks in SPSClike scenarios, which is essential for maintaining performance under varying production rates. The daking::MPSC_queue is characterized by:

1. Optimal Performance in Uneven Production Scenarios: It excels during sudden bursts of production, effectively lowering contention and enhancing throughput to levels comparable to single-consumer conditions.
2. Bulk Enqueue Capabilities: The queue's enqueue_bulk function efficiently aggregates messages into a batch, allowing for only one CAS operation to merge them into the queue, thus optimizing performance further during bulk operations.

Benchmarking and Results

Performance Benchmark Analysis provides a comprehensive profile of the daking::MPSC_queue under various concurrent led scenarios. The queue displays remarkable resilience and performance consistency compared to traditional implementations, such as moodycamel::ConcurrentQueue, particularly in MPSC contexts.

Sample Performance Data

1. Uniform MPSC Contention (Single-Element Enqueue): This tests throughput under continuous uniform producer operations, effectively identifying the limits of contention on the queue's performance.
2. Uneven Sequential Bursts: This assesses the queue's ability to manage heterogeneous load patterns effectively, demonstrating its capability for elastic performance recovery.
3. Bulk Enqueue Operations: Validates the queue's efficiency during bulk operations, confirming its design advantages over conventional linked-list structures.

Advantages of Using MPSC_queue

• High throughput even during bursty production, accomplished through efficient batch operations.
• Limited locking necessary for memory allocation, significantly minimizing overhead.
• Fast and consistent Enqueue and Dequeue operations with complexity of O(1) for both processes.
• Efficient memory management with reduced contention through utilization of a thread-local pool.

Example Usage

To utilize the daking::MPSC_queue, a producer can enqueue items as shown below:

// Producer Example
#include "MPSC_queue.hpp"
daking::MPSC_queue<int> queue;
queue.enqueue(1);

Consumers can dequeue items using the provided methods:

// Consumer Example
int get;
while (!queue.try_dequeue(get)) {
    // Handle wait or break if the queue is empty
}

This concise documentation outlines essential aspects of the MPSC_queue, promoting its suitability for concurrent programming in high-performance applications while maintaining clarity and effectiveness in usage.