Skip to content

simd.md

Latest commit

 

History

History
1039 lines (780 loc) · 44.8 KB

simd.md

File metadata and controls

1039 lines (780 loc) · 44.8 KB
Raw

SIMD (Single Instruction, Multiple Data)

Home > Docs > Optimizations > SIMD

SIMD enables parallel processing of multiple data elements with a single instruction. Modern CPUs provide various SIMD extensions with different vector widths and capabilities.

Overview

Extension Width Platform Key Instructions Best For
SSE2 128-bit x86_64 Basic vector ops Baseline
AVX2 256-bit x86_64 Wide vectors, gather Memory-bound work
AVX-512 512-bit x86_64 VPOPCNTDQ, masked ops Compute-bound only
BMI2 64-bit x86_64 PDEP, PEXT Bit manipulation
NEON 128-bit ARM64 TBL, CNT, parallel ops ARM baseline
PMULL 64→128 ARM64 Carryless multiply Prefix XOR (DSV)
SVE2-BITPERM 64-bit ARM64 BDEP, BEXT Bit deposit/extract

x86_64 SIMD Hierarchy

SSE2 (Baseline)

Available on all x86_64 CPUs. 128-bit vectors (16 bytes).

use core::arch::x86_64::*;

unsafe fn classify_sse2(data: &[u8; 16]) -> u16 {
    let chunk = _mm_loadu_si128(data.as_ptr() as *const __m128i);

    // Compare for specific characters
    let quotes = _mm_cmpeq_epi8(chunk, _mm_set1_epi8(b'"' as i8));
    let backslash = _mm_cmpeq_epi8(chunk, _mm_set1_epi8(b'\\' as i8));

    // Extract to bitmask
    let mask = _mm_or_si128(quotes, backslash);
    _mm_movemask_epi8(mask) as u16
}

Key instructions:

  • _mm_cmpeq_epi8: Compare 16 bytes in parallel
  • _mm_movemask_epi8: Extract comparison results to 16-bit mask
  • _mm_loadu_si128: Unaligned 128-bit load

AVX2

256-bit vectors (32 bytes). Best for memory-bound workloads.

use core::arch::x86_64::*;

unsafe fn classify_avx2(data: &[u8; 32]) -> u32 {
    let chunk = _mm256_loadu_si256(data.as_ptr() as *const __m256i);

    // Character classification
    let quotes = _mm256_cmpeq_epi8(chunk, _mm256_set1_epi8(b'"' as i8));
    let colon = _mm256_cmpeq_epi8(chunk, _mm256_set1_epi8(b':' as i8));
    let comma = _mm256_cmpeq_epi8(chunk, _mm256_set1_epi8(b',' as i8));
    // ... more characters ...

    let structural = _mm256_or_si256(quotes, _mm256_or_si256(colon, comma));
    _mm256_movemask_epi8(structural) as u32
}

Result in succinctly: 78% faster JSON parsing vs SSE2.

AVX-512

512-bit vectors. Use with caution - not always faster.

use core::arch::x86_64::*;

#[target_feature(enable = "avx512vpopcntdq")]
unsafe fn popcount_avx512(words: &[u64; 8]) -> u64 {
    let data = _mm512_loadu_si512(words.as_ptr() as *const i32);
    let counts = _mm512_popcnt_epi64(data);
    _mm512_reduce_add_epi64(counts) as u64
}

When AVX-512 wins: Compute-bound operations like popcount — but only against a baseline build. Explicit VPOPCNTDQ is 5–9× faster than count_ones() when the latter is left as scalar broadword (default cargo build), yet drops to ≈1× once you compile with -C target-cpu=native and LLVM auto-vectorizes count_ones() to VPOPCNTDQ itself. See Popcount Strategies for the full measured data.

When AVX-512 loses: Memory-bound operations like JSON parsing (7-17% slower) and YAML parsing (7% slower at 64B).

Why it can be slower:

  1. Memory bandwidth bottleneck: Sequential text parsing saturates RAM bandwidth at AVX2 width already
  2. Zen 4 splits AVX-512 ops: Physical execution units are 256-bit wide, so 512-bit ops split into two 256-bit micro-ops (overhead without benefit)
  3. Higher power → frequency throttling: CPU may reduce clock speed with AVX-512
  4. Benchmark design matters: Measuring loop iterations vs actual work can show misleading "wins"

Lessons from YAML P8 rejection (2026-01-18):

  • AVX-512 showed 7% regression at realistic 64B chunk size
  • Apparent "2x wins" at 256B+ were benchmark artifacts (half the loop iterations, not twice the efficiency)
  • Real parsing scans linearly → AVX2 and AVX-512 do same total work, but AVX-512 adds overhead
  • Pattern: When JSON AVX-512 failed (7-17% slower), YAML AVX-512 also failed (same memory-bound workload)
  • See docs/parsing/yaml.md for full analysis

ARM NEON

128-bit vectors, always available on ARM64.

Basic Operations

use core::arch::aarch64::*;

unsafe fn classify_neon(data: &[u8; 16]) -> u16 {
    let chunk = vld1q_u8(data.as_ptr());

    // Character comparisons
    let quotes = vceqq_u8(chunk, vdupq_n_u8(b'"'));
    let backslash = vceqq_u8(chunk, vdupq_n_u8(b'\\'));

    let mask = vorrq_u8(quotes, backslash);
    neon_movemask(mask)
}

NEON Movemask (Custom)

NEON lacks movemask. Use multiplication trick:

unsafe fn neon_movemask(mask: uint8x16_t) -> u16 {
    // Extract high bit of each byte
    let high_bits = vshrq_n_u8(mask, 7);

    // Pack into u64 using magic multiplication
    let magic: u64 = 0x0102040810204080;

    let lo = vget_low_u8(high_bits);
    let hi = vget_high_u8(high_bits);

    let lo_sum = vaddv_u8(vmul_u8(lo, vcreate_u8(magic)));
    let hi_sum = vaddv_u8(vmul_u8(hi, vcreate_u8(magic)));

    ((hi_sum as u16) << 8) | (lo_sum as u16)
}

Result: 10-18% improvement over variable shifts.

When only "any match" and "first match" are needed, use the shrn nibble mask instead (neon_nibble_mask in util/simd/escape.rs, #2963): one narrowing shift packs every lane's top nibble into a u64, so mask != 0 is the any-match test and mask.trailing_zeros() / 4 is the first lane, after a single vector-to-GPR transfer.

unsafe fn neon_nibble_mask(v: uint8x16_t) -> u64 {
    // nibble i of the result is 0xF iff lane i of `v` is 0xFF
    let nibbles = vshrn_n_u16::<4>(vreinterpretq_u16_u8(v));
    vget_lane_u64::<0>(vreinterpret_u64_u8(nibbles))
}

The multiply form costs two lane extracts, two 64-bit multiplies and a shift-and-or on the critical path of every chunk; that latency is what made a per-string 16-byte chunk lose to a scalar loop on an M4 Pro (see the #2963 section). Keep the multiply form where a dense 16-bit mask is consumed (bit iteration, popcount, concatenation with a neighbouring chunk).

NEON Table Lookup (vqtbl1q_u8)

16 parallel lookups from a 16-entry table:

unsafe fn nibble_classify(chars: uint8x16_t) -> uint8x16_t {
    let lo_nibble = vandq_u8(chars, vdupq_n_u8(0x0F));
    let hi_nibble = vshrq_n_u8(chars, 4);

    let lo_table = vld1q_u8(LO_TABLE.as_ptr());
    let hi_table = vld1q_u8(HI_TABLE.as_ptr());

    let lo_result = vqtbl1q_u8(lo_table, lo_nibble);
    let hi_result = vqtbl1q_u8(hi_table, hi_nibble);

    vandq_u8(lo_result, hi_result)
}

Result: Replaces 13 comparisons with 6 operations.

Exactness caveat (#186): each bit plane of lo_table[lo] & hi_table[hi] matches exactly the Cartesian product {lo nibbles} × {hi nibbles} it is set for. A byte set that is not such a product (e.g. ,+:, or a range like A-Z that spans two hi nibbles) needs one bit plane per product — sharing a plane over-matches neighbouring bytes (@ \ ^ _ for a shared "uppercase" plane) and silently diverges from backends using exact range compares. Exhaustive 256-byte table tests in json/simd/neon.rs enforce this.

NEON PMULL for Prefix XOR (2026-01-22)

Carryless multiplication computes prefix XOR in O(1) instead of O(log n):

#[target_feature(enable = "neon")]
unsafe fn prefix_xor_neon(x: u64) -> u64 {
    use core::arch::aarch64::*;

    // Load x into polynomial register
    let a = vreinterpretq_p64_u64(vdupq_n_u64(x));
    let b = vreinterpretq_p64_u64(vdupq_n_u64(!0u64));

    // Carryless multiply: prefix_xor(x) = clmul(x, 0xFFFF...FFFF)
    let product = vmull_p64(vgetq_lane_p64::<0>(a), vgetq_lane_p64::<0>(b));

    vgetq_lane_u64::<0>(vreinterpretq_u64_p128(product))
}

Why it works: Carryless multiplication by all-1s propagates each bit to all higher positions via XOR, which is exactly the prefix XOR operation (cumulative XOR from bit 0 to bit i).

Result: 25% faster DSV index building on ARM64 (3.18 → 3.84 GiB/s on Graviton 4).

Platform support: Works on ALL ARM64 (ARMv8 Cryptography Extension is mandatory since ARMv8.0).

NEON Popcount

unsafe fn popcount_neon(data: &[u8; 64]) -> u32 {
    let mut sum = vdupq_n_u8(0);

    for chunk in data.chunks_exact(16) {
        let v = vld1q_u8(chunk.as_ptr());
        sum = vaddq_u8(sum, vcntq_u8(v));
    }

    // Horizontal sum with widening to avoid overflow
    let sum16 = vpaddlq_u8(sum);
    let sum32 = vpaddlq_u16(sum16);
    let sum64 = vpaddlq_u32(sum32);

    vgetq_lane_u64(sum64, 0) as u32 + vgetq_lane_u64(sum64, 1) as u32
}

NEON Horizontal Reductions (VMINV, VMAXV, VADDV)

NEON provides horizontal reduction instructions that operate across all lanes:

use core::arch::aarch64::*;

unsafe fn find_min_across_vector(values: int16x8_t) -> i16 {
    vminvq_s16(values)  // Single instruction - finds minimum across 8 lanes
}

unsafe fn sum_across_vector(values: int16x8_t) -> i16 {
    vaddvq_s16(values)  // Single instruction - sums all 8 lanes
}

Result in succinctly: VMINV enables 2.8x faster BP index construction by finding block minimums in a single instruction instead of a scalar loop.

Key pattern: Combine SIMD prefix sums with horizontal reduction:

  1. Load 8 values
  2. Compute prefix sums using parallel prefix (3 shuffle+add steps)
  3. Add offset to all values
  4. Use VMINV/VMAXV to find min/max in one instruction

ARM SVE2-BITPERM (Graviton 4+)

SVE2-BITPERM provides BDEP (bit deposit) and BEXT (bit extract) instructions equivalent to x86 BMI2 PDEP/PEXT. Available on Neoverse-V2 (AWS Graviton 4) and Azure Cobalt 100.

BDEP for select_in_word (2026-01-23)

The select_in_word(x, k) function finds the position of the k-th set bit in a 64-bit word. The BDEP implementation provides O(1) complexity vs O(k) for the CTZ loop:

#[target_feature(enable = "sve2-bitperm")]
pub unsafe fn select_in_word_bdep(x: u64, k: u32) -> u32 {
    if x == 0 { return 64; }
    let pop = x.count_ones();
    if k >= pop { return 64; }

    // Create mask with k+1 low bits set
    let mask = if k >= 63 { u64::MAX } else { (1u64 << (k + 1)) - 1 };

    // BDEP scatters the mask bits to positions where x has set bits
    let scattered = bdep_u64(mask, x);

    // Find highest set bit (the k-th bit position)
    63 - scattered.leading_zeros()
}

Micro-benchmark results (AWS Graviton 4):

Pattern CTZ Loop BDEP Speedup
sparse (k=0) 0.88 ns 1.78 ns 0.5x (CTZ wins)
dense (64 bits) 20.4 ns 1.7 ns 12x
high_k (k=32-63) 30.8 ns 1.8 ns 17x
mixed patterns 9.6 ns 1.8 ns 5.4x

End-to-end results (full select1 operations):

Benchmark Change Notes
select1/1M/90% -4.9% Dense bitvectors benefit most
select1/10M/50% -1.8% Modest improvement

Why modest end-to-end improvement: SelectIndex provides O(1) jump to approximate position, so most selects only need 1-2 select_in_word calls. The optimization benefits dense patterns most.

Platform support: Requires SVE2-BITPERM (Graviton 4+). Falls back to CTZ loop on older CPUs.

x86 SSE4.1 Horizontal Minimum (PHMINPOSUW)

SSE4.1 provides PHMINPOSUW (_mm_minpos_epu16) for finding the minimum across 8 unsigned 16-bit values. This is the x86 equivalent of ARM NEON's vminvq_s16, but with a key limitation: unsigned only.

Bias Trick for Signed Values

To use PHMINPOSUW with signed i16 values (like min_excess which can be negative):

use core::arch::x86_64::*;

#[target_feature(enable = "sse4.1")]
unsafe fn horizontal_min_i16(values: __m128i) -> i16 {
    // Bias by 0x8000 to convert signed range [-32768, 32767] to unsigned [0, 65535]
    let bias = _mm_set1_epi16(i16::MIN);  // 0x8000
    let biased = _mm_add_epi16(values, bias);

    // Find unsigned minimum with PHMINPOSUW
    let minpos = _mm_minpos_epu16(biased);
    let biased_min = _mm_extract_epi16(minpos, 0) as i16;

    // Unbias: wrapping add converts back to signed
    biased_min.wrapping_add(i16::MIN)
}

Application: BP L1/L2 Index Building (2026-01-24)

Used SSE4.1 to accelerate balanced parentheses index construction, mirroring the NEON VMINV optimization.

Benchmark Results (AMD Ryzen 9 7950X, Zen 4):

Size Scalar SSE4.1 Improvement
10K nodes 1.97 µs 1.98 µs ~0% (neutral)
100K nodes 18.96 µs 18.97 µs ~0% (neutral)
1M nodes 188.0 µs 197.2 µs -5% (regression)
10M nodes 3.15 ms 3.05 ms +3%
100M nodes 31.98 ms 31.36 ms +2%
500M nodes 253.8 ms 250.6 ms +1%

Why SSE4.1 is less effective than ARM NEON:

Factor ARM NEON x86 SSE4.1
Horizontal min vminvq_s16 (signed direct) _mm_minpos_epu16 (unsigned only)
Horizontal sum vaddvq_s16 (single instruction) Multiple shifts + adds
Bias overhead None needed +2 ops per block
Result 2.8x improvement 1-3% improvement (large data)

Key insight: ARM's vminvq_s16 handles signed values directly in a single instruction. SSE4.1's unsigned-only PHMINPOSUW requires bias/unbias overhead that negates most benefit at typical data sizes. Only at 10M+ nodes does the SSE4.1 path show measurable improvement.

Future opportunity: AVX-512 provides _mm512_reduce_min_epi16 which handles signed 16-bit values directly and processes 32 lanes. This could provide better results on CPUs with efficient AVX-512 execution.

Runtime Feature Detection

x86_64

fn select_simd_impl() -> impl Fn(&[u8]) -> Vec<u64> {
    if is_x86_feature_detected!("avx2") {
        avx2_impl
    } else {
        sse2_impl
    }
}

Dispatch order: AVX-512 VPOPCNTDQ → AVX2+BMI2 → AVX2 → SSE2

ARM64

NEON is always available - no runtime detection needed:

#[cfg(target_arch = "aarch64")]
fn process(data: &[u8]) -> Vec<u64> {
    neon_impl(data)
}

SIMD Patterns

Character Classification

Process N bytes, produce N-bit mask:

// Input:  ['{', 'a', '"', 'b', '}', ...]
// Output: [1,   0,   1,   0,   1,   ...]  (structural chars)

Pattern:

  1. Load vector
  2. Compare against each target character
  3. OR results together
  4. Extract to bitmask

Prefix Operations

Compute cumulative XOR/sum across vector:

fn prefix_xor(mut y: u64) -> u64 {
    y ^= y << 1;
    y ^= y << 2;
    y ^= y << 4;
    y ^= y << 8;
    y ^= y << 16;
    y ^= y << 32;
    y
}

Application: Quote state tracking in CSV/JSON parsing.

Batch Processing

Process chunks larger than vector width:

// Process 64 bytes using 2x AVX2 (32-byte) loads
unsafe fn process_64_avx2(data: &[u8; 64]) -> u64 {
    let lo = _mm256_loadu_si256(data[0..32].as_ptr() as *const __m256i);
    let hi = _mm256_loadu_si256(data[32..64].as_ptr() as *const __m256i);

    let lo_mask = classify_avx2(lo);
    let hi_mask = classify_avx2(hi);

    (lo_mask as u64) | ((hi_mask as u64) << 32)
}

Successful SIMD Optimizations

YAML Unquoted Structural Skip (+3-8%)

Pattern: Use SIMD to find the next structural character (\n, #, :) in unquoted values, then handle context-aware validation at scalar level.

// NEON implementation - find next \n, #, or :
let newline_vec = vdupq_n_u8(b'\n');
let hash_vec = vdupq_n_u8(b'#');
let colon_vec = vdupq_n_u8(b':');

while offset + 16 <= len {
    let chunk = vld1q_u8(data.as_ptr().add(offset));

    // Compare against all three targets
    let newlines = vceqq_u8(chunk, newline_vec);
    let hashes = vceqq_u8(chunk, hash_vec);
    let colons = vceqq_u8(chunk, colon_vec);

    // OR all results together
    let matches = vorrq_u8(vorrq_u8(newlines, hashes), colons);
    let mask = neon_movemask(matches);

    if mask != 0 {
        return Some(offset + mask.trailing_zeros() as usize);
    }
    offset += 16;
}

Benchmark results (Apple M1 Max):

Size Before After Improvement
10 KB 28.9 µs 28.3 µs +3.8%
100 KB 264 µs 257 µs +5.2%
1 MB 2.51 ms 2.33 ms +8.3%

YAML Block Scalar SIMD (NEON) - 11-23% Improvement

Pattern: Use NEON to scan for newlines in block scalars, then verify indentation.

// NEON implementation - scan for newlines in 16-byte chunks
let newline_vec = vdupq_n_u8(b'\n');

while offset + 16 <= len {
    let chunk = vld1q_u8(data.as_ptr().add(offset));
    let newlines = vceqq_u8(chunk, newline_vec);
    let mask = neon_movemask(newlines);

    if mask != 0 {
        // Found newline - check indentation of next line
        let nl_pos = offset + mask.trailing_zeros() as usize;
        // ... indentation validation
    }
    offset += 16;
}

Benchmark results (Apple M1 Max - block scalar parsing):

Benchmark Before After Improvement
block_scalars/10x10 8.4 µs 7.5 µs +10.9%
block_scalars/50x50 176 µs 152 µs +13.8%
block_scalars/100x100 699 µs 606 µs +13.3%
block_scalars/10x1000 693 µs 591 µs +14.1%
block_scalars/long_10x100 172 µs 132 µs +23.2%
block_scalars/long_50x100 786 µs 671 µs +14.7%

Why it works: Block scalars contain long runs of content where the only structural character is the newline at line boundaries. SIMD efficiently skips content bytes.

YAML Anchor/Alias SIMD (NEON) - 3-6% Improvement

Pattern: Use NEON to scan for anchor name terminators (space, newline, colon, etc.).

// NEON implementation - find anchor name end
let space_vec = vdupq_n_u8(b' ');
let newline_vec = vdupq_n_u8(b'\n');
let colon_vec = vdupq_n_u8(b':');

while offset + 16 <= len {
    let chunk = vld1q_u8(data.as_ptr().add(offset));

    let spaces = vceqq_u8(chunk, space_vec);
    let newlines = vceqq_u8(chunk, newline_vec);
    let colons = vceqq_u8(chunk, colon_vec);

    let matches = vorrq_u8(vorrq_u8(spaces, newlines), colons);
    let mask = neon_movemask(matches);

    if mask != 0 {
        return offset + mask.trailing_zeros() as usize;
    }
    offset += 16;
}

Benchmark results (Apple M1 Max - anchor-heavy YAML):

Benchmark Before After Improvement
anchors/10 3.76 µs 3.64 µs +3.1%
anchors/100 28.8 µs 27.2 µs +5.8%
anchors/1000 314 µs 299 µs +4.7%
anchors/5000 1.67 ms 1.61 ms +3.8%
anchors/k8s_10 8.25 µs 7.85 µs +4.9%
anchors/k8s_50 32.5 µs 30.6 µs +5.1%
anchors/k8s_100 64.1 µs 60.9 µs +5.0%

Why it works: Anchor names in Kubernetes-style YAML (like &default-config) are typically 15-30 characters, making SIMD worthwhile for scanning to the terminator.

Why it works (unlike previous YAML SIMD attempts):

Factor Failed Attempts This Approach
Target : (2-char pattern) \n, #, : (1-char each)
Context handling Tried SIMD Scalar at found position
Typical scan distance 5-15 bytes (keys) 30-100+ bytes (values)
SIMD setup amortization Below breakeven Well above breakeven

Key insight: SIMD works for finding the next interesting byte in potentially long runs of uninteresting bytes. Context-sensitive checks (e.g., # needs preceding space, : needs following whitespace) are handled efficiently at scalar level after the jump.

This avoids the trap that killed the colon-space detection: trying to validate context in SIMD when the context check is simple and cheap at scalar level.

Failed SIMD Optimizations

AVX-512 JSON Parser (-10% penalty)

Attempted: Process 64 bytes per iteration with AVX-512. Result: 7-17% slower than AVX2. Reason: Memory-bound workload doesn't benefit from wider vectors.

BMI1 Mask Iteration (-26% penalty)

Attempted: Use TZCNT/BLSR to skip non-structural bytes. Result: 9-31% slower. Reason: Optimized <1% of execution time; state machine needs all bytes.

NEON Batched Popcount (-25% penalty)

Attempted: Batch popcount 8 words for cumulative index. Result: 1.33x slower. Reason: Prefix sum is inherently sequential; extraction overhead dominates.

NEON Nibble Lookup for YAML (-12-15% penalty)

Attempted: Use nibble-based lookup tables for YAML string scanning.

The simdjson technique splits each byte into high/low nibbles (4 bits each), looks up both in precomputed 16-entry tables, and ANDs the results to classify characters:

unsafe fn classify_yaml_chars(chunk: uint8x16_t) -> uint8x16_t {
    let lo_table = vld1q_u8(YAML_LO_NIBBLE.as_ptr());
    let hi_table = vld1q_u8(YAML_HI_NIBBLE.as_ptr());

    let lo_nibble = vandq_u8(chunk, vdupq_n_u8(0x0F));
    let hi_nibble = vshrq_n_u8::<4>(chunk);

    let lo_result = vqtbl1q_u8(lo_table, lo_nibble);
    let hi_result = vqtbl1q_u8(hi_table, hi_nibble);

    vandq_u8(lo_result, hi_result)  // Each byte has classification flags
}

Result: 12-15% slower than direct comparison for YAML.

Benchmark data (Apple M1, finding quote at end of string):

Size Nibble Lookup Direct Comparison Delta
16B 2.77 ns 2.43 ns -12%
64B 5.58 ns 4.75 ns -15%
256B 16.83 ns 14.88 ns -12%

Why it failed for YAML:

YAML string scanning only needs to find 2-3 specific characters (", \, ').

Approach Operations per 16-byte chunk
Direct comparison 2 comparisons + 1 OR
Nibble lookup 2 table loads + 2 lookups + 1 AND + 1 test

The table lookup overhead doesn't amortize when searching for few characters.

When nibble lookup DOES work:

It's effective for JSON (used in json/simd/neon.rs) where you classify 6+ character types simultaneously: {, }, [, ], :, ,, ", \, plus value chars. The single classification pass replaces ~13 comparisons with 6 operations.

NEON/SSE2 Colon-Space Detection for YAML (-15-20% end-to-end penalty)

Attempted: Use SIMD to find the : pattern for YAML key-value detection.

// NEON approach - find colons, then check if next byte is space
let colon_vec = vdupq_n_u8(b':');
let chunk = vld1q_u8(data.as_ptr().add(offset));
let colons = vceqq_u8(chunk, colon_vec);
let colon_mask = neon_movemask(colons);

if colon_mask != 0 {
    let bit_pos = colon_mask.trailing_zeros() as usize;
    if data[offset + bit_pos + 1] == b' ' {
        return Some(offset + bit_pos);
    }
}

Isolation benchmark (Apple M1 Max) - looked promising:

Scenario SIMD Scalar Speedup
Short key (11 bytes) 4.13 ns 2.31 ns -44% (slower)
Medium key (46 bytes) 3.35 ns 10.67 ns 3.2x
Long key (92 bytes) 4.97 ns 27.79 ns 5.6x

End-to-end result: 15-20% slower when integrated into parser.

YAML benchmark With SIMD Without SIMD Change
simple_kv/10 1.38 µs 1.33 µs -4% (slower)
simple_kv/100 6.05 µs 5.26 µs -15% (slower)
simple_kv/1000 53.7 µs 44.7 µs -20% (slower)

Why it failed end-to-end:

Factor Isolation Benchmark Real YAML Parsing
Search distance 46-92+ bytes 5-15 bytes (typical keys)
Breakeven point ~16 bytes Keys shorter than breakeven
Additional overhead None Finding line_end, extra call

Key insight: SIMD setup cost (~4 ns) is only amortized when scanning 40+ bytes. Typical YAML keys like name:, host:, timeout: are 5-15 chars, where scalar wins.

Lesson learned: Isolation benchmarks can mislead - a function can be 5x faster in isolation but cause regression when integrated due to real-world data characteristics.

Instruction counts vs wall-clock: the document-splitter string scan (#2878 / #2963)

#2878 routed the CLI's JSON document splitter (string_literal_end, reached from jq_runner.rs's scan_one_json_token / find_matching_close on every JSON input the CLI reads) through find_json_escape, replacing a byte-at-a-time loop. CI's perf guard (cachegrind instruction counts against the PR's merge-base) read the change as -8.2% on ARM64-Linux and +2.2% on x86_64 for users_keys_unsorted, and #2963 was filed to attribute and, if warranted, tune away the x86_64 cost.

Wall-clock told a different story on both architectures, and the sign of the instruction count was wrong on both.

Attribution (x86_64, cachegrind on the guard's own users 2 MB fixture)

The fixture has 111,849 strings, 6.7 content bytes on average, every one shorter than 32 bytes, and no escapes. The whole +2.18% (66,354,221 -> 67,800,879 Ir) is in the scan:

Function (self Ir) pre-#2878 post-#2878 per string
scan_one_json_token (inlined scalar loop) 15,216,621 8,160,432 ~63 -> ~6
string_literal_end (not inlined) -- 5,033,209 45.0
json_escape::avx2 (#[target_feature]) -- 3,467,379 31.0

Two facts fall out of the disassembly:

  1. The scanner never sees a short input. find_json_escape(bytes, i) is handed the rest of the document, so O3's "scalar below 16 bytes" threshold (which compares against the buffer remainder) is always false from inside a string, and the first 32-byte AVX2 chunk resolves every string in one iteration. The cost per string is flat, ~76 Ir, regardless of its length. The issue body's proposal of "a length threshold at the call site" cannot be applied as written -- the length is what the scan is looking for.
  2. The cost is dispatch, not bytes. ~45 of those 76 Ir are string_literal_end's own prologue/epilogue, the avx2_enabled OnceLock read, the call to the non-inlinable #[target_feature(enable = "avx2")] kernel and unpacking its Option; the kernel's 31 include three constant broadcasts and a vzeroupper per call. None of that is the < 0x20 comparison the correctness rule added.

Wall-clock, both machines (interleaved scripts/ab-cli.py, 9 reps, min column)

jq keys_unsorted on 10 MB 7950X pre -> post M4 Pro pre -> post
users (6.7-byte strings) -6.5% +10.7%
wide (6-7-byte keys) -0.4% +1.1%
unicode (~21-byte) -12.5% +4.9%
strings (120-byte) -14.9% -19.7%

Control runs (a binary against a copy of itself) read within -2.4%..+1.2% at 10 MB on both machines. So on the 7950X the +2.2% instruction count is a wall-clock win on every shape -- a 32-byte compare-and-movemask retires faster than a 12-instruction-per-byte branchy loop even at 7 bytes -- and the x86_64 tuning the issue asked for was declined. On the M4 Pro the -8.2% instruction count (measured on ARM64-Linux) is a wall-clock regression on every shape shorter than ~24 bytes. The NEON path is latency-bound: compare, or, the multiply-based movemask (two lane extracts, two 64-bit multiplies, a shift-and-or) and a vector-to-GPR transfer sit on the critical path of every chunk, and the next string cannot start until the index comes back. A scalar loop over 7 bytes with well-predicted branches is simply shorter.

What shipped (aarch64 only; x86_64 measured identical to the instruction)

  • shrn nibble mask for the escape scanner's NEON movemask (neon_nibble_mask in util/simd/escape.rs): one narrowing shift and one transfer replace the multiply emulation. Every consumer of the scanner benefits; on the M4 Pro against main, 7 of 8 rows moved negative (users keys_unsorted -3.3%, unicode -2.3%, jq identity rows -1.3%).

  • An 8-byte word probe in string_literal_end (STRING_SCALAR_PREFIX, aarch64 only, zero elsewhere): the first 8 bytes of every string are checked with one 64-bit load and the haszero/hasless word tricks (word_special_mask), and the SIMD scanner takes over from byte 8. 84% of the users shape's strings never reach the chunk. Measured on the M4 Pro against the shrn build alone (10 MB, jq keys_unsorted, min column): users -5.1%, wide -1.0%, unicode -0.5%, strings -0.0%. Against pre-#2878: users +0.1%, unicode -2.1%, strings -17.9%: the regression is gone and the long-string win is kept.

    Two probe shapes were measured first and rejected:

    10 MB, jq keys_unsorted, vs shrn build byte loop K=8 byte loop K=16 word K=8
    users -9.1% -6.3% -5.1%
    wide +1.2% +0.0% -1.0%
    unicode +0.4% +2.7% -0.5%
    strings -0.1% +1.0% -0.0%
    ARM64-Linux guard, users_keys_unsorted +8.8% Ir -- +6.2% out of line, +1.1% inlined

    The byte loop's K=16 loses on unicode (p50 = 21 bytes: 16 scalar iterations and the chunk), the risk the triage plan named. Its K=8 is the fastest on the M4 Pro but costs ~33 instructions per string on the guard's ARM64-Linux leg (+8.8%, over the 5% gate) -- a byte loop retires ~6 instructions per byte, and the guard cannot see the wall-clock win it buys. The word probe is a flat ~14 instructions for 8 bytes.

    The word probe's first push still read +6.2% on that leg. The disassembly showed why: with the probe added, fat LTO stopped inlining string_literal_end into the splitter's loops, so every string paid a call, a prologue/epilogue and ~16 instructions rebuilding the probe's and the NEON chunk's constants. inline(always) on string_literal_end (the same load-bearing attribute find_json_escape carries from O3) hoists the constants back out of the per-string path. Inlined, the M4 Pro reads users -6.1% against the shrn build and -0.0% against pre-#2878, and the ARM64-Linux guard reads users_keys_unsorted +1.1%. On the 7950X the same inlining reads users_keys_unsorted -2.7% on the guard (prologue and epilogue gone), every other row inside ±0.6% except arrays_first_map_iterate +3.5% -- a shape with no strings, the codegen-layout class #2603/#2655 documented -- and times neutral against its true baseline (min column within ±2% on every row).

    That last measurement was first read as +9% to +19% and the attribute was nearly gated to aarch64 on the strength of it. The "before" binary on the x86 box was a main checkout from the start of the issue, and main had moved: the two mains time +17% apart on users keys_unsorted on the 7950X with instruction counts identical to the guard's 0.0% (filed as #3100). The A/B rule "the baseline must predate your first commit" has a companion: it must also be the base your branch is actually on.

  • On x86_64 the probe compiles out (PREFIX = 0); before the inlining change the guard read every row at ±0.0% against main on the 7950X. A build with the word probe enabled on x86_64 too was measured and not shipped: the guard read users_keys_unsorted +1.2% and the 7950X timed it neutral (every row within ±1.2%, inside the control range) -- the AVX2 path is already the fastest shape there.

What to take from it

  • The perf guard measures instructions, and instructions and time can disagree in sign -- per architecture. A guard row moving negative is not evidence of a win, and a row moving positive is not evidence of a loss; either one is a prompt to time it. The same change was +Ir/-time on x86_64 and -Ir/+time on Apple Silicon.
  • A buffer-relative SIMD threshold never fires on a whole-document scan. If the thing being found is the length, the threshold has to be a prefix probe at the call site, and its K is a per-shape trade (8 bytes here; 16 lost on 21-byte strings).
  • Latency, not instruction count, decides a per-item SIMD path. Count the cycles on the critical path from load to the branch that consumes the index; on NEON the movemask emulation and the vector-to-GPR transfer dominate a 16-byte chunk, and the shrn trick is the cheapest known form of it.
  • Shape the probe for the metric that gates it as well as the one that matters. The byte loop and the word probe resolve the same 8 bytes; one costs ~33 instructions per string on the ARM64-Linux guard and the other ~18, for a 4-point difference in wall-clock on the M4 Pro. ARM64-Linux (CI's runner) has no wall-clock measurement in this repo, so the guard's instruction count is the only ARM-Linux number, and a probe that fails it does not ship however it times elsewhere.

Popcount Strategies: Explicit SIMD vs Auto-Vectorized count_ones()

Measured for issue #45, raised on r/rust: has explicit SIMD popcount actually been benchmarked against LLVM's auto-vectorized count_ones()?

The crate offers three popcount strategies for the popcount_words() hot path (bits/popcount.rs), selected at compile time:

Strategy Feature flag Implementation
default (none) w.count_ones() in a loop — LLVM lowers the ctpop intrinsic
simd --features simd explicit AVX-512 VPOPCNTDQ (x86, runtime-detected) / 256-byte-unrolled NEON (ARM)
portable --features portable-popcount broadword SWAR (popcount_word_portable)

The popcount_strategies benchmark measures all three in one run — the scalar (= default count_ones()) and portable arms are always present; the simd arm is compiled with --features simd.

Methodology. Criterion, 100 samples, median times, random word pattern. Popcount is branchless and fixed-cost per word, so it is data-independent: across all six bit patterns (zeros…random) at 256 KiB the medians agree within noise (simd ≤ 0.6%, scalar ≤ 2%). The axis that matters is working-set size (cache residency), not bit density. Two machines, two build modes each: x86_64 = AMD Ryzen 9 7950X (Zen 4, AVX-512 VPOPCNTDQ), Linux, rustc 1.97, pinned to one core; aarch64 = Apple M4 Pro, macOS, rustc 1.96.

TL;DR

  • On x86_64 it is a build-flag question, not a size question. In a default build count_ones() lowers to the scalar broadword sequence (byte-for-byte as fast as the portable arm), and explicit AVX-512 is 5–9× faster. Rebuild with -C target-cpu=native (or +avx512vpopcntdq) and count_ones() auto-vectorizes to VPOPCNTDQ, reaching parity with the explicit path (within ±15%, usually a hair faster).
  • On aarch64 explicit NEON always wins ~1.55–1.6×, at every size and in every build mode. CNT is baseline on ARM so count_ones() already vectorizes — but LLVM does not reproduce the 256-byte-unrolled loop's deferred horizontal reduction.
  • portable-popcount is never distinguishable from default count_ones() on either platform in any build — LLVM lowers both to the same instructions. It buys nothing performance-wise; it exists only to force a pure-arithmetic lowering.

x86_64 — AMD Ryzen 9 7950X (Zen 4), simd = AVX-512 VPOPCNTDQ

Default build (cargo bench --bench popcount_strategies --features simd). count_ones() compiles to broadword — note count_ones() ≈ portable:

Size count_ones() simd portable SIMD×
64 B 3.50 ns 1.83 ns 3.51 ns 1.9×
512 B 25.6 ns 3.52 ns 25.5 ns 7.3×
4 KiB 203 ns 22.5 ns 203 ns 9.0×
32 KiB 1.61 µs 199 ns 1.61 µs 8.1×
256 KiB 12.9 µs 1.76 µs 12.9 µs 7.3×
1 MiB 51.9 µs 8.74 µs 51.8 µs 5.9×
10 MiB 521 µs 106 µs 520 µs 4.9×

Throughput @ 1 MiB: simd 112.7 GiB/s, count_ones()/portable 18.8 GiB/s.

target-cpu=native build (RUSTFLAGS="-C target-cpu=native" cargo bench …). count_ones() now auto-vectorizes to VPOPCNTDQ and reaches parity:

Size count_ones() simd portable SIMD×
64 B 0.92 ns 1.10 ns 0.92 ns 0.83× (scalar wins)
512 B 3.23 ns 2.84 ns 3.23 ns 1.14×
4 KiB 21.9 ns 23.0 ns 22.0 ns 0.95×
32 KiB 159 ns 181 ns 160 ns 0.88×
256 KiB 1.79 µs 1.72 µs 1.78 µs 1.04×
1 MiB 7.92 µs 8.24 µs 7.90 µs 0.96×
10 MiB 109 µs 103 µs 109 µs 1.06×

Throughput @ 1 MiB: count_ones() 126 GiB/s, simd 122 GiB/s. Criterion's A/B delta between the two builds records count_ones() @ 1 MiB dropping −85% in time (18.8 → 126 GiB/s) — that is the switch from broadword to VPOPCNTDQ.

aarch64 — Apple M4 Pro, simd = 256-byte-unrolled NEON

CNT is baseline on ARM, so the build mode barely matters (native matches the numbers below within ~2%). count_ones() ≈ portable again; the explicit NEON path is uniformly ahead:

Size count_ones() simd portable SIMD×
64 B 1.17 ns 0.95 ns 1.18 ns 1.24×
512 B 7.40 ns 4.59 ns 7.40 ns 1.61×
4 KiB 57.2 ns 36.0 ns 57.2 ns 1.59×
32 KiB 457 ns 289 ns 457 ns 1.58×
256 KiB 3.76 µs 2.43 µs 3.77 µs 1.55×
1 MiB 15.1 µs 9.69 µs 15.2 µs 1.56×
10 MiB 154 µs 98.7 µs 155 µs 1.56×

Throughput @ 1 MiB: simd 99.8 GiB/s, count_ones()/portable 63.7 GiB/s.

Answers to the issue's questions

  1. When does explicit SIMD beat count_ones()?
    • x86_64: only when the build does not enable the POPCNT/AVX-512 target features. A default cargo build/cargo bench (baseline x86-64-v1) leaves count_ones() as scalar broadword, and explicit AVX-512 wins 5–9×. Under -C target-cpu=native the win vanishes (parity).
    • aarch64: always, by ~1.55–1.6×, independent of build flags and array size — the explicit loop's batched reduction is something the auto-vectorizer does not emit.
  2. Is the simd feature worth the maintenance burden?
    • x86_64: as a speed feature, no — a target-cpu=native build gets the same VPOPCNTDQ for free. Its remaining value is narrow but real: a portable binary compiled for a baseline target still reaches VPOPCNTDQ through the runtime is_x86_feature_detected! dispatch, which auto-vectorization cannot provide.
    • aarch64: yes — the ~1.56× is real, unconditional, and not recovered by the compiler.
  3. Where is the crossover (small vs large arrays)?
    • There is no size crossover. The ratio is essentially flat across 64 B → 10 MiB on both platforms (it only sags on x86 at ≤ 512 B where loop/setup overhead dominates). The real "crossover" on x86 is the build flag, not the input size.

Caveat. These numbers isolate the popcount kernel over a contiguous &[u64]. In real rank/select index building, popcount is interleaved with loads, shifts and stores, so these ratios are an upper bound on what the strategy contributes end-to-end — consistent with this project's recurring "micro-benchmarks mislead" finding.

Reproduce

# All three arms in one report (scalar / simd / portable):
cargo bench --bench popcount_strategies --features simd

# Let count_ones() auto-vectorize to VPOPCNTDQ (x86) / native CNT (ARM):
RUSTFLAGS="-C target-cpu=native" cargo bench --bench popcount_strategies --features simd

Usage in Succinctly

SIMD Level Location Purpose Speedup
AVX-512 bits/popcount.rs Parallel popcount 5–9× / ≈1ׇ
AVX2 json/simd/avx2.rs JSON char classification 1.78x
AVX2+BMI2 util/simd/x86.rs DSV quote masking 10x
NEON json/simd/neon.rs ARM JSON parsing 1.11x
NEON dsv/simd/neon.rs ARM DSV parsing 1.8x
NEON trees/bp.rs BP L1/L2 index (VMINV) 2.8x (L1), 1-3% (L2)
SSE4.1 trees/bp.rs BP L1/L2 index (PHMINPOSUW) 1-3% (10M+ nodes)
NEON bits/popcount.rs 256-byte unrolling 1.6ׇ
NEON/AVX2 yaml/simd/ YAML unquoted structural 3-8%
NEON yaml/simd/neon.rs Block scalar scanning 11-23%
NEON yaml/simd/neon.rs Anchor name scanning 3-6%
SVE2-BDEP util/broadword.rs select_in_word 5-17x (micro), 2-5% (e2e)

‡ Popcount speedups are measured, and depend on build flags. AVX-512 VPOPCNTDQ is 5–9× faster than a baseline-build count_ones() but ≈1× once count_ones() auto-vectorizes under -C target-cpu=native; the NEON 1.6× (Apple M4 Pro) holds regardless of build flags. Full data and methodology: Popcount Strategies.

Key Lessons

  1. Wider isn't always faster: AVX-512 loses on memory-bound tasks
  2. Profile the bottleneck: Don't optimize 1% of runtime
  3. Memory bandwidth limits: 32 bytes/cycle is often the ceiling
  4. Runtime dispatch is cheap: One branch vs. many iterations
  5. ARM NEON is different: No movemask; use multiplication trick
  6. SIMD setup cost matters: For short operations (<16 bytes), scalar wins
  7. Isolation benchmarks can mislead: A function can be 5x faster in isolation but cause regression when integrated (colon-space detection won for 46+ byte scans, but real YAML keys are 5-15 bytes)
  8. Know your data characteristics: Benchmark with realistic data sizes, not arbitrary test cases
  9. Specialized instructions win: SVE2 inline assembly for general ops is 50% slower than NEON, but BDEP (SVE2-BITPERM) provides 5-17x speedup for select_in_word
  10. Instruction counts and wall-clock can disagree in sign, per architecture: the document-splitter scan was +2.2% Ir / -6.5% time on a 7950X and -8.2% Ir / +10.7% time on an M4 Pro (#2963). A per-item NEON path is decided by the latency from load to the consuming branch, not by how many instructions it retires

See Also

References