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

Question

这是一段C ++代码，显示了一些非常特殊的行为。由于某些奇怪的原因，奇迹般地对数据进行排序使代码快了将近六倍：

#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)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

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

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

• 不使用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)
        {
            // Primary loop
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

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

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

我首先想到的是排序将数据带入缓存，但是后来我想到这是多么愚蠢，因为刚刚生成了数组。

• 到底是怎么回事？
• 为什么处理排序数组比处理未排序数组快？
• 该代码总结了一些独立的术语，因此顺序无关紧要。

Answer 1

您是分支预测失败的受害者。

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

该图显示了铁路枢纽 Mecanismo的图片，通过Wikimedia Commons。在CC-By-SA 3.0许可下使用。

现在，为了争论起见，假设这是在1800年代-在进行长距离或无线电通信之前。

您是路口的操作员，并且听到火车驶入。您不知道应该走哪条路。您停下火车，询问驾驶员他们想要哪个方向。然后您适当地设置开关。

火车很重，惯性很大。因此，它们花了永远的时间来启动和减速。

有没有更好的办法？您猜火车将朝哪个方向行驶！

• 如果您猜对了，它将继续进行。
• 如果您猜错了，机长会停下来，后退并大喊大叫，以拨动开关。然后，它可以沿着其他路径重新启动。
• 如果您每次都猜对了，火车将永远不会停止。
• 如果您经常猜错，火车将花费大量时间停止，备份和重新启动。

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

包含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, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   (completely random - hard 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版本

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java-NetBeans 7.1.1 JDK 7-x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

观察结果：

• 使用分支：排序和未排序的数据之间存在巨大差异。
• 使用Hack：排序和未排序的数据之间没有区别。
• 在C ++情况下，对数据进行排序时，hack实际上比分支慢一点。
  一般的经验法则是避免在关键循环中避免依赖数据的分支（例如在此示例中）。
  

更新：

• x64上-O3或-ftree-vectorizex64上的GCC 4.6.1能够产生条件移动。因此，已排序和未排序的数据之间没有区别-两者都很快速。

（或者有点快：对于已经排序的情况，cmov可能会变慢，特别是如果GCC将其放在关键路径上而不是仅仅在add，尤其是在Broadwell之前cmov有2个周期延迟的Intel上：gcc优化标志-O3会使代码比-O2慢）

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

• 英特尔C 编译器（ICC）11起到了神奇的作用。它互换两个循环，从而将不可预测的分支提升到外部循环。因此，它不仅可以避免错误预测，而且还比VC 和GCC生成的速度快两倍！换句话说，ICC利用测试循环击败了基准测试…

• 如果给Intel编译器提供无分支的代码，它就直接对其进行矢量化处理……并且与分支（通过循环交换）一样快。