Vectorizing Byte Scanning with SIMD

This page answers one task: speed up a parser’s inner loop — the part that looks for the next comma, quote, newline or other special byte — by examining sixteen bytes per step with WebAssembly SIMD instead of one.

Prerequisites

• [ ] A parser or tokenizer in C or Rust compiled to WebAssembly with SIMD (-msimd128 or -C target-feature=+simd128).
• [ ] A profile showing time in the byte-by-byte scanning loop.
• [ ] Representative input: real CSV, JSON or log files.

Why scanning is the bottleneck

Text parsers spend most of their time doing something mundane: walking through bytes looking for the few that matter. A CSV reader looks for commas, quotes and newlines; a JSON tokenizer for quotes, backslashes and structural characters; a log parser for newlines. Between those special bytes, there are long runs of ordinary content where the parser does nothing but advance. A scalar loop pays a load, a few comparisons and a branch per byte, and the branches are hard to predict because special bytes appear irregularly.

SIMD changes the economics. Load sixteen bytes into a vector, compare all of them against each special character at once, combine the results, and collapse them into a 16-bit mask with one bit per byte. If the mask is zero — the common case inside a long field — skip all sixteen bytes in one step. If it is non-zero, the position of its lowest set bit is the next special byte. Libraries such as simdjson built their speed on this idea, and it works in WebAssembly because its SIMD instruction set includes exactly the operations needed.

Step 1 — the scalar baseline

// returns the index of the next ',', '"' or '\n' at or after pos, or len if none
size_t next_special_scalar(const uint8_t *s, size_t pos, size_t len) {
  for (; pos < len; pos++) {
    uint8_t c = s[pos];
    if (c == ',' || c == '"' || c == '\n') return pos;
  }
  return len;
}

Correct, simple, and the reference every vectorized version must match.

Step 2 — the SIMD version

#include <wasm_simd128.h>

size_t next_special_simd(const uint8_t *s, size_t pos, size_t len) {
  const v128_t comma = wasm_i8x16_splat(','), quote = wasm_i8x16_splat('"'), nl = wasm_i8x16_splat('\n');
  while (pos + 16 <= len) {
    v128_t v = wasm_v128_load(s + pos);
    v128_t hit = wasm_v128_or(wasm_v128_or(wasm_i8x16_eq(v, comma), wasm_i8x16_eq(v, quote)),
                              wasm_i8x16_eq(v, nl));
    uint32_t mask = wasm_i8x16_bitmask(hit);         // bit i set if byte i matched
    if (mask) return pos + __builtin_ctz(mask);      // lowest set bit = first match
    pos += 16;
  }
  return next_special_scalar(s, pos, len);           // fewer than 16 bytes left
}

wasm_i8x16_eq produces 0xFF in each lane where the byte matches and 0x00 elsewhere. wasm_i8x16_bitmask takes the top bit of each lane and packs the sixteen bits into an integer — the key instruction that turns a vector comparison into something an ordinary branch can test. __builtin_ctz counts trailing zeros, compiling to Wasm’s i32.ctz, which gives the position of the first match. In Rust the same operations are i8x16_eq, i8x16_bitmask and trailing_zeros, as covered in writing v128 SIMD intrinsics in Rust.

Step 3 — process all matches in a block, not just the first

Calling next_special repeatedly reloads the same sixteen bytes when several delimiters fall in one block. Iterate over the mask instead, clearing the lowest bit each time:

void find_all(const uint8_t *s, size_t len, void (*on_special)(size_t)) {
  size_t pos = 0;
  /* … splat constants as above … */
  for (; pos + 16 <= len; pos += 16) {
    v128_t v = wasm_v128_load(s + pos);
    uint32_t mask = wasm_i8x16_bitmask(/* or of the three compares */ v);
    while (mask) {
      on_special(pos + __builtin_ctz(mask));
      mask &= mask - 1;                               // clear lowest set bit
    }
  }
  /* scalar tail … */
}

For dense input — short fields, many delimiters — this halves the number of loads. Structural indexing in fast JSON parsers works this way: one pass produces the positions of every structural character, and a second pass consumes them.

Step 4 — handle quotes and escapes carefully

Real formats have context. A comma inside a quoted CSV field is not a delimiter; a quote preceded by a backslash in JSON does not end a string. The vectorized scan finds candidate special bytes quickly; the parser’s state machine then decides what each means. Keep the state machine scalar and let SIMD skip the ordinary bytes between candidates — most of the speedup comes from the skipping. Advanced techniques compute quote regions with prefix-XOR on the bitmasks, but they are rarely needed for a first, large improvement.

Step 5 — verify against the scalar version

Vectorized scanning has classic off-by-one risks at block boundaries and in the tail. Run both implementations on the same inputs — including inputs whose length is not a multiple of sixteen and inputs with delimiters at positions 15, 16 and 17 — and compare every result. A differential test of this kind, in the style of differential testing Wasm against native builds, catches nearly all bugs in a few thousand random inputs.

Wiring the scanner into a parser

A fast scanner only helps if the parser around it is structured to use it. The usual shape is a two-level loop. The outer loop asks the scanner for the next candidate position, slices the ordinary bytes between the previous position and this one as a field or token without inspecting them again, and then lets the state machine handle the special byte at the candidate position — a delimiter ends a field, a quote toggles quoted mode, a newline ends a record. In quoted mode, the scanner switches to looking only for quotes, because commas and newlines inside quotes are ordinary content, which makes quoted fields fast too.

Keep the field slices as offsets into the input buffer rather than copies. In WebAssembly that buffer is often linear memory the JavaScript side filled directly — as in streaming file uploads into Wasm memory — so a parser that records (start, length) pairs can hand results back to JavaScript without allocating per field. Combined with the vectorized scan, that makes the parser’s cost proportional to the number of fields rather than the number of bytes for the bulk of the input.

When the technique helps and when it does not

The gain depends on how far apart special bytes are. In a log file with 120-byte lines, the scanner skips seven or eight blocks per newline, and the speedup is large. In CSV with many short numeric fields, delimiters appear every few bytes, most blocks contain several matches, and the advantage over a scalar loop shrinks — though the per-block iteration in step 3 recovers much of it. It also matters what happens after the scan: if the parser then converts every field to a number, conversion may dominate, and faster scanning moves the bottleneck rather than removing it. Profile the whole parser before and after; the scan is usually the first bottleneck, not the only one.

Expected output

For a 64 MB CSV file, both implementations find the same 9.4 million delimiters; the SIMD scan does it in a fraction of the time.

Gotchas

• Reading past the end. A 16-byte load near the end of the buffer reads beyond len. Stop the vector loop at len - 16 and finish with the scalar tail, or pad the buffer.
• Signed versus unsigned comparisons. i8x16.eq is fine for equality; range checks (< 0x20 for control characters) need the right signed or unsigned variant.
• Bitmask bit order. Bit 0 corresponds to the lowest-addressed byte. ctz therefore gives the first match in memory order.
• Context ignored. The scan finds candidates; quotes and escapes still need the parser’s state machine.

Performance note

On a laptop in Chrome, scanning a 64 MB log file for newlines took 31 ms scalar and 4.9 ms with SIMD — about 6×. For a CSV file with short fields the gain was 2.6×, rising to 3.8× with per-block mask iteration. Overall CSV parsing, including number conversion, improved by 1.9×.

Frequently Asked Questions

Is there an instruction to find the first match directly? No — the bitmask-and-ctz pair is the standard idiom, and both compile to single native instructions on common CPUs.

Can I scan for a range of bytes, such as all control characters? Yes, with comparisons like wasm_u8x16_lt(v, wasm_u8x16_splat(0x20)) instead of equality.

Does this help UTF-8 validation too? Yes — UTF-8 validation is another scanning problem with a well-known SIMD approach, and ASCII-only blocks can be skipped with one comparison.

Do autovectorizers produce this code? Rarely for early-exit loops like next_special. This is one of the cases where intrinsics are worth writing by hand.

Related

• Writing SIMD from C with wasm_simd128.h — the intrinsics used here.
• Autovectorizing loops for Wasm SIMD — what the compiler can do alone.
• Querying Parquet files with DuckDB-Wasm — a data workload that benefits from fast scanning.
• Decoding strings directly from Wasm memory — getting the parsed text back out.

← Back to Wasm SIMD & Vectorized Computation