Skip to content

PATTERN Cited by 1 source

Branchless sweep then check

Intent

Process an entire buffer with a branchless loop body, accumulating metadata about exceptional conditions (e.g., non-ASCII bytes) into a register, then check the accumulator once after the loop to decide whether a second (expensive) pass is needed.

Mechanism

Instead of: 

for each byte:
    if exceptional: break  // ← prevents vectorization
    process(byte)
// handle remaining from break point

Use: 

accumulator = 0
for each byte:
    accumulator |= byte   // ← same info, no branch
    process(byte)          // ← branchless transform
if accumulator & sentinel:
    // run second pass only on the exceptional tail

The key insight is that the early-exit branch carries the same information as the post-loop accumulator test, but the branch form prevents the compiler from vectorizing the loop. The accumulator form allows the compiler to emit SIMD instructions that process 16+ bytes per iteration.

Trade-off

This pattern does "wasted work" — it processes bytes past the first exceptional one. But because the SIMD-vectorized loop runs at memory bandwidth (>45 GiB/s), the total cost of sweeping the entire buffer is less than the cost of the scalar branch-per-byte loop that stops early.

Canonical instance

GitHub's casefold crate: high_bit_acc |= *b accumulates non-ASCII detection across the whole buffer, while simultaneously lowercasing ASCII bytes in place. After the loop, high_bit_acc & 0x80 == 0 means pure ASCII (already folded, return immediately); otherwise, memchr to the first non-ASCII byte and run the Unicode tail path.

Result: 3.1 GiB/s (early-exit) → >45 GiB/s (branchless sweep + post-check). 15× improvement.

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

Applicability

Best when: - The common case is "no exceptional condition" (e.g., ASCII-dominated text) - The per-element processing is cheap (constant-time arithmetic) - The buffer fits in cache or the operation is already memory-bound - The "wasted work" on exceptional elements is harmless (e.g., lowercasing non-ASCII bytes is incorrect but gets overwritten by the second pass)

Seen in

Last updated · 607 distilled / 1,851 read