假设用户搜索 café，而语料库包含 CAFÉ，或者他们输入 straße，而你存储的是 STRASSE。要使这些计为匹配，你需要一个擦除大小写区别的规范形式，这样仅在大小写上不同的两个字符串比较相等。这种形式就是大小写折叠，它出现在任何匹配文本而非显示文本的地方：搜索引擎、正则表达式 (?i) 标志、不区分大小写的用户名和主机名。
这是一个基本操作，但在 GitHub 我们大量运行它。GitHub 的代码搜索引擎 Blackbird 索引了超过 1.8 亿个仓库——超过 480TB 的源代码。每个字节在提取 ngram 并构建索引之前都会进行大小写折叠，对于每个潜在的查询结果，都需要另一个（隐式或显式）大小写折叠操作来定位匹配。在这种规模下，即使是基本操作的速度也开始变得重要。
这篇文章讲述了我们如何让它变得快速，它从一个反直觉的地方开始：ASCII 快速路径中最大的收益来自于移除一个优化，而不是添加一个。事实证明，分支自由地扫描整个缓冲区比在第一个非 ASCII 字节处提前停止更快。我们将结果开源为一个名为 casefold 的 Rust crate。
折叠不是小写化
人们很容易使用 str::to_lowercase，但小写化和折叠是不同的操作，有不同的目标：
小写化用于显示，它是区域和上下文敏感的：希腊语词尾 sigma 在单词末尾小写为 ς，在其他地方小写为 σ，土耳其语 I 的小写方式与英语 I 不同。大小写折叠用于比较，它是故意无上下文和独立于区域的。重点是保持稳定和对称的关系，这样如果 A 折叠匹配 B，那么 B 折叠匹配 A 在任何区域。Unicode 字符数据库正是为此提供了明确的 CaseFolding.txt。
这两个操作在真实字符上存在分歧——ß、İ、词尾 sigma——这就是为什么小写化作为替代方案会悄无声息地产生错误的匹配。此 crate 仅实现简单的（1 对 1）折叠——CaseFolding.txt 中的 C 和 S 状态——而不实现多字符“完整”折叠（ß → ss）或突厥语区域折叠（带点的 İ）。这不是一个不寻常的选择：像 ripgrep 这样的常用工具和正则引擎做出了同样的限制，在工具之间保持一致很重要。
反直觉的核心：不要提前停止
我们主要处理源代码，因此我们折叠的文本绝大多数是 ASCII，让它以内存速度运行是我们能做的最重要的事情。其他一切只需要防止罕见的非 ASCII 路径破坏它。
ASCII 字母的折叠很简单——A..=Z 映射到 a..=z，其他一切保持不变——所以 ASCII 过程实际上只是“扫描缓冲区，原地小写”。向任何 LLM 询问这个，你可能会得到类似这样的东西：
let bytes = s.as_bytes_mut();
for (i, b) in bytes.iter_mut().enumerate() {
if *b >= 0x80 {
break; // 非 ASCII 在索引 i 处：将剩余部分交给 Unicode 路径
}
if b.is_ascii_uppercase() {
*b += 32; // 'A'..='Z' → 'a'..='z'
}
}这看起来很理想：做便宜的字节工作，一旦遇到非 ASCII 字节就立即中断，让“真正的” Unicode 路径接管：“只做便宜的工作，直到你必须这样做。”在 Apple M4 上，这运行在约 3 GiB/s。孤立地听起来不错，但由于 if 分支，它比“最优”慢了 15 倍以上。
让我们逐行删除每个分支：
if b >= 0x80 { break }→ 根本不停。用累加器OR每个字节，并在循环后 一次 测试它：high_bit_acc |= *b。相同的信息（是否有任何非 ASCII 字节？），主体中零分支。A..=Z范围测试 → 将其变为算术。b.wrapping_sub(b'A') < 26恰好对A..=Z为真（任何其他字节都回绕到 ≥ 26），产生 0/1 掩码而无需分支。- 条件写入 → 将掩码折叠到存储中。
| (is_upper << 5)设置位 5——将大写字母转为小写，对其他一切都是无操作——字节总是被写入，从不分支。
剩下的主体中没有分支，也没有提前退出：
let mut high_bit_acc: u8 = 0;
for b in &mut bytes {
high_bit_acc |= *b; // 检测任何非 ASCII 字节
let is_upper = b.wrapping_sub(b'A') < 26; // 无分支 A..=Z 测试
*b |= u8::from(is_upper) << 5; // 设置位 5 → 小写，否则无操作
}
if high_bit_acc & 0x80 == 0 {
return bytes; // 纯 ASCII：已在原地折叠，无需第二个缓冲区
}没有数据依赖控制流的循环可以被平凡地向量化：LLVM 发出 16 字节一次的 NEON，整个过程以 > 45 GiB/s 运行——基本上是内存带宽。而且我们从通过 high_bit_acc 已经知道是否还有任何非 ASCII 工作要做。
每个步骤有多重要？在纯 ASCII 上测量累积阶梯（Apple M4，5.7 KB 缓冲区）：
| 版本 | 吞吐量 | 向量化？ |
|---|---|---|
| 朴素（break + 分支测试） | 3.1 GiB/s | 否（0 条向量指令） |
| → 无分支测试/写入，保留 break | 2.6 GiB/s | 否（0 条向量指令） |
| → 移除提前退出 break | 7.6 GiB/s | 部分（25 条向量指令） |
| → 无分支测试 + 写入（循环） | >45 GiB/s | 完全（41 条向量指令） |
提前退出是向量化的大门：保留 break 但使主体完全无分支，你仍然得到 零 条向量指令（~2.6 GiB/s）；数据依赖的循环退出本身就足以使循环保持标量。只有在 break 消失后，编译器才能向量化。最后一步——使大写折叠无分支——然后将部分向量化循环（仍将条件存储编译为 compare-blend-masked-store，~7.6 GiB/s）转变为达到内存带宽的直线算术。
注意：无分支在标量代码中是一种性能退化。 再看一下表格：使主体无分支同时保留 break（2.6 GiB/s）实际上比朴素的有分支循环（3.1 GiB/s）更慢。asm 解释了原因。有分支版本只在实际更改字节时才存储字节；它的条件 strb 对于每个小写字母、数字和空格（实际文本的绝大多数）都被跳过，保护它的预测良好的分支几乎是免费的。无分支版本用无条件的 strb每次迭代 替换那个很少执行的存储，写回全部 ~5,700 字节而不是只有少数大写字母。对无益处的额外写入流量。无分支写入只在循环向量化后获胜，因为那时存储变为单个 16 字节向量写入，无论内容如何，每字节成本都消失了。教训：无分支主体只作为向量化的使能器才有价值。单独在标量代码中，它可能会让你付出代价。
还有一个中间地带，这是标准库使用的。不是一次测试一个字节，[u8]::is_ascii 一次扫描一个机器字——在 64 位目标上，它通过 OR 两个 u64 通道并用 单个 & 0x8080_8080_8080_8080 掩码检查它们的所有高位来测试每次迭代 16 字节。你可以在此之上构建 ASCII 快速路径：分块扫描以找到 ASCII 前缀，然后在其上运行无分支（可向量化的）转换。这保留了提前退出能力——它仍然在第一个非 ASCII 块上退出——同时让两半都快速运行。问题是它两次读取数据（一次扫描，一次转换），达到约 23 GiB/s——大约是单遍无分支扫描的一半，是朴素 break 循环的 ~7 倍。一个可靠的通用默认值；只是当你控制整个循环并可以将检测和转换折叠为一个无分支遍时，不是绝对上限。
融合 这两个遍会更快吗？ 这是显而易见的下一个想法：保留分块提前退出，但在确认每个 16 字节块是 ASCII 后立即转换它，只读取数据一次。测量结果是 ~2.6× 更慢——8.7 GiB/s 对比两遍的 23。内部块转换仍然向量化到单个 16 字节操作，但现在每 16 字节就有数据依赖的提前退出分支，这个分支将循环固定在一个块一次：编译器不会跨块展开或软件流水线，每次迭代都支付完整的 load→test→branch→convert→store 延迟，没有任何东西可以隐藏在后面。分成两遍，每个都是干净的：扫描是分支轻量、无存储的字扫描，可以快速通过内存，而转换是完全向量化的无分支扫描，速度 >45 GiB/s。两个快速的无分支遍胜过一个有分支的融合遍——即使融合版本接触数据的次数只有一半。这又是同样的教训：在热循环中，分支是敌人。
避免堆分配
四十五 GiB/s 也意味着做零不必要的分配。simple_fold 按值获取输入 String，拥有它可以变异并返回的堆缓冲区。如果 OR 累加器的高位为清零，则输入已经是纯 ASCII 且已在原地折叠。我们直接交还相同的分配，无需第二个缓冲区和复制。否则，我们 memchr 到第一个非 ASCII 字节并从那里扫描尾部，在遇到折叠为不同字节的字符之前，让输出缓冲区保持未分配（空写入游标）。其多字节内容从不折叠的文本——CJK、韩文、假名、阿拉伯语、希伯来语、符号——也返回原始分配未触碰，从不复制一个字节。
为什么要用第二个缓冲区而不是像 ASCII 遍那样原地重写？因为折叠可能使字符串更长：几乎每个折叠都保留 UTF-8 长度或缩小它，但有两个异常增长——U+023A (Ⱥ) 和 U+023E (Ɀ) 各为 2 字节却折叠为 3 字节字符（ⱥ、ɀ）。一旦出现一个，输出就不再适合输入的字节，我们需要新的地方来写入。
我们一次分配该缓冲区，按最坏情况大小，而不是随着更多折叠出现而增长。增量保留调用意味着重新检查容量，偶尔重新分配，复制到目前为止写入的所有内容，以及处理额外的长度/容量记账；一次预先分配让原始写入游标直奔终点而没有任何这些。而且由于游标是 null 直到第一个增长/变化的折叠，它也充当“是否已经分配额外缓冲区？”标志。
大小需要增长上限，同样的两个异常给出了它：每 2 个输入字节最多产生 3 个输出字节，将输出上限为输入的 1.5 倍——正是我们保留的容量：
out = Vec::with_capacity(bytes.len() + bytes.len() / 2 + 4); 之后循环通过原始指针写入而无需容量检查，并在末尾调用一次 set_len。另外两个细节保持分支轻量。两个折叠之间未更改字节的运行用单个 copy_nonoverlapping 而不是逐字节移动。每个折叠无条件地写入小端字的所有 4 字节，然后仅按折叠后长度（1–4）增加游标——从热路径中删除输出长度上的分支，保留中的 +4 作为使最后一个字符的超存储安全的余量。
让 Unicode 也便宜
当一个字符确实折叠时，我们仍然不想掉下悬崖——解码 UTF-8，哈希查找，再编码。Unicode 16.0 有 1484 个简单折叠映射，但它们是一个非常稀疏且非常结构化的关系。四个观察将它们缩小到 1776 字节，并让折叠运行时从不解码完整字符。
即使在非 ASCII 路径上，绝大多数字符也不折叠。热操作实际上不是“折叠这个字符”，而是“这个字符是否折叠？”几乎总是否。表必须使这个否定测试尽可能便宜；实际折叠是已经在罕见路径上的罕见情况。这个优先级塑造了下面的布局——页位图的存在正是为了让非折叠字符在单个位测试中被拒绝，直接从其前导 UTF-8 字节，无需解码或扫描任何内容。
这正是为什么 HashMap<u32, u32> 是这项工作的错误形状，而不仅仅是更大的形状。哈希映射针对命中进行了优化：它在大约一次探测中找到存在的键，并且只有在负载因子或冲突咬合时才花费额外工作（更多探测、完整键比较）。但我们的工作负载由未命中主导——表中根本不存在的字符——而未命中是哈希映射最不喜欢的查询：它仍然必须哈希键，跳转到桶，并走探测序列足够远以证明不存在。
可折叠码点聚类为 64 码点“页”
可折叠码点聚集在一起。将码空间切成 64 码点“页”，~1484 个折叠只触及 ~1960 个可能页中的 59 个。每个页一位的存在位图单独回答否定测试：清零位是确定性的“无折叠”——复制通过，完成——这使无折叠脚本变得便宜。只有在设置位时我们才查阅第二个结构，累积 popcount 侧表，它对页进行排名（它之前有多少个已填充页）以找到其条目切片，为 ~1900 个空页存储任何内容。
let (word_idx, bit_idx, c_len) = if lead < 0xE0 {
(0usize, lead & 0x1F, 2usize) // 2 字节：字 0
} else if lead < 0xF0 {
((lead & 0x0F) as usize, bytes[read + 1] & 0x3F, 3) // 3 字节：字 = 半字节
} else {
(
(((lead & 0x07) as usize) << 6) | (bytes[read + 1] & 0x3F) as usize,
bytes[read + 2] & 0x3F,
4usize,
) // 4 字节：合并 2 字节
};
// 无需解码就拒绝：清零位 ⇒ 无折叠
if word_idx >= PAGE_BITMAP.len() || (PAGE_BITMAP[word_idx] >> bit_idx) & 1 == 0 {
read += c_len;
continue;
} 因为 word_idx 仅依赖于前导字节（以及对于四字节序列，第一个延续字节），位图加载可以提前发出。
在一页内，折叠成运行
设置的页位告诉我们此页上有某些东西折叠，但不是哪些码点或折叠为什么。明显的编码是每个可折叠码点一个条目——但这既笨重又搜索缓慢：一页可以容纳数十个折叠，我们必须扫描它们全部以找到匹配当前码点的一个。数据的结构再次拯救了我们。相邻码点绝大多数共享到其折叠的相同增量：A–Z 都映射 +32，拉丁语扩展充满了交替运行如 0x0100、0x0102、0x0104、…，其中每第二个码点折叠。我们不存储每个码点条目，而是存储运行——开始、结束、步长、增量——一个 1 位步长标志覆盖连续和每隔一个的情况。这种间隔压缩将 ~1484 个单独折叠折叠为仅 59 页中的 238 个运行（每页 ≈4 个），使页内搜索只需要查看少量条目而不是数十个。这种带增量的范围编码（包括步长技巧）借用自 Go 的 unicode 包，其 CaseRange 记录存储 Lo/Hi 范围加上每种情况的增量，用 UpperLower 哨兵标记交替块。运行在页边界处分割，所以运行从不跨越两页。
运行记录是两个干净字节
由于两个端点都在一页内，它们适合 6 位，分布在两个数组中：RUN_END_LOW[``i``] = end & 0x3F（扫描键）和 RUN_START_STRIDE[``i``] = (start & 0x3F) | ((stride − 1) << 6)（仅在命中时读取）。因为每个键都是一个干净字节，页内搜索可以变宽：而不是一次比较 cp & 0x3F 与运行，我们加载8 个 end_low 字节到单个 u64 中，并用一个无分支 SWAR 步骤一次测试它们全部——(chunk | 0x80…80) − broadcast(low) & 0x80…80 设置键 ≥ cp & 0x3F 的每个通道的最高位。该掩码的单一位扫描（键已排序，所以第一个设置通道是我们想要的运行）找到槽位。一页平均有 ~4 个运行；那个 8 宽比较几乎总是用一步解决整个搜索。一个不幸的页确实有 30 个运行，这将比较放在一个短循环中，该循环每次跨八个键步进——但该循环在整个 Unicode 中只在一个页上最多触发几次，而且从不在常见页上。无论哪种方式：没有每运行分支，也没有任何地方有码点重建。
/// 页中 `n` 个运行中第一个 `end_low >= low_v` 的运行的偏移量，
/// 如果没有则为 `n`。通过 SWAR 一次扫描 8 个 `end_low` 字节。
#[inline]
fn scan_end_low(lo: usize, n: usize, low_v: u8) -> usize {
const HIGH: u64 = 0x8080_8080_8080_8080;
const ONES: u64 = 0x0101_0101_0101_0101;
let bcast = (low_v as u64).wrapping_mul(ONES);
let mut base = 0;
while base < n {
// RUN_END_LOW 填充了 8 字节，所以此读取总是在边界内。
let chunk = u64::from_le_bytes(
RUN_END_LOW[lo + base..lo + base + 8]
.try_into()
.expect("8-byte slice"),
);
// `(b | 0x80) - low_v` 保持其高位当且仅当 `b >= low_v`（无跨通道借位）。第一个设置通道是第一个 `>= low_v` 的运行。
let ge = (chunk | HIGH).wrapping_sub(bcast) & HIGH;
if ge != 0 {
let j = base + (ge.trailing_zeros() / 8) as usize;
return if j < n { j } else { n };
}
base += 8;
}
n
} 折叠是小端字节加法
在小端机器上，读取为 u32 的折叠后字符的 UTF-8 字节，等于源字节（作为 u32）加上每运行常量。并行的 BYTE_DELTA[i] 表然后将整个折叠转变为掩码加载、一次 wrapping_add 和 4 字节存储：
let word = u32::from_le_bytes(next_four_bytes) & length_mask; // 保留此字符的字节
let folded = word.wrapping_add(BYTE_DELTA[i]); // 折叠，作为一次字节加法
write_u32_le(dst, folded); // 存储所有 4 字节...
dst += utf8_len(folded); // ...按折叠后长度前进该代码片段中的两个长度——源字符的 length_mask 和目标的按折叠后长度前进——都来自另一个小技巧。UTF-8 序列的长度由其前导字节的前四位固定，让 16 个可能的长度每个打包一个半字节到一个 64 位常量（0x4322_1111_1111_1111）中；然后长度是移位和掩码，(LEN_BITS >> (4 * (lead >> 4))) & 0xF——没有 if 链，没有表内存，没有任何东西让预测器出错。（计数前导一——(!lead).leading_zeros()——也可以工作，因为前导字节每个序列字节携带一个前导 1 位。）
/// UTF-8 序列的字节数，其前导字节为 `lead`。
#[inline]
pub fn utf8_len(lead: u8) -> usize {
const UTF8_LEN_BY_LEAD: u64 = 0x4322_1111_1111_1111;
((UTF8_LEN_BY_LEAD >> (4 * (lead >> 4))) & 0xF) as usize
}因为我们按折叠后长度前进，这甚至处理长度变化的折叠——U+212A KELVIN SIGN（3 字节）→ k（1 字节），或 U+023A Ⱥ（2 字节）→ U+2C65 ⱥ（3 字节）——通过写入比读取更少或更多的字节。这部分我们相信是真正新的：我们查看过的每个其他文件夹——ICU、Go 的 unicode、Rust 的 regex、CPython、glibc——都将 UTF-8 解码为码点，在那里应用折叠，然后重新编码（即使 SIMD 文件夹也先解码）。在字节空间中做算术跳过了解码和编码，这正是为什么此路径可以超越已经有答案制表的哈希映射——哈希映射仍然必须解码其键并编码其结果。字节空间算术假设输入是格式良好的、最短形式 UTF-8——每个码点都用最少字节数编码。将源字节读取为 u32 并添加每运行增量只有在源为规范形式时才会落在正确的折叠编码上；过长编码（填充到比必要更多字节的码点，例如 / 作为 0xC0 0xAF）有不同的字节模式，会破坏 length_mask 和增量算术。这在 Rust 中不是真正的限制——&str/String 保证持有有效 UTF-8，根据定义拒绝过长序列——但从其他地方提供原始字节的调用者必须先验证（或以其他方式规范化）它们。
尾部循环中的 ASCII 快捷方式
另一个快捷方式完善了尾部循环。请记住，第一遍已经小写了每个 ASCII 字节，所以当扫描在尾部遇到 ASCII 字节时，它前进一个字节并继续——根本没有页探测，没有表接触。而且它也不复制那个字节：未修改的字节（ASCII 和非折叠多字节都一样）不是一次移动一个。扫描只是继续行走，直到到达实际折叠的字符，然后用单个 copy_nonoverlapping 刷新上一个折叠和这个之间的整个未更改运行。因此混合文本——带 ASCII 空格和标点的 CJK，或带偶尔带重音标识符的代码——因此快速通过 ASCII 填充物，只为真正的多字节字符查阅位图，批量复制而不是逐字节。
放在一起：整个表
| 组件 | 字节 |
|---|---|
| PAGE_BITMAP（每 64-cp 页 1 位） | 248 |
| POPCNT_SAMPLES（累积 popcount） | 32 |
| PAGE_OFFSET（每个已填充页） | 60 |
| RUN_END_LOW（扫描键，end & 0x3F，+8 填充） | 246 |
| RUN_START_STRIDE（start & 0x3F | stride） | 238 |
| BYTE_DELTA（每运行的小端折叠增量） | 952 |
| 总计 | 1776 |
那是 每个折叠条目 9.6 位，其中一半以上是我们为无解码路径交换的 BYTE_DELTA 侧表；索引 + 运行记录单独约为 4.4 位/条目。
与明显的替代方案相比，这 1776 字节小一个数量级或更多——而且与大多数不同，它从不解码字符：
| 表示 | 大小 |
|---|---|
| 朴素 [(u32, u32); 1484] | ~11.6 KB |
| regex-syntax 的 case_folding_simple 表 | ~70 KB |
| Go 的 unicode.SimpleFold（轨道 + ASCII + 范围） | ~7.3 KB |
| 运行时 HashMap<u32, u32> | ~17 KB |
| 此 crate（分页位图 + 打包运行） | 1776 B |
它与替代方案相比的位置
在常见情况下，ASCII，折叠以内存带宽运行（>45 GiB/s），比其他真实文件夹快一个数量级以上，比（非等价的）str::to_lowercase 函数快 50% 以上。为了获得非 ASCII 情况的粗略“上限”，我们测量了优化后的 Utf8 解码 + 编码往返，而不使用 simdutf crate 执行任何实际大小写折叠。这个实验始终达到约 2GB/秒，对于最坏情况的全折叠输入，它仅比我们的解决方案快约两倍。朴素哈希映射在所有工作负载上都落后于一切。
三列是产生相同输出的真实大小写文件夹：simple_fold（此 crate）、simd_normalizer（simd-normalizer crate）和 HashMap（朴素 CaseFolding.txt 查找）。工作负载行选择模拟从典型到最坏情况的不同场景：
| 工作负载（输入大小） | simple_fold | simd_normalizer | HashMap（字节路径） |
|---|---|---|---|
| 纯 ASCII（5.7 KB） | >45 GiB/s | 1.21 GiB/s | 213 MiB/s |
| CJK，无折叠（8.1 KB） | 2.95 GiB/s | 1.97 GiB/s | 558 MiB/s |
| 符号 / 缅甸语，无折叠（9.0 KB） | 2.96 GiB/s | 1.56 GiB/s | 410 MiB/s |
| 最坏情况：拉丁语/希腊语/西里尔语（Unicode U+0000–U+FFFF），全折叠（8.8 KB） | 869 MiB/s | 922 MiB/s | 334 MiB/s |
| 长度变化折叠（1.7 KB） | 1.26 GiB/s | 716 MiB/s | 233 MiB/s |
将绝对数字视为说明性的，不可移植的：整个设计依赖于自动向量化、SWAR 和小端字节算术，所以数字——甚至行之间的比率——在不同的微架构上（更宽或更窄的向量单元、不同的内存带宽、大端目标、x86 vs ARM）可能会发生实质性变化。
更多细节可以在 README 的性能部分 中找到。
带走这个
大小写折叠是文本操作中最基本的一种，这正是为什么值得努力：我们对索引的每个字节运行它。收益来自两个与直觉相悖的想法——分支自由地扫描整个缓冲区而不是提前停止，以及将折叠作为字节空间算术而不是解码到码点。它们一起让常见情况以内存带宽运行，罕见折叠无需解码运行，表足够小（1776 字节）以保持驻留。无解码字节空间折叠是我们相信真正新的部分；这就是为什么此路径可以击败已经有答案的哈希映射。
这里肯定还有更多可以发现的东西，我们希望看到它。crate 是 casefold；生成的表和完整设计说明与源代码一起存在。
0 Comments
Log in to join the conversation.No comments yet. Be the first to share your thoughts.