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

java c++ performance cpu-architecture branch-prediction

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

如果没有 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);
    }
}

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

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

到底是怎么回事?

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

该代码总结了一些独立的术语,因此顺序无关紧要。

关于不同/更高版本的编译器和选项的相同效果的相关/后续问答:

为什么处理未排序数组的速度与使用现代 x86-64 clang 处理已排序数组的速度相同?

gcc 优化标志 -O3 使代码比 -O2 慢

作为记录,您的数据不需要排序,只需 partitioned,这是一个更快的操作。

另一个观察结果是您不需要对数组进行排序,而只需使用值 128 对其进行分区。排序是 n*log(n),而分区只是线性的。基本上,这只是快速排序分区步骤的一次运行,其中枢轴选择为 128。不幸的是,在 C++ 中只有 nth_element 函数,它按位置分区,而不是按值分区。

@screwnut 这是一个实验,它表明分区就足够了:创建一个未排序但分区的数组,其中包含其他随机内容。测量时间。解决。再次测量时间。这两个测量值应该基本上无法区分。 (实验 2:创建一个随机数组。测量时间。对其进行分区。再次测量时间。您应该看到与排序相同的加速。您可以将两个实验合二为一。)

顺便提一句。在 Apple M1 上,未排序的代码在 17 秒内运行,排序后的代码在 7 秒内运行,因此分支预测惩罚在 risc 架构上并没有那么糟糕。

@RomanYavorskyi:这取决于编译器。如果他们为此特定测试制作无分支汇编(例如,作为像 Why is processing an unsorted array the same speed as processing a sorted array with modern x86-64 clang? 中使用 SIMD 进行矢量化的一部分,或者只是使用标量 cmov (gcc optimization flag -O3 makes code slower than -O2)),那么排序与否无关紧要。但不可预测的分支仍然存在当它不像计数那么简单时,这是一件非常真实的事情,所以删除这个问题会很疯狂。

Z
Zoe stands with Ukraine

您是 branch prediction 失败的受害者。

什么是分支预测?

考虑一个铁路枢纽:

https://i.stack.imgur.com/muxnt.jpg

现在为了争论,假设这是在 1800 年代——在远距离或无线电通信之前。

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

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

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

如果你猜对了,它会继续。

如果你猜错了,船长会停下来,后退,然后对你大喊大叫来拨动开关。然后它可以重新启动另一条路径。

如果你每次都猜对了,火车就永远不用停下来。如果您经常猜错,火车将花费大量时间停止、倒车和重新启动。

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

https://i.stack.imgur.com/pyfwC.png

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

现代处理器很复杂并且有很长的流水线。这意味着他们需要永远“热身”和“减速”。

有没有更好的办法?你猜这个分支会往哪个方向走!

如果你猜对了,你继续执行。

如果你猜错了,你需要刷新管道并回滚到分支。然后,您可以重新启动另一条路径。

如果你每次都猜对了,执行将永远不会停止。如果您经常猜错,您会花费大量时间停止、回滚和重新启动。

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

您将如何策略性地猜测以最小化火车必须倒车并沿另一条路径行驶的次数?你看看过去的历史!如果火车 99% 的时间都是左转,那么你猜是左转。如果它交替,那么你交替你的猜测。如果它每 3 次去一个方向,你猜同样...

换句话说,您尝试识别一种模式并遵循它。这或多或少是分支预测器的工作方式。

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

进一步阅读:"Branch predictor" article on Wikipedia

正如上面所暗示的,罪魁祸首是这个 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[] 的所有输入值都有效。)

基准测试:Core 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

观察:

使用分支:已排序数据和未排序数据之间存在巨大差异。

使用技巧:排序数据和未排序数据之间没有区别。

在 C++ 的情况下,当数据被排序时,hack 实际上比使用分支慢一点。

一般的经验法则是避免关键循环中的数据相关分支(例如在此示例中)。

更新:

在 x64 上带有 -O3 或 -ftree-vectorize 的 GCC 4.6.1 能够生成条件移动,因此已排序和未排序的数据之间没有区别 - 两者都很快。 (或者有点快:对于已经排序的情况,cmov 可能会更慢,特别是如果 GCC 将它放在关键路径上而不是仅仅添加,尤其是在 Broadwell 之前的 Intel 上,其中 cmov 有 2 个周期延迟:gcc 优化标志 -O3 使代码变慢比 -O2)

即使在 /Ox 下,VC++ 2010 也无法为此分支生成条件移动。

英特尔 C++ 编译器 (ICC) 11 做了一些神奇的事情。它交换两个循环,从而将不可预测的分支提升到外部循环。它不仅不受错误预测的影响,而且速度也是 VC++ 和 GCC 生成的速度的两倍!换句话说,ICC 利用测试循环击败了基准测试......

如果您为英特尔编译器提供无分支代码,它会直接对其进行矢量化......并且与分支(使用循环交换)一样快。

这表明即使是成熟的现代编译器在优化代码的能力上也会有很大的不同......

等一下,是否将负值转移到正确的产量实现定义的值? int t = (data[c] - 128) >> 31;总和 += ~t & 数据[c];

顺便说一句,分支预测失败也可能是 exploited by a program to obtain crypto keys being used by another program 在同一个 CPU 内核上。

@Mycotina,我不是专家,但我的理解是:处理器需要多个步骤来执行一条指令(获取、解码等)——这被称为“指令流水线”——所以,作为一种优化,它将一次获取多条指令并在执行当前指令时“预热”下一条指令。如果选择了错误的分支,则必须丢弃流水线中正在“预热”的指令,以便可以将正确分支上的指令放入流水线中。

@Mycotina 当您将指令管道缓存视为轨道,将火车(有汽车)视为指令以及在火车末端由某个家伙向左还是向右的指示器时,会更容易理解;不是开始。当你看到他就知道你猜对了,不仅换东西为时已晚,前面的管道已经填满了,而且方向错了。如果您猜错了,则需要扔掉预测的管道(使火车脱轨;将其拖回开关房前,将其放回轨道上,然后将其发送到另一个方向)。

@C.Binair 主要是运行时,即处理器在执行代码时预测分支。处理器还记得以前的结果,并用它来预测下一次跳跃。但是,编译器可以在编译时为分支预测提供一些初始提示——搜索“可能”和“不太可能”的属性。所以你可以说答案是两者兼而有之,但运行时是它实际发生的时间。

C
Community

分支预测。

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

分支预测在排序数组与具有不同模式的数组上效果更好吗?例如,对于数组 --> { 10, 5, 20, 10, 40, 20, ... } 模式中数组中的下一个元素是 80。这种数组是否会通过分支预测加速如果遵循模式,下一个元素是 80?或者它通常只对排序数组有帮助?

所以基本上我从传统上学到的关于 big-O 的一切都在窗外?分拣成本比分支成本更好吗?

@AgrimPathak 这取决于。对于不太大的输入,当具有较高复杂度的算法的常数较小时,具有较高复杂度的算法比具有较低复杂度的算法更快。盈亏平衡点在哪里很难预测。此外,compare this,位置很重要。 Big-O 很重要,但它不是性能的唯一标准。

何时进行分支预测?语言何时会知道数组已排序?我正在考虑看起来像这样的数组情况: [1,2,3,4,5,...998,999,1000, 3, 10001, 10002] ?这个不起眼的3会增加运行时间吗?它会和未排序的数组一样长吗?

@FilipBartuzi 分支预测发生在处理器中,低于语言级别(但语言可能会提供告诉编译器可能发生什么的方法,因此编译器可以发出适合该情况的代码)。在您的示例中,无序的 3 将导致分支错误预测(对于适当的条件,其中 3 给出的结果与 1000 不同),因此处理该数组可能需要比排序后的数组几乎不会引起注意。花费时间的是我的错误预测率很高,每 1000 个错误预测并不多。

M
Mihir Ajmera

数据排序后性能显着提高的原因是分支预测惩罚被移除,如 Mysticial's answer 中所述。

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

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

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

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 程序集来更仔细地观察。为简单起见,我们使用两个函数 max1max2

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

由于使用了指令 cmovgemax2 使用的代码要少得多。但真正的收获是 max2 不涉及分支跳转,jmp 如果预测结果不正确,这将产生显着的性能损失。

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

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

在分支情况下,后面的指令是由前面的指令决定的,所以我们不能进行流水线操作。我们必须等待或预测。

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

Computer Systems: A Programmer's Perspective, second edition 一书详细解释了这一点。您可以查看第 3.6.6 节的条件移动指令,查看整个第 4 章的处理器架构,查看第 5.11.2 节的分支预测和错误预测惩罚的特殊处理

有时,一些现代编译器可以将我们的代码优化为具有更好性能的汇编,而有时一些编译器则不能(有问题的代码使用 Visual Studio 的本机编译器)。当场景变得如此复杂以至于编译器无法自动优化它们时,了解分支和条件移动之间的性能差异可以帮助我们编写性能更好的代码。

stackoverflow.com/questions/9745389/…

您忘记启用优化;对 store/reload everything to the stack 的调试版本进行基准测试没有用处。如果您想要希望使用 cmov 的高效标量汇编,请使用 gcc -O2 -fno-tree-vectorize -S。 (-O3 可能会自动矢量化,使用 GCC12 或更高版本的 -O2 也会如此。)另请参阅 gcc optimization flag -O3 makes code slower than -O2(对于已排序的情况,当它对 if 使用 cmov 时效果不佳)。

P
Peter Mortensen

如果您对可以对此代码进行的更多优化感到好奇,请考虑以下几点:

从原始循环开始:

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 倍。

P
Peter Mortensen

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

排序:

==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%   )

未分类:

==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 产生的逐行输出,我们看到有问题的循环:

排序:

          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];
           .      .  .   .          }
           .      .  .   .      }

未分类:

          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),而在排序版本中它仅导致 10,006 个。

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

perf stat ./sumtest_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

未分类:

 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

这很可怕,在未排序的列表中,应该有 50% 的机会点击添加。不知何故,分支预测只有 25% 的未命中率,它怎么能比 50% 的未命中率更好呢?

@tall.b.lo:25% 是所有分支的 - 循环中有 两个 分支,一个用于 data[c] >= 128(如您所建议的那样有 50% 的未命中率),一个用于循环条件 c < arraySize 的缺失率约为 0%。

请注意,基准测试/分析未优化(“调试模式”)代码通常是一个坏主意。通过优化,没有分支未命中的版本会更快,并且不会因局部变量的存储/重新加载延迟而停滞不前。但是,关键分支的实际分支错误预测率应该大致相同(假设有一个:现代编译器可以 vectorize this 或以其他方式制作无分支 asm)。循环展开可以通过减少运行可预测的循环分支来改变整体未命中率。

P
Palec

我刚刚阅读了这个问题及其答案,我觉得缺少答案。

我发现在托管语言中特别有效的消除分支预测的一种常用方法是使用表查找而不是使用分支(尽管在这种情况下我没有对其进行测试)。

这种方法通常在以下情况下有效:

它是一个小表,可能会缓存在处理器中,并且您正在以非常紧凑的循环运行事物和/或处理器可以预加载数据。

背景和原因

从处理器的角度来看,您的内存很慢。为了弥补速度上的差异,您的处理器中内置了几个高速缓存(L1/L2 高速缓存)。所以想象一下,你正在做你的漂亮计算,并发现你需要一块内存。处理器将执行其“加载”操作并将这块内存加载到缓存中——然后使用缓存来完成其余的计算。因为内存相对较慢,所以这个“负载”会减慢你的程序。

与分支预测一样,这在奔腾处理器中进行了优化:处理器预测它需要加载一段数据并尝试在操作实际命中缓存之前将其加载到缓存中。正如我们已经看到的那样,分支预测有时会出错——在最坏的情况下,您需要返回并实际等待内存加载,这将花费很长时间(换句话说:失败的分支预测是不好的,内存分支预测失败后加载太可怕了!)。

对我们来说幸运的是,如果内存访问模式是可预测的,处理器会将其加载到其快速缓存中,一切都很好。

我们首先要知道什么是小?虽然通常越小越好,但经验法则是坚持使用 <= 4096 字节大小的查找表。作为上限:如果您的查找表大于 64K,则可能值得重新考虑。

构建表

所以我们发现我们可以创建一个小表。接下来要做的是获得一个查找功能。查找函数通常是使用几个基本整数运算(和、或、异或、移位、加、删除甚至乘)的小函数。您希望通过查找功能将您的输入翻译成表格中的某种“唯一键”,然后它会简单地为您提供您希望它完成的所有工作的答案。

在这种情况下:>= 128 意味着我们可以保留该值,< 128 意味着我们摆脱它。最简单的方法是使用“AND”:如果我们保留它,我们用 7FFFFFFF 与它;如果我们想去掉它,我们用 0 与它。还要注意 128 是 2 的幂——所以我们可以继续制作一个包含 32768/128 整数的表,并用一个 0 和很多7FFFFFFFF 的。

托管语言

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

好吧,不完全是...... :-)

在消除托管语言的这个分支方面已经做了很多工作。例如:

for (int i = 0; i < array.Length; ++i)
{
   // Use array[i]
}

在这种情况下,编译器很明显永远不会遇到边界条件。至少 Microsoft JIT 编译器(但我希望 Java 会做类似的事情)会注意到这一点并完全删除检查。哇,这意味着没有分支。同样,它将处理其他明显的情况。

如果您在使用托管语言进行查找时遇到问题 - 关键是在查找函数中添加 & 0x[something]FFF 以使边界检查可预测 - 并观察它的运行速度。

本案结果

// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];

Random random = new Random(0);
for (int c = 0; c < arraySize; ++c)
{
    data[c] = random.Next(256);
}

/*To keep the spirit of the code intact, 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();
N
Neuron

由于在对数组进行排序时数据分布在 0 到 255 之间,因此大约前半部分的迭代不会进入 if 语句(if 语句在下面共享)。

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

问题是:是什么让上述语句在某些情况下不像排序数据那样执行?这里出现了“分支预测器”。分支预测器是一种数字电路,它试图猜测分支(例如 if-then-else 结构)在确定之前会走哪条路。分支预测器的目的是改善指令流水线中的流程。分支预测器在实现高效性能方面发挥着关键作用!

让我们做一些基准测试以更好地理解它

if 语句的性能取决于其条件是否具有可预测的模式。如果条件始终为真或始终为假,处理器中的分支预测逻辑将选择该模式。另一方面,如果模式不可预测,则 if 语句的开销会大得多。

让我们在不同的条件下测量这个循环的性能:

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-语句比“good”模式慢六倍!当然,哪种模式好,哪种模式不好取决于编译器和特定处理器生成的确切指令。

所以分支预测对性能的影响是毫无疑问的!

@MooingDuck'因为它不会产生影响-该值可以是任何值,但仍会在这些阈值的范围内。那么,当您已经知道限制时,为什么还要显示一个随机值呢?虽然我同意你可以为了完整性而展示一个,并且“只是为了它的见鬼”。

@cst1992:现在他最慢的时间是 TTFFTTFFTTFF,在我看来,这似乎是可以预测的。 Random 本质上是不可预测的,因此完全有可能它会更慢,因此超出此处显示的限制。 OTOH,可能是 TTFFTTFF 完美地击中了病理案例。不能说,因为他没有显示随机时间。

@MooingDuck 在人眼看来,“TTFFTTFFTTFF”是一个可预测的序列,但我们在这里谈论的是内置于 CPU 中的分支预测器的行为。分支预测器不是 AI 级别的模式识别;这很简单。当您只是交替分支时,它不能很好地预测。在大多数代码中,分支几乎总是以相同的方式进行。考虑一个执行一千次的循环。循环结束的分支回到循环开始 999 次,然后第 1000 次做了不同的事情。一个非常简单的分支预测器通常效果很好。

@steveha:我认为您正在对 CPU 分支预测器的工作方式做出假设,我不同意这种方法。我不知道那个分支预测器有多先进,但我似乎认为它比你先进得多。你可能是对的,但测量肯定会很好。

@steveha:两级自适应预测器可以毫无问题地锁定 TTFFTTFF 模式。 “大多数现代微处理器都使用这种预测方法的变体”。局部分支预测和全局分支预测基于两级自适应预测器,它们也可以。 “全局分支预测用于 AMD 处理器,以及基于 Intel Pentium M、Core、Core 2 和 Silvermont 的 Atom 处理器” 还将同意预测器、混合预测器、间接跳转预测添加到该列表中。循环预测器不会锁定,但会达到 75%。只剩下2个无法锁定

j
jakubde

避免分支预测错误的一种方法是构建一个查找表,并使用数据对其进行索引。 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 语句的版本快得多。

但是在我的测试中,显式查找表比这稍微快一点,可能是因为索引到查找表比位移略快。这显示了我的代码如何设置和使用查找表(代码中“查找表”的名称为 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 语句,可用于决定使用哪个指针。我看到一个实现二叉树的库,而不是有两个命名指针(pLeftpRight 或其他),而是有一个长度为 2 的指针数组,并使用“决策位”技术来决定遵循哪一个。例如,而不是:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

这个库会做类似的事情:

i = (x < node->value);
node = node->link[i];

这是此代码的链接:Red Black TreesEternally Confuzzled

是的,您也可以直接使用该位并相乘(data[c]>>7 - 此处也有讨论);我故意忽略了这个解决方案,但你当然是正确的。只是一个小提示:查找表的经验法则是,如果它适合 4KB(由于缓存),它会起作用 - 最好使表尽可能小。对于托管语言,我会将其推至 64KB,对于 C++ 和 C 等低级语言,我可能会重新考虑(这只是我的经验)。从 typeof(int) = 4 开始,我会尽量坚持最多 10 位。

我认为使用 0/1 值进行索引可能会比整数乘法更快,但我想如果性能真的很关键,你应该对其进行分析。我同意小型查找表对于避免缓存压力至关重要,但很明显,如果您有更大的缓存,您可以使用更大的查找表,因此 4KB 更多的是经验法则而不是硬性规则。我想你的意思是sizeof(int) == 4?这对于 32 位是正确的。我两岁的手机有一个 32KB 的 L1 缓存,所以即使是 4K 的查找表也可以工作,特别是如果查找值是一个字节而不是一个 int。

可能我遗漏了一些东西,但是在您的 j 等于 0 或 1 方法中,为什么不将值乘以 j 然后再添加它而不是使用数组索引(可能应该乘以 1-j 而不是j)

@steveha 乘法应该更快,我尝试在英特尔书籍中查找它,但找不到它......无论哪种方式,基准测试也在这里给了我这个结果。

@steveha PS:另一个可能的答案是 int c = data[j]; sum += c & -(c >> 7); ,它根本不需要乘法。

K
Konard

在排序的情况下,您可以比依赖成功的分支预测或任何无分支比较技巧做得更好:完全删除分支。

实际上,该阵列被划分在一个用 data < 128 和另一个用 data >= 128 的连续区域中。因此,您应该找到具有 dichotomic search 的分区点(使用 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];

一种更快的方法,它为排序或未排序提供 近似 解决方案:sum= 3137536;(假设真正均匀分布,16384 个样本,期望值为 191.5):-)

sum= 3137536 - 聪明。这显然不是问题的重点。问题显然是关于解释令人惊讶的性能特征。我倾向于说增加做 std::partition 而不是 std::sort 是有价值的。尽管实际问题不仅仅局限于给出的综合基准。

@DeadMG:这确实不是对给定键的标准二分搜索,而是对分区索引的搜索;它需要每次迭代进行一次比较。但是不要依赖这个代码,我没有检查过。如果您对有保证的正确实施感兴趣,请告诉我。

不需要对切点进行二进制搜索,只需从您想要保留的末尾开始求和,当您达到您不想要的值时停止。 (除非硬件预取在向下循环而不是向上循环时效果更差)。当然,实际上花时间进行排序并不是以未排序数据开始的算法的有用部分。直方图可能是,如果您想从相同的数据回答不同切点的多个查询,而不是 128 个。 (因为小值范围意味着这个小数组中有很多重复项。)

P
Peter Cordes

由于分支预测,上述行为正在发生。

要了解分支预测,首先必须了解指令流水线。

运行一条指令的步骤可以与运行上一条和下一条指令的步骤顺序重叠,从而可以并行并行执行不同的步骤。这种技术称为指令流水线,用于提高现代处理器的吞吐量。要更好地理解这一点,请参阅此example on Wikipedia

通常,现代处理器具有相当长(且宽)的管道,因此可以运行许多指令。请参阅 Modern Microprocessors A 90-Minute Guide!,它首先介绍了基本的有序流水线,然后从那里开始。

但为方便起见,让我们考虑一个仅包含这 4 个步骤的简单有序管道。
(类似于 classic 5-stage RISC,但省略了单独的 MEM 阶段。)

IF -- 从内存中取指令 ID -- 解码指令 EX -- 执行指令 WB -- 写回 CPU 寄存器

https://i.stack.imgur.com/PqBBR.png

回到上面的问题,让我们考虑以下说明:

                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().

如果没有分支预测,将发生以下情况:

为了执行指令 B 或指令 C,处理器必须等待(停止)直到指令 A 离开流水线中的 EX 阶段,因为执行指令 B 或指令 C 的决定取决于指令 A 的结果。从下一个获取。)因此管道将如下所示:

https://i.stack.imgur.com/0H4gP.png

https://i.stack.imgur.com/APpca.png

由于等待指令 A 的结果,在上述情况下花费的总 CPU 周期(没有分支预测;对于真和假)是 7。

那么什么是分支预测呢?

分支预测器将尝试猜测分支(if-then-else 结构)在确定之前会走哪条路。它不会等待指令 A 到达流水线的 EX 阶段,但它会猜测决定并转到该指令(在我们的示例中为 B 或 C)。

https://i.stack.imgur.com/ZYUbs.png

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

在OP的代码中,第一次有条件的时候,分支预测器没有任何信息来预测,所以第一次它会随机选择下一条指令。 (或者回退到静态预测,通常是向前不采用,向后采用)。稍后在 for 循环中,它可以根据历史记录进行预测。对于按升序排序的数组,有三种可能:

所有元素都小于 128 所有元素都大于 128 一些开始的新元素小于 128,后来它变得大于 128

让我们假设预测器在第一次运行时总是假设真正的分支。

所以在第一种情况下,它总是会选择真正的分支,因为历史上它的所有预测都是正确的。在第二种情况下,最初它会预测错误,但经过几次迭代后,它会正确预测。在第三种情况下,它最初会正确预测,直到元素小于 128。之后它会失败一段时间,当它在历史上看到分支预测失败时会自行纠正。

在所有这些情况下,失败的数量都会太少,因此,只有几次它需要丢弃部分执行的指令并从正确的分支重新开始,从而减少 CPU 周期。

但是在随机未排序数组的情况下,预测将需要丢弃部分执行的指令并在大多数情况下从正确的分支重新开始,并且与排序数组相比会导致更多的 CPU 周期。

进一步阅读:

现代微处理器 90 分钟指南!

Dan Luu 关于分支预测的文章(涵盖较旧的分支预测器,而不是现代 IT-TAGE 或感知器)

https://en.wikipedia.org/wiki/Branch_predictor

Branch Prediction and the Performance of Interpreters - Don't Trust Folklore - 2015 年的论文展示了 Intel 的 Haswell 在预测 Python 解释器主循环的间接分支方面的表现(由于不简单的模式而在历史上存在问题),而早期的 CPU没有使用 IT-TAGE。 (不过,它们对这种完全随机的情况没有帮助。当源被编译为分支 asm 时,Skylake CPU 上循环内的 if 仍然有 50% 的错误预测率。)

较新的 Intel 处理器上的静态分支预测 - CPU 在运行没有可用动态预测的分支指令时实际执行的操作。从历史上看,前向未采用(如 if 或 break),后向采用(如循环)已被使用,因为它总比没有好。布局代码以使快速路径/常见情况最小化所采用的分支对于 I-cache 密度和静态预测都有好处,因此编译器已经这样做了。 (这是 C 源代码中可能/不太可能提示的真实效果,实际上并未提示大多数 CPU 中的硬件分支预测,除非可能通过静态预测。)

两条指令如何一起执行?这是用单独的 cpu 内核完成的还是流水线指令集成在单个 cpu 内核中?

@M.kazemAkhgary 这一切都在一个逻辑核心中。如果您有兴趣,可以在 Intel Software Developer Manual 中很好地描述这一点

g
greatwolf

官方答案将来自

英特尔 - 避免分支错误预测的成本 英特尔 - 分支和循环重组以防止错误预测 科学论文 - 分支预测计算机架构 书籍:JL Hennessy,DA Patterson:计算机架构:定量方法 科学出版物中的文章:TY Yeh,YN Patt很多这些关于分支预测。

您还可以从这个可爱的 diagram 中看出为什么分支预测器会混淆。

https://i.stack.imgur.com/pBMV2.png

原始代码中的每个元素都是一个随机值

data[c] = std::rand() % 256;

因此预测器将在 std::rand() 打击时改变方向。

另一方面,一旦排序后,预测器将首先进入强烈不采用的状态,当值变为高值时,预测器将在三个运行中从强烈不采用到强烈采用变化。

S
Stacked

在同一行中(我认为任何答案都没有强调这一点)很高兴提到有时(特别是在性能很重要的软件中——比如在 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 次的错误情况,那么为什么不通知编译器呢?这样,默认情况下,分支预测会假设条件为假。

S
Sujal Patel

C++ 中常用的布尔运算在编译后的程序中产生许多分支。如果这些分支在循环内部并且难以预测,它们会显着减慢执行速度。布尔变量存储为 8 位整数,false 的值为 0true 的值为 1

布尔变量是超定的,因为所有将布尔变量作为输入的运算符都会检查输入是否具有除 01 之外的任何其他值,但将布尔变量作为输出的运算符只能产生 01。这使得以布尔变量作为输入的操作比必要的效率低。考虑示例:

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;
}

这段代码远非最佳。如果发生错误预测,分支可能需要很长时间。如果可以确定操作数除了 01 之外没有其他值,则布尔运算可以变得更加高效。编译器不做这种假设的原因是,如果变量未初始化或来自未知来源,它们可能具有其他值。如果 ab 已初始化为有效值,或者它们来自产生布尔输出的运算符,则可以优化上述代码。优化后的代码如下所示:

char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

使用 char 代替 bool 以便可以使用按位运算符(&|)代替布尔运算符(&&||)。位运算符是只占用一个时钟周期的单条指令。即使 ab 具有除 01 之外的其他值,OR 运算符 (|) 也有效。如果操作数的值不是 01,则 AND 运算符 (&) 和 EXCLUSIVE OR 运算符 (^) 可能会给出不一致的结果。

~ 不能用于 NOT。相反,您可以通过与 1 异或来对已知为 01 的变量进行布尔 NOT:

bool a, b;
b = !a;

可以优化为:

char a = 0, b;
b = a ^ 1;

如果 b 是一个不应在 afalse 时计算的表达式(&& 不会计算 b& 会),则 a && b 不能替换为 a & b。同样,如果 b 是一个不应在 atrue 时计算的表达式,则 a || b 不能替换为 a | b

如果操作数是变量,则使用位运算符比操作数是比较时更有利:

bool a; double x, y, z;
a = x > y && z < 5.0;

在大多数情况下是最优的(除非您期望 && 表达式会产生许多分支错误预测)。

C
Community

这是肯定的!...

由于代码中发生的切换,分支预测使逻辑运行速度变慢!这就像你要走一条笔直的街道或一条有很多转弯的街道,肯定会更快地完成笔直的!...

如果数组已排序,则您的条件在第一步中为假:data[c] >= 128,然后在整个到街道尽头的过程中变为真值。这就是你如何更快地到达逻辑的结尾。另一方面,使用未排序的数组,您需要大量的转动和处理,这肯定会使您的代码运行速度变慢......

看看我在下面为你创建的图像。哪条街会更快完工?

https://i.stack.imgur.com/cSmCa.jpg

所以以编程方式,分支预测会导致过程变慢......

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

1.静态

2.动态

https://i.stack.imgur.com/ZfhDu.jpg

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

D
Deduplicator

这个问题已经被很好地回答了很多次了。我仍然想提请小组注意另一个有趣的分析。

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

链接在这里:A Demonstration of Self-Profiling

那是一篇很有趣的文章(其实我也刚看完),但是它是如何回答这个问题的呢?

@PeterMortensen 我对你的问题有点困惑。例如,这里是那篇文章中的一个相关行:When the input is unsorted, all the rest of the loop takes substantial time. But with sorted input, the processor is somehow able to spend not just less time in the body of the loop, meaning the buckets at offsets 0x18 and 0x1C, but vanishingly little time on the mechanism of looping. 作者试图在此处发布的代码上下文中讨论分析,并在此过程中试图解释为什么排序案例要快得多。

E
Eugene

正如其他人已经提到的,神秘的背后是Branch Predictor

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

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

https://i.stack.imgur.com/unxnb.png

基于所描述的场景,我编写了一个动画演示来展示指令在不同情况下如何在管道中执行。

没有分支预测器。

如果没有分支预测,处理器将不得不等到条件跳转指令通过执行阶段,然后下一条指令才能进入流水线中的取指阶段。

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

https://i.stack.imgur.com/GMFQ6.gif

完成 3 条指令需要 9 个时钟周期。

使用分支预测器,不要进行条件跳转。让我们假设预测没有进行条件跳转。

https://i.stack.imgur.com/Ms5p1.gif

完成 3 条指令需要 7 个时钟周期。

使用分支预测器并进行条件跳转。让我们假设预测没有进行条件跳转。

https://i.stack.imgur.com/HIpG3.gif

完成 3 条指令需要 9 个时钟周期。

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

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

这是一个非常简单的演示,阐明了分支预测器的基本部分。如果这些 GIF 令人讨厌,请随时从答案中删除它们,访问者还可以从 BranchPredictorDemo 获取实时演示源代码

几乎和英特尔的营销动画一样好,他们不仅痴迷于分支预测,而且痴迷于乱序执行,这两种策略都是“投机”的。在内存和存储中提前读取(顺序预取到缓冲区)也是推测性的。这一切都加起来了。

@mckenzm:乱序推测执行使分支预测更有价值;除了隐藏提取/解码气泡外,分支预测 + 推测执行还消除了关键路径延迟中的控制依赖关系。 if() 块内部或之后的代码可以在分支条件已知之前执行。或者对于像 strlenmemchr 这样的搜索循环,交互可以重叠。如果在运行任何下一次迭代之前必须等待知道匹配或不匹配结果,那么您将成为缓存负载 + ALU 延迟而不是吞吐量的瓶颈。

您是否使用 JavaFX 制作了示例应用程序?

@HannaMcquaig 不,它是 Swing 制作的。代码可在 github.com/Eugene-Mark/branch-predictor-demo 获得。

C
Community

分支预测增益!

重要的是要了解分支错误预测不会减慢程序的速度。错过预测的代价就好像分支预测不存在并且您等待表达式的评估来决定运行什么代码(下一段中的进一步解释)。

if (expression)
{
    // Run 1
} else {
    // Run 2
}

只要有 if-else \ switch 语句,就必须计算表达式以确定应该执行哪个块。在编译器生成的汇编代码中,插入了条件 branch 指令。

分支指令可能导致计算机开始执行不同的指令序列,从而偏离其按顺序执行指令的默认行为(即,如果表达式为假,程序将跳过 if 块的代码),具体取决于某些条件,这是我们案例中的表达式评估。

话虽如此,编译器会在实际评估结果之前尝试预测结果。它将从 if 块中获取指令,如果表达式结果为真,那就太好了!我们获得了评估它所需的时间,并在代码中取得了进展;如果不是,那么我们运行了错误的代码,刷新了管道,运行了正确的块。

可视化:

假设您需要选择路线 1 或路线 2。等待您的伙伴查看地图时,您已在 ## 停下来等待,或者您可以选择路线 1,如果幸运的话(路线 1 是正确的路线),那么太好了,您不必等待您的搭档检查地图(您节省了他检查地图的时间),否则您只会折返。

虽然冲洗管道的速度非常快,但如今赌一把是值得的。预测排序数据或变化缓慢的数据总是比预测快速变化更容易和更好。

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------

虽然冲洗管道超级快 不是真的。与一直到 DRAM 的缓存未命中相比,它的速度很快,但在现代高性能 x86(如英特尔 Sandybridge 系列)上,它大约需要十几个周期。尽管快速恢复确实允许它避免在开始恢复之前等待所有较旧的独立指令达到退休,但您仍然会因错误预测而损失大量前端周期。 What exactly happens when a skylake CPU mispredicts a branch?。 (并且每个周期大约可以执行 4 条工作指令。)对高吞吐量代码不利。

L
Luke Hutchison

在 ARM 上,不需要分支,因为每条指令都有一个 4 位条件字段,它测试(以零成本)处理器状态寄存器中可能出现的任何 16 different different conditions,以及指令上的条件是否为假, 指令被跳过。这消除了对短分支的需要,并且该算法不会有分支预测命中。 因此,由于排序的额外开销,该算法的排序版本在 ARM 上的运行速度会比未排序的版本慢。

该算法的内部循环在 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

但这实际上是更大图景的一部分:

CMP 操作码总是更新处理器状态寄存器 (PSR) 中的状态位,因为这是它们的目的,但大多数其他指令不会触及 PSR,除非您在指令中添加可选的 S 后缀,指定 PSR应根据指令的结果进行更新。 就像 4 位条件后缀一样,能够在不影响 PSR 的情况下执行指令是一种减少 ARM 上分支需求的机制,也便于在硬件层面进行乱序调度,因为在执行了一些更新状态位的操作 X 之后,随后(或并行)您可以做一堆其他明确不应该影响(或受其影响)状态位的工作,然后您可以测试状态位的状态由 X 提前设置。

条件测试字段和可选的“设置状态位”字段可以组合,例如:

ADD R1、R2、R3 执行 R1 = R2 + R3 而不更新任何状态位。

仅当影响状态位的先前指令导致大于或等于条件时,ADDGE R1、R2、R3 才会执行相同的操作。

ADDS R1、R2、R3 执行加法,然后根据结果是负数、零、进位(无符号加法)还是溢出(有符号加法)更新处理器状态寄存器中的 N、Z、C 和 V 标志.

ADDSGE R1、R2、R3 仅在 GE 测试为真时执行加法,然后根据加法结果更新状态位。

大多数处理器架构没有这种能力来指定是否应该为给定操作更新状态位,这可能需要编写额外的代码来保存和稍后恢复状态位,或者可能需要额外的分支,或者可能会限制处理器的输出顺序执行效率:大多数 CPU 指令集架构在大多数指令之后强制更新状态位的副作用之一是,很难区分哪些指令可以并行运行而不会相互干扰。更新状态位有副作用,因此对代码有线性化影响。 ARM 在任何指令上混合和匹配无分支条件测试以及在任何指令之后更新或不更新状态位的选项的能力对于汇编语言程序员和编译器来说都非常强大,并且可以生成非常高效的代码。

当您不必分支时,您可以避免因短分支而刷新管道的时间成本,并且可以避免多种形式的推测评估的设计复杂性。许多最近发现的处理器漏洞(Spectre 等)的缓解措施的初始简单实施对性能的影响向您展示了现代处理器的性能在多大程度上取决于复杂的推测评估逻辑。凭借较短的流水线和大幅减少的分支需求,ARM 不需要像 CISC 处理器那样依赖推测评估。 (当然,高端 ARM 实现确实包括推测性评估,但它只是性能故事的一小部分。)

如果您曾经想知道为什么 ARM 取得了如此惊人的成功,那么这两种机制的出色效率和相互作用(与另一种机制相结合,可以让您向左或向右“桶移”任何算术运算符或偏移内存访问的两个参数之一)零额外成本的运营商)是故事的重要组成部分,因为它们是 ARM 架构效率的一些最大来源。早在 1983 年,ARM ISA 的原始设计师 Steve Furber 和 Roger(现为 Sophie)Wilson 的才华怎么强调都不为过。

ARM 中的另一项创新是添加了 S 指令后缀,它在(几乎)所有指令上也是可选的,如果不存在,则会阻止指令更改状态位(CMP 指令除外,其工作是设置状态位,所以它不需要 S 后缀)。这允许您在许多情况下避免 CMP 指令,只要比较为零或相似(例如,当 R0 达到零时,SUBS R0、R0、#1 将设置 Z(零)位)。条件和 S 后缀产生零开销。这是一个相当漂亮的ISA。

不添加 S 后缀可以让您连续拥有多个条件指令,而不必担心其中一个可能会更改状态位,否则可能会产生跳过其余条件指令的副作用。

请注意,OP 不包括在其测量中排序的时间。在运行分支 x86 循环之前先排序也可能是一个整体损失,即使未排序的情况使循环运行得更慢。但是对一个大数组进行排序需要大量的工作。

顺便说一句,您可以通过相对于数组末尾的索引来保存循环中的指令。在循环之前,设置 R2 = data + arraySize,然后从 R1 = -arraySize 开始。循环的底部变为 adds r1, r1, #1 / bnz inner_loop。编译器出于某种原因不使用此优化:/ 但无论如何,在这种情况下,add 的谓词执行与您可以在其他 ISA(如 x86 cmov)上使用无分支代码执行的操作没有根本的不同。虽然它不是那么好:gcc optimization flag -O3 makes code slower than -O2

(ARM 谓词执行确实 NOP 指令,因此您甚至可以在会出错的加载或存储上使用它,这与带有内存源操作数的 x86 cmov 不同。大多数 ISA,包括 AArch64,只有 ALU 选择操作。所以 ARM 谓词可以比大多数 ISA 上的无分支代码更强大,更有效地使用。)

P
Peter Cordes

这是关于分支预测的。它是什么?

分支预测器是一种古老的性能改进技术,它仍然在现代架构中找到相关性。虽然简单的预测技术提供了快速查找和功率效率,但它们的误预测率很高。

另一方面,复杂的分支预测——无论是基于神经的还是两级分支预测的变体——提供了更好的预测精度,但它们消耗更多的能量并且复杂度呈指数级增长。

除此之外,在复杂的预测技术中,预测分支所花费的时间本身就非常高——从 2 到 5 个周期不等——这与实际分支的执行时间相当。

分支预测本质上是一个优化(最小化)问题,其重点在于以最少的资源实现尽可能低的未命中率、低功耗和低复杂度。

实际上有三种不同的分支:

前向条件分支 - 基于运行时条件,PC(程序计数器)更改为指向指令流中的前向地址。

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

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

静态/动态分支预测:微处理器第一次遇到条件分支时使用静态分支预测,而动态分支预测用于条件分支代码的后续执行。

参考:

分支预测器

自我剖析的示范

分支预测回顾

分支预测(使用回路机)

Y
Yochai Timmer

除了分支预测可能会减慢您的速度之外,排序数组还有另一个优点:

您可以有一个停止条件,而不仅仅是检查值,这样您就只循环相关数据,而忽略其余数据。分支预测只会错过一次。

 // sort backwards (higher values first), may be in some other part of the code
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }

是的,但是对数组进行排序的设置成本是 O(N log N),所以如果你对数组进行排序的唯一原因是能够早点中断,那么早点中断对你没有帮助。但是,如果您有其他理由对数组进行预排序,那么是的,这很有价值。

取决于您对数据进行排序的次数与循环次数的比较。这个例子中的排序只是一个例子,它不必在循环之前

是的,这正是我在第一条评论中提出的观点 :-) 你说“分支预测只会错过一次”。但是您没有计算排序算法中的 O(N log N) 分支预测未命中,这实际上大于未排序情况下的 O(N) 分支预测未命中。因此,您需要使用整个排序数据 O(log N) 次来收支平衡(实际上可能更接近 O(10 log N),具体取决于排序算法,例如快速排序,由于缓存未命中 - 合并排序缓存更一致,因此您需要更接近 O(2 log N) 的使用量才能达到收支平衡。)

不过,一项重要的优化是只进行“半快速排序”,只对小于目标枢轴值 127 的项目进行排序(假设小于或等于枢轴的所有内容都在枢轴之后排序)。到达枢轴后,将枢轴之前的元素求和。这将在 O(N) 启动时间而不是 O(N log N) 中运行,尽管仍然会有很多分支预测未命中,根据我之前给出的数字可能是 O(5 N) 的数量级,因为这是半个快速排序。

来这里寻找这个确切的答案。提前中止是排序的主要原因。完全限制搜索空间。在我的测试中,由于能够在循环中更早地停止查找,它再次快了 2 倍。

D
Deduplicator

由于称为分支预测的现象,排序数组的处理速度比未排序数组快。

分支预测器是一个数字电路(在计算机体系结构中),试图预测分支将走向哪条路,从而改善指令流水线中的流程。电路/计算机预测下一步并执行它。

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

你的问题的答案很简单。

在未排序的数组中,计算机会做出多个预测,从而导致出错的机会增加。而在排序数组中,计算机做出的预测更少,从而减少了出错的机会。做出更多预测需要更多时间。

排序数组:直路

____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

未排序的数组:弯曲的道路

______   ________
|     |__|

分支预测:猜测/预测哪条路是直的,并在不检查的情况下跟随它

___________________________________________ Straight road
 |_________________________________________|Longer road

虽然两条路都到达同一个目的地,但笔直的路较短,而另一条路较长。如果那时你选错了,那就没有回头路了,如果你选择更长的路,你会浪费一些额外的时间。这类似于计算机中发生的情况,我希望这有助于您更好地理解。

我还想从评论中引用 @Simon_Weaver

它不会做出更少的预测——它会做出更少的错误预测。它仍然必须通过循环预测每次......

P
Peter Mortensen

我在 MacBook Pro(Intel i7,64 位,2.4 GHz)上使用 MATLAB 2011b 对以下 MATLAB 代码尝试了相同的代码:

% Processing time with Sorted data vs unsorted data
%==========================================================================
% Generate data
arraySize = 32768
sum = 0;
% Generate random integer data from range 0 to 255
data = randi(256, arraySize, 1);


%Sort the data
data1= sort(data); % data1= data  when no sorting done


%Start a stopwatch timer to measure the execution time
tic;

for i=1:100000

    for j=1:arraySize

        if data1(j)>=128
            sum=sum + data1(j);
        end
    end
end

toc;

ExeTimeWithSorting = toc - tic;

上述MATLAB代码的结果如下:

  a: Elapsed time (without sorting) = 3479.880861 seconds.
  b: Elapsed time (with sorting ) = 2377.873098 seconds.

@GManNickG 中的 C 代码结果我得到:

  a: Elapsed time (without sorting) = 19.8761 sec.
  b: Elapsed time (with sorting ) = 7.37778 sec.

基于此,看起来 MATLAB 比没有排序的 C 实现慢了近 175 倍,而使用排序则慢了 350 倍。换句话说,(分支预测的)效果对于 MATLAB 实现是 1.46 倍,对于 C 实现是 2.7 倍。

只是为了完整起见,这可能不是您在 Matlab 中实现的方式。我敢打赌,如果在对问题进行矢量化之后完成它会快得多。

Matlab 在许多情况下会自动并行化/矢量化,但这里的问题是检查分支预测的效果。无论如何,Matlab 也不能幸免!

matlab 是使用本机数字还是 matlab 特定的实现(无限位数左右?)

u
user2297550

其他答案的假设需要对数据进行排序是不正确的。

以下代码不会对整个数组进行排序,而是仅对其中的 200 个元素段进行排序,因此运行速度最快。

仅对 k 元素部分进行排序以线性时间 O(n) 完成预处理,而不是对整个数组进行排序所需的 O(n.log(n)) 时间。

#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;
}

这也“证明”了它与排序顺序等任何算法问题无关,确实是分支预测。

我真的不明白这如何证明什么?您所展示的唯一一件事是“不完成对整个数组进行排序的所有工作比对整个数组进行排序花费的时间更少”。您声称这“也运行得最快”是非常依赖于架构的。请参阅我关于这如何在 ARM 上工作的回答。 PS,您可以通过将总和放入 200 个元素的块循环中,反向排序,然后使用 Yochai Timmer 的建议,即一旦您获得超出范围的值就中断,从而使您的代码在非 ARM 架构上更快。这样每个 200 元素块求和可以提前终止。

如果您只想在未排序的数据上有效地实现该算法,您可以无分支地执行该操作(并使用 SIMD,例如使用 x86 pcmpgtb 来查找设置了高位的元素,然后将较小的元素归零)。花任何时间实际排序块会更慢。无分支版本将具有独立于数据的性能,也证明成本来自分支错误预测。或者直接使用性能计数器来观察,例如 Skylake int_misc.clear_resteer_cyclesint_misc.recovery_cycles 来计算来自错误预测的前端空闲周期

上面的两条评论似乎都忽略了一般的算法问题和复杂性,而是提倡使用特殊机器指令的专用硬件。我发现第一个特别琐碎,因为它盲目地支持专门的机器指令,而轻率地忽略了这个答案中重要的一般见解。

另请注意,如果 if 中的计算比简单的加法更复杂(这在一般情况下很可能),则专用硬件指令无济于事。因此,这个答案在提供仍然是 O(n) 的通用解决方案方面是独一无二的

仅作记录,因为我们之前的评论已经被核弹了,我不认为通过花时间(部分)排序来获得整体性能,除非你人为地重复循环像这个微基准测试中的数组。那么是的,这种分段排序接近于完整排序的优势(例如,在 Skylake 上,此分段排序为 2.4 秒,完整排序为 1.7 秒,在执行 10 万次之前没有排序为 10.9 秒。如果您使用 g++ -Os -Wa,-mbranches-within-32B-boundaries首先制作分支汇编而不是正常构建)。

2
2 revs, 2 users 75%

Bjarne Stroustrup's Answer回答这个问题:

这听起来像是一个面试问题。这是真的吗?你怎么知道的?不先进行一些测量就回答有关效率的问题是一个坏主意,因此了解如何测量很重要。

因此,我尝试使用一百万个整数的向量并得到:

Already sorted    32995 milliseconds
Shuffled          125944 milliseconds

Already sorted    18610 milliseconds
Shuffled          133304 milliseconds

Already sorted    17942 milliseconds
Shuffled          107858 milliseconds

我跑了几次以确定。是的,这种现象是真实的。我的关键代码是:

void run(vector<int>& v, const string& label)
{
    auto t0 = system_clock::now();
    sort(v.begin(), v.end());
    auto t1 = system_clock::now();
    cout << label
         << duration_cast<microseconds>(t1 — t0).count()
         << " milliseconds\n";
}

void tst()
{
    vector<int> v(1'000'000);
    iota(v.begin(), v.end(), 0);
    run(v, "already sorted ");
    std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
    run(v, "shuffled    ");
}

至少这种现象在这个编译器、标准库和优化器设置中是真实的。不同的实现可以并且确实给出不同的答案。事实上,有人确实进行了更系统的研究(快速的网络搜索会找到它)并且大多数实现都显示了这种效果。

一个原因是分支预测:排序算法中的关键操作是 “if(v[i] < pivot]) …” 或等价的。对于测试总是正确的排序序列,而对于随机序列,选择的分支随机变化。

另一个原因是当向量已经排序时,我们永远不需要将元素移动到正确的位置。这些小细节的影响就是我们看到的五六倍。

快速排序(以及一般的排序)是一项复杂的研究,吸引了一些计算机科学界最伟大的思想家。一个好的排序函数是选择一个好的算法和在其实现中注意硬件性能的结果。

如果你想编写高效的代码,你需要对机器架构有所了解。

这似乎错过了问题的重点,并且正在回答排序本身是否对已经排序的数组更快。这并不令人惊讶,因为正如这个答案所指出的那样,除了分支预测效应之外,还有更少的工作要做(使用除合并排序之外的大多数排序算法)。实际问题排除了这种影响,并且只是为有条件的增量计时。

P
Peter Cordes

这个问题源于 CPU 上的分支预测模型。我建议阅读这篇论文:

Increasing the Instruction Fetch Rate via Multiple Branch Prediction and a Branch Address Cache(但现在真正的 CPU 仍然不会在每个时钟周期进行多次采用的分支预测,除了 Haswell 和后来的 effectively unrolling tiny loops in its loop buffer。现代 CPU 可以预测多个未采用的分支以在大范围内使用它们的提取块。)

当您对元素进行排序后,分支预测很容易正确预测(除了在边界处),让指令有效地流过 CPU 管道,而无需回退并在错误预测时采取正确的路径。

不管错误预测如何,指令在 CPU 的 L1 指令高速缓存中都保持热状态。问题是在紧接前一条指令解码并完成执行之前,以正确的顺序将它们提取到管道中。

此外,在具有“指令寄存器”的简单 CPU 中,作为执行指令的一部分,它肯定总是需要将每条指令读入 IR。这个答案的最后一段与 CPU 的实际工作方式有很大的不同。一些带有循环缓冲区的 CPU 可能能够将一系列指令锁定到一个循环中,以避免从 L1i 缓存中重新获取,只要它们继续以相同的方式执行,但这通常是次要的(例如,在 Intel Skylake禁用LSD的微码更新并没有太大伤害),只是从正确的分支预测中获得更多价值。

该论文从 o(n) 的角度给出了它如何处理将协调数据作为指令获取的一般概念,它也是在 90 年代初编写的,因此当时不存在任何尖端的内存/寄存器设计。现代 CPU 缓存设计和算法可以在多篇论文中找到,其中一篇可能是 ieeexplore.ieee.org/document/1027060?arnumber=1027060

我不是在谈论链接论文的内容,而是在谈论您实际答案中的句子,特别是最后一段。 (您的答案中的论文发表于 1993 年,并提到了超标量 CPU 和 cpu 架构的未来方向,因此乱序 exec 即将出现,它肯定假设并行获取和解码多条指令。事实上,这就是他们提议的全部要点;在更广泛的设计中查看每个时钟周期的多个分支,将它们从 L1i 缓存中提取到管道中。当前的 CPU 仍然不这样做。)

G
Günter Zöchbauer

快速简单理解的答案(阅读其他内容了解更多详细信息)

这个概念称为分支预测

分支预测是一种优化技术,可以在确定代码之前预测代码将采用的路径。这很重要,因为在代码执行期间,机器会预取几个代码语句并将它们存储在管道中。

问题出现在条件分支中,其中有两个可能的路径或可以执行的代码部分。

当预测为真时,优化技术就奏效了。

当预测错误时,简单来说,存储在管道中的代码语句被证明是错误的,并且必须完全重新加载实际代码,这会占用大量时间。

正如常识所暗示的那样,对已排序事物的预测比对未排序事物的预测要准确得多。

分支预测可视化:

https://i.stack.imgur.com/BhphM.png

应该是在排序的火车轨道/执行路径的中间附近发生的变化,因为循环内的分支被用于前半部分,而不是用于后半部分元素。 (反之亦然。)此外,未排序情况下的 5 个不同级别是什么意思?这是一个2路分支。

M
Muhammad Ali

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

代码示例:

// CPP program to demonstrate processing
// time of sorted and unsorted array
#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;

const int N = 100001;

int main()
{
    int arr[N];

    // Assign random values to array
    for (int i=0; i<N; i++)
        arr[i] = rand()%N;

    // for loop for unsorted array
    int count = 0;
    double start = clock();
    for (int i=0; i<N; i++)
        if (arr[i] < N/2)
            count++;

    double end = clock();
    cout << "Time for unsorted array :: "
        << ((end - start)/CLOCKS_PER_SEC)
        << endl;
    sort(arr, arr+N);

    // for loop for sorted array
    count = 0;
    start = clock();

    for (int i=0; i<N; i++)
        if (arr[i] < N/2)
            count++;

    end = clock();
    cout << "Time for sorted array :: "
        << ((end - start)/CLOCKS_PER_SEC)
        << endl;

    return 0;
}

执行时间:

https://i.stack.imgur.com/9kOtq.png

结论:

请注意,与未排序数组相比,处理排序数组所花费的时间更少。对排序数组进行这种优化的原因是分支预测。

什么是分支预测?

计算机体系结构中的分支预测侧重于确定程序指令管道中的条件分支(跳转)是否可能被采用。因为它们必须在当前指令执行之前猜测要获取的地址字段,所以所有流水线处理器都以某种方式进行分支预测。

分支预测如何不适用于上述情况?

if 条件检查 arr[i] < 5000,但如果您观察排序数组的情况,在传递数字 5000 之后条件始终为假,而在此之前,它始终为真。 CPU 将识别该模式并能够正确预测在条件分支之后接下来执行哪条指令,而不是有时不得不在猜错后倒退。

分支预测算法的工作:

分支预测适用于算法遵循的模式或基本上是历史,它在前面的步骤中是如何执行的。如果猜测正确,则 CPU 继续执行,如果出错,则 CPU 需要刷新管道并回滚到分支并从头开始重新启动。

编译器在此处优化代码并跳过 if 条件。不,分支预测(和分支错误预测)是运行时效应。如果编译器知道它已排序,它可以进行循环裂变优化并进行两个循环,一个只搜索第一个错误情况,另一个只运行数组的其余部分。 (或者我想优化掉第二个循环,因为它是空的。)

示例 2 与分支预测有什么关系?您正在将线性搜索与二进制搜索和类似算法进行比较。人工搜索巨大的排序列表通常不是通过按顺序扫描每个条目来完成的。一旦你到达正确的页面,你就会这样做,在这种情况下,是的,你会向下扫描一列,直到你找到它或看到你已经过去,例如约翰斯顿,是的,你可以以一种方式快速扫描类似于线性搜索。但实际上您并没有完全查看每个条目,因此即使这样也不是一个完美的类比。

这个答案增加了现有答案中缺少的什么?

@GManNickG 这个答案以一种简单易懂的方式解释。