分支预测是否仍能显着加快数组处理速度？

Question

我正在阅读一篇关于 why is it faster to process a sorted array than an unsorted array? 的有趣 post 并且看到@mp31415 发表的评论说：

Just for the record. On Windows / VS2017 / i7-6700K 4GHz there is NO difference between two versions. It takes 0.6s for both cases. If number of iterations in the external loop is increased 10 times the execution time increases 10 times too to 6s in both cases

所以我在 online c/c++ compiler（我想是现代服务器架构）上试了一下，我得到，对于排序和未排序，分别是 ~1.9s 和 ~1.85s，差别不大但可重复。

所以我想知道现代建筑是否仍然如此？问题是从 2012 年开始的，离现在不远...... 或者我哪里错了？

重开题精度：

请忘记我添加 C 代码作为示例。这是一个 可怕的 错误。代码不仅是错误的，post它还误导了关注代码本身而不是问题的人。
当我首先尝试上面 link 中使用的 C++ 代码时，只有 2% 的差异（1.9s 和 1.85s）。
我的第一个问题和意图是关于之前的post，它的c++代码和@mp31415的评论。
@rustyx 发表了一个有趣的评论，我想知道它是否可以解释我观察到的情况。

Interestingly, a debug build exhibits 400% difference between sorted/unsorted, and a release build at most 5% difference (i7-7700).

换句话说，我的问题是：

为什么之前 post 中的 c++ 代码没有像之前 OP 声称的那样表现良好？

精确度：

发布版本和调试版本之间的时间差异可以解释吗？

Answer 1

您是 as-if rule 的受害者：

... conforming implementations are required to emulate (only) the observable behavior of the abstract machine ...

考虑被测函数...

const size_t arraySize = 32768;
int *data;

long long test()
{
    long long sum = 0;
    for (size_t i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (size_t c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }
    return sum;
}

和 generated assembly（VS 2017，x86_64 /O2 模式）

机器不执行你的循环，而是执行一个类似的程序来执行这个：

long long test()
{
    long long sum = 0;
    // Primary loop
    for (size_t c = 0; c < arraySize; ++c)
    {
        for (size_t i = 0; i < 20000; ++i)
        {
            if (data[c] >= 128)
                sum += data[c] * 5;
        }
    }
    return sum;
}

观察优化器如何颠倒循环顺序并击败您的基准。

显然后一个版本对分支预测器更友好。

你可以反过来通过在外循环中引入依赖来破坏循环提升优化：

long long test()
{
    long long sum = 0;
    for (size_t i = 0; i < 100000; ++i)
    {
        sum += data[sum % 15];  // <== dependency!
        // Primary loop
        for (size_t c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }
    return sum;
}

现在这个版本再次显示 sorted/unsorted 数据之间的巨大差异。在我的系统 (i7-7700) 上 1.6s 与 11s（或 700%）。

结论：如今，当我们面临前所未有的流水线深度和指令级并行性时，分支预测器比以往任何时候都重要。

分支预测是否仍能显着加快数组处理速度？

Is branch prediction still significantly speeding up array processing?

c

c++

performance

branch-prediction

重开题精度：