Low-Latency Interview Deep Dives

Most memory-ordering questions reduce to four litmus tests. Know each one's forbidden outcome, the weakest orderings that forbid it, and what x86 and ARM do without help.

• Message passing (MP). Thread 1 writes data, then sets a flag. Thread 2 reads the flag, then the data. Can it see the flag set and stale data? In Rust it can, unless the flag store is Release and the flag load is Acquire. Those two form a synchronises-with edge, so the data write happens-before the data read. x86 hardware never shows the stale outcome, because stores aren't reordered with stores and loads aren't reordered with loads, but the compiler can still reorder Relaxed operations. ARM and POWER hardware do show it.
• Store buffering (SB). Each thread stores to its own flag and then loads the other's. Can both loads see 0? Yes, even on x86, because a store can sit in the store buffer while a later load to a different address completes. This is the one reordering x86-TSO allows. Acquire/Release doesn't help, because no load reads from the other thread's store, so no synchronises-with edge exists. Only SeqCst on all four operations, or SeqCst fences between store and load, forbids it. This is Dekker's and Peterson's problem, and why a SeqCst store on x86 compiles to xchg (or mov + mfence).
• Load buffering (LB). Each thread loads one location and then stores to the other. Can both loads see the other's later store? The C++/Rust model allows it with Relaxed. x86 forbids it in hardware. In the language you need Acquire loads and Release stores: then each load synchronises with the other thread's store, and the two outcomes together would form a happens-before cycle.
• IRIW (independent reads of independent writes). Two writers each write a different variable, and two readers read both in opposite orders. Can the readers disagree about which write happened first? With Acquire/Release, yes. Only SeqCst gives a single total order everyone agrees on. Hardware differs: POWER can show it even with ordered reads, while x86 and ARMv8 (which is "other-multi-copy atomic") don't once each reader's two loads are ordered.

data.store(1, Relaxed);
flag.store(1, Relaxed);

let r1 = flag.load(Relaxed);
let r2 = data.load(Relaxed);

x.store(1, Relaxed);
let r1 = y.load(Relaxed);

y.store(1, Relaxed);
let r2 = x.load(Relaxed);

Know these orders of magnitude for a current x86 server, and know that every one varies by microarchitecture:

• Cache line. 64 bytes on x86 (Apple's M-series uses 128-byte lines). Intel's spatial prefetcher fetches lines in adjacent pairs, which is why crossbeam's CachePadded aligns to 128 bytes on x86-64.
• Hit latencies. L1 ~4–5 cycles (~1 ns), L2 ~12–16 cycles (~3–5 ns), L3 ~40–70 cycles (~10–20 ns), local DRAM ~80–100 ns, remote-socket DRAM ~1.5–2× that.
• Coherence. Writing a line requires exclusive ownership (MESI and its variants), so writing a line another core holds means invalidating its copy and transferring the line: roughly 50–100 ns between cores on one socket, often over 100 ns across sockets. That's the real cost of a contended atomic and of false sharing, not the instruction itself.
• Prefetchers reward sequential and strided access and can't help a pointer chase. That's why a linked list of orders loses to an array even when big-O says otherwise.
• TLB. With 4 KiB pages, an L1 data TLB of ~64 entries covers ~256 KiB. A random walk over a 1 GiB book misses the TLB constantly and pays page walks. 2 MiB huge pages cut that by 512×.
• Branch mispredict ~15–20 cycles: invisible on average, visible in a tight matching loop.

The canonical networking deep dive is "walk me through what happens when a packet arrives". A strong answer names the stages and roughly what each costs:

1. The NIC DMAs the frame into a receive-ring buffer in host memory, and may timestamp it.
2. It raises an interrupt, possibly delayed by interrupt coalescing (ethtool -C, often tens of µs by default), or the driver is already busy-polling.
3. The kernel's NAPI poll runs in softirq context, builds an sk_buff, and runs IP and UDP/TCP processing.
4. The data is queued on the socket's receive buffer, and the waiting thread is woken: a scheduler wakeup, a context switch if it was asleep, possibly on another core.
5. The thread's recv copies the data to user space and returns.

On a tuned host, a one-way kernel UDP path from wire to application is typically a few microseconds, with wakeups and coalescing dominating the tail. With kernel bypass (week 33) the application polls the NIC ring directly from user space and the same path is around a microsecond or less.

Other perennials, with numbers:

• Syscall. The bare entry and exit costs on the order of 100 ns on modern CPUs, more with some side-channel mitigations. A context switch costs a few µs once you count the cache and TLB damage.
• Page faults. A minor fault costs around a microsecond. A major fault (from disk) costs milliseconds. Pre-fault and mlock the hot path.
• Nagle plus delayed ACK. Small writes held back by Nagle's algorithm while the peer delays its ACK produce stalls of tens of milliseconds (Linux's minimum delayed-ACK timeout is 40 ms). Set TCP_NODELAY on order sessions.
• The scheduler. Linux moved from CFS to EEVDF in 6.6, but on a hot core the answer is the same: pin the thread, isolate the core and don't let the scheduler make decisions there.

Rules for timed coding: state the invariants before writing code, narrate your ordering choices as you write them, test as you go, and leave five minutes for the questions you know are coming (cached indices, padding, batching, why &mut self).

This version is harder than week 1's: generic over non-Copy T, with runtime capacity rounded up to a power of two (so index & mask replaces %), MaybeUninit slots, and a Drop that drops exactly the values still in the ring. The harness counts drops, so leaks and double drops both fail.

use std::cell::UnsafeCell;
use std::mem::MaybeUninit;
use std::sync::atomic::{AtomicUsize, Ordering};
use std::sync::Arc;

struct Shared<T> {
    slots: Box<[UnsafeCell<MaybeUninit<T>>]>,
    mask: usize,       // capacity - 1 (capacity is a power of two)
    head: AtomicUsize, // next index to write; only the producer stores it
    tail: AtomicUsize, // next index to read; only the consumer stores it
}

// SAFETY: write your argument here before you write the code.
unsafe impl<T: Send> Send for Shared<T> {}
unsafe impl<T: Send> Sync for Shared<T> {}

pub struct Producer<T> {
    shared: Arc<Shared<T>>,
}

pub struct Consumer<T> {
    shared: Arc<Shared<T>>,
}

/// Capacity is rounded up to a power of two (minimum 1).
pub fn spsc<T>(capacity: usize) -> (Producer<T>, Consumer<T>) {
    let _ = capacity;
    todo!()
}

impl<T> Producer<T> {
    /// Err(value) when full, handing the value back.
    pub fn try_push(&mut self, value: T) -> Result<(), T> {
        let _ = value;
        todo!()
    }

    pub fn capacity(&self) -> usize {
        self.shared.mask + 1
    }
}

impl<T> Consumer<T> {
    pub fn try_pop(&mut self) -> Option<T> {
        todo!()
    }

    /// Items currently in the ring, as seen by the consumer.
    pub fn len(&self) -> usize {
        todo!()
    }
}

impl<T> Drop for Shared<T> {
    fn drop(&mut self) {
        // TODO: drop every value still in [tail, head), exactly once.
    }
}

The LRU is a classic for a reason. It combines a hash index with an ordered structure, and the low-latency twist is no allocation after construction. Allocation on the hot path is a tail-latency problem: malloc is usually tens of nanoseconds, but occasionally it must fetch memory from the OS and fault pages in, and that's microseconds. The usual design is an array-backed slab of nodes linked by u32 indices (no Box, no Rc<RefCell>), with eviction reusing the least recently used slot in place.

The harness installs a counting global allocator and runs 50,000 operations after warm-up. Try the obvious HashMap::with_capacity(cap) first and watch it fail. With today's std HashMap, steady remove-then-insert churn leaves deleted-slot tombstones that eat the table's growth budget, and a table sized for exactly cap entries eventually resizes. Explaining why, and the fixes (headroom, or your own open-addressing table with backward-shift deletion), is exactly the follow-up an interviewer wants.

use std::collections::HashMap;

const NIL: u32 = u32::MAX;

struct Node {
    key: u64,
    value: u64,
    prev: u32, // towards the most recently used end; NIL at the head
    next: u32, // towards the least recently used end; NIL at the tail
}

/// Fixed-capacity LRU cache that never allocates after `with_capacity`.
pub struct Lru {
    nodes: Vec<Node>,         // slab; grows to `cap` once, then slots are reused
    index: HashMap<u64, u32>, // key -> slot
    head: u32,                // most recently used (NIL when empty)
    tail: u32,                // least recently used (NIL when empty)
    cap: usize,
}

impl Lru {
    /// cap >= 1. Allocate everything you will ever need here.
    pub fn with_capacity(cap: usize) -> Self {
        let _ = cap;
        todo!()
    }

    /// The value for `key`, marking it most recently used.
    pub fn get(&mut self, key: u64) -> Option<u64> {
        let _ = key;
        todo!()
    }

    /// Insert or update `key` as most recently used. If a new key doesn't
    /// fit, evict the least recently used entry and return it.
    pub fn put(&mut self, key: u64, value: u64) -> Option<(u64, u64)> {
        let _ = (key, value);
        todo!()
    }

    pub fn len(&self) -> usize {
        todo!()
    }
}

The strongest deep-dive answers come from your own system: "In my exchange, the matching loop's p99 was 1.4 µs until I found false sharing between the sequence counter and the stats counter. Padding took it to 600 ns, and here's the perf c2c output." Prepare six such stories: one each on memory ordering, cache behaviour, allocation, kernel networking, a correctness bug, and a measurement mistake you made and caught. For each: the symptom, the hypothesis, the evidence, the fix and the number before and after.

Then run a full mock with the AI interviewer, asking it to deep-dive one component of your exchange, and do a round of spot-the-concurrency-bug at /hft/drills to warm up.