Adding `aarc` library as a dependency

Run this command in a terminal, in your project's directory:

cargo add aarc

To add it manually, edit your project's Cargo.toml file and add to the [dependencies] section:

aarc = "0.4.0"

The aarc library will be automatically available globally. Read the aarc library documentation.

Back to the crate overview.

Readme

aarc

Quickstart
Motivation
Examples

Quickstart

Arc: a replacement for the standard library's Arc, but implemented with deferred reclamation semantics.
AtomicArc: an Arc with an atomically updatable pointer. Supports standard atomic operations like compare_exchange.
Guard: A special smart pointer that is loaded from AtomicArc. It is similar to Arc in that it prevents deallocation, but it does not contribute to reference counts. This reduces contention when multiple threads operate on the same variable.

Motivation

Data structures built with Arc typically require locks for synchronization, as only the reference counts may be atomically updated, not the pointer nor the contained data. While locks are often the right approach, lock-free data structures can have better theoretical and practical performance guarantees in highly-contended and/or read-heavy settings.

Instead of protecting in-place updates with locks, an alternative approach is to perform copy-on-write updates by atomically installing pointers. To avoid use-afer-free, mechanisms for safe memory reclamation (SMR) are typically utilized (i.e. hazard pointers, epoch-based reclamation). aarc uses the wait-free and robust algorithm provided by the fast-smr crate and builds on top of it, hiding unsafety and providing convenient RAII semantics through reference-counted pointers.

Examples

Example 1: Treiber Stack

use std::ptr::null;
use aarc::{Arc, AtomicArc, CompareExchange, Guard};

struct StackNode {
    val: usize,
    next: Option<Arc<Self>>,
}

struct Stack {
    top: AtomicArc<StackNode>,
}

impl Stack {
    fn push(&self, val: usize) {
        let mut top = self.top.load();
        loop {
            let next = top.as_ref().map(Arc::from);
            let new_node = Arc::new(StackNode { val, next });
            match self.top.compare_exchange(top.as_ref(), Some(&new_node)) {
                Ok(_) => break,
                Err(before) => top = before,
            }
        }
    }
    fn pop(&self) -> Option<Guard<'_, StackNode>> {
        let mut top = self.top.load();
        while let Some(top_node) = top.as_ref() {
            let next = top_node.next.as_ref();
            match self.top.compare_exchange(top.as_ref(), next) {
                Ok(_) => return top,
                Err(actual_top) => top = actual_top,
            }
        }
        None
    }
}

Adding aarc library as a dependency

Adding `aarc` library as a dependency