Java的分支预测

codingman included in Algorithms Java

2020-06-06 2243 words 5 minutes

Contents

1. 简介

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

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

2. 什么是指令管道？

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

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

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

处理器内部更长的流水线不仅可以简化每个部分，还可以并行执行更多部分。这可以提高系统的整体性能。例如，我们可以有一个简单的程序：

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

这可能由包含 Fetch、Decode、Execute、Store 段的管道处理为：

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

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. 计数列表条目

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

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 的列表仍然显示时间为 0 毫秒。但是，当列表变得足够大以至于我们可以对其进行计时时，我们可以看到基于我们是否对列表进行了洗牌的显着差异。对于 10,000,000 个号码的列表：

排序 – 44 毫秒
洗牌 - 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);

当计算 10,000,000 个数字时，无论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

所以使用两个不同条件的选项实际上需要两倍的时间来执行。