Module shared_deque 

SharedDeque<T> - cross-thread / cross-process Chase-Lev work- stealing deque backed by a memory-mapped file.

Chase-Lev’s signature asymmetry is what makes this primitive interesting: the owner of the deque pushes and pops the bottom end with no atomic CAS on the fast path (a Relaxed store on the bottom index), while any number of thieves steal from the top end with one CAS each. There is no MPMC ring contention; the local-pop fast path costs roughly one cache-line write.

Lifting this protocol into a memory-mapped file lets the same deque serve in-process worker-thread stealing AND cross-process work distribution. A second process opens the same file via SharedDeque::open_as_thief and steals from a remote owner with the identical CAS protocol, because the atomics touch physical pages whose coherence is identical to the cross-thread case (kernel uninvolved on the steal hot path).

The trade is a discriminant on the stored type: values stored in the deque must implement Marshal, the type-system contract that the value’s bytes mean the same thing in every address space. Closures with environment-capturing pointers cannot be stored directly; they must travel through pass_registry as (closure_id, args) pairs where args: T: Marshal.

Source

• David Chase and Yossi Lev, Dynamic Circular Work-Stealing Deque, SPAA 2005.
• The capacity is fixed at create time so the slot layout matches the MMF’s fixed file size; the paper’s resizing variant is a different primitive shape with a different contract and is not what this file implements.

Layout

+-----------------------------+
| DequeHeader (64B aligned)   |
|   magic, capacity, slot_bytes
|   owner_pid (informational) |
|   top: AtomicI64            |
|   bottom: AtomicI64         |
+-----------------------------+
| Slot[0]  (slot_bytes)       |  marshalled T payload
| Slot[1]                     |
| ...                         |
| Slot[capacity - 1]          |
+-----------------------------+

capacity is required to be a power of two so the slot-index computation is b & (capacity - 1). Each slot stores exactly T::PAYLOAD_BYTES rounded up to 8-byte alignment.

Structs

DequeHeader

File header. 64-byte aligned, fits in one cache line so the owner’s bottom updates and a thief’s top CAS land on the same cache-line coherence path.

SharedDeque

Chase-Lev work-stealing deque backed by a memory-mapped file.

Enums

DequeError

Errors returned by SharedDeque operations.

Constants

DEQUE_MAGIC

ASCII ‘WDEQ’ + version 1.

Functions

deque_file_size

Compute the total MMF byte size for a deque of capacity slots holding T values.

slot_bytes_for

Per-T slot byte width, rounded up to 8-byte alignment for atomic- friendly storage.