这是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 单位开关循环不一定需要固定分支预测的任何特殊代码顺序,因为通常只使用循环迭代器的条件。

其他回答

这个问题已经回答过很多次了。我还是想提醒大家注意另一个有趣的分析。

最近,这个例子(稍作修改)也被用来演示如何在 Windows 上显示一个代码在程序本身中被剖析。 顺便提一下, 作者还展示了如何使用结果来确定代码的大部分时间用于分解和未排序的案例中。 最后, 文章还展示了如何使用HAL( Hardware Empaction Develople) 的一个鲜为人知的特征来确定未分类案例中的分支错误发生多少。

链接在此 :自我辩护示范

分部门预测。

以排序数组数组, 条件data[c] >= 128第一个是false一连串的数值,然后变成true后期所有值。 这很容易预测。 使用一个未排序的阵列, 您支付分支成本 。

如果您对这个代码可以做的更多优化感到好奇, 请考虑 :

以原始循环开始 :

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

这比以前快了十万倍

当对数组进行排序时,数据在 0 到 255 之间分布, 大约在迭代的前半部不会输入if- 声明if报表如下。 )

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

The question is: What makes the above statement not execute in certain cases as in case of sorted data? Here comes the "branch predictor". A branch predictor is a digital circuit that tries to guess which way a branch (e.g. an 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

“A ““真实的假造模式可以使if- 计算速度比“或”慢6倍。良好当然,哪一种模式是好的,哪一种模式是坏的,取决于汇编者的确切指示和具体处理者。

因此,部门预测对业绩的影响是毫无疑问的!

毫无疑问,我们中有些人会感兴趣的是,如何确定对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)
...

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