SIMD substring search

Deep dive

How it works

In: haystack bytes and a needle of 1 or k bytes · Out: position of the first match, or none · State: none (needle splats and dispatch pointer only) · Cost: O(n) typical, n/16 vector steps (SSE2); O(n·k) worst case without a Two-Way fallback

memchr (one byte b):

1. v = splat(b). For each 16-byte block: m = movemask(cmpeq(load(h+i), v)). If m ≠ 0, return i + tz(m).
2. Tail of < 16 bytes: scalar loop (or an overlapping final unaligned load).

memmem (needle n of length k ≥ 2), "generic SIMD" filter:

1. F = splat(n[0]), L = splat(n[k−1]).
2. For each block of 16 candidate starts i..i+15: m = movemask(cmpeq(load(h+i), F) & cmpeq(load(h+i+k−1), L)).
3. For each set bit j of m (lowest first): if h[i+j+1 .. i+j+k−1] == n[1..k−1], return i+j. Clear the bit (m &= m−1).
4. Advance i by 16; finish the tail with a scalar search.

needle "parse"        F = 'p' x16, L = 'e' x16
h+i    : t o _ p a r s e _ p a r k e d _
h+i+4  : a r s e _ p a r k e d _ t h e m
eq F   : 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0
eq L   : 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0
AND    : 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0   -> verify only j = 3

SWAR memchr: x = word ^ (b × 0x0101…01) makes matching bytes 0; (x − 0x0101…01) & !x & 0x8080…80 sets bit 7 exactly in the first zero byte (later bytes may be false positives, which do not matter for "first").

Code

/// Portable SWAR memchr: 8 bytes per step, no intrinsics.
pub fn memchr_swar(h: &[u8], b: u8) -> Option<usize> {
    const LO: u64 = 0x0101_0101_0101_0101;
    const HI: u64 = 0x8080_8080_8080_8080;
    let pat = LO * b as u64;
    let mut i = 0;
    while i + 8 <= h.len() {
        let x = u64::from_le_bytes(h[i..i + 8].try_into().unwrap()) ^ pat; // matching bytes become 0
        let z = x.wrapping_sub(LO) & !x & HI; // lowest set bit = first zero byte (exact)
        if z != 0 { return Some(i + (z.trailing_zeros() / 8) as usize); }
        i += 8;
    }
    h[i..].iter().position(|&c| c == b).map(|p| p + i)
}

pub fn find_scalar(h: &[u8], n: &[u8]) -> Option<usize> {
    if n.is_empty() { return Some(0); }
    h.windows(n.len()).position(|w| w == n)
}

/// Substring search: SSE2 first/last-byte filter, scalar fallback elsewhere.
pub fn find(h: &[u8], n: &[u8]) -> Option<usize> {
    #[cfg(target_arch = "x86_64")]
    if n.len() >= 2 && h.len() >= n.len() {
        return unsafe { find_sse2(h, n) }; // SSE2 is baseline on x86_64
    }
    find_scalar(h, n)
}

#[cfg(target_arch = "x86_64")]
#[target_feature(enable = "sse2")]
unsafe fn find_sse2(h: &[u8], n: &[u8]) -> Option<usize> {
    use std::arch::x86_64::*;
    let k = n.len();
    let first = _mm_set1_epi8(n[0] as i8);
    let last = _mm_set1_epi8(n[k - 1] as i8);
    let mut i = 0;
    while i + k - 1 + 16 <= h.len() { // both 16-byte loads stay in bounds
        let bf = _mm_loadu_si128(h.as_ptr().add(i) as *const __m128i);
        let bl = _mm_loadu_si128(h.as_ptr().add(i + k - 1) as *const __m128i);
        let eq = _mm_and_si128(_mm_cmpeq_epi8(first, bf), _mm_cmpeq_epi8(last, bl));
        let mut mask = _mm_movemask_epi8(eq) as u32; // bit j: candidate start at i + j
        while mask != 0 {
            let j = i + mask.trailing_zeros() as usize;
            if h.get_unchecked(j + 1..j + k - 1) == n.get_unchecked(1..k - 1) { return Some(j); }
            mask &= mask - 1; // clear lowest set bit
        }
        i += 16;
    }
    find_scalar(&h[i..], n).map(|p| p + i) // fewer than 16 candidate starts left
}

/// SSE2 memchr for comparison with the SWAR version.
#[cfg(target_arch = "x86_64")]
#[target_feature(enable = "sse2")]
pub unsafe fn memchr_sse2(h: &[u8], b: u8) -> Option<usize> {
    use std::arch::x86_64::*;
    let v = _mm_set1_epi8(b as i8);
    let mut i = 0;
    while i + 16 <= h.len() {
        let x = _mm_loadu_si128(h.as_ptr().add(i) as *const __m128i);
        let m = _mm_movemask_epi8(_mm_cmpeq_epi8(x, v));
        if m != 0 { return Some(i + m.trailing_zeros() as usize); }
        i += 16;
    }
    h[i..].iter().position(|&c| c == b).map(|p| p + i)
}

Complexity and constants

• memchr: 1 load + 1 compare + 1 movemask + 1 test per 16 bytes (SSE2); with AVX2 and 4× unrolling (OR four compare results, test once), order of 1 cycle per 32-64 bytes, i.e., memory bandwidth bound beyond L2.
• memmem filter: 2 loads, 2 compares, AND, movemask per 16 positions, about 2× the work of memchr. False-positive rate per position ≈ p(first) × p(last); for English text and letters with frequency ~5-10 %, under 1 % of positions need verification.
• SWAR: about 5 ALU ops per 8 bytes. Measured on a 64 MB haystack, one Apple M-series core: 27 GB/s, vs 4 GB/s for iter().position.
• Worst case: a needle like aaa…aba over a long run of a passes the filter at every position and verifies about k bytes each: O(n·k).

Efficiency

• Cost: memchr needs 1 load, 1 compare, 1 movemask and 1 test per 16 bytes (SSE2); with AVX2 and 4× unrolling order of 1 cycle per 32-64 bytes, memory-bandwidth bound beyond L2. The memmem filter costs about 2× that. SWAR (8 bytes per u64) measured 27 GB/s versus 4 GB/s for iter().position on a 64 MB haystack, one Apple M-series core. Memory: none beyond the haystack. Bound: memory bandwidth, then the false-positive rate of the filter.
• Levers:
  • SIMD compare of first and last (or two rarest) needle bytes — order of 5-15 GB/s for substring search on text — needles of 2+ bytes
  • rare-byte choice from a byte-frequency table (memchr crate) — far fewer verifications than first/last on text — natural-language and source text
  • unroll 2-4 vectors and OR the masks, branch once — fewer branches per byte — large haystacks
  • runtime CPU dispatch cached in a function pointer — no per-call feature check — short searches
  • Two-Way fallback when verifications pile up — linear worst case, closes the adversarial DoS hole — user-supplied patterns
• Naive → standard → state of the art:
  • byte loop with branches · about 4 GB/s (measured, iter().position)
  • SWAR, no intrinsics · about 27 GB/s (measured above)
  • AVX2/AVX-512 filter with rare bytes and Two-Way fallback · order of 5-15 GB/s substring, tens of GB/s for memchr

Implementation notes

• Choose rare bytes, not first/last: the memchr crate picks the two rarest needle bytes using a static byte-frequency table (rarebytes), which cuts candidates sharply on text (spaces and 'e' are bad filter bytes).
• Unroll and combine: process 2-4 vectors per iteration and OR the masks before branching; branch only when something matched.
• Tail handling: an overlapping unaligned load of the last 16 bytes (masking already-scanned positions) avoids a scalar tail and its mispredictions.
• Runtime dispatch: check AVX2 once (is_x86_feature_detected!("avx2")) and store a function pointer; checking per call costs more than short searches take.
• ARM NEON has no movemask; use vshrn_n_u16 to narrow the compare result to a 64-bit mask with 4 bits per byte, then trailing_zeros() / 4.
• Prefilter + fallback: count verifications; if the filter's hit rate is poor, switch to Two-Way for linear worst case.
• Case-insensitive ASCII: OR haystack bytes with 0x20 before comparing (only valid for letters; check the needle bytes are letters).

Pitfalls

• Reading past the end of the slice with unaligned vector loads: only safe within the allocation; with Rust slices, bound the loop as above or use a final overlapping load.
• Empty needle and needle longer than haystack: define and test both (empty matches at 0).
• _mm256_movemask_epi8 returns i32, negative when byte 31 matches; cast to u32 before shifts or > 0 tests.
• No fallback for adversarial input: a filter-only memmem is a DoS vector on user-supplied patterns.
• Benchmarking on short haystacks: setup (splat, dispatch) dominates under ~64 bytes; small searches may be faster scalar.

Variants and alternatives

In production

Developer tools: ripgrep (via the Rust memchr crate; the same crate serves regex and many parsers). Operating systems: glibc memchr/strlen/strchr (SSE2/AVX2/EVEX variants chosen at load time). Network security: Hyperscan / Vectorscan (Teddy, FDR), which Suricata can use for multi-pattern matching. Data parsing: simdjson (SIMD structural character search). Libraries: StringZilla.

Implementations

Sources

• W. Muła, SIMD-friendly algorithms for substring searching, 0x80.pl, 2016 (updated 2018). post
• M. Crochemore, D. Perrin, Two-way string-matching, Journal of the ACM, 1991. paper
• X. Wang, Y. Hong, H. Chang, K. Park, G. Langdale, J. Hu, H. Zhu, Hyperscan: A Fast Multi-pattern Regex Matcher for Modern CPUs, NSDI, 2019. paper · code
• R. N. Horspool, Practical Fast Searching in Strings, Software: Practice and Experience, 1980.
• A. Gallant, memchr crate source and documentation (github.com/BurntSushi/memchr). code · docs
• Suricata documentation, Hyperscan (performance). docs