c++ - 分支预测仍然可以显着加快数组处理速度吗？

Question

我正在阅读一篇关于 why is it faster to process a sorted array than an unsorted array? 的有趣文章并看到@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 代码作为示例。这是一个可怕的错误。该代码不仅是错误的，而且发布它还误导了那些关注代码本身而不是问题的人。

• 当我第一次尝试上面链接中使用的 C++ 代码时，只有 2% 的差异(1.9 秒和 1.85 秒)。

• 我的第一个问题和意图是关于上一篇文章、其 C++ 代码和 @mp31415 的评论。

• @rustyx 发表了一条有趣的评论，我想知道它是否可以解释我所观察到的情况。

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

换句话说，我的问题是:

• 为什么上一篇文章中的 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;
}

现在这个版本再次展现出排序/未排序数据之间的巨大差异。在我的系统 (i7-7700) 上，1.6 秒 vs 11 秒(或 700%)。

结论:当我们面临前所未有的管道深度和指令级并行性时，分支预测器比以往任何时候都更加重要。