Java 中的分支预测
发布于 1 个月前 作者 yan 13 次浏览

(给ImportNew加星标,提高Java技能)

编译:ImportNew/覃佑桦

www.baeldung.com/java-branch-prediction

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语句。 在解析前,虽然计算机能看到这些指令,但不能加载 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); 

请注意,这里只对计数循环计时,因为这才我们感兴趣的工作。那么需要多少时间呢?

如果生成的列表较小,那么代码执行很快,无法统计:10万条数据的列表执行结果为0毫秒。但是当列表足够大时,可以看到计时结果中 shuffle 条件对结果有显著影响。包含1000万个数字的列表:

  • Sorted – 44ms
  • Shuffled – 221ms

也就是说,即使计算的数据相同,随机(shuffled)列表用时是排序后的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); 

计算1000万个数字时,无论 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上找到。

github.com/eugenp/tutorials/tree/master/core-java-modules/core-java-perf

推荐阅读  点击标题可跳转 Mybatis 面试问题集锦

Java8 的 Stream 对集合操作飞起来

2020 年最棒的 9 个 Java 框架,哪个最香?

看完本文有收获?请转发分享给更多人

关注「ImportNew」,提升Java技能

好文章,我在看❤️

回到顶部