通过尽早计算条件来避免停止管道
Avoid stalling pipeline by calculating conditional early
在谈论 ifs 的性能时，我们通常会谈论错误预测如何使流水线停止。我看到的推荐方案是：
- 对于通常只有一个结果的条件，请相信分支预测器；或
- 尽可能避免使用一点位魔术进行分支；或
- 尽可能有条件地移动。
我找不到的是我们是否可以及早计算条件以尽可能提供帮助。所以，而不是：
... work
if (a > b) {
... more work
}
做这样的事情：
bool aGreaterThanB = a > b;
... work
if (aGreaterThanB) {
... more work
}
这样的事情是否可以完全避免在此条件下的停顿（取决于管道的长度和我们可以在 bool 和 if 之间放置的工作量）？它不必像我写的那样，但是 有没有一种方法可以尽早评估条件，这样 CPU 就不必尝试预测分支 ？
此外，如果这有帮助，编译器是否可能会这样做？
乱序执行绝对是一回事（不仅是编译器，甚至处理器芯片本身都可以对指令进行重新排序），但它对数据依赖性导致的流水线停顿的帮助大于错误预测导致的流水线停顿。
在控制流场景中的优势在某种程度上受到以下事实的限制：在大多数体系结构中，条件分支指令仅基于标志寄存器而不是基于通用寄存器做出决定。除非中间 "work" 非常不寻常，否则很难提前设置标志寄存器，因为大多数指令会更改标志寄存器（在大多数体系结构上）。
可能识别
的组合
TST (reg)
J(condition)
当 (reg) 提前设置得足够远时， 可以设计为最小化停顿。这当然需要处理器很大程度的帮助，而不仅仅是编译器。并且处理器设计人员可能会针对更早（无序）执行设置分支标志的指令的更一般情况进行优化，结果标志通过管道转发，提前结束停顿。
是，允许分支条件尽可能早计算是有益的，这样任何错误预测都可以尽早解决，管道的前端部分可以尽早开始重新填充。在最好的情况下，如果已经有足够的工作可以完全隐藏前端气泡，那么错误预测可以是 免费。
不幸的是，在乱序的 CPU 上，early 有一个有点微妙的定义，因此让分支尽早解决并不像在来源 - 您可能必须更改条件的计算方式。
什么不起作用
遗憾的是，前面的没有引用源文件中condition/branch的位置，也没有引用对应的汇编指令的位置比较或分支。因此，从根本上讲，它主要 7 不像您的示例那样工作。
即使源级别定位很重要，它也可能在您的示例中不起作用，因为：
您已将条件的评估向上移动并将其分配给 bool，但可能会产生错误预测的不是测试（< 运算符），而是后续的条件分支：毕竟，这是一个 分支 的错误预测。在您的示例中，分支在两个地方都位于同一位置：其形式只是从 if (a > b) 更改为 if (aGreaterThanB).
除此之外，您转换代码的方式不太可能欺骗大多数编译器。优化编译器不会按照您编写代码的顺序逐行发出代码，而是根据源代码级依赖项按它们认为合适的方式安排事情。提早提出条件很可能会被忽略，因为编译器希望将检查放在它自然会去的地方：大约在带有标志寄存器的体系结构上的分支之前。
例如，考虑以下两个简单函数的实现，它们遵循您建议的模式。第二个函数将条件移动到函数的顶部。
int test1(int a, int b) {
int result = a * b;
result *= result;
if (a > b) {
return result + a;
}
return result + b * 3;
}
int test2(int a, int b) {
bool aGreaterThanB = a > b;
int result = a * b;
result *= result;
if (aGreaterThanB) {
return result + a;
}
return result + b * 3;
}
我检查了 gcc、clang2 和 MSVC，并且都编译了这两个函数 identically（编译器之间的输出不同，但对于每个编译器，输出都是相同的对于这两个功能）。例如，用 gcc 编译 test2 会导致：
test2(int, int):
mov eax, edi
imul eax, esi
imul eax, eax
cmp edi, esi
jg .L4
lea edi, [rsi+rsi*2]
.L4:
add eax, edi
ret
cmp 指令对应于 a > b 条件，gcc 已将其移回所有 "work" 并放在 jg 旁边是条件分支。
什么有效
那么，如果我们知道在源代码中简单地操纵操作顺序是行不通的，那么 有什么用呢？事实证明，您可以通过移动数据流图中的分支条件 "up" 所做的任何事情都可以通过更早地解决错误预测来提高性能。我不打算深入探讨现代 CPU 如何依赖数据流，但您可以找到 brief overview here 并在末尾提供进一步阅读的指针。
遍历链表
这是一个涉及链表遍历的真实示例。
考虑将所有值相加的任务是一个空终止链表，该链表还将其长度1 存储为链表头结构的成员。链表实现为一个 list_head 对象和零个或多个列表节点（具有单个 int value 有效负载），定义如下：
struct list_node {
int value;
list_node* next;
};
struct list_head {
int size;
list_node *first;
};
canonical 搜索循环将使用最后一个节点中的 node->next == nullptr 哨兵来确定是否已到达列表末尾，如下所示：
long sum_sentinel(list_head list) {
int sum = 0;
for (list_node* cur = list.first; cur; cur = cur->next) {
sum += cur->value;
}
return sum;
}
就这么简单。
然而，这将结束求和的分支（第一个cur == null）放在节点到节点指针追逐的末尾，这是数据流图中最长的依赖关系.如果该分支预测错误，将发生预测错误的解决"late"，前端气泡将直接添加到运行时间。
另一方面，您可以通过显式计算节点来进行求和，如下所示：
long sum_counter(list_head list) {
int sum = 0;
list_node* cur = list.first;
for (int i = 0; i < list.size; cur = cur->next, i++) {
sum += cur->value;
}
return sum;
}
与哨兵解决方案相比，我们似乎增加了额外的工作：我们现在需要初始化、跟踪和递减计数4。然而，关键是这个递减依赖链非常短，因此它会 "run ahead" 指针追踪工作，并且错误预测会提前发生，而仍然有有效的剩余指针追踪工作要做，可能与运行时间的巨大改进。
让我们实际尝试一下。首先我们检查两个解决方案的程序集，这样我们就可以验证没有发生任何意外情况：
<sum_sentinel(list_head)>:
test rsi,rsi
je 1fe <sum_sentinel(list_head)+0x1e>
xor eax,eax
loop:
add eax,DWORD PTR [rsi]
mov rsi,QWORD PTR [rsi+0x8]
test rsi,rsi
jne loop
cdqe
ret
<sum_counter(list_head)>:
test edi,edi
jle 1d0 <sum_counter(list_head)+0x20>
xor edx,edx
xor eax,eax
loop:
add edx,0x1
add eax,DWORD PTR [rsi]
mov rsi,QWORD PTR [rsi+0x8]
cmp edi,edx
jne loop:
cdqe
ret
正如预期的那样，sentinel 方法稍微简单一些：在设置期间少了一条指令，在循环中少了一条指令5，但总体而言，关键指针追逐和添加步骤是相同，我们希望这个循环由连续节点指针的延迟控制。
事实上，当预测影响可以忽略不计时，循环在对短列表或长列表求和时的表现几乎相同。对于长列表，分支预测的影响自动变小，因为到达列表末尾时的单个错误预测会在多个节点上分摊，并且 运行time 渐近地达到每个节点几乎恰好 4 个周期L1，这是我们对英特尔最佳情况 4 周期加载到使用延迟的预期。
对于短列表，如果列表的模式是可预测的，则分支预测错误可以忽略不计：总是相同或以某个适度周期循环（可以是 1000 或更多，预测良好！）。在这种情况下，当对许多短列表求和时，每个节点的时间可以少于 4 个周期，因为多个列表可以同时运行（例如，如果汇总列表数组）。在任何情况下，两种实现的表现几乎相同。例如，当列表总是有 5 个节点时，无论哪种实现，对一个列表求和的时间大约为 12 个周期：
** Running benchmark group Tests written in C++ **
Benchmark Cycles BR_MIS
Linked-list w/ Sentinel 12.19 0.00
Linked-list w/ count 12.40 0.00
让我们将分支预测添加到组合中，方法是更改 list generation code 以创建 平均长度 长度为 5 的列表，但实际长度均匀分布在 [0, 10]。求和代码没有变化：只是输入不同。随机列表长度的结果：
** Running benchmark group Tests written in C++ **
Benchmark Cycles BR_MIS
Linked-list w/ Sentinel 43.87 0.88
Linked-list w/ count 27.48 0.89
BR_MIS 列显示我们在每个列表6 中得到近一个分支预测错误，正如预期的那样，因为循环退出是不可预测的。
但是，哨兵算法现在需要大约 44 个周期，而计数算法需要大约 27.5 个周期。计数算法快了大约 16.5 个周期。您可以使用列表长度和其他因素，并更改绝对时间，但增量几乎总是在 16-17 个周期左右，这与最近 Intel 的分支预测错误惩罚大致相同并非巧合！通过尽早解决分支条件，我们避免了前端泡沫，那里什么都不会发生。
提前计算迭代次数
另一个例子类似于计算浮点值的循环，比如泰勒级数近似，其中终止条件取决于计算值的某个函数。这与上面的效果相同：终止条件取决于慢循环携带的依赖性，因此它的解析速度与值本身的计算一样慢。如果出口不可预测，您将在出口处遇到停滞。
如果您可以将其更改为预先计算迭代计数，则可以使用解耦整数计数器作为终止条件，从而避免出现气泡。即使前期计算增加了一些时间，它仍然可以提供整体加速（并且计算可以 运行 与循环的第一次迭代并行，无论如何，所以它的成本可能要低得多d 通过查看它的延迟来期望）。
1 MIPS 是一个有趣的例外，它没有标志寄存器——测试结果直接存储到通用寄存器中。
2 Clang 以无分支方式编译了这个和许多其他变体，但它仍然很有趣，因为您仍然具有相同的测试指令结构和条件移动（代替分行）。
3 就像 C++11 std::list.
4 事实证明，在 x86 上，由于 dec 隐式设置零标志，所以我们不需要额外的 test 指令，而指针追踪中使用的 mov 不需要，所以计数器方法有一个额外的 dec 而哨兵方法有一个额外的测试，使它成为一个洗涤。
5 虽然这部分只是因为 gcc 没有设法将递增 for 循环转换为递减循环以利用 dec 设置零标志，避免 cmp。也许较新的 gcc 版本做得更好。另见脚注 4。
6 我猜这比 1.0 更接近 0.9，因为分支预测器可能仍然得到 length = 10 的情况是正确的，因为一旦你循环了 9 次下一次迭代总是会退出。较少的 synthetic/exact 分布不会表现出这一点。
7 我说 主要是 因为在某些情况下，您可能会通过此类源代码或程序集级别的重新排序节省一两个周期，因为这些事情对乱序处理器的执行顺序影响很小，执行顺序也受汇编顺序影响，但仅在数据流图的约束范围内。另见 。
分支预测失误的主要问题不是它在刷新较新的操作（相对较快）时作为惩罚而招致的几个周期，而是如果分支存在数据依赖性，它可能会沿着管道很晚发生条件必须先解决。
对于基于先前计算的分支，依赖项就像其他操作一样工作。此外，分支很早就沿着管道通过预测，以便机器可以继续获取和分配进一步的操作。如果预测不正确（数据依赖分支的情况更常见，不像循环控制通常表现出更可预测的模式），那么只有在解决依赖关系并且预测被证明是错误的情况下才会发生刷新。越晚处罚越大。
由于乱序执行会在解决依赖关系后立即安排操作（假设没有端口压力），因此向前移动操作可能不会有帮助，因为它不会改变依赖链，也不会影响调度时间太多。唯一的潜在好处是，如果你将它移动得足够远，以便 OOO window 可以更早地看到它，但现代 CPU 通常 运行 提前数百条指令，并且提升指令那么远而不会破坏程序很难。不过，如果您要 运行 进行一些循环，那么如果可能的话，提前计算未来迭代的条件可能会很简单。
None 这将改变完全正交的预测过程，但一旦分支到达机器的 OOO 部分，它将立即得到解决，如果需要则清除，并产生最小的惩罚.
在谈论 ifs 的性能时，我们通常会谈论错误预测如何使流水线停止。我看到的推荐方案是：
- 对于通常只有一个结果的条件，请相信分支预测器；或
- 尽可能避免使用一点位魔术进行分支；或
- 尽可能有条件地移动。
我找不到的是我们是否可以及早计算条件以尽可能提供帮助。所以，而不是：
... work
if (a > b) {
... more work
}
做这样的事情：
bool aGreaterThanB = a > b;
... work
if (aGreaterThanB) {
... more work
}
这样的事情是否可以完全避免在此条件下的停顿（取决于管道的长度和我们可以在 bool 和 if 之间放置的工作量）？它不必像我写的那样，但是 有没有一种方法可以尽早评估条件，这样 CPU 就不必尝试预测分支 ？
此外，如果这有帮助，编译器是否可能会这样做？
乱序执行绝对是一回事（不仅是编译器，甚至处理器芯片本身都可以对指令进行重新排序），但它对数据依赖性导致的流水线停顿的帮助大于错误预测导致的流水线停顿。
在控制流场景中的优势在某种程度上受到以下事实的限制：在大多数体系结构中，条件分支指令仅基于标志寄存器而不是基于通用寄存器做出决定。除非中间 "work" 非常不寻常，否则很难提前设置标志寄存器，因为大多数指令会更改标志寄存器（在大多数体系结构上）。
可能识别
的组合TST (reg)
J(condition)
(reg) 提前设置得足够远时，可以设计为最小化停顿。这当然需要处理器很大程度的帮助，而不仅仅是编译器。并且处理器设计人员可能会针对更早（无序）执行设置分支标志的指令的更一般情况进行优化，结果标志通过管道转发，提前结束停顿。
是，允许分支条件尽可能早计算是有益的，这样任何错误预测都可以尽早解决，管道的前端部分可以尽早开始重新填充。在最好的情况下，如果已经有足够的工作可以完全隐藏前端气泡，那么错误预测可以是 免费。
不幸的是，在乱序的 CPU 上，early 有一个有点微妙的定义，因此让分支尽早解决并不像在来源 - 您可能必须更改条件的计算方式。
什么不起作用
遗憾的是，前面的没有引用源文件中condition/branch的位置，也没有引用对应的汇编指令的位置比较或分支。因此，从根本上讲，它主要 7 不像您的示例那样工作。
即使源级别定位很重要，它也可能在您的示例中不起作用，因为：
您已将条件的评估向上移动并将其分配给 bool，但可能会产生错误预测的不是测试（< 运算符），而是后续的条件分支：毕竟，这是一个 分支 的错误预测。在您的示例中，分支在两个地方都位于同一位置：其形式只是从 if (a > b) 更改为 if (aGreaterThanB).
除此之外，您转换代码的方式不太可能欺骗大多数编译器。优化编译器不会按照您编写代码的顺序逐行发出代码，而是根据源代码级依赖项按它们认为合适的方式安排事情。提早提出条件很可能会被忽略，因为编译器希望将检查放在它自然会去的地方：大约在带有标志寄存器的体系结构上的分支之前。
例如，考虑以下两个简单函数的实现，它们遵循您建议的模式。第二个函数将条件移动到函数的顶部。
int test1(int a, int b) {
int result = a * b;
result *= result;
if (a > b) {
return result + a;
}
return result + b * 3;
}
int test2(int a, int b) {
bool aGreaterThanB = a > b;
int result = a * b;
result *= result;
if (aGreaterThanB) {
return result + a;
}
return result + b * 3;
}
我检查了 gcc、clang2 和 MSVC，并且都编译了这两个函数 identically（编译器之间的输出不同，但对于每个编译器，输出都是相同的对于这两个功能）。例如，用 gcc 编译 test2 会导致：
test2(int, int):
mov eax, edi
imul eax, esi
imul eax, eax
cmp edi, esi
jg .L4
lea edi, [rsi+rsi*2]
.L4:
add eax, edi
ret
cmp 指令对应于 a > b 条件，gcc 已将其移回所有 "work" 并放在 jg 旁边是条件分支。
什么有效
那么，如果我们知道在源代码中简单地操纵操作顺序是行不通的，那么 有什么用呢？事实证明，您可以通过移动数据流图中的分支条件 "up" 所做的任何事情都可以通过更早地解决错误预测来提高性能。我不打算深入探讨现代 CPU 如何依赖数据流，但您可以找到 brief overview here 并在末尾提供进一步阅读的指针。
遍历链表
这是一个涉及链表遍历的真实示例。
考虑将所有值相加的任务是一个空终止链表，该链表还将其长度1 存储为链表头结构的成员。链表实现为一个 list_head 对象和零个或多个列表节点（具有单个 int value 有效负载），定义如下：
struct list_node {
int value;
list_node* next;
};
struct list_head {
int size;
list_node *first;
};
canonical 搜索循环将使用最后一个节点中的 node->next == nullptr 哨兵来确定是否已到达列表末尾，如下所示：
long sum_sentinel(list_head list) {
int sum = 0;
for (list_node* cur = list.first; cur; cur = cur->next) {
sum += cur->value;
}
return sum;
}
就这么简单。
然而，这将结束求和的分支（第一个cur == null）放在节点到节点指针追逐的末尾，这是数据流图中最长的依赖关系.如果该分支预测错误，将发生预测错误的解决"late"，前端气泡将直接添加到运行时间。
另一方面，您可以通过显式计算节点来进行求和，如下所示：
long sum_counter(list_head list) {
int sum = 0;
list_node* cur = list.first;
for (int i = 0; i < list.size; cur = cur->next, i++) {
sum += cur->value;
}
return sum;
}
与哨兵解决方案相比，我们似乎增加了额外的工作：我们现在需要初始化、跟踪和递减计数4。然而，关键是这个递减依赖链非常短，因此它会 "run ahead" 指针追踪工作，并且错误预测会提前发生，而仍然有有效的剩余指针追踪工作要做，可能与运行时间的巨大改进。
让我们实际尝试一下。首先我们检查两个解决方案的程序集，这样我们就可以验证没有发生任何意外情况：
<sum_sentinel(list_head)>:
test rsi,rsi
je 1fe <sum_sentinel(list_head)+0x1e>
xor eax,eax
loop:
add eax,DWORD PTR [rsi]
mov rsi,QWORD PTR [rsi+0x8]
test rsi,rsi
jne loop
cdqe
ret
<sum_counter(list_head)>:
test edi,edi
jle 1d0 <sum_counter(list_head)+0x20>
xor edx,edx
xor eax,eax
loop:
add edx,0x1
add eax,DWORD PTR [rsi]
mov rsi,QWORD PTR [rsi+0x8]
cmp edi,edx
jne loop:
cdqe
ret
正如预期的那样，sentinel 方法稍微简单一些：在设置期间少了一条指令，在循环中少了一条指令5，但总体而言，关键指针追逐和添加步骤是相同，我们希望这个循环由连续节点指针的延迟控制。
事实上，当预测影响可以忽略不计时，循环在对短列表或长列表求和时的表现几乎相同。对于长列表，分支预测的影响自动变小，因为到达列表末尾时的单个错误预测会在多个节点上分摊，并且 运行time 渐近地达到每个节点几乎恰好 4 个周期L1，这是我们对英特尔最佳情况 4 周期加载到使用延迟的预期。
对于短列表，如果列表的模式是可预测的，则分支预测错误可以忽略不计：总是相同或以某个适度周期循环（可以是 1000 或更多，预测良好！）。在这种情况下，当对许多短列表求和时，每个节点的时间可以少于 4 个周期，因为多个列表可以同时运行（例如，如果汇总列表数组）。在任何情况下，两种实现的表现几乎相同。例如，当列表总是有 5 个节点时，无论哪种实现，对一个列表求和的时间大约为 12 个周期：
** Running benchmark group Tests written in C++ **
Benchmark Cycles BR_MIS
Linked-list w/ Sentinel 12.19 0.00
Linked-list w/ count 12.40 0.00
让我们将分支预测添加到组合中，方法是更改 list generation code 以创建 平均长度 长度为 5 的列表，但实际长度均匀分布在 [0, 10]。求和代码没有变化：只是输入不同。随机列表长度的结果：
** Running benchmark group Tests written in C++ **
Benchmark Cycles BR_MIS
Linked-list w/ Sentinel 43.87 0.88
Linked-list w/ count 27.48 0.89
BR_MIS 列显示我们在每个列表6 中得到近一个分支预测错误，正如预期的那样，因为循环退出是不可预测的。
但是，哨兵算法现在需要大约 44 个周期，而计数算法需要大约 27.5 个周期。计数算法快了大约 16.5 个周期。您可以使用列表长度和其他因素，并更改绝对时间，但增量几乎总是在 16-17 个周期左右，这与最近 Intel 的分支预测错误惩罚大致相同并非巧合！通过尽早解决分支条件，我们避免了前端泡沫，那里什么都不会发生。
提前计算迭代次数
另一个例子类似于计算浮点值的循环，比如泰勒级数近似，其中终止条件取决于计算值的某个函数。这与上面的效果相同：终止条件取决于慢循环携带的依赖性，因此它的解析速度与值本身的计算一样慢。如果出口不可预测，您将在出口处遇到停滞。
如果您可以将其更改为预先计算迭代计数，则可以使用解耦整数计数器作为终止条件，从而避免出现气泡。即使前期计算增加了一些时间，它仍然可以提供整体加速（并且计算可以 运行 与循环的第一次迭代并行，无论如何，所以它的成本可能要低得多d 通过查看它的延迟来期望）。
1 MIPS 是一个有趣的例外，它没有标志寄存器——测试结果直接存储到通用寄存器中。
2 Clang 以无分支方式编译了这个和许多其他变体，但它仍然很有趣，因为您仍然具有相同的测试指令结构和条件移动（代替分行）。
3 就像 C++11 std::list.
4 事实证明，在 x86 上，由于 dec 隐式设置零标志，所以我们不需要额外的 test 指令，而指针追踪中使用的 mov 不需要，所以计数器方法有一个额外的 dec 而哨兵方法有一个额外的测试，使它成为一个洗涤。
5 虽然这部分只是因为 gcc 没有设法将递增 for 循环转换为递减循环以利用 dec 设置零标志，避免 cmp。也许较新的 gcc 版本做得更好。另见脚注 4。
6 我猜这比 1.0 更接近 0.9，因为分支预测器可能仍然得到 length = 10 的情况是正确的，因为一旦你循环了 9 次下一次迭代总是会退出。较少的 synthetic/exact 分布不会表现出这一点。
7 我说 主要是 因为在某些情况下，您可能会通过此类源代码或程序集级别的重新排序节省一两个周期，因为这些事情对乱序处理器的执行顺序影响很小，执行顺序也受汇编顺序影响，但仅在数据流图的约束范围内。另见
分支预测失误的主要问题不是它在刷新较新的操作（相对较快）时作为惩罚而招致的几个周期，而是如果分支存在数据依赖性，它可能会沿着管道很晚发生条件必须先解决。
对于基于先前计算的分支，依赖项就像其他操作一样工作。此外，分支很早就沿着管道通过预测，以便机器可以继续获取和分配进一步的操作。如果预测不正确（数据依赖分支的情况更常见，不像循环控制通常表现出更可预测的模式），那么只有在解决依赖关系并且预测被证明是错误的情况下才会发生刷新。越晚处罚越大。
由于乱序执行会在解决依赖关系后立即安排操作（假设没有端口压力），因此向前移动操作可能不会有帮助，因为它不会改变依赖链，也不会影响调度时间太多。唯一的潜在好处是，如果你将它移动得足够远，以便 OOO window 可以更早地看到它，但现代 CPU 通常 运行 提前数百条指令，并且提升指令那么远而不会破坏程序很难。不过，如果您要 运行 进行一些循环，那么如果可能的话，提前计算未来迭代的条件可能会很简单。
None 这将改变完全正交的预测过程，但一旦分支到达机器的 OOO 部分，它将立即得到解决，如果需要则清除，并产生最小的惩罚.