Struct WorkStealingDeque

Fixed-capacity deque for schedulers with one owner thread and one or more stealing worker threads.

struct WorkStealingDeque(T, ulong Capacity);

The owner pushes and pops work at the bottom. Thieves remove work from the opposite end. This lets the owner use a fast local LIFO path while thieves obtain older work in FIFO order. Use this family for work-stealing schedulers; do not use it as a general multi-producer queue.

Calling owner-only operations from more than one thread violates the concurrency protocol even though the operations are @safe. The deque transports trivial atomic value representations and does not own referenced objects. Pointee lifetime and reclamation remain the caller's responsibility.

The deque never resizes and performs no scheduler action when full. .init is a valid empty deque.

Methods

NameDescription
pop () Removes one value from the owner end in LIFO order.
steal () Attempts to remove one value from the thief end in FIFO order.
stealBatch (output) Attempts to steal a bounded batch into caller-owned output storage.
tryPush (item) Appends one value at the owner end.

Parameters

NameDescription
T trivial atomically transportable shared-compatible value representation with no destructor/postblit ownership semantics
Capacity compile-time element capacity; power of two in [2, 2^61]

Allocation

Construction and steady-state operations perform no backing allocation.

Thread Safety

Exactly one owner thread may call tryPush and pop. Zero or more thief threads may call steal and stealBatch concurrently.

Identity

Copy construction, move construction, assignment, and pass-by-value use are disabled. Establish the deque at its final address before concurrent use.

Failure

Full or empty conditions are reported through operation results. The deque does not block, resize, spill, park threads, or run scheduler policy.

Example

A scheduler owner keeps its newest work local while a thief takes older work. 

WorkStealingDeque!(ulong, 8) ready;

// The owner publishes work and normally consumes the newest item itself.
assert(ready.tryPush(10));
assert(ready.tryPush(20));
assert(ready.tryPush(30));

auto owner = ready.pop();
assert(owner.found && owner.value == 30);

// A thief takes from the opposite end so older work is shared first.
auto thief = ready.steal();
assert(thief.found && thief.value == 10);

ulong[4] batch;
const taken = ready.stealBatch(batch[]);
assert(taken == 1);
assert(batch[0] == 20);