分支对性能的影响以及分支优化

,

1. 参考文章

How branches influence the performance of your code and what can you do about it?

2. 概述

本文属于上述参考文章的一篇读后感，该文章讲了一些关于分支对于软件性能的影响，以及如何通过优化代码中的分支来提高性能。因为之前的工作中也涉及到类似的工作，顺路在这里重新学习并总结一下。

3. 详述

分支（branch，jump）是非常常见的指令类型之一。根据统计，平均每五条指令就要遇到一条分支指令。对于CPU来说，有效的分支实现对于良好的性能至关重要。

3.1. CPU相关的知识

许多现代处理器（但不是全部，特别是嵌入式系统中使用的一些处理器）都具有以下部分或全部功能：

  • 流水线（pipeline）：流水线允许CPU同时执行多条指令。CPU将每条指令的执行分为几个阶段，并且每条指令处于不同的执行阶段。汽车工厂也采用同样的原理：在任何给定时间，工厂同时生产五十辆汽车，例如，一辆汽车正在喷漆，另一辆汽车正在安装发动机，第三辆汽车正在安装车灯，流水线可以很短，只有几个阶段（例如三个阶段），也可以很长，有很多阶段（例如二十个阶段）。

  • 乱序执行（OOE，out of order exexcution）：从程序员的角度来看，程序运行一条又一条指令。在CPU中情况看起来完全不同：CPU不需要按照指令在内存中出现的顺序来执行它们。在执行过程中，一些指令会被阻塞在CPU中等待来自内存的数据或者等待来自其他指令的数据。CPU可以向前看并执行稍后出现但不会被阻塞的指令。当被阻止的指令的数据变得可用时，之前未被阻止的指令已经完成。这可以节省CPU指令执行周期。

  • 推断执行（speculative exexcution）：即使不能100%确定需要执行指令，CPU也可以开始执行指令。例如，它会猜测条件分支指令的目的地，然后在100%确定会采用分支之前开始执行分支目的地的指令。如果后来CPU发现猜测（推断）是错误的，它将取消推断执行指令的结果，并且一切都将显示为没有进行任何推断。

  • 分支预测（branch prediction）：现代CPU具有特殊电路，每个分支指令都会记住其先前的结果：采用分支或未采用分支。当下次执行相同的分支指令时，CPU将使用该信息来猜测分支的目的地，然后在分支目的地开始推断执行指令。如果分支预测器正确，这将导致性能加速。

所有现代处理器都具有pipeline，以便更好地利用CPU资源。并大多数都有分支预测和推断执行。就乱序执行而言，大多数低端低功耗处理器不具备此功能，因为它消耗大量电量且速度提升并不大。

3.2. CPU处理分支的几种方法

当分支指令进入处理器流水线时，在对其进行解码并计算其目的地之前，分支目的地是未知的。分支指令之后的指令可以是：直接跟随分支的指令或分支目的地处的指令。CPU对于分支指令的处理可以有三种方式：

  • 暂停流水线（pause pipeline，stall pipeline）：暂停流水线并停止解码指令，直到分支指令被解码并且知道分支目的地。然后它可以使用正确的指令恢复加载流水线。

  • 加载紧随分支之后的指令。万一后来发现这是错误的选择，处理器将需要刷新流水线并开始从分支目的地加载正确的指令。

  • 询问分支预测器是否应该加载紧接在分支之后的指令或分支目的地处的指令。分支预测器还需要告诉流水线分支目的地在哪里（否则将新指令加载到流水线中并将需要等待流水线解析分支目的地）。

采用第一种方式的处理器现在很少见，除了一些非常低端的嵌入式处理器，仅仅让处理器什么都不做就是浪费资源。因此大多数处理器会执行采用第二种方式，常见于低端嵌入式系统和低功耗处理器。采用第三种方式的处理器是常见的台式机和笔记本电脑CPU以及高性能CPU。

3.3. 分支对于性能的影响

主要介绍以下两点影响：

  • 在某些处理器上，指令自上而下“贯穿”（fall through）的开销远远小于分支指令的开销。

  • 自动向量化（auto vectorization）是现代处理器中比较常用的提高性能的手段，分支的加入通常导致代码无法向量化。

3.4. 分支优化手段

本文重点不在于介绍分支预测，而是较少如何优化代码达到去分支或减少分支来提高软件性能。

3.4.1. 优化连接条件（join condition）

连接条件是(cond1 && cond2)或(cond1 || cond2)类型的条件。根据C和C++标准，在(cond1 && cond2)的情况下，如果cond1为false，则不会评估cond2。类似地，在(cond1 || cond2)的情况下，如果cond1为true，则不会评估cond2。

3.4.2. 优化if/else结构

以如下代码为例：

1
2
3
4
5
6
7
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%。在这种情况下，重新排列上述代码是最合乎逻辑的：

1
2
3
4
5
6
7
if (a < 0) { 
    do_something_yet_else();
} else if (a > 0) { 
   do_something();
} else {
    do_something_else();
}

3.4.3. 使用查找表替换switch语句

在删除分支时，查找表（lookup table, LUT）有时会很方便。不幸的是，在switch语句中，分支在大多数情况下很容易预测，因此这种优化可能不会产生任何效果。示例如下：

1
2
3
4
5
6
7
switch(day) {
    case MONDAY: return "Monday";
    case TUESDAY: return "Tuesday";
   ...
    case SUNDAY: return "Sunday";
    default: return "";
};

上面的语句可以使用LUT来实现：

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

通常，编译器可以通过用查找表替换开关来为完成这项工作。

3.4.4. 将最常见的情况移出switch语句

如果使用switch命令并且其中一种情况似乎最常见，可以将其移出switch并给予特殊处理。继续上一节的示例：

1
2
3
4
5
6
7
8
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;
        ....
    };
}

3.4.5. 重写连接条件

如前所述，在连接条件的情况下，如果第一个条件具有特定值，则根本不需要评估第二个条件。编译器是如何做到这一点的？以下面的函数为例：

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

现在假设a[i] > x和a[i] < y评估起来很便宜（所有数据都在寄存器或缓存中）但难以预测。该序列将转换为以下伪汇编程序：

1
2
3
4
if_not (a[i] > x) goto ENDIF;
if_not (a[i] < y) goto ENDIF;
do_something;
ENDIF

这里有两个难以预测的分支。如果我们用&而不是&&连接两个条件，我们将：

  • 强制同时评估两个条件：&运算符是算术AND运算，并且必须评估两边。
  • 使条件更容易预测，从而降低分支误预测率：两个完全独立的条件（概率为50%）将产生一个联合条件（概率为25%）。
  • 摆脱一个分支：我们将拥有一个更容易预测的分支，而不是原来的两个分支。

运算符&评估这两个条件，并且在生成的程序集中将只有一个分支而不是两个。同样的情况也适用于运算符||及其孪生运算符|。
请注意：根据C++标准，bool类型的值为0表示false，任何其他值表示true。C++标准保证逻辑运算和算术比较的结果始终为零或一，但不能保证所有布尔值都只有这两个值。您可以通过应用!!来标准化bool变量其上的操作。

3.4.6. 向编译器建议哪个分支概率更高

GCC和CLANG提供了关键字，程序员可以使用这些关键字来告诉他们哪些分支具有更高的概率。例如：

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

通常我们通过可能和不太可能的宏使用__builtin_expect，因为它们的语法在任何地方使用都很麻烦。当这样注释时，编译器将重新排列if和else分支中的指令，以便最优化地使用底层硬件。请确保条件概率正确，否则性能可能会下降。

3.4.7. 使用无分支算法

一些用分支表达的算法可以转换为无分支算法。例如，下面的函数abs使用一种技巧来计算数字的绝对值。

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

3.4.8. 使用条件加载而不是分支

许多CPU支持可用于删除分支的条件移动指令。这是一个例子：

1
2
3
if (x > y) {
    x++;
}

可以重写为：

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

编译器应该认识到第2行的命令可以写为变量x的条件加载并发出条件移动指令。不幸的是，编译器对于何时发出条件分支有自己的内部逻辑，这并不总是像开发人员所期望的那样。但是，可以使用内联汇编来强制条件加载。

3.4.9. 通过算术实现无分支

有一种方法可以通过巧妙地使用算术运算来实现无分支。条件增量示例：

1
2
3
4
5
6
// With branch
if (a > b) {
    x += y;
}
// Branchless
x += -(a > b) & y;

在上面的示例中，表达式-(a > b)将创建一个掩码，当条件为假时，该掩码为0；当条件为真时，该掩码全为1。

条件赋值的示例：

1
2
3
4
5
// With branch
x = (a > b) ? val_a : val_b;
// Branchless
x = val_a;
x += -(a > b) & (val_b - val_a);

在循环缓冲区中移动索引的示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 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;
}

3.4.10. 重新组织代码以避免分支

假设您有一个名为animation的类，它可以是可见的也可以是隐藏的。处理可见animation与处理隐藏animation有很大不同。有一个包含名为animation_list的animation的列表，处理如下所示：

1
2
3
4
5
6
7
8
9
10
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();
    }
}

除非animation根据可见性进行排序，否则分支预测器确实很难处理上述代码。有两种方法可以解决这个问题。一是根据is_visible()对animation_list中的动画进行排序。第二种是创建两个列表，animation_list_visible和animation_list_hidden，并重写代码如下：

1
2
3
4
5
6
7
8
9
10
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();
}

所有的条件都消失了，并且没有分支错误预测。

3.4.11. 使用模板删除分支

如果将布尔值传递给函数并且在函数内部将其用作参数，则可以通过将其作为模板参数传递来删除它。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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的条件。要删除评估，请将参数作为模板参数而不是函数参数传递。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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，一种不带有include_negatives（以防调用此参数具有不同值的函数）。分支完全消失了，未使用的分支中的代码也消失了。

但现在需要以不同的方式调用您的函数。所以会这样称呼它：

1
2
3
4
5
6
7
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 optimization的编译器优化。如果include_negatives的值在编译时已知并且编译器决定内联函数平均值，它将删除分支和未使用的代码。然而，带有模板的版本保证了这一点，而原始版本则不然。

编译器通常可以进行这种优化。如果编译器可以保证值include_negatives在循环执行期间不会更改其值，则它可以创建两个版本的循环：一种用于其值为true的情况，另一种用于其值为false的情况。这种优化称为循环不变代码优化。

3.4.12. 避免分支的其他一些技巧

如果在代码中多次检查不可更改的条件，则通过检查一次然后进行一些代码复制可能会获得更好的性能。因此，在下面的示例中，两个分支可以替换为一个分支。

1
2
3
4
5
6
7
if (is_visible) {
    hide();
}
process();
if (is_visible) {
    display();
}

可以替换为：

1
2
3
4
5
6
7
if (is_visible) {
    hide();
    process();
    display();
} else {
    process();
}

您还可以引入一个两元素数组，一个用于在条件为true时保存结果，另一个用于在条件为false时保存结果。一个例子：

1
2
3
4
5
6
7
int larger = 0;
for (int i = 0; i < n; i++) {
    if (a[i] > m) {
        larger++;
    }
}
return larger;

可以替换为：

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

3.5. 实验

作者在“AMD A8-4500M quad-core x86-64” ，“Allwinner sun7i A20 dual-core ARMv7”和“Ingenic JZ4780 dual-core MIPS32r2”三种处理器上进行了多组对照试验，具体细节暂不描述，结论如下：

分支推测打破了一些数据依赖性，并有效地掩盖了CPU需要等待内存数据的时间。如果分支预测器的猜测是正确的，那么当数据从内存到达时，很多工作就已经完成了。对于无分支的代码来说，情况并非如此。