c++ - 分支预测优化

Question

我想了解 gcc/clang 对这段代码做了什么样的神奇优化。

#include <random>
#include <iostream>

int main()
{
    std::random_device rd;
    std::mt19937 mt(rd());
    const unsigned arraySize = 100000;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = mt() % 256;

    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }
    std::cout << sum << std::endl;
}

和这段代码

#include <random>
#include <iostream>
#include <algorithm>
int main()
{
    std::random_device rd;
    std::mt19937 mt(rd());
    const unsigned arraySize = 100000;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = mt() % 256;

    std::sort(data, data + arraySize);
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }
    std::cout << sum << std::endl;
}

基本上，当我大约 3 年前编译并运行它时，由于更好的分支预测，第二个代码快了 4 倍。我现在编译运行，几乎是同时运行的，不知道gcc/clang有什么魔力。

Answer 1

这是 gcc 的输出(使用 gcc.godbolt.org，带 -O3)

.L4: //Inner loop
    movslq  (%rax), %rdx
    movq    %rdx, %rcx
    addq    %rsi, %rdx
    cmpl    $127, %ecx
    cmovg   %rdx, %rsi
    addq    $4, %rax
    cmpq    %rdi, %rax
    jne .L4

您可以看到它进行了比较“cmpl $127,$ecx”，但是在比较之后它并没有分支。相反，它总是添加(在比较上方的行中使用“addq”)，然后根据比较使用添加的结果(感谢“cmovg”“条件移动”指令)。

它避免了内部循环中的分支，因此性能不依赖于分支预测。因此，对输入进行排序没有任何区别(就像您在第二个示例中所做的那样)。