java - 为什么处理排序数组比处理未排序数组更快？

Question

这是一段 C++ 代码，显示了一些非常奇特的行为。出于某种奇怪的原因，对数据进行排序(在定时区域之前)奇迹般地使循环快了近 6 倍。

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

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

    // !!! With this, the next loop runs faster.
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;
    for (unsigned i = 0; i < 100000; ++i)
    {
        for (unsigned c = 0; c < arraySize; ++c)
        {   // Primary loop
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock()-start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << '\n';
    std::cout << "sum = " << sum << '\n';
}

无 std::sort(data, data + arraySize); ，代码运行时间为 11.54 秒。

使用排序后的数据，代码运行时间为 1.93 秒。

(排序本身比遍历数组需要更多的时间，因此如果我们需要为未知数组计算它实际上不值得这样做。)

最初，我认为这可能只是一种语言或编译器异常，所以我尝试了 Java:

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;
        for (int i = 0; i < 100000; ++i)
        {
            for (int c = 0; c < arraySize; ++c)
            {   // Primary loop
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

具有类似但不那么极端的结果。

我的第一个想法是排序将数据带入 cache ，但后来我认为这是多么愚蠢，因为数组刚刚生成。

到底是怎么回事？

为什么处理排序数组比处理未排序数组更快？

代码总结了一些独立的术语，所以顺序应该无关紧要。

相关/后续问答 不同/更高版本的编译器和选项的效果大致相同:

Why is processing an unsorted array the same speed as processing a sorted array with modern x86-64 clang?

gcc optimization flag -O3 makes code slower than -O2

Answer 1

你是 branch prediction 失败的受害者。

什么是分支预测？
考虑一个铁路枢纽:

Image 来自 Mecanismo，来自 Wikimedia Commons。在 CC-By-SA 3.0 许可下使用。
现在为了争论，假设这是在 1800 年代 - 在长途或 radio 通信之前。
你是一个路口的运算符(operator)，你听到一列火车驶来。你不知道它应该走哪条路。你停下火车问司机他们想要哪个方向。然后你适本地设置开关。
火车很重，惯性很大，所以它们需要很长时间才能启动和减速。
有没有更好的办法？你猜火车会往哪个方向走!

如果你猜对了，它会继续。

如果你猜错了，船长会停下来，后退，并大喊你拨动开关。然后它可以从另一条路径重新启动。

如果你每次都猜对了 ，火车将永远不必停下来。
如果你经常猜错 ，火车会花很多时间 parking 、备份和重新启动。

考虑一个 if 语句: 在处理器层面，它是一条分支指令:

你是一个处理器，你看到一个分支。你不知道它会走哪条路。你做什么工作？您停止执行并等待前面的指令完成。然后你继续沿着正确的路径前进。
现代处理器很复杂并且有很长的管道。这意味着他们需要永远“热身”和“减速”。
有没有更好的办法？你猜分支会往哪个方向走!

如果你猜对了，你继续执行。

如果你猜错了，你需要刷新管道并回滚到分支。然后你可以从另一条路径重新开始。

如果您每次都猜对 ，则执行将永远不必停止。
如果您经常猜错 ，您将花费大量时间停止、回滚和重新启动。

这就是分支预测。我承认这不是最好的类比，因为火车只能用旗子指示方向。但是在计算机中，处理器直到最后一刻才知道一个分支将走向哪个方向。
您将如何战略性地猜测以最小化火车必须倒退并沿另一条路径行驶的次数？你看看过去的历史!如果火车 99% 的时间都向左行驶，那么您猜是向左行驶。如果它交替，那么你改变你的猜测。如果它每三遍一次，你猜也是一样的......
换句话说，您尝试识别一种模式并遵循它。 这或多或少是分支预测器的工作方式。
大多数应用程序都有行为良好的分支。因此，现代分支预测器通常会达到 >90% 的命中率。但是当面对没有可识别模式的不可预测的分支时，分支预测器实际上是无用的。
进一步阅读: "Branch predictor" article on Wikipedia 。

正如上面所暗示的，罪魁祸首是这个 if 语句:

if (data[c] >= 128)
    sum += data[c];

注意数据在0到255之间是均匀分布的。当数据排序后，大概前半部分的迭代不会进入if语句。之后，他们都会进入if语句。
这对分支预测器非常友好，因为分支连续多次沿同一方向前进。即使是一个简单的饱和计数器也能正确预测分支，除了它切换方向后的几次迭代。
快速可视化:

T = branch taken
N = branch not taken

data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...

       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)

但是，当数据完全随机时，分支预测器就变得无用了，因为它无法预测随机数据。因此可能会有大约 50% 的错误预测(不比随机猜测好)。

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T  ...

       = TTNTTTTNTNNTTT ...   (completely random - impossible to predict)

可以做什么？
如果编译器无法将分支优化为有条件的移动，如果您愿意为了性能而牺牲可读性，您可以尝试一些技巧。
代替:

if (data[c] >= 128)
    sum += data[c];

和:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

这消除了分支并用一些按位运算替换它。
(请注意，此 hack 并不严格等同于原始 if 语句。但在这种情况下，它对 data[] 的所有输入值都有效。)
基准:Core i7 920 @ 3.5 GHz
C++ - Visual Studio 2010 - x64 版本


设想
时间(秒)


分支 - 随机数据
11.777

分支 - 排序数据
2.352

无分支 - 随机数据
2.564

Branchless - 排序数据
2.587


Java - NetBeans 7.1.1 JDK 7 - x64


设想
时间(秒)


分支 - 随机数据
10.93293813

分支 - 排序数据
5.643797077

无分支 - 随机数据
3.113581453

Branchless - 排序数据
3.186068823


观察:

与分支: 排序和未排序的数据之间存在巨大差异。

使用 Hack: 已排序和未排序数据之间没有区别。

在 C++ 的情况下，当数据被排序时，hack 实际上比分支慢一点。

一般的经验法则是避免关键循环中的数据相关分支(例如在本例中)。

更新:

GCC 4.6.1 with -O3 or -ftree-vectorize on x64 能够生成条件移动，因此排序和未排序数据之间没有区别 - 两者都很快。
(或者有点快:对于已经排序的情况， cmov 可能会更慢，特别是如果 GCC 将它放在关键路径上而不是 add ，尤其是在 Broadwell 之前的 Intel 上，其中 cmov 有 2 个周期延迟:gcc optimization flag -O3 makes code slower than -O2 )

VC++ 2010 即使在 /Ox 下也无法为此分支生成条件移动。

Intel C++ Compiler (ICC) 11 做了一些神奇的事情。它 interchanges the two loops ，从而将不可预测的分支提升到外循环。它不仅不受错误预测的影响，而且速度是 VC++ 和 GCC 生成的速度的两倍!换句话说，ICC 利用测试循环来击败基准测试......

如果您给英特尔编译器提供无分支代码，它会直接将其矢量化……并且与分支(使用循环交换)一样快。

这表明即使是成熟的现代编译器在优化代码的能力方面也会有很大差异......