AtomicRingBuffer / AtomicRingQueue

A constant-size almost lock-free concurrent ring buffer

Upsides

• fast, trypush and trypop are O(1)
• scales well even during heavy concurrency
• AtomicRingBuffer has only 4 words of memory overhead (AtomicRingQueue has 6 words of overhead)
• blocking pop supported via AtomicRingQueue
• no memory allocations after initial creation

Downsides

• growing/shrinking is not supported
• maximum capacity of (usize >> 16) entries
• capacity is rounded up to the next power of 2

This queue should perform similar to mpmc but with a lower memory overhead. If memory overhead is not your main concern you should run benchmarks to decide which one to use.

Implementation details

This implementation uses two atomics to store the readindex/writeindex

Text Read index atomic +63------------------------------------------------16+15-----8+7------0+ | read_index | r_done | r_pend | +----------------------------------------------------+--------+--------+ Write index atomic +63------------------------------------------------16+15-----8+7------0+ | write_index | w_done | w_pend | +----------------------------------------------------+--------+--------+

• writeindex/readindex (16bit on 32bit arch, 48bits on 64bit arch): current read/write position in the ring buffer (head and tail).
• rpend/wpend (8bit): number of pending concurrent read/writes
• rdone/wdone (8bit): number of completed read/writes.

For reading rpend is incremented first, then the content of the ring buffer is read from memory. After reading is done rdone is incremented. readindex is only incremented if rdone is equal to r_pend.

For writing first wpend is incremented, then the content of the ring buffer is updated. After writing wdone is incremented. If wdone is equal to wpend then both are set to 0 and write_index is incremented.

In rare cases this can result in a race where multiple threads increment rpend in turn and rdone never quite reaches rpend. If rpend == 255 or w_pend == 255 a spinloop waits it to be <255 to continue. This rarely happens in practice, that's why this is called almost lock-free.

Structs

This package provides AtomicRingBuffer without blocking pop support and AtomicRingQueue with blocking pop support.

Dependencies

This package depends on parking_lot for blocking support in AtomicRingQueue

Usage

To use AtomicRingBuffer, add this to your Cargo.toml:

toml [dependencies] atomicring = "0.5.1"

And something like this to your code

```rust

// create an AtomicRingBuffer with capacity of 1024 elements let ring = ::atomicring::AtomicRingBuffer::with_capacity(900);

// trypop removes an element of the buffer and returns None if the buffer is empty asserteq!(None, ring.trypop()); // pushoverwrite adds an element to the buffer, overwriting the oldest element if the buffer is full: ring.pushoverwrite(1); asserteq!(Some(1), ring.trypop()); asserteq!(None, ring.try_pop()); ```

License

Licensed under the terms of MIT license and the Apache License (Version 2.0).

See LICENSE-MIT and LICENSE-APACHE for details.