c++ - 为什么 __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

性能差异来自 128 位除法/模的效率 使用 GCC/Clang 在这种特殊情况下 .
事实上，在我的系统以及 godbolt 上, sizeof(long long) = 8和 sizeof(__int128_t) = 16 .因此，前者的操作由 native 指令执行，而后者则不是(因为我们专注于 64 位平台)。加法、乘法和减法使用 __int128_t 较慢.但是，用于 16 字节类型(在 x86 GCC/Clang 上的 __divti3 和 __modti3)上的除法/模数的内置函数比原生 idiv 快得多指令(这很慢，至少在英特尔处理器上)。
如果我们深入查看 GCC/Clang 内置函数的实现(此处仅用于 __int128_t)，我们可以看到 __modti3 使用条件(当调用 __udivmodti4 时)。 英特尔处理器 可以更快地执行代码，因为:

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

除法/模数被拆分为更快的 native 指令，这些指令主要可以由多个 CPU 端口并行执行(并且受益于乱序执行)。一个 div在大多数可能的路径中仍然使用指令(特别是在这种情况下)；

div的执行时间/idiv指令涵盖了大部分整体执行时间，因为它们非常高延迟 . div/idiv由于 ，指令无法并行执行循环依赖 .但是，div 的延迟低于idiv使前者更快。

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