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

• Folly

  90 27,072 9.8 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.)

• Disruptor

  30 17,020 5.4 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...

• InfluxDB

  www.influxdata.com sponsored

  Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.

  

• loom

  1 19 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...

• disruptor.cr

  4 3 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.

• disruptor

  1 28 - Ruby

  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.

• lfbb

  10 56 6.2 C++

  A Lock Free Bipartite Buffer Library written in standard C11

• lockfree

  11 695 7.9 C++

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

• WorkOS

  workos.com sponsored

  The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.

  

• slice_deque

  2 150 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