2026-10-24 Wait-Free Hazard Pointer Acquisition on Linux

Quantlarping in the big 2026

If you talk to any starry-eyed CS student, most of them say that they wanna break into quant. But usually the thing they come up with to build a portfolio for a quant internship is the typical stock or crypto trading bot, which is certainly something that has never been done before. More creative ones usually make parsers, maybe for NASDAQ ITCH data or HIP-3 arbitrage if they’re feeling a bit more current. But this misses the nuance in programming trading engines, as these portfolio pieces mostly cover “solved problems” within the industry. When you’re at an HFT pod, the question is sometimes not “what to buy” but “how to buy/sell it faster than everyone else”. This is where we get to the beauty of low-latency programming.

It’s actually quite easy to write low-latency software, but it’s less easy to predict how that software will perform in production, such as cache line trampling, TLB misses, branch-heavy loops, and fragmentation. Figuring out quirks in how hardware and software interact can actually teach you a lot more than building typical vibecoded trading bots, and these can also be worked into existing projects that you may have, such as for building trading engines.

Getting market data into an order book is only part of a trading engine, as something still has to read that book and decide what to quote. That code may also need a volatility surface, fitted elsewhere and swapped in periodically. Loading a pointer looks like the easy part, but the issue is that the thread doing the swap also wants its memory back. The natural fix is an atomic pointer, but the catch is that atomizing the pointer does nothing to stop someone freeing the object it points to while you are still using it. This is where hazard pointers become interesting, a reader publishes which object it is borrowing, and the cleanup code leaves that object alone. We can build a small version of that protocol and look at the retry loop it introduces.

We’ll use an NASDAQ ITCH-derived order book snapshot. One thread reconstructs the mutable book, copies its best bid and ask, and publishes the copy. Strategy threads borrow that snapshot to calculate spread or imbalance. The copy stays immutable until it is destroyed.

struct Level {
    std::uint32_t price; // fixed point: real price = price * 10^-4.
    std::uint64_t quantity; // q = sum of displayed shares at this price; q = 0 => absent.
};

struct Snapshot {
    std::uint64_t generation; // g_k = k + 1 for publication k >= 0.
    std::uint64_t event_index; // e_(k+1) > e_k; ordinal in the source replay.
    std::uint64_t itch_timestamp_ns; // t in ns since midnight; 0 <= t < 86400 * 10^9.
    std::uint16_t locate; // constant within the input; 1 <= locate <= 65535.
    Level bid;
    Level ask;
};

Prices use ITCH’s integer units of 0.0001, quantities are the total displayed shares at the best price.¹ Keeping both levels inside the snapshot gives us one allocation to protect. A pointer into the builder’s changing arrays would leave the reader exposed to concurrent updates. We’ll start with ordinary hazard pointers and use their retry loop to understand what the wait-free version changes, then look at an implementation for Linux.

Suppose current is an atomic pointer. The publisher constructs next, exchanges it into place, and deletes the old snapshot. The two columns below run on different threads:

// reader                                // publisher
auto* p = current.load(                  auto* old = current.exchange(
    std::memory_order_acquire);              next, std::memory_order_acq_rel);
auto bid = p->bid;                       delete old;

The exchange cannot tear the pointer, but it can happen between the reader’s load and its access to bid:

The acquire load lets the reader observe initialization performed before publication. By the time it reads the bid, though, that initialized object may have been destroyed. We need the publisher to know which snapshots readers are still using. Give each reader a slot in a fixed array. The reader writes the address it is borrowing into that slot, and the publisher checks the slots before deleting anything.

using Token = std::uintptr_t;
constexpr auto sc = std::memory_order_seq_cst;
constexpr std::size_t reader_count = 4;
static_assert(std::atomic<Token>::is_always_lock_free);

struct alignas(64) Hazard {
    std::atomic<Token> pin{0};
};

std::atomic<Token> current{0};
std::array<Hazard, reader_count> hazards;

Token holds a pointer representation, zero means no borrowed object. The example assumes a conventional flat-address compiler/ABI where allocated snapshots have nonzero tokens and validated tokens convert back to the corresponding live objects. That is a platform assumption, not a guarantee supplied by uintptr_t alone.²

The 64-byte alignment separates reader writes on machines with 64-byte cache lines. Without it, threads modifying different slots could keep transferring ownership of the same line. Prefetching can make wider spacing useful, depending on the CPU. Some Intel processors fetch the adjacent line within a 128-byte aligned pair, aligning and spacing slots at 128 bytes keeps neighboring pins out of that pair.³

Now consider the gap between loading current and announcing it. The publisher could remove and free the snapshot during that gap. We have to read current again after writing the slot:

const Snapshot* protect(Hazard& h) noexcept {
    for (;;) {
        const Token candidate = current.load(sc);
        h.pin.store(candidate, sc); // p: publish candidate.
        const Token observed = current.load(sc); // v: p <_sc v.
        if (candidate == observed)
            return observed == 0 ? nullptr
                                 : reinterpret_cast<const Snapshot*>(observed);
    }
}

If the second load disagrees, we retry without touching the candidate’s fields. Even reading its generation would be unsafe at this point. We validate against current, whose storage stays alive for the whole program. All accesses to current and the hazard slots use seq_cst. For these atomics, we can reason about one total order. Call the allocation observed by the successful validation A:

P precedes V in the reader. V observes A before A’s removal U, and the publisher scans only after removal. Therefore S must see the announcement of A or a later write to that slot. If it sees A, it keeps the snapshot. If it sees a later clear or a different announcement, the reader has finished that borrow.

The ordinary field accesses need ordering too. The publishing exchange releases the initialized snapshot, and the validating load acquires it. After the calculation, the reader’s release clear is observed by an acquire scan before destruction. A later release store from the same reader also suffices. Our sequentially consistent operations provide those release/acquire semantics.⁴

Simply changing the announcement to release and the scan to acquire would lose the total-order argument. A scan that reads the old empty slot hasn’t synchronized with the announcement. The stronger orders here let us establish correctness before attempting to reduce their cost.

The publisher exchanges the pointer as before, but saves the old allocation in retired instead of deleting it:

std::vector<Token> retired; // r = removed allocations awaiting reclamation; one owner thread.

void publish(std::unique_ptr<Snapshot> next) {
    assert(next);
    if (retired.size() == retired.capacity())
        retired.reserve(retired.capacity() ? retired.capacity() * 2 : 64);

    const Token replacement = reinterpret_cast<Token>(next.get());
    const Token old = current.exchange(replacement, sc);
    next.release();
    if (old != 0) retired.push_back(old);
}

Reserving storage before the exchange keeps an allocation failure from interrupting the ownership transfer. If reserve throws, the old snapshot is still published and next still owns the replacement. After the exchange, appending the old token doesn’t allocate.

The same thread runs collection. It reads every hazard slot, then frees retired snapshots whose tokens weren’t found:

void collect() {
    std::array<Token, reader_count> pinned{};
    for (std::size_t i = 0; i < reader_count; ++i)
        pinned[i] = hazards[i].pin.load(sc);

    std::size_t keep = 0;
    // reclaim r \ h; h is the set of sampled hazard tokens.
    for (Token object : retired) {
        bool protected_now = false;
        for (Token pin : pinned) protected_now |= pin == object;
        if (protected_now) retired[keep++] = object;
        else delete reinterpret_cast<const Snapshot*>(object);
    }
    retired.resize(keep);
}

The retired batch must be fixed before the scan. Including objects retired after their readers were scanned would allow the collector to miss a new borrow. This example avoids that problem by keeping publication and collection on one thread. A separate collector would need a synchronized retirement handoff.

The slots needn’t be read at one instant. For a borrow that validated before removal, the scan either finds its token or observes a later slot write, after that borrow ended. A reader that validates after removal cannot borrow that retired allocation. If a reader finishes just after being scanned, we retain its snapshot until a later collection.

This small collector does O(readers × retired objects) comparisons. A larger registry could build a searchable set of pins once per batch. With four slots, each completed scan retains at most four distinct retired snapshots. That bound assumes we keep collecting, an idle collector lets the retirement list grow.

The reader keeps its hazard slot occupied for the whole calculation, then clears it. ReadGuard handles that lifetime:

std::optional<Signal> signal;
{
    ReadGuard guard(hazards[reader_id]);
    if (const Snapshot* book = guard.get()) signal = analyse(*book);
}

A spread calculation needs one guard around both sides. Separate acquisitions could combine the bid from one generation with the ask from another, even though each pointer was individually safe.

struct Signal {
    std::uint64_t generation; // g_k = k + 1 for publication k >= 0.
    std::int64_t spread; // d = int64(ask.price) - int64(bid.price).
    double imbalance; // i = (q_bid - q_ask) / (q_bid + q_ask); both q > 0.
};

std::optional<Signal> analyse(const Snapshot& book) noexcept {
    if (book.bid.quantity == 0 || book.ask.quantity == 0) return std::nullopt;
    const double bids = static_cast<double>(book.bid.quantity);
    const double asks = static_cast<double>(book.ask.quantity);
    return Signal{book.generation,
                  std::int64_t(book.ask.price) - std::int64_t(book.bid.price),
                  (bids - asks) / (bids + asks)};
}

The signed subtraction handles crossed books without unsigned wraparound. An empty side produces no signal. Converting quantities to double before the arithmetic avoids integer overflow or underflow, though binary64 can round quantities above 2^53. Equal quantities give zero imbalance; a positive result means the converted bid quantity is larger.

Readers may observe the same generation repeatedly or skip generations when publication runs ahead. A strategy that needs every event would also need a queue or another delivery mechanism.

class ReadGuard {
    Hazard& hazard_;
    const Snapshot* snapshot_;
public:
    explicit ReadGuard(Hazard& h) noexcept
        : hazard_(h), snapshot_(protect(h)) {}
    ~ReadGuard() { hazard_.pin.store(0, sc); }
    ReadGuard(const ReadGuard&) = delete;
    ReadGuard& operator=(const ReadGuard&) = delete;
    const Snapshot* get() const noexcept { return snapshot_; }
};

Each slot supports one active guard. Nesting guards on the same slot would overwrite the first borrow’s protection. Any raw pointer obtained from the guard must stop being used before the guard is destroyed. Return to protect. Its validation can keep failing:

The publisher is making progress throughout this sequence. The reader may still take arbitrarily many attempts. A wait-free acquisition would finish within a bounded number of its own algorithmic steps, regardless of those publications. The is_always_lock_free assertion doesn’t give us that bound. It describes the atomic type, and says nothing about the number of attempts in our loop.⁵ Allocation and collection also have their own progress properties.

The loop exists because loading the pointer and announcing it are separate operations. If we could copy from current directly into the hazard slot atomically, there would be no intermediate state to validate. Blelloch and Wei’s acquire-retire construction does this with swcopy, a primitive that atomically copies into a destination with one writer. They build swcopy in software from pointer-width atomic reads, writes and CAS. It takes constant time, with O(M + P²) total space for M destination objects and P processes. Using it, their construction gives constant-time acquire, release and retire, and expected constant time for eject. We can therefore make acquisition wait-free without a dedicated hardware copy instruction.

On Linux x86-64, Paul Khuong’s construction shortens the reader by relying on the collector for coordination. It uses MOVSQ without REP to copy one eight-byte word. A precise interrupt sees the architectural state before or after that instruction, never a partially completed copy:

# linux x86-64 sysv; df = 0; rsi % 8 = rdi % 8 = 0.
# source and destination storage remain live throughout acquisition.
pin_x86_64:
    movsq                    # m64[rdi] <- m64[rsi]; rsi += 8; rdi += 8
    movq -8(%rdi), %rax       # rax <- m64[rdi - 8]
    ret

This does not make the copy atomic to other cores or turn it into a memory fence, as another core can replace the source after MOVSQ reads it but before the pin becomes visible. The collector handles that gap by fixing its retired batch, calling membarrier, and scanning only after the call succeeds. Each running reader passes an ordering point during the call; a non-running reader is already in the required ordered state. These points needn’t coincide. A copy before its reader’s point leaves a visible pin, unless the borrow has ended and the slot was cleared or reused. A copy after it cannot acquire an allocation already removed into the batch.⁶

We’ll use distinct, naturally aligned eight-byte words in ordinary write-back memory. The source cell must stay alive throughout acquisition, and the slot throughout the borrow and any scan that could read it. As with our C++ guard, each slot belongs to one reader and cannot be reused by a nested acquisition or a signal handler. The reader no longer retries when current changes, but the pointer returned to analyse still travels through the hazard slot. MOVSQ writes it, the following movq reads it into rax, and the caller uses rax to address the book’s fields. Store-to-load forwarding may satisfy that reload from the store buffer, but the field loads still depend on the copy. MOVSQ also updates two address registers; the uops.info measurements show that its cost depends on the processor.

Khuong’s next step is to get a candidate into rax earlier, with an ordinary MOV before the copy. We then compare it with the token written by MOVSQ. If they match, we return the register we already had. Otherwise, we load the copied token. His speculative variant uses the same reclamation protocol:

# linux x86-64 sysv; rsi = source cell; rdi = hazard slot; df = 0.
# rsi % 8 = rdi % 8 = 0; source and slot are distinct, live words.
pin_x86_64_speculative:
    movq (%rsi), %rax        # g <- m64[rsi]; g is an unprotected token
    movsq                   # h <- m64[rsi]; m64[rdi] <- h; rsi += 8; rdi += 8
    cmpq %rax, -8(%rdi)      # zf <- (h == g)
    jne .Lpin_correct       # h != g => select the protected token
    ret                     # rax = g = h
.Lpin_correct:
    movq -8(%rdi), %rax      # rax <- h; no second acquisition
    ret

The -8 reaches the original slot because MOVSQ advanced rdi. Only the owning reader writes this slot; the collector scans it. If an out-of-order CPU predicts equality, it may continue into the caller using the initial movq result while the comparison is pending. Our bid and ask loads can then overlap work they previously had to wait for. MOVSQ still executes; the early register value supplies the address dependency for those later loads. In Khuong’s own measurements on a Xeon E5-4617, the speculative variant cut roughly 15% from plain MOVSQ in pure pointer chasing but still trailed a retrying reader that relied on membarrier; with a few cycles of work per pointer, it pulled slightly ahead.

The comparison must resolve before the speculative instructions can retire. A wrong prediction squashes their results before they become architectural state, although the loads can still affect caches.⁷ Writing the same choice in C++ can lose the instruction sequence we wanted:

Token choose(Token guess, Token pinned) noexcept {
    return guess == pinned ? guess : pinned;
}

For every pair of inputs, the result is pinned. A compiler can reduce this to return pinned, removing the branch and the early register value. An empty asm("" : "+r"(x)) tells the compiler that x may have changed, which kept the early register value with Clang in his tests. GCC still inferred the equality and merged the values again. His addendum gives Alexander Monakov’s plain-C version, whose loop structure preserved speculation with both compilers.

Writing our acquisition in assembly lets us specify the load, copy and branch directly. To see why its mismatch path needs no retry, suppose the early load sees A and MOVSQ observes a later publication of B:

The fallback returns B, which this acquisition already pinned. Loading current again could produce another unprotected token. Both paths instead return the copied token’s value. The early A was only a guess read from the live source cell; it may already be stale and must not be dereferenced in C++ before the check. If the address was reused between loads, the returned token refers to the allocation pinned by MOVSQ, under our pointer-representation assumptions.

The speculative routine has five instructions on the matching path and six on the mismatch path, including ret. Concurrent publications cannot force a retry. Assuming the underlying memory instructions complete and the platform requirements above hold, acquisition finishes in a bounded number of the reader’s own steps. This is the wait-free guarantee for acquiring the pointer. Cache misses, faults and preemption still affect elapsed time, the guarantee gives no timing bound and makes no progress guarantee for the strategy or collector.

The branch provides no synchronization of its own. Initialization must precede publication, and the reader’s field accesses must stay ordered after the copy’s source load and before clearing the slot. For ordinary write-back memory, x86 guarantees these load/load and load/store orders architecturally. The CPU can still execute loads out of order while speculating, if their results would violate those rules, it discards and re-executes the affected work.⁸

The compiler must preserve those orders too, while membarrier orders the copy against reclamation. On Linux, MEMBARRIER_CMD_PRIVATE_EXPEDITED targets running threads in the calling process. Check support with MEMBARRIER_CMD_QUERY and register with MEMBARRIER_CMD_REGISTER_PRIVATE_EXPEDITED before using it.⁶ On the compiler side of that protocol, we can use a memory clobber to prevent memory accesses from moving across a chosen point:

inline void compiler_barrier() noexcept {
    __asm__ __volatile__("" ::: "memory");
}

As the GCC documentation explains, the memory clobber tells the compiler that assembly may access memory. This empty template emits no CPU instruction. Integrating our routines into C++ therefore requires compiler-specific guarantees for concurrent accesses and their ordering. Passing a std::atomic address to assembly doesn’t make raw MOVSQ a C++ atomic operation, and a compiler barrier doesn’t make ordinary C++ data races valid.

Moving collection to a housekeeping core doesn’t change the private command’s process-wide scope.⁶ Any reader latency measurement needs to include collection, since its coordination can interrupt readers even when acquisition is short. Collecting less often reduces the frequency of that coordination but retains more memory. At publication rate R and fixed snapshot size S, leaving reclamation idle for T seconds adds approximately R × T × S bytes of snapshot storage, before allocator overhead. The hazard slots only limit the objects readers pin, they don’t empty the retirement list.