现在在 x86-64 上还值得使用 Quake 快速反平方根算法吗？

Question

具体来说，这是我正在讨论的代码：

float InvSqrt(float x) {
  float xhalf = 0.5f*x;
  int i = *(int*)&x;        // warning: strict-aliasing UB, use memcpy instead
  i = 0x5f375a86- (i >> 1);
  x = *(float*)&i;          // same
  x = x*(1.5f-xhalf*x*x);
  return x;  
}

我忘了我从哪里得到这个，但它显然比原来的 Quake III 算法（魔法常数略有不同）更好、更高效或更精确，但这个算法创建以来已经有 20 多年了，我只是想知道它是否是就性能而言，或者如果有一条指令已经在现代 x86-64 CPU 中实现了它，那么仍然值得使用它。

Answer 1

起源：

\n

参见约翰·卡马克的不寻常的快速平方根倒数（雷神之锤 III）

\n\n

现代实用性：无，已被 SSE1 废弃rsqrtss

\n

使用_mm_rsqrt_ps或ss来并行获得 4 个浮点的非常近似的倒数平方根，比一个好的编译器可以用它做的要快得多（使用 SSE2 整数移位/加法指令将 FP 位模式保留在 XMM 寄存器中，这可能不是它实际上如何使用类型双关语编译为整数。这是 C 或 C++ 中的严格别名 UB；使用memcpy或 C++20 std::bit_cast。）

\n

https://www.felixcloutier.com/x86/rsqrtss记录了 asm 指令的标量版本，包括|Relative Error| \xe2\x89\xa4 1.5 \xe2\x88\x97 2\xe2\x88\x9212保证。（即大约一半的尾数位是正确的。）一次 Newton-Raphson 迭代可以将其精确到正确的 1ulp 以内，尽管仍然不是您从实际 sqrt 中获得的 0.5ulp。请参阅快速矢量化 rsqrt 和 SSE/AVX 的倒数，具体取决于精度）

\n

rsqrtpsmulps在大多数 CPU 上，执行速度仅比/指令稍慢mulss，例如 5 个周期延迟，1 个时钟吞吐量。（通过牛顿迭代来改进它，更多的 uops。）延迟因微架构而异，在 Zen 3 中低至 3 uops，但自 Conroe 以来，英特尔至少以大约 5c 的延迟运行（https://uops.info/）。

\n

Quake InvSqrt 中的幻数的整数移位/减去类似地提供了更粗略的初始猜测，其余的（在将位模式类型双关回到 a 之后float是牛顿拉夫森迭代。

\n\n

编译器甚至会rsqrtss在使用 进行编译时sqrt为您-ffast-math使用，具体取决于上下文和调整选项。1.0f/sqrtf(x)（例如，使用-O3 -ffast-math -march=skylake https://godbolt.org/z/fT86bKesb进行现代 clang 编译，使用vrsqrtss3x vmulss 加上 FMA。）非互易 sqrt 通常不值得，但 rsqrt + 细化避免了除法和 sqrt。

\n\n

全精度平方根和除法本身并不像以前那么慢，至少与 mul/add/sub 相比，如果您不经常使用它们的话。（例如，如果您可以隐藏延迟，则每 12 个左右的其他操作可能花费大约相同的成本，仍然是单个 uop，而不是 rsqrt + 牛顿迭代的多个 uop。）请参阅浮点除法与浮点乘法
\n但是 sqrt 和 div确实会相互竞争吞吐量，因此需要除以平方根是一种令人讨厌的情况。

\n

_mm_rsqrt_ps因此，如果您在一个主要只执行 sqrt 的数组上有一个错误的循环，而不是与其他数学运算混合，那么这就是（和牛顿迭代）作为比以下更高的吞吐量近似值的用例_mm_sqrt_ps

\n

但是，如果您可以将该通道与其他东西结合起来以增加计算强度并在保留 div/sqrt 单位的同时完成更多工作，通常最好单独使用真正的 sqrt 指令，因为这仍然是只需 1 uop 供前端发出，供后端跟踪和执行。与牛顿迭代相比，如果 FMA 可用于倒数平方根，则需要大约 5 微秒，否则更多（如果需要非倒数平方根也是如此）。

\n

例如，Skylake 每 3 个周期有 1 个sqrtps xmm吞吐量（128 位向量），如果您每 6 个数学运算不执行超过 1 个，则其成本与 mul/add/sub/fma 操作相同。（对于 256 位 YMM 向量，6 个周期，吞吐量更差。）牛顿迭代会花费更多的 uops，因此如果端口 0/1 的 uops 是瓶颈，那么直接使用 sqrt 会是一个胜利。（这是假设无序 exec 可以隐藏延迟，通常是在每次循环迭代都是独立的情况下。）如果您使用多项式近似作为 log 或 exp 等内容的一部分，这种情况很常见。环形。

\n

另请参阅快速矢量化 rsqrt 和 SSE/AVX 的倒数，具体取决于精度re：现代 OoO 执行 CPU 上的性能。

\n