Fast FAA Array Queue

A fast, lock-free, multi-producer, multi-consumer (MPMC) queue implementation in C23. It uses a Fetch-And-Add (FAA) strategy on array indices for high throughput and relies on a hazard pointer implementation for safe memory reclamation. This is a modified version of FAAArrayQueue ported to C23.

USAGE

The API has no thread ids and no thread registration: any number of threads may use any queue at any time. Each thread lazily attaches per-queue state (two hazard pointers) on first use, caches it for its most recently used queues, and releases it automatically when the thread exits or when the queue is destroyed.

1. Creation

FAAArrayQueue_t *faa_queue_create(void);

• Returns: A pointer to the initialized queue, or nullptr on allocation failure.

FAAArrayQueue_t* my_queue = faa_queue_create();
if (!my_queue) {
    // Handle creation failure
}

2. Enqueue

Add an item to the tail of the queue. Lock-free; safe to call from any number of threads concurrently.

void faa_queue_enqueue(FAAArrayQueue_t *q, void *item);

• item: The pointer to enqueue. nullptr is ignored (nullptr is what dequeue returns for "empty").

int* my_data = malloc(sizeof(int));
*my_data = 123;
faa_queue_enqueue(my_queue, my_data);

3. Dequeue

Remove an item from the head of the queue. Lock-free; safe to call from any number of threads concurrently.

void *faa_queue_dequeue(FAAArrayQueue_t *q);

• Returns: The dequeued item, or nullptr if the queue was empty. The result is [[nodiscard]].

int* received = faa_queue_dequeue(my_queue);
if (received != nullptr) {
    printf("Dequeued: %d\n", *received);
    free(received);
}

4. Destruction

Free all memory associated with the queue. Call it only when no other thread is accessing the queue (after all producer/consumer threads have been joined). Remaining items are drained in FIFO order through free_payload (if non-null) before the memory is freed.

void faa_queue_destroy(FAAArrayQueue_t *q, void (*free_payload)(void *));

faa_queue_destroy(my_queue, free);

Complete Example

#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include "faaq.h"

int main(void) {
    FAAArrayQueue_t* q = faa_queue_create();
    assert(q != nullptr);

    faa_queue_enqueue(q, (void*)10);
    faa_queue_enqueue(q, (void*)20);

    void* item1 = faa_queue_dequeue(q);
    void* item2 = faa_queue_dequeue(q);

    printf("Dequeued: %ld\n", (intptr_t)item1); // Prints 10
    printf("Dequeued: %ld\n", (intptr_t)item2); // Prints 20
    assert(faa_queue_dequeue(q) == nullptr);   // empty

    faa_queue_destroy(q, nullptr);
    return 0;
}

See example.c for a multi-threaded producer/consumer example.

How the per-thread state works (why there is no tid)

The original FAAArrayQueue takes a thread id because its hazard pointers live in a per-queue array indexed by tid. Here that state lives in the thread instead:

• Each thread has a small thread-local cache (FAAQ_TLS_SLOTS, default 4, most-recently-used first) of per-queue entries: two hazard pointers plus the last head and tail node it protected. The hot path is one thread-local compare of the queue's id against the front entry.
• Queues carry a process-unique 64-bit id that is never reused, so an entry left behind by a destroyed queue can never match a new queue allocated at the same address.
• A thread that touches more queues than it has slots evicts the least recently used entry (correct, just slower). A thread that exits releases everything through a C23 tss_t destructor; hazard pointer records are recycled for later threads.
• Stale entries for a destroyed queue in other threads are inert; until they are evicted or the thread exits, each one pins at most two node-sized allocations from reuse. This is the one resource cost of the design.

Reclaimed nodes are cached per thread (FAAQ_NODE_CACHE_CAPACITY, default 256) and freed at thread exit.

What is different from the original FAAArrayQueue

Four things, each measured on its own (see the comparison below):

• Cached protection. A thread keeps its hazard pointers on the head and tail nodes it last used, so the protect-validate sequence (with its seq_cst fence) runs only when it moves to another node, not on every operation.
• No hot-line read on the pop side. The empty check compares deqidx with enqidx, and enqidx is the line every enqueuer hammers. It only grows, so a value read earlier on the same node is a lower bound: while deqidx is below it the queue is provably non-empty and the read is skipped.
• Speculative claim (FAAQ_SPEC_CLAIM, default 16). Under contention the pop's deqidx load and its fetch-add each miss on the same line, because other dequeuers steal it in between. When the last enqidx a thread saw lies more than the slack beyond its own last claimed index, producer-claimed items provably lie ahead and the dequeue claims with the fetch-add alone. An overshoot (other dequeuers consumed the slack) shows up as an empty slot, is poisoned immediately, and the next attempt takes the checked path; linearizability is unchanged because a claimed index is handled exactly as a claimed-but-not-yet-stored slot already was.
• The fetch-add's address waits for the previous access. A locked read-modify-write needs its line in the modified state, and the core requests the line as soon as the address is known, while the instruction cannot execute before every older memory access has completed. With the node pointer cached in the thread, the address is known at once, so the request went out while the previous operation's slot access was still in flight, and under contention the line arrived, was stolen by another thread's fetch-add, and had to be fetched again: hardware counters showed 1.5 demand fills per fetch-add. Each operation now ends by storing a zero that data-depends on its last memory result (faaq_dep(), an and the compiler cannot see through), and the next operation ORs it into the node pointer, so the request is issued when the fetch-add can execute. Worth 40 percent at 8 threads in the random mix and 48 percent in the pairs workload, for 4 to 5 percent single-threaded. A fence in front of the fetch-add does the opposite (the address is ready even longer before the instruction) and measures slower, which is why the fence-based attempts listed below never helped.

The hot paths of both operations are call-free: every slow path (slot miss, re-protecting the cached node, node full, node drained, waiting for a pending slot) lives in an out-of-line helper that finishes by re-entering the operation, which the compiler turns into a tail jump. The fast dequeue is 28 instructions with no stack frame and no saved register; the fast enqueue is 17 instructions from the queue-id compare to the CAS.

Things that were tried and measured as useless or harmful on this code, so they are not in it: pacing the fetch-adds by observed contention; fences at any of six placements around the fetch-add and the slot access; a load or a pause in front of the fetch-add; write-intent prefetches of the counter or slot lines; a plain store or an exchange instead of the slot CAS (same throughput: the line transfer just moves to the next locked instruction); node layouts with the counters in a separate page, packed like xenium's, or placed after the items; other slot-map strides and a bit-reversed slot map; node sizes other than 512; disabling the node cache or zeroing nodes with rep stos; tighter or delayed polling of pending slots; consumer hold-off heuristics; backoff on empty pops; validating the cached node against the live head/tail pointer; and shorter reclamation scan intervals.

Building and testing

make test          # ASan + UBSan build of test_faaq.c, then run
make tsan          # ThreadSanitizer build of the suite and of the fuzz harness, then run
make bench         # -O3 -flto benchmark driver: ./bench_faaq [-s sec] [-t 1,2,4] [-w sym|pc|mix|both|all] [-r reps] [-p] [-i inflight]
make example

The optimized targets pass -fomit-frame-pointer explicitly: the nixpkgs cc wrapper appends -fno-omit-frame-pointer -mno-omit-leaf-frame-pointer to every x86-64 compile (it is not part of the hardening that the flake disables, and there is no knob), and a flag on the command line wins. Sanitizer builds keep frame pointers for their stack traces.

test_faaq.c covers teardown/leaks, a deterministic regression for a thread whose cached head node was drained and unlinked by other threads, many queues per thread (slot eviction), 300 short-lived threads (hazard pointer record recycling), exact-once MPMC delivery at 4+4 and 16+16 threads, and a scaling benchmark. Under ThreadSanitizer the suite shrinks the concurrent phases (1/20 scale, and 8+8 threads at 1/100 for the oversubscribed one: TSan serializes every atomic through per-address locks, and 32 polling threads turn that into a convoy) and routes thread creation through pthreads (test_threads.h), because glibc's thrd_create calls its pthread internals directly and bypasses TSan's interceptors.

Fuzzing

fuzz_faaq.c is a model-based harness in the libFuzzer convention (LLVMFuzzerTestOneInput). The input bytes are a small program over six live queues: enqueue, dequeue, bulk enqueue/dequeue, destroy+recreate, explicit hazard pointer cleanup, drain, and BURST, which runs a real multi-threaded phase (1-4 producers, 1-4 consumers) and checks exact-once delivery, per-producer FIFO order, emptiness afterwards, and (with one consumer) that a dequeue never reports "empty" once all producers have finished. Every single-threaded dequeue is checked against a reference FIFO and every destroy must drain exactly the model's contents in order.

The fuzz builds shrink the tunables (FUZZ_CFG in the Makefile: 4-slot nodes, hazard pointer scans every 8 retirements, no spin-waits, 2 thread-local slots, no node cache) so node boundaries, reclamation, slot poisoning, per-thread slot eviction and real free()s all happen every few operations.

make fuzz-smoke                 # gcc + ASan/UBSan, PRNG-driven, no fuzzing engine needed
make fuzz-afl FUZZ_SEC=600      # AFL++ (afl-clang-lto, ASan+UBSan), campaign into fuzz/out
make fuzz-libfuzzer FUZZ_SEC=300 # libFuzzer, in the flake's clang shell (nix develop .#clang)

The flake's dev shells provide AFL++ (aflplusplus, the actively developed general-purpose fuzzer for C; libFuzzer has been maintenance-only since 2022). afl-clang-lto gives collision-free LTO edge coverage and CmpLog; the same harness runs unchanged under libFuzzer. For more cores, add secondary instances: afl-fuzz -S s1 -i fuzz/seeds -o fuzz/out -- ./fuzz_faaq_afl. Do not set AFL_CC in the environment: afl-cc reads it as the name of its backend compiler.

Comparison with xenium's ramalhete_queue

xenium has a C++17 FAAArrayQueue (ramalhete_queue) with pluggable reclamation. bench_xenium.cpp is a line-for-line mirror of bench_faaq.c (same barrier, pinning, isolated control words, pre-fill, drain, CSV), each queue in its own language, both built by the same GCC 15 with -O3 -flto -DNDEBUG. Following xenium's own harness, every batch of 100 operations runs inside a region_guard. Workloads: sym (every thread alternates push and pop; the queue stays near-empty and pushers and poppers contend on the same node), mix (every thread pushes or pops with equal probability; the random walk keeps a backlog of thousands of items, so pushers and poppers work on different nodes; every operation counts), and pc (half producers, half consumers, producers throttled to 8192 items in flight).

make bench_xenium XENIUM_DIR=/path/to/xenium
make compare-xenium XENIUM_DIR=/path/to/xenium > compare.csv

Results on a Ryzen 9 9950X3D (one thread per physical core, pinned, 2 s runs, medians of 3 interleaved repetitions, spread within 5 percent, both sides built with -O3 -flto -fomit-frame-pointer), in M ops/s. x-hp is xenium with hazard pointers, x-qsbr with quiescent-state-based reclamation; the other three xenium reclaimers (EBR, NEBR, DEBRA) score between those two or below.

workload	threads	ours	x-hp	x-qsbr	ours / best xenium
sym	1	164.7	59.3	109.4	1.48x (NEBR 111.0)
sym	2	73.3	47.8	50.7	1.44x (QSBR 50.7)
sym	4	97.8	61.0	48.3	1.60x
sym	8	108.0	66.1	47.4	1.63x
sym	16	61.7	40.3	30.3	1.53x
mix	1	153.0	63.2	105.4	1.44x (NEBR 106.2)
mix	2	105.4	63.4	60.8	1.66x
mix	4	121.0	90.5	58.7	1.34x
mix	8	123.6	109.5	60.0	1.13x
mix	16	82.0	77.7	42.1	1.06x
pc	2	45.2	31.6	36.0	1.26x (QSBR 36.0)
pc	4	45.1	55.2	34.7	0.82x
pc	8	52.0	63.0	36.7	0.83x
pc	16	27.1	30.2	25.1	0.89x

Reading: this queue leads xenium's best reclaimer at every point of the pairs and random-mix workloads, by 1.06x to 1.66x, and leads its fence-free reclaimers (QSBR, NEBR, EBR, DEBRA), which pay the same per-operation cost we do, by 1.06x to 2.27x everywhere. It trails xenium's hazard-pointer variant only in the throttled producer/consumer split at 4, 8 and 16 threads. That split is paced by the driver's in-flight counter, a third contended line that every operation on either side updates, and by whichever side is slower: xenium-HP's pop is its slower side, so its queue sits at the 8192-item cap, its producers idle on the throttle and its consumers never see an empty queue; our push is our slower side (a fetch-add and a CAS on lines other cores own), so the queue sits empty and the producers set the pace. On this workload a bounded exponential backoff on empty pops gains nothing, peeking at the head slot before reading enqidx gains 4 percent here and costs 6 in the mix, and speculation margins other than 16 lose more than they gain, so none of them is in the code. The mix deficit reported here earlier was the address-generation effect described above, found by counting demand fills per operation (2.46 against xenium's 1.73 with the same two contended accesses) and confirmed by instruction-level sampling of the fill and cycle events; removing it also removed the pairs deficit at 4 threads and above. xenium's hazard-pointer variant is the slowest of the five single-threaded and the fastest under contention, but its per-operation fence is not what makes it fast (removing it changes nothing): its guard merely happens to load the node pointer after the fence, which is the same effect this queue now gets from a data dependency.

References

This work is directly inspired by:

• The CPP implementation of FAAArrayQueue

• Folly's Hazard Pointer Implementation folly