每個時代蕉鸳，都不會虧待會學(xué)習(xí)的人。

大家好忍法，我是 yes潮尝。

這次本來是打算寫一篇 RocketMQ 相關(guān)文章的，但是被插隊了饿序，我也是沒想到的勉失。

說來也是巧最近在看 Dubbo 源碼，然后發(fā)現(xiàn)了一處很奇怪的代碼原探，于是就有了這篇文章乱凿，讓我們來看一下這段代碼顽素，它屬于 ChannelEventRunnable，這個 runnable 是 Dubbo IO 線程創(chuàng)建徒蟆，將此任務(wù)扔到業(yè)務(wù)線程池中處理胁出。

看到?jīng)]，把 state == ChannelState.RECEIVED 拎出來獨立一個 if段审，而其他的 state 還是放在 switch 里面判斷全蝶。

我當(dāng)時腦子里就來回掃描，想想這個到底有什么花頭寺枉，奈何知識淺薄一臉懵逼抑淫。

于是就開始了一波探險之旅！

原來是 CPU 分支預(yù)測

遇到問題當(dāng)然是問搜索引擎了姥闪，一般而言我會同時搜索各大引擎始苇，咱這也不說誰比誰好，反正有些時候度娘還是不錯的筐喳，比如這次搜索度娘給的結(jié)果比較靠前催式，google 較靠后谚中。

一般搜索東西我都喜歡先在官網(wǎng)上搜跟压，找不到了再放開搜鼓鲁，所以先這么搜 site:xxx.com key爽哎。

你看這就有了爽柒，完美按税尽甜刻！

我們先來看看官網(wǎng)的這篇博客怎么說的呻袭，然后再詳細(xì)地分析一波顿天。

Dubbo 官網(wǎng)的博客

現(xiàn)代 CPU 都支持分支預(yù)測 (branch prediction) 和指令流水線 (instruction pipeline)堂氯，這兩個結(jié)合可以極大提高 CPU 效率。對于像簡單的 if 跳轉(zhuǎn)牌废，CPU 是可以比較好地做分支預(yù)測的咽白。但是對于 switch 跳轉(zhuǎn)，CPU 則沒有太多的辦法鸟缕。 switch 本質(zhì)上是根?據(jù)索引晶框，從地址數(shù)組里取地址再跳轉(zhuǎn)。

也就是說 if 是跳轉(zhuǎn)指令懂从，如果是簡單的跳轉(zhuǎn)指令的話 CPU 可以利用分支預(yù)測來預(yù)執(zhí)行指令授段，而 switch 是要先根據(jù)值去一個類似數(shù)組結(jié)構(gòu)找到對應(yīng)的地址，然后再進(jìn)行跳轉(zhuǎn)番甩，這樣的話 CPU 預(yù)測就幫不上忙了侵贵。

然后又因為一個 channel 建立了之后，超過99.9%情況它的 state 都是 ChannelState.RECEIVED缘薛，因此就把這個狀態(tài)給挑出來窍育，這樣就能利用 CPU 分支預(yù)測機制來提高代碼的執(zhí)行效率卡睦。

并且還給出了 Benchmark 的代碼，就是通過隨機生成 100W 個 state漱抓，并且 99.99% 是 ChannelState.RECEIVED表锻，然后按照以下兩種方式來比一比（這 benchSwitch 官網(wǎng)的例子名字打錯了，我一開始沒發(fā)現(xiàn)后來校對文章才發(fā)現(xiàn)）乞娄。

雖然博客也給出了它的對比結(jié)果浩嫌，但是我還是本地來跑一下看看結(jié)果如何，其實 JMH 不推薦在 ide 里面跑补胚，但是我懶，直接 idea 里面跑了追迟。

從結(jié)果來看確實通過 if 獨立出來代碼的執(zhí)行效率更高（注意這里測的是吞吐）溶其，博客還提出了這種技巧可以放在性能要求嚴(yán)格的地方，也就是一般情況下沒必要這樣特殊做敦间。

至此我們已經(jīng)知道了這個結(jié)論是對的瓶逃，不過我們還需要深入分析一波，首先得看看 if 和 switch 的執(zhí)行方式到底差別在哪里廓块，然后再看看 CPU 分支預(yù)測和指令流水線的到底是干啥的厢绝，為什么會有這兩個東西？

if vs switch

我們先簡單來個小 demo 看看 if 和 switch 的執(zhí)行效率带猴，其實就是添加一個全部是 if else 控制的代碼昔汉， switch 和 if + switch 的不動，看看它們之間對比效率如何（此時還是 RECEIVED 超過99.9%）拴清。

來看一下執(zhí)行的結(jié)果如何：

好家伙靶病，我跑了好幾次，這全 if 的比 if + switch 強不少啊口予，所以是不是源碼應(yīng)該全改成 if else 的方式娄周，你看這吞吐量又高，還不會像現(xiàn)在一下 if 一下又 switch 有點不倫不類的樣子沪停。

我又把 state 生成的值改成隨機的煤辨，再來跑一下看看結(jié)果如何：

我跑了多次還是 if 的吞吐量都是最高的，怎么整這個全 if 的都是最棒滴木张。

反編譯 if 和 switch

在我的印象里這個 switch 應(yīng)該是優(yōu)于 if 的众辨，不考慮 CPU 分支預(yù)測的話，當(dāng)從字節(jié)碼角度來說是這樣的舷礼，我們來看看各自生成的字節(jié)碼泻轰。

先看一下 switch 的反編譯，就截取了關(guān)鍵部分且轨。

也就是說 switch 生成了一個 tableswitch浮声，上面的 getstatic 拿到值之后可以根據(jù)索引直接查這個 table虚婿，然后跳轉(zhuǎn)到對應(yīng)的行執(zhí)行即可，也就是時間復(fù)雜度是 O(1)泳挥。

比如值是 1 那么直接跳到執(zhí)行 64 行然痊，如果是 4 就直接跳到 100 行。

關(guān)于 switch 還有一些小細(xì)節(jié)屉符，當(dāng) swtich 內(nèi)的值不連續(xù)且差距很大的時候剧浸，生成的是 lookupswitch，按網(wǎng)上的說法是二分法進(jìn)行查詢（我沒去驗證過）矗钟，時間復(fù)雜度是 O(logn)唆香，不是根據(jù)索引直接能找到了，我看生成的 lookup 的樣子應(yīng)該就是二分了吨艇，因為按值大小排序了躬它。

還有當(dāng) switch 里面的值不連續(xù)但是差距比較小的時候，還是會生成 tableswtich 不過填充了一些值东涡，比如這個例子我 switch 里面的值就 1冯吓、3、5疮跑、7组贺、9，它自動填充了2祖娘、4失尖、6、8 都指到 default 所跳的行渐苏。

讓我們再來看看 if 的反編譯結(jié)果：

可以看到 if 是每次都會取出變量和條件進(jìn)行比較雹仿，而 switch 則是取一次變量之后查表直接跳到正確的行，從這方面來看 switch 的效率應(yīng)該是優(yōu)于 if 的整以。當(dāng)然如果 if 在第一次判斷就過了的話也就直接 goto 了胧辽，不會再執(zhí)行下面的哪些判斷了。

所以從生成的字節(jié)碼角度來看 switch 效率應(yīng)該是大于 if 的公黑，但是從測試結(jié)果的角度來看 if 的效率又是高于 switch 的邑商，不論是隨機生成 state，還是 99.99% 都是同一個 state 的情況下凡蚜。

首先 CPU 分支預(yù)測的優(yōu)化是肯定的人断，那關(guān)于隨機情況下 if 還是優(yōu)于 switch 的話這我就有點不太確定為什么了，可能是 JIT 做了什么優(yōu)化操作朝蜘，或者是隨機情況下分支預(yù)測成功帶來的效益大于預(yù)測失敗的情形恶迈？

難道是我枚舉值太少了體現(xiàn)不出 switch 的效果？不過在隨機情況下 switch 也不應(yīng)該弱于 if 啊谱醇，我又加了 7 個枚舉值暇仲，一共 12 個值又測試了一遍步做，結(jié)果如下：

好像距離被拉近了，我看有戲奈附，于是我背了波 26 個字母全度，實不相瞞還是唱著打的字母。

擴(kuò)充了分支的數(shù)量后又進(jìn)行了一波測試斥滤，這次 swtich 爭氣了将鸵，終于比 if 強了。

題外話:
我看網(wǎng)上也有對比 if 和 switch 的佑颇，它們對比出來的結(jié)果是 switch 優(yōu)于 if顶掉，首先 jmh 就沒寫對，定義一個常量來測試 if 和 switch挑胸，并且測試方法的 result 寫了沒有消費痒筒，這代碼也不知道會被 JIT 優(yōu)化成啥樣了，寫了幾十行嗜暴，可能直接優(yōu)化成 return 某個值了。

小結(jié)一下測試結(jié)果

對比了這么多我們來小結(jié)一下议蟆。

首先對于熱點分支將其從 switch 提取出來用 if 獨立判斷闷沥，充分利用 CPU 分支預(yù)測帶來的便利確實優(yōu)于純 swtich，從我們的代碼測試結(jié)果來看咐容，大致吞吐量高了兩倍舆逃。

而在熱點分支的情形下改成純 if 判斷而不是 if + swtich的情形下，吞吐量提高的更多戳粒。是純 switch 的 3.3 倍路狮，是 if + switch 的 1.6 倍。

在隨機分支的情形下蔚约，三者差別不是很大奄妨，但是還是純 if 的情況最優(yōu)秀。

但是從字節(jié)碼角度來看其實 switch 的機制效率應(yīng)該更高的苹祟，不論是 O(1) 還是 O(logn)砸抛，但是從測試結(jié)果的角度來說不是的。

在選擇條件少的情況下 if 是優(yōu)于 switch 的树枫，這個我不太清楚為什么直焙，可能是在值較少的情況下查表的消耗相比帶來的收益更大一些？有知道的小伙伴可以在文末留言砂轻。

在選擇條件很多的情況下 switch 是優(yōu)于 if 的奔誓，再多的選擇值我就沒測了，大伙有興趣可以自己測測搔涝，不過趨勢就是這樣的厨喂。

CPU 分支預(yù)測

接下來咱們再來看看這個分支預(yù)測到底是怎么弄的和措，為什么會有分支預(yù)測這玩意，不過在談到分支預(yù)測之前需要先介紹下指令流水線（Instruction pipelining）杯聚，也就是現(xiàn)代微處理器的 pipeline臼婆。

CPU 本質(zhì)就是取指執(zhí)行，而取指執(zhí)行我們來看下五大步驟幌绍，分別是獲取指令(IF)颁褂、指令解碼(ID)、執(zhí)行指令(EX)傀广、內(nèi)存訪問(MEM)颁独、寫回結(jié)果(WB)，再來看下維基百科上的一個圖伪冰。

當(dāng)然步驟實際可能更多誓酒，反正就是這個意思需要經(jīng)歷這么多步，所以說一次執(zhí)行可以分成很多步驟贮聂，那么這么多步驟就可以并行靠柑，來提升處理的效率。

所以說指令流水線就是試圖用一些指令使處理器的每一部分保持忙碌吓懈，方法是將傳入的指令分成一系列連續(xù)的步驟歼冰，由不同的處理器單元執(zhí)行，不同的指令部分并行處理耻警。

就像我們工廠的流水線一樣隔嫡，我這個奧特曼的腳拼上去了馬上拼下一個奧特曼的腳，我可不會等上一個奧特曼的都組裝完了再組裝下一個奧特曼甘穿。

當(dāng)然也沒有這么死板腮恩，不一定就是順序執(zhí)行，有些指令在等待而后面的指令其實不依賴前面的結(jié)果温兼，所以可以提前執(zhí)行秸滴，這種叫亂序執(zhí)行。

我們再說回我們的分支預(yù)測募判。

這代碼就像我們的人生一樣總會面臨著選擇缸榛，只有做了選擇之后才知道后面的路怎么走呀，但是事實上發(fā)現(xiàn)這代碼經(jīng)常走的是同一個選擇兰伤，于是就想出了一個分支預(yù)測器内颗，讓它來預(yù)測走勢，提前執(zhí)行一路的指令敦腔。

那預(yù)測錯了怎么辦均澳？這和咱們?nèi)松灰粯樱梢?strong>把之前執(zhí)行的結(jié)果全拋了然后再來一遍，但是也有影響找前，也就是流水線越深糟袁，錯的越多浪費的也就越多，錯誤的預(yù)測延遲是10至20個時鐘周期之間躺盛，所以還是有副作用的项戴。

簡單的說就是通過分支預(yù)測器來預(yù)測將來要跳轉(zhuǎn)執(zhí)行的那些指令，然后預(yù)執(zhí)行槽惫，這樣到真正需要它的時候可以直接拿到結(jié)果了周叮，提升了效率。

分支預(yù)測又分了很多種預(yù)測方式界斜，有靜態(tài)預(yù)測仿耽、動態(tài)預(yù)測、隨機預(yù)測等等各薇，從維基百科上看有16種项贺。

我簡單說下我提到的三種，靜態(tài)預(yù)測就是愣頭青峭判，就和蒙英語選擇題一樣开缎，我管你什么題我都選A，也就是說它會預(yù)測一個走勢林螃，一往無前奕删，簡單粗暴。

動態(tài)預(yù)測則會根據(jù)歷史記錄來決定預(yù)測的方向治宣，比如前面幾次選擇都是 true 急侥，那我就走 true 要執(zhí)行的這些指令砌滞，如果變了最近幾次都是 false 侮邀，那我就變成 false 要執(zhí)行的這些指令，其實也是利用了局部性原理贝润。

隨機預(yù)測看名字就知道了绊茧，這是蒙英語選擇題的另一種方式，瞎猜打掘，隨機選一個方向直接執(zhí)行华畏。

還有很多就不一一列舉了，各位有興趣自行去研究尊蚁，順便提一下在 2018 年谷歌的零項目和其他研究人員公布了一個名為 Spectre 的災(zāi)難性安全漏洞亡笑，其可利用 CPU 的分支預(yù)測執(zhí)行泄漏敏感信息，這里就不展開了横朋，文末會附上鏈接仑乌。

之后又有個名為 BranchScope 的攻擊，也是利用預(yù)測執(zhí)行，所以說每當(dāng)一個新的玩意出來總是會帶來利弊晰甚。

至此我們已經(jīng)知曉了什么叫指令流水線和分支預(yù)測了衙传，也理解了 Dubbo 為什么要這么優(yōu)化了，但是文章還沒有結(jié)束厕九，我還想提一提這個 stackoverflow 非常有名的問題蓖捶，看看這數(shù)量。

為什么處理有序數(shù)組要比非有序數(shù)組快扁远？

這個問題在那篇博客開頭就被提出來了俊鱼，很明顯這也是和分支預(yù)測有關(guān)系，既然看到了索性就再分析一波穿香，大伙可以在腦海里先回答一下這個問題亭引，畢竟咱們都知道答案了，看看思路清晰不皮获。

就是下面這段代碼焙蚓，數(shù)組排序了之后循環(huán)的更快。

然后各路大神就蹦出來了洒宝，我們來看一下首贊的大佬怎么說的购公。

一開口就是，直擊要害雁歌。

You are a victim of branch prediction fail.

緊接著就上圖了宏浩，一看就是老司機。

他說讓我們回到 19世紀(jì)靠瞎，一個無法遠(yuǎn)距離交流且無線電還未普及的時候比庄，如果是你這個鐵路交叉口的扳道工，當(dāng)火車快來的時候乏盐，你如何得知該扳哪一邊佳窑？

火車停車再重啟的消耗是很大的，每次到分叉口都停車父能，然后你問他神凑，哥們?nèi)ツ陌。缓蟀饬说篮瘟撸僦貑⒕秃芎臅r溉委，怎么辦？猜爱榕！

猜對了火車就不用停瓣喊，繼續(xù)開。猜錯了就停車然后倒車然后換道再開黔酥。

所以就看猜的準(zhǔn)不準(zhǔn)了藻三！搏一搏單車變摩托八匠。

然后大佬又指出了關(guān)鍵代碼對應(yīng)的匯編代碼，也就是跳轉(zhuǎn)指令了趴酣，這對應(yīng)的就是火車的岔口梨树，該選條路了。

后面我就不分析了岖寞，大伙兒應(yīng)該都知道了抡四，排完序的數(shù)組執(zhí)行到值大于 128 的之后肯定全部大于128了，所以每次分支預(yù)測的結(jié)果都是對了仗谆！所以執(zhí)行的效率很高指巡。

而沒排序的數(shù)組是亂序的，所以很多時候都會預(yù)測錯誤隶垮，而預(yù)測錯誤就得指令流水線排空啊藻雪，然后再來一遍，這速度當(dāng)然就慢了狸吞。

所以大佬說這個題主你是分支預(yù)測錯誤的受害者勉耀。

最終大佬給出的修改方案是咱不用 if 了，惹不起咱還躲不起嘛蹋偏？直接利用位運算來實現(xiàn)這個功能便斥，具體我就不分析了，給大家看下大佬的建議修改方案威始。

最后

這篇文章就差不多了枢纠，今天就是從 Dubbo 的一段代碼開始了探險之旅，分析了波 if 和 switch黎棠，從測試結(jié)果來看 Dubbo 的這次優(yōu)化還不夠徹底晋渺，應(yīng)該全部改成 if else 結(jié)構(gòu)。

而 swtich 從字節(jié)碼上看是優(yōu)于 if 的脓斩，但是從測試結(jié)果來看在分支很多的情況下能顯示出優(yōu)勢木西，一般情況下還是打不過 if 。

然后也知曉了什么叫指令流水線俭厚，這其實就是結(jié)合實際了户魏，流水線才夠快呀驶臊，然后分支預(yù)測預(yù)執(zhí)行也是一個提高效率的方法挪挤，當(dāng)然得猜的對，不然分支預(yù)測錯誤的副作用還是無法忽略的关翎，所以對分支預(yù)測器的要求也是很高的扛门。

JMH 的測試代碼我也打個包，想自己跑的同學(xué)后臺輸入「分支預(yù)測」即可獲取纵寝，如果覺得這篇文章不錯點個在看喲论寨，如果有紕漏請趕緊聯(lián)系鞭撻我星立。

巨人的肩膀

Spectre :https://www.freebuf.com/vuls/160161.html
Dubbo 博客 :http://dubbo.apache.org/zh-cn/blog/optimization-branch-prediction.html
https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array
https://en.wikipedia.org/wiki/Instruction_pipelining
https://en.wikipedia.org/wiki/Branch_predictor

我是 yes，從一點點到億點點葬凳，我們下篇見绰垂。