Skip to content

CONCEPT Cited by 1 source

SWAR byte parallelism

Definition

SWAR — SIMD Within A Register — is a technique that exploits the regular byte structure of machine words to perform parallel operations on multiple sub-word elements (typically bytes) packed into a single 64-bit or 32-bit integer, without requiring actual SIMD instructions. It achieves sub-word parallelism using ordinary integer arithmetic and bitwise operations.

Core technique

The key insight is that with careful arithmetic, operations on individual bytes packed into a u64 can be performed in parallel by treating the register as 8 independent byte lanes:

  • Broadcast: (value as u64) * 0x0101_0101_0101_0101 replicates a byte into all 8 lanes
  • High-bit sentinel: 0x8080_8080_8080_8080 provides per-lane overflow detection
  • Parallel comparison: (chunk | HIGH) - broadcast(target) & HIGH sets the high bit of every lane where lane >= target
  • Result extraction: trailing_zeros() / 8 finds the first matching lane

Application: casefold lookup table

GitHub's casefold crate uses SWAR to search within a 64-codepoint "page" of Unicode fold entries. Instead of comparing a codepoint against runs one at a time, it loads 8 end_low bytes into a single u64 and tests all of them in one step:

let ge = (chunk | HIGH).wrapping_sub(bcast) & HIGH;
// first set lane is the first run >= target

This resolves the typical ~4-run page search in a single comparison. Only one outlier page (30 runs) requires more than one 8-wide compare step.

(Source: sources/2026-07-31-github-dont-stop-early-case-folding-source-code-at-memory-speed)

When to use SWAR vs SIMD

  • SWAR: Portable across all architectures; no special instructions needed; useful when processing 4–8 elements in the context of a larger scalar algorithm; no alignment requirements.
  • SIMD: Higher throughput (16–64 bytes per instruction); requires target-specific instructions or auto-vectorization; best for bulk buffer sweeps.

SWAR is complementary to SIMD — casefold uses SIMD (via auto-vectorization) for the ASCII fast path and SWAR for the rare non-ASCII lookup within the scalar tail loop.

Standard library usage

[u8]::is_ascii() in Rust's standard library uses a SWAR-like technique: scanning a machine word at a time by OR-ing two u64 lanes and checking high bits with & 0x8080_8080_8080_8080. This tests 16 bytes per iteration — halfway between scalar (1 byte) and SIMD (16+ bytes with vector registers).

Seen in

Last updated · 607 distilled / 1,851 read