为什么处理排序数组比处理未排序数组更快？-Java 学习之路

22299

这是一段看似非常特殊的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);
    }
}

有点相似但不太极端的结果 .

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

发生了什么事？
为什么处理排序数组比未排序数组更快？
代码总结了一些独立的术语，顺序无关紧要 .

22 回答

3035

这是肯定的！...

Branch prediction 使逻辑运行速度变慢，因为代码中发生了切换！这就像你要走一条直街或一条有很多转弯的街道，肯定会直接做得更快！...

如果数组已排序，则第一步的条件为false： data[c] >= 128 ，然后变为整个街道末尾的真值 . 这就是你如何更快地完成逻辑的结束 . 另一方面，使用未排序的数组，您需要进行大量的转换和处理，这会使您的代码运行速度变慢...

看下面我为你创建的图像 . 哪条街要快点完成？

因此，以编程方式， branch prediction 会导致进程变慢...

最后，我们很高兴知道我们有两种分支预测，每种预测都会以不同的方式影响您的代码：

1. Static

2. Dynamic

第一次遇到条件分支时，微处理器使用静态分支预测，并且动态分支预测用于条件分支代码的后续执行 . 为了有效地编写代码以利用这些规则，在编写if-else或switch语句时，首先检查最常见的情况，然后逐步降低到最不常见的情况 . 循环不一定需要任何特殊的静态分支预测代码排序，因为通常只使用循环迭代器的条件 .

回复于 2024-04-25T13:30:59+08:00

909

在ARM上，不需要分支，因为每条指令都有一个4位条件字段，以零成本进行测试 . 这消除了对短分支的需要，并且不会出现分支预测 . 因此，由于排序的额外开销，排序版本将比ARM上的未排序版本运行得慢 . 内部循环看起来如下所示：

MOV R0, #0     // R0 = sum = 0
MOV R1, #0     // R1 = c = 0
ADR R2, data   // R2 = addr of data array (put this instruction outside outer loop)
.inner_loop    // Inner loop branch label
    LDRB R3, [R2, R1]     // R3 = data[c]
    CMP R3, #128          // compare R3 to 128
    ADDGE R0, R0, R3      // if R3 >= 128, then sum += data[c] -- no branch needed!
    ADD R1, R1, #1        // c++
    CMP R1, #arraySize    // compare c to arraySize
    BLT inner_loop        // Branch to inner_loop if c < arraySize

回复于 2024-04-25T13:30:59+08:00

609
当数据被排序时，性能大幅提升的原因是分支预测惩罚被删除，正如在Mysticial的答案中精美地解释的那样 .

现在，如果我们看一下代码
```
if (data[c] >= 128)
    sum += data[c];
```
我们可以发现这个特定的 if... else... 分支的含义是在条件满足时添加一些东西 . 这种类型的分支可以很容易地转换为 conditional move 语句，该语句将被编译为 x86 系统中的条件移动指令： cmovl . 分支以及因此潜在的分支预测惩罚被移除 .

在 C 中，因此 C++ ，将直接编译（没有任何优化）到 x86 中的条件移动指令的语句是三元运算符 ... ? ... : ... . 所以我们将上面的语句重写为等价的语句：
```
sum += data[c] >=128 ? data[c] : 0;
```
在保持可读性的同时，我们可以检查加速因子 .

在Intel Core i7 -2600K @ 3.4 GHz和Visual Studio 2010发布模式下，基准测试是（从Mysticial复制的格式）：

x86
```
//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71
```
x64
```
//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 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
```
由于使用了指令 cmovge ， max2 使用的代码少得多 . 但真正的好处是 max2 不涉及分支跳跃，如果预测结果不正确，则会产生显着的性能损失 .

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

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

在分支案例中，以下内容指令由前一个决定，所以我们不能做流水线操作 . 我们必须等待或预测 .

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

书Computer Systems: A Programmer's Perspective, second edition详细解释了这一点 . 您可以检查第3.6.6节有关条件移动指令，整个第4章用于处理器体系结构，第5.11.2节用于特殊处理分支预测和错误预测惩罚 .

有时，一些现代编译器可以优化我们的代码以便以更好的性能进行汇编，有时一些编译器不能（有问题的代码使用Visual Studio的本机编译器） . 在不可预测的情况下了解分支和条件移动之间的性能差异可以帮助我们在场景变得如此复杂以至于编译器无法自动优化它们时编写具有更好性能的代码 .
回复于 2024-04-25T13:30:59+08:00
0

Branch prediction.

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

回复于 2024-04-25T13:30:59+08:00
1201
在排序的情况下，您可以做得比依赖成功的分支预测或任何无分支比较技巧更好：完全删除分支 .

实际上，数组在 data < 128 的连续区域中划分，而 data >= 128 则划分为另一个 . 因此，您应该使用二分搜索找到分区点（使用 Lg(arraySize) = 15 比较），然后从该点直接累积 .

像（未选中）的东西
```
int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];
```
或者，稍微混淆一点
```
int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];
```
一种更快的方法，即为已排序或未排序的方法提供 approximate 解决方案： sum= 3137536; （假设真正均匀分布，16384个样本，预期值为191.5） :-)
回复于 2024-04-25T13:30:59+08:00
730
由于分支预测，上述行为正在发生 .

要理解分支预测，首先必须了解 Instruction Pipeline ：

任何指令都被分成一系列步骤，以便可以并行地同时执行不同的步骤 . 这种技术称为指令流水线，用于提高现代处理器的吞吐量 . 要更好地理解这一点，请参阅example on Wikipedia .

通常，现代处理器具有相当长的流水线，但为了方便起见，我们只考虑这4个步骤 .
- IF - 从内存中获取指令
- ID - 解码指令
- EX - 执行指令
- WB - 写回CPU寄存器
4-stage pipeline in general for 2 instructions.

回到上面的问题，让我们考虑以下说明：
```
A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().
```
如果没有分支预测，将发生以下情况：

为了执行指令B或指令C，处理器必须等到指令A没有到达流水线中的EX阶段，因为转到指令B或指令C的决定取决于指令A的结果 . 所以管道会是这样的 .

when if condition returns true:

When if condition returns false:

作为等待指令A的结果的结果，在上述情况下花费的总CPU周期（没有分支预测;对于真和假）都是7 .

So what is branch prediction?

分支预测器将尝试猜测分支（if-then-else结构）将以何种方式确定之前 . 它不会等待指令A到达流水线的EX阶段，但是它会猜测决定并转到该指令（在我们的例子中是B或C） .

In case of a correct guess, the pipeline looks something like this:

如果稍后检测到猜测错误则丢弃部分执行的指令，并且管道以正确的分支重新开始，从而引起延迟 . 在分支错误预测的情况下浪费的时间等于从提取阶段到执行阶段的管道中的阶段的数量 . 现代微处理器往往具有相当长的流水线，因此误预测延迟在10到20个时钟周期之间 . 管道越长，对branch predictor的需求就越大 .

在OP的代码中，第一次有条件时，分支预测器没有任何基于预测的信息，所以第一次它会随机选择下一条指令 . 稍后在for循环中，它可以基于历史记录进行预测 . 对于按升序排序的数组，有三种可能性：
- 所有元素都小于128
- 所有元素都大于128
- 一些起始新元素小于128，后来大于128
让我们假设预测器将始终在第一次运行时假设真正的分支 .

因此，在第一种情况下，它始终采用真正的分支，因为历史上它的所有预测都是正确的 . 在里面第二种情况，最初它会预测错误，但经过几次迭代后，它会正确预测 . 在第三种情况下，它将最初正确地预测，直到元素小于128.之后它将失败一段时间并且当它看到历史中的分支预测失败时正确 .

在所有这些情况下，故障的数量将会减少，因此，只需要几次就可以丢弃部分执行的指令并重新使用正确的分支，从而减少CPU周期 .

但是在随机未排序的数组的情况下，预测将需要丢弃部分执行的指令并且在大多数时间重新开始使用正确的分支，并且与排序的数组相比产生更多的CPU周期 .
回复于 2024-04-25T13:30:59+08:00
148
官方的答案是来自
- Intel - Avoiding the Cost of Branch Misprediction
- Intel - Branch and Loop Reorganization to Prevent Mispredicts
- Scientific papers - branch prediction computer architecture
- 书籍：J.L . 轩尼诗，D.A . 帕特森：计算机架构：一种定量方法
- 科学出版物中的文章：T.Y . Ye，Y.N . Patt在分支预测上做了很多这些 .
你也可以从这个可爱的diagram中看到为什么分支预测器会混淆 .

原始代码中的每个元素都是随机值
```
data[c] = std::rand() % 256;
```
因此预测变量将会因为 std::rand() 而受到影响 .

另一方面，一旦它被排序，预测器将首先进入强烈未被采用的状态，并且当值变为高值时，预测器将在三次运行中通过从强烈不采取到强烈采取的一直改变 .
回复于 2024-04-25T13:30:59+08:00
641
在同一行（我认为没有任何答案突出显示），有时候（特别是在性能很重要的软件中，比如在Linux内核中），你可以找到一些if语句，如下所示：
```
if (likely( everything_is_ok ))
{
    /* Do something */
}
```
或者类似的：
```
if (unlikely(very_improbable_condition))
{
    /* Do something */    
}
```
likely() 和 unlikely() 实际上都是通过使用类似GCC的 __builtin_expect 来定义的宏来帮助编译器插入预测代码以支持考虑用户提供的信息的条件 . GCC支持其他可能改变正在运行的程序行为的内置函数或发出低级指令，如清除缓存等 . 请参阅this documentation，它通过可用的GCC内置函数 .

通常，这种优化主要在硬实时应用程序或嵌入式系统中找到，其中执行时间很重要且非常重要 . 例如，如果您正在检查仅发生1/10000000次的错误情况，那么为什么不通知编译器呢？这样，默认情况下，分支预测会假设条件为假 .
回复于 2024-04-25T13:30:59+08:00

3769

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

从原始循环开始：

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倍

回复于 2024-04-25T13:30:59+08:00

2085
当数组排序时，数据分布在0到255之间，迭代的前半部分将不会进入 if -statement（ if 语句在下面共享） .
```
if (data[c] >= 128)
    sum += data[c];
```
问题是：在某些情况下，如果排序数据的情况，上述语句不执行的原因是什么？这是"branch predictor" . 分支预测器是一种数字电路，它试图猜测分支（例如 if-then-else 结构）在确定之前会走哪条路 . 分支预测器的目的是改善指令流水线中的流程 . 分支预测器在实现高效性能方面发挥着关键作用！

Let's do some bench marking to understand it better

if -statement的性能取决于其条件是否具有可预测的模式 . 如果条件始终为真或始终为假，则处理器中的分支预测逻辑将获取模式 . 另一方面，如果模式不可预测， if -statement将更加昂贵 .

让我们用不同的条件来衡量这个循环的性能：
```
for (int i = 0; i < max; i++)
    if (condition)
        sum++;
```
以下是具有不同真假模式的循环的时序：
```
Condition            Pattern                 Time (ms)

(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0            TF alternating    760

(i & 3) == 0            TFFFTFFF…          513

(i & 2) == 0            TTFFTTFF…          1675

(i & 4) == 0            TTTTFFFFTTTTFFFF… 1275

(i & 8) == 0            8T 8F 8T 8F …     752

(i & 16) == 0            16T 16F 16T 16F … 490
```
“ bad ”真假模式可以使 if -statement比“ good ”模式慢6倍！当然，哪种模式好，哪种模式不好取决于编译器和特定处理器生成的确切指令 .

因此，分支预测对性能的影响毫无疑问！
回复于 2024-04-25T13:30:59+08:00
578
由于称为分支预测的现象，排序的阵列比未排序的阵列处理得更快 .

分支预测器是一种数字电路（在计算机体系结构中），试图预测分支将采用哪种方式，从而改善指令流水线中的流量 . 该电路/计算机预测下一步并执行它 .

做出错误的预测会导致返回上一步，并执行另一个预测 . 假设预测正确，代码将继续下一步 . 错误的预测导致重复相同的步骤，直到发生正确的预测 .

你的问题的答案很简单 .

在未排序的数组中，计算机会进行多次预测，从而导致出错的可能性增加 . 然而，在排序中，计算机进行的预测更少，从而减少了出错的可能性 . 进行更多预测需要更多时间 .

分类阵列：直道
```
____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
```
未排序的阵列：弯曲的道路
```
______   ________
|     |__|
```
分支预测：猜测/预测哪条道路是直的并且在没有检查的情况下跟随它
```
___________________________________________ Straight road
 |_________________________________________|Longer road
```
虽然两条道路都到达同一目的地，但直道较短，而另一条道路较长 . 如果那时你错误地选择了另一个，那么就没有回头了，所以如果选择更长的路，你会浪费一些额外的时间 . 这与计算机上发生的情况类似，我希望这有助于您更好地理解 .

更新：在@Simon_Weaver所说的之后，我想添加另一个事实......“它不会做出更少的预测 - 它会减少不正确的预测 . 它仍然需要预测每次循环 . ”
回复于 2024-04-25T13:30:59+08:00

29314

虽然，正如其他答案所提到的，现代编译器或体系结构（ARM）使这个具体的例子没有实际意义，但在一般情况下，人们需要对数据进行排序的其他答案的假设并不完全正确 .

以下代码不对整个数组进行排序，而是仅对其中的200个元素进行排序，从而运行得最快 .

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

int main() {
    int data[32768]; const int l = sizeof data / sizeof data[0];

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

    // sort 200-element segments, not the whole array
    for (unsigned c = 0; c + 200 <= l; c += 200)
        std::sort(&data[c], &data[c + 200]);

    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i) {
        for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

仅对k元素部分进行排序以线性时间完成预处理，而不是 n.log(n) 一般情况 .

这也“证明”它与任何算法问题（例如排序顺序）无关，它确实是分支预测 .

回复于 2024-04-25T13:30:59+08:00

255
正如其他人已经提到的那样，神秘背后的是Branch Predictor .

我不是想添加一些东西，而是以另一种方式解释这个概念 . 维基上有一个简明的介绍，其中包含文本和图表 . 我喜欢下面的解释，它使用图表直观地阐述了分支预测器 .

在计算机体系结构中，分支预测器是一种数字电路，它试图猜测分支（例如if-then-else结构）在确定之前会走哪条路 . 分支预测器的目的是改善指令流水线中的流程 . 分支预测器在许多现代流水线微处理器架构（如x86）中实现高效性能方面发挥着关键作用 . 双向分支通常使用条件跳转指令来实现 . 条件跳转可以是“未采用”并继续执行第一个代码分支，紧接在条件跳转之后，或者可以“采取”并跳转到程序存储器中的不同位置，其中第二个代码分支是存储 . 在计算条件并且条件跳转已经过指令流水线中的执行阶段之前，不确定是否采取条件跳转是未知的（见图1） .

基于所描述的场景，我编写了一个动画演示，以显示在不同情况下如何在管道中执行指令 .
- 没有分支预测器 .
如果没有分支预测，处理器必须等到条件跳转指令通过执行阶段，然后下一条指令才能进入流水线中的提取阶段 .

该示例包含三条指令，第一条是条件跳转指令 . 后两条指令可以进入流水线，直到执行条件跳转指令 .

完成3条指令需要9个时钟周期 .
- 使用分支预测器并且假设预测是 not 进行条件跳转 .
完成3条指令需要7个时钟周期 .
- 使用分支预测器并进行条件跳转 . 让我们假设预测是 not 采取条件跳跃 .
完成3条指令需要9个时钟周期 .

在分支错误预测的情况下浪费的时间等于从提取阶段到执行阶段的管道中的阶段数 . 现代微处理器往往具有相当长的流水线，因此误预测延迟在10到20个时钟周期之间 . 因此，使管道更长时间增加了对更高级分支预测器的需求 .

如您所见，似乎我们没有理由不使用Branch Predictor .

这是一个非常简单的演示，阐明了Branch Predictor的基本部分 . 如果这些GIF很烦人，请随时将它们从答案中删除，访问者也可以从git获取演示
回复于 2024-04-25T13:30:59+08:00
241

这个问题已经存在得到了很多次的回答 . 我仍然希望将该小组的注意力吸引到另一个有趣的分析上 .

最近这个例子（稍微修改过）也被用来演示如何在Windows上的程序本身中分析一段代码 . 在此过程中，作者还展示了如何使用结果来确定代码在排序和未排序的情况下花费大部分时间的位置 . 最后，该文章还展示了如何使用HAL（硬件抽象层）的一个鲜为人知的特征来确定在未排序的情况下发生了多少分支错误预测 .

链接在这里：http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm

回复于 2024-04-25T13:30:59+08:00
1735
You are a victim of branch prediction fail.

什么是分支预测？

考虑一个铁路交界处：

图片来自Mecanismo，来自Wikimedia Commons . 在CC-By-SA 3.0许可下使用 .

现在为了争论，假设这是在19世纪 - 在长途或无线电通信之前 .

您是交叉路口的运营商，您会听到火车即将到来 . 你不知道应该走哪条路 . 你停下火车去询问司机他们想要的方向 . 然后适当地设置开关 .

火车很重，有很多惯性 . 所以他们需要永远的启动和放慢速度 .

有没有更好的办法？你猜猜火车往哪个方向走！
- 如果你猜对了，它会继续 .
- 如果你猜对了，机长会停下来，然后向你大喊大叫，然后翻转开关 . 然后它可以重新启动另一条路径 .
If you guess right every time ，火车永远不会停下来 .
If you guess wrong too often ，火车将花费大量时间停车，备份和重新启动 .

Consider an if-statement: 在处理器级别，它是一个分支指令：

你是一个处理器，你看到一个分支 . 你不知道它会走哪条路 . 你是做什么？您暂停执行并等待前面的指令完成 . 然后继续沿着正确的路径前进 .

现代处理器很复杂，管道很长 . 所以他们永远地把"warm up"和"slow down" .

有没有更好的办法？你猜猜分支的方向！
- 如果你猜对了，你继续执行 .
- 如果您猜错了，则需要刷新管道并回滚到分支 . 然后你可以重新启动另一条路径 .
If you guess right every time ，执行永远不会停止 .
If you guess wrong too often ，你花了很多时间拖延，回滚和重新启动 .

这是分支预测 . 我承认这不是最好的类比，因为火车可以用旗帜向方向发出信号 . 但是在计算机中，处理器直到最后一刻才知道分支将朝哪个方向发展 .

那么你如何战略性地猜测火车必须备份并沿着另一条路走下去的次数呢？你看看过去的历史！如果火车99％的时间都离开了，那么你猜对了 . 如果它交替，那么你交替猜测 . 如果它每3次走一条路，你就猜相同......

In other words, you try to identify a pattern and follow it. 这或多或少是分支预测器的工作方式 .

大多数应用程序具有良好的分支 . 因此，现代分支预测器通常会达到> 90％的命中率 . 但是当面对不可预测的分支而没有可识别的模式时，分支预测器实际上是无用的 .

进一步阅读："Branch predictor" article on Wikipedia .

如上所述，罪魁祸首就是这个if语句：
```
if (data[c] >= 128)
    sum += data[c];
```
请注意，数据均匀分布在0到255之间 . 当数据排序时，大致前半部分的迭代不会进入if语句 . 之后，他们都将进入if语句 .

这对分支预测器非常友好，因为分支连续多次朝同一方向运行 . 即使是简单的饱和计数器也会正确地预测分支，除了在切换方向后的几次迭代 .

Quick visualization:
```
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)
```
So what can be done?

如果编译器无法将分支优化为条件移动，那么如果您愿意牺牲性能的可读性，则可以尝试一些黑客攻击 .

更换：
```
if (data[c] >= 128)
    sum += data[c];
```
有：
```
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
```
这消除了分支并用一些按位操作替换它 .

（注意，这个hack并不完全等同于原始的if语句 . 但在这种情况下，它对data []的所有输入值都有效 . ）

Benchmarks: 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
```
观察：
- With the Branch: 已排序和未排序的数据之间存在巨大差异 .
- With the Hack: 已排序和未排序数据之间没有区别 .
- 在C情况下，当数据排序时，hack实际上比分支慢一点 .
一般的经验法则是避免关键循环中依赖于数据的分支 . （比如在这例）

Update:

在x64上使用 -O3 或 -ftree-vectorize 的
- GCC 4.6.1能够生成条件移动 . 因此，排序和未排序数据之间没有区别 - 两者都很快 .
- 即使在 /Ox 下，VC 2010也无法为此分支生成条件移动 .
- 英特尔编译器11做了一些奇迹 . 它interchanges the two loops，从而将不可预测的分支提升到外环 . 因此，它不仅可以免受错误预测的影响，而且速度也是VC和GCC产生的速度的两倍！换句话说，ICC利用测试循环来击败基准......
- 如果你给英特尔编译器提供无分支代码，它只是向右矢量化它......并且与分支一样快（使用循环交换） .
这表明即使是成熟的现代编译器在优化代码的能力方面也会有很大差异......
回复于 2024-04-25T13:30:59+08:00
1072
我刚刚读到了这个问题及其答案，我觉得答案遗失了 .

消除我发现在托管语言中工作特别好的分支预测的常用方法是查找表而不是使用分支（尽管在这种情况下我还没有测试过它） .

如果符合以下情况，此方法通用
- 这是一张小 table ，可能会被缓存在处理器中
- 您正在以非常紧凑的循环运行和/或处理器可以预加载数据
Background and why

Pfew，那到底是什么意思呢？

从处理器的角度来看，你的记忆很慢 . 为了弥补速度上的差异，他们在处理器（L1 / L2缓存）中构建了几个缓存来补偿这一点 . 所以想象一下，你正在做你很好的计算，并发现你需要一块记忆 . 处理器将获得其“加载”操作并将内存加载到缓存中 - 然后使用缓存执行其余计算 . 因为内存相对较慢，这种“加载”会降低程序的速度 .

与分支预测一样，这在Pentium处理器中进行了优化：处理器预测它需要加载一段数据并尝试在操作实际到达缓存之前将其加载到缓存中 . 正如我们已经看到的那样，分支预测有时会出现严重错误 - 在最坏的情况下，您需要返回并实际等待内存负载，这将需要永远（ in other words: failing branch prediction is bad, a memory load after a branch prediction fail is just horrible! ） .

幸运的是，如果内存访问模式是可预测的，处理器将把它加载到快速缓存中，一切都很好 .

我们需要知道的第一件事是小什么？虽然较小通常更好，但经验法则是坚持查找大小<= 4096字节的表 . 作为上限：如果您的查找表大于64K，则可能值得重新考虑 .

Constructing a table

所以我们已经发现我们可以创建一个小表 . 接下来要做的是获得一个查找功能 . 查找函数通常是使用几个基本整数运算的小函数（和，或者，xor，shift，add，remove和multiply） . 您希望通过查找功能将您的输入转换为表格中的某种“唯一键”，然后简单地为您提供您希望它完成的所有工作的答案 .

在这种情况下：> = 128意味着我们可以保留值，<128意味着我们摆脱它 . 最简单的方法是使用'AND'：如果我们保留它，我们和它一起使用7FFFFFFF;如果我们想摆脱它，我们和它为0.注意，128也是2的幂 - 所以我们可以继续制作一个32768/128整数的表并填充一个零和很多7FFFFFFFF的 .

Managed languages

您可能想知道为什么这在托管语言中运行良好 . 毕竟，托管语言使用分支检查数组的边界，以确保您不会陷入困境......

好吧，不完全...... :-)

为管理语言消除此分支已经做了相当多的工作 . 例如：
```
for (int i=0; i<array.Length; ++i)
   // Use array[i]
```
在这种情况下，编译器显然不会遇到边界条件 . 至少Microsoft JIT编译器（但我希望Java做类似的事情）会注意到这一点，并完全取消检查 . 哇 - 这意味着没有分支 . 同样，它将处理其他明显的案例 .

如果您在托管语言上查找时遇到麻烦 - 关键是在查找函数中添加 & 0x[something]FFF 以使边界检查可预测 - 并且观察它更快 .

The result of this case
```
// 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.Next(256);

//To keep the spirit of the code in-tact I'll make a separate lookup table
// (I assume we cannot modify 'data' or the number of loops)
int[] lookup = new int[256];

for (int c = 0; c < 256; ++c)
    lookup[c] = (c >= 128) ? c : 0;

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        // Here you basically want to use simple operations - so no
        // random branches, but things like &, |, *, -, +, etc. are fine.
        sum += lookup[data[j]];
    }
}

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);

Console.ReadLine();
```
回复于 2024-04-25T13:30:59+08:00
150
在C中经常使用的布尔运算在编译的程序中产生许多分支 . 如果这些分支在内部循环中并且很难预测它们会显着减慢执行速度 . 布尔变量存储为8位整数， 0 为 false ， 1 为 true .

布尔变量是超定的，因为所有具有布尔变量作为输入的运算符检查输入是否具有除 0 或 1 之外的任何其他值，但是具有布尔值作为输出的运算符不能产生除 0 或 1 之外的其他值 . 这使得操作使用布尔变量作为输入效率低于必要的效率 . 考虑示例：
```
bool a, b, c, d;
c = a && b;
d = a || b;
```
这通常由编译器以下列方式实现：
```
bool a, b, c, d;
if (a != 0) {
    if (b != 0) {
        c = 1;
    }
    else {
        goto CFALSE;
    }
}
else {
    CFALSE:
    c = 0;
}
if (a == 0) {
    if (b == 0) {
        d = 0;
    }
    else {
        goto DTRUE;
    }
}
else {
    DTRUE:
    d = 1;
}
```
这段代码远非最佳 . 如果误预测，分支机构可能需要很长时间 . 如果确定操作数没有 0 和 1 之外的其他值，则可以使布尔运算更有效 . 编译器没有做出这样的假设的原因是，如果变量未初始化或来自未知来源，则变量可能具有其他值 . 如果 a 和 b 已初始化为有效值，或者它们来自产生布尔输出的运算符，则可以优化上述代码 . 优化的代码如下所示：
```
char a = 0, b = 1, c, d;
c = a & b;
d = a | b;
```
使用 char 代替 bool ，以便可以使用按位运算符（ & 和 | ）代替布尔运算符（ && 和 || ） . 按位运算符是单指令，只需一个时钟周期 . 即使 a 和 b 具有除 0 或 1 之外的其他值，OR运算符（ | ）也可以工作 . 如果操作数具有除 0 和 1 之外的其他值，则AND运算符（ & ）和EXCLUSIVE OR运算符（ ^ ）可能会产生不一致的结果 .

~ 不能用于NOT . 相反，您可以通过使用 1 对其进行异或来对已知为 0 或 1 的变量进行布尔值NOT：
```
bool a, b;
b = !a;
```
可以优化为：
```
char a = 0, b;
b = a ^ 1;
```
a && b 不能替换为 a & b ，如果 b 是一个不应该被评估的表达式，如果 a 是 false （ && 将不评估 b ， & 将） . 同样， a || b 不能替换为 a | b ，如果 b 是 a 为 true 时不应评估的表达式 .

如果操作数是变量而不是操作数是比较，则使用按位运算符更有利：
```
bool a; double x, y, z;
a = x > y && z < 5.0;
```
在大多数情况下是最佳的（除非您希望 && 表达式生成许多分支错误预测） .
回复于 2024-04-25T13:30:59+08:00
98
这是关于分支预测 . 它是什么？
- 分支预测器是古老的性能改进技术之一，它仍然与现代建筑相关 . 虽然简单的预测技术提供快速查找和功率效率，但是它们具有高的误预测率 .
- 另一方面，复杂的分支预测 - 无论是基于神经的还是两级分支预测的变体 - 提供更好的预测准确性，但它们消耗更多的功率和复杂性以指数方式增加 .
- 除此之外，在复杂的预测技术中，预测分支所花费的时间本身非常高，从2到5个周期 - 这与实际分支的执行时间相当 .
- 分支预测本质上是一种优化（最小化）问题，其中重点在于以最少的资源实现最低可能的未命中率，低功耗和低复杂度 .
确实有三种不同的分支：

Forward conditional branches - 基于运行时条件，PC（程序计数器）被更改为指向指令流中的前向地址 .

Backward conditional branches - PC在指令流中更改为指向后方 . 分支基于某些条件，例如，当循环结束时的测试表明循环应该再次执行时，向后分支到程序循环的开头 .

Unconditional branches - 这包括跳转，过程调用和没有特定条件的返回 . 例如，无条件跳转指令可能用汇编语言编码为"jmp"，并且指令流必须立即定向到跳转指令指向的目标位置，而可能编码为"jmpne"的条件跳转会重定向指令仅当先前"compare"指令中两个值的比较结果显示值不相等时才流 . （x86架构使用的分段寻址方案增加了额外的复杂性，因为跳转可以是"near"（在段内）或"far"（在段外） . 每种类型对分支预测算法都有不同的影响 . ）

Static/dynamic Branch Prediction ：微处理器在第一次遇到条件分支时使用静态分支预测，并且动态分支预测用于条件分支代码的后续执行 .

参考文献：
回复于 2024-04-25T13:30:59+08:00
85
避免分支预测错误的一种方法是构建查找表，并使用数据对其进行索引 . Stefan de Bruijn在他的回答中讨论了这一点 .

但在这种情况下，我们知道值在[0,255]范围内，我们只关心值> = 128.这意味着我们可以轻松地提取一个位，告诉我们是否需要一个值：通过移位右边的数据7位，我们留下0位或1位，我们只想在有1位时添加该值 . 我们称这个位为“决策位” .

通过使用决策位的0/1值作为数组的索引，无论数据是排序还是未排序，我们都可以制作同样快速的代码 . 我们的代码总是会添加一个值，但是当决策位为0时，我们会将值添加到我们不关心的地方 . 这是代码：
```
// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];
```
此代码浪费了一半的添加但从未有分支预测失败 . 随机数据的速度比具有实际if语句的版本快得多 .

但在我的测试中，显式查找表略快于此，可能是因为索引到查找表的速度比位移略快 . 这显示了我的代码如何设置和使用查找表（在代码中为"LookUp Table"无法想象地称为 lut ） . 这是C代码：
```
// declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}
```
在这种情况下，查找表只有256个字节，因此它非常适合缓存，而且速度很快 . 如果数据是24位值并且我们只想要它们中的一半，这种技术将无法正常工作......查找表太大而不实用 . 另一方面，我们可以结合上面显示的两种技术：首先将位移位，然后索引查找表 . 对于我们只想要上半部分值的24位值，我们可能将数据右移12位，并为表索引留下12位值 . 12位表索引意味着一个包含4096个值的表，这可能是实用的 .

编辑：有一件事我忘记了 .

索引到数组而不是使用 if 语句的技术可用于决定使用哪个指针 . 我看到一个实现二叉树的库，而不是有两个命名指针（ pLeft 和 pRight 或其他）有一个长度为2的指针数组，并使用"decision bit"技术来决定遵循哪一个 . 例如，而不是：
```
if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;
```
这个库会做类似的事情：
```
i = (x < node->value);
node = node->link[i];
```
以下是此代码的链接：Red Black Trees，Eternal Confuzzled
回复于 2024-04-25T13:30:59+08:00
82
Branch-prediction gain!

重要的是要理解分支错误预测不会减慢程序的速度 . 错过预测的成本就像分支预测不存在一样，您等待表达式的评估以决定运行什么代码（在下一段中进一步说明） .
```
if (expression)
{
    // Run 1
} else {
    // Run 2
}
```
只要存在 if-else \ switch 语句，就必须计算表达式以确定应该执行哪个块 . 在编译器生成的汇编代码中，插入了条件branch指令 .

分支指令可以使计算机开始执行不同的指令序列，从而偏离其按顺序执行指令的默认行为（即，如果表达式为假，则程序会跳过 if 块的代码），具体取决于某些条件，是我们案例中的表达评估 .

话虽这么说，编译器会尝试在实际评估之前预测结果 . 它将从 if 块中获取指令，如果表达式结果为真，则很棒！我们获得了评估它并在代码中取得进展所花费的时间;如果没有，那么我们运行错误的代码，刷新管道，并运行正确的块 .

可视化：

假设您需要选择路线1或路线2.等待您的伴侣检查 Map ，您已停在##并等待，或者您可以选择路线1，如果您幸运（路线1是正确路线），然后很棒，你不必等待你的伴侣检查 Map （你节省了检查 Map 的时间），否则你只需要回头 .

虽然冲洗管道速度非常快，但现在采取这种赌博是值得的 . 预测排序数据或变化缓慢的数据总是比预测快速变化更容易和更好 .
```
O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------
```
回复于 2024-04-25T13:30:59+08:00
74
除了分支预测可能会降低您的速度之外，排序数组还有另一个优势：

您可以设置停止条件而不是仅检查值，这样您只需循环访问相关数据，并忽略其余数据 .
分支预测只会遗漏一次 .
```
// sort backwards (higher values first)
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }
```
回复于 2024-04-25T13:30:59+08:00

1004

毫无疑问，我们中的一些人会对识别对CPU的分支预测器有问题的代码感兴趣 . Valgrind工具 cachegrind 有一个分支预测模拟器，使用 --branch-sim=yes 标志启用 . 在这个问题的例子中运行它，外部循环的数量减少到10000并用 g++ 编译，给出了以下结果：

Sorted:

==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )

Unsorted:

==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )

深入研究 cg_annotate 产生的逐行输出，我们看到有问题的循环：

Sorted:

Bc    Bcm Bi Bim
      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .      .  .   .      {
           .      .  .   .          // primary loop
 327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .      .  .   .          {
 327,680,000 10,006  0   0              if (data[c] >= 128)
           0      0  0   0                  sum += data[c];
           .      .  .   .          }
           .      .  .   .      }

Unsorted:

Bc         Bcm Bi Bim
      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .           .  .   .      {
           .           .  .   .          // primary loop
 327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .           .  .   .          {
 327,680,000 164,050,007  0   0              if (data[c] >= 128)
           0           0  0   0                  sum += data[c];
           .           .  .   .          }
           .           .  .   .      }

这使您可以轻松识别有问题的行 - 在未排序的版本中 if (data[c] >= 128) 行导致在cachegrind下导致164,050,007个错误预测的条件分支（ Bcm ）'s branch-predictor model, whereas it'仅在排序版本中导致10,006 .

或者，在Linux上，您可以使用性能计数器子系统来完成相同的任务，但使用CPU计数器具有本机性能 .

perf stat ./sumtest_sorted

Sorted:

Performance counter stats for './sumtest_sorted':

  11808.095776 task-clock                #    0.998 CPUs utilized          
         1,062 context-switches          #    0.090 K/sec                  
            14 CPU-migrations            #    0.001 K/sec                  
           337 page-faults               #    0.029 K/sec                  
26,487,882,764 cycles                    #    2.243 GHz                    
41,025,654,322 instructions              #    1.55  insns per cycle        
 6,558,871,379 branches                  #  555.455 M/sec                  
       567,204 branch-misses             #    0.01% of all branches        

  11.827228330 seconds time elapsed

Unsorted:

Performance counter stats for './sumtest_unsorted':

  28877.954344 task-clock                #    0.998 CPUs utilized          
         2,584 context-switches          #    0.089 K/sec                  
            18 CPU-migrations            #    0.001 K/sec                  
           335 page-faults               #    0.012 K/sec                  
65,076,127,595 cycles                    #    2.253 GHz                    
41,032,528,741 instructions              #    0.63  insns per cycle        
 6,560,579,013 branches                  #  227.183 M/sec                  
 1,646,394,749 branch-misses             #   25.10% of all branches        

  28.935500947 seconds time elapsed

它还可以使用反汇编来执行源代码注释 .

perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted

Percent |      Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
         :                      sum += data[c];
    0.00 :        400a1a:       mov    -0x14(%rbp),%eax
   39.97 :        400a1d:       mov    %eax,%eax
    5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax
    4.60 :        400a26:       cltq   
    0.00 :        400a28:       add    %rax,-0x30(%rbp)
...

有关详细信息，请参阅the performance tutorial .

回复于 2024-04-25T13:30:59+08:00

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

22 回答

什么是分支预测？

如上所述，罪魁祸首就是这个if语句：

可视化：

相关问题