SIMD for Market Data

A SIMD register is split into lanes: 128 bits (SSE2 on every x86-64, NEON on Arm) holds four i32s, 256 bits (AVX2) eight, 512 bits (AVX-512) sixteen. Vertical operations work lane by lane — add, compare, min, max — and are as cheap as their scalar versions, so you get 4–16× the work per instruction. Horizontal operations combine lanes — sum all lanes, find the first set lane — and need shuffles or special instructions. The rule of thumb: stay vertical inside the loop, go horizontal once at the end.

Three practical caveats:

• Layout decides everything. Lanes load contiguous memory. Summing qty from a struct-of-arrays ladder is one load per eight levels; summing it from an array of 24-byte Level structs needs gathers or shuffles and often is not worth vectorizing. Week 28 was this week's prerequisite for a reason.
• Width is not free. On some Intel server generations (Skylake-SP in particular), sustained heavy 512-bit work lowers the core's clock, which can slow down the scalar code around it; newer Intel cores reduce the effect, and AMD's Zen 4 executes AVX-512 on 256-bit datapaths. This is hardware-specific — measure on your target.
• The baseline matters. A default x86_64-unknown-linux-gnu build may only assume SSE2 (128-bit). AVX2 needs -C target-cpu=..., -C target-feature=+avx2, or runtime detection (Day 4).

LLVM vectorizes loops when it can prove it is safe and profitable: a countable loop, no early exit, no aliasing it cannot rule out, operations that have vector forms. Rust helps because slices carry their length and &mut guarantees no aliasing.

// Vectorizes: counted loop, integer reduction (reassociation is exact).
pub fn depth(qty: &[u32]) -> u64 {
    qty.iter().map(|&q| q as u64).sum()
}

// Does NOT vectorize as a reduction: f64 addition is not associative, and
// LLVM may not reorder it without fast-math permission.
pub fn notional_f64(px: &[f64], qty: &[f64]) -> f64 {
    px.iter().zip(qty).map(|(p, q)| p * q).sum()
}

// Does NOT vectorize: data-dependent early exit.
pub fn first_ge(px: &[i32], t: i32) -> Option<usize> {
    px.iter().position(|&p| p >= t)
}

The float case deserves a second look: summing in lanes changes the result in the last bits, because floating-point addition is not associative. That is why the compiler refuses, and why prices and quantities in an exchange are integers (week 8): integer sums — even wrapping ones — give the identical answer in any order.

How to check: cargo asm (cargo-show-asm) or Compiler Explorer. Look for vector registers (xmm = 128-bit, ymm = 256-bit, zmm = 512-bit) and packed instructions (vpaddq, vpcmpgtd). Then rebuild with -C target-cpu=native (or -C target-cpu=x86-64-v3, the level that includes AVX2) and watch xmm become ymm.

Depth aggregation answers questions market-data consumers and the risk layer ask constantly: how much quantity rests in the first N levels, and how many levels does a market order of size Q sweep? Three techniques make these loops vector-friendly:

• Explicit lanes. Accumulate into [u64; 8] over chunks_exact(8), then the remainder, then one horizontal sum. This spells out the independence the vectorizer needs, and it is portable — no unsafe, no intrinsics.
• Widening. Quantities are u32; sixty-four levels of u32::MAX overflow a u32 sum. Widen each element to u64 before adding. (In intrinsics this is an explicit zero-extend; in the portable version it is as u64.)
• Two-phase search. "How many levels until the cumulative quantity reaches Q" has an early exit, which blocks vectorization. Split it: sum whole blocks of eight with the lane trick until the block that crosses Q, then walk that one block level by level.

Run the drill in release mode and look at the timing case. In our runs the plain iterator sum() in the starter was already vectorized by LLVM, and the explicit-lane version was only modestly faster. That is the "know when the compiler already did it" lesson in one number.

/// Scalar reference: total quantity in the first `n` levels (n clamped).
pub fn depth_scalar(qty: &[u32], n: usize) -> u64 {
    qty[..n.min(qty.len())].iter().map(|&q| q as u64).sum()
}

/// Same answer, shaped for the vectorizer: eight independent u64
/// accumulators over chunks_exact(8), then the remainder, then one
/// horizontal sum. Widen before adding — no lane may overflow.
pub fn depth_lanes(qty: &[u32], n: usize) -> u64 {
    todo!()
}

/// How many levels a market order of `target` quantity sweeps: the smallest
/// k with qty[0] + ... + qty[k-1] >= target. Some(0) when target is 0;
/// None when the whole book holds less. Sum whole 8-level blocks first and
/// walk level by level only inside the block that crosses the target.
pub fn levels_to_fill(qty: &[u32], target: u64) -> Option<usize> {
    todo!()
}

/// Notional of the first n levels: sum of px[i] * qty[i] (n clamped to both
/// lengths) with WRAPPING multiply and add, accumulated in 4 lanes, so the
/// result equals the scalar wrapping sum exactly.
pub fn notional_lanes(px: &[i64], qty: &[u32], n: usize) -> i64 {
    todo!()
}

Finding a level by price in a sorted window is a search, and searches have early exits. The SIMD idiom turns the search into counting: in a sorted array, the index of the first element ≥ target equals the number of elements < target. Compare eight prices against the target in one instruction, collapse the comparison into an 8-bit mask, popcount it, add — no branches, no early exit, the same work for every query.

#[cfg(target_arch = "x86_64")]
#[target_feature(enable = "avx2")]
unsafe fn count_below_avx2(px: &[i32], target: i32) -> usize {
    use std::arch::x86_64::*;
    let t = _mm256_set1_epi32(target);                // broadcast target to 8 lanes
    let mut n = 0;
    for c in px.chunks_exact(8) {
        let v = _mm256_loadu_si256(c.as_ptr() as *const __m256i);
        let lt = _mm256_cmpgt_epi32(t, v);             // lane = all ones where v < target
        let m = _mm256_movemask_ps(_mm256_castsi256_ps(lt)) as u32; // 1 bit per lane
        n += m.count_ones() as usize;
    }
    n // + the remainder, scalar
}

The safety contract: a #[target_feature] function may only be called on a CPU that has the feature, so it is unsafe to call, and you check first with is_x86_feature_detected!("avx2") (the result is cached, so the check is cheap but not free). Two details that bite:

• AVX2 integer compares are signed. _mm256_cmpgt_epi32 compares as i32. For u32 quantities above i32::MAX, flip the sign bit of both operands (XOR with 0x8000_0000) before comparing, or use a portable path.
• Dispatch cost. A #[target_feature] function cannot be inlined into a caller compiled without that feature, so per-call dispatch adds a check and a real call to every lookup. For a 64-level window that overhead is comparable to the work. Dispatch once — pick a function pointer at startup, or compile the whole hot path with the feature enabled.

How close is it? On one AMD Zen 3 server, a 64-level lookup took about 5–7 ns with Rust's partition_point (which is already a branchless binary search), about 10 ns with the AVX2 count behind per-call runtime dispatch, and under 5 ns with the same AVX2 count compiled with -C target-cpu=native so it inlined. Your numbers will differ; the ranking is the lesson.

/// Scalar reference: first index i with px[i] >= target in an ascending
/// array (px.len() if there is none).
pub fn lower_bound_scalar(px: &[i32], target: i32) -> usize {
    px.iter().position(|&p| p >= target).unwrap_or(px.len())
}

/// Branch-free lower bound for a SORTED array: the answer equals how many
/// elements are < target. Count them 8 lanes at a time, no early exit.
pub fn lower_bound_count(px: &[i32], target: i32) -> usize {
    todo!()
}

/// AVX2: _mm256_set1_epi32, _mm256_loadu_si256, _mm256_cmpgt_epi32,
/// _mm256_movemask_ps(_mm256_castsi256_ps(..)), count_ones; scalar tail.
#[cfg(target_arch = "x86_64")]
#[target_feature(enable = "avx2")]
unsafe fn lower_bound_avx2(px: &[i32], target: i32) -> usize {
    todo!()
}

/// Dispatch: call lower_bound_avx2 when is_x86_feature_detected!("avx2"),
/// otherwise lower_bound_count. Must compile on non-x86 targets too.
pub fn lower_bound(px: &[i32], target: i32) -> usize {
    todo!()
}

/// UNSORTED scan: first level whose quantity is >= min_qty. Per chunk of 8,
/// build a hit mask (bit i set when chunk[i] >= min_qty); if non-zero, the
/// answer is in this chunk at mask.trailing_zeros(). Mind the remainder.
pub fn first_at_least(qty: &[u32], min_qty: u32) -> Option<usize> {
    todo!()
}

Text protocols are where SIMD earns its keep. FIX (week 14) is a sequence of tag=value fields separated by the SOH byte (0x01). A scalar parser looks at one byte at a time. A SIMD scanner loads 32 bytes, compares all of them against 0x01 with _mm256_cmpeq_epi8, movemasks the result into a 32-bit integer whose set bits are the field boundaries, and walks them with trailing_zeros — the simdjson pattern. FIX's CheckSum is the sum of all bytes modulo 256, and _mm256_sad_epu8 against a zero vector sums each group of eight bytes in one instruction.

Fixed-layout binary protocols (ITCH, SBE, your week 11 wire format) usually gain little: every field is at a known offset, so "parsing" is already a handful of loads. Do not vectorize something that is not a loop.

A SIMD benchmark is easy to win and easy to fake. The checklist:

• Same flags for both sides. Compare against the scalar code compiled in release with the same target-cpu — not a debug build, not a build where you disabled the vectorizer.
• Realistic sizes. A book with ten levels and a window with 4,096 have different winners; fixed costs (dispatch, horizontal reduction, remainder handling) dominate small inputs. Benchmark the sizes your feed actually produces.
• Cache residency. If the data streams from DRAM, the loop is memory-bound and wider vectors barely help. State whether your benchmark is L1-resident and whether production is.
• Identical results. Property-test the SIMD path against the scalar path on random inputs, including lengths that are not multiples of the vector width, negative values and extremes.
• End-to-end effect. A 4× faster depth sum that was 1% of the publish path changes nothing. Re-run the week 25 open-loop measurement.