这是C++代码的一块 显示一些非常特殊的行为

由于某种原因,对数据进行分类(在时间区之前)奇迹般地使主要循环速度快近六倍:

#include 
#include 
#include 

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(clock()-start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << '\n';
    std::cout << "sum = " << sum << '\n';
}

没有 std: sort( 数据, 数据+数组Size); 代码在 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);
    }
}

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


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

为什么处理一个分类阵列的速度要快于处理一个未分类阵列的速度?

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


与不同的/后来的汇编者和备选办法具有相同效果:

为什么处理一个未排列的阵列的速度与处理一个用现代 x86-64 叮当的排序阵列的速度相同? gcc 优化标记 -O3 使代码慢于 -O2


当前回答

在 ARM 中,不需要分支, 因为每个指令都有一个 4 位条件字段, 它( 零成本) 测试处理器状态登记册中可能出现的16种不同条件中的任何一种, 如果指令条件不实, 则跳过指令。 这就消除了对短分支的需求, 并且不会为此算法找到分支预测 。 因此, 此算法的分类版本会比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

但这其实是大局的一部分:

处理器状态登记册(PSR)中的状态位元总是更新 OP 代码, 因为这是它的目的, 但大多数其他指令都没有触动 PSR , 除非您在指令中添加一个可选的后缀, 并明确指出 PSR 应该根据指令的结果更新 。 就像 4 位条件后缀一样, 能够执行指令而不影响 PSR 是一种机制, 减少了对 ARM 上分支的需求, 并且也便利了硬件级的异常发送, 因为执行了 X 操作后, 您可以在随后( 或平行) 执行一系列其他工作, 明确不应该影响( 或受) 状态位元的影响 。 然后您可以测试 X 先前设定的状态位的状态状态 。

条件测试字段和可选的“ 设定状态位” 字段可以合并, 例如 :

ADDR R1、R2、R3在不更新任何状态位数的情况下执行R1 = R2 + R3。ADDGE R1、R2、R3仅在影响状态位数的先前指令导致大于或等于条件时才执行相同的操作。ADDDS R1、R2、R3在处理器状态登记册中进行添加并随后更新N、Z、C和V国旗,依据是结果是否为负、Ze、C(未签名添加)或oVerflowed(供签名添加)。ADDDDSGE R1、R2、R3仅在GE测试属实的情况下执行添加,然后根据添加结果更新状态位数。

大多数处理器结构没有这种能力来说明是否应该为特定操作更新状态位元,这可能需要写入额外的代码来保存和随后恢复状态位元,或者可能需要额外的分支,或者可能限制处理器的异常执行效率:大多数CPU指令设置的架构的副作用之一是,在大多数指令之后强制更新状态位元,是很难分离哪些指令可以平行运行而不相互干扰的。更新状态位元具有副作用,因此对代码具有线性效果。ARM在任何指令上混合和匹配无分支条件测试的能力,在任何指令非常强大之后,可以对组合语言程序员和编译员更新或不更新状态位,并生成非常高效的代码。

当您不需要分行时, 您可以避免冲刷管道的时间成本, 否则就是短的分支, 您也可以避免许多投机性蒸发形式的设计复杂性。 缓解最近发现的很多处理器弱点( 特例等)的最初天真效果影响 表明现代处理器的性能在多大程度上取决于复杂的投机性评估逻辑。 由于输油管很短,对分支的需求也大大减少, ARM不需要像 CISC 处理器那样依赖投机性评估。 ( 当然, 高端的ARM 实施过程包括投机性评估, 但是它只是绩效故事中的一小部分 ) 。

如果你曾经想过为什么ARM如此成功,那么这两种机制(加上另一个允许你“轮回”左转或右转的机制,任何算术操作员的两个论点之一或以零额外费用抵消内存存存取操作员的两种论点之一)的辉煌效力和互动作用是故事的一大部分,因为它们是ARM结构效率的最大来源。 1983年ARM ISA原设计师Steve Furber和Roger(现为Sophie)Wilson的聪明才智无论怎样强调都不为过。

其他回答

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

消除我发现在管理下语言中特别出色的分支预测的一个常见方法是, 表格搜索而不是使用分支(虽然我还没有在本案中测试过它 ) 。

如果:

它是一个小桌子, 很可能被隐藏在处理器中, 而你运行的东西在一个非常紧凑的循环中, 和/或处理器可以预加载数据。

背景和原因

从处理器的角度来看,您的内存是慢的。为了弥补速度的差异,在您的处理器( L1/L2 缓存) 中嵌入了几个缓存。 想象一下, 您正在做你的好计算, 并发现您需要一个内存。 处理器会得到它的“ 装载” 操作, 并将内存部分装入缓存中, 然后用缓存来进行其余的计算。 因为内存相对缓慢, 此“ 装载” 将会减缓您的程序 。

像分支预测一样,这在Pentium处理器中得到了优化:处理器预测,它需要在操作实际击中缓存之前装入一个数据,并试图将数据装入缓存中。我们已经看到,分支预测有时会发生可怕的错误 -- -- 在最坏的情况下,你需要回去等待一个记忆负荷,这将需要永远的时间(换句话说:不完成分支预测是坏的,在分支预测失败之后的记忆负荷实在太可怕了!)

幸运的是,对于我们来说,如果记忆存取模式可以预测,处理器将装在快速缓存中,一切都很好。

我们首先需要知道的是小什么是小什么?虽然小一般比较好,但大拇指规则是坚持使用大小为 4096 字节的搜索表格。作为一个上限:如果您的查看表格大于 64K, 可能值得重新考虑 。

构建表格

因此我们发现我们可以创建一个小表格。 接下来要做的是设置一个查找功能。 查找功能通常是使用几个基本整数操作( 以及, 或者, xor, 转换, 转换, 添加, 删除, 或倍增) 的小型函数。 您想要将您的输入通过外观功能转换为表格中某种“ 独一无二的密钥 ” , 这样就可以简单给出您想要它做的所有工作的答案 。

在此情况下 : 128 表示我们可以保留这个值, < 128 表示我们摆脱它。 最简单的方法就是使用“ 和 ” : 如果我们保留它, 我们和它使用 7FFFFFFF; 如果我们想要摆脱它, 我们和它使用 0。 注意 128 也是一种2 的功率, 所以我们可以继续制作一个32768/128 整数的表格, 并填满它 1 0 和很多 7FFFFFFFFFFFF。

受管理语言

毕竟,管理下的语言会用分支来检查阵列的界限,以确保你不会搞砸...

嗯,不确切地说... : -)

在取消管理下语文的这一分支方面,已经做了相当多的工作。

for (int i = 0; i < array.Length; ++i)
{
   // Use array[i]
}

在此情况下, 编译者明显知道边界条件永远不会被击中 。 至少微软 JIT 编译者( 但我预计爪哇会做类似的事情) 将会注意到这一点并完全取消检查 。 WOW 表示没有分支 。 同样, 它也会处理其他明显的例子 。

如果您遇到管理下语言的查询问题 -- -- 关键是将 & 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();

这是肯定的!

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

If the array is sorted, your condition is false at the first step: data[c] >= 128, then becomes a true value for the whole way to the end of the street. That's how you get to the end of the logic faster. On the other hand, using an unsorted array, you need a lot of turning and processing which make your code run slower for sure...

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

因此,在程序上,分支预测导致过程的慢化...

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

1. 静态

2. 动态

微处理器在第一次遇到有条件分支时使用静态分支预测,在随后执行有条件分支代码时则使用动态分支预测。为了有效编写代码以利用这些规则,在撰写 if-else 或 开关 语句时,先检查最常见的情况,然后逐步工作到最不常见的情况。循环不一定要求固定分支预测使用任何特殊的代码顺序,因为通常只使用循环迭代器的条件。

毫无疑问,我们中有些人会感兴趣的是如何识别对CPU的分支定位器有问题的代码。 Valgrind 工具缓冲grinnd 拥有一个通过使用 -- 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_ anoteate 产生的逐行输出,

分类 :

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

这样您就可以很容易地识别问题行 - 在未排序版本中, 如果( data[c] 128) 线导致164 050 007 错误预测的有条件分支( Bcm) , 在缓存grind 的分支- 指示模型下, 而分类版本中它只造成 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)
...

详情请见性能辅导课程。

官方的回答是来自

英特尔 -- -- 避免误用英特尔分公司的成本 -- -- 分公司和循环重组以防止误用科学论文 -- -- 分公司预测计算机建筑书籍:J.L. Hennessy, D.A. Patterson:计算机结构:定量方法 科学出版物中的文章:T.Y. Yeh, Y.N. Patt在分支预测方面做了许多这些。

你也可以从这张可爱的图表中看到 树枝预测器为什么会被混淆。

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

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

所以预测器会随着 : rand () 的打击而改变两边。

另一方面,一旦对预测进行分类, 预测器将首先进入一个 强烈未被采纳的状态, 当值变化到高值时, 预测器将分三步走, 从强烈未被采纳到强烈被采纳。


这个问题根植于CPUs的分支预测模型。

通过多分支预测和分支处理缓存来提高教学取回率(但现在的实际 CPU 仍然不能在每时钟周期中做出多个支流控制,但Haswell 和后来在循环缓冲中有效释放的小循环除外。 现代 CPU 可以预测多个未取用的分支, 以利用大毗连区块中的提取。 )

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