bespoke-algorithm
Table of Contents
Bespoke algorithm
Bespoke algorithm is a custom lock-free data structure designed for one specific use case rather than a general-purpose structure. By exploiting known constraints (single producer, fixed capacity, or known access patterns), a bespoke design eliminates overhead that a general-purpose structure carries for flexibility.
Bespoke algorithms trade generality for performance and sometimes for simplicity—but the assumptions must hold at every call site or the structure silently breaks with data races.
Example
SPSC (single-producer, single-consumer) ring buffer needs no CAS.
_Atomic size_t head = 0; // only producer writes _Atomic size_t tail = 0; // only consumer writes bool push(ring_t *r, void *item) { size_t h = atomic_load_explicit(&head, memory_order_relaxed); size_t next = (h + 1) % r->capacity; if (next == atomic_load_explicit(&tail, memory_order_acquire)) return false; // full r->buf[h] = item; atomic_store_explicit(&head, next, memory_order_release); return true; }
bespoke-algorithm.md · Last modified: by 127.0.0.1
