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

小编典典

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

javascript

这是一段 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);
    }
}

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

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

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

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

阅读 251

2021-12-29

共4个答案

小编典典

对于排序数组，条件data[c] >= 128首先false是连续值，然后true是所有后续值。这很容易预测。对于未排序的数组，您需要支付分支成本。

2021-12-29

小编典典

什么是分支预测？

考虑一个铁路枢纽：

图片来自 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, ...
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[]。）

基准：酷睿 i7 920 @ 3.5 GHz

C++ - Visual Studio 2010 - x64 版本

设想	时间（秒）
分支 - 随机数据	11.777
分支 - 排序数据	2.352
无分支 - 随机数据	2.564
无分支 - 排序数据	2.587

Java - NetBeans 7.1.1 JDK 7 - x64

设想	时间（秒）
分支 - 随机数据	10.93293813
分支 - 排序数据	5.643797077
无分支 - 随机数据	3.113581453
无分支 - 排序数据	3.186068823

观察：

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

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

更新：

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

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

即使在/Ox.
英特尔 C++ 编译器(ICC) 11 做了一些神奇的事情。它交换了两个循环，从而将不可预测的分支提升到外循环。它不仅不受错误预测的影响，而且速度是 VC++ 和 GCC 生成的速度的两倍！换句话说，ICC 利用测试循环来击败基准测试......
如果您为英特尔编译器提供无分支代码，它会直接将其矢量化……并且与分支（使用循环交换）一样快。

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

2021-12-29

小编典典

对数据进行排序时性能显着提高的原因是删除了分支预测惩罚，正如Mysticial 的回答中所解释的那样。

现在，如果我们看一下代码

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

我们可以发现这个特定if... else...分支的含义是在满足条件时添加一些东西。这种类型的分支可以很容易地转换为条件移动语句，该语句将被编译为条件移动指令：cmovl, 在x86系统中。分支以及潜在的分支预测惩罚被移除。

在C，因此C++，语句，这将直接编译（不使用任何优化）插入在条件移动指令x86，是三元运算符... ? ... : ...。所以我们把上面的语句改写成等价的：

sum += data[c] >=128 ? data[c] : 0;

在保持可读性的同时，我们可以检查加速因子。

在 Intel Core i7 -2600K @ 3.4 GHz 和 Visual Studio 2010 发布模式上，基准是：

x86

设想	时间（秒）
分支 - 随机数据	8.885
分支 - 排序数据	1.528
无分支 - 随机数据	3.716
无分支 - 排序数据	3.71

x64

设想	时间（秒）
分支 - 随机数据	11.302
分支 - 排序数据	1.830
无分支 - 随机数据	2.736
无分支 - 排序数据	2.737

结果在多个测试中是稳健的。当分支结果不可预测时，我们获得了很大的加速，但当它是可预测的时，我们会受到一点影响。事实上，当使用条件移动时，无论数据模式如何，性能都是相同的。

现在让我们通过研究x86它们生成的程序集来更仔细地观察。为简单起见，我们使用两个函数max1和max2。

max1使用条件分支if... else ...：

int max1(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

max2使用三元运算符... ? ... : ...：

int max2(int a, int b) {
    return a > b ? a : b;
}

在 x86-64 机器上，GCC -S生成下面的程序集。

:max1
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    -8(%rbp), %eax
    jle     .L2
    movl    -4(%rbp), %eax
    movl    %eax, -12(%rbp)
    jmp     .L4
.L2:
    movl    -8(%rbp), %eax
    movl    %eax, -12(%rbp)
.L4:
    movl    -12(%rbp), %eax
    leave
    ret

:max2
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    %eax, -8(%rbp)
    cmovge  -8(%rbp), %eax
    leave
    ret

max2由于指令的使用，使用的代码要少得多cmovge。但真正的好处是max2不涉及分支跳转，jmp如果预测结果不正确，这将导致显着的性能损失。

那么为什么有条件的移动表现更好呢？

在典型的x86处理器中，一条指令的执行分为几个阶段。粗略地说，我们有不同的硬件来处理不同的阶段。因此，我们不必等待一条指令完成即可开始新的一条指令。这称为流水线。

在分支情况下，后面的指令是由前面的指令决定的，所以我们不能做流水线。我们要么等待，要么预测。

在条件移动的情况下，执行的条件移动指令分为几个阶段，但前面的阶段喜欢Fetch并且Decode不依赖于前一条指令的结果；只有后期需要结果。因此，我们等待了一条指令执行时间的一小部分。这就是为什么在预测容易时，条件移动版本比分支慢的原因。

2021-12-29

小编典典

如果您对可以对此代码进行的更多优化感到好奇，请考虑：

从原始循环开始：

for (unsigned i = 0; i < 100000; ++i)
{
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

通过循环交换，我们可以安全地将此循环更改为：

for (unsigned j = 0; j < arraySize; ++j)
{
    for (unsigned i = 0; i < 100000; ++i)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

然后，您可以看到在if整个i循环执行过程中条件是恒定的，因此您可以提升if输出：

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            sum += data[j];
        }
    }
}

然后，您会看到内部循环可以折叠为一个表达式，假设浮点模型允许（/fp:fast例如，抛出）

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}

那个比以前快100,000倍。

2021-12-29