http://www.cnblogs.com/yangecnu/p/4196026.html
2014
一 一個(gè)問(wèn)題
在StackOverflow上有這么一個(gè)問(wèn)題
Why is processing a sorted array faster than an unsorted array? 。例子中，對(duì)一個(gè)數(shù)組進(jìn)行條件求和，在排序前和排序后，性能有很大的差別。原始的例子是C++和Java的，這里將其換成了C# ：
static void Main(string[] args){ // Generate data int arraySize; int[] data; Random rnd; arraySize = 32768; data = new int[arraySize]; rnd = new Random(0); for (int c = 0; c < arraySize; ++c) data[c] = rnd.Next(256); // Test long sum = 0; CodeTimer.Time("unsorted array", 100000, () => { for (int c = 0; c < arraySize; ++c) { if (data[c] >= 128) sum += data[c]; } }); Array.Sort(data); sum = 0; CodeTimer.Time("sorted array", 100000, () => { for (int c = 0; c < arraySize; ++c) { if (data[c] >= 128) sum += data[c]; } }); Console.ReadKey();}
代碼中首先初始化了一個(gè) 32768大小的int型數(shù)組，給這個(gè)數(shù)組的每個(gè)元素隨機(jī)賦予0-256之間的值，然后對(duì)該數(shù)組中大于128部分的數(shù)據(jù)進(jìn)行求和，并將這個(gè)過(guò)程累加100000次。然后分別測(cè)量數(shù)組在排序前和排序后的 耗時(shí)。 這里使用了老趙的
CodeTimer工具來(lái)，本人機(jī)器Xeon? E3-1230
v3@3.30GHz，在debug條件下，結(jié)果如下：
在release條件下，結(jié)果如下：
然后作者提出了問(wèn)題，為什么僅僅對(duì)數(shù)據(jù)進(jìn)行了排序，處理速度就快了將近一倍還要多呢？
排名第一的回答，解釋到是由于分支預(yù)測(cè)錯(cuò)誤導(dǎo)致的性能懲罰，所以會(huì)產(chǎn)生性能的差別。要解釋分支預(yù)測(cè)的懲罰，首先來(lái)看什么是分支預(yù)測(cè)，以及為什么預(yù)測(cè)錯(cuò)誤會(huì)導(dǎo)致懲罰。
二 分支預(yù)測(cè)
什么是分支預(yù)測(cè)? 直接說(shuō)計(jì)算機(jī)概念或許不太好理解，答案以一個(gè)鐵路分支路口的例子來(lái)說(shuō)明了什么是分支預(yù)測(cè)。
考慮下面的鐵軌分支:
假設(shè)在還沒(méi)有遠(yuǎn)距離信號(hào)通訊的時(shí)代。你是一個(gè)鐵路分支路口的操作人員，當(dāng)聽(tīng)到火車(chē)要來(lái)了，你根本不知道即將到來(lái)的這輛火車(chē)要開(kāi)往哪個(gè)方向。于是，你讓這輛或者停下來(lái)，問(wèn)列車(chē)長(zhǎng)這輛車(chē)要開(kāi)往那個(gè)方向，然后將鐵軌扳到對(duì)應(yīng)的方向上。
火車(chē)是一個(gè)很笨重的東西，因此具有很大的慣性，需要花很多時(shí)間啟動(dòng)和停止。
那么，有沒(méi)有更好的辦法呢？那就是，由你來(lái)猜這輛火車(chē)要往那個(gè)方向走！
如果猜對(duì)了，火車(chē)可以直接開(kāi)往要去的方向
如果猜錯(cuò)了，火車(chē)要停下來(lái)，然后倒車(chē)，然后將車(chē)軌扳到正確的方向，然后火車(chē)重新開(kāi)往正確的方向。
如果你的猜測(cè)總是正確的，那么火車(chē)就不用停下來(lái)了
如果你經(jīng)常猜錯(cuò)，那么火車(chē)就要花很多的時(shí)間停下來(lái)，后退，然后重新開(kāi)動(dòng)。
現(xiàn)在，考慮一個(gè)if語(yǔ)句。if 語(yǔ)句編譯為一個(gè)分支判斷指令：
如果你是處理器，你看到了這個(gè)分支，你事先完全沒(méi)沒(méi)有辦法知道將從那個(gè)分支走。那么怎么辦呢？你可以讓指令暫停，等待直到之前的指令執(zhí)行完成，然后比較結(jié)果，然后往正確的那個(gè)方向走。
現(xiàn)代處理器很復(fù)雜，并且有很長(zhǎng)的流水線，因此如果是這樣的話，就需要很多時(shí)間來(lái)預(yù)熱啟動(dòng)和停止。
那么，有沒(méi)有更好一點(diǎn)兒的辦法呢？你來(lái)猜這個(gè)指令將往那個(gè)方向走:
如果猜對(duì)了，語(yǔ)句可以繼續(xù)執(zhí)行
如果猜錯(cuò)了，處理器會(huì)放棄整個(gè)流水線，然后回退到分支地方，繼續(xù)朝正確的分支執(zhí)行。
如果每次都猜對(duì)，那么處理器不需要暫停可以一直執(zhí)行
如果經(jīng)常猜錯(cuò)，那么處理器就要話很多時(shí)間來(lái)暫停，回退，然后重新啟動(dòng)。
這就是分支預(yù)測(cè)，雖然用火車(chē)鐵軌的方式來(lái)解釋可能不太恰當(dāng)，因?yàn)橥ㄟ^(guò)旗幟或者信號(hào)可以提前通知要往那個(gè)方向。 但是對(duì)于計(jì)算機(jī)來(lái)說(shuō)，處理器提前是不知道將要執(zhí)行那個(gè)分支的，只有等到執(zhí)行到分支判斷的那一刻，值求出來(lái)之后才可以確定。
因此如何采用一種策略來(lái)減少出錯(cuò)的次數(shù)，減少類(lèi)似火車(chē)停車(chē)，倒車(chē)，再啟動(dòng)的問(wèn)題呢？很自然的，可以根據(jù)以往的情形來(lái)推斷！如果這個(gè)火車(chē)以前有99%的情況走左邊，那么就可以在火車(chē)來(lái)之前猜測(cè)他走左邊。如果行為發(fā)生變化，可以做相應(yīng)的調(diào)整。如果發(fā)現(xiàn)每3次調(diào)整一次方向，那么總結(jié)出這個(gè)規(guī)律后就可以做出適當(dāng)?shù)恼{(diào)整。
換句話說(shuō)，我們需要總結(jié)出一些模式，然后遵循。這或多或少就是
分支預(yù)測(cè)器的工作。
大多數(shù)的應(yīng)用都有行為良好的分支。因此現(xiàn)代的分支預(yù)測(cè)器能到達(dá)到90%以上的預(yù)測(cè)正確率。但是面對(duì)一些不可預(yù)見(jiàn)的分支和不可知的模式，分支預(yù)測(cè)器就沒(méi)有多大用了。
通過(guò)上面的描述，出現(xiàn)性能差別的問(wèn)題關(guān)鍵在于這個(gè)if語(yǔ)句：
if (data[c] >= 128) sum += data[c];
注意到data這個(gè)數(shù)組里面的值是平均分布于0-255之間的。當(dāng)數(shù)據(jù)排好序之后，前半部分的數(shù)據(jù)都會(huì)小于128，所以不會(huì)進(jìn)到if語(yǔ)句里面，后半部分的值都大于128，所以會(huì)進(jìn)到循環(huán)語(yǔ)句。
這種規(guī)律對(duì)于分支預(yù)測(cè)器非常友好，因?yàn)榉种袛嗾Z(yǔ)句發(fā)現(xiàn)總是選擇某個(gè)方向很多次，于是就很容易做出判斷。即使一個(gè)簡(jiǎn)單的計(jì)數(shù)器就可以正確預(yù)測(cè)分支的方向，除了改變方向之后的一兩次預(yù)測(cè)失敗之外。
下面描述了理器在分支預(yù)測(cè)時(shí)的行為：
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 (很容易進(jìn)行預(yù)測(cè))
可以看到，當(dāng)數(shù)據(jù)排好序之后，對(duì)分支預(yù)測(cè)器十分友好，很容易進(jìn)行預(yù)測(cè)。
但是，當(dāng)數(shù)據(jù)完全是隨機(jī)的時(shí)候，分支預(yù)測(cè)器便失去了用處，因?yàn)樗麩o(wú)法預(yù)測(cè)隨機(jī)的數(shù)據(jù)。因此會(huì)有大概50%的預(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ī)出現(xiàn) – 很難預(yù)測(cè))
那么怎么辦呢？
如果計(jì)算機(jī)沒(méi)有辦法將分支優(yōu)化成條件轉(zhuǎn)移，也可以使用一些技巧，犧牲一些可讀性，移除條件判斷，來(lái)提高性能
比如，可以將下面的分支語(yǔ)句：
if (data[c] >= 128) sum += data[c];
替換為：
int t = (data[c] - 128) >> 31;sum += ~t & data[c];
這里使用了位運(yùn)算，移除了分支預(yù)測(cè)。 移除分之后，再進(jìn)行測(cè)試，在release條件下，結(jié)果如下：
可以看到，在沒(méi)有分支判斷的條件下，對(duì)有序和無(wú)序數(shù)組的處理，在速度上是差不多的。
但是，為什么分支預(yù)測(cè)能夠提高應(yīng)用程序的執(zhí)行效率，這就要來(lái)看看現(xiàn)代CPU的流水線設(shè)計(jì)了。
三 指令的流水線
指令的流水線化(pipelining)是一種增加指令吞吐量(throughput)的方法，即在單位時(shí)間內(nèi)能夠提高同時(shí)執(zhí)行指令的個(gè)數(shù)。他將一個(gè)基本的流水線拆分為了幾個(gè)連續(xù)的，獨(dú)立的步驟，然后某些步驟就可以同時(shí)執(zhí)行。
流水線化通過(guò)同時(shí)執(zhí)行一系列操作增加了吞吐量，但是她并沒(méi)有減少延遲，即并沒(méi)有減少一條指令從執(zhí)行開(kāi)始到執(zhí)行結(jié)束的時(shí)間，仍要等到這一系列指令完成。實(shí)際上,流水線化由于將一條指令拆分成了幾個(gè)步驟從而可能會(huì)增加延遲。
上圖是一個(gè)具有4層流水線的示意圖，一般的一個(gè)方法可以分為四個(gè)步驟，讀取指令(Fetch)，指令解碼(Decode),運(yùn)行指令(Execute)和寫(xiě)回運(yùn)行結(jié)果(Write back)。
上方灰色部分是一連串未運(yùn)行的指令；下方灰色部分是已執(zhí)行完成的指令，中間白色部分是流水線。下面是在每個(gè)時(shí)鐘周期下指令的執(zhí)行狀態(tài)。
時(shí)鐘序列
運(yùn)行情況
0
四條指令等待運(yùn)行
1
· 從
存儲(chǔ)器(memory)中讀取綠色指令
2
· 綠色指令被解碼
· 從主存儲(chǔ)器中讀取紫色指令
3
· 綠色指令被運(yùn)行（事實(shí)上運(yùn)算已經(jīng)開(kāi)始(performed)）
· 紫色指令被解碼
· 從主存儲(chǔ)器中讀取藍(lán)色指令
4
· 綠色指令的運(yùn)算結(jié)果被寫(xiě)回到
寄存器(register)或者主存儲(chǔ)器
· 紫色指令被運(yùn)行
· 藍(lán)色指令被解碼
· 從主存儲(chǔ)器中讀取紅色指令
5
· 綠色指令被運(yùn)行完畢
· 紫色指令的運(yùn)算結(jié)果被寫(xiě)回到寄存器或者主存儲(chǔ)器
· 藍(lán)色指令被運(yùn)行
· 紅色指令被解碼
6
· 紫色指令被運(yùn)行完畢
· 藍(lán)色指令的運(yùn)算結(jié)果被寫(xiě)回到寄存器或者主存儲(chǔ)器
· 紅色指令被運(yùn)行
7
· 藍(lán)色指令被運(yùn)行完畢
· 紅色指令的運(yùn)算結(jié)果被寫(xiě)回到寄存器或者主存儲(chǔ)器
8
· 紅色指令被運(yùn)行完畢
可見(jiàn)，流水線技術(shù)的主要目的就是通過(guò)重疊連續(xù)指令的步驟來(lái)提高吞吐量從而獲得性能，要做到這一點(diǎn)，就必須能夠?qū)崿F(xiàn)確定要執(zhí)行指令的序列和先后順序，這樣才能使流水線中充滿(mǎn)了待執(zhí)行的指令。當(dāng)處理器遇到分支條件跳轉(zhuǎn)時(shí)，通常不能確定執(zhí)行那個(gè)分支，因此處理器采用分支預(yù)測(cè)器來(lái)猜測(cè)每條跳轉(zhuǎn)指令是否會(huì)執(zhí)行。如果猜測(cè)比較可靠，那么流水線中就會(huì)充滿(mǎn)指令。但是，如果對(duì)跳轉(zhuǎn)的指令猜測(cè)錯(cuò)誤，那么就要要求處理器丟掉它這個(gè)跳轉(zhuǎn)指令后的所有已做的操作，然后再開(kāi)始用從正確位置處起始的指令去填充流水線，可以看到這種預(yù)測(cè)錯(cuò)誤會(huì)導(dǎo)致很?chē)?yán)重的性能懲罰，會(huì)導(dǎo)致大約20-40個(gè)時(shí)鐘周期的浪費(fèi)，從而導(dǎo)致性能的嚴(yán)重下降。
在這部分開(kāi)始處已經(jīng)說(shuō)明，如果編譯器不能將分支跳轉(zhuǎn)優(yōu)化為條件轉(zhuǎn)移指令，可以使用一些技巧，比如位運(yùn)算來(lái)移除分支判斷。
那就是說(shuō)，如果能夠優(yōu)化為條件轉(zhuǎn)移指令，也能提升性能。在該問(wèn)題的Update部分，提問(wèn)者說(shuō):
“GCC 4.6.1 with -O3 or -ftree-vectorize on x64 is able to generate a conditional move. So there is no difference between the sorted and unsorted data - both are fast. ”
GCC是C/C++編譯器，-O3是表示優(yōu)化級(jí)別，可以將條件跳轉(zhuǎn)優(yōu)化為條件傳送指令，從而使得在有序和無(wú)序情況下，對(duì)數(shù)據(jù)的處理同樣高效，那么條件轉(zhuǎn)移指令是什么呢？
四 條件傳送指令
關(guān)于條件傳送指令，在CSAPP這本書(shū)的第3.6.6部分有教詳細(xì)的介紹。這里針對(duì)這一具體問(wèn)題詳細(xì)介紹一下，條件轉(zhuǎn)移指令是如何優(yōu)化條件分支判斷，從而利用流水線從而提高應(yīng)用程序效率的。
條件傳送是一種條件跳轉(zhuǎn)的一種替換策略，他首先就計(jì)算出一個(gè)條件的兩種結(jié)果，然后等到執(zhí)行到分支判斷的地方，根據(jù)條件選擇一個(gè)結(jié)果。只有在一些受限的條件下這種策略才可行，比如這個(gè)例子中的判斷數(shù)字是否大于128然后求和。但是如果可行，就可以通過(guò)一條簡(jiǎn)單的條件傳送指令來(lái)實(shí)現(xiàn)，而不是需要條件跳轉(zhuǎn)指令來(lái)實(shí)現(xiàn)分支判斷。比如下面的求兩個(gè)數(shù)相減絕對(duì)值的方法，如果不使用條件傳送指令：
在比較大小之后，通過(guò)跳轉(zhuǎn)指令，可以跳轉(zhuǎn)到正確的分支然后執(zhí)行接下來(lái)的邏輯。 要利用流水線技術(shù)，分支預(yù)測(cè)器不能依賴(lài)上一步驟的結(jié)果出來(lái)了再去做判斷，它不可能等到cmpl執(zhí)行完成再去選擇分支，它需要提前做出判斷，如果判斷正確，沒(méi)有問(wèn)題，如果錯(cuò)誤，就有比較嚴(yán)重的錯(cuò)誤懲罰，從而影響應(yīng)用程序性能。
但是，如果使用條件跳轉(zhuǎn)，情況如下：
首先計(jì)算出了兩個(gè)分支的結(jié)果，然后判斷條件，對(duì)兩個(gè)分支的結(jié)果做出選擇。這里面就沒(méi)有分支判斷和跳轉(zhuǎn)指令，通過(guò)一條cmovl指令 (c表示條件，l表示less)就可以完成判斷和賦值，這樣分支預(yù)測(cè)器不需要做出分支判斷，能夠利用流水線，從而提高應(yīng)用程序性能。
但是，使用條件傳送也不總是能夠提高代碼效率。如果條件的兩個(gè)分支都需要大量的計(jì)算，那么實(shí)現(xiàn)計(jì)算出來(lái)就需要很多時(shí)間，當(dāng)條件不滿(mǎn)足時(shí)，這部分工作就浪費(fèi)了。編譯器必須在條件傳送浪費(fèi)的計(jì)算時(shí)間和分支預(yù)測(cè)錯(cuò)誤造成的性能處罰之間做出權(quán)衡。一般的，只有在分支處的兩個(gè)表達(dá)式都很容易計(jì)算時(shí)，比如只有一條加法指令，就像本例中的”
sum += data[c]; “ 這樣，條件傳送替換條件跳轉(zhuǎn)才能提高效率?？偟膩?lái)說(shuō)，條件數(shù)據(jù)傳送提供了一種用條件轉(zhuǎn)移來(lái)實(shí)現(xiàn)條件操作的替換策略，他只能用于一些很簡(jiǎn)單的場(chǎng)景，但是這種情況還是比較常見(jiàn)的，它能夠充分利用現(xiàn)代處理器的流水線從而提高效率。
五 結(jié)論
本文首先引用了StackOverflow上的一個(gè)問(wèn)題及其解答說(shuō)明了分支預(yù)測(cè)錯(cuò)誤對(duì)應(yīng)于程序性能的影響，然后簡(jiǎn)單分析了現(xiàn)代處理器流水線中如何使用分支預(yù)測(cè)提高應(yīng)用程序性能以及分支預(yù)測(cè)錯(cuò)誤導(dǎo)致的性能懲罰，最后結(jié)合問(wèn)題給出的使用技巧替換分支判斷，簡(jiǎn)要分析了為什么通過(guò)將條件跳轉(zhuǎn)優(yōu)化為條件傳送能夠充分利用指令流水線，從而同樣能夠提高程序性能。
希望本文對(duì)您了解分支預(yù)測(cè)、條件轉(zhuǎn)移和指令流水線有所幫助。
參考資料
Why is processing a sorted array faster than an unsorted array?Computer Systems: A Programmer's Perspective (2nd Edition),Chapter 3.66Branch_predictorInstruction_pipelinewhy-is-a-conditional-move-not-vulnerable-for-branch-prediction-failure
