这怎么更快？52 位模乘法使用 "FPU trick" 比 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 %3nt"              /* mul a*b -> rdx:rax */
"divq %4nt"              /* (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位乘64位除法和"半"64位乘64位数除法(其中上qword为零(之间有很大区别。完整的一个可能需要近100个周期(根据rdx中的值略有变化，但当rdx设置为1时会出现突然的"悬崖"(，半个周期更多的是30到40个ish周期，具体取决于µarch。

64位浮点除法(对于除法(相对较快，大约为14到20个周期，具体取决于µarch，因此即使有这一点和其他一些不太重要的开销，也不足以浪费"半"除法与"全"除法相比的60个周期优势。因此，复杂的浮点版本可以提前推出。

Icelake显然有一个惊人的分频器，可以在18个周期内进行全分频("半"分频并不更快(，内联asm在Icelake上应该很好。

在AMD Ryzen上，随着rdx越来越高(不太像"性能悬崖"(，具有非零上qword的划分似乎越来越慢。