分支预测优化

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    7, %ecx
    cmovg   %rdx, %rsi
    addq    , %rax
    cmpq    %rdi, %rax
    jne .L4

你可以看到它进行了比较"cmpl 7,$ecx"，但是在比较之后它并没有分支。相反，它总是添加（在比较上方的行中使用 "addq"），然后根据比较使用添加的结果（感谢 "cmovg" "conditional move" 指令）。

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

分支预测优化

Branch prediction optimizations

c++

optimization

g++

branch

prediction