分支是如何影响代码性能的？

上周在ryf的公众号上发现一篇名为《How branches influence the performance of your code and what can you do about it?》[1]的文章，讲述了代码分支（if语句）对于程序性能的影响。主要契机是在AFL源码的if语句中常常出现的likely和unlikely用法，所以这一篇文章就挺让我在意的，不过上周一直在整PE Parser，就没来得及去看。恰逢这周已经整完了PE Parser，故腾出时间来看一看这篇文章，并记录相关要点。

1. CPU的一些特性

• 管线化（Pipeline）：
  • 这个概念和我们计网中学习流水线技术相似，对于CPU来说，这其实就是多条指令时间并行处理的技术
• 乱序执行（Out of order execution）
• 预测执行（Speculative execution）
  • 预测分支的目的地
  • 如果预测有误，则预测运行的结果将会清空
• 分支预测（Branch prediction）
  • 分支预测器

2. CPU如何影响分支

• 为了保持最大化流水线并避免降速，处理器需要知道分支最终目的地址（甚至在处理器解码分支指令之前）

• 处理器可能的相关操作（与具体处理器设计有关）

  • 1⃣ 暂停流水线（stall the pipeline）并停止指令解码操作直到分支指令被解码且分支的目的地已知，然后将继续载入流水线执行正确的指令；
  • 2⃣ 加载该分支后面的指令：
    • 如果之后在该分支处做出了错误的选择（i.e. 也就是说不执行该分支后面的指令，而是执行跳转的指令），那么处理器将清空流水线并开始载入正确的指令
  • 3⃣ 向分支预测期询问应该加载分支后面的指令还是分支跳转的目的地址的指令

  需要注意的是：主流的处理器一般不会进行1⃣ 的操作，原因是1⃣ 的操作开销过大；主流处理器一般会采用2⃣或3⃣的方式进行处理，2⃣通常在低端嵌入式系统或低开销处理器中使用，3⃣通常在桌面端或笔记本端的高性能CPU中使用⭐。

无分支预测特性的CPU

• 直接载入分支后面的指令
• 如果预测失败，则清空已加载的错误指令；因此，在不执行分支操作的情况下，该操作的成本最低
• 需要注意的是，由于无分支预测特性的CPU设计通常是简单的 ==> 流水线较短，因此做出错误选择的惩罚并不是特别高

有分支预测特性的CPU

• 如果CPU流水线很长，那么分支预测器预测失败所带了的影响就会很大 [体现在流水线上执行的错误指令将被清空]
• 分支预测的复杂性
  • 有一些分支很好预测
  • 另一些分支很难预测
• 说白了就是分支预测器进行分支推测，并预处理预测分支处的指令，如果预测成功，那将提高程序的运行速度，否则，将浪费资源在无用的指令上，因而带来额外的开销；🤔换句话说，其性能完全取决于分支预测的成功率。

3. 汇编概述

• 假设我们的C代码片段如下所示：

if (p != nullptr) {
    transform(p);
} else {
    invalid++;
}

• 汇编包含两种指令，一种是比较指令，另外一种是跳转指令；上述C代码对应于下面的伪汇编程序：

      p_not_null = (p != nullptr)
      if_not (p_not_null) goto ELSE;
      transform(p);
      goto ENDIF;
  ELSE:
      invalid++;
  ENDIF:

  • 汇编会评估原始C条件语句p!=nullptr，如果为false，则执行与else分支相对应的指令分支，否则，就执行与if分支主体相对应的指令
  • 上述伪汇编还有一种等价形式：

      p_not_null = (p != nullptr)
      if (p_not_null) goto IF:
      invalid++;
      goto ENDIF;
  IF:
      transform(p);
  ENDIF: 

• 虽然上面两种伪汇编是等价的，但是大多数编译器会形如第一个的汇编，开发者可以使用GCC builtins来影响这一决策；关键的见解⭐是：在一些处理器上，顺序执行比跳转的开销要小很多，这样的话，告诉编译器如何结构化代码将会带来更好的性能

4. 分支和向量化

• 向量化：简单来说，其实就是现代的CPU有一些特殊的向量指令，这些向量指令能够处理超过一个同类型的数据，e.g. 有一个指令能够从内存中载入4个整数，一个指令能够做4次加法，另一个指令能够将4个结果存回内存

• 自动向量化（autovectorization）：向量化的好处是能够使运行速度变快。CPU的自动向量化会自动生成向量指令来加快运行速度

• 自动向量化的局限性（与分支有关）：

  • for (int i = 0; i < n; i++) {
        if (a[i] > 0) {
            a[i]++;
        } else {
            a[i]--;
        }
    }
      * 上述循环很难被向量化，原因在于数据本身的改变与数据值之间的关系
    
    ## 5. 程序运行更快的技巧（:star:）
    
    * 相关定义：
      * 定义1 **条件概率**：指的是条件为真的可能性
        * 具有分支预测的CPU能很快识别出哪一个条件很可能为真/假；当遇到很难预测的分支时，分支预测器将有50%正确预测的概率，而这些分支便有优化的潜力
      * 定义2 *computational intensive*, *expensive* or *heavy condition*
        * 计算时需要很多的指令 or 需要参与计算的数据不在缓存（单个指令需要很多时间去完成）
    
    ### 优化If/else命令链
    
    假设有以下源代码：
    
    ```c
    if (a > 0) { 
        do_something();
    } else if (a == 0) { 
       do_something_else();
    } else {
        do_something_yet_else();
    }
    

进一步假设（a < 0）概率为70%；（a > 0）概率为20%，（a == 0）概率为10%，那么我们可以重排上述代码中的顺序，具体来说，将触发概率高的条件越往前放置

if (a < 0) {   // 70 %
    do_something_yet_else();
} else if (a > 0) {   // 20 %
   do_something();
} else {    // 10 %
    do_something_else();
}

使用查找表而不是switch语句

在删除分支时，查找表LUT偶尔会排上用场。虽然switch语句中的分支在大多数情况下都很容易预测，因而这种优化很可能不会带来任何效果。尽管如此，还是尽可能去做这种转换。假设有下述代码：

switch(day) {
    case MONDAY: return "Monday";
    case TUESDAY: return "Tuesday";
   ...
    case SUNDAY: return "Sunday";
    default: return "";
};

上述代码可以使用LUT进行实现：

if (day < MONDAY || day > SUNDAY) return "";
char* days_to_string = { "Monday", "Tuesday", ... , "Sunday" };
return days_to_string[day - MONDAY];

通常情况下编译器可能会为你完成上述操作，i.e.将switch语句转为一个查找表，

此外，GNU语言扩展中有一个叫computed labels的东西能够允许你实现存储labels的查找表，这个玩意对于实现解析器来说是很有用的，如：

    static const void* days[] = { &&monday, &&tuesday, ..., &&sunday };
    goto days[day];
monday:
    return "Monday";
tuesday:
    return "Tuesday";
...
sunday:
    return "Sunday";

将最常见的case移出switch

R.T., e.g.：

day get_first_workday() {
     std::chrono::weekday first_workday = read_first_workday();
    if (first_workday == Monday) { return day::Monday; }
    switch(first_workday) { 
        case Tuesday: return day::Tueasday;
        ....
    };
}

重写条件连结符

我们从一个例子引入此节的观点，假设有以下代码片段：

if (a[i] > x && a[i] < y) {
    do_something();
}

从汇编角度来看：

if_not (a[i] > x) goto ENDIF;
if_not (a[i] < y) goto ENDIF;
do_something;
ENDIF

虽然 a[i] > x 和 a[i] < y 都是很容易计算的（所有数据都已经在寄存器或者缓存），但都很难预测。这里我们如果使用&连结这两个条件，主要的作用有：

1. 强制将两个条件同时计算（将不会有&&的短路运算）
2. 使条件更容易预测，因而会降低分支预测出错的概率：假设条件1与条件2概率均为50%，那么再使用&连结符之后，整个分支为真的概率为25%
3. 去掉一个分支

相似的，将||替换为|也可以达到相同的目的

PS: C++中bool类型0表示false，而其他任何数字表示true

C++标准保证逻辑操作符的结果和算术比较的结果总会为0或者1，但是并不保证所有bool都有这两类值的参与，因此如果需要标准化bool变量，需要应用!!符。（我们在阅读C类代码的时候，时常会看到!!的操作符，该操作符其实就是将结果标准化为bool变量）

告知编译器哪一个分支有更高的概率

GCC和Clang提供指示分支概率性的关键字：__builtin_expect，e.g.

#define likely(x)      __builtin_expect(!!(x), 1)
#define unlikely(x)    __builtin_expect(!!(x), 0)
if (likely(ptr)) {
    ptr->do_something();
}

我们在阅读AFL源码的时候，也观察到AFL源码中if语句处大量使用了likely(...)、unlikely(...)语法，其目的就是对分支进行优化；

在底层，编译器会重排if/else分支语句所对应的指令，以便更有效地使用底层硬件。

PS: 这里的见解其实我们在第3节中已经介绍过了，i.e.

在一些处理器上，顺序执行比跳转的开销要小很多，这样的话，告诉编译器如何结构化代码将会带来更好的性能

因此编译器根据用户定义的概率重排if/else语句将会带来更好的性能

使用无分支算法

简单来说这里其实使用了位运算来消除算法中的分支，e.g. 取绝对值函数abs()在计算某一个数的绝对值时，就用了一个trick：

int abs(int a) {
  int const mask = 
        a >> sizeof(int) * CHAR_BIT - 1;
    return  = (a + mask) ^ mask;
}

⭐ 一些位运算的其他tricks可以参考这一篇文章Bit Twiddling Hacks (stanford.edu)

使用条件载入取代分支

假设有分支语句：

if (x > y) {
    x++;
}

可以如下重写：

int new_x = x + 1;
x = (x > y) ? new_x : x; // the compiler should recognize this and emit a conditional branch

这里第2行的语句可以被（condition move - cmov）指令进行优化，因此可以删除分支

使用算术运算删除分支

e.g.

// With branch
if (a > b) {
    x += y;
}
// Branchless
x += -(a > b) & y; 

当a > b为假时，-(a > b) & y为0；当a > b为真时，-(a > b) = -1 => -(a > b) & y = -1 & y = y

另外一个例子：

// With branch
x = (a > b) ? val_a : val_b;
// Branchless
x = val_a;
x += -(a > b) & (val_b - val_a);

上述示例均使用了算术运算来避免分支，但根据CPU分支错误预测惩罚和数据缓存命中率，该做法可能会提高性能，可能也不会，请根据情况酌情使用（我们可以看出，这样做转化后，代码的可阅读性变差了）

最后是一个环形缓冲区的例子：

// With branch
int get_next_element(int current, int buffer_len) {
    int next = current + 1;
    if (next == buffer_len) {
        return 0;
    }
    return next;
}
// Branchless
int get_next_element_branchless(int current, int buffer_len) {
    int next = current + 1;
    return (next < buffer_len) * next;
}

重组代码来避免分支

这种方式属于代码逻辑层面的重组，使用上较为灵活。下面以一个名为animation的类为例：

假设下述代码遍历animation_list中的每一个animation实例，并且根据实例是否可见来执行相应的成员方法：

for (const animation& a: animation_list) {
   a.step_a();
   if (a.is_visible()) {
      a.step_av();
   }
   a.step_b();
   if (a.is_visible) {
       a.step_bv();
}

一种优化的思路是：根据is_visible()函数的结果对animation_list中的数据进行排序，比如说最前面放置可见的实例，后面放置隐藏的实例，并使用一个变量记录分割点；

另一种优化思路是：使用额外的两个数组来分别存放可见和隐藏的实例，animation_list_visible 和 animation_list_hidden，重写后的代码如下：

for (const animation& a: animation_list_visible) {
   a.step_a();
   a.step_av();
   a.step_b();
   a.step_bv();
}
for (const animation& a: animation_list_hidden) {
   a.step_a();
   a.step_b();
}

使用模板删除分支

如果一个布尔型变量被传给函数且作为函数的一个参数，那么可以通过传递一个模板参数来消除函数的参数，e.g.

int average(int* array, int len, bool include_negatives) {
    int average = 0;
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (include_negatives) {
            average += array[i];
        } else {
            if (array[i] > 0) {
                average += array[i];
                count++;
            }
        }
    }
    if (include_negatives) {
         return average / len;
    } else {
        return average / count;
    }
}

在这个函数中，包含include_negatives的条件可能会被计算很多次，传递一个模板参数而不是函数参数可以有效的减少这类计算，如：

template <bool include_negatives>
int average(int* array, int len) {
    int average = 0;
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (include_negatives) {
            average += array[i];
        } else {
            if (array[i] > 0) {
                average += array[i];
                count++;
            }
        }
    }
    if (include_negatives) {
         return average / len;
    } else {
        return average / count;
    }
}

编译器会为上述代码生成两个版本的函数，一个是include_negatives为真时的代码，一个是为假时的代码。这样一来，分支就完全消失了，未使用的分支中的代码也消失了。但需要注意的是，在调用时有略微的不同：

int avg;
bool should_include_negatives = get_should_include_negatives();
if (should_include_negatives) {
    avg = average<true>(array, len);
} else {
    avg = average<false>(array, len);
}

以上其实是一种叫branch optiomization的编译器优化技术。如果include_negatives值在编译时是已经得，那么编译器将决定内联函数，并删除分支以及未使用的代码。但是，带模板的这一版代码能够保证上述过程，而原始版的代码并不一定能够保证上述过程。

其他的一些技巧来避免分支

如果代码中检查了若干次不可变条件，那么你可以通过进行代码拷贝的方式获得更好的性能，e.g.

if (is_visible) {
    hide();
}
process();
if (is_active) {
    display();
}

如下重写：

if (is_visible) {
    hide();
    process();
    display();
} else {
    process();
}

---

你也可以引入两个元素的数组，一个用于存放条件为真的结果，另一个用于存放条件为假的结果，e.g.

if (is_visible) {
    hide();
    process();
    display();
} else {
    process();
}

如下重写：

int result[] = { 0, 0 };
for (int i = 0; i < n; i++) {
    result[a>i]++;
}
return result[1];

6. 总结

• 本文主要从CPU（包括一些优化技术）及汇编的角度重新审视代码中分支对于程序运行性能上的影响，并在第5节中提出了一些优化程序运行性能的技巧，这些技巧的主要见解有两个：一是减少程序中分支数，二是前置高概率分支；
• How branches influence the performance of your code and what can you do about it? - Johnny’s Software Lab (johnnysswlab.com)这篇文章对不同的CPU做了一些实验来验证上述技巧的有效性，本文并没有花过多的时间进行介绍，感兴趣的可以去阅读一下原文；
• 本文介绍了很多使程序运行更快的技巧，然而这些技巧与使用场景也是密切相关的，需要在今后的工程实践中加以理解使用；此外需要注意的是，这些技巧并总是有效，例如某些技巧可能会降低代码的可阅读性等。