Crate st3

St³ — Stealing Static Stack

Very fast lock-free, bounded, work-stealing queue with FIFO stealing and LIFO or FIFO semantic for the worker thread.

The Worker handle enables push and pop operations from a single thread, while Stealer handles can be shared between threads to perform FIFO batch-stealing operations.

St³ is effectively a faster, fixed-size alternative to the Chase-Lev double-ended queue. It uses no atomic fences, much fewer atomic loads and stores, and fewer Read-Modify-Write operations: none for push, one for pop and one (LIFO) or two (FIFO) for steal.

Example

use std::thread;
use st3::lifo::Worker;

// Push 4 items into a queue of capacity 256.
let worker = Worker::new(256);
worker.push("a").unwrap();
worker.push("b").unwrap();
worker.push("c").unwrap();
worker.push("d").unwrap();

// Steal items concurrently.
let stealer = worker.stealer();
let th = thread::spawn(move || {
    let other_worker = Worker::new(256);

    // Try to steal half the items and return the actual count of stolen items.
    match stealer.steal(&other_worker, |n| n/2) {
        Ok(actual) => actual,
        Err(_) => 0,
    }
});

// Pop items concurrently.
let mut pop_count = 0;
while worker.pop().is_some() {
    pop_count += 1;
}

// Does it add up?
let steal_count = th.join().unwrap();
assert_eq!(pop_count + steal_count, 4);

Modules

fifo

FIFO, bounded, work-stealing queue.

lifo

LIFO, bounded, work-stealing queue.

Enums

StealError

Error returned when stealing is unsuccessful.