Don't stop early: Case-folding source code at memory speed
4 days ago
- Case folding is a context-free, locale-independent comparison operation, distinct from lowercasing which is for display and context-sensitive.
- The ASCII fast path achieves >45 GiB/s by using a branchless, vectorizable loop that sweeps the entire buffer without early exit, despite this being counterintuitive.
- Removing the early-exit break (which gates vectorization) and making the upper-case test and write branchless are the key optimizations that enable memory-speed performance.
- A branchless body is a pessimization in scalar code, as it adds unconditional writes, but becomes essential when it enables vectorization.
- A chunked early-exit approach (e.g., scanning words with masks) is faster than a naive single-byte break, but still slower than the single-pass branchless sweep.
- Fusing detection and conversion into a single loop with early exit is slower than two separate branch-free passes, because the data-dependent branch prevents unrolling and pipelining.
- The implementation avoids unnecessary heap allocations by reusing the input buffer when possible and only allocating a single worst-case-size buffer for potential length changes.
- The non-ASCII path uses a compact 1776-byte table (paged bitmap, packed runs, and byte-space deltas) to avoid decoding UTF-8 characters, rejecting non-folding cases with a single bit test.
- Folding is performed by pure byte arithmetic: adding a per-run little-endian delta to the source bytes, which handles even length-changing folds without explicit decode/encode.
- The casefold crate is open-sourced, with performance benchmarks showing superiority over alternatives like simd_normalizer and HashMap on most workloads, especially ASCII.
- The design relies on auto-vectorization, SWAR, and little-endian assumptions, with performance varying across architectures.
- Key takeaways: branch-free full sweeps beat early exits, byte-space arithmetic beats code-point decoding, and the combination achieves memory bandwidth for common cases.