Java 中的分支预测-Java快速进阶教程

大家好，欢迎来到IT知识分享网。

1. 简介

分支预测是计算机科学中一个有趣的概念，可以对我们应用程序的性能产生深远的影响。然而，它通常没有得到很好的理解，大多数开发人员很少关注它。

在本文中，我们将确切地探讨它是什么，它如何影响我们的软件，以及我们可以做些什么。

2. 什么是指令流水线？

当我们编写任何计算机程序时，我们正在编写一组我们希望计算机按顺序执行的命令。

早期的计算机会一次运行一个。这意味着每个命令都会加载到内存中，完整地执行，只有当它完成时，下一个命令才会被加载。

指令流水线是对此的改进。它们允许处理器将工作分成几部分，然后并行执行不同的部分。这将允许处理器在加载下一个命令的同时执行一个命令，准备就绪。

处理器内部较长的流水线不仅可以简化每个部分，还可以并行执行其中的更多部分。这可以提高系统的整体性能。

例如，我们可以有一个简单的程序：

int a = 0; a += 1; a += 2; a += 3;

这可能由由获取、解码、执行、存储段组成的管道处理为：

我们可以在这里看到四个命令的整体执行是如何并行运行的，从而使整个序列更快。

3. 有哪些危害？

处理器需要执行的某些命令会导致流水线出现问题。这些命令是管道的一部分的执行依赖于早期部分，但这些早期部分可能尚未执行的任何命令。

树枝是一种特定形式的危害。它们会导致执行朝两个方向之一进行，并且在解析分支之前不可能知道哪个方向。这意味着任何通过分支加载命令的尝试都是不安全的，因为我们无法知道从哪里加载它们。

让我们更改我们的简单程序以引入一个分支：

int a = 0; a += 1; if (a < 10) { a += 2; } a += 3;

其结果与以前相同，但我们在其中中间引入了一个if语句。计算机将看到此内容，并且在解决此问题之前无法加载超过此值的命令。因此，流将如下所示：

我们可以立即看到这对程序执行的影响，以及执行相同结果需要多少时钟步长。

4. 什么是分支预测？

分支预测是对上述内容的增强，我们的计算机将尝试预测分支将要走哪条路，然后采取相应的行动。

在上面的例子中，处理器可能会预测if（<10）很可能为真，因此它将表现得好像指令a += 2是下一个要执行的指令。这将导致流如下所示：

我们可以立即看到，这提高了我们程序的性能——它现在需要 9 个即时报价而不是 11 个，所以它的速度提高了 19%。

不过，这并非没有风险。如果分支预测出错，那么它将开始排队不应该执行的指令。如果发生这种情况，那么计算机将需要将它们扔掉并重新开始。

让我们把我们的条件转过来，让它现在为假：

int a = 0; a += 1; if (a > 10) { a += 2; } a += 3;

这可能会执行类似以下内容：

现在这比以前的流程慢，即使我们做得更少！处理器错误地预测分支的计算结果为true，开始排队a += 2指令，然后不得不丢弃它并在分支计算结果为 false 时重新开始。

5. 对代码的真正影响

现在我们知道什么是分支预测以及它的好处是什么，它如何影响我们？毕竟，我们谈论的是高速计算机上丢失几个处理器周期，所以肯定不会很明显。

有时这是真的。但有时它会对我们应用程序的性能产生令人惊讶的差异。这在很大程度上取决于我们在做什么。具体来说，这取决于我们在短时间内做了多少。

5.1. 计算列表条目

让我们尝试计算列表中的条目。我们将生成一个数字列表，然后计算其中有多少小于某个截止值。这与上面的例子非常相似，但我们是在循环中完成的，而不仅仅是作为单个指令：

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);

请注意，我们只对执行计数的循环进行计时，因为这是我们感兴趣的。那么，这需要多长时间？

如果我们生成足够小的列表，那么代码运行得如此之快，以至于无法计时——大小为 100，000 的列表仍然显示 0ms 的时间。但是，当列表变得足够大以至于我们可以计时时，我们可以看到基于我们是否洗牌列表的显着差异。对于 10，000，000 个号码的列表：

• 排序 – 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);

此代码大约在同一时间执行 – 排序数字~35ms，随机数字~200ms – 当计数10，000，000个数字时，无论cutoffPercent的值如何。

这是因为分支预测器平等地处理两个分支，并正确猜测我们将采用哪种方式。

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. 结论

我们已经了解了什么是分支预测以及它如何对我们的项目产生影响。这可以为我们提供一些额外的工具，以确保我们的程序尽可能高效。

但是，与往常一样，我们需要记住在进行重大更改之前分析我们的代码。有时，进行更改以帮助分支预测在其他方面成本更高。