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

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

具有相似但不太极端的结果。


我首先想到的是排序将数据带入缓存,但是后来我想到这样做是多么愚蠢,因为刚刚生成了数组。

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

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

答案

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


什么是分支预测?

考虑一个铁路枢纽:

该图显示了铁路枢纽 Mecanismo 的图片 ,通过 Wikimedia Commons。在CC-By-SA 3.0许可下使用。

现在,为了论证,假设这是在 1800 年代 - 在进行长距离或无线电通信之前。

您是路口的操作员,并且听到火车驶入。您不知道应该走哪条路。您停下火车,询问驾驶员他们想要哪个方向。然后您适当地设置开关。

火车很重,惯性很大。因此,它们要花很多时间才能启动和减速。

有没有更好的办法?您猜火车将朝哪个方向行驶!

  • 如果您猜对了,它将继续进行。
  • 如果您猜错了,机长会停下来,后退并大喊大叫,以拨动开关。然后,它可以沿着其他路径重新启动。

如果您每次都猜对了 ,火车将永远不会停止。
如果您经常猜错 ,火车将花费大量时间停止,备份和重新启动。


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

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

您是处理器,并且看到一个分支。您不知道它将走哪条路。你是做什么?您停止执行,并等待之前的说明完成。然后,您沿着正确的路径继续。

现代处理器很复杂,而且流程很长。因此,他们需要永远进行 “热身” 和 “减速”。

有没有更好的办法?您猜分支将朝哪个方向前进!

  • 如果您猜对了,则继续执行。
  • 如果您猜错了,则需要刷新管道并回滚到分支。然后,您可以沿着其他路径重新启动。

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


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

那么,您如何从战略上猜测如何将火车必须倒退和走另一条路的次数降至最低?您看看过去的历史!如果火车有 99%的时间向左行驶,那么您就猜到了。如果它交替出现,那么您将交替猜测。如果它每三回去一次,您会猜到相同...

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

大多数应用程序具有行为良好的分支。因此,现代分支预测器通常将达到 90%以上的命中率。但是,当面对没有可识别模式的不可预测分支时,分支预测变量实际上是无用的。

进一步阅读: 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, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)

那该怎么办呢?

如果编译器无法将分支优化为有条件的移动,那么如果您愿意牺牲可读性来提高性能,则可以尝试一些破解。

更换:

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

与:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

这消除了分支,并用一些按位运算将其替换。

(请注意,这种破解并不严格等同于原始的 if 语句。但是在这种情况下,它对data[]所有输入值均有效。)

基准: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

观察结果:

  • 使用分支:排序和未排序的数据之间存在巨大差异。
  • 使用 Hack:排序和未排序的数据之间没有区别。
  • 在 C ++ 情况下,对数据进行排序时,hack 实际上比分支慢一点。

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


更新:

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

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

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

  • 英特尔 C ++ 编译器 (ICC)11 发挥了神奇的作用。它互换两个循环 ,从而将不可预测的分支提升到外部循环。因此,它不仅可以避免错误预测,而且还比 VC ++ 和 GCC 生成的速度快两倍!换句话说,ICC 利用测试循环来击败基准测试……

  • 如果给 Intel 编译器提供无分支的代码,它将直接对其进行矢量化处理…… 并且速度与分支一样快(通过循环交换)。

这表明即使是成熟的现代编译器,其优化代码的能力也可能存在巨大差异。

分支预测。

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

当对数据进行排序时,性能大幅提高的原因是消除了分支预测损失,如Mysticial 的答案中所详细解释的那样。

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

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

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

C ,因此在C++ ,将直接(不进行任何优化)编译为x86的条件移动指令的语句是三元运算符... ? ... : ... 。因此,我们将上面的语句重写为等效的语句:

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

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

在 Intel Core i7 -2600K @ 3.4 GHz 和 Visual Studio 2010 Release Mode 上,基准是(从 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程序集,让我们更加仔细地研究。为了简单起见,我们使用两个函数max1max2

if... else ... max1将使用条件分支:

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不涉及分支跳转jmp ,如果预测结果不正确,则会对性能造成重大影响。

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

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

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

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

第二版计算机系统:程序员的观点 》一书对此进行了详细说明。您可以检查第 3.6.6 节中的 “ 条件移动指令” ,第 4 章中的 “ 处理器体系结构 ” 和第 5.11.2 节中的 “ 分支预测和错误预测惩罚”的特殊处理。

有时,某些现代的编译器可以优化我们的代码以使其具有更好的性能,而有时某些编译器则不能(问题代码使用 Visual Studio 的本机编译器)。当情况变得如此复杂以至于编译器无法自动优化它们时,了解分支与条件移动之间的性能差异(这是不可预测的)可以帮助我们编写性能更高的代码。

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

从原始循环开始:

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

毫无疑问,我们中的某些人会对识别对 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产生的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 的 branch-predictor 模型下导致 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)
...

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

我只是阅读了这个问题及其答案,所以我觉得答案丢失了。

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

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

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

背景以及原因

从处理器的角度来看,您的内存很慢。为了弥补速度上的差异,处理器内置了两个缓存(L1 / L2 缓存)。因此,假设您正在执行出色的计算,并发现您需要一块内存。处理器将执行其 “加载” 操作,并将内存加载到缓存中,然后使用缓存进行其余的计算。由于内存相对较慢,因此此 “加载” 将减慢您的程序的速度。

像分支预测一样,它在奔腾处理器中进行了优化:处理器预测它需要加载一条数据,并在操作实际到达缓存之前尝试将其加载到缓存中。正如我们已经看到的那样,分支预测有时会出现严重的错误 - 在最坏的情况下,您需要返回并实际上等待内存加载,这将永久占用内存( 换句话说:失败的分支预测很糟糕,内存不足)分支预测失败后的负载简直太可怕了! )。

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

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

构造表

因此,我们发现可以创建一个小表。接下来要做的就是准备好查找功能。查找函数通常是使用几个基本整数运算(以及,或 “异或”,“移位”,“加法”,“删除” 以及 “也许乘”)的小函数。您希望通过查找功能将您的输入转换为表中的某种 “唯一键”,然后简单地为您提供所需的所有工作的答案。

在这种情况下:> = 128 表示我们可以保留该值,<128 表示我们可以摆脱它。最简单的方法是使用 “ AND”:如果我们保留它,我们将其与 7FFFFFFF 进行 AND;如果要删除它,则将其与 0 进行 “与” 运算。还要注意 128 是 2 的幂 - 因此我们可以继续制作一张 32768/128 整数的表,并用一个零和很多零填充 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();

当对数组进行排序时,由于数据分布在 0 到 255 之间,因此在迭代的前半部分将不会输入if -statement(下面共享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

一个 “ ” 的真假模式会使if语句的速度比 “ ” 模式慢六倍!当然,哪种模式好坏,取决于编译器和特定处理器生成的确切指令。

因此,毫无疑问分支预测对性能的影响!

避免分支预测错误的一种方法是建立查找表,并使用数据对其进行索引。 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语句)来确定要使用的指针。我看到了一个实现二叉树的库,它没有两个命名的指针( pLeftpRight或其他), pRight一个长度为 2 的指针数组,并使用 “决策位” 技术来决定遵循哪个。例如,代替:

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

该库将执行以下操作:

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

这是此代码的链接: 红黑树永远困惑

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

实际上,该数组在data < 128data >= 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) :-)

由于分支预测,因此发生了上述现象。

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

任何指令都分为一系列步骤,以便可以并行并行执行不同的步骤。该技术称为指令流水线,用于提高现代处理器的吞吐量。为了更好地理解这一点,请参见Wikipedia 上的示例

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

  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 的结果。因此,管线会像这样。

如果条件返回 true: 在此处输入图片说明

如果条件返回假: 在此处输入图片说明

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

那么什么是分支预测?

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

在正确猜测的情况下,管道如下所示: 在此处输入图片说明

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

在 OP 的代码中,有条件的第一次,分支预测变量没有任何信息可作为预测的基础,因此,第一次它将随机选择下一条指令。稍后在 for 循环中,它可以将预测基于历史记录。对于按升序排序的数组,存在三种可能性:

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

让我们假设预测变量在首次运行时将始终假设为真实分支。

因此,在第一种情况下,由于历史上所有的预测都是正确的,因此它将始终采用真正的分支。在第二种情况下,最初将预测错误,但是经过几次迭代后,它将正确预测。在第 3 种情况下,它最初将正确预测直到元素少于 128 个。此后,它将失败一段时间并在历史中看到分支预测失败时进行自我纠正。

在所有这些情况下,故障的数量将太少,因此,仅需几次就可以丢弃部分执行的指令并从正确的分支重新开始,从而减少了 CPU 周期。

但是,如果是随机未排序的数组,则预测将需要丢弃部分执行的指令,并在大多数时间中从正确的分支重新开始,与排序后的数组相比,将导致更多的 CPU 周期。