A lock-free ring-buffer with contiguous reservations (2019)

1. Folly

   1 108 30,404 9.9 C++

   An open-source C++ library developed and used at Facebook.

   

   To set a HP on Linux, Folly just does a relaxed load of the src pointer, release store of the HP, compiler-only barrier, and acquire load. (This prevents the compiler from reordering the 2nd load before the store, right? But to my understanding does not prevent a hypothetical CPU reordering of the 2nd load before the store, which seems potentially problematic!)

   Then on the GC/reclaim side of things, after protected object pointers are stored, it does a more expensive barrier[0] before acquire-loading the HPs.

   I'll admit, I am not confident I understand why this works. I mean, even on x86, loads can be reordered before earlier program-order stores. So it seems like the 2nd check on the protection side could be ineffective. (The non-Linux portable version just uses an atomic_thread_fence SeqCst on both sides, which seems more obviously correct.) And if they don't need the 2nd load on Linux, I'm unclear on why they do it.

   [0]: https://github.com/facebook/folly/blob/main/folly/synchroniz...

   (This uses either mprotect to force a TLB flush in process-relevant CPUs, or the newer Linux membarrier syscall if available.)

2. SaaSHub

   www.saashub.com featured

   SaaSHub - Software Alternatives and Reviews. SaaSHub helps you find the best software and product alternatives

   

3. Disruptor

   2 36 18,273 5.9 Java

   High Performance Inter-Thread Messaging Library

   

   See also the Java LMAX Disruptor https://github.com/LMAX-Exchange/disruptor

   I've built a similar lock-free ring buffer in C++11 https://github.com/posterior/loom/blob/master/doc/adapting.m...

4. loom

   3 1 20 4.6 C++

   A streaming cross-cat inference engine (by posterior)

   

   See also the Java LMAX Disruptor https://github.com/LMAX-Exchange/disruptor

   I've built a similar lock-free ring buffer in C++11 https://github.com/posterior/loom/blob/master/doc/adapting.m...

5. disruptor.cr

   4 5 4 0.0 Crystal

   LMAX Disruptor implementation in Crystal

   

   I also wrote an LMAX Disruptor in Crystal: https://github.com/nolantait/disruptor.cr

   Here is one in Ruby: https://github.com/ileitch/disruptor

   Both languages are quite readable and I've used these to teach the concepts to beginners.

6. disruptor

   5 2 31 - Ruby

   Discontinued The LMAX Disruptor in Ruby. (by ileitch)

   

   I also wrote an LMAX Disruptor in Crystal: https://github.com/nolantait/disruptor.cr

   Here is one in Ruby: https://github.com/ileitch/disruptor

   Both languages are quite readable and I've used these to teach the concepts to beginners.

7. lfbb

   6 10 117 5.9 C++

   A Lock Free Bipartite Buffer Library written in standard C11

   

8. lockfree

   7 11 966 4.8 C++

   A collection of lock-free data structures written in standard C++11

   

9. slice_deque

   8 3 158 0.0 Rust

   A contiguous-in-memory double-ended queue that derefs into a slice

   

   > It's not an attack on the wording, but the correctness of your first bullet point. `unsafe` is appropriate for the initialization of a ring buffer in Rust. That's true for using `mmap` or anything in "pure" Rust using the allocator API to get the most idiomatic representation (which can't be done in safe or stable Rust). It's not one line. It's also not platform dependent, the code is the same on MacOS, Linux, and Windows the last I tried it.

   We're not talking about the same thing then.

   I'm talking about this code here: <https://github.com/gnzlbg/slice_deque/tree/master/src/mirror...> It is absolutely platform specific.

   Yes, most ring buffer implementations feature a little bit of `unsafe` code. No, it doesn't make sense to say "I have a tiny amount of `unsafe` already, so adding more has no cost."

   > But if your bottleneck is determined by the frequency at which channels get created or how many exist then I would call architecture into the question. ... This last month I've written a lock-free ring buffer to solve a problem and there's exactly one in an application that spawns millions of concurrent tasks.

   Okay, but a lot of applications or libraries are written to support many connections, and you don't necessarily know when writing the code (or even when your server receives them) if those connections will be just cycled very quickly or will be high-throughput long-lived affairs. Each of those probably has a send buffer and a receive buffer. So while it might make sense for your application to have a single ring buffer for its life, applications which churn through them heavily are completely valid.

Suggest a related project