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

Original Article ↗ Hacker News Discussion ↗

Lock-free ring buffers and related “bip buffers” are examined as high-performance data structures for single-producer/single-consumer communication, especially in systems that must avoid dynamic allocation or blocking (e.g., DMA, embedded, real-time). Commenters compare designs like LMAX Disruptor and “magic” VM-mapped ring buffers, weighing their elegance and performance against downsides such as platform-specific `unsafe` code, TLB overhead, and setup cost. Much of the exchange focuses on the subtleties of atomic memory ordering, cache behavior, and correctness guarantees, highlighting how hard it is to implement truly safe, efficient lock-free structures and how tools like TLA+ or Loom can help.

Related designs and implementations

  • Multiple commenters link similar SPSC/MPMC ring buffers and LMAX Disruptor-style queues in Java, C++, Rust, Crystal, Ruby, Go, and C/C++ libraries.
  • Bipartite (bip) buffers get special praise as underused but powerful for variable-size payloads.

Virtual-memory “magic ring buffer” trick

  • Several mention mapping the buffer twice contiguously in virtual memory (“magic ring buffer”) to avoid handling wrap-around, used in GNU Radio and BPF.
  • Pros: simplifies handling variable-size messages; very ergonomic.
  • Cons: requires OS-specific mmap-style APIs and unsafe code; setup/teardown cost is higher than normal allocations; page- and TLB-heavy for many small buffers.
  • Only contiguous in virtual memory, so not suitable for DMA that needs contiguous physical memory; an IOMMU could theoretically help, but often absent on low-end microcontrollers.

Rust, unsafe, and portability

  • Debate over how much unsafe is acceptable: some say any production ring buffer must use unsafe; others stress the difference between small, contained unsafe and large, platform-specific VM code.
  • Mirrored allocations are clearly platform-specific and require separate code paths per OS.

Correctness and verification

  • No formal specification or proof is known; some suggest model checking in TLA+.
  • One commenter questions a specific watermark-update snippet and proposes a non-atomic, ownership-based watermark scheme.
  • Others report using dynamic analysis and CI across x86 and ARM to catch ordering bugs.

Bounded vs unbounded / broadcast logs

  • Bounded broadcast logs are seen as straightforward; making them unbounded and efficient is hard.
  • Suggestions include linked lists of bounded logs plus an indexed indirection, but that typically reintroduces locks.
  • Several argue that locking is often “good enough” and sometimes faster than complex lock-free designs, especially on some architectures.

Atomics, memory ordering, and “lock-free”

  • Clarification that “lock-free” is a term of art: algorithms use atomics (which use hardware locking) but guarantee progress and avoid blocking other threads.
  • Strong advice to understand acquire/release vs SeqCst rather than defaulting to SeqCst; later references highlight better learning material on memory ordering.
  • Discussion dives into subtle issues like ABA, hazard pointers, asymmetric barriers, and the difficulty of reasoning about weak memory models.