fzf 模糊匹配中的 SIMD 双字节查找：indexByteTwo 的 NEON/AVX2 实现解析

本文以 fzf 仓库中的 src/algo/SIMD.md 为核心，系统讲解 IndexByteTwo / lastIndexByteTwo 这对 SIMD 字节查找函数的设计动机、跨架构实现（ARM64 NEON、AMD64 AVX2/SSE2、纯 Go 回退）、在模糊匹配算法中的实际调用方式，以及仓库提供的三层正确性验证体系（表驱动测试、穷举测试、fuzz 测试）与微基准测试方法。读完后你将能够：理解 fzf 如何用一条 SIMD 指令流同时查找大小写两个字节、看懂两套汇编的 syndrome/mask 提取原理，并知道如何在本地运行测试与基准来验证这套实现。

函数定义与动机

这对函数的语义非常简洁：

• IndexByteTwo(s []byte, b1, b2 byte) int —— 返回 s 中 b1 或 b2 首次出现的下标，不存在则返回 -1；
• lastIndexByteTwo(s []byte, b1, b2 byte) int —— 返回 s 中 b1 或 b2 最后一次出现的下标，不存在则返回 -1。

它们的用途直接来自 fzf 的模糊匹配算法（src/algo/algo.go）：在大小写不敏感的搜索中，算法需要“跳过”输入中不匹配的区域。如果分别调用两次 bytes.IndexByte（一次查小写、一次查大写），就要扫两遍内存；而 IndexByteTwo 用一条 SIMD 通道同时匹配两个字节，一次遍历即可定位两者中最早出现的位置。

从源码结构看，这对函数在算法中的两个真实调用点可以印证这一动机：

1. src/algo/algo.go 的 trySkip 函数中，当模式大小写不敏感且目标字符是英文字母时，直接调用 IndexByteTwo(byteArray, b, b-32) —— 利用 ASCII 中小写字母与对应大写字母相差 32 的特性，把“小写 x 或大写 X”编码成一次双字节查找；
2. src/algo/algo.go 中用 lastIndexByteTwo(tail, b, b-32) 定位模式最后一个字符的最后一次出现，以此收窄后续 DP 匹配的计算范围。

也就是说，SIMD 双字节查找是 fzf 匹配热路径（Algo 接口定义于 src/algo/algo.go）的组成部分，而不是孤立的微优化。

文件布局

SIMD.md 给出了该功能的完整文件布局，以下表格与仓库实际文件一一对应：

文件	作用
indexbyte2_arm64.go	ARM64 的 Go 声明（//go:noescape）
indexbyte2_arm64.s	ARM64 NEON 汇编（32 字节对齐块 + syndrome 提取）
indexbyte2_amd64.go	AMD64 的 Go 声明 + AVX2 运行时检测
indexbyte2_amd64.s	AMD64 AVX2/SSE2 汇编（含 CPUID 分发逻辑）
indexbyte2_other.go	其他架构的纯 Go 回退实现
indexbyte2_test.go	单元测试、穷举测试、fuzz 测试与基准测试

各平台通过 Go 构建标签隔离：indexbyte2_amd64.go 带 //go:build amd64，indexbyte2_arm64.go 带 //go:build arm64，indexbyte2_other.go 带 //go:build !arm64 && !amd64，保证任一架构下恰好有一个实现参与编译。

ARM64（NEON）实现原理

src/algo/indexbyte2_arm64.s 的汇编改编自 Go 标准库 internal/bytealg/indexbyte_arm64.s（单字节版本），核心是把单字节 mask 扩展为每字节 2 比特的 64 位 syndrome：

• 两个目标字节分别通过 VMOV 广播进 NEON 寄存器（V0 = splat(b1)、V7 = splat(b2)）；
• 数据按 32 字节对齐块处理。每个块对两个半区分别执行 VCMEQ（与 b1 比较、与 b2 比较），再用 VORR 把两组结果按字节取或合并；
• 关键的 syndrome 构造：用魔数常量 0x40100401（每 4 字节中各字节分别带 1、4、16、64 比特）对合并结果 VAND 后做 VADDP 归约，最终得到一个 64 位值，第 2i 位对应块内第 i 个字节是否命中；
• IndexByteTwo（正向）在尾部用 RBIT + CLZ 求出 syndrome 中最低置位比特，除以 2 即得块内字节偏移（见 tail 标签处）；
• lastIndexByteTwo（反向）从包含末字节的对齐块开始向前扫，直接对原始 syndrome 用 CLZ 求最高置位比特：byte_offset = (63 - CLZ) / 2（见 llast 标签处）；
• 未对齐的首/尾块通过左右移位做比特遮罩，清掉不属于切片的字节对应的位；反向版本还需区分“头尾块相同”（lmaskfirst）与“仅一块”（ltailonly）两种边界情形。

由于 32 字节块会越过切片边界多读最多 31 字节，所有块内比较后都必须遮罩越界位——这正是汇编中大量 LSL/LSR 成对移位的作用。

AMD64（AVX2 + SSE2 回退）实现原理

AMD64 侧采用运行时 CPUID 分发，而不是编译期选择：

• 初始化时 cpuHasAVX2() 检查 CPUID + XGETBV（AVX2 支持 + 操作系统 YMM 状态保存支持），结果缓存在包级变量 _useAVX2 中，见 indexbyte2_amd64.go。汇编实现 cpuHasAVX2 依次验证：CPUID 最大叶子 ≥ 7、CPUID.1:ECX bit 27（OSXSAVE）、CPUID.7.0:EBX bit 5（AVX2）、XGETBV 返回的 bit 1+bit 2 全置位（OS 支持 XMM/YMM 状态）；
• AVX2 路径（输入 ≥ 32 字节且 CPU 支持时进入）：
  • 用 VPBROADCASTB 把两个目标字节各广播进一个 YMM 寄存器；
  • 主循环每次处理 32 字节：VMOVDQU 载入 → VPCMPEQB 分别与两个目标比较 → VPOR 合并 → VPMOVMSKB 取出 32 位 mask → BSFL（正向）/ BSRL（反向）扫描位；
  • 从 fwd_avx2_loop 可以看到每次循环体只有 5 条指令（对比 SSE2 路径的 7 条），且单条吞吐是 2 倍，因此总吞吐约为 SSE2 的 4 倍量级；
  • 每个返回点前都执行 VZEROUPPER，避免 SSE/AVX 状态切换惩罚（fwd_avx2_success、back_avx2_first 等标签处均可见）；
  • 最后 32 字节块单独再查一次（允许与前一块重叠），因为主循环的终止条件是 DI < AX，其中 AX = base + len - 32；
• SSE2 路径（输入 < 32 字节，或 CPU 无 AVX2）：
  • 广播方式为 MOVD + PUNPCKLBW ×2 + PSHUFL（AVX2 才有 VPBROADCASTB）；
  • 主循环每次处理 16 字节：PCMPEQB ×2、POR、PMOVMSKB，随后同样是 BSFL/BSRL；
  • < 16 字节的小输入有专门路径（fwd_small / back_small）：16 字节载入可能越过 4KB 页边界触发缺页异常，所以先 TESTW $0xff0 检查是否贴近页尾；贴近页尾时改为从 base + len - 16 载入（保证落在合法页内），再按 SHLL/SHRL 移位把 mask 对齐回正确的字节坐标。这是这段汇编中最易错的边界逻辑，也是穷举测试重点覆盖的区域；
• 反向版本（lastIndexByteTwo）的块结构相同，区别仅在于从尾部对齐块向前步进，用 BSRL 找每个块内最高置位位。

从源码结构看，AMD64 与 ARM64 两条路径在策略上是一致的——“块内并行比较 + 位压缩定位”，只是压缩介质不同：AVX2/SSE2 用 PMOVMSKB 直接产出 1 比特/字节的 mask（因为块大小恰好是 mask 位宽），NEON 则用 syndrome（2 比特/字节）来支持 32 字节块。

其他架构的纯 Go 回退

src/algo/indexbyte2_other.go 提供语义完全一致的纯 Go 实现：

• IndexByteTwo 先 bytes.IndexByte(s, b1) 找 b1 的位置 i1，再把 b2 的搜索范围收窄到 s[:i1]（scope-limiting），取两者中更靠前者；i1 == 0 时提前短路；
• lastIndexByteTwo 就是一个简单的倒序 for 循环。

这两个函数同时承担了测试中的参考实现角色（见下文测试一节），保证“汇编输出 = 朴素循环输出”这一等价性可以被机器反复验证。

在模糊匹配算法中的调用链

结合 src/algo/algo.go，这对函数参与两条具体流程：

1. 正向跳过（skip）：trySkip 被字符模式匹配（char algo）用于定位模式每个字符的候选位置。对英文字母的大小写不敏感查找，IndexByteTwo(byteArray, b, b-32) 一次遍历同时覆盖两种大小写，返回值再偏移 from 还原为原切片坐标；找不到则立即返回 -1，整个模式匹配失败，这本身也是重要的剪枝。
2. 反向收窄（scope limit）：匹配前算法先粗略定位模式首尾字符的出现区间；其中“模式最后一个字符在输入尾部最后出现的位置”用 lastIndexByteTwo(tail, b, b-32) 计算，得到 firstIdx, lastIdx + 1 + end + 1 的收窄区间，供后续 DP（Hunt 式）匹配限制宽度。last 方向的选择与 forward 参数（Algo 函数签名的第三个布尔参数）对应。

两条路径共同点：只有 !caseSensitive && b >= 'a' && b <= 'z' 时才走双字节 SIMD 查找，其余字符（非字母、数字、符号）仍走单字节 bytes.IndexByte/bytes.LastIndexByte，避免了不必要的双路比较开销。

运行测试

SIMD.md 给出的测试命令可直接使用（在仓库根目录执行）：

# 单元测试 + 穷举测试
go test ./src/algo/ -run 'TestIndexByteTwo|TestLastIndexByteTwo' -v

# Fuzz 测试（各运行 10 秒）
go test ./src/algo/ -run '^$' -fuzz FuzzIndexByteTwo -fuzztime 10s
go test ./src/algo/ -run '^$' -fuzz FuzzLastIndexByteTwo -fuzztime 10s

# 交叉架构：在 arm64 Mac 上（经 Rosetta）跑 amd64 测试
GOARCH=amd64 go test ./src/algo/ -run 'TestIndexByteTwo|TestLastIndexByteTwo' -v
GOARCH=amd64 go test ./src/algo/ -run '^$' -fuzz FuzzIndexByteTwo -fuzztime 10s
GOARCH=amd64 go test ./src/algo/ -run '^$' -fuzz FuzzLastIndexByteTwo -fuzztime 10s

对应 src/algo/indexbyte2_test.go 中的测试入口：TestIndexByteTwo、TestLastIndexByteTwo、FuzzIndexByteTwo、FuzzLastIndexByteTwo。

三层正确性验证体系

这套汇编的正确性不靠人眼审读保证，而是由 indexbyte2_test.go 中的三层测试机器验证：

1. 表驱动测试：已知输入 → 期望输出的固定用例集，快速定位回归；
2. 穷举测试：覆盖长度 0–256、每个可能的匹配位置、无匹配用例、以及“两个目标字节都出现”的混合用例，全部与朴素循环参考 loopIndexByteTwo（indexbyte2_test.go）逐一对比。长度上限 256 特意跨越了 16/32 字节块边界以及页边界安全路径的各种组合；
3. Fuzz 测试：基于 testing.F 的随机化输入，同样以朴素循环（loopIndexByteTwo / refLastIndexByteTwo）为参考实现持续比对。

这种“汇编 vs 参考循环”的等价性测试模式与 Go 标准库 internal/bytealg 的测试策略一致，是验证 SIMD 汇编可靠性的标准做法。

运行微基准

# 全部 indexByteTwo / lastIndexByteTwo 基准（含内存统计）
go test ./src/algo/ -bench 'IndexByteTwo' -benchmem

# 指定规模
go test ./src/algo/ -bench 'IndexByteTwo_1000'

基准入口见 indexbyte2_test.go：BenchmarkIndexByteTwo_{10,100,1000} 与 BenchmarkLastIndexByteTwo_{10,100,1000}。每个基准内部构造一段 size 长度的数据（字符在 'a' 附近循环、在 pos 处埋一个目标字节 'Z'），然后对比三种实现的耗时（见 benchIndexByteTwo）：

• asm：IndexByteTwo（SIMD 实现）；
• 2xIndexByte：refIndexByteTwo，两次 bytes.IndexByte 的 scope-limiting 写法（即回退实现的策略，也是 SIMD 出现前的朴素做法）；
• loop：逐字节 for 循环。

反向基准（benchLastIndexByteTwo）对比 asm（lastIndexByteTwo）与 loop 两种实现。基准结果的具体数值依赖运行机器，本文不预设任何性能数据；但指令计数层面的事实可以从汇编直接读出：AVX2 主循环 5 条指令/32 字节，SSE2 主循环 7 条指令/16 字节。

小结

• IndexByteTwo/lastIndexByteTwo 为 fzf 的大小写不敏感模糊匹配提供了“一次遍历匹配两个字节”的 SIMD 原语，调用点位于 src/algo/algo.go 的 trySkip 与 src/algo/algo.go 的范围收窄逻辑；
• ARM64 与 AMD64 分别以 NEON syndrome（2 比特/字节）和 AVX2/SSE2 mask（1 比特/字节）实现块内并行比较 + 位扫描定位，AMD64 侧还有运行时 CPUID/XGETBV 分发与页边界安全的小输入路径；
• 非 x86/ARM64 架构有纯 Go 回退（src/algo/indexbyte2_other.go），语义与汇编版本完全一致；
• 正确性由表驱动、0–256 长度穷举、fuzz 三层测试保证，性能可通过 go test -bench 在本地对 asm/2xIndexByte/loop 三种实现直接对比验证。