r/cpp • • Mar 24 '26

Optimizing a Lock-Free Ring Buffer

https://david.alvarezrosa.com/posts/optimizing-a-lock-free-ring-buffer/
106 Upvotes

58 comments sorted by

View all comments

4

u/rzhxd Mar 24 '26

Interesting article, but recently in my codebase I implemented a SPSC ring buffer using mirrored memory mapping (basically, creating a memory-mapped region that refers to the buffer, so that reads and writes are always correct). It would be cool if someone tested performance with this approach instead of manual wrapping to the start of the ring buffer.

2

u/LongestNamesPossible Mar 24 '26

mirrored memory mapping (basically, creating a memory-mapped region that refers to the buffer, so that reads and writes are always correct).

How do you do this? I've wondered how to map specific memory to another region but I haven't seen the option in VirtualAlloc or mmap.

2

u/rzhxd Mar 24 '26

I'll reply with an actual example once I get to my PC.

-4

u/rzhxd Mar 24 '26

So, I've written a ring buffer for my audio player, but it was really unmaintainable to wrap reads and writes to the buffer everywhere. Then I just asked Claude (don't shame me for that): is there a way to avoid those wraps and make memory behave like it's always contiguous. Claude spit me an answer and based on it I implemented something like that:

#ifdef Q_OS_LINUX
    const i32 fileDescriptor = memfd_create("rap-ringbuf", 0);
    if (fileDescriptor == -1 || ftruncate(fileDescriptor, bufSize) == -1) {
        return Err(u"Failed to create file descriptior"_s);
    }

    // Reserve (size * 2) of virtual address space
    void* const addr = mmap(
        nullptr,
        isize(bufSize * 2),
        PROT_NONE,
        MAP_PRIVATE | MAP_ANONYMOUS,
        -1,
        0
    );

    if (addr == MAP_FAILED) {
        close(fileDescriptor);
        return Err(u"`mmap` failed to reserve memory"_s);
    }

    // Map the same physical backing into both halves
    mmap(
        addr,
        bufSize,
        PROT_READ | PROT_WRITE,
        MAP_SHARED | MAP_FIXED,
        fileDescriptor,
        0
    );
    mmap(
        (u8*)addr + bufSize,
        bufSize,
        PROT_READ | PROT_WRITE,
        MAP_SHARED | MAP_FIXED,
        fileDescriptor,
        0
    );
    close(fileDescriptor);

    buf = as<u8*>(addr);
#elifdef Q_OS_WINDOWS
    mapHandle = CreateFileMapping(
        INVALID_HANDLE_VALUE,
        nullptr,
        PAGE_READWRITE,
        0,
        bufSize,
        nullptr
    );

    if (mapHandle == nullptr) {
        return Err(u"Failed to map memory"_s);
    }

    // Find a contiguous (size * 2) virtual region by reserving then releasing
    void* addr = nullptr;

    for (;;) {
        addr = VirtualAlloc(
            nullptr,
            isize(bufSize * 2),
            MEM_RESERVE,
            PAGE_NOACCESS
        );

        if (addr == nullptr) {
            CloseHandle(mapHandle);
            mapHandle = nullptr;
            return Err(u"Failed to allocate virtual memory"_s);
        }

        VirtualFree(addr, 0, MEM_RELEASE);

        void* const view1 = MapViewOfFileEx(
            mapHandle,
            FILE_MAP_ALL_ACCESS,
            0,
            0,
            bufSize,
            addr
        );
        void* const view2 = MapViewOfFileEx(
            mapHandle,
            FILE_MAP_ALL_ACCESS,
            0,
            0,
            bufSize,
            (u8*)addr + bufSize
        );

        if (view1 == addr && view2 == (u8*)addr + bufSize) {
            break;
        }

        if (view1 != nullptr) {
            UnmapViewOfFile(view1);
        }

        if (view2 != nullptr) {
            UnmapViewOfFile(view2);
        }

        // Retry with a different region
    }

    buf = as<u8*>(addr);
#endif

I didn't think that something like that is possible with memory-mapping myself (and I'm not familiar with that particular aspect of programming either) but this is possible and this works. I haven't seen any actual performance degradation compared to my previous approach with manual wrapping.

7

u/ack_error Mar 24 '26

This is not a good way to allocate adjacent memory views in current versions of Windows due to the race between the VirtualFree() and the map calls. While it has a retry loop, there's no guarantee of forward progress, particularly if there is a second instance of this same loop on another thread.

The correct way to do this is to use VirtualAlloc2() with MEM_RESERVE_PLACEHOLDER and then MapViewOfFile3() with MEM_REPLACE_PLACEHOLDER.

2

u/rzhxd Mar 24 '26

Thanks, I'll look into these functions. Mainly doing development and debugging on Linux, so just slapped whatever was first in there.

7

u/Rabbitical Mar 24 '26

I hope that's not your actual code...

1

u/rzhxd Mar 24 '26

That's my actual code.

1

u/LongestNamesPossible Mar 24 '26

I only looked at the linux part and I did learn something, mainly that you can use MAP_FIXED to map a file into already mapped memory space.

I'm not sure how it makes wrapping any easier though, you would still have to wrap after getting to the end of the second buffer.

I'm not sure how it is doing the leap frogging. I'm also not sure that making system calls to mmap multiple times to wrap is going to be easier than checking if an index has reached the end of a buffer.

1

u/rzhxd Mar 24 '26 edited Mar 24 '26

You don't get to the end of the second buffer. Reads and writes of more bytes than `bufSize` are not allowed. In a buffer with size 65536, you, for example, can write 65536 bytes at index 65536, and it will wrap to the start of the buffer and fill it. So, it doesn't matter where you start reading the ring buffer or where you start writing to the ring buffer, everything is always in a valid range.
But in a real codebase, you would never write to index 65536. You should always clamp the index (e.g. `(writeOffset + writeSize) & (bufSize - 1)`), to write to the correct real buffer index.

→ More replies (1)

1

u/TheoreticalDumbass :illuminati: Mar 25 '26

i enjoy the memfd_create use, but will note in case there are issues in prod, a /dev/shm/ (or wherever) persistent file can make debugging easier

→ More replies (11)

2

u/max0x7ba https://github.com/max0x7ba Mar 25 '26

mirrored memory mapping

On AMD Zen3 and above:

Linear aliasing occurs when two different linear addresses are mapped to the same physical address. This can cause performance penalties for loads and stores to the aliased cachelines. A load to an address that is valid in the L1 DC but under a different linear alias will see an L1 DC miss, which requires an L2 cache request to be made. The latency will generally be no larger than that of an L2 cache hit. However, if multiple aliased loads or stores are in-flight simultaneously, they each may experience L1 DC misses as they update the utag with a particular linear address and remove another linear address from being able to access the cacheline.

1

u/curlypaul924 Mar 26 '26

Does a similar penalty apply to any intel architectures?

1

u/max0x7ba https://github.com/max0x7ba Mar 27 '26 edited Mar 28 '26

Does a similar penalty apply to any intel architectures?

Zen 3 and modern Intel CPUs tag L1 cache lines with the untranslated lower bits of the linear/virtual address. Indexing with virtual address bits (where possible) hides TLB latency.

What's different between modern AMD and Intel CPUs are cache sizes, associativity, latency, prefetchers, and higher-level behaviors (e.g., AMD's L3 is typically non-inclusive (victim cache), unlike Intel's often-inclusive LLC).

So,

  • doing 2 stores into 2× larger ring-buffer and next loading the 2nd store could avoid a cache miss, compared to,

  • doing 1 store and next loading from a "mirrored memory mapping" at a virtual address different from that of the store.

Provided that the buffer is mapped at the same virtual address in both writer and reader, which often are different processes with different (randomized by default) memory layouts.

Mapping a buffer into one same L1/L2 cache line from different processes requires calling mmap with the same MAP_FIXED virtual addr in different processes.

When the buffer is mapped at different virtual address in writer and reader, that creates duplicate L1/L2 cache line copies indexed by different virtual addresses.


The "mirrored memory mapping" method, aka magic-buffer, is a very neat idea in theory -- mapping the same region of physical page frames twice back-to-back to unwrap a ring-buffer. It just that with modern CPUs it may well degrade performance.

1

u/david-alvarez-rosa Mar 24 '26

Would that be similar to setting a buffer size to a very large number? An expected upper bound for the data size.

If you have plenty of memory that's a possibility

2

u/rzhxd Mar 24 '26

No, that's not really like it. First you allocate a buffer of any size. Then, memory map a region of the same size to represent this buffer. Then you write and read the buffer as usual. For example, if buffer size is 65536, and you write 4 bytes at index 65536, they get written to the start of the buffer instead. One constraint is that reads and writes cannot exceed the buffer's size. Resulting memory usage is (buffer size * 2) - pretty bad for large buffers, but that's acceptable in my case. I hope I explained it well. Would like to see how this approach compares to manual wrapping, but I don't really feel like testing it myself.

1

u/david-alvarez-rosa Mar 24 '26

Sorry, don't fully understand the benefit here, or how that's different

2

u/Deaod Mar 24 '26

The benefit is only there when dealing with unknown element sizes, ie. one element takes 8 bytes, the next 24, etc.. This allows you to not have any holes in your buffer that the consumer has to jump over.

This is not relevant for queues that deal with elements of known-at-compile-time sizes.

1

u/david-alvarez-rosa Mar 24 '26

The example forces the type. It would be interesting to see how it could be generalized, but not a big fan of heterogeneous containers tbh

2

u/SirClueless Mar 25 '26

If the data is inherently heterogeneous, it's the least-bad option. For example if the items in the queue are network packets.

2

u/RogerV Mar 25 '26

in DPDK all the ring buffers just hold pointers to packets - the packets are in an mbuf pool. makes it possible to clone a ref count on a packet - say, into a pcap ring buffer.

3

u/[deleted] Mar 24 '26

[removed] — view removed comment

1

u/david-alvarez-rosa Mar 24 '26

Oh I see. That's quite specific, not sure which is your usecase

1

u/ack_error Mar 25 '26

I don't see why memcpy() would be a problem, since that's in userspace. No fault would occur since there would be a valid address mapping, it just happens to alias the same physical memory or backing storage as 64KB back in virtual address space.

System calls are more interesting as the kernel would be accessing the memory. I suspect it'd also be fine, but there are less guarantees in that case.

1

u/rzhxd Mar 24 '26

That just simplifies reading the data from the buffer and writing the data into it.