A PathScale fork of asynchronics/st3, published as
ps-st3. The library is still namedst3, souse st3::lifo::Workeris unchanged. It carries upstream PR #12 (bulk segmented copies on steal) ahead of a release, plus a differential test holding that bulk path against the per-element reference.
Lock-free, bounded, work-stealing queues with FIFO stealing and LIFO or FIFO semantic for the worker thread.
The Go scheduler and the Tokio runtime are examples of high-performance
schedulers that rely on fixed-capacity (bounded) work-stealing queues to avoid
the allocation and synchronization overhead associated with unbounded queues
such as the Chase-Lev work-stealing deque (used in particular by Crossbeam
Deque). This is a natural design choice for schedulers that use a global
injector queue as the latter often can, at nearly no extra cost, buffer the
overflow should a local queue become full. For such applications, St3 provides
high-performance, fixed-size, lock-free FIFO and LIFO work-stealing queues.
The FIFO queue is based on the Tokio queue, but provides a somewhat more convenient and more flexible API. The LIFO queue is a novel design with the same API and performance profile as its FIFO counterpart; it can be considered a faster, fixed-size alternative to the Chase-Lev deque.
Add this to your Cargo.toml:
[dependencies]
ps-st3 = "0.6.2"For the queues alone, without the pool below and without its one dependency:
[dependencies]
ps-st3 = { version = "0.6.2", default-features = false }A deque on its own is not much use, so the crate ships the pool that makes one.
st3::fanout is a fixed set of workers, each owning a lifo::Worker taken by
value, stealing from the others, with the operating system behind a three-method
Host trait so the pool itself is still no_std.
use std::sync::Arc;
use st3::fanout::{Pool, StdHost};
let host = Arc::new(StdHost::new(4));
let pool = Pool::new(4, 4096, host);
// The pool does not spawn. You hand each worker a thread of your own.
let threads: Vec<_> = (0..4)
.map(|id| {
let (pool, runner) = (pool.clone(), pool.runner(id));
std::thread::spawn(move || pool.run(runner))
})
.collect();
pool.submit(0, Box::new(|| println!("on some worker, at some point")));
pool.shut_down();
for t in threads {
let _ = t.join();
}Three things it deliberately does not do. It does not spawn threads, so a caller
can put a worker on a thread it already owns. It has no join and no completion
signal, so a caller that needs to know when a batch finished counts for itself.
And it does not apply backpressure: capacity bounds what a worker holds, not
what a caller may hand it.
Features: fanout is on by default and costs one dependency, spin, which has
no dependencies of its own. host is off by default and is what links std,
for the StdHost above.
docs/design-choices.md records the decisions behind it, an external review of
it, and which of that review's findings were taken.
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);The St³ queues are low-level primitives and as such their implementation
relies on unsafe. The test suite makes extensive use of Loom to assess
correctness. As amazing as it is, however, Loom is only a tool: it cannot
formally prove the absence of data races.
Before St³ sees wider use in the field and receives greater scrutiny, you should exercise caution before using it in mission-critical software. The LIFO queue in particular is a new concurrent algorithm and it is therefore possible that soundness issues will be discovered that weren't caught by the test suite.
The St³ queues use no atomic fences and very few atomic Read-Modify-Write
(RMW) operations. Similarly to the Tokio queue, they needs no RMW for push and
only one for pop. Stealing operations require only a single RMW in the LIFO
variant and 2 in the FIFO variant.
The first benchmark measures performance in the single-threaded, no-stealing
case: a series of 64 push operations (or 256 in the large-batch case) is
followed by as many pop operations.
Test CPU: i5-7200U
| benchmark | queue | average time |
|---|---|---|
| push_pop-small_batch | St³ FIFO | 841 ns |
| push_pop-small_batch | St³ LIFO | 830 ns |
| push_pop-small_batch | Tokio (FIFO) | 834 ns |
| push_pop-small_batch | Crossbeam Deque (Chase-Lev) FIFO | 835 ns |
| push_pop-small_batch | Crossbeam Deque (Chase-Lev) LIFO | 1346 ns |
| benchmark | queue | average time |
|---|---|---|
| push_pop-large_batch | St³ FIFO | 3383 ns |
| push_pop-large_batch | St³ LIFO | 3370 ns |
| push_pop-large_batch | Tokio (FIFO) | 3280 ns |
| push_pop-large_batch | Crossbeam Deque (Chase-Lev) FIFO | 5282 ns |
| push_pop-large_batch | Crossbeam Deque (Chase-Lev) LIFO | 7306 ns |
The second benchmark is a synthetic test that aims at characterizing multi-threaded performance with concurrent stealing. It uses a toy work-stealing executor which schedules on each of 4 workers an arbitrary number of tasks (from 1 to 256), each task being repeated by re-injection onto its worker an arbitrary number of times (from 1 to 100). The number of tasks initially assigned to each workers and the number of times each task is to be repeated are deterministically pre-determined with a pseudo-RNG, meaning that the workload is the same for all benchmarked queues. All queues use the Crossbeam Dequeue work-stealing strategy: half of the tasks are stolen, up to a maximum of 32 tasks. Nevertheless, the re-distribution of tasks via work-stealing is ultimately non-deterministic as it is affected by thread timing.
Given the somewhat simplistic and subjective design of the benchmark, the figures below must be taken with a grain of salt. In particular, this benchmark does not model message-passing.
Test CPU: i5-7200U
| benchmark | queue | average time |
|---|---|---|
| executor | St³ FIFO | 216 µs |
| executor | St³ LIFO | 222 µs |
| executor | Tokio (FIFO) | 254 µs |
| executor | Crossbeam Deque (Chase-Lev) FIFO | 321 µs |
| executor | Crossbeam Deque (Chase-Lev) LIFO | 301 µs |
Just like the Tokio queue, the St³ queues are susceptible to ABA. For instance, in a naive implementation, if a steal operation was preempted at the wrong moment for exactly the time necessary to pop a number of items equal to the queue capacity while pushing less items than are popped, once resumed the stealer could attempt to steal more items than are available. ABA is overcome by using buffer positions that can index many times the actual buffer capacity so as to increase the cycle period beyond worst-case preemption.
For this reason, St³ will use 32-bit buffer positions whenever the target supports 64-bit atomics, which should in practice provide full resilience against ABA. Targets that only support 32-bit atomics (e.g. MIPS) will instead use 16-bit buffer positions, which in theory introduces a very remote risk of ABA. Note that Tokio had been using 16-bit positions for all targets up to version 1.21.1, so you probably should not worry too much about it.
Although the LIFO implementation ended up quite different, the Tokio FIFO queue was an inspiration which also helped set the goal in terms of performance.
Tokio's queue is itself a modified version of Go's work-stealing queue. Go uses something akin to a Seqlock pattern where stealers optimistically read all items marked for stealing and later discard them if they have been concurrently evicted from the queue. Because of its stricter aliasing rules, Rust makes this pattern hard to implement so the Tokio queue was designed with the ability to "book" the items beforehand, an idea which St³'s LIFO queue borrowed.
This software is licensed under the Apache License, Version 2.0 or the MIT license, at your option.
Some assets of the test suite and benchmark may be licensed under different terms, which are explicitly outlined within those assets.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.
Enable atomic-host with default-features = false for fanout::AtomicHost.
Pass the worker count and a fn() -> u64 monotonic nanosecond clock. The host
uses atomic-wait platform calls, retains wake permits, and has no periodic
parking timeout. Your embedding owns worker creation and shutdown. The host
feature adds StdHost with an Instant clock over this same implementation.
Tuning::with_stealable_inbox(true) lets idle peers take displaced local jobs
while retaining a warm LIFO slot between fairness boundaries. At the LIFO quota,
the slot job also enters the stealable inbox, including a lone self-waking task.
A lone job stays available to awake thieves without waking a sleeping peer;
the active owner can run it. Spare local or inbox work still triggers a wake.
It is a Rust callsite option, useful
for independent tasks; measure its extra sharing cost on lock handoffs.
The opt-in preset Tuning::almost_tokio() combines a three-poll LIFO quota,
a shared FIFO inbox and host parking without idle spin rounds. It is a Nagoya
scheduler policy, not a Tokio compatibility mode. Dated benchmark reports
called this policy parking; the earlier aggressive-spin almost_tokio
preset was retired before release.
The default locality policy uses four empty search rounds and 128 spin hints per round before host parking. Keep CPU use between bursts alongside throughput when tuning this budget.