这是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秒内运行

(分类本身需要的时间比这个通过数组的时间要长, 所以如果我们需要计算未知数组, 它实际上不值得做 。)


起初,我以为这只是一种语言或编译器异常, 所以我尝试了爪哇:

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

其结果类似,但不太极端。


我第一种想法是 分类能把数据带进缓存缓存,但那是愚蠢的 因为阵列是刚刚产生的。

  • 这是怎么回事?
  • 为什么处理一个分类阵列的速度要快于处理一个未排序阵列的速度?

守则正在总结一些独立的术语,因此命令不应重要。


相关/后续行动不同/以后的编译者和选项的相同效果:


当前回答

这是肯定的!

分处预测逻辑会放慢速度, 因为代码中的转换会发生! 就像你走一条直街或一条路, 转得很多,

如果对数组进行了排序,您的状态在第一步是虚假的:data[c] >= 128,然后成为通向街道尽头的整个路程的真正价值。这就是你如何更快地达到逻辑的终点。另一方面,使用一个未分类的阵列,你需要大量转动和处理,这可以保证你的代码运行速度较慢...

看看我在下面为你们创造的图象,哪条街会更快完工?

Branch Prediction

因此,从方案上说,子分支预测导致进程变慢...

最后,很高兴知道 我们有两种分支预测 每个分支将对你的代码产生不同的影响:

1. 静态

2. 动态

Branch Prediction

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

为了有效地编写你的代码,以便利用这些规则,在撰写时if-ele 单位开关循环不一定需要固定分支预测的任何特殊代码顺序,因为通常只使用循环迭代器的条件。

其他回答

毫无疑问,我们中有些人会感兴趣的是,如何确定对CPU的分支种植者有问题的代码。cachegrind使用--branch-sim=yes将外环数量减少到10 000个,并编成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)造成164 050 007个错误预测的附带条件的分支(第1行)。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)
...

见见性能辅导以获取更多细节。

这个问题的根源在于分支预测模型我建议读读这篇论文:

通过多分支预测和一个分支处理缓存,提高通过多分支预测和分支处理获取指令的比率(除了Haswell和后来的Haswell之外)在其循环缓冲中有效释放小圆环。现代的CPU可以预测多个未获取的分支,以便利用其在大毗连区块中的提取。 )

当您对元素进行分类时,分支预测很容易预测正确,除非在边界正确,允许指示有效通过CPU管道,而不必倒转和正确选择错误预测路径。

避免分支预测错误的一种方法是建立一个搜索表,并用数据来编制索引。 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];

此代码浪费了一半的添加值, 但从未出现分支预测失败 。 随机数据比有实际的如果声明的版本要快得多 。

但在我的测试中,一个清晰的查看表比这个稍快一些, 可能是因为对一个查看表的索引比位变换略快一些。 这显示了我的代码是如何设置和使用搜索表的( 无法想象地称为“ 搜索表 ” ) 。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至2的指针阵列,并使用“决定位位”技术来决定应跟随哪一个。例如,而不是:

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

这个图书馆会做一些事情,比如:

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

以下是这个代码的链接:红黑树, 永久封存

在对数据进行分类时,业绩显著改善的原因是,如A/CN.9/WG.WG.III/WG.WG.III/WP.A/WG.WG.III/WP.A/A/WG.WG.III/WP.A/WG.A/WP.A/WG.A/WP.A/WP.A/WP.A/WG.A/WP.A/WP.A/WP.A/WP.A/WP.神秘的答案.

现在,如果我们看看代码

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

我们能发现这个特别的if... else...当满足条件时,该分支将添加某种内容。这种类型的分支可以很容易地转换成条件移动语句,该语句将汇编成有条件移动指令:cmovl,在一个x86取消了分支系统,从而取消了潜在的分支预测罚款。

C因此,C++,该语句,该语句将直接(不作任何优化)编成有条件移动指令x86,是永久经营人... ? ... : ...。因此,我们将上述声明重写为相应的声明:

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

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

在一个情报机关上,核心 i7-2600K@3.4 GHz和视觉工作室2010发布模式,基准是:

x86x86

假设情景 时间( 秒)
分处 - 随机数据 8.885
分支 - 分类数据 1.528
无分支 - 随机数据 3.716
无分支 - 排序数据 3.71

x64 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处理器, 执行指令分为几个阶段。 大致说来, 我们用不同的硬件处理不同阶段。 因此, 我们不必等待一个指令完成才能启动一个新的指令。 这被称为管线,.

在一个分支中,下列的训导是由前面的训导决定的,所以我们不得管线。我们不是等待的,就是预告的。

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

这本书计算机系统:程序员的观点,第二版请查看3.6.6节。有条件移动指令整个第4章处理器建筑第5.1.1.2节,以及第5.1.1.2节,处 处 处 预测和错误预防处罚.

有时,一些现代编译者可以以更好的性能优化我们的代码组装,有时有些编译者无法(有关代码是使用视觉工作室的本地编译者 ) 。 当无法预测的情况变得如此复杂,以至于编译者无法自动优化代码时,他们知道分支和有条件的动作之间的性能差异。

我用MATLAB 2011b 和我的MacBook Pro(Intel i7, 64位, 2.4 GHz) 尝试了以下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.

校对:Soup

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

基于这个,看来MATLAB几乎是175乘175次低于 C 执行的慢于 C 执行,没有排序和350乘350次换句话说,其效果(分支预测)是:1.46x执行和2.7x执行《公约》的《公约》。