为什么在x86-64 GCC上，_uint128\u t比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和双都明显快于long long；long long已成为最慢的类型。

这是怎么发生的？

Answer 1

TL:DR:uu int128除法辅助函数在内部执行无符号的div reg64（在值为正且上半部分为0的一些分支之后）。在英特尔CPU上，64位div比GCC内联的带符号idiv reg64更快。更快，足以弥补辅助函数的所有额外开销，并扩展其他操作的精度。

您可能不会在AMD CPU上看到这种效果：long-long会像预期的那样更快，因为idiv r64在性能上与div r64相当。

即使在Intel CPU上，例如在3.9GHz的i7-6700k（Skylake）上，无符号长长也比无符号int128快（在性能统计下运行，以确保测试期间的CPU频率）：

• 2097（i128）与2332（i64）-您的原始测试（背靠背运行以进行CPU频率预热）

此外，从这样一个非常具体的微观基准中得出任何一般性结论都是一个坏主意。然而，有趣的是，深入了解为什么扩展精度int128类型在这个除法基准中能够更快，因为正数小到足以容纳32位整数。

您的基准测试非常偏重于除法，您每次迭代执行两次（/和%），尽管它比其他操作贵得多，并且在大多数代码中使用的频率要低得多。（例如，求和整个数组，然后除法一次以获得平均值。）

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

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

128位整数除法（特别是有符号除法）对于GCC来说太复杂，无法内联，因此GCC发出对辅助函数的调用，\uu divti3或\uu modti3。（TI=tetra integer，GCC的内部名称，表示大小为int的4倍的整数）这些功能记录在GCC内部手册中。

即128位加法与add/adc，乘法与1mul低半部的全乘，以及2倍非加宽的imul的交叉乘积。是的，这些比int64_t的单指令等价物慢。

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

扩展精度有符号除法是通过在必要时求反和对64位块进行无符号除法来实现的，然后在必要时固定结果的符号。

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

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

# 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以来）的延迟为零，因此所有这些开销不会显著恶化关键路径延迟（这是您的瓶颈）。或者至少不足以弥补idiv和div之间的差异。

分支通过分支预测和推测执行来处理，仅在实际输入寄存器值相同的情况下检查事后预测。分支每次都以相同的方式进行，因此分支预测学习起来很简单。由于分工如此缓慢，有足够的时间让无序的执行官迎头赶上。

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

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

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

延迟最好的情况发生在小商数或小股息或其他东西，我永远不记得是哪一个。

类似于GCC在软件中对64位的128位划分所做的分支，我认为CPU微码在内部对更窄的操作进行64位划分，可能是32位，对于有符号或无符号只有10 uops，延迟要低得多。（冰湖改进了分频器，因此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）。只有用商=1来测试除法似乎很愚蠢。（第一次迭代可能不同，但我们在第二次及以后的迭代中会进入这种状态。）

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

关于：关于除法与乘法，请参阅浮点除法与浮点乘法。FP部门通常更难避免，其性能与更多情况相关，因此处理得更好。

相关：

• 试用划分代码在Windows上运行32位比64位快2倍Linux有一个在使用足够小的数字的程序中将div r64更改为div r32的具体示例，并看到吞吐量提高了约3倍。
• 在某些情况下，128bit/64bit硬件无符号划分是否比x86-64 Intel/AMD CPU上的64bit/32bit划分更快？有一些关于div和idiv被微码的细节。
• 编译后GCC的sqrt（）是如何工作的？使用哪种root方法？Newton-Raphson？有一些硬件细节，说明div/sqrt执行单元通常是如何设计的，以及在较旧的Intel CPU中。但这并不能解释为什么64位比32位多这么多uops；我只是推断硬件在冰湖之前一定更窄，因为它需要更多uops的微码。

Answer 2

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

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

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

• 在这种情况下，可以很好地预测执行的分支，因为它们总是相同的（也因为循环执行了数百万次）

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