这如何更快？使用“FPU 技巧”的 52 位模乘法比 x64 上的内联 ASM 更快

Question

我发现这个：

#define mulmod52(a,b,m) (((a * b) - (((uint64_t)(((double)a * (double)b) / (double)m) - 1ULL) * m)) % m)

... 比：

static inline uint64_t _mulmod(uint64_t a, uint64_t b, uint64_t n) {
    uint64_t d, dummy;                    /* d will get a*b mod c */
    asm ("mulq %3\n\t"              /* mul a*b -> rdx:rax */
         "divq %4\n\t"              /* (a*b)/c -> quot in rax remainder in rdx */
         :"=a"(dummy), "=&d"(d)     /* output */
         :"a"(a), "rm"(b), "rm"(n)  /* input */
         :"cc"                      /* mulq and divq can set conditions */
        );
    return d;
}

前者是利用 FPU 计算两个最多 52 位数字的模乘法的技巧。后者是简单的 X64 ASM，用于计算两个 64 位数字的模乘，当然它也仅适用于 52 位。

前者比后者快约 5-15%，具体取决于我在哪里测试。

鉴于 FPU 技巧还涉及一次整数乘法和一次整数除法（模数）以及额外的 FPU 工作，这怎么可能？这里有一些我不明白的地方。是一些奇怪的编译器工件，例如asm内联破坏编译器优化传递吗？

Answer 1

在之前的 Icelake 处理器（例如Skylake ）上，“完整”128 位 x 64 位除法和“半”64 位 x 64 位除法（其中上 qword 为零）之间存在很大差异。完整的可能需要近 100 个周期（根据 中的值略有不同rdx，但rdx即使设置为 1时也会突然出现“悬崖” ），半个周期更多，大约需要 30 到 40 个周期，具体取决于µarch。

64 位浮点除法（对于除法）在 14 到 20 个周期内相对较快，具体取决于 µarch，因此即使有这个和其他一些更不重要的开销，也不足以浪费 60 个周期的优势“半”师与“全”师相比较。所以复杂的浮点版本可以提前出现。

Icelake显然有一个惊人的分频器，可以在 18 个周期内完成一个完整的除法（“半”除法并不会更快），内联汇编在 Icelake 上应该很好。

在 AMD Ryzen 上，具有非零上 qword 的分区似乎随着rdx变得更高而逐渐变慢（“性能悬崖”更少）。