Module shared_deque_khl

Expand description

SharedDequeKhl - K-axis Hierarchical LCRQ deque, MMF-backed.

Novel SubEtha-native hybrid that pulls THREE amortization levers the four prior primitives pull individually:

KHPD’s 3-items-per-Release-store - each ring slot carries up to KHL_ITEMS_PER_SLOT = 3 LineItem payloads, and one Release-store on the slot’s Vyukov sequence number publishes them all together. The per-item coherence cost is one cache line bounce per 3 items.
LOH’s K-slots-per-counter-update - SharedDequeKhl::publish_batch reserves ceil(K / KHL_ITEMS_PER_SLOT) slots with ONE update of the producer tail counter, amortizing the producer-counter cost across the whole batch.
Chase-Lev’s owner-private tail counter - the producer’s tail-counter update is a Release-store (not a LOCK XADD), because the contract is “single owner process pushes.” The Release ordering on the per-slot sequence number is what publishes the slot bytes; the tail counter only signals “this many slots reserved.” Saves ~15 cycles per batch vs an atomic fetch_add.

Why this hybrid is SubEtha-only: the upstream LCRQ-on-LIFO ring has 56 bytes of dispatch-coupled payload per slot (closure id + args + latch offset), so three slots cannot fit in one cache line. SubEtha’s byte-oriented LineItem is 16 bytes; three of them plus an 8-byte sequence number plus a 4-byte count plus 4 bytes of reservation fit exactly in 64 bytes. The decoupling between dispatch (pass_registry) and transport (SharedDeque*) is what unlocks the hybrid.

§Cost-model comparison (per K=64 producer-fast batch)

Primitive	Producer atomics	Thief CAS attempts
`SharedDeque<u64>` (Chase-Lev per-item)	64 Release-stores + 64 fences	64
`SharedDequeKhpd::publish_batch`	22 slot Release-stores + 1 `fetch_add(LOCK XADD)`	22
`SharedDequeLoh::publish_batch`	64 slot Release-stores + 1 `fetch_add(LOCK XADD)`	64
`SharedDequeKhl::publish_batch`	22 slot Release-stores + 1 Release-store on tail	22

KHL matches KHPD’s per-slot count, matches LOH’s per-batch counter amortization, and adds Chase-Lev’s owner-private counter to save the LOCK XADD on top of that.

§Layout

+-----------------------------+
| KhlHeader (192B)            |  magic, capacity, owner_pid,
|                             |  epoch, tail on its own cache
|                             |  line, head on its own cache line
+-----------------------------+
| KhlSlot[0]  (64B)           |  sequence (8B) + n_items (4B) +
| KhlSlot[1]                  |  reserved (4B) + 3 LineItems (48B)
| ...                         |
| KhlSlot[capacity-1]         |
+-----------------------------+

Each slot is exactly one cache line. The Vyukov sequence number gating protocol is identical to SharedDequeLoh at the per-slot level: seq == idx (empty) -> seq == idx + 1 (published) -> seq == idx + capacity (consumed).

§When to use this vs the four base primitives

SharedDeque (Chase-Lev): per-item dispatch, no batching. Lowest constant per push but pays one Release-store per item.
SharedDequeKhpd: small batches (K up to ~64 on Zen+ R7 2700). Pays one fetch_add per batch.
SharedDequeLoh: very large batches where the per-slot amortization dominates the per-line one.
SharedDequeUrd: multi-thief workloads where the per-thief mailbox eliminates shared-head CAS contention.
SharedDequeKhl: producer-fast single-thief batches at any K >= 6 where the caller wants the best of KHPD’s per-slot density and LOH’s per-batch amortization simultaneously. Empirically the strongest single-thief batched primitive on Zen+ R7 2700.

Structs§

KhlHeader: File header. Cache-line aligned. head and tail each get their own cache line so the producer’s owner-private store on tail does not invalidate the consumer-side head line.
KhlSlot: Ring slot: Vyukov sequence (with n_items bit-packed into the low 2 bits) + 3 LineItem payloads. Fixed shape, 64 bytes, process-portable.
SharedDequeKhl: MMF-backed K-axis Hierarchical LCRQ deque. Single owner, N thieves.
StealResult: Payload returned by a successful steal.

Enums§

PublishRadius: K_radius axis - the coherence distance the publish operation crosses. Captures the empirical observation that the optimal publish mechanism differs by 50-100x across coherence domains (same-CCX vs cross-CCX vs cross-socket), and that no algorithmic structure axis (K_inner/K_outer/K_consumer/K_counter_share) captures this dimension.
PushError: Outcome of SharedDequeKhl::publish_batch.
Steal: Outcome of SharedDequeKhl::steal_slot.

Constants§

KHL_ITEMS_PER_SLOT: Items per slot: state (8 B sequence + 4 B n_items + 4 B reserved = 16 B header) + 3 * 16 = 48 B = 64 B total.
KHL_MAGIC: Magic byte sequence marking a valid KHL file. ASCII “WKHL” + ver 2 (bumped for the n_items-into-sequence bit-pack layout change).
KHL_SLOT_SIZE: Cache-line size; one slot per cache line.

Functions§

khl_file_size: Total file size for a ring with capacity slots.
pack_seq: Pack (idx_value, n_items) into a single i64 for atomic store.
unpack_idx: Unpack idx_value from a packed sequence word.
unpack_n_items: Unpack n_items from a packed sequence word.