Using SIMD for String Search

This page answers one task: your WebAssembly module searches text — log lines, documents, CSV fields — for substrings, and the byte-by-byte loop dominates the profile. You want a SIMD search that checks 16 positions at once, returns exactly the same matches as the scalar version, and falls back cleanly where SIMD is unavailable.

Prerequisites

  • [ ] A scalar substring search in Rust or C compiled to Wasm, with tests.
  • [ ] A SIMD-enabled build and a baseline build, chosen at startup.
  • [ ] Representative text and needles for benchmarking (not just random bytes).

The first-and-last-byte filter

The fastest generic SIMD substring search compares two bytes of the needle at many positions at once. For a needle of length n, load 16 haystack bytes at position i and 16 bytes at i + n − 1. Compare the first vector with the needle’s first byte splatted across all lanes, and the second with the needle’s last byte. AND the results: lane k is all-ones only if position i + k starts with the right byte and ends with the right byte. Most text rarely matches both, so the filter discards nearly all positions in a few instructions; the few candidates are verified with a full comparison.

Choosing two bytes far apart makes false positives much rarer than with the first byte alone — searching “the” in English text matches ‘t’ very often, but ‘t’ followed two bytes later by ‘e’ far less often.

Searching 16 positions per iteration Splat the needle's first and last bytes into vectors. For each block, load 16 haystack bytes at the current position and at the position plus needle length minus one. Compare each with its splatted byte and combine with AND. Convert the mask to a bitmask; for each set bit verify the full needle at that position. Advance 16 bytes when no candidate matches. splat first + last byte i8x16.splat load two windows at i and i+n-1 compare + AND i8x16.eq, v128.and bitmask i8x16.bitmask verify candidates full compare per bit 
use core::arch::wasm32::*;

#[target_feature(enable = "simd128")]
pub unsafe fn find_simd(hay: &[u8], needle: &[u8]) -> Option<usize> {
    let n = needle.len();
    if n == 0 { return Some(0); }
    if n > hay.len() { return None; }
    let first = u8x16_splat(needle[0]);
    let last = u8x16_splat(needle[n - 1]);
    let end = hay.len() - n + 1;                    // number of candidate start positions
    let mut i = 0;
    while i + 16 <= end {
        let a = v128_load(hay.as_ptr().add(i) as *const v128);
        let b = v128_load(hay.as_ptr().add(i + n - 1) as *const v128);
        let mut mask = u8x16_bitmask(v128_and(u8x16_eq(a, first), u8x16_eq(b, last))) as u32;
        while mask != 0 {
            let k = mask.trailing_zeros() as usize;
            if &hay[i + k + 1..i + k + n] == &needle[1..] { return Some(i + k); }
            mask &= mask - 1;                           // clear lowest set bit
        }
        i += 16;
    }
    hay[i..].windows(n).position(|w| w == needle).map(|p| i + p)   // scalar tail
}

u8x16_bitmask packs the top bit of each lane into a 16-bit integer, so trailing_zeros gives the first candidate lane and clearing the lowest set bit visits the rest in order. Because positions are visited in increasing order, the first verified match is the leftmost one — identical to the scalar result.

Step 2 — keep loads in bounds

The second window starts at i + n − 1 and reads 16 bytes, ending at i + n + 14. The loop condition i + 16 <= end (where end = len − n + 1) guarantees i + n + 14 <= len − 1, so both loads stay inside the haystack. Positions that do not fill a whole block go to the scalar tail. Getting this wrong reads past the slice — in Wasm that reads whatever follows in linear memory (or traps at the memory end), which produces wrong matches rather than crashes in most cases.

Step 3 — special-case short needles

For a one-byte needle, the first and last bytes are the same; a single comparison per block suffices, and this is just memchr. For two-byte needles, the filter is already exact — no verification needed. Dispatch on needle length: 1 → memchr-style loop, 2–16 → the filter above, long needles → the same filter (verification costs more but candidates are rare), or a different algorithm for pathological inputs where both bytes are very common.

Choosing a search strategy by needle length One-byte needles use a single comparison per block like memchr. Two-byte needles use the first-and-last filter with no verification. Medium and long needles use the filter with verification. Highly repetitive inputs where both filter bytes are common benefit from choosing rarer bytes or a two-way algorithm. needle strategy verification notes 1 byte memchr: one eq per block none fastest 2 bytes first + last filter none (exact) very fast 3–64 bytes first + last filter per candidate typical case repetitive text rare-byte filter per candidate pick rarest bytes

Step 4 — test against the scalar version

Property-test the SIMD function against windows(n).position(..) on random haystacks and needles, including needles at the very start and end, haystacks shorter than 16 bytes, overlapping matches (“aaa” in “aaaa”), and needles longer than the haystack. Run the tests in a Wasm runtime with SIMD enabled (Node.js or wasmtime) so they exercise the real instructions.

Step 5 — consider existing crates first

In Rust, the memchr crate’s memmem module implements this technique (plus rare-byte selection and a two-way fallback) with a Wasm simd128 backend when the target feature is enabled at compile time. If it fits, use it — it is heavily tested. Write your own when you need something it does not offer, such as case-insensitive matching (compare after OR-ing ASCII letters with 0x20), searching for any of several bytes, or fusing the search with other per-byte work.

Searching UTF-8 bytes for a UTF-8 needle is correct as is: valid UTF-8 cannot produce a match starting in the middle of a character, because continuation bytes never equal a leading byte. Case-insensitive ASCII search folds both vectors with v128_or(v, u8x16_splat(0x20)) before comparing — correct for letters, but it also merges some punctuation pairs (such as the at sign and the backtick), so verify candidates with a proper case-insensitive comparison. Full Unicode case folding is not a byte operation and needs a different approach.

Exposing the search to JavaScript

The usual interface is a pair of exported functions: one that returns a pointer to a reusable input buffer of a given size, and one that searches it. JavaScript encodes the text once with TextEncoder.encodeInto directly into Wasm memory, writes the needle after it, and calls the search with offsets and lengths:

const enc = new TextEncoder();
const hayPtr = exports.buffer(text.length * 3 + needle.length * 3);   // worst-case UTF-8 size
const mem = new Uint8Array(exports.memory.buffer);
const { written: hayLen } = enc.encodeInto(text, mem.subarray(hayPtr));
const { written: nLen } = enc.encodeInto(needle, mem.subarray(hayPtr + hayLen));
const pos = exports.find(hayPtr, hayLen, hayPtr + hayLen, nLen);       // byte offset or -1

The result is a byte offset in UTF-8, not a JavaScript string index. If callers need a string index, convert by decoding the prefix or by counting UTF-16 code units while scanning; for ASCII-only text the two are equal. Searching a large text many times should keep the encoded haystack in memory between calls, because encoding usually costs more than the SIMD search itself.

Counting and iterating all matches

Returning every match instead of the first changes only the inner loop: instead of returning on the first verified candidate, append its position to an output buffer and continue clearing bits. Decide whether matches may overlap — “aa” in “aaaa” is at 0, 1, 2 when overlapping, at 0 and 2 when not — and, for non-overlapping search, skip candidates that start before the end of the previous match. Write the semantics into the tests, because both behaviours are reasonable and scalar reference implementations differ between libraries.

Reading the generated code

To confirm the compiler emitted what you intended, disassemble the SIMD build and look for the core sequence inside the loop: two v128.load, two i8x16.eq, a v128.and and an i8x16.bitmask. Unexpected scalar loads or calls inside the loop usually mean a bounds check was not hoisted; using raw pointers for the loads, as above, avoids per-iteration slice checks.

Expected output

The SIMD search returns the same leftmost positions as the scalar search on all tests, including tails and overlapping matches; it processes 16 positions per iteration; one- and two-byte needles take faster paths; and the baseline build is used on engines without SIMD.

Gotchas

  • Loads past the haystack. Derive loop bounds from both windows. Use a scalar tail.
  • Returning a non-leftmost match. Visit mask bits in increasing order.
  • Common filter bytes. Repetitive input defeats the filter. Choose rarer bytes.
  • Case folding with OR 0x20 on non-letters. False candidates. Verify properly.
  • Reinventing a tested crate. Use memchr::memmem when it fits.
  • Re-encoding the haystack for every search. Encoding costs more than searching. Keep it in memory.

Performance note

Searching a 10 MB log for a 9-byte needle in Chrome, the SIMD filter ran about 7× faster than a naive scalar loop, and close to the memchr crate’s simd128 build.

Searching 10 MB of log text for a 9-byte needle Milliseconds to find all occurrences of a nine-byte needle in ten megabytes of log text with a naive scalar Wasm loop, a hand-written SIMD first-and-last filter, and the memchr crate's memmem with simd128. ms for 10 MB naive scalar 21 ms SIMD first + last filter 3 ms memchr::memmem simd128 2.7 ms

Frequently Asked Questions

Why not compare all needle bytes in SIMD? Comparing two bytes filters almost every position cheaply; full comparisons run only on rare candidates.

Is u8x16_bitmask fast on all engines? It maps to a single instruction on x64 and a short sequence on Arm, fast enough for this loop.

Does this work for JavaScript strings? Only after encoding them to UTF-8 bytes in Wasm memory; JavaScript strings are UTF-16.

Can I search for several needles at once? For a few, run the filter per needle; for many, use a multi-pattern algorithm such as Teddy or Aho-Corasick.

Is the returned position a string index? No — it is a UTF-8 byte offset; convert it if JavaScript needs a UTF-16 index.

How do I return all matches? Keep clearing mask bits after each verified candidate and write positions to an output buffer.

← Back to Wasm SIMD & Vectorized Computation