现代处理器是超标量的，也就是说，它们能够同时执行多个指令。 例如，某些处理器每个周期可以处理4到6条指令。 而且，许多这样的处理器能够无序地启动指令：它们可以在很晚的时候开始使用位于代码中的命令。
同时，代码通常包含分支（
if–then ）。 这样的分支通常被实现为“转换”，其中处理器要么继续执行代码下方的指令，要么继续当前路径。
由于命令的超标量执行乱序，因此分支变得困难。 为此，处理器具有复杂的分支预测块。 也就是说，处理器正在尝试预测未来。 当他看到一个分支，从而看到一个过渡时，他尝试猜测程序将以哪种方式运行。
通常，这很好。 例如，大多数循环被实现为分支。 在循环的每次迭代结束时，处理器必须预测是否将执行下一次迭代。 对于处理器而言，预测周期将持续（永远）通常更安全。 在这种情况下，处理器错误地预测每个周期只有一个分支。
还有其他常见示例。 如果访问数组的内容，那么许多编程语言都会添加“绑定检查”，即在访问数组的值之前对索引正确性的隐藏检查。 如果索引不正确，则会生成错误，否则代码将继续以通常的方式执行。 边界检查是可以预见的，因为在正常情况下所有访问操作都应该正确。 因此，大多数处理器应几乎完美地预测结果。
如果分支难以预测会怎样？
在处理器内部，必须取消所有已执行但在错误预测的分支上的指令，并且必须重新开始计算。 可以预期，对于每个分支预测误差，我们要付出10个以上的周期。 因此，程序的执行时间可能会大大增加。
让我们看一个简单的代码，其中我们将随机整数写入输出数组：
while (howmany != 0) { out[index] = random(); index += 1; howmany--; }
我们可以平均生成3个周期的合适随机数。 即，随机数发生器的总延迟可以等于10个周期。 但是我们的处理器是超标量的，也就是说，我们可以同时执行几个随机数计算。 因此，我们将能够大约每3个周期生成一个新的随机数。
让我们稍微更改一下函数，以便仅将奇数写入数组：
while (howmany != 0) { val = random(); if( val is an odd integer ) { out[index] = val; index += 1; } howmany--; }
您可能天真地认为此新功能可能会更快。 实际上，因为我们平均只需要记录两个整数之一。 代码中有一个分支，但是要检查整数的奇偶校验，只需检查一位。
我在Skylake处理器上用C ++对这两个函数进行了基准测试：
第二个功能的工作时间大约是原来的五倍！
可以在这里固定任何东西吗？ 是的，我们可以消除分支。 奇数整数的特征在于，它是按位逻辑AND，其值1等于1。 诀窍是仅当随机值是奇数时才将数组索引增加1。
while (howmany != 0) { val = random(); out[index] = val; index += (val bitand 1); howmany--; }
在此新版本中，即使不需要，我们总是将随机值写入输出数组。 乍看之下，这是浪费资源。 但是，它使我们免受了错误预测的分支的影响。 实际上，性能几乎与原始代码相同，并且比带有分支的版本要好得多：
编译器可以自行解决此问题吗？ 通常，答案是否定的。 有时，即使源代码中包含
if-then ，编译器也有一些选项可以完全消除分支。 例如，有时可以用“条件移动”或其他算术技巧代替分支。 但是，这种技巧在编译器中使用是不安全的。
一个重要的结论：错误地预测分支不是一个无关紧要的问题，它具有很大的影响。
我的源代码在Github上 。
创建基准是一项艰巨的任务：处理器学会预测分支
[注意 transl。：这部分是与作者
分开的文章 ，但我将其与前
一篇文章结合了起来，因为它们具有共同的主题。]
在上一部分中，我展示了程序的大部分执行时间可能是由错误的分支预测引起的。 我的基准测试是将6400万个随机整数值写入数组。 当我尝试仅记录奇数随机数时，由于错误的预测而导致的性能大大下降。
为什么我使用6400万个整数而不是2000？ 如果您仅运行一项测试，则无所谓。 但是，如果我们尝试多次，会发生什么？ 错误预测的分支数量将迅速降至零。 英特尔Skylake处理器的性能不言而喻：
从下面的图表可以看出，“训练”将继续进行。 逐渐地，错误预测的分支比例下降到大约2％。
也就是说，如果我们继续测量同一任务所花费的时间，则它会越来越少，因为处理器学会了更好地预测结果。 “培训”的质量取决于特定的处理器模型，但是希望新的处理器学习得更好。
最新的AMD服务器处理器学会了在不到10次尝试的情况下几乎完美地预测了分支（在0.1％以内）。
当问题中的值的数量从2000增加到10,000时，对AMD Rome的理想预测就消失了：最佳预测从0.1％的错误率变为33％。
您可能应该避免在分支小任务时使用基准测试代码。
我的github代码 。
致谢 ：Vel Erwan提供的AMD罗马价值观。
附加阅读 ：
一种（部分）TAgged GEometric历史长度分支预测的案例（Seznec等）