#?干了這碗雞湯

我要再和生活死磕幾年。要么我就毀滅，要么我就注定鑄就輝煌。如果有一天，你發(fā)現(xiàn)我在平庸面前低了頭，請(qǐng)向我開炮。

--杰克·凱魯亞克

if-else涉及到分支預(yù)測(cè)的概念，關(guān)于分支預(yù)測(cè)上篇文章《虛函數(shù)真的就那么慢嗎？它的開銷究竟在哪里？來看這4段代碼！》程序喵就粗略提到過，這里詳細(xì)講解一下。

首先看一段經(jīng)典的代碼，并統(tǒng)計(jì)它的執(zhí)行時(shí)間：

// test_predict.cc #include?<algorithm> #include?<ctime> #include?<iostream> int?main()?{const?unsigned?ARRAY_SIZE?=?50000;int?data[ARRAY_SIZE];const?unsigned?DATA_STRIDE?=?256;for?(unsigned?c?=?0;?c?<?ARRAY_SIZE;?++c)?data[c]?=?std::rand()?%?DATA_STRIDE;std::sort(data,?data?+?ARRAY_SIZE);{??//?測(cè)試部分clock_t?start?=?clock();long?long?sum?=?0;for?(unsigned?i?=?0;?i?<?100000;?++i)?{for?(unsigned?c?=?0;?c?<?ARRAY_SIZE;?++c)?{if?(data[c]?>=?128)?sum?+=?data[c];}}double?elapsedTime?=?static_cast<double>(clock()?-?start)?/?CLOCKS_PER_SEC;std::cout?<<?elapsedTime?<<?"\n";std::cout?<<?"sum?=?"?<<?sum?<<?"\n";}return?0; } ~/test$ g++ test_predict.cc ;./a.out 7.95312 sum = 480124300000

此程序的執(zhí)行時(shí)間是7.9秒，如果把排序那一行代碼注釋掉，即

// std::sort(data, data + ARRAY_SIZE);

結(jié)果為：

~/test$ g++ test_predict.cc ;./a.out 24.2188 sum = 480124300000

改動(dòng)后的程序執(zhí)行時(shí)間變?yōu)榱?4秒。

其實(shí)只改動(dòng)了一行代碼，程序執(zhí)行時(shí)間卻有3倍的差距，而且看上去數(shù)組是否排序與程序執(zhí)行速度貌似沒什么關(guān)系，這里面其實(shí)涉及到CPU分支預(yù)測(cè)的知識(shí)點(diǎn)。

提到分支預(yù)測(cè)，首先要介紹一個(gè)概念：流水線。

拿理發(fā)舉例，小理發(fā)店一般都是一個(gè)人工作，一個(gè)人洗剪吹一肩挑，而大理發(fā)店分工明確，洗剪吹都有特定的員工，第一個(gè)人在剪發(fā)的時(shí)候，第二個(gè)人就可以洗頭了，第一個(gè)人剪發(fā)結(jié)束吹頭發(fā)的時(shí)候，第二個(gè)人可以去剪發(fā)，第三個(gè)人就可以去洗頭了，極大的提高了效率。

這里的洗剪吹就相當(dāng)于是三級(jí)流水線，在CPU架構(gòu)中也有流水線的概念，如圖：

在執(zhí)行指令的時(shí)候一般有以下幾個(gè)過程：

取指：Fetch

譯指：Decode

執(zhí)行：execute

回寫：Write-back

流水線架構(gòu)可以更好的壓榨流水線上的四個(gè)員工，讓他們不停的工作，使指令執(zhí)行的效率更高。

再談分支預(yù)測(cè)，舉個(gè)經(jīng)典的例子：

火車高速行駛的過程中遇到前方有個(gè)岔路口，假設(shè)火車內(nèi)沒有任何通訊手段，那火車就需要在岔路口前停下，下車詢問別人應(yīng)該選擇哪條路走，弄清楚路線后后再重新啟動(dòng)火車?yán)^續(xù)行駛。高速行駛的火車慢速停下，再重新啟動(dòng)后加速，可以想象這個(gè)過程浪費(fèi)了多少時(shí)間。

有個(gè)辦法，火車在遇到岔路口前可以猜一條路線，到路口時(shí)直接選擇這條路行駛，如果經(jīng)過多個(gè)岔路口，每次做出選擇時(shí)都能選擇正確的路口行駛，這樣火車一路上都不需要減速，速度自然非常快。但如果火車開過頭才發(fā)現(xiàn)走錯(cuò)路了，就需要倒車回到岔路口，選擇正確的路口繼續(xù)行駛，速度自然下降很多。所以預(yù)測(cè)的成功率非常重要，因?yàn)轭A(yù)測(cè)失敗的代價(jià)較高，預(yù)測(cè)成功則一帆風(fēng)順。

計(jì)算機(jī)的分支預(yù)測(cè)就如同火車行駛中遇到了岔路口，預(yù)測(cè)成功則程序的執(zhí)行效率大幅提高，預(yù)測(cè)失敗程序的執(zhí)行效率則大幅下降。

CPU都是多級(jí)流水線架構(gòu)運(yùn)行，如果分支預(yù)測(cè)成功，很多指令都提前進(jìn)入流水線流程中，則流水線中指令運(yùn)行的非常順暢，而如果分支預(yù)測(cè)失敗，則需要清空流水線中的那些預(yù)測(cè)出來的指令，重新加載正確的指令到流水線中執(zhí)行，然而現(xiàn)代CPU的流水線級(jí)數(shù)非常長，分支預(yù)測(cè)失敗會(huì)損失10-20個(gè)左右的時(shí)鐘周期，因此對(duì)于復(fù)雜的流水線，好的分支預(yù)測(cè)方法非常重要。

預(yù)測(cè)方法主要分為靜態(tài)分支預(yù)測(cè)和動(dòng)態(tài)分支預(yù)測(cè)：

靜態(tài)分支預(yù)測(cè)：聽名字就知道，該策略不依賴執(zhí)行環(huán)境，編譯器在編譯時(shí)就已經(jīng)對(duì)各個(gè)分支做好了預(yù)測(cè)。

動(dòng)態(tài)分支預(yù)測(cè)：即運(yùn)行時(shí)預(yù)測(cè)，CPU會(huì)根據(jù)分支被選擇的歷史紀(jì)錄進(jìn)行預(yù)測(cè)，如果最近多次都走了這個(gè)路口，那CPU做出預(yù)測(cè)時(shí)會(huì)優(yōu)先考慮這個(gè)路口。

tips：這里只是簡(jiǎn)單的介紹了分支預(yù)測(cè)的方法，更多的分支預(yù)測(cè)方法資料大家可關(guān)注公眾號(hào)回復(fù)分支預(yù)測(cè)關(guān)鍵字領(lǐng)取。

了解了分支預(yù)測(cè)的概念，我們回到最開始的問題，為什么同一個(gè)程序，排序和不排序的執(zhí)行速度相差那么多。

因?yàn)槌绦蛑杏袀€(gè)if條件判斷，對(duì)于不排序的程序，數(shù)據(jù)散亂分布，CPU進(jìn)行分支預(yù)測(cè)比較困難，預(yù)測(cè)失敗的頻率較高，每次失敗都會(huì)浪費(fèi)10-20個(gè)時(shí)鐘周期，影響程序運(yùn)行的效率。而對(duì)于排序后的數(shù)據(jù)，CPU根據(jù)歷史記錄比較好判斷即將走哪個(gè)分支，大概前一半的數(shù)據(jù)都不會(huì)進(jìn)入if分支，后一半的數(shù)據(jù)都會(huì)進(jìn)入if分支，預(yù)測(cè)的成功率非常高，所以程序運(yùn)行速度很快。

如何解決此問題？總體思路肯定是在程序中盡量減少分支的判斷，方法肯定是具體問題具體分析了，對(duì)于該示例程序，這里提供兩個(gè)思路削減if分支。

方法一：使用位操作：

int t = (data[c] - 128) >> 31; sum += ~t & data[c];

方法二：使用表結(jié)構(gòu)：

#include?<algorithm> #include?<ctime> #include?<iostream>int?main()?{const?unsigned?ARRAY_SIZE?=?50000;int?data[ARRAY_SIZE];const?unsigned?DATA_STRIDE?=?256;for?(unsigned?c?=?0;?c?<?ARRAY_SIZE;?++c)?data[c]?=?std::rand()?%?DATA_STRIDE;int?lookup[DATA_STRIDE];for?(unsigned?c?=?0;?c?<?DATA_STRIDE;?++c)?{lookup[c]?=?(c?>=?128)???c?:?0;}std::sort(data,?data?+?ARRAY_SIZE);{??//?測(cè)試部分clock_t?start?=?clock();long?long?sum?=?0;for?(unsigned?i?=?0;?i?<?100000;?++i)?{for?(unsigned?c?=?0;?c?<?ARRAY_SIZE;?++c)?{//?if?(data[c]?>=?128)?sum?+=?data[c];sum?+=?lookup[data[c]];}}double?elapsedTime?=?static_cast<double>(clock()?-?start)?/?CLOCKS_PER_SEC;std::cout?<<?elapsedTime?<<?"\n";std::cout?<<?"sum?=?"?<<?sum?<<?"\n";}return?0; }

其實(shí)Linux中有一些工具可以檢測(cè)出分支預(yù)測(cè)成功的次數(shù)，有valgrind和perf，使用方式如圖：

圖片截自下方參考資料中

條件分支的使用會(huì)影響程序執(zhí)行的效率，我們平時(shí)開發(fā)過程中應(yīng)該盡可能減少在程序中隨意使用過多的分支，能避免則避免。

更多的分支預(yù)測(cè)方法資料大家可關(guān)注公眾號(hào)回復(fù)分支預(yù)測(cè)關(guān)鍵字領(lǐng)取。

參考資料

http://matt33.com/2020/04/16/cpu-branch-predictor/

https://zhuanlan.zhihu.com/p/22469702

https://en.wikipedia.org/wiki/Branch_predictor

https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array

總結(jié)

以上是生活随笔為你收集整理的少写点if-else吧，它的效率有多低你知道吗？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。