Module shared_deque_fcl 

SharedDequeFcl - Fat Chase-Lev: counter-only Chase-Lev with K_inner = 3 items per slot.

This primitive answers the design-cube question “is there middle ground between Chase-Lev (K_inner=1, counter-only) and KHL (K_inner=3, per-slot atomic)?”. The answer is yes: Chase- Lev’s safety proof never required K_inner = 1; it only required that the producer’s bottom store be Release-fenced after the slot bytes are written. With K_inner = 3 the protocol becomes:

1. Producer loads bottom (Relaxed) + top (Acquire).
2. Capacity check: (bottom - top) + n_slots <= capacity.
3. For each of the n_slots slots: write 64 bytes (sequence- number-free) carrying 3 LineItem payloads + a count.
4. ONE Release fence orders all slot writes.
5. ONE Relaxed store on owner-private bottom advances bottom by n_slots, atomically publishing all slots from the thieves’ perspective.

No per-slot atomic. No per-slot Acquire-Release pair. Per K=64 items the producer pays one top load + 22 cache-line writes + one Release fence + one bottom store - 24 atomic ops total, of which 22 are just memory writes.

Cost-model comparison (K=64 producer-fast)

Primitive	Producer atomics
SharedDeque<u64> (Chase-Lev K_inner=1)	64 Release fences + 64 Relaxed bottom stores + 64 top loads
SharedDequeKhpd::publish_batch	22 slot Release-stores on state + 1 fetch_add (LOCK XADD)
SharedDequeLoh::publish_batch	64 slot Release-stores on sequence + 1 LOCK XADD
SharedDequeKhl::publish_batch	22 slot Acquire-loads on sequence + 22 slot Release-stores on sequence + 1 Release-store on owner-private tail
SharedDequeFcl::publish_batch	1 top Acquire-load + 22 cache-line writes + 1 Release fence + 1 Relaxed bottom store

Fcl’s producer side has the fewest atomic operations of any batched deque-family primitive on this substrate. The trade-off is on the thief side: Chase-Lev’s steal protocol does a speculative slot read BEFORE the head CAS, so a thief that loses the CAS has read a 64-byte slot for nothing. Under heavy contention this wastes cache bandwidth; under producer-fast single-thief (the workload-shape Fcl targets) the speculative reads never get wasted because the CAS never loses.

Why this is novel

The Chase-Lev literature treats K_inner = 1 as a fixed feature of the protocol, but inspecting the safety proof shows it never depended on the slot size. SubEtha’s byte-oriented LineItem decoupling makes the natural fat-slot extension trivial: three LineItem payloads (16 B each = 48 B) plus an 8 B count word plus 8 B of tail padding fit exactly in 64 B. The slot becomes cache-line aligned by construction; sequential slot writes are sequential cache-line writes. This is the counter-only end’s analogue of the K_inner = 3 lever that KHPD pulled on the per-slot end.

When to use this

• Producer-fast single-thief batched workloads: this is the win zone. Fcl’s per-batch cost is dominated by 22 cache-line writes; everything else is essentially free.
• NOT for multi-thief contention: the speculative slot read before head CAS wastes cache when the CAS races. Use SharedDequeUrd instead.
• NOT for per-item dispatch with K = 1: just use plain SharedDeque; Fcl’s K_inner = 3 wastes slot bytes if the caller has nothing to fill them with.

Structs

SharedDequeFcl

MMF-backed Fat Chase-Lev deque. Counter-only Chase-Lev protocol with K_inner = 3 items per slot, single owner, N thieves.