建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
說(shuō)明： 本文以stackoverflow上Why is it faster to process a sorted array than an unsorted array?為原型，翻譯了問(wèn)題和高票回答并加入了大量補(bǔ)充說(shuō)明，方便讀者理解。
創(chuàng)新互聯(lián)憑借專(zhuān)業(yè)的設(shè)計(jì)團(tuán)隊(duì)扎實(shí)的技術(shù)支持、優(yōu)質(zhì)高效的服務(wù)意識(shí)和豐厚的資源優(yōu)勢(shì)，提供專(zhuān)業(yè)的網(wǎng)站策劃、網(wǎng)站設(shè)計(jì)、成都網(wǎng)站設(shè)計(jì)、網(wǎng)站優(yōu)化、軟件開(kāi)發(fā)、網(wǎng)站改版等服務(wù)，在成都10余年的網(wǎng)站建設(shè)設(shè)計(jì)經(jīng)驗(yàn)，為成都1000+中小型企業(yè)策劃設(shè)計(jì)了網(wǎng)站。
背景
先來(lái)看段c++代碼，我們用256的模數(shù)隨機(jī)填充一個(gè)固定大小的大數(shù)組，然后對(duì)數(shù)組的一半元素求和：
- #include
- #include
- #include
- int main()
- {
- // 隨機(jī)產(chǎn)生整數(shù)，用分區(qū)函數(shù)填充，以避免出現(xiàn)分桶不均
- const unsigned arraySize = 32768;
- int data[arraySize];
- for (unsigned c = 0; c < arraySize; ++c)
- data[c] = std::rand() % 256;
- // !!! 排序后下面的Loop運(yùn)行將更快
- std::sort(data, data + arraySize);
- // 測(cè)試部分
- clock_t start = clock();
- long long sum = 0;
- for (unsigned i = 0; i < 100000; ++i)
- {
- // 主要計(jì)算部分，選一半元素參與計(jì)算
- for (unsigned c = 0; c < arraySize; ++c)
- {
- if (data[c] >= 128)
- sum += data[c];
- }
- }
- double elapsedTime = static_cast
(clock() - start) / CLOCKS_PER_SEC; - std::cout << elapsedTime << std::endl;
- std::cout << "sum = " << sum << std::endl;
- }
編譯并運(yùn)行：
- g++ branch_prediction.cpp
- ./a.out
在我的macbook air上運(yùn)行結(jié)果：
- # 1. 取消std::sort(data, data + arraySize);的注釋?zhuān)聪扰判蚝笥?jì)算
- 10.218
- sum = 312426300000
- # 2. 注釋掉std::sort(data, data + arraySize);即不排序，直接計(jì)算
- 29.6809
- sum = 312426300000
由此可見(jiàn)，先排序后計(jì)算，運(yùn)行效率有進(jìn)3倍的提高。
為保證結(jié)論的可靠性， 我們?cè)儆胘ava來(lái)測(cè)一遍：
- import java.util.Arrays;
- import java.util.Random;
- public class Main
- {
- public static void main(String[] args)
- {
- // Generate data
- int arraySize = 32768;
- int data[] = new int[arraySize];
- Random rnd = new Random(0);
- for (int c = 0; c < arraySize; ++c)
- data[c] = rnd.nextInt() % 256;
- // !!! With this, the next loop runs faster
- Arrays.sort(data);
- // Test
- long start = System.nanoTime();
- long sum = 0;
- for (int i = 0; i < 100000; ++i)
- {
- // Primary loop
- for (int c = 0; c < arraySize; ++c)
- {
- if (data[c] >= 128)
- sum += data[c];
- }
- }
- System.out.println((System.nanoTime() - start) / 1000000000.0);
- System.out.println("sum = " + sum);
- }
- }
在intellij idea中運(yùn)行結(jié)果：
- # 1. 先排序后計(jì)算
- 5.549553
- sum = 155184200000
- # 2. 不排序直接結(jié)算
- 15.527867
- sum = 155184200000
也有三倍左右的差距。且java版要比c++版整體快近乎1倍?這應(yīng)該是編譯時(shí)用了默認(rèn)選項(xiàng)，gcc優(yōu)化不夠的原因，后續(xù)再調(diào)查這個(gè)問(wèn)題。
問(wèn)題的提出
以上代碼在數(shù)組填充時(shí)已經(jīng)加入了分區(qū)函數(shù)，充分保證填充值的隨機(jī)性，計(jì)算時(shí)也是按一半的元素來(lái)求和，所以不存在特例情況。而且，計(jì)算也完全不涉及到數(shù)據(jù)的有序性，即數(shù)組是否有序理論上對(duì)計(jì)算不會(huì)產(chǎn)生任何作用。在這樣的前提下，為什么排序后的數(shù)組要比未排序數(shù)組運(yùn)行快3倍以上?
分析
想象一個(gè)鐵路分叉道口。
為了論證此問(wèn)題，讓我們回到19世紀(jì)，那個(gè)遠(yuǎn)距離無(wú)線(xiàn)通信還未普及的年代。你是鐵路交叉口的扳道工。當(dāng)聽(tīng)到火車(chē)快來(lái)了的時(shí)候，你無(wú)法猜測(cè)它應(yīng)該朝哪個(gè)方向走。于是你叫停了火車(chē)，上前去問(wèn)火車(chē)司機(jī)該朝哪個(gè)方向走，以便你能正確地切換鐵軌。
要知道，火車(chē)是非常龐大的，切急速行駛時(shí)有巨大的慣性。為了完成上述停車(chē)-問(wèn)詢(xún)-切軌的一系列動(dòng)作，火車(chē)需耗費(fèi)大量時(shí)間減速，停車(chē)，重新開(kāi)啟。
既然上述過(guò)車(chē)非常耗時(shí)，那是否有更好的方法?當(dāng)然有!當(dāng)火車(chē)即將行駛過(guò)來(lái)前，你可以猜測(cè)火車(chē)該朝哪個(gè)方向走。
- 如果猜對(duì)了，它直接通過(guò)，繼續(xù)前行。
- 如果猜錯(cuò)了，車(chē)頭將停止，倒回去，你將鐵軌扳至反方向，火車(chē)重新啟動(dòng)，駛過(guò)道口。
如果你不幸每次都猜錯(cuò)了，那么火車(chē)將耗費(fèi)大量時(shí)間停車(chē)-倒回-重啟。如果你很幸運(yùn)，每次都猜對(duì)了呢?火車(chē)將從不停車(chē)，持續(xù)前行!
上述比喻可應(yīng)用于處理器級(jí)別的分支跳轉(zhuǎn)指令里：
原程序：
- if (data[c] >= 128)
- sum += data[c];
匯編碼：
- cmp edx, 128
- jl SHORT $LN3@main
- add rbx, rdx
- $LN3@main:
讓我們回到文章開(kāi)頭的問(wèn)題?，F(xiàn)在假設(shè)你是處理器，當(dāng)看到上述分支時(shí)，當(dāng)你并不能決定該如何往下走，該如何做?只能暫停運(yùn)行，等待之前的指令運(yùn)行結(jié)束。然后才能繼續(xù)沿著正確地路徑往下走。
要知道，現(xiàn)代編譯器是非常復(fù)雜的，運(yùn)行時(shí)有著非常長(zhǎng)的pipelines， 減速和熱啟動(dòng)將耗費(fèi)巨量的時(shí)間。
那么，有沒(méi)有好的辦法可以節(jié)省這些狀態(tài)切換的時(shí)間呢?你可以猜測(cè)分支的下一步走向!
如果猜錯(cuò)了，處理器要flush掉pipelines, 回滾到之前的分支，然后重新熱啟動(dòng)，選擇另一條路徑。
如果猜對(duì)了，處理器不需要暫停，繼續(xù)往下執(zhí)行。
如果每次都猜錯(cuò)了，處理器將耗費(fèi)大量時(shí)間在停止-回滾-熱啟動(dòng)這一周期性過(guò)程里。如果僥幸每次都猜對(duì)了，那么處理器將從不暫停，一直運(yùn)行至結(jié)束。
上述過(guò)程就是分支預(yù)測(cè)(branch prediction)。雖然在現(xiàn)實(shí)的道口鐵軌切換中，可以通過(guò)一個(gè)小旗子作為信號(hào)來(lái)判斷火車(chē)的走向，但是處理器卻無(wú)法像火車(chē)那樣去預(yù)知分支的走向--除非最后一次指令運(yùn)行完畢。
那么處理器該采用怎樣的策略來(lái)用最小的次數(shù)來(lái)盡量猜對(duì)指令分支的下一步走向呢?答案就是分析歷史運(yùn)行記錄： 如果火車(chē)過(guò)去90%的時(shí)間都是走左邊的鐵軌，本次軌道切換，你就可以猜測(cè)方向?yàn)樽?，反之，則為右。如果在某個(gè)方向上走過(guò)了3次，接下來(lái)你也可以猜測(cè)火車(chē)將繼續(xù)在這個(gè)方向上運(yùn)行...
換句話(huà)說(shuō)，你試圖通過(guò)歷史記錄，識(shí)別出一種隱含的模式并嘗試在后續(xù)鐵道切換的抉擇中繼續(xù)應(yīng)用它。這和處理器的分支預(yù)測(cè)原理或多或少有點(diǎn)相似。
大多數(shù)應(yīng)用都具有狀態(tài)良好的(well-behaved)分支，所以現(xiàn)代化的分支預(yù)測(cè)器一般具有超過(guò)90%的命中率。但是面對(duì)無(wú)法預(yù)測(cè)的分支，且沒(méi)有識(shí)別出可應(yīng)用的的模式時(shí)，分支預(yù)測(cè)器就無(wú)用武之地了。
關(guān)于分支預(yù)測(cè)期，可參考維基百科相關(guān)詞條"Branch predictor" article on Wikipedia..
文首導(dǎo)致非排序數(shù)組相加耗時(shí)顯著增加的罪魁禍?zhǔn)妆闶莍f邏輯：
- if (data[c] >= 128)
- sum += data[c];
注意到data數(shù)組里的元素是按照0-255的值被均勻存儲(chǔ)的(類(lèi)似均勻的分桶)。數(shù)組data有序時(shí)，前面一半元素的迭代將不會(huì)進(jìn)入if-statement, 超過(guò)一半時(shí)，元素迭代將全部進(jìn)入if-statement.
這樣的持續(xù)朝同一個(gè)方向切換的迭代對(duì)分支預(yù)測(cè)器來(lái)說(shuō)是非常友好的，前半部分元素迭代完之后，后續(xù)迭代分支預(yù)測(cè)器對(duì)分支方向的切換預(yù)測(cè)將全部正確。
簡(jiǎn)單地分析一下：有序數(shù)組的分支預(yù)測(cè)流程：
- T = 分支命中
- N = 分支沒(méi)有命中
- data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
- branch = N N N N N ... N N T T T ... T T T ...
- = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (非常容易預(yù)測(cè))
無(wú)序數(shù)組的分支預(yù)測(cè)流程：
- data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
- branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
- = TTNTTTTNTNNTTTN ... (完全隨機(jī)--無(wú)法預(yù)測(cè))
在本例中，由于data數(shù)組元素填充的特殊性，決定了分支預(yù)測(cè)器在未排序數(shù)組迭代過(guò)程中將有50%的錯(cuò)誤命中率，因而執(zhí)行完整個(gè)sum操作將會(huì)耗時(shí)更多。
優(yōu)化
利用位運(yùn)算取消分支跳轉(zhuǎn)?；局R(shí)：
- |x| >> 31 = 0 # 非負(fù)數(shù)右移31為一定為0
- ~(|x| >> 31) = -1 # 0取反為-1
- -|x| >> 31 = -1 # 負(fù)數(shù)右移31為一定為0xffff = -1
- ~(-|x| >> 31) = 0 # -1取反為0
- -1 = 0xffff
- -1 & x = x # 以-1為mask和任何數(shù)求與，值不變
故分支判斷可優(yōu)化為：
- int t = (data[c] - 128) >> 31; # statement 1
- sum += ~t & data[c]; # statement 2
分析：
- data[c] < 128, 則statement 1值為: 0xffff = -1, statement 2等號(hào)右側(cè)值為: 0 & data[c] == 0;
- data[c] >= 128, 則statement 1值為: 0, statement 2等號(hào)右側(cè)值為: ~0 & data[c] == -1 & data[c] == 0xffff & data[c] == data[c];
故上述位運(yùn)算實(shí)現(xiàn)的sum邏輯完全等價(jià)于if-statement, 更多的位運(yùn)算hack操作請(qǐng)參見(jiàn)bithacks.
若想避免移位操作，可以使用如下方式：
- int t=-((data[c]>=128)); # generate the mask
- sum += ~t & data[c]; # bitwise AND
結(jié)論
- 使用分支預(yù)測(cè): 是否排序嚴(yán)重影響performance
- 使用bithack: 是否排序?qū)erformance無(wú)顯著影響
這個(gè)例子告訴給我們啟示: 在大規(guī)模循環(huán)邏輯中要盡量避免數(shù)據(jù)強(qiáng)依賴(lài)的分支(data-dependent branching).
補(bǔ)充知識(shí)
Pipeline
先簡(jiǎn)單說(shuō)明一下CPU的instruction pipeline(指令流水線(xiàn))，以下簡(jiǎn)稱(chēng)pipeline。 Pipieline假設(shè)程序運(yùn)行時(shí)有一連串指令要被運(yùn)行，將程序運(yùn)行劃分成幾個(gè)階段，按照一定的順序并行處理之，這樣便能夠加速指令的通過(guò)速度。
絕大多數(shù)pipeline都由時(shí)鐘頻率(clock)控制，在數(shù)字電路中，clock控制邏輯門(mén)電路(logical cicuit)和觸發(fā)器(trigger), 當(dāng)受到時(shí)鐘頻率觸發(fā)時(shí)，觸發(fā)器得到新的數(shù)值，并且邏輯門(mén)需要一段時(shí)間來(lái)解析出新的數(shù)值，而當(dāng)受到下一個(gè)時(shí)鐘頻率觸發(fā)時(shí)觸發(fā)器又得到新的數(shù)值，以此類(lèi)推。
而借由邏輯門(mén)分散成很多小區(qū)塊，再讓觸發(fā)器鏈接這些小區(qū)塊組，使邏輯門(mén)輸出正確數(shù)值的時(shí)間延遲得以減少，這樣一來(lái)就可以減少指令運(yùn)行所需要的周期。 這對(duì)應(yīng)Pipeline中的各個(gè)stages。
一般的pipeline有四個(gè)執(zhí)行階段(execuate stage): 讀取指令(Fetch) -> 指令解碼(Decode) -> 運(yùn)行指令(Execute) -> 寫(xiě)回運(yùn)行結(jié)果(Write-back).
分支預(yù)測(cè)器
分支預(yù)測(cè)器是一種數(shù)字電路，在分支指令執(zhí)行前，猜測(cè)哪一個(gè)分支會(huì)被執(zhí)行，能顯著提高pipelines的性能。
條件分支通常有兩路后續(xù)執(zhí)行分支，not token時(shí),跳過(guò)接下來(lái)的JMP指令，繼續(xù)執(zhí)行， token時(shí)，執(zhí)行JMP指令，跳轉(zhuǎn)到另一塊程序內(nèi)存去執(zhí)行。
為了說(shuō)明這個(gè)問(wèn)題，我們先考慮如下問(wèn)題。
沒(méi)有分支預(yù)測(cè)器會(huì)怎樣?
加入沒(méi)有分支預(yù)測(cè)器，處理器會(huì)等待分支指令通過(guò)了pipeline的執(zhí)行階段(execuate stage)才能把下一條指令送入pipeline的fetch stage。
這會(huì)造成流水線(xiàn)停頓(stalled)或流水線(xiàn)冒泡(bubbling)或流水線(xiàn)打嗝(hiccup)，即在流水線(xiàn)中生成一個(gè)沒(méi)有實(shí)效的氣泡， 如下圖所示：
圖中一個(gè)氣泡在編號(hào)為3的始終頻率中產(chǎn)生，指令運(yùn)行被延遲。
Stream hiccup現(xiàn)象在早期的RISC體系結(jié)構(gòu)處理器中常見(jiàn)。
有分支預(yù)測(cè)期的pipeline
我們來(lái)看分支預(yù)測(cè)器在條件分支跳轉(zhuǎn)中的應(yīng)用。條件分支通常有兩路后續(xù)執(zhí)行分支，not token時(shí),跳過(guò)接下來(lái)的JMP指令，繼續(xù)執(zhí)行， token時(shí)，執(zhí)行JMP指令，跳轉(zhuǎn)到另一塊程序內(nèi)存去執(zhí)行。
加入分支預(yù)測(cè)器后，為避免pipeline停頓(stream stalled)，其會(huì)猜測(cè)兩路分支哪一路最有可能執(zhí)行，然后投機(jī)執(zhí)行，如果猜錯(cuò)，則流水線(xiàn)中投機(jī)執(zhí)行中間結(jié)果全部拋棄，重新獲取正確分支路線(xiàn)上的指令執(zhí)行?？梢?jiàn)，錯(cuò)誤的預(yù)測(cè)會(huì)導(dǎo)致程序執(zhí)行的延遲。
由前面可知，Pipeline執(zhí)行主要涉及Fetch, Decode, Execute, Write-back幾個(gè)stages, 分支預(yù)測(cè)失敗會(huì)浪費(fèi)Write-back之前的流水線(xiàn)級(jí)數(shù)?，F(xiàn)代CPU流水線(xiàn)級(jí)數(shù)非常長(zhǎng)，分支預(yù)測(cè)失敗可能會(huì)損失20個(gè)左右的時(shí)鐘周期，因此對(duì)于復(fù)雜的流水線(xiàn)，好的分支預(yù)測(cè)器非常重要。
常見(jiàn)的分支預(yù)測(cè)器
- 靜態(tài)分支預(yù)測(cè)器
靜態(tài)分支預(yù)測(cè)器有兩個(gè)解碼周期，分別評(píng)價(jià)分支，解碼。即在分支指令執(zhí)行前共經(jīng)歷三個(gè)時(shí)鐘周期。詳情見(jiàn)圖：
- 雙模態(tài)預(yù)測(cè)器(bimodal predictor)
也叫飽和計(jì)數(shù)器，是一個(gè)四狀態(tài)狀態(tài)機(jī). 四個(gè)狀態(tài)對(duì)應(yīng)兩個(gè)選擇: token, not token， 每個(gè)選擇有兩個(gè)狀態(tài)區(qū)分強(qiáng)弱：strongly,weakly。分別是Strongly not taken，Weakly not taken, Weakly taken, Strongly taken。
狀態(tài)機(jī)工作原理圖如下：
圖左邊兩個(gè)狀態(tài)為不采納(not token)，右邊兩個(gè)為采納(token)。由not token到token中間有兩個(gè)漸變狀態(tài)。由紅色到綠色翻轉(zhuǎn)需要連續(xù)兩次分支選擇。
技術(shù)實(shí)現(xiàn)上可用兩個(gè)二進(jìn)制位來(lái)表示，00, 01, 10, 11分別對(duì)應(yīng)strongly not token, weakly not token, weakly token, strongly token。 一個(gè)判斷兩個(gè)分支預(yù)測(cè)規(guī)則是否改變的簡(jiǎn)單方法便是判斷這個(gè)二級(jí)制狀態(tài)高位是否跳變。高位從0變?yōu)?， 強(qiáng)狀態(tài)發(fā)生翻轉(zhuǎn)，則下一個(gè)分支指令預(yù)測(cè)從not token變?yōu)閠oken，反之亦然。
據(jù)評(píng)測(cè)，雙模態(tài)預(yù)測(cè)器的正確率可達(dá)到93.5%。預(yù)測(cè)期一般在分支指令解碼前起作用。
其它常見(jiàn)分支預(yù)測(cè)器如兩級(jí)自適應(yīng)預(yù)測(cè)器，局部/全局分支預(yù)測(cè)器，融合分支預(yù)測(cè)器，Agree預(yù)測(cè)期，神經(jīng)分支預(yù)測(cè)器等。
分享標(biāo)題：深入理解CPU的分支預(yù)測(cè)(BranchPrediction)模型
分享URL：http://www.5511xx.com/article/cdjoipp.html
