基线实现应该是可预测的

作者写Reciprocal是因为找不到 Rust 中无数据相关行为的良好 div-by-mul 实现。某些除数在经典实现中需要不同的、较慢的代码路径,而 Reciprocal 使用统一代码路径实现两个表达式来避免此问题。

  • 第一个表达式\(f_{m,s}(x) = \left\lfloor \frac{m x}{2^s} \right\rfloor\)对应通常的 div-by-mul 近似,第二个表达式\(g_{m^\prime,s^\prime}(x) = \left\lfloor\frac{m^\prime \cdot \min(x + 1, \mathtt{u64::MAX})}{2^{s^\prime}}\right\rfloor\)是另一种乘法和加法方案。
  • 有一对对偶近似,可避免数据依赖行为,且能在最差情况下获得额外一位精度。幸运的是,除 1 和u64::MAX外,u64::MAX的所有因子都适用于“向上取整”近似,所以饱和增量在实际使用第二个“向下取整”近似时总是安全的。
  • 在不同除数的测试中,除以 2 时 Reciprocal 不如右移快,但在除以 7 等“硬”除法时表现较好,在除以 11 等常规除法时也能保持 1.3ns/division 的稳定速度,且其热路径不受除数影响,具有可预测的性能。而其他分支实现在面对不同除数时性能变化较大, unpredictable 代码容易在基准测试中表现良好,但难以确定与实际工作负载的差异。

总之,Reciprocal 展示了对于常量整数除法,无特殊情况的可预测基线实现是较好的选择。

阅读 6
0 条评论