查询表顺序不同引发性能差异的原因排查

问题背景 #

有如下Rust函数，用于检查指定位置是否被攻击：

pub fn attacked(&self, sq: usize) -> bool {
    self.lut1[sq] || self.lut2[sq] || self.lut3[sq] || self.lut4[sq] || self.lut5[sq]
}

该函数查询5个类型为[u64; N]的栈上查找表，通过短路求值返回是否任意表中对应位置为true。函数占模拟程序总逻辑的约5%，编译参数为codegen-units = 1和opt-level = 3。

测试发现：调整查找表的查询顺序会导致吞吐量出现显著差异（最高65 Mnodes/s，最低50 Mnodes/s）。已知每个表的命中概率相同，排除短路求值的逻辑差异；总表大小约1MB，理论上可完全驻留在CPU缓存中，排除内存延迟影响。且无法复现最小示例，移除无关代码后差异消失或变化。

可能的原因分析 #

• CPU指令级并行（ILP）与指令调度差异：不同查询顺序会让编译器生成不同的指令序列，影响CPU超标量执行单元的利用率。比如某些顺序下，内存加载和逻辑判断的指令组合更适合CPU乱序执行引擎，能重叠操作减少流水线停顿；反之则可能导致执行单元闲置。

• 缓存行对齐与缓存冲突：单个查找表的起始地址与缓存行边界的相对位置不同，不同查询顺序会改变缓存行访问模式。若先访问的表占用了关键缓存组，后续访问可能触发缓存冲突，增加命中延迟；部分顺序下的表访问可能集中在同一缓存行，提升访问效率。

• 编译器全局优化的上下文依赖：opt-level=3下编译器会做跨函数内联、寄存器分配等全局优化，查询顺序会影响寄存器分配策略。比如某些顺序下，编译器能将表地址或索引保留在寄存器中，减少寄存器-内存交互开销；函数内联后，查询顺序与调用处代码的组合不同，优化空间也会变化。

• 分支预测的细微差异：虽然命中概率一致，但不同查询顺序对应的短路跳转分支模式不同，可能影响CPU分支预测器的准确率。哪怕微小的预测失败率提升，也会触发流水线清空，拉低整体性能。

• 硬件预取器效率差异：CPU预取器会根据访问模式提前加载数据，不同查询顺序形成的地址访问规律不同。若顺序中表地址存在连续偏移，预取器能高效提前加载后续数据；无规律的地址顺序会让预取器失效，增加内存访问等待时间。

内容的提问来源于stack exchange，提问作者user1002430