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

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


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

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

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


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


当前回答

是关于分支预测的 是什么?

  • 分支预测器是古老的改进性能的技术之一,在现代建筑中仍然具有相关性。 虽然简单的预测技术能提供快速搜索和电力效率,但它们的误判率很高。

  • 另一方面,复杂的分支预测 — — 无论是基于神经的预测还是两级分支预测的变异 — — 提供了更好的预测准确性,但是它们消耗更多的能量和复杂性会成倍增加。

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

  • 部门预测基本上是一个优化(最小化)问题,重点是实现尽可能低的误差率、低电耗和最低资源复杂性低。

确实有三种不同的分支:

附加条件的分支- 根据运行时间条件,PC(程序表计数器)被修改为指示流中前方的地址。

后向附加条件分支- PC被修改为指令流的后向点。分支基于某种条件,例如当循环结束时的测试显示循环应该再次执行时,分支会向后到程序循环开始处。

无条件分支- 包括跳跃、程序呼叫和没有特定条件的返回。 例如, 无条件跳跃指令可能以组合语言编码为简单的“ jmp ” , 且指令流必须直接指向跳跃指令指向的目标位置, 而有条件跳跃, 代号为“ jmpne ” , 只有在对先前“ 比较” 指令中两个数值进行比较的结果显示数值不相等时, 才会改变教学流的方向。 (x86 结构使用的分段处理方案增加了额外的复杂度, 因为跳跃可以是“ 接近” (在段内) , 也可以是“ 远” (在段外) 。 每种类型都对分支预测算法有不同的影响 。

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

参考文献:

其他回答

除了树枝预测可能会减慢你的速度之外 分解阵列还有另一个优势

您可以有一个停止状态, 而不是仅仅检查值, 这样你只能环绕相关数据, 忽略其它数据 。
分支预测只会错失一次。

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

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

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

链接在此 :自我辩护示范

以上行为之所以发生 是因为分局的预测

要理解分支预测,首先必须了解指令管道。

运行一个指令的步骤可以与运行上一个和下一个指令的步骤序列相重叠,这样可以同时同时执行不同的步骤。 这种技术被称为指令管衬,用来增加现代处理器的输送量。 要更好地了解这一点,请看维基百科的示例.

一般而言,现代处理器有相当长(和宽)的管道,因此许多教学可能正在飞行中。现代微处理器 A 90-minute指南!首先是引入基本自序管管,然后从那里开始。

但为容易,让我们考虑一个简单的 单用这四个步骤的单向输油管。
(像经典的5级RIRC,但忽略了单独的MEM阶段。 ))

  1. IF -- -- 从内存获取指令
  2. ID - 解码指令
  3. EX - 执行指令
  4. WB - 回写到 CPU 注册簿

一般为2项指示提供4级输油管。
4-stage pipeline in general

回到上述问题,让我们考虑以下指示:

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

如果没有部门预测,将出现下列情况:

要执行指令B或指令C,处理器必须等待(缓档直至指示A离开输油管中的EX阶段,因为进入指示B或指示C的决定取决于指示A的结果(即从何处取取取)。

无预测:何时if条件为真 : enter image description here

无预测:何时if条件为假 : enter image description here

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

那么什么是分支预测?

分支预测器将尝试猜测分支( 如果- 如果- 如果- 如果- else 结构) 将往哪个方向走, 然后再确定这一点。 它不会等待指令 A 到达管道的 EX 阶段, 而是会猜测决定并转到该指令( 以我们为例 ) ( B 或 C ) 。

如果猜对了,输油管看起来是这样的: enter image description here

如果后来发现猜测是错误的,那么部分执行的指示就会被丢弃,管道从正确的分支开始,造成延误。如果分支错误,浪费的时间相当于管道从取货阶段到执行阶段的阶段数。现代微处理器往往有相当长的管道,因此错误处理的延迟时间在10到20小时的周期之间。输油管越长,对货物的需求就越大。分支分支预测器.

在业务方案代码中,这是有条件的、分支预测员第一次没有任何信息作为预测基础,因此第一次随机选择下一个指令。 (或返回到后方)静静在循环中,它可以将预测建立在历史之上。对于按升序排序的阵列,有三种可能性:

  1. 所有元素小于 128
  2. 所有元素大于 128
  3. 一些开始的新元素还不到128个,后来则大于128个

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

因此,在第一种情况下,它总是要真正的分支,因为历史上它所有的预测都是正确的。 在第二种情况下,它最初预测错误,但经过几次反复,它会正确预测。 在第二种情况下,它最初将正确预测,直到元素低于128。 之后,它会失败一段时间,当它看到分支预测在历史上失败时,它会失败一段时间,它会正确。

在所有这些情况下,失败的数量将太少,因此,只需放弃部分执行的指示,从正确的分支重新开始,就只需要放弃部分执行的指示的几次,导致CPU周期减少。

但如果是随机的未排序数组,预测将需要丢弃部分执行的指示,然后大部分时间以正确的分支重新开始,结果与分类数组相比,CPU周期会增加。


进一步读作:

  • 现代微处理器 A 90-minute指南!
  • Dan Luu关于分支预测的文章(涵盖较老的分支预测器,而不是现代的IT-TAGE或倍数)
  • https://en.wikipedia.org/wiki/Branch_predictor
  • 处处预测和口译员的工作表现 -- -- 不相信民俗- 2015年,Intel's Haswell在预测Python口译员主循环的间接分支(由于不简单模式,历史上存在问题)方面表现如何,相对于未使用 IT-TAGE 的早期CPU。 (虽然他们不帮助完全随机的这个案例。如果在Skylake CPU的环中,当源被编译为分支时,如果在环中,Skylake CPU的误判率仍为50%。 )
  • 最新 Intel 处理器的静态分支预测- CPUs在运行分支指令时实际做什么,该指令没有动态预测。ifbreak)))后取(像环状)已被使用,因为它比什么都没有好。 设置代码, 这样快速路径/ 普通大小写最小化的分支对 I -cache 密度和静态预测都有好处, 所以编译者已经这样做了 。实际效果联 联 年 月 日 月 日 月 月 日 月 月 日 月 月 月 日 月 月 日 月 月 日 月 月 月 日 月 月 日 月 月 月 日 月 的 月 月 月 日 月 月 日 月 的 月 月 月 月 日 月 月 月likely / unlikely在 C 源中提示, 而不是在大多数 CPU 中暗示硬件分支预测, 除了通过静态预测。 )

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

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

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

以原始循环开始 :

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

这比以前快了十万倍