CPU分支预测对程序的影响

分支预测的英文名字是“Branch Prediction”，如果大家在Google上搜索这个关键字，可以看到关于分支预测的很多内容。不过，要搞清楚分支预测是如何工作的，才是问题的关键。

分支预测对程序的影响

下面，我们先来看两段代码。

代码1：

#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<double>(clock()-start) / CLOCKS_PER_SEC;
    std::cout << elapsedTime << '
';
    std::cout << "sum = " << sum << '
';
}

@ubuntu:/data/study$ g++ fenzhi.cpp && ./a.out
21.6046
sum = 314931600000

#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<double>(clock()-start) / CLOCKS_PER_SEC;
    std::cout << elapsedTime << '
';
    std::cout << "sum = " << sum << '
';
}

@ubuntu:/data/study$ g++ fenzhi.cpp && ./a.out
8.52157
sum = 314931600000

究竟发生了什么事情？

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

CPU会有一个提前预测机制，比如前面的执行结果都是true，那么下一次在判断if的时候，就会默认由true来处理，让下面的几条指令提前进入预装。

当然，这个判断不会影响实际的结果输出，这个判断只是为了让CPU并行执行代码。

CPU执行一条指令分为几个阶段：

int a = 0;
a += 1;
a += 2;
a += 3;

如果预测失败，会不会就影响了执行的时间？答案是肯定的。

在前面的例子中，没有对数组排序的情况下，分支预测大部分都会是失败的，这个时候就会在执行结束后重新取指令执行，会严重影响执行效率。

而在排序后的例子中，分支预测一直处于成功的状态，CPU的执行速率得到大幅度的提升。

如何解决性能下降问题？

分支预测会存在一定的能性下降，想让性能提升的方法，就是不要使用这个该死的if语句。

比如上面的代码，我们可以修改成这样：

#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
            int t = (data[c] - 128) >> 31;
            sum += ~t & data[c];
        }
    }
    double elapsedTime = static_cast<double>(clock()-start) / CLOCKS_PER_SEC;
    std::cout << elapsedTime << '
';
    std::cout << "sum = " << sum << '
';
}

比如，我们看到的绝对值代码，里面也用了这样的思想。

/**
 * abs - return absolute value of an argument
 * @x: the value. If it is unsigned type, it is converted to signed type first.
 * char is treated as if it was signed (regardless of whether it really is)
 * but the macro's return type is preserved as char.
 *
 * Return: an absolute value of x.
 */
#define abs(x) __abs_choose_expr(x, long long, 
    __abs_choose_expr(x, long, 
    __abs_choose_expr(x, int, 
    __abs_choose_expr(x, short, 
    __abs_choose_expr(x, char, 
    __builtin_choose_expr( 
      __builtin_types_compatible_p(typeof(x), char), 
      (char)({ signed char __x = (x); __x<0?-__x:__x; }), 
      ((void)0)))))))

#define __abs_choose_expr(x, type, other) __builtin_choose_expr( 
  __builtin_types_compatible_p(typeof(x), signed type) || 
  __builtin_types_compatible_p(typeof(x), unsigned type), 
  ({ signed type __x = (x); __x < 0 ? -__x : __x; }), other)

当然，你也可以这样写：

int abs(int i){
   if(i<0)
    return ~(--i);
  return i;
}

所以说，计算机的尽头是数学~

　　审核编辑：汤梓红