Site Tools


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