最近，我有一些空闲时间，开始学习一些低级计算机基础知识，试图更详细地练习和更好地理解这些概念。在此过程中，我了解了一个名为LLVM的现代编译器基础架构，该基础架构是一个独立于目标的优化器和代码生成器，已用作Rust，Zig或Haskell等不同编程语言的许多编译器的一部分。在潜入LLVM的积极优化功能的同时，我有一个令人沮丧的实现：即使是最先进的编译器优化也无法使您免于硬件级别的基本限制。如果我们的计划具有不可预测的分支，那么所有聪明的LLVM优化都将成为所谓的“分支预测”的次要。差的分支预测模式很容易否定多个LLVM优化的好处。
根据杰夫·迪恩（Jeff Dean）的说法，每个程序员都应该知道一些延迟数字，其中一个是分支机构错误预测，在2012年的价格约为5N ，并且延迟与撰写此帖子的时间大致相同。那么，分支机构的预测是什么，当它被错误预测时会发生什么？为什么它的昂贵？在进行解释之前，我认为值得一提的是，CPU理想的期望是什么样的指令执行模式。由于内存布局是线性的，并且当程序被编译并存储在内存中时，其说明将作为连续序列存储：
MARKDOWN
内存地址指令PC值 0x1000 mov eax，5 pc = 0x1000 0x1003添加eax，10 pc = 0x1003 0x1006 mov [0x2000]，eax pc = 0x1006 0x100A RET PC = 0x100A
阅读本文的自然方式是从上到下，就像读书一样。在CPU中，有一个名为Program Counter （PC）的特殊寄存器，其作业是记录当前指令的地址。 CPU的程序计数器自然会将下一个顺序指令地址递增：
[MATH] PC = PC +指令 size [/MATH]
指令大小是当前指令的大小，例如，在执行MOV EAX, 5 （3个字节）之后，CPU自动设置：
[MATH] PC = 0x1000 + 3 = 0x1003 [/MATH]
因此，CPU可以找出下一个指令的地址，然后执行下一个指令。但是这里的一个重要细节是，要完成指令，每个说明都会始终具有多个内部阶段，而这里的一个问题是，CPU是否只等待一个指令上的所有阶段才能完成，然后执行下一个指令？要回答这个问题，让我们首先看一下典型处理器需要在每个指令上执行的不同内部阶段：
指令获取（如果）：从内存中获取指令
指令解码（id）：弄清楚它的含义
执行（EX）：执行操作
内存访问（MEM）：如果需要的话，请访问存储器
写回（WB）：将结果存储在内存中
现代CPU采用了一种称为指令管道的技术，这意味着，即使一项指令尚未完成所有阶段，下一个指令也可以立即平行启动，因此想法是利用CPU拥有的所有硬件功率。这意味着每个说明阶段都将通过不同的硬件零件来处理，例如，可能会有获取硬件单元，解码硬件单元，执行硬件单元。当执行硬件单元在当前指令的执行阶段工作时，获取硬件单元可能会在下一个指令的获取阶段并行工作。
降价
┌┌前往┌┌┌氨 - ─-─-─-─-─-─-─-─-─-─达教前培训 │多个获取单元│多个解码单元│ │││││┌届┐┐┐┐┐届─┐┐届┐│届│┌届┐│┐┐届┐┐┐┐届┌┌┐届┌┐┐届┐┐┐届┌┐┐┐届┐┐┐┐┐┐┐┐┐┐ IF1 if2│││││││││││ID1││ID2││ID3│ │││││└届┘┘┘┘┘届─┘┘届┘│届│└届┘│┘┘届┘┘┘┘届└└┘届└┘┘届┘┘┘届└┘┘┘届┘┘┘┘┘┘┘┘┘┘ ├├前往├├├├氨 - ─-─-─-─-─-─-─-─-─-─-─-─-─-─-─-─-─-─-─-─-─-─-─-─杏仁 - ─杏仁 - ─-─-──杏仁 - ─-─杏仁 - ─-─-─杏仁 - ─- - ─- - ─-─-─-─- - ─-─------------------------------------------------------------------------------------------------------------------------------ │多个执行单元│多个内存单元│ ││┌│││届┐┐┌届┌┌┐届─┐┌届┐┐┐届┌┌┐届┐│┐│┐│届┐│┐│┐│届┐│┐│┐│┐│届┐┐┌届┐┐┐届┐┐┐┐ Alu1 Alu2 Alu2 fpu││Lld1│st1│St1│││ ││└│││届┘┘└届└└┘届─┘└届┘┘┘届└└┘届┘│┘│┘│届┘│┘│┘│届┘│┘│┘│┘│届┘┘└届┘┘┘届┘┘┘┘ └└前往└└└└氨 - ─-─-─-─-─-─-─-─-─-─-─-─-─-─-─-─-─-─-─-─-─-─-─-─杏仁 - ─杏仁 - ─-─-──杏仁 - ─-─杏仁 - ─-─-─杏仁 - ─- - ─- - ─-─-─-─- - ─-─------------------------------------------------------------------------------------------------------------------------------ 带有管道的时间表以进行独立说明（现代CPU）： 时间：1 2 3 4 5 6 7 8 9 10 Inst1：fdemw Inst2：fdemw Inst3：fdemw
instruction N ，它知道instruction N + 1位于PC + instruction_size 。这种可预测性允许管道保持充分和高效。
但是，当顺序代码损坏时，存在一个问题，而CPU需要跳到某个位置，而该位置可能不仅仅是当前一个指令的下一个指令。例如，此时可能会有类似JE target_address指令，CPU面对不确定性：它应该在target_address上获取指令，还是继续顺序执行下一个指令？管道现在需要知道，但是至少几个周期无法解决该条件。查看此代码段：
Markdown
0x1000：CMP EAX，10;将EAX与10比较（进行3-5个周期） 0x1003：JE 0x2000;如果相等的话，请跳跃（2个字节指令） 0x1005：MOV EBX，1;路径A：设置EBX = 1 0x1008：添加ECX，EBX;路径A：添加到ECX ... 0x2000：MOV EBX，99；路径B：设置EBX = 99
在地址0x1003上获取指令JE 0x2000之后，获取硬件单元需要再次获取下一个指令，但是这次，它不确定它将在0x1005或0x2000处执行指令，因为以前的比较指令的结果尚不可用。在这里，我们可以通过类似的内容来形象化：
周期1：
MARKDOWN
提取：阅读CMP EAX，10来自地址0x1000 解码：[空] 执行：[空] 内存：[空] 写：[空] PC = 0x1003（已经移至下一个指令）
周期2：
MARKDOWN
提取：读取JE 0x2000从地址0x1003 解码：解码CMP EAX，10 执行：[空] 内存：[空] 写：[空] PC = 0x1005（再次移动！）
Markdown
Fetth：???必须决定接下来要获取什么？？？ 解码：解码JE 0x2000 执行：执行CMP EAX，10（正在进行的比较...） 内存：[空] 写：[空] PC = ???应该是0x1005或0x2000 ???
CPU没有停止管道（会浪费循环），而是对分支将采取哪个方向并立即开始从预测路径中获取指令进行预测。这创造了2个可能的结果：
正确的预测：管道全速持续，没有罚款
不正确的预测：CPU必须冲洗所有投机性执行的说明并从正确的道路重新启动，从而受到重大罚款。
很难想象为什么几个浪费的周期将是一个问题，但是随着分支机构的数量增加，我们的程序的效果就越明显。有不同的分支指令破坏了自然的指令流。最明显的是if-else语句。这是一个性能挑战：两种相同的算法处理相同的电子商务数据 - 一个带有随机排列产品的算法，另一个带有分类产品。您认为哪个运行速度更快？
Rust
Fn Process_predictable_data（＆self） - > f64 {
用于in＆self.predictable_products {
如果product.price <100.0 {//可预测：大多数是真实的
如果product.in_stock {
total_revenue += product.price;
如果product.is_premium {
total_revenue += 5.0; //优质奖金
}
}
} else如果product.price <300.0 {//可预测：主要在中间
如果product.in_stock {
total_revenue += product.price * 1.1; //标记
如果product.is_premium {
total_revenue += 15.0;
}
}
} else {//可预测：主要在最后
如果product.in_stock {
total_revenue += product.price * 1.2; //更高的标记
如果product.is_premium {
total_revenue += 25.0;
}
}
}
}
total_revenue
}
fn process_unpredictable_data（＆self） - > f64 {
令Mut total_revenue = 0.0;
//每个条件可能是正确的/false
用于in＆self.random_products {
如果product.price <100.0 {//无法预测：随机/fals/fals
如果product.in_stock {
total_revenue += product.price;
如果product.is_premium {
total_revenue += 5.0;
}
}
} else如果product.price <300.0 {//无法预测：随机true/false
如果product.in_stock {
total_revenue += product.price * 1.1;
如果product.is_premium {
total_revenue += 15.0;
}
}
} else {//无法预测：随机true/false
如果product.in_stock {
total_revenue += product.price * 1.2;
如果product.is_premium {
total_revenue += 25.0;
}
}
}
}
total_revenue
}在运行基准测试之前，让我们考虑一下：
这两个过程都产生相同的100K产品
两者都使用相同的逻辑和计算
两者都可以访问相同数量的内存
唯一的区别是数据排序
这是结果：
降级
测试1：可预测的分支模式 数据：用价格排序的产品（低→高） 分支机构行为：价格检查是可预测的 收入：$ 21068967.18 结果：总计89.572224 测试2：不可预测的分支模式 数据：相同的产品，随机洗牌 分支机构行为：价格检查是不可预测的 收入：$ 21068967.18 结果：142.038094625S
刚刚发生了什么？两项测试都处理了相同的数据，并产生了完全相同的收入$ 21068967.18 ，但比另一个的收入约为60％ 。唯一的区别是产品在内存中的顺序。这种戏剧性的性能差异揭示了分支预测的隐藏成本。在代码中，每个if-else块都会创建一个有条件的跳跃，其中CPU必须在其中预测要采取和执行的路径。 CPU对要遵循哪个分支进行了有根据的猜测。
使用分类的数据（测试1）：由于价格比较的可预测性，CPU预测非常准确 - 早期便宜的产品，稍后昂贵的产品。
使用随机数据（测试2）：由于产品被随机排序，价格不同，因此这种不可预测的模式使CPU更难正确猜测。相同的价格比较变成了不可预测的硬币翻转。 CPU经常猜测错误，迫使其丢弃投机执行的说明并从正确的路径重新启动。
随着产品和分支机构的增加，该问题成倍增加，将一些浪费的周期变成了重大的性能罚款，使生产系统中的真实金钱成本。
现在，我们更好地了解哪种数据模式对CPU猜测分支方向更有利。但是，如果根本没有分支预测，CPU只需等待每个分支条件的结果，该怎么办？首先，让我们找出产品收入计算功能中的分支数量，为简单起见，我们只计算有条件的跳跃（即，If-elseif-else语句），然后忽略循环开销（在分支机构计数中很重要，但我们只是跳过它）：
分支1：我应该跳到<100个价格块（是/否决定）
分支2：我应该跳到100-300的价格块（是/否决定）
最终的语句不会跳到任何地方。它只是依次继续执行
分支3：库存检查
if product.in_stock（始终执行，完全是3股票支票之一，具体取决于价格范围）分支4：premium检查
if product.is_premium（仅在product.in_stock为true时执行）
100K产品和4个产品分支机构，因此我们总共有40万个分支。为了使计算更加实用，我们还指定一些CPU规格：
管道深度：14个阶段[英特尔优化手册2021]
频率：[MATH] F_ {CPU} = 3GHz = 3 * 10^9 Cycles / second [ /Math]
分支错误预测的惩罚：15-22个周期（英特尔第12代：〜16-20，AMD Zen 4：〜18-22）
分支机构时间：2-3个用于登记比较的周期[英特尔文档]
我们首先需要计算基本执行时间（分支说明除外的任何指令），其中可能包括：
产品数据的内存负载/存储
算术操作（价格计算，收入增加）
循环迭代开销
功能调用开销
估计100K产品：
每产品的降价
指令：〜8-12（负载，算术，商店） 总说明：100,000×10 = 1,000,000说明 CPI（每指令循环）：〜1.2（现代超级CPU） 基本周期：1,000,000×1.2 = 1,200,000周期
[MATH] 大{t_ {base} = frac {1.200.000} {3 * 10^9} = 0.4 0.4 text {ms}}} [/MATH]
假设每个分支分辨率将进行3个周期；然后，我们可以得出没有分支预测的管道摊位公式：
[MATH] 大{ = frac {1.200.000} {3 * 10^9} = 400 * 10^{ - 6} = 0.40 ms} [/MATH]
为了计算与启用分支预测相比，浪费了多少时间，截至撰写本文时，根据工作量特征，现代CPU的分支预测准确率约为90-97％的精度：
高度规则的模式（循环，分类数据）：95 - 97％
混合图案（典型应用）：90 - 95％
和其他模式…
因此，分支顶部公式将是：
[MATH] 大{
在哪里：
[MATH] N_ text {branches} = = 400.000 [/MATH]
[数学] r_ text {miss} = 0.05 （ text {5％的猜测错误}）[/MATH]
[MATH] P_ TEXT {MISS} = 17 （ Text {每个失败的预测成本17个周期}）[/MATH]
[数学] r_ text {hit} = 0.95 （ text {95％的猜测}}）[/MATH]
[MATH] p_ text {hit} = 0 （ text {成功的预测没有任何惩罚}）[/MATH]
我们只需要将这些数字插入公式，然后查看其理论上花费了多少时间来处理100K产品，分支预测成功率为95％ ：
[MATH] 大{ 0.85} {3 * 10^9}}}} of cout 0.113ms [/MATH]
现在，我们可以计算没有分支预测的总执行时间，以及有分支预测时：
[MATH] ligal {t_ text {total_no_pred} = t_ t_ text {base} + t_ t_ text {no_pred} = 0.4 + + + 0.4 0.4 = = 0.8 0.8 0.8 0.8 0.8 t_ text {base} + t_ text {branch_pred} = 0.4 + 0.113 = 0.513 text {ms}}}} [/MATH]
最后，我们可以计算放缓因子：
[MATH] 大{ text {slowdown因数} = frac {0.8} {0.513} {0.513 _
| 基本执行 | 0.40ms | 0.40ms | 0ms |
| 分支在头顶 | 0.113ms | 0.40ms | +0.287ms |
| 总时间 | 0.513ms | 0.80ms | +慢56％ |
这里的关键见解是，通过启用分支预测，它可以自动节省56％的执行时间，在这里，我们只有一个小例子，但是在现实世界中，我们使用的每个智能设备上可能会发生数十亿个预测，而我们使用的每个智能设备都是完全透明的。
结论
每个if语句都是CPU需要回答的问题，我们可以做的是使问题易于预测：
过程中的处理数据
批量类似的操作一起
避免在关键性能路径中随机有条件逻辑
正如我们在电子商务示例中看到的那样，有时最强大的优化并没有改变我们的算法 - 它只是组织数据以与硬件合作而不是与之抗衡。
完整的代码示例可在此处提供。