完美预测分支的分支预测开销
Branch prediction overhead of perfectly predicted branch
我读到一个完美预测的分支的开销为零/几乎为零。 （例如在 Effects of branch prediction on performance? 的回答中）
我不太明白人们的意思。至少要评估分支条件，这可以是一个简单的 bool 或函数调用，这需要时间。
分支预测是在指令级别预测条件的结果，这是 C 或 C++ 条件下的实际结果 - 如果这是一百万个字符串比较的结果，它可能不是特别有用，因为比较会花费很多时间。如果它是 for 循环的结束条件，它迭代两个字符串，每个字符串都有一百万个字符，那么它非常有用，因为它在该循环中发生了很多次（假设字符串相等）。
对两个长字符串进行字符串比较不是免费的。可以自由猜测，字符串比较将继续（直到我们找到字符串的结尾或差异，此时分支预测出错）。
A "unpredictable" 分支将导致处理器不知道代码继续到哪里。现代 CPU 有相当长的流水线（15-30 步），所以如果流水线没有充满 "right" 代码，处理器将不得不等待 "right" 代码完成通过管道滴流。
所以要回答实际问题：
当分支本身被很好地预测时，处理器已经在流水线中获得了RIGTH指令，并且没有"pipeline bubble"走完流水线才能执行正确的指令继续程序.看下面的类比。如果预测错误，流水线中就会有正确指令以外的其他内容，处理器必须通过这些指令来处理，然后将它们丢弃。
把它想象成一家汽车工厂，生产 A 型和 B 型汽车，在一条生产线上，首先将车身安装到底盘上，然后喷漆（神奇的油漆，它几乎立即干燥），然后安装发动机和变速箱，然后装上轮子，装上车灯，最后装上玻璃，就成了一辆完整的车。每一步需要 20 分钟执行，小车的传送带每 20 分钟就会向前移动到下一个位置[对于这个练习，我们忽略移动本身需要时间的事实]。
你是生产线负责人，生产线上有一堆A车。突然，大老板说，"we've just got an order for B cars, change to making model B immediately"。因此，您开始将 B 车零件送入生产线。但是下一辆B车在另一端出来还需要一段时间。
分支预测的工作方式是 "guesses" 代码是否会改变方向或转到下一条指令。如果它猜对了，就像猜什么时候 "big boss" 下来告诉你在 A 和 B 车型之间切换，这样你就可以在老板需要的时候让合适的车准备好下线，而不是而不是等待整条生产线
当它工作时，它很棒，因为预期的事情已经准备就绪。如果你猜错了，你仍然需要等待生产线的其余部分 运行 通过当前设置，并将它们存放到 "we don't have a customer for these" 角落（或 CPU 说明 "discard the instruction").
大多数现代 CPU 也允许 "speculative execution"。这意味着处理器将在实际确定条件之前开始执行指令。所以在老板说之前，处理器会从 A 车转向 B 车。如果到那时，老板说 "no, you should keep working on A cars"，你有一堆车要丢弃，你已经开始工作了。您不一定要制造所有的汽车，但您必须让它们通过生产线，每 20 分钟一个步骤。
总结
评估分支条件总是需要一些工作，即使预测得很好，但由于现代CPU的内部并行性额外工作 不必添加到特定指令序列的 成本 。
详情
我认为部分混淆在于许多人执行 CPU 指令时的心理表现模型。是的，每条指令都需要一些 work，所以这应该意味着每条指令都有一些 cost，但以执行时间衡量时，无论多小，对吧？
好吧，如果执行的总成本只是简单地添加到每条指令的工作中，那将是正确的 - 您只需将所有 工作 加在一起并得到最终的 费用。由于现代 CPUs 中大量的并行性，它不是那样工作的。
可以把它想象成举办生日派对。你可能要买面粉，花 10 分钟，然后烤一个蛋糕，花 60 分钟，然后去拿 30 分钟路程外的特别礼物。这些时间都是 activity 所需的 "work"。但是，有人可以在捡面粉和烤蛋糕的时候去拿礼物。但是，没有面粉就不能烤蛋糕。所以你有两个依赖链：70 分钟买面粉 -> 烤蛋糕链，和 30 分钟取礼物链。在无限并行的情况下，只有 70 分钟的蛋糕相关链有助于一切准备就绪的时间。领取礼物需要 30 分钟的工作，但最终 花费 时间（不延迟所有任务的完成），由于其他工作需要更长的时间（又名关键路径）并且并行发生。
可以并行完成更多额外任务，直到您 运行 没有人可以分配给他们。 （此时，执行吞吐量限制开始增加延迟，这称为资源冲突。如果资源冲突延迟了关键路径，而不是较短的依赖链之一。CPUs 不知道哪个依赖链是/将是关键路径，因此他们的调度不会像聪明人在这个规划类比中那样优先考虑它。）
要了解这些东西如何直接应用于 CPU 的不那么抽象但更实用的外观，请参阅 A Whirlwind Introduction to Dataflow Graphs。
一旦我们有了这个新的心智模型，其中指令序列的成本通常由通过序列的一些关键路径决定，我们就可以开始明白为什么 well-predicted 分支的成本通常非常低或为零:
- 分支指令没有输出寄存器和没有内存输出1。这意味着它们不能参与典型的依赖链，除非作为最终节点 - 它们总是 end 依赖链。所以分支不参与长依赖链的形成，因此在某种意义上 "out of line" 并且可以自由地与其他结果并行计算。
- 分支指令的实际执行通常需要很少的工作：在现代 x86 上，它们可以在两个端口上执行，延迟为 1 个周期。此外，分支指令可以 融合 与先前的 ALU 操作，并且生成的操作仍然在 1 个周期内执行 - 因此在某种意义上，分支有时可以折叠到先前的操作中 因为在执行时没有额外的工作2。这明显有助于 "near zero cost" 论点，但也有助于 "truly zero cost" 论点，因为需要更少的资源意味着它不太可能触发会干扰零成本执行计划的吞吐量瓶颈。
这些因素结合起来使得大多数预测的分支指令成本为零或几乎为零。
你不必相信我的话，让我们看一个真实的例子：
int mul1(int count, int x) {
do {
x *= 111;
} while (--count);
return x;
}
给定一个 count 和一个初始值 x，它将 x 乘以 111 count 次，得到 returns 结果。循环 assembles 到 3 条指令 一条用于乘法，一条用于 --count 和一条用于检查 count 值的分支：
.L2:
imul eax, eax, 111
sub edi, 1
jne .L2
现在是同一个循环，但多了一个分支：
int mul2(int count, int x) {
do {
x *= 111;
if (x == 0) {
abort();
}
} while (--count);
return x;
}
这assembles到5条指令。额外的两个用于 x 的测试和测试显示 x 为零的分支：
.L7:
imul eax, eax, 111
test eax, eax
je .L12 ; ends up calling abort
sub edi, 1
jne .L7
那么增加 60% 的指令（包括分支）的成本是多少？零，至少到4位有效数字3:
Running benchmarks groups using timer libpfc
** Running benchmark group Whosebug tests **
Benchmark Cycles
No branch 3.000
Added test-branch 3.000
外观每次迭代需要 3 个周期，因为它受到涉及 3 个周期乘法的依赖链的限制。额外的指令和分支没有任何成本，因为它们没有添加到这个依赖链并且能够执行 "out of line"，隐藏在关键路径的延迟之后。
1 从概念上讲，分支指令写"rip" 寄存器，但这根本不像其他寄存器那样对待：它的进展是提前预测的，所以依赖性被预测器打破了。
2 当然，首先解码和融合指令还有额外的工作，但这通常不是瓶颈，所以可能是 "free"在成本方面，uop 缓存之类的东西意味着它甚至可能不会经常执行。此外，在 x86 上，虽然融合分支指令与 ALU op 具有相同的延迟，但就其可以在哪些端口上执行而言，它的灵活性较低，因此根据端口压力，融合指令可能会产生一些成本与裸 ALU 运算相比。
3 事实上，如果您转到 "infinite" 有效数字并查看原始循环计数，您会发现此循环的额外迭代成本 exactly 在这两种情况下都是 3 个周期。 no-branch 案例通常最终会缩短 1 个周期（随着迭代次数的增加，相对意义上的差异变为 0），可能是因为初始 non-steady-state 迭代需要一个额外的周期，或者错误预测恢复在最后一次迭代中需要一个额外的周期。
我读到一个完美预测的分支的开销为零/几乎为零。 （例如在 Effects of branch prediction on performance? 的回答中）
我不太明白人们的意思。至少要评估分支条件，这可以是一个简单的 bool 或函数调用，这需要时间。
分支预测是在指令级别预测条件的结果，这是 C 或 C++ 条件下的实际结果 - 如果这是一百万个字符串比较的结果，它可能不是特别有用，因为比较会花费很多时间。如果它是 for 循环的结束条件，它迭代两个字符串，每个字符串都有一百万个字符，那么它非常有用，因为它在该循环中发生了很多次（假设字符串相等）。
对两个长字符串进行字符串比较不是免费的。可以自由猜测，字符串比较将继续（直到我们找到字符串的结尾或差异，此时分支预测出错）。
A "unpredictable" 分支将导致处理器不知道代码继续到哪里。现代 CPU 有相当长的流水线（15-30 步），所以如果流水线没有充满 "right" 代码，处理器将不得不等待 "right" 代码完成通过管道滴流。
所以要回答实际问题：
当分支本身被很好地预测时，处理器已经在流水线中获得了RIGTH指令，并且没有"pipeline bubble"走完流水线才能执行正确的指令继续程序.看下面的类比。如果预测错误，流水线中就会有正确指令以外的其他内容，处理器必须通过这些指令来处理，然后将它们丢弃。
把它想象成一家汽车工厂，生产 A 型和 B 型汽车，在一条生产线上，首先将车身安装到底盘上，然后喷漆（神奇的油漆，它几乎立即干燥），然后安装发动机和变速箱，然后装上轮子，装上车灯，最后装上玻璃，就成了一辆完整的车。每一步需要 20 分钟执行，小车的传送带每 20 分钟就会向前移动到下一个位置[对于这个练习，我们忽略移动本身需要时间的事实]。
你是生产线负责人，生产线上有一堆A车。突然，大老板说，"we've just got an order for B cars, change to making model B immediately"。因此，您开始将 B 车零件送入生产线。但是下一辆B车在另一端出来还需要一段时间。
分支预测的工作方式是 "guesses" 代码是否会改变方向或转到下一条指令。如果它猜对了，就像猜什么时候 "big boss" 下来告诉你在 A 和 B 车型之间切换，这样你就可以在老板需要的时候让合适的车准备好下线，而不是而不是等待整条生产线
当它工作时，它很棒，因为预期的事情已经准备就绪。如果你猜错了，你仍然需要等待生产线的其余部分 运行 通过当前设置，并将它们存放到 "we don't have a customer for these" 角落（或 CPU 说明 "discard the instruction").
大多数现代 CPU 也允许 "speculative execution"。这意味着处理器将在实际确定条件之前开始执行指令。所以在老板说之前，处理器会从 A 车转向 B 车。如果到那时，老板说 "no, you should keep working on A cars"，你有一堆车要丢弃，你已经开始工作了。您不一定要制造所有的汽车，但您必须让它们通过生产线，每 20 分钟一个步骤。
总结
评估分支条件总是需要一些工作，即使预测得很好，但由于现代CPU的内部并行性额外工作 不必添加到特定指令序列的 成本 。
详情
我认为部分混淆在于许多人执行 CPU 指令时的心理表现模型。是的，每条指令都需要一些 work，所以这应该意味着每条指令都有一些 cost，但以执行时间衡量时，无论多小，对吧？
好吧，如果执行的总成本只是简单地添加到每条指令的工作中，那将是正确的 - 您只需将所有 工作 加在一起并得到最终的 费用。由于现代 CPUs 中大量的并行性，它不是那样工作的。
可以把它想象成举办生日派对。你可能要买面粉，花 10 分钟，然后烤一个蛋糕，花 60 分钟，然后去拿 30 分钟路程外的特别礼物。这些时间都是 activity 所需的 "work"。但是，有人可以在捡面粉和烤蛋糕的时候去拿礼物。但是，没有面粉就不能烤蛋糕。所以你有两个依赖链：70 分钟买面粉 -> 烤蛋糕链，和 30 分钟取礼物链。在无限并行的情况下，只有 70 分钟的蛋糕相关链有助于一切准备就绪的时间。领取礼物需要 30 分钟的工作，但最终 花费 时间（不延迟所有任务的完成），由于其他工作需要更长的时间（又名关键路径）并且并行发生。
可以并行完成更多额外任务，直到您 运行 没有人可以分配给他们。 （此时，执行吞吐量限制开始增加延迟，这称为资源冲突。如果资源冲突延迟了关键路径，而不是较短的依赖链之一。CPUs 不知道哪个依赖链是/将是关键路径，因此他们的调度不会像聪明人在这个规划类比中那样优先考虑它。）
要了解这些东西如何直接应用于 CPU 的不那么抽象但更实用的外观，请参阅 A Whirlwind Introduction to Dataflow Graphs。
一旦我们有了这个新的心智模型，其中指令序列的成本通常由通过序列的一些关键路径决定，我们就可以开始明白为什么 well-predicted 分支的成本通常非常低或为零:
- 分支指令没有输出寄存器和没有内存输出1。这意味着它们不能参与典型的依赖链，除非作为最终节点 - 它们总是 end 依赖链。所以分支不参与长依赖链的形成，因此在某种意义上 "out of line" 并且可以自由地与其他结果并行计算。
- 分支指令的实际执行通常需要很少的工作：在现代 x86 上，它们可以在两个端口上执行，延迟为 1 个周期。此外，分支指令可以 融合 与先前的 ALU 操作，并且生成的操作仍然在 1 个周期内执行 - 因此在某种意义上，分支有时可以折叠到先前的操作中 因为在执行时没有额外的工作2。这明显有助于 "near zero cost" 论点，但也有助于 "truly zero cost" 论点，因为需要更少的资源意味着它不太可能触发会干扰零成本执行计划的吞吐量瓶颈。
这些因素结合起来使得大多数预测的分支指令成本为零或几乎为零。
你不必相信我的话，让我们看一个真实的例子：
int mul1(int count, int x) {
do {
x *= 111;
} while (--count);
return x;
}
给定一个 count 和一个初始值 x，它将 x 乘以 111 count 次，得到 returns 结果。循环 assembles 到 3 条指令 一条用于乘法，一条用于 --count 和一条用于检查 count 值的分支：
.L2:
imul eax, eax, 111
sub edi, 1
jne .L2
现在是同一个循环，但多了一个分支：
int mul2(int count, int x) {
do {
x *= 111;
if (x == 0) {
abort();
}
} while (--count);
return x;
}
这assembles到5条指令。额外的两个用于 x 的测试和测试显示 x 为零的分支：
.L7:
imul eax, eax, 111
test eax, eax
je .L12 ; ends up calling abort
sub edi, 1
jne .L7
那么增加 60% 的指令（包括分支）的成本是多少？零，至少到4位有效数字3:
Running benchmarks groups using timer libpfc
** Running benchmark group Whosebug tests **
Benchmark Cycles
No branch 3.000
Added test-branch 3.000
外观每次迭代需要 3 个周期，因为它受到涉及 3 个周期乘法的依赖链的限制。额外的指令和分支没有任何成本，因为它们没有添加到这个依赖链并且能够执行 "out of line"，隐藏在关键路径的延迟之后。
1 从概念上讲，分支指令写"rip" 寄存器，但这根本不像其他寄存器那样对待：它的进展是提前预测的，所以依赖性被预测器打破了。
2 当然，首先解码和融合指令还有额外的工作，但这通常不是瓶颈，所以可能是 "free"在成本方面，uop 缓存之类的东西意味着它甚至可能不会经常执行。此外，在 x86 上，虽然融合分支指令与 ALU op 具有相同的延迟，但就其可以在哪些端口上执行而言，它的灵活性较低，因此根据端口压力，融合指令可能会产生一些成本与裸 ALU 运算相比。
3 事实上，如果您转到 "infinite" 有效数字并查看原始循环计数，您会发现此循环的额外迭代成本 exactly 在这两种情况下都是 3 个周期。 no-branch 案例通常最终会缩短 1 个周期（随着迭代次数的增加，相对意义上的差异变为 0），可能是因为初始 non-steady-state 迭代需要一个额外的周期，或者错误预测恢复在最后一次迭代中需要一个额外的周期。