Module shared_deque_khpd 

SharedDequeKhpd - K-axis Hierarchical Publication Deque, MMF-backed.

Companion primitive to SharedDeque (the Chase-Lev work-stealing deque) for workloads where the producer batches and the per-line transfer cost dominates the round-trip.

The amortization lever

Chase-Lev pays one cache-line bounce per single-item handoff between owner and thief. KHPD packs LINE_ITEMS = 3 items into one 64-byte cache line and atomically publishes them with a single Release-store on the line’s state word. A thief takes the whole line in one CAS, reading all three items in a single cache-line transfer. The architectural saving is one Release- store per item amortized over three items - measured at 1.16x producer-side throughput vs Chase-Lev on a Zen+ R7 2700 when the workload uses the batch publish API.

Layout

+-----------------------------+
| KhpdHeader (128B)           |  magic, capacity, owner_pid,
|                             |  tail on its own line,
|                             |  head on its own line
+-----------------------------+
| PublicationLine[0]  (64B)   |  state (8B) + 3 LineItems (48B)
| PublicationLine[1]          |  + 8B padding
| ...                         |
| PublicationLine[capacity-1] |
+-----------------------------+

Each PublicationLine is exactly one cache line so adjacent lines never share coherence-traffic lines. state is an AtomicU64 packed as (epoch: u32 << 32) | (n_items: u16 << 16) | claim: u16; the publisher writes the line items in place and issues one Release-store on state with claim = CLAIM_BIT and n_items set. The claimer reads state Acquire, validates the epoch matches its head, CAS-takes the head, then reads the line items and releases the slot by storing STATE_EMPTY for the next round’s producer.

Each LineItem is a 16-byte byte-oriented payload. Callers marshal their own value into the payload at publish time and unmarshal it at steal time. SubEtha’s Marshal trait is the recommended packing contract.

When to use this vs SharedDeque

• SharedDeque<T> (Chase-Lev) - per-item dispatch and steal, strict LIFO at the owner, optimal at low per-item batch size.
• SharedDequeKhpd (this primitive) - producer batches multiple items per publication line. Beats Chase-Lev by ~16% on producer-side throughput when the workload calls publish with several staged items. On per-item dispatch (one stage + one publish per call), KHPD gives back the amortization win and may underperform.

Structs

FatLineItem

64-byte cache-line-sized payload carrying up to LINE_ITEMS = 3 LineItem payloads plus a count. The deque-family hybrid SharedDequeFcl uses this as the slot type for counter-only Chase-Lev with K_inner = 3: each push publishes 3 items in one cache-line write, with NO per-slot atomic and ONE owner-private bottom store amortized across the whole batch.

KhpdHeader

File header. Cache-line aligned. head and tail each get their own cache line to prevent producer and consumer counters from invalidating each other.

LineItem

One item carried in a publication line. 16 bytes.

PublicationLine

One publication line: state + LINE_ITEMS items + padding.

SharedDequeKhpd

MMF-backed K-axis Hierarchical Publication Deque. Single owner, arbitrarily many thieves.

StealResult

Result of a successful steal: the publication line’s items.

Enums

PushError

Outcome of SharedDequeKhpd::publish.

Steal

Outcome of SharedDequeKhpd::steal_line.

Constants

KHPD_ITEM_BYTES

Bytes per LineItem payload. Callers marshal their value into these 16 bytes (and unmarshal at steal time).

KHPD_LINE_SIZE

Cache-line size; one publication line per cache line.

KHPD_MAGIC

Magic byte sequence marking a valid KHPD file. ASCII ‘WKHP’ + ver.

LINE_ITEMS

Items per publication line. State (8 B) + 3 * 16 = 56 B; 8 B trailing padding rounds the line to 64.

Functions

khpd_file_size

Total file size for a KHPD with capacity publication lines.