条件判断语句与分支预测

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
本作品 (李兆龙 博文, 由 李兆龙 创作)，由 李兆龙 确认，转载请注明版权。

引言

写下这篇文章的原因是看到了[1]这个问题，虽然以前了解过分支预测，但没想到在极端条件下对性能的影响如此之大。本来想就着自己的理解详细的描述下这个问题以及其答案，但是发现其实很多文章都已经完成了这个目标了，所以这篇文章就简单的聊一聊。

问题描述

首先就是看一段十分经典的代码：

#include <algorithm>
#include <ctime>
#include <iostream>

int main() {
    const unsigned ARRAY_SIZE = 50000;
    int data[ARRAY_SIZE];
    const unsigned DATA_STRIDE = 256;

    for (unsigned c = 0; c < ARRAY_SIZE; ++c) data[c] = std::rand() % DATA_STRIDE;

    std::sort(data, data + ARRAY_SIZE);

    {  // 测试部分
        clock_t start = clock();
        long long sum = 0;

        for (unsigned i = 0; i < 100000; ++i) {
            for (unsigned c = 0; c < ARRAY_SIZE; ++c) {
                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";
    }
    return 0;
}

我们来看看注释掉sort和不注释掉sort对程序有怎样的影响，当然按照常理来讲并不会有什么影响，反而排序会更慢，因为时间复杂度从O(N)升到了O(NlogN)，以下是结果：

上面的是加sort的，下面是不加的。

怎么样，震惊吧。竟然有三倍以上的性能差距，和预期完全不符合。问题的答案其实就是分支预测。

在学微机原理的时候我们知道在BLU中其实会进行预取指令，因为对于CPU来说，一个指令从头到尾要经历如下几个步骤：

1. 取指：Fetch
2. 译指：Decode
3. 执行：execute
4. 回写：Write-back

显然执行只是一部分，那么此时应用流水线（pipelines）显然是一种压榨CPU更好的方法，因为可以在CPU执行是不浪费总线资源，且执行完一条指令以后不必再等待取指的过程。但是在遇到条件判断语句的时候可能出现一个问题，根据判定条件的真/假的不同，有可能会产生转跳，而我们在条件判断之前并不知道该跳转到哪一个分支上，此时显然有两种方法，一种是同步等待，这样一定不会取错指令，但是很慢；第二个方法就是基于某种条件挑一个分支，先加载到指令队列中，预测成功就万事大吉，错误了就flush缓冲区，回滚到之前的分支重新取指就可以，具体的分支预测策略可参考[5][3]。

维基对分支预测有如下描述[3]：

• Without branch prediction, the processor would have to wait until the conditional jump instruction has passed the execute stage before the next instruction can enter the fetch stage in the pipeline. The branch predictor attempts to avoid this waste of time by trying to guess whether the conditional jump is most likely to be taken or not taken. The branch that is guessed to be the most likely is then fetched and speculatively executed. If it is later detected that the guess was wrong, then the speculatively executed or partially executed instructions are discarded and the pipeline starts over with the correct branch, incurring a delay.
• The time that is wasted in case of a branch misprediction is equal to the number of stages in the pipeline from the fetch stage to the execute stage. Modern microprocessors tend to have quite long pipelines so that the misprediction delay is between 10 and 20 clock cycles. As a result, making a pipeline longer increases the need for a more advanced branch predictor.

• 如果没有分支预测，则处理器将必须等到条件跳转指令通过执行阶段，然后下一条指令才能进入流水线中的提取阶段。 分支预测器通过尝试猜测是否有可能发生条件跳转来尝试避免浪费时间。 然后获取最有可能被猜测的分支并进行推测性执行。 如果以后检测到猜测是错误的，则将丢弃由推测执行或部分执行的指令，并且管道将从正确的分支重新开始，从而导致延迟。
• 在分支预测错误的情况下所浪费的时间等于从获取阶段到执行阶段的流水线中的阶段数。现代微处理器往往具有很长的流水线，因此误预测延迟在10到20个时钟周期之间。结果，使流水线更长会增加对更高级的分支预测器的需求。

所以我们可以从上面的这个简单的小demo中得出一个简单的结论：记得在大量的循环的条件下对优化逻辑判断留一个心眼。

当然使用设计模式中的策略模式可以避免多个if-else的困扰，但是常见的策略模式的实现基本是基于查表的[6]，也就是里面放一张哈希表，参数传入不同的类型，用以执行不同的代码块。策略模式的定义是这样的：

• Define a family of algorithms, encapsulate each one, and make them interchangeable. Strategy lets the algorithm vary independently from clients that use it.
• 定义一族算法类,将每个算法分别封装起来,让它们可以互相替换。策略模式可以使算法的变化独立于使用它们的客户端。

可以看到策略模式想做的事情并不是单纯让它效率更高，而是使得调用方与代码提供方松耦合，甚至可以满足开闭原则。

诚然，更多的时候对于我们来讲需要的是代码的可读性，可维护性。性能优化是很后期的事情，而需要指令级别的优化的场景我想更少，比如存储，内核这样的场景。

优化

上面的代码确实比较极端的，那么我们可以优化吗？当然可以，就是用位运算去优化条件分支，这样的话对于CPU来说就不需要分支预测了，当然也不会出现像上面代码一样那么动荡的性能变化了。

策略来自[2]：

|x| >> 31 = 0 # 非负数右移31为一定为0
~(|x| >> 31) = -1 # 0取反为-1

-|x| >> 31 = -1 # 负数右移31为一定为0xffff = -1
~(-|x| >> 31) = 0 # -1取反为0

-1 = 0xffff
-1 & x = x # 以-1为mask和任何数求与，值不变

int t = (data[c] - 128) >> 31; # statement 1
sum += ~t & data[c]; # statement 2

更巧妙的是这个：

int t=-((data[c]>=128)); # generate the mask
sum += ~t & data[c]; # bitwise AND

其实就是data[c]大于128是与其相&的值就是0xffff；相反就是0了。这种一个大于条件的判断语句其实挺常见的，所以很多地方我们都可以这样修改，算是编程技巧的一种吧。可以在[7]中看到更多对位运算的运用。

对我们代码的启发

其实我想说的就是两个GCC的built-in functions，它们与分支预测有关系，其中一种在我们代码中应该是可以使用的。

__builtin_speculation_safe_value

这个函数的作用在GNU手册中描述为下：

• This built-in function can be used to help mitigate against unsafe speculative execution. type may be any integral type or any pointer type.
• 此built-in function可用于帮助缓解不安全的预测执行。类型可以是任何整数类型或任何指针类型。

手册中给出如下样例：

int array[500];
int f (unsigned untrusted_index)
{
  if (untrusted_index < 500)
    return array[untrusted_index];
  return 0;
}

这其实在我们日常的编码过程来看没有任何问题，但是其实这段代码有一点点危险，问题出在分支预测上。

如果多次使用小于500的值调用此函数，随后使用超出范围的值调用该函数，它将仍然首先尝试执行该代码块，直到CPU确定预测不正确为止（CPU将在此时取消所有不正确的操作）。但是，根据函数结果的使用方式，可能会在高速缓存中留下一些痕迹，这些痕迹可以揭示出存储在越界位置的内容。通过使用__builtin_speculation_safe_value可以避免这种情况：

int array[500];
int f (unsigned untrusted_index)
{
  if (untrusted_index < 500)
    return array[__builtin_speculation_safe_value (untrusted_index)];
  return 0;
}

当我们把代码改成上述格式后可以保证安全。手册中描述内置函数此时有两种可能的行为：

1. 将导致执行停止，直到条件分支已完全解决为止；
2. 可以允许推测执行继续进行，但如果超出限制，则使用0而不是untrusted_value；

手册描述到可能在推测执行不正确时访问任何内存位置都不安全，此时可以把代码重写为：

int array[500];
int f (unsigned untrusted_index)
{
  if (untrusted_index < 500)
    return *__builtin_speculation_safe_value (&array[untrusted_index], NULL);
  return 0;
}

这种情况其实比较令人疑惑，我认为可能描述的是第二种执行可能，即使用0是不安全的行为，此时如果array[untrusted_index]是预测的值，那么我们直接在缓存中放NULL

__builtin_expect

简单粗暴的一个功能，手册中描述如下：

• You may use __builtin_expect to provide the compiler with branch prediction information.

当然如果你确定你程序的访问频率的话可以使用这个，但是正如手册中所调侃的：

as programmers are notoriously bad at predicting how their programs actually perform.

但是很多场景还是很有用的，举个很经典的例子，即打日志是需要gettid，这是一个系统调用，显然开销极大，但是在线程运行期间不会改变，那么缓存这个值就是一个非常正常且合理的操作了，我们可以这样写，代码来自于adl的adlserver：

//currentTheread.h
extern __thread int t_cachedTid;
void cacheTid();
inline int tid() {
  if (__builtin_expect(t_cachedTid == 0, 0)) {
    cacheTid();
  }
  return t_cachedTid;
}

//currentTheread.cpp
__thread int CurrentThread::t_cachedTid = 0;

void CurrentThread::cacheTid() {
  if (t_cachedTid == 0) {
    t_cachedTid = adl::gettid();
  }
}

代码非常好懂，就不解释啦。

总结

祝大家大年初一多收压岁钱！在新的一年中身体倍健康，心情特别好！好运天天交，口味顿顿妙！家里出黄金，墙上长钞票。

参考：

1. 《代码里充斥着 if-else 分支有什么不好吗？除了可维护性，对程序运行效率有什么影响吗？》
2. 《深入理解 CPU 的分支预测(Branch Prediction)模型》
3. wiki Branch predictor
4. GNU manul https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
5. 《分支预测(Branch Prediction)》
6. 《极客时间 设计模式之美》
7. 《Bit Twiddling Hacks》