网友问题：
下面是一段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)
    {
        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';
}

• 如果没有 ，代码将在 11.54 秒内运行。std::sort(data, data + arraySize);
• 使用排序后的数据，代码在 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);
    }
}

结果相似但不那么极端。

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

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

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

相关/后续问答与不同/后来的编译器和选项具有相同的效果：

• 为什么处理未排序数组的速度与使用现代 x86-64 clang 处理排序数组的速度相同？
• gcc 优化标志 -O3 使代码比 -O2 慢

网友回答：

分支预测。

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

网友回答：

当数据被排序时，性能大幅提高的原因是删除了分支预测惩罚，正如Mysticial的答案中所解释的那样。

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

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

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

因此，在 中，直接（无需任何优化）编译成条件移动指令的语句是三元运算符。因此，我们将上述语句重写为等效语句：CC++x86... ? ... : ...

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

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

在英特尔酷睿 i7-2600K @ 3.4 GHz 和 Visual Studio 2010 发布模式下，基准测试为：

x86

x64

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

现在，让我们通过调查它们生成的程序集来更仔细地查看。为简单起见，我们使用两个函数和.x86max1max2

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由于使用了指令，使用的代码要少得多。但真正的收益是，这不涉及分支跳跃，如果预测结果不正确，这将对性能造成重大损失。cmovgemax2jmp

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

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

在分支情况下，以下指令由前一条指令确定，因此我们无法进行流水线处理。我们必须等待或预测。

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

《计算机系统：程序员的视角》（Computer Systems： A Programmer’s Perspective， Second Edition）一书对此进行了详细的解释。您可以查看第 3.6.6 节以了解条件移动指令，查看整个第 4 章以了解处理器体系结构，以及第 5.11.2 节以了解分支预测和错误预测处罚的特殊处理。

有时，一些现代编译器可以优化我们的代码以具有更好的性能进行汇编，有时一些编译器不能（有问题的代码使用的是Visual Studio的本机编译器）。了解不可预测时分支和条件移动之间的性能差异可以帮助我们在场景变得如此复杂以至于编译器无法自动优化它们时编写具有更好性能的代码。

网友回答：

You are a victim of branch prediction fail.

What is Branch Prediction?

考虑一个铁路枢纽：

_{图片由Mecanismo提供，通过维基共享资源。在 CC-By-SA 3.0 许可证下使用。}

现在为了论证，假设这可以追溯到 1800 年代——在长途或无线电通信之前。

你是一个路口的盲人操作员，你听到一列火车来了。你不知道它应该走哪条路。你停下火车，问司机他们想要哪个方向。然后适当地设置开关。

火车很重，惯性很大，所以它们需要很长时间才能启动和减速。

有没有更好的方法？你猜火车会朝哪个方向走！

• 如果你猜对了，它将继续下去。
• 如果你猜错了，船长会停下来，后退，对你大喊大叫，让你拨动开关。然后它可以沿着另一条路径重新启动。

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

考虑一个 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[] 的所有输入值都有效。}

基准测试：酷睿i7 920 @ 3.5 GHz

C++ – Visual Studio 2010 – x64 发布

Java – NetBeans 7.1.1 JDK 7 – x64

观察：

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

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

更新：

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

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

• VC++ 2010 无法为此分支生成条件移动，即使在 下也是如此。/Ox
• 英特尔C++编译器 （ICC） 11 创造了奇迹。它互换两个回路，从而将不可预测的分支吊到外环路。它不仅不受错误预测的影响，而且速度是VC++和GCC可以生成的两倍！换句话说，ICC利用测试循环来击败基准……
• 如果您为英特尔编译器提供无分支代码，它只会直接对其进行矢量化…并且与分支（使用循环交换）一样快。

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