Crate atomic_backoff 

atomic-backoff

Customizable backoff strategies for compare-and-swap loops and spin loops.

Compare-and-swap (CAS) loops and spin loops can often be optimized by adding backoff at each iteration, i.e. waiting a bit before the next iteration, in order to reduce the contention on the CPU’s cache lines.

As the optimal backoff strategy depends on multiple factors, especially the expected contention, this crate provides a generic BackoffStrategy to help customize algorithms using CAS/spin loops. Typical backoff strategies like ExponentialBackoff are also provided.

Atomic types are extended with try_update_with_backoff/update_with_backoff methods, mirroring their std try_update/update counterparts.

For handwritten CAS loops, see BackoffStrategy::backoff_reload and BackoffState; for spin loops, see BackoffStrategy::backoff_until, or BoundedBackoffStrategy to spin a bounded number of iterations before falling back to a slower waiting mechanism.

Examples

use std::{
    sync::atomic::{AtomicUsize, Ordering::Relaxed},
    thread,
    time::{Duration, Instant},
};

use atomic_backoff::{AtomicWithBackoffExt, BackoffStrategy, ExponentialBackoff, NoBackoff};

fn parallel_increment<S: BackoffStrategy>(threads: usize, iterations: usize) -> Duration {
    let counter = AtomicUsize::new(0);
    let start = Instant::now();
    thread::scope(|s| {
        for _ in 0..threads {
            s.spawn(|| {
                for _ in 0..iterations {
                    counter.update_with_backoff(Relaxed, Relaxed, |x| x + 1, S::default());
                }
            });
        }
    });
    assert_eq!(counter.load(Relaxed), threads * iterations);
    start.elapsed()
}

let no_backoff = parallel_increment::<NoBackoff>(4, 10_000);
let exponential = parallel_increment::<ExponentialBackoff<6, 4>>(4, 10_000);
println!("no backoff: {no_backoff:?}, exponential backoff: {exponential:?}");
// no backoff: 2.08ms, exponential backoff: 646µs

Structs

BackoffLimit

Wraps a BackoffStrategy to make it a BoundedBackoffStrategy completing after LIMIT iterations.

BackoffState

A wrapper around a BackoffStrategy to be used in CAS loops when the atomic value must be checked after each reload.

ExponentialBackoff

Performs exponential backoff.

NoBackoff

No backoff.

SpinBackoff

Emits a spin_loop and reloads the atomic value before retrying the CAS.

Enums

RetryStrategy

Retry strategy of a failed atomic compare-and-swap (CAS).

Traits

Atomic

An atomic type.

AtomicWithBackoffExt

Extension trait providing CAS loop methods using a given BackoffStrategy.

BackoffStrategy

Backoff strategy to be used after an atomic compare-and-swap (CAS) failure and in spin loops.

BackoffUntilCondition

A condition checked in BackoffStrategy::backoff_until.

BoundedBackoffStrategy

A BackoffStrategy which completes after a bounded number of iterations.