时间戳

首页 > 解决方案 > 这怎么更快？使用“FPU 技巧”的 52 位模乘法比 x64 上的内联 ASM 更快

performance - 这怎么更快？使用“FPU 技巧”的 52 位模乘法比 x64 上的内联 ASM 更快

问题描述

我发现这是：

#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 inline 破坏了编译器优化通道？

标签： performanceassemblyoptimizationx86-64

解决方案

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

64 位浮点除法（对于除法）相对较快，大约 14 到 20 个周期，具体取决于 µarch，因此即使加入了这一点以及一些其他更不显着的开销，这还不足以浪费 60 个周期的优势“半”师与“全”师相比。所以复杂的浮点版本可以提前出来。

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

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

推荐阅读