Struct atomicring::AtomicRingBuffer

pub struct AtomicRingBuffer<T: Sized> { /* fields omitted */ }

A constant-size almost lock-free concurrent ring buffer

Upsides

• fast, try_push and pop are O(1)
• scales well even during heavy concurrency
• only 4 words of memory overhead
• no memory allocations after initial creation

Downsides

• growing/shrinking is not supported
• no blocking poll support (see AtomicRingQueue for blocking poll support)
• 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 read_index/write_index

 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 |
+----------------------------------------------------+--------+--------+

• write_index/read_index (16bit on 32bit arch, 48bits on 64bit arch): current read/write position in the ring buffer (head and tail).
• r_pend/w_pend (8bit): number of pending concurrent read/writes
• r_done/w_done (8bit): number of completed read/writes.

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

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

In rare cases this can result in a race where multiple threads increment r_pend in turn and r_done never quite reaches r_pend. If r_pend == 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.

Usage

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

[dependencies]
atomicring = "0.5.4"

And something like this to your code

let ring = ::atomicring::AtomicRingBuffer::with_capacity(900);

assert_eq!(None, ring.try_pop());
ring.push_overwrite(1);
assert_eq!(Some(1), ring.try_pop());
assert_eq!(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.

Methods

impl<T: Default> AtomicRingBuffer<T>

pub fn try_write<F: FnOnce(&mut T)>(&self, writer: F) -> Result<(), ()>

Write an object from the ring buffer, passing an &mut pointer to a given function to write to during transaction. The cell will be initialized with Default::default()

impl<T: Sized> AtomicRingBuffer<T>

pub fn with_capacity(capacity: usize) -> AtomicRingBuffer<T>

Constructs a new empty AtomicRingBuffer with the specified capacity the capacity is rounded up to the next power of 2

Examples

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

 // try_pop removes an element of the buffer and returns None if the buffer is empty
 assert_eq!(None, ring.try_pop());
 // push_overwrite adds an element to the buffer, overwriting the oldest element if the buffer is full:
 ring.push_overwrite(10);
 assert_eq!(Some(10), ring.try_pop());
 assert_eq!(None, ring.try_pop());

pub fn try_push(&self, content: T) -> Result<(), T>

Try to push an object to the atomic ring buffer. If the buffer has no capacity remaining, the pushed object will be returned to the caller as error.

pub fn try_unsafe_write<F: FnOnce(*mut T)>(&self, writer: F) -> Result<(), ()>

Write an object from the ring buffer, passing an uninitialized *mut pointer to a given fuction to write to during transaction. The cell will NOT be initialized and has to be overwritten using ptr::write_unaligned!

pub fn push_overwrite(&self, content: T)

Pushes an object to the atomic ring buffer. If the buffer is full, another object will be popped to make room for the new object.

pub fn try_pop(&self) -> Option<T>

Pop an object from the ring buffer, returns None if the buffer is empty

pub fn try_read<U, F: FnOnce(&mut T) -> U>(&self, reader: F) -> Option<U>

Read an object from the ring buffer, passing an &mut pointer to a given function to read during transaction

pub fn len(&self) -> usize

Returns the number of objects stored in the ring buffer that are not in process of being removed.

pub fn is_empty(&self) -> bool

Returns the true if ring buffer is empty. Equivalent to self.len() == 0

pub fn cap(&self) -> usize

Returns the maximum capacity of the ring buffer

pub fn remaining_cap(&self) -> usize

Returns the remaining capacity of the ring buffer. This is equal to self.cap() - self.len() - pending writes + pending reads.

pub fn clear(&self)

Pop everything from ring buffer and discard it.

pub fn memory_usage(&self) -> usize

Returns the memory usage in bytes of the allocated region of the ring buffer. This does not include overhead.

Trait Implementations

impl<T: Send> Send for AtomicRingBuffer<T>

If T is Send, AtomicRingBuffer is Send + Sync

impl<T: Send> Sync for AtomicRingBuffer<T>

Any particular T should never accessed concurrently, so T does not need to be Sync. If T is Send, AtomicRingBuffer is Send + Sync

impl<T> Debug for AtomicRingBuffer<T>

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<T> Drop for AtomicRingBuffer<T>

fn drop(&mut self)

Executes the destructor for this type.