快速和慢速的 if 语句:现代处理器的分支预测

语句的性能取决于它的判断条件是否拥有可预测模式,你知道吗?如果条件始终为真或者始终为假,处理器内的分支预测逻辑会选择该模式。此外,如果该模式不可预测,if语句的开销将更大。本文将解释为什么现代处理器要这样做。

接下来,我们在不同条件下测试该循环的性能:

以下是不同真-假模式下该循环的耗时:

条件 Pattern/模式 时间 (ms)
(i & 0x80000000) == 0 T repeated 322
(i & 0xffffffff) == 0 F repeated 276
(i & 1) == 0 TF alternating 760
(i & 3) == 0 TFFFTFFF… 513
(i & 2) == 0 TTFFTTFF… 1675
(i & 4) == 0 TTTTFFFFTTTTFFFF… 1275
(i & 8) == 0 8T 8F 8T 8F … 752
(i & 16) == 0 16T 16F 16T 16F … 490

语句在“坏”真-假模式下比在“好”模式下慢了近六倍!当然,模式的好坏取决于编译器产生的具体指令集和具体处理器。

让我们看看处理器计数器

了解处理器如何利用时间的一种方式是查看硬件计数器。为帮助性能调试,现代处理器在执行代码时跟踪各种计数器:执行指令的数量,各种类型内存访问的数量,遇到分支的数量等等。要读取计数器,你需要像Visual Studio 2010预览版或旗舰版中的profilerAMD Code Analyst或者Intel VTune类似的工具。

为了验证我们观察到的性能降低是由于if语句造成的,我们可以查看分支预测错误计数器:

TF pattern

最糟糕的模式(TTFFTTFF…)将导致744次分支预测错误,而好的模式下大约只有10次。无疑坏情况花费最长的1.67秒,而好模式下仅花费大约300毫秒!

接下来分析分支预测做了什么,以及为什么它会对处理器性能有这么大影响。

分支预测扮演什么角色?

为解释分支预测是什么以及为何会影响性能参数,首先我们需要了解一下现代处理器的工作原理。为了执行每条指令,CPU会经历以下这些(可能更多)步骤:

1. 取指:读取下一条指令。

2. 译码:完成指令的翻译。

3. 执行:执行指令。

4. 回写:保存结果到内存。

一个重要的优化是流水线阶段可同时处理不同指令。那么,在读取一条指令时,第二条指令正在译码,第三条指令正在执行,而第四条指令正在回写。现代处理器有10-31级流水线(例如,Pentium 4 Prescott有31级),为优化性能,保持所有阶段尽可能一直工作非常重要。

pipeline
图像来源于http://commons.wikimedia.org/wiki/File:Pipeline,_4_stage.svg

分支(即条件跳转)给处理器流水线提出一个难题。在获取一条指令后,处理器需要获取下一条指令。但是下一条指令有两种可能!处理器不确定取哪一条,直到分支条件指令执行到流水线结束。

与暂停流水线直至分支条件指令完全执行不同,现代处理器尝试预测是否需要进行跳转。然后处理器会读取它认为正确的下一条指令。如果预测出错,处理器会丢弃在流水线上执行了部分的指令。在维基分支预测器实现页面上,可以看到处理器获取并解释分支统计数据的一些经典技术。

现代分支预测器适合分析简单模式:全真,全假,真-假交替等。但是如果模式超出分支预测器的预测,性能影响将会非常严重。幸好大部分分支很容易预测,比如下面两个高亮的例子:

第一个高亮的条件检查输入的合法性,那么该分支很少会执行。第二条高亮条件是循环终止条件。这也几乎总是朝着一个方向走,除非处理的数组非常短。所以,在这些情况下,与大多数情况类似,处理器分支预测逻辑可以有效防止处理器流水线暂停。

更新和说明

本文被reddit收录,并且在reddit评论中获得不少关注。我会对下面的问题、评论和批评进行回复。

首先,关于分支预测优化通常是个坏主意的评论:我同意。我没有在文中任何地方争辩说你应该尝试为分支预测优化你的代码。对于绝大部分高级语言代码,我甚至不敢想象你们是如何做到的。

第二点,有人担心除常量值,是不是不同情况下执行的指令都不一样。它们是一样的——我查看了JIT-ted汇编。如果你想要了解JIT-ted汇编代码或者C#源代码,请给我发封邮件,我会把他们发送给你。(我在这里不贴出代码,因为我不想让更新过于庞大。)

第三点,另一个问题是关于TTFF*模式效率极低。TTFF*模式周期很短,这应该是一个简单的分支跳转预测算法的应用场景。

然而,问题在于现代处理器不单独跟踪每一条分支指令历史。相反,它们要么跟踪所有分支的全局历史,要么它们有一些历史插槽,每一个都被多分支指令共享。或者,它们可以使用这些技巧与其他技术组合。

所以,if语句中的TTFF模式在到达分支预测器时可能并不是TTFF模式。它可能会和其他分支(在for循环体中有两个分支指令)交错在一起,可能和其他模式非常接近。但是,我并不是处理器运作方面的专家,如果读本文的人有不同处理器(尤其是我测试用的Intel Core2)如何运转的权威参考,请在评论区告诉我。

1 2 收藏 3 评论

关于作者:汤晓

(新浪微博:<a href="http://weibo.com/u/2151517721">@ashiontang</a>) 个人主页 · 我的文章 · 10

相关文章

可能感兴趣的话题



直接登录
最新评论
  • jpycrgo   2015/10/29

    不明觉厉,我是根本看不懂。

    • luciferlu   2015/10/29

      举个例子,你走在路上,这时候前面出现了两条路,按照过去经验,你知道左边那条更快,也更可能到目的地,于是你想都没想就先走过去了,走了一段路之后,你爸爸打电话过来告诉你说左边那条路前面在修路,不通了,于是你又回来到另外一条路上。

      这里你自己算算成本看,假如你猜对了,是不是比你等着别人告诉你该走那一条更快。
      然而你老猜错,是不是要走很多冤枉路,而这冤枉路的成本还很高,涉及处理器状态回滚,堆栈重新恢复等等成本。

      那么有这么多坑,为什么还要有这个优化呢?
      因为,只要写代码的人有这个意识,那么修改下算法,就能充分利用分支预测功能,帮忙提升效率。

      一般分支预测的效率提升都在循坏如for, while这些语句中体现出来。

  • luciferlu   2015/10/29

    对于大家说到的高级语言能不能充分应用该特性,放心都没问题,编译器会很聪明的。特别是那类JIT,比你想象得更加聪明。因为,写他们的人都是食物链顶端的人物,他们经历过从汇编到高级语言的全过程,了解处理器优化的所有历史。

跳到底部
返回顶部