分支预测是什么？为什么有序数组比无序数组快？

末蓝、 2023-07-10 14:08 15阅读 0赞

*  1. 背景
    
     *  1.1. 问题的提出
 *  2. 前情提示
    
     *  2.1. 流水线
     *  2.2. 分支预测器
        
         *  2.2.1. 久远的历史
         *  2.2.2. 在现代CPU中的情况
            
             *  2.2.2.1. 没有分支预测器会怎样？
             *  2.2.2.2. 有分支预测期的pipeline
             *  2.2.2.3. 常见的分支预测器
 *  3. 分析
 *  4. 结论

# 1. 背景 #

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

在intellij idea中运行结果：

# 1. 先排序后计算
    5.549553
    sum = 155184200000
    # 2. 不排序直接结算
    15.527867
    sum = 155184200000

## 1.1. 问题的提出 ##

以上代码在数组填充时已经加入了分区函数，充分保证填充值的随机性，计算时也是按一半的元素来求和，所以不存在特例情况。而且，计算也完全不涉及到数据的有序性，即数组是否有序理论上对计算不会产生任何作用。在这样的前提下，为什么**排序后**的数组要比**未排序**数组运行快3倍以上？

# 2. 前情提示 #

## 2.1. 流水线 ##

先简单说明一下CPU的instruction pipeline(指令流水线)，以下简称pipeline。 Pipieline假设程序运行时有一连串指令要被运行，将程序运行划分成几个阶段，按照一定的顺序并行处理之，这样便能够加速指令的通过速度。  
绝大多数pipeline都由时钟频率(clock)控制，在数字电路中，clock控制逻辑门电路(logical cicuit)和触发器(trigger), 当受到时钟频率触发时，触发器得到新的数值，并且逻辑门需要一段时间来解析出新的数值，而当受到下一个时钟频率触发时触发器又得到新的数值，以此类推。  
而借由逻辑门分散成很多小区块，再让触发器链接这些小区块组，使逻辑门输出正确数值的时间延迟得以减少，这样一来就可以减少指令运行所需要的周期。 这对应Pipeline中的各个stages。  
取指令 - 指令译码 - 执行指令 这认为是一个三级流水线  
如果我们进一步把“执行指令”拆分成“ALU 计算（指令执行）- 内存访问 - 数据写回”，那么它就会变成一个五级的流水线  
像我们现代的 ARM 或者 Intel 的 CPU，流水线级数都已经到了 14 级。  
**流水线的级数越高越好吗？**  
每一级流水线对应的输出，都要放到流水线寄存器（Pipeline Register）里面，然后在下一个时钟周期，交给下一个流水线级去处理。所以，每增加一级的流水线，就要多一级写入到流水线寄存器的操作。虽然流水线寄存器非常快，比如只有 20 皮秒（ps，10−12 秒）  
如果我们指令的执行有 3 纳秒，也就是 3000 皮秒。我们需要 20 级的流水线，那流水线寄存器的写入就需要花费 400 皮秒，占了超过 10%。如果我们需要 50 级流水线，就要多花费 1 纳秒在流水线寄存器上，占到 25%。这也就意味着，单纯地增加流水线级数，不仅不能提升性能，反而会有更多的 overhead 的开销。  
![format_png_height_250][]  
所有的流水线停顿操作都要从指令执行阶段开始。流水线的前两个阶段，也就是取指令（IF）和指令译码（ID）的阶段，是不需要停顿的。CPU 会在流水线里面直接去取下一条指令，然后进行译码。  
取指令和指令译码不会需要遇到任何停顿，这是基于一个假设。这个假设就是，所有的指令代码都是顺序加载执行的。不过这个假设，在执行的代码中，一旦遇到 if…else 这样的条件分支，或者 for/while 循环，就会不成立。  
![format_png_height_250 1][]  
可以看到，在 jmp 指令发生的时候，CPU 可能会跳转去执行其他指令。jmp 后的那一条指令是否应该顺序加载执行，在流水线里面进行取指令的时候，我们没法知道。要等 jmp 指令执行完成，去更新了 PC 寄存器之后，我们才能知道，是否执行下一条指令，还是跳转到另外一个内存地址，去取别的指令。  
有什么优化的手段呢

## 2.2. 分支预测器 ##

### 2.2.1. 久远的历史 ###

想象一个铁路分叉道口。  
![format_png_width_808][]  
为了论证此问题，让我们回到19世纪，那个远距离无线通信还未普及的年代。你是铁路交叉口的扳道工。当听到火车快来了的时候，你无法猜测它应该朝哪个方向走。于是你叫停了火车，上前去问火车司机该朝哪个方向走，以便你能正确地切换铁轨。  
要知道，火车是非常庞大的，切急速行驶时有巨大的惯性。为了完成上述停车-问询-切轨的一系列动作，火车需耗费大量时间减速，停车，重新开启。  
既然上述过车非常耗时，那是否有更好的方法？当然有！当火车即将行驶过来前，你可以猜测火车该朝哪个方向走。

*  如果猜对了，它直接通过，继续前行。
 *  如果猜错了，车头将停止，倒回去，你将铁轨扳至反方向，火车重新启动，驶过道口。

如果你不幸每次都猜错了，那么火车将耗费大量时间停车-倒回-重启。  
如果你很幸运，每次都猜对了呢？火车将从不停车，持续前行！

### 2.2.2. 在现代CPU中的情况 ###

分支预测器是一种数字电路，在分支指令执行前，猜测哪一个分支会被执行，能显著提高pipelines的性能。  
条件分支通常有两路后续执行分支，not token时,跳过接下来的JMP指令，继续执行， token时，执行JMP指令，跳转到另一块程序内存去执行。  
为了说明这个问题，我们先考虑如下问题。

#### 2.2.2.1. 没有分支预测器会怎样？ ####

加入没有分支预测器，处理器会等待分支指令通过了pipeline的执行阶段(execuate stage)才能把下一条指令送入pipeline的fetch stage。  
这会造成流水线停顿(stalled)或流水线冒泡(bubbling)或流水线打嗝(hiccup)，即在流水线中生成一个没有实效的气泡， 如下图所示：  
![format_png_width_849][]  
图中一个气泡在编号为3的始终频率中产生，指令运行被延迟。  
Stream hiccup现象在早期的RISC体系结构处理器中常见。

#### 2.2.2.2. 有分支预测期的pipeline ####

我们来看分支预测器在条件分支跳转中的应用。  
条件分支通常有两路后续执行分支，not token时,跳过接下来的JMP指令，继续执行， token时，执行JMP指令，跳转到另一块程序内存去执行。  
加入分支预测器后，为避免pipeline停顿(stream stalled)，其会猜测两路分支哪一路最有可能执行，然后投机执行，如果猜错，则流水线中投机执行中间结果全部抛弃，重新获取正确分支路线上的指令执行。可见，错误的预测会导致程序执行的延迟。  
由前面可知，Pipeline执行主要涉及Fetch, Decode, Execute, Write-back几个stages, 分支预测失败会浪费Write-back之前的流水线级数。现代CPU流水线级数非常长，分支预测失败可能会损失20个左右的时钟周期，因此对于复杂的流水线，好的分支预测器非常重要。

#### 2.2.2.3. 常见的分支预测器 ####

*  静态分支预测器

最简单的分支预测技术，叫作“假装分支不发生”。顾名思义，自然就是仍然按照顺序，把指令往下执行。其实就是 CPU 预测，条件跳转一定不发生。这样的预测方法，其实也是一种静态预测技术。就好像猜硬币的时候，你一直猜正面，会有 50% 的正确率。  
如果分支预测是正确的，我们自然赚到了。这个意味着，我们节省下来本来需要停顿下来等待的时间。如果分支预测失败了呢？那我们就把后面已经取出指令已经执行的部分，给丢弃掉。这个丢弃的操作，在流水线里面，叫作 Zap 或者 Flush。CPU 不仅要执行后面的指令，对于这些已经在流水线里面执行到一半的指令，我们还需要做对应的清除操作。比如，清空已经使用的寄存器里面的数据等等，这些清除操作，也有一定的开销。所以，CPU 需要提供对应的丢弃指令的功能，通过控制信号清除掉已经在流水线中执行的指令。只要对应的清除开销不要太大，我们就是划得来的。  
![format_png_height_250 2][]

*  双模态预测器(bimodal predictor)

上面的静态预测策略，看起来比较简单，预测的准确率也许有 50%。但是如果运气不好，可能就会特别差。于是，工程师们就开始思考，我们有没有更好的办法呢？比如，根据之前条件跳转的比较结果来预测，是不是会更准一点？我们日常生活里，最经常会遇到的预测就是天气预报。如果没有气象台给你天气预报，你想要猜一猜明天是不是下雨，你会怎么办？有一个简单的策略，就是完全根据今天的天气来猜。如果今天下雨，我们就预测明天下雨。如果今天天晴，就预测明天也不会下雨。这是一个很符合我们日常生活经验的预测。因为一般下雨天，都是连着下几天，不断地间隔地发生“天晴 - 下雨 - 天晴 - 下雨”的情况并不多见。那么，把这样的实践拿到生活中来是不是有效呢？我在这里给了一张 2019 年 1 月上海的天气情况的表格。  
![format_png_width_808 1][]  
我们用前一天的是不是下雨，直接来预测后一天会不会下雨。这个表格里一共有 31 天，那我们就可以预测 30 次。你可以数一数，按照这种预测方式，我们可以预测正确 23 次，正确率是 76.7%，比随机预测的 50% 要好上不少。

而同样的策略，我们一样可以放在分支预测上。这种策略，我们叫**一级分支预测**（One Level Branch Prediction），或者叫\*\* 1 比特饱和计数\*\*（1-bit saturating counter）。这个方法，其实就是用一个比特，去记录当前分支的比较情况，直接用当前分支的比较情况，来预测下一次分支时候的比较情况。只用一天下雨，就预测第二天下雨，这个方法还是有些“草率”，我们可以用更多的信息，而不只是一次的分支信息来进行预测。于是，我们可以引入一个状态机（State Machine）来做这个事情。如果连续发生下雨的情况，我们就认为更有可能下雨。之后如果只有一天放晴了，我们仍然认为会下雨。在连续下雨之后，要连续两天放晴，我们才会认为之后会放晴。  
这个状态机里，我们一共有 4 个状态，所以我们需要 2 个比特来记录对应的状态。这样这整个策略，就可以叫作 2 比特饱和计数，或者叫双模态预测器（Bimodal Predictor）。  
![format_png_width_846][]  
图左边两个状态为不采纳(not token)，右边两个为采纳(token)。由not token到token中间有两个渐变状态。由红色到蓝色翻转需要连续两次分支选择。  
技术实现上可用两个二进制位来表示，`00, 01, 10, 11`分别对应`strongly not token, weakly not token, weakly token, strongly token`。 一个判断两个分支预测规则是否改变的简单方法便是判断这个二级制状态高位是否跳变。高位从0变为1， 强状态发生翻转，则下一个分支指令预测从`not token`变为`token`，反之亦然。  
据评测，双模态预测器的正确率可达到93.5%。预测期一般在分支指令解码前起作用。  
其它常见分支预测器如两级自适应预测器，局部/全局分支预测器，融合分支预测器，Agree预测期，神经分支预测器等。

# 3. 分析 #

原程序中：

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

汇编码：

cmp edx, 128
    jl SHORT $LN3@main
    add rbx, rdx
    $LN3@main:

让我们回到文章开头的问题。现在假设你是处理器，当看到上述分支时，当你并不能决定该如何往下走，该如何做？只能暂停运行，等待之前的指令运行结束。然后才能继续沿着正确地路径往下走。  
要知道，现代编译器是非常复杂的，运行时有着非常长的流水线， 减速和热启动将耗费巨量的时间。  
那么，有没有好的办法可以节省这些状态切换的时间呢？你可以猜测分支的下一步走向！

*  如果猜错了，处理器要清楚刚刚执行的中间结果, 回滚到之前的分支，然后重新热启动，选择另一条路径。
 *  如果猜对了，处理器不需要暂停，继续往下执行。

如果每次都猜错了，处理器将耗费大量时间在停止-回滚-热启动这一周期性过程里。  
如果侥幸每次都猜对了，那么处理器将从不暂停，一直运行至结束。  
上述过程就是分支预测(branch prediction)。虽然在现实的道口铁轨切换中，可以通过一个小旗子作为信号来判断火车的走向，但是处理器却无法像火车那样去预知分支的走向–除非最后一次指令运行完毕。  
那么处理器该采用怎样的策略来用最小的次数来尽量猜对指令分支的下一步走向呢？答案就是分析历史运行记录： 如果火车过去90%的时间都是走左边的铁轨，本次轨道切换，你就可以猜测方向为左，反之，则为右。如果在某个方向上走过了3次，接下来你也可以猜测火车将继续在这个方向上运行…  
换句话说，你试图通过历史记录，识别出一种隐含的模式并尝试在后续铁道切换的抉择中继续应用它。这和处理器的分支预测原理或多或少有点相似。  
大多数应用都具有状态良好的(well-behaved)分支，所以现代化的分支预测器一般具有超过90%的命中率。但是面对无法预测的分支，且没有识别出可应用的的模式时，分支预测器就无用武之地了。  
关于分支预测期，可参考维基百科相关词条["Branch predictor" article on Wikipedia.][Branch predictor_ article on Wikipedia.].  
文首导致非排序数组相加耗时显著增加的罪魁祸首便是if逻辑：

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

注意到data数组里的元素是按照0-255的值被均匀存储的(类似均匀的分桶)。数组data有序时，前面一半元素的迭代将不会进入if-statement, 超过一半时，元素迭代将全部进入if-statement.  
这样的持续朝同一个方向切换的迭代对分支预测器来说是非常友好的，前半部分元素迭代完之后，后续迭代分支预测器对分支方向的切换预测将全部正确。  
简单地分析一下：  
有序数组的分支预测流程：

T = 分支命中
    N = 分支没有命中
    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  (非常容易预测)
    无序数组的分支预测流程：
    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 ...   (完全随机--无法预测)

在本例中，由于data数组元素填充的特殊性，决定了分支预测器在未排序数组迭代过程中将有50%的错误命中率，因而执行完整个sum操作将会耗时更多。

# 4. 结论 #

*  使用分支预测: 是否排序严重影响performance
 *  使用bithack: 是否排序对performance无显著影响

这个例子告诉给我们启示: 在大规模循环逻辑中要尽量避免数据强依赖的分支(data-dependent branching).  
switch对分支预测不友好，dubbo中也有利用分支预测的写法

public void benchIfAndSwitch(ExecutionPlan plan, Blackhole bh) {
        int result = 0;
        for (int i = 0; i < plan.size; ++i) {
            ChannelState state = plan.states[i];
            if (state == ChannelState.RECEIVED) {
                result += ChannelState.RECEIVED.ordinal();
            } else {
                switch (state) {
                case CONNECTED:
                    result += ChannelState.CONNECTED.ordinal();
                    break;
                case SENT:
                    result += ChannelState.SENT.ordinal();
                    break;
                case DISCONNECTED:
                    result += ChannelState.DISCONNECTED.ordinal();
                    break;
                case CAUGHT:
                    result += ChannelState.CAUGHT.ordinal();
                    break;
                }
            }
        }
        bh.consume(result);
    }}
    public void benchSiwtch(ExecutionPlan plan, Blackhole bh) {
            int result = 0;
            for (int i = 0; i < plan.size; ++i) {
                switch (plan.states[i]) {
                case CONNECTED:
                    result += ChannelState.CONNECTED.ordinal();
                    break;
                case DISCONNECTED:
                    result += ChannelState.DISCONNECTED.ordinal();
                    break;
                case SENT:
                    result += ChannelState.SENT.ordinal();
                    break;
                case RECEIVED:
                    result += ChannelState.RECEIVED.ordinal();
                    break;
                case CAUGHT:
                    result += ChannelState.CAUGHT.ordinal();
                    break;
                }
            }
            bh.consume(result);
        }
    Result "io.github.hengyunabc.jmh.TestBenchMarks.benchSiwtch":
      576.745 ±(99.9%) 6.806 ops/s [Average]
      (min, avg, max) = (490.348, 576.745, 618.360), stdev = 20.066
      CI (99.9%): [569.939, 583.550] (assumes normal distribution)
    # Run complete. Total time: 00:06:48
    Benchmark                         (size)   Mode  Cnt     Score    Error  Units
    TestBenchMarks.benchIfAndSwitch  1000000  thrpt  100  1535.867 ± 61.212  ops/s
    TestBenchMarks.benchSiwtch       1000000  thrpt  100   576.745 ±  6.806  ops/s

可以明显看到if前置的每秒操作数更多，效率更高

[format_png_height_250]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubmxhcmsuY29tL3l1cXVlLzAvMjAyMC9wbmcvMzMwMzk1LzE1ODMxNTYxODgyNzAtZGI3ZmQxNWYtYTg4Yi00ZGIwLWE0ZDYtMTQ5ZWFmYzcyNDRmLnBuZw?x-oss-process=image/format,png#height=250
[format_png_height_250 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubmxhcmsuY29tL3l1cXVlLzAvMjAyMC9wbmcvMzMwMzk1LzE1ODMxNTYxODgxMDMtNzIyODA0ZGYtNWFjMC00ODhkLTgzNzMtNjZlNWYyZmZiMDFmLnBuZw?x-oss-process=image/format,png#height=250
[format_png_width_808]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubmxhcmsuY29tL3l1cXVlLzAvMjAyMC9wbmcvMzMwMzk1LzE1ODMxNTYxODc3NTgtZWU5Y2IwZjEtZjFjZi00YjIxLTgxZmQtMWRjNmM5ZGQzZTg5LnBuZw?x-oss-process=image/format,png#width=808
[format_png_width_849]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubmxhcmsuY29tL3l1cXVlLzAvMjAyMC9wbmcvMzMwMzk1LzE1ODMxNTYxODc5NzQtNGZjNGYwM2EtZTk0Yi00ZDY3LTk4YTEtNjYxOTc2YjFmMWZkLnBuZw?x-oss-process=image/format,png#width=849
[format_png_height_250 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubmxhcmsuY29tL3l1cXVlLzAvMjAyMC9wbmcvMzMwMzk1LzE1ODMxNTYxODgxMzQtY2NlMmQyYTktZjRiMy00NjRjLWJkNGItMmM2NDYyMjg4ODVkLnBuZw?x-oss-process=image/format,png#height=250
[format_png_width_808 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubmxhcmsuY29tL3l1cXVlLzAvMjAyMC9wbmcvMzMwMzk1LzE1ODMxNTYxODgxOTQtMmM5ZjllNTUtYjFiMy00NGI3LTk1OWItMDIyMjFjMTA2ZDMxLnBuZw?x-oss-process=image/format,png#width=808
[format_png_width_846]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubmxhcmsuY29tL3l1cXVlLzAvMjAyMC9wbmcvMzMwMzk1LzE1ODMxNTYxODgyNDAtYjRmOTYwMjEtZDY1YS00OWQxLWE3ODctOTA3MmMyNjI1ZDI1LnBuZw?x-oss-process=image/format,png#width=846
[Branch predictor_ article on Wikipedia.]: https://en.wikipedia.org/wiki/Branch_predictor