A constant-size lock-free and almost wait-free ring buffer

Upsides

• Very fast, push and pop should be approx. O(1) even during heavy concurrency
• Only 4 words of memory overhead

• no memory allocations after initial creation

  Downsides

• Fixed size, growing/shrinking is not supported

• No method for blocking poll
• Only efficient on 64bit architectures, due to
• maximum capacity of 65536 entries

• capacity is rounded up to the next power of 2

  Implementation details

  This implementation uses a 64 Bit atomic to store the state

Text +64------+56------+48--------------+32------+24------+16-------------0+ | w_done | w_pend | write_index | r_done | r_pend | read_index | +--------+--------+----------------+--------+--------+----------------+

• writeindex/readindex (16bit): current read/write position in the ring buzffer.
• 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 and rdone never quite reaches rpend. If rpend == 255 or w_pend == 255 a spinloop waits it to be <255 to continue.

Dependencies

This package only depends on atomic64

Usage

AtomicRingBuffer is on crates.io and on docs.rs

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

toml [dependencies] atomicring = "0.1.0"

And something like this to your code

```rust

// create an AtomicRingBuffer with capacity of 1024 elements let ring = ::atomicring::AtomicRingBuffer::new(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()); ```