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

在此 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);
    }
}

结果类似，但不那么极端。

我的第一个想法是排序将数据带入缓存，但这很愚蠢，因为数组刚刚生成。

• 到底是怎么回事？
• 为什么处理排序数组比处理未排序数组更快？

该代码正在总结一些独立的术语，因此顺序并不重要。

现在为了论证的目的，假设这是在 19 世纪 - 长距离或无线电通信之前。

你是一个盲人，在路口操作，你听到火车驶来。你不知道火车应该往哪个方向开。你停下火车，问司机他们要往哪个方向开。然后你把道岔调到合适的位置。

火车很重，而且惯性很大，所以启动和减速需要很长时间。

有没有更好的办法？你猜火车会往哪个方向开！

• 如果你猜对了，它就会继续。
• 如果你猜错了，司机就会停车、倒车，并大喊让你扳动开关。然后它就可以沿着另一条路重新出发。

如果你每次都猜对了，火车就永远不会停下来。
如果你猜错的次数太多，火车就会花很多时间停下来、倒车、再重新启动。

考虑一个 if 语句：在处理器级别，它是一个分支指令：

你是一个处理器，你看到一个分支。你不知道它会朝哪个方向发展。你会怎么做？你暂停执行并等待前面的指令完成。然后你继续沿着正确的路径前进。

现代处理器非常复杂，流水线很长。这意味着它们需要很长时间才能“预热”和“减速”。

有没有更好的办法？你猜一下树枝会往哪个方向走！

• 如果猜对了，就继续执行。
• 如果猜错了，则需要刷新管道并回滚到分支。然后，您可以沿着另一条路径重新启动。

如果每次都猜对，执行就永远不会停止。
如果猜错次数太多，就会花费大量时间停滞、回滚和重新启动。

这就是分支预测。我承认这不是最好的类比，因为火车可以用旗帜来指示方向。但在计算机中，处理器直到最后一刻才知道分支会朝哪个方向走。

你会如何策略性地猜测，以尽量减少火车必须倒车并沿另一条路径行驶的次数？看看过去的历史！如果火车 99% 的时间都是向左行驶，那么你猜是向左行驶。如果它交替行驶，那么你交替猜测。如果它每三次都往一个方向行驶，你的猜测是一样的……

换句话说，你试图识别一种模式并遵循它。这或多或少就是分支预测器的工作原理。

大多数应用程序的分支都表现良好。因此，现代分支预测器通常可实现 90% 以上的命中率。但当面对不可预测且没有可识别模式的分支时，分支预测器几乎毫无用处。

正如上面暗示的那样，罪魁祸首就是这个 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];

这将消除分支并将其替换为一些按位运算。

（请注意，此技巧并不严格等同于原始的 if 语句。但在这种情况下，它对所有的输入值都有效data[]。）

基准测试：Core i7 920 @ 3.5 GHz

C++ - Visual Studio 2010 - x64 版本

Java-NetBeans 7.1.1 JDK 7-x64

观察结果：

• 与分支：排序后的数据和未排序的数据之间存在巨大差异。
• 使用 Hack：排序的数据和未排序的数据之间没有区别。
• 在 C++ 的情况下，当数据排序时，黑客实际上比分支慢一点。