Don't stop early: Case-folding source code at memory speed
4 days ago
- 大小写折叠是一种上下文无关、与区域设置无关的比较操作，与用于显示且上下文相关的小写化不同。
- ASCII 快速路径通过使用无分支、可向量化的循环实现了超过 45 GiB/s 的速度，该循环扫描整个缓冲区而不提前退出，尽管这看起来有悖常理。
- 移除门控向量化的提前退出 break，并使大写测试和写入无分支，是实现内存速度性能的关键优化。
- 在标量代码中，无分支体是一种性能退化，因为它增加了无条件写入，但当它能够启用向量化时，它变得至关重要。
- 分块的提前退出方法（例如，使用掩码扫描单词）比简单的单字节 break 更快，但仍然比单遍无分支扫描慢。
- 将检测和转换合并到具有提前退出的单个循环中比两个独立的无分支遍历慢，因为数据相关的分支会阻碍循环展开和流水线化。
- 该实现尽可能重用输入缓冲区，并且仅为潜在的长度变化分配一个最坏情况大小的缓冲区，从而避免不必要的堆分配。
- 非 ASCII 路径使用紧凑的 1776 字节表（分页位图、压缩游程和字节空间增量）来避免解码 UTF-8 字符，通过单个位测试即可拒绝不折叠的情况。
- 折叠通过纯字节运算执行：将每个游程的小端增量添加到源字节，即使长度变化的折叠也无需显式解码/编码。
- casefold crate 是开源的，性能基准测试显示其在大多数工作负载（尤其是 ASCII）上优于 simd_normalizer 和 HashMap 等替代方案。
- 该设计依赖于自动向量化、SWAR 和小端假设，性能因架构而异。
- 关键要点：无分支的全缓冲区扫描优于提前退出，字节空间运算优于码点解码，两者结合在常见情况下实现了内存带宽。