1. 概述
分支预测是计算机科学中一个有趣的概念，可以对我们的应用程序的性能产生深远的影响。然而，它通常没有得到很好的理解，大多数开发人员也很少关注它。
在本文中，我们将探讨它到底是什么，它如何影响我们的软件，以及我们可以做些什么。
2. 什么是指令流水线？
当我们编写任何计算机程序时，我们都是在编写一组我们希望计算机按顺序执行的命令。
早期的计算机会一次运行这些，这意味着每个命令都被加载到内存中，完整地执行，只有当它完成时才会加载下一个命令。
指令流水线是对此的改进，它们允许处理器将工作分成几部分，然后并行执行不同的部分。因此，这将允许处理器在加载下一个准备就绪的命令时执行一个命令。
处理器内部更长的流水线不仅可以简化每个部分，还可以并行执行其中的更多部分，这可以提高系统的整体性能。
例如，我们可以有一个简单的程序：
int a = 0;
a += 1;
a += 2;
a += 3;
这可能由包含获取、解码、执行、存储段的管道处理为：
我们可以在这里看到4个命令的整体执行是如何并行运行的，从而使整个序列更快。
3. 有什么危害？
处理器需要执行的某些命令会导致流水线问题，这些命令是管道的一部分的执行依赖于早期部分，但这些早期部分可能尚未执行的任何命令。
分支是一种特殊形式的危险，它们导致执行朝两个方向之一进行，并且在解析分支之前不可能知道哪个方向。这意味着任何通过分支加载命令的尝试都是不安全的，因为我们无法知道从哪里加载它们。
让我们改变我们的简单程序来引入一个分支：
int a = 0;
a += 1;
if (a < 10) {
a += 2;
}
a += 3;
其结果与之前相同，但我们在中间引入了一个if语句。计算机将看到它，并且在它被解析之前将无法加载通过它的命令。因此，流将类似于：
我们可以立即看到这对我们程序的执行的影响，以及执行相同结果需要多少个时钟步长。
4. 什么是分支预测？
分支预测是对上述内容的增强，我们的计算机将尝试预测分支将走哪条路，然后采取相应的行动。
在上面的示例中，处理器可能会预测if (a < 10)很可能为true，因此它的行为就好像指令a += 2是下一个要执行的指令一样。这将导致流程看起来像：
我们可以立即看到这提高了我们程序的性能-它现在需要9个时钟而不是11个时钟，所以速度提高了19%。
不过，这并非没有风险。如果分支预测出错，那么它将开始排队不应该执行的指令。如果发生这种情况，那么计算机将需要丢弃它们并重新开始。
让我们改变我们的条件，使它现在为false：
int a = 0;
a += 1;
if (a > 10) {
a += 2;
}
a += 3;
这可能会执行类似：
现在这比以前的流程慢了，尽管我们做得更少了！处理器错误地预测分支的计算结果为true，开始排队a += 2指令，然后不得不丢弃它并在分支评估为false时重新开始。
5. 对代码的实际影响
既然我们知道什么是分支预测以及有什么好处，那么它对我们有什么影响呢？毕竟，我们谈论的是在高速计算机上损失几个处理器周期，所以肯定不会很明显。
有时这是真的，但有时它会对我们应用程序的性能产生惊人的影响，这在很大程度上取决于我们在做什么。具体来说，这取决于我们在短时间内做了多少。
5.1 计数列表条目
让我们尝试对列表中的条目进行计数。我们将生成一个numbers列表，然后计算其中有多少小于某个截止值。这与上面的示例非常相似，但我们是在一个循环中执行它，而不仅仅是作为单个指令：
List<Long> numbers = LongStream.range(0, top)
.boxed()
.collect(Collectors.toList());
if (shuffle) {
Collections.shuffle(numbers);
}
long cutoff = top / 2;
long count = 0;
long start = System.currentTimeMillis();
for (Long number : numbers) {
if (number < cutoff) {
++count;
}
}
long end = System.currentTimeMillis();
LOG.info("Counted {}/{} {} numbers in {}ms", count, top, shuffle ? "shuffled" : "sorted", end - start);
请注意，我们只是对进行计数的循环计时，因为这是我们感兴趣的。那么，这需要多长时间？
如果我们生成足够小的列表，那么代码运行速度太快以至于无法计时—大小为100000的列表仍然显示0毫秒的时间。然而，当列表变得足够大以至于我们可以对其进行计时时，我们可以看到基于是否对列表进行洗牌的显著差异。对于10000000个数字的列表：
- 已排序：44ms
- 洗牌：221ms
也就是说，洗牌列表的计数时间比排序列表长5倍，即使实际计数的数字相同。
然而，对列表进行排序的行为比仅仅执行计数要昂贵得多。我们应该始终分析我们的代码并确定是否有任何性能提升是有益的。
5.2 分支顺序
根据以上内容，if/else语句中分支的顺序应该很重要似乎是合理的。也就是说，与重新排序分支相比，我们可以预期以下表现会更好：
if (mostLikely) {
// Do something
} else if (lessLikely) {
// Do something
} else if (leastLikely) {
// Do something
}
但是，现代计算机可以通过使用分支预测缓存来避免这个问题。事实上，我们也可以测试一下：
List<Long> numbers = LongStream.range(0, top)
.boxed()
.collect(Collectors.toList());
if (shuffle) {
Collections.shuffle(numbers);
}
long cutoff = (long)(top * cutoffPercentage);
long low = 0;
long high = 0;
long start = System.currentTimeMillis();
for (Long number : numbers) {
if (number < cutoff) {
++low;
} else {
++high;
}
}
long end = System.currentTimeMillis();
LOG.info("Counted {}/{} numbers in {}ms", low, high, end - start);
当计算10000000个数字时，无论cutoffPercentage的值如何，这段代码的执行时间大约为-排序后的数字约35毫秒，打乱后的数字约200毫秒。
这是因为分支预测器平等地处理两个分支，并正确地猜测我们将为它们走哪条路。
5.3 组合条件
如果我们可以在一个或两个条件之间进行选择怎么办？可能以具有相同行为的不同方式重写我们的逻辑，但我们应该这样做吗？
例如，如果我们将两个数字与0进行比较，另一种方法是将它们相乘并将结果与0进行比较，这就是用乘法代替条件，但这值得吗？
让我们考虑一个例子：
long[] first = LongStream.range(0, TOP)
.map(n -> Math.random() < FRACTION ? 0 : n)
.toArray();
long[] second = LongStream.range(0, TOP)
.map(n -> Math.random() < FRACTION ? 0 : n)
.toArray();
long count = 0;
long start = System.currentTimeMillis();
for (int i = 0; i < TOP; i++) {
if (first[i] != 0 && second[i] != 0) {
++count;
}
}
long end = System.currentTimeMillis();
LOG.info("Counted {}/{} numbers using separate mode in {}ms", count, TOP, end - start);
如上所述，我们在循环内的条件可以被替换，这样做实际上会影响运行时间：
- 单独条件：40ms
- 多重和单一条件：22ms
因此，使用两个不同条件的选项实际上需要两倍的时间来执行。
6. 总结
我们已经了解了什么是分支预测以及它如何对我们的程序产生影响。这可以为我们提供一些额外的工具，以确保我们的程序尽可能高效。
但是，与往常一样，我们需要记住在进行重大更改之前分析我们的代码。有时可能会发生这样的情况，即以其他方式进行更改以帮助分支预测成本更高。
与往常一样，本教程的完整源代码可在GitHub上获得。
Post Directory
