分支预测是否仍在显着加快阵列处理速度？

Question

我正在阅读一篇有趣的文章，内容涉及为什么处理排序数组比未排序数组更快？并看到@ mp31415发表的评论说：

仅作记录。在Windows / VS2017 / i7-6700K 4GHz上，两个版本之间没有区别。两种情况都需要0.6s。如果外部循环中的迭代次数增加了10倍，则两种情况下的执行时间也会增加10倍，至6s

因此，我在一个在线c / c ++编译器（我想是现代服务器体系结构）上进行了尝试，得到的排序和未排序分别为〜1.9s和〜1.85s，没有太大区别，但可重复。

因此，我想知道现代建筑是否仍然适用？问题是从2012年开始的，距离现在不远...还是我错在哪里？

---

重新开启的问题精确度：

• 请忘记我添加C代码作为示例。这是一个可怕的错误。不仅代码是错误的，而且将代码发布误导了专注于代码本身而不是问题的人们。

• 当我第一次尝试上面链接中使用的C ++代码时，只有2％的差异（1.9s和1.85s）。

• 我的第一个问题和意图是关于上一篇文章，其c ++代码和@ mp31415的注释。

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

  有趣的是，调试版本在排序/未排序之间的差异为400％，而发布版本的差异最大为5％（i7-7700）。

换句话说，我的问题是：

• 为什么上一篇文章中的c ++代码不能像上一版OP所声称的那样具有良好的性能？

精确度：

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

Answer 1

您是常规规则的受害者：

...需要遵循的实现来（仅）模拟抽象机的可观察行为 ...

考虑被测功能...

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;
}

和生成的程序集（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.6s vs 11s（或700％）。

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