bounded-spsc-queue
lockfree
| bounded-spsc-queue | lockfree | |
|---|---|---|
| 1 | 11 | |
| 154 | 704 | |
| - | - | |
| 10.0 | 7.9 | |
| over 1 year ago | about 1 month ago | |
| Rust | C++ | |
| Apache License 2.0 | MIT License |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
bounded-spsc-queue
-
Optimizing a Ring Buffer for Throughput
It's just amortizing for large transfers. For frequent near-empty cases it still has the shared pointers problem. NVMe have a really clever way to avoid this, but it depends on the fact that there's [occasional] communication on the reverse stream (the SQ/CQ pair): The cache line sized entries in the submit queue has a "phase" bit in the last word. The reader can just read that to know when the entry has updated (the polarity of the bit toggles each time we loop around and you can just use the top+1 index bit if power-of-two sized).
The back pressure is handled with a credit scheme and the producer gets an updated copy of most recently-know consumer read counter with every completion message back.
Using this scheme you can achieve the optimal performance with just a single cache line of traffic for each cache-line sized message.
Unfortunately I haven't found a SPSC Rust crate that does this, but https://github.com/polyfractal/bounded-spsc-queue [abandoned] comes close.
lockfree
- A lock-free ring-buffer with contiguous reservations (2019)
-
Atomics and Concurrency
If you're interested about lock-free data structures, I wrote [lockfree](https://github.com/DNedic/lockfree) a collection of lock-free data structures meant to be readable and both hosted system and embedded friendly.
-
Optimizing a Ring Buffer for Throughput
If you want more than a spsc queue, I've written `lockfree`, a collection of SPSC and MPMC data structures along the same principles the author here used:https://github.com/DNedic/lockfree.
The library is written in standard C++11 (but additional API's for higher C++ versions have been added), uses no dynamic allocation and is configurable so it is both big metal and deeply embedded friendly.
-
A collection of lock-free data structures written in standard C++11
- A lot of code won't work for types with no default constructors, but that is at least compile error
- Using memcpy[0] for arbitrary types is just wrong, see [1]
[0] https://github.com/DNedic/lockfree/blob/main/lockfree/inc/bi...
[1] https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p11...
-
Lock-free data structures
My friend wrote a few lock-free data structures and he is now looking for some feedback. Here is the link: https://github.com/DNedic/lockfree
- A collection of lock-free data structures written in standard c++11
- A collection of embedded friendly lock-free data structures written in standard C++11
What are some alternatives?
rc_event_queue - VecDeque-like fast, unbounded, mpmc/spmc concurent FIFO message queue. Lockless reads, write-lock writes.
glibc - GNU Libc
distortos - object-oriented C++ RTOS for microcontrollers
micro-gl - Headers Only C++11 CPU Vector Graphics. no std-lib, no FPU and no GPU required !
tlaplus - TLC is a model checker for specifications written in TLA+. The TLA+Toolbox is an IDE for TLA+.
Ring-Buffer - A simple ring buffer (circular buffer) designed for embedded systems.
multiversion-concurrency-control - Implementation of multiversion concurrency control, Raft, Left Right concurrency Hashmaps and a multi consumer multi producer Ringbuffer, concurrent and parallel load-balanced loops, parallel actors implementation in Main.java, Actor2.java and a parallel interpreter
set-ethernet-max-ring-buffer - Set max TX/RX ring buffer for ethernet device
jemalloc
rust-playground - The Rust Playground
multiversion-concurrency-contro