专注IT技术、资源分享!
神奇,同样执行1,000,000次循环的时间竟然会不一样?
神奇,同样执行1,000,000次循环的时间竟然会不一样?

神奇,同样执行1,000,000次循环的时间竟然会不一样?

场景

事情是这样的,我先来还原一下场景,有如下图中的一段代码,这段代码的逻辑很简单。

  1. 先生成一个0-top范围的有序集合,比如top=100,那么就是生成[0,1,2,3,…99,100];
  2. 如果shuffle=true,则将这个集合顺序打乱,相当于洗牌;
  3. 然后遍历这个集合,统计出集合中数值小于top/2的数量,这个结果不管是否洗牌都是top的一半;
  4. 记录循环开始和结束的时间,看看循环总共花费多少时间。

按理说,不管这个集合有多大,都会执行top次的循环,每个循环里都要执行if判断,所以花费的时间不管是否洗牌应该都是一样的对吧。

但是,神奇的事情发生了!

public static void main(String[] args) {
  perdication(1000000,true);
  perdication(1000000,false);
}

我们执行这段代码,分别用有序的集合和打乱的集合执行,看看花费的时间。

从执行结果发现,顺序打乱的集合执行的时间比有序集合执行的时间竟然要长!!并且多次执行后,情况一样。

这是为什么呢?

原来计算机在背后帮我们做了一些事情,对我们的代码进行了一些性能上的优化。

计算机做的事情叫做分支预测。在开始说分支预测前,先要普及一个概念叫做指令管道

指令管道

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

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

指令管道对这种情况的一种改进技术,它允许处理器将工作分成多个部分,然后并行执行。允许处理在执行一个命令时就将一下个命令加载进来准备就绪。

比如,我们有一个简单的程序:

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

每一行代码都会由处理器进行加载(Fetch)、解码(Decode)、执行(Execute)、存储(Store)等步骤执行。

从上图可以看出这四个命令的执行是如何并行运行的,从花费的时间上变得更快。

会产生什么问题呢?

通过指令管道进行优化后,虽然能在多少情况下让程序运行变快,但是会导致出现一些问题。

有一些命令的执行,依赖于另一些命令执行的结果,而在该命令执行时可能依赖命令还没有执行完毕。

代码中的分支就可能导致这种问题发生。因为在分支部分执行方向只会选择其中的一个,并且在执行分支之前是不能知道走哪个方向的。

这会导致任何对分支执行方向的预测变得不安全,因为我们无法确定分支的具体走向。

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

这段代码从执行结果上和上面的代码一样,但是因为增加了一个if语句,会导致计算机无法预知if分支的走向,所以在执行if之前,不能加载后续的代码命令。

可以发现,因为引入了一个if分支,导致执行时间立马变长。

那这和我们最开始的分支预测又有什么关系呢?

什么是分支预测?

其实,分支预测是对指令管道优化的一个增强。计算机会尝试预测分支的走向,然后按照预测的结果进行一些指定的加载。

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

同样这段代码,计算机可能会预测a<10为true,这样一来,指令执行情况将变成下面这样:

可以看到,时间立马从原来的11变成9,提高了程序性能。

但是,这样预测是存在风险的,因为计算机也可能预测错误,如果执行结果和预测结果不一致,那么已经加载的命令不应该被执行,将会被丢掉之后重新加载新的命令。比如,我们将程序中的条件修改为a>10:

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

那么它的执行情况可能就是这样:

image-20220204123700871

可以发现这比上面的执行时间要慢。

分支预测有什么影响?

现在我们知道了分支预测,那它对代码又有什么影响呢?

通常情况下,我们的业务逻辑并不复杂,或者说因为分支预测错误,导致多执行几个处理器的命令,对性能并不会有太大的影响。

但是在一些特定的场景下,这种机制可能就会带来巨大的性能提升。

再来回忆一下开始的代码。

就是因为在for循环中,对if条件的执行结果进行预测,并行的对指令进行加载,提高了执行效率。

而洗牌之后的集合,因为数字顺序被打乱,导致分支预测的结果多数情况下和实际不一致,导致需要丢掉命令后重新加载正确的命令执行。

小结

通过以上内容我们了解了分支预测是什么以及它对我们的程序产生的影响。可以让我们进行程序性能优化时,多一个选择。

如果你觉得本文有点意思,不妨点个赞吧。

我是小黑,一名在互联网“苟且”的程序员

流水不争先,贵在滔滔不绝

发表回复

您的电子邮箱地址不会被公开。