26250

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

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


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

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

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


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

4

28 回答 28

33859

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


什么是分支预测?

考虑一个铁路枢纽:

显示铁路枢纽的图像 图片由 Mecanismo 提供,来自 Wikimedia Commons。在CC-By-SA 3.0许可下使用。

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

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

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

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

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

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


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

包含 if 语句的已编译代码的屏幕截图

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

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

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

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

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


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

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

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

大多数应用程序都有良好的分支。因此,现代分支预测器通常会达到 >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[]。)

基准测试: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 实际上比使用分支慢一点。

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


更新:

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

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

  • 即使在/Ox.

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

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

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

于 2012-06-27T13:56:42.820 回答
4465

分支预测。

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

于 2012-06-27T13:54:45.240 回答
3623

数据排序后性能显着提高的原因是分支预测惩罚被删除,正如Mysticial 的回答中所解释的那样。

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

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

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

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

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

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

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

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

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

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

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

于 2012-06-28T02:14:03.600 回答
2491

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

从原始循环开始:

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

于 2012-07-03T02:25:30.523 回答
2046

毫无疑问,我们中的一些人会对识别对 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)
...

有关更多详细信息,请参阅性能教程

于 2012-10-12T05:53:33.240 回答
1493

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

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

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

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

背景和原因

从处理器的角度来看,您的内存很慢。为了弥补速度上的差异,您的处理器中内置了几个高速缓存(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();
于 2013-04-24T06:26:28.820 回答
1334

由于在数组排序时数据分布在 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

“<strong>bad”真假模式可以if比“<strong>good”模式慢六倍!当然,哪种模式好,哪种模式不好取决于编译器和特定处理器生成的确切指令。

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

于 2013-02-15T07:24:16.033 回答
1267

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

于 2013-07-22T08:29:30.290 回答
1140

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

实际上,该阵列被划分在一个连续的区域中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];

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

于 2013-07-24T07:57:39.443 回答
934

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

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

任何指令都被分解为一系列步骤,以便不同的步骤可以同时并行执行。这种技术被称为指令流水线,用于增加现代处理器的吞吐量。为了更好地理解这一点,请在 Wikipedia 上查看此示例

通常,现代处理器的流水线很长,但为了方便起见,我们只考虑这 4 个步骤。

  1. IF——从内存中获取指令
  2. ID——解码指令
  3. EX -- 执行指令
  4. WB——写回CPU寄存器

4 级流水线一般用于 2 条指令。 一般4级流水线

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

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

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

要执行指令 B 或指令 C,处理器必须等到指令 A 未到达流水线中的 EX 阶段,因为执行指令 B 或指令 C 的决定取决于指令 A 的结果。所以流水线看起来像这样。

当 if 条件返回 true 时: 在此处输入图像描述

当 if 条件返回 false 时: 在此处输入图像描述

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

那么什么是分支预测呢?

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

如果猜对了,管道看起来像这样: 在此处输入图像描述

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

在OP的代码中,第一次有条件的时候,分支预测器没有任何信息来预测,所以第一次它会随机选择下一条指令。稍后在 for 循环中,它可以根据历史记录进行预测。对于按升序排序的数组,有三种可能:

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

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

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

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

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

于 2015-07-03T15:35:52.687 回答
827

官方答案将来自

  1. 英特尔 - 避免分支错误预测的成本
  2. 英特尔 - 分支和循环重组以防止错误预测
  3. 科学论文——分支预测计算机架构
  4. 书籍:JL Hennessy、DA Patterson:计算机体系结构:定量方法
  5. 科学出版物中的文章:TY Yeh、YN Patt 在分支预测方面做了很多这样的文章。

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

2位状态图

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

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

所以预测器会随着std::rand()打击而改变方向。

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


于 2015-10-11T21:05:18.123 回答
797

在同一行中(我认为任何答案都没有强调这一点)很高兴提到有时(特别是在性能很重要的软件中——比如在 Linux 内核中)你可以找到一些 if 语句,如下所示:

if (likely( everything_is_ok ))
{
    /* Do something */
}

或类似地:

if (unlikely(very_improbable_condition))
{
    /* Do something */    
}

两者实际上都是使用 GCC 之类的东西定义的宏,likely()以帮助编译器插入预测代码以支持考虑用户提供的信息的条件。GCC 支持其他可以改变正在运行的程序的行为或发出低级指令(如清除缓存等)的内置指令。请参阅此文档,了解可用的 GCC 内置指令。unlikely()__builtin_expect

通常这种优化主要出现在执行时间很重要且至关重要的硬实时应用程序或嵌入式系统中。例如,如果您正在检查仅发生 1/10000000 次的错误情况,那么为什么不通知编译器呢?这样,默认情况下,分支预测会假设条件为假。

于 2015-09-23T14:57:47.163 回答
781

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

布尔变量在某种意义上是超定的,即所有将布尔变量作为输入的运算符都会检查输入是否具有除0or之外的任何其他值1,但将布尔变量作为输出的运算符不能产生除0or之外的任何其他值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以便可以使用按位运算符 ( &and |) 代替布尔运算符 ( &&and ||)。位运算符是只占用一个时钟周期的单条指令。OR 运算符 ( |) 即使a并且具有除orb以外的其他值也可以工作。如果操作数具有除and以外的其他值,AND 运算符 ( ) 和 EXCLUSIVE OR 运算符 ( ) 可能会给出不一致的结果。01&^01

~不能用于 NOT。相反,您可以在已知为的变量上创建布尔值 NOT01通过对它进行 XOR 运算1

bool a, b;
b = !a;

可以优化为:

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

a && b不能替换为a & bif bis 一个不应该被评估的表达式 if ais false( &&will not evaluate b, &will)。同样,a || b不能替换为a | bif bis 一个不应评估 if is 的a表达式true

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

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

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

于 2015-10-10T00:30:42.687 回答
435

这是肯定的!...

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

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

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

分支预测

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

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

1.静态

2.动态

分支预测

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

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

于 2017-06-18T11:40:43.007 回答
399

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

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

链接在这里: 自我分析的演示

于 2017-01-12T01:50:28.280 回答
361

正如其他人已经提到的,神秘的背后是分支预测器

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

在计算机体系结构中,分支预测器是一个数字电路,它试图猜测分支(例如 if-then-else 结构)在确定之前会走哪条路。分支预测器的目的是改善指令流水线中的流程。分支预测器在许多现代流水线微处理器架构(如 x86)中实现高效性能方面发挥着关键作用。

双向分支通常使用条件跳转指令来实现。条件跳转可以“不执行”并继续执行条件跳转后紧跟的第一个代码分支,也可以“执行”并跳转到程序内存中第二个代码分支所在的不同位置存储。在计算出条件并且条件跳转已经通过指令流水线中的执行阶段之前,是否会进行条件跳转是不确定的(见图 1)。

图1

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

  1. 没有分支预测器。

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

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

没有分支预测器

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

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

在此处输入图像描述

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

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

在此处输入图像描述

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

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

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

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

于 2017-11-06T16:15:16.070 回答
275

分支预测增益!

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

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

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

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

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

可视化:

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

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

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------
于 2017-08-04T10:07:12.513 回答
238

在 ARM 上,不需要分支,因为每条指令都有一个 4 位条件字段,它测试(以零成本)处理器状态寄存器中可能出现的16 种不同不同条件中的任何一种,以及指令上的条件是否为false,该指令被跳过。这消除了对短分支的需要,并且该算法不会有分支预测命中。因此,由于排序的额外开销,该算法的排序版本将比 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执行加法,然后根据结果是负数、零、进位(无符号加法)或溢出(有符号加法)更新处理器状态寄存器中的NZ和标志。CV
  • ADDSGE R1, R2, R3仅当测试为真时才执行加法GE,然后根据加法结果更新状态位。

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

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

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

于 2017-12-22T13:13:05.870 回答
214

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

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

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

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

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

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

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

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

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

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

参考:

于 2017-10-03T09:47:54.423 回答
205

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

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

 // 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];               
 }
于 2017-11-23T14:28:29.353 回答
188

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

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

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

你的问题的答案很简单。

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

排序数组:直路

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

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

______   ________
|     |__|

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

___________________________________________ Straight road
 |_________________________________________|Longer road

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


我还想从评论中引用@Simon_Weaver

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

于 2017-12-07T17:28:29.557 回答
173

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

于 2012-12-30T16:16:46.597 回答
110

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

以下代码不会对整个数组进行排序,而是仅对其中的 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;
}

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

于 2018-12-09T06:18:17.047 回答
96
于 2019-10-14T23:34:40.167 回答
87

This question is rooted in branch prediction models on CPUs. I'd recommend reading this paper:

Increasing the Instruction Fetch Rate via Multiple Branch Prediction and a Branch Address Cache

When you have sorted elements, the IR can not be bothered to fetch all CPU instructions, again and again. It fetches them from the cache.

于 2019-10-23T21:35:40.250 回答
23

BRANCH PREDICTION

This is called branch prediction. Without branch prediction, the processor would have to wait until the conditional jump instruction has passed the execute stage before the next instruction can enter the fetch stage in the pipeline. The branch predictor attempts to avoid this waste of time by trying to guess whether the conditional jump is most likely to be taken or not taken. The branch that is guessed to be the most likely is then fetched and speculatively executed. If it is later detected that the guess was wrong, then the speculatively executed, incurring a delay.

data[c] >= 128

Take more help from this link: Multiple Branch Prediction for Wide-Issue Superscalar

于 2021-04-14T08:08:30.667 回答
17

An answer for quick and simple understanding (read the others for more details)

This concept is called branch prediction

Branch prediction is an optimization technique that predicts the path the code will take before it is known with certainty. This is important because during the code execution, the machine prefetches several code statements and stores them in the pipeline.

The problem arises in conditional branching, where there are two possible paths or parts of the code that can be executed.

When the prediction was true, the optimization technique worked out.

When the prediction was false, to explain it in a simple way, the code statement stored in the pipeline gets proved wrong ant the actual code has to be completely reloaded, which takes up a lot of time.

As common sense suggests, predictions of something sorted are way more accurate than predictions of something unsorted.

branch prediction visualisation:

sorted
sorted unsorted unsorted

于 2021-11-05T10:05:03.933 回答
8

Why is processing a sorted array faster than processing an unsorted array?

Example from the code:

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

Execution Timing:

timing of execution

Conclusion:

Observe that time taken for processing a sorted array is less as compared to an unsorted array. The reason for this optimization for the sorted arrays is branch prediction.

What is branch prediction?

Branch prediction in computer architecture focuses on determining whether a conditional branch (jump) in a program's instructions pipeline is likely to be taken or not. Because they must guess the address field to fetch before the current instruction is executed, all pipelined processors do branch prediction in some manner.

How is branch prediction inapplicable on the above case ?

The if condition checks that arr[i] < 5000, but if you observe in case of a sorted array, after passing the number 5000 the condition is always false, and before that, it is always true. The CPU will recognize that pattern and be able to predict correctly which instruction to execute next after the conditional branch, instead of sometimes having to rewind after guessing wrong.

Working Of Branch Prediction Algorithm:

Branch prediction works on the pattern the algorithm is following or basically the history, how it got executed in previous steps. If the guess is correct, then CPU continues executing and if it goes wrong, then the CPU needs to flush the pipeline and roll back to the branch and restart from the beginning.

于 2021-10-26T09:25:28.920 回答