为什么 __int128_t 在 x86-64 GCC 上比 long long 快？

Question

这是我的测试代码：

#include <chrono>
#include <iostream>
#include <cstdlib>
using namespace std;

using ll = long long;

int main()
{
    __int128_t a, b;
    ll x, y;

    a = rand() + 10000000;
    b = rand() % 50000;
    auto t0 = chrono::steady_clock::now();
    for (int i = 0; i < 100000000; i++)
    {
        a += b;
        a /= b;
        b *= a;
        b -= a;
        a %= b;
    }
    cout << chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - t0).count() << ' '
         << (ll)a % 100000 << '\n';

    x = rand() + 10000000;
    y = rand() % 50000;
    t0 = chrono::steady_clock::now();
    for (int i = 0; i < 100000000; i++)
    {
        x += y;
        x /= y;
        y *= x;
        y -= x;
        x %= y;
    }
    cout << chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - t0).count() << ' '
         << (ll)x % 100000 << '\n';

    return 0;
}

这是测试结果：

$ g++ main.cpp -o main -O2
$ ./main
2432 1
2627 1

在 x64 GNU/Linux 上使用 GCC 10.1.0，无论是使用 -O2 优化还是未优化，__int128_t总是比long long.

int并且double都明显快于long long; long long已成为最慢的类型。

这是怎么发生的？

Answer 1

性能差异来自在这种特定情况下使用 GCC/Clang的 128 位除法/模数的效率。

事实上，在我的系统以及对godbolt，sizeof(long long) = 8和sizeof(__int128_t) = 16。因此，前者的操作由本机指令执行，而后者则不是（因为我们专注于 64 位平台）。加法、乘法和减法的速度较慢__int128_t。但是，用于 16 字节类型（__divti3以及__modti3x86 GCC/Clang）上的除法/模数的内置函数比本机idiv指令快得多（这非常慢，至少在 Intel 处理器上）。

如果我们更深入地查看 GCC/Clang 内置函数的实现（仅用于__int128_t此处），我们可以看到它__modti3使用了条件（在调用 时__udivmodti4）。英特尔处理器可以更快地执行代码，因为：

• 采取分支可以很好地预测在这种情况下，因为它们总是相同的（并且还因为循环执行数百万次）;
• 除法/模数被拆分为更快的本机指令，这些指令主要可以由多个 CPU 端口并行执行（并且受益于乱序执行）。甲div指令仍然使用在最可能的路径（特别是在这种情况下）;
• div/idiv指令的执行时间涵盖了整个执行时间的大部分，因为它们的延迟非常高。由于循环依赖性，div/idiv指令无法并行执行。但是，a比a 低的延迟使得前者更快。dividiv

请注意，两种实现的性能可能因一种架构而异（因为 CPU 端口的数量、分支预测能力和idiv指令的延迟/吞吐量）。事实上，例如，一条 64 位idiv指令的延迟在 Skylake 上需要 41-95 个周期，而在 AMD Ryzen 处理器上需要 8-41 个周期。div在 Skylake 上，a 的延迟分别约为 6-89 个周期，在 Ryzen 上仍然相同。这意味着基准性能结果在 Ryzen 处理器上应该有显着差异（由于 128 位情况下的额外指令/分支成本，可能会看到相反的效果）。

Answer 2

TL:DR：__int128除法辅助函数在内部最终执行无符号运算div reg64（在对正值和上半部分进行一些分支之后0）。64 位div在 Intel CPU 上比idiv reg64GCC 内联的 Signed更快long long。快到足以弥补辅助函数的所有额外开销，以及其他操作的扩展精度。

您可能不会在 AMD CPU 上看到这种影响：long long会比预期的更快，因为idiv r64在性能上与div r64那里足够相似。

而且unsigned long long快于unsigned __int128在3.9GHz甚至在英特尔CPU，例如在我的i7-6700k（SKYLAKE微架构）（下运行perf stat在测试过程中，以确保CPU的频率）：

• 2097 (i128) 与 2332 (i64) - 您的原始测试（连续运行 CPU 频率预热）
• 2075 (u128) 与 1900 (u64) - 未签名版本。u128 分区与 i128 的分支略少，但 i64 与 u64 的主要区别在于，唯一的区别是div与idiv.

此外，从像这样的非常具体的微基准中得出任何一般性结论都是一个坏主意。有趣的是，深入研究为什么扩展精度__int128类型在这个除法基准测试中设法更快，正数小到足以容纳 32 位整数。

您的基准是沉重朝师，你每次迭代（做两次加权/和%），即使它远高于其他业务更昂贵和更少用到最代码。（例如，对整个数组求和然后除以一次以获得平均值。）

您的基准测试也没有指令级并行性：每个步骤都依赖于前一步的数据。这可以防止自动矢量化或任何会显示较窄类型的一些优点的东西。

（在 CPU 达到最大 turbo 之前，避免第一个定时区域变慢等预热效果也很不小心。 性能评估的惯用方法？。但是这比定时区域的几秒钟要快得多，所以这就是这里不是问题。）

128 位整数除法（特别是有符号的）对于 GCC 来说太复杂了，无法内联，因此 gcc 发出对辅助函数的调用，__divti3或者__modti3. （TI = tetra-integer，GCC 的内部名称是一个整数的 4 倍int。）这些函数在GCC-internals 手册中有记录。

你可以在上面看到编译器生成的 asm 在 Godbolt compiler-explorer。即带有 add/adc 的 128 位加法，与mul低半部分的一个完整乘法的乘法，以及imul交叉乘积的2 倍非加宽。是的，这些比int64_t.

但是 Godbolt 没有向您展示 libgcc 辅助函数的 asm。即使在“编译为二进制”和反汇编模式下（而不是通常的编译器 asm 文本输出），它也不会反汇编它们，因为它动态链接 libgcc_s 而不是libgcc.a.

扩展精度有符号除法是通过在必要时取反和对 64 位块进行无符号除法来完成的，然后在必要时修正结果的符号。

由于输入既小又正，就不需要实际的否定（只是测试和分支）。 对于小数（高半除数 = 0，商将适合 64 位）也有快速路径，这里就是这种情况。 最终结果是执行路径__divti3如下所示：

这是在我的 Arch GNU/Linux 系统上使用 gcc-libs 10.1.0-2__divti3编译后，手动单g++ -g -O3 int128-bench.cpp -o int128-bench.O3步调用 gdb。

# Inputs: dividend = RSI:RDI, divisor = RCX:RDX
# returns signed quotient RDX:RAX
|  >0x7ffff7c4fd40 <__divti3>       endbr64             # in case caller was using CFE (control-flow enforcement), apparently this instruction has to pollute all library functions now.  I assume it's cheap at least in the no-CFE case.
?   0x7ffff7c4fd44 <__divti3+4>     push   r12
?   0x7ffff7c4fd46 <__divti3+6>     mov    r11,rdi
?   0x7ffff7c4fd49 <__divti3+9>     mov    rax,rdx                                                                                                       ?   0x7ffff7c4fd4c <__divti3+12>    xor    edi,edi
?   0x7ffff7c4fd4e <__divti3+14>    push   rbx
?   0x7ffff7c4fd4f <__divti3+15>    mov    rdx,rcx
?   0x7ffff7c4fd52 <__divti3+18>    test   rsi,rsi      # check sign bit of dividend (and jump over a negation)
?   0x7ffff7c4fd55 <__divti3+21>    jns    0x7ffff7c4fd6e <__divti3+46>
... taken branch to
|  >0x7ffff7c4fd6e <__divti3+46>    mov    r10,rdx
?   0x7ffff7c4fd71 <__divti3+49>    test   rdx,rdx      # check sign bit of divisor (and jump over a negation), note there was a mov rdx,rcx earlier
?   0x7ffff7c4fd74 <__divti3+52>    jns    0x7ffff7c4fd86 <__divti3+70>
... taken branch to
?  >0x7ffff7c4fd86 <__divti3+70>    mov    r9,rax
?   0x7ffff7c4fd89 <__divti3+73>    mov    r8,r11
?   0x7ffff7c4fd8c <__divti3+76>    test   r10,r10      # check high half of abs(divisor) for being non-zero
?   0x7ffff7c4fd8f <__divti3+79>    jne    0x7ffff7c4fdb0 <__divti3+112>  # falls through: small-number fast path
?   0x7ffff7c4fd91 <__divti3+81>    cmp    rax,rsi      # check that quotient will fit in 64 bits so 128b/64b single div won't fault: jump if (divisor <= high half of dividend)
?   0x7ffff7c4fd94 <__divti3+84>    jbe    0x7ffff7c4fe00 <__divti3+192>  # falls through: small-number fast path
?   0x7ffff7c4fd96 <__divti3+86>    mov    rdx,rsi
?   0x7ffff7c4fd99 <__divti3+89>    mov    rax,r11
?   0x7ffff7c4fd9c <__divti3+92>    xor    esi,esi
?  >0x7ffff7c4fd9e <__divti3+94>    div    r9                #### Do the actual division ###
?   0x7ffff7c4fda1 <__divti3+97>    mov    rcx,rax
?   0x7ffff7c4fda4 <__divti3+100>   jmp    0x7ffff7c4fdb9 <__divti3+121>
...taken branch to
?  >0x7ffff7c4fdb9 <__divti3+121>   mov    rax,rcx
?   0x7ffff7c4fdbc <__divti3+124>   mov    rdx,rsi
?   0x7ffff7c4fdbf <__divti3+127>   test   rdi,rdi     # check if the result should be negative
?   0x7ffff7c4fdc2 <__divti3+130>   je     0x7ffff7c4fdce <__divti3+142>
... taken branch over a neg rax / adc rax,0 / neg rdx
?  >0x7ffff7c4fdce <__divti3+142>   pop    rbx
?   0x7ffff7c4fdcf <__divti3+143>   pop    r12
?   0x7ffff7c4fdd1 <__divti3+145>   ret
... return back to the loop body that called it

Intel CPU（自 IvyBridge 起）具有零延迟mov，因此所有这些开销不会显着恶化关键路径延迟（这是您的瓶颈）。或者至少不足以弥补idiv和div。

分支由分支预测和推测执行处理，仅在实际输入寄存器值相同时才检查预测。分支每次都以相同的方式进行，因此分支预测的学习是微不足道的。由于除法太慢，乱序执行者有足够的时间来追赶。

64 位操作数大小的整数除法在 Intel CPU 上非常慢，即使数字实际上很小并且适合 32 位整数，并且用于有符号整数除法的额外微码甚至更加昂贵。

例如在我的 Skylake (i7-6700k) 上，https ://uops.info/显示（表格搜索结果）

• idiv r64前端为 56 uop，延迟为 41 到 95 个周期（从除数到商，我认为这是相关情况）。
• div r64前端为 33 uop，延迟为 35 到 87 个周期。（对于相同的延迟路径）。

延迟最好的情况发生在小商数或小红利之类的情况下，我永远不记得是哪个。

类似于 GCC 在软件中对 64 位进行 128 位除法的分支，我认为 CPU 微码在更窄的操作方面在内部进行 64 位除法，可能是 32 位只有 10 uop 的签名或未签名，延迟要低得多。（Ice Lake 改进了除法器，因此 64 位除法并不比 32 位慢多少。）

这就是为什么您发现long long比此基准测试慢得多int的原因。在很多情况下，如果涉及内存带宽或 SIMD，它的速度大致相同，或者速度减半。（每 128 位向量宽度只有 2 个元素，而不是 4 个）。

AMD CPU 更有效地处理 64 位操作数大小，性能仅取决于实际值，因此对于具有相同数字的 div r32 与 div r64 大致相同。

顺便说一句，实际值往往类似于a=1814246614 / b=1814246613= 1，然后a=1 % b=1814246612（b每次迭代减少 1）。 只用 quotient=1 测试除法似乎很愚蠢。 （第一次迭代可能会有所不同，但我们会在第二次及以后进入这种状态。）

除除法以外的整数运算的性能不依赖于现代 CPU 的数据。（当然除非有编译时时常量允许发出不同的 asm。像在编译时计算乘法逆时，用常量除法会便宜得多。）

回复：：double请参阅浮点除法与浮点乘法的除法与乘法。FP 除法通常更难避免，它的性能在更多情况下是相关的，因此处理得更好。

有关的：

• 试除代码在 Windows 上的运行速度是 32 位的 2 倍，比 Linux上的64 位有一个特定的例子，div r64它div r32在使用足够小的数字的程序中更改为，并且看到吞吐量提高了大约 3 倍。
• 在某些情况下，128 位/64 位硬件无符号除法能否比 x86-64 Intel/AMD CPU 上的 64 位/32 位除法更快？有一些关于 div 和 idiv 被微编码的细节。
• GCC 的 sqrt() 编译后如何工作？使用哪种root方法？牛顿-拉夫森？有一些关于 div/sqrt 执行单元一般是如何设计的以及在较旧的 Intel CPU 中如何设计的硬件细节。但这并不能解释为什么 64 位比 32 位的 uop 多得多；我只是推断在 Ice Lake 之前硬件必须更窄，因为它需要更多的微码。