分支預(yù)測(cè)的英文名字是“Branch Prediction”，如果大家在Google上搜索這個(gè)關(guān)鍵字，可以看到關(guān)于分支預(yù)測(cè)的很多內(nèi)容。不過(guò)，要搞清楚分支預(yù)測(cè)是如何工作的，才是問(wèn)題的關(guān)鍵。

?

分支預(yù)測(cè)對(duì)程序的影響

?

下面，我們先來(lái)看兩段代碼。

?

代碼1：

?

#include?
#include?
#include?
int?main()
{
????// Generate data
????const?unsigned?arraySize = 32768;
????int?data[arraySize];
????for?(unsigned?c = 0; c < arraySize; ++c)
????????data[c] = std::rand() % 256;
????// !!! With this, the next loop runs faster.
????//std::sort(data, data + arraySize);
????// Test
????clock_t?start = clock();
????long?long?sum = 0;
????for?(unsigned?i = 0; i < 100000; ++i) {
????????for?(unsigned?c = 0; c < arraySize; ++c) { // Primary loop
????????????if?(data[c] >= 128) sum += data[c];
????????}
????}
????double?elapsedTime = static_cast<double>(clock()-start) / CLOCKS_PER_SEC;
????std::cout?<< elapsedTime << '
';
????std::cout?<< "sum = "?<< sum << '
';
}

?

?

@ubuntu:/data/study$ g++ fenzhi.cpp && ./a.out
21.6046
sum = 314931600000

?

?

#include?
#include?
#include?
int?main()
{
????// Generate data
????const?unsigned?arraySize = 32768;
????int?data[arraySize];
????for?(unsigned?c = 0; c < arraySize; ++c)
????????data[c] = std::rand() % 256;
????// !!! With this, the next loop runs faster.
????std::sort(data, data + arraySize);
????// Test
????clock_t?start = clock();
????long?long?sum = 0;
????for?(unsigned?i = 0; i < 100000; ++i) {
????????for?(unsigned?c = 0; c < arraySize; ++c) { // Primary loop
????????????if?(data[c] >= 128) sum += data[c];
????????}
????}
????double?elapsedTime = static_cast<double>(clock()-start) / CLOCKS_PER_SEC;
????std::cout?<< elapsedTime << '
';
????std::cout?<< "sum = "?<< sum << '
';
}

?

?

@ubuntu:/data/study$ g++ fenzhi.cpp && ./a.out
8.52157
sum = 314931600000

?

?

究竟發(fā)生了什么事情？

?

?

if?(data[c] >= 128) sum += data[c];

?

CPU會(huì)有一個(gè)提前預(yù)測(cè)機(jī)制，比如前面的執(zhí)行結(jié)果都是true，那么下一次在判斷if的時(shí)候，就會(huì)默認(rèn)由true來(lái)處理，讓下面的幾條指令提前進(jìn)入預(yù)裝。

?

當(dāng)然，這個(gè)判斷不會(huì)影響實(shí)際的結(jié)果輸出，這個(gè)判斷只是為了讓CPU并行執(zhí)行代碼。

?

CPU執(zhí)行一條指令分為幾個(gè)階段：

?

?

?

int?a = 0;
a?+= 1;
a?+= 2;
a?+= 3;

?

?

?

?

?

?

?

?

?

?

如果預(yù)測(cè)失敗，會(huì)不會(huì)就影響了執(zhí)行的時(shí)間？答案是肯定的。

?

在前面的例子中，沒(méi)有對(duì)數(shù)組排序的情況下，分支預(yù)測(cè)大部分都會(huì)是失敗的，這個(gè)時(shí)候就會(huì)在執(zhí)行結(jié)束后重新取指令執(zhí)行，會(huì)嚴(yán)重影響執(zhí)行效率。

?

而在排序后的例子中，分支預(yù)測(cè)一直處于成功的狀態(tài)，CPU的執(zhí)行速率得到大幅度的提升。

?

如何解決性能下降問(wèn)題？

?

分支預(yù)測(cè)會(huì)存在一定的能性下降，想讓性能提升的方法，就是不要使用這個(gè)該死的if語(yǔ)句。

?

比如上面的代碼，我們可以修改成這樣：

?

#include?
#include?
#include?
int?main()
{
????// Generate data
????const?unsigned?arraySize = 32768;
????int?data[arraySize];
????for?(unsigned?c = 0; c < arraySize; ++c)
????????data[c] = std::rand() % 256;
????// !!! With this, the next loop runs faster.
????//std::sort(data, data + arraySize);
????// Test
????clock_t?start = clock();
????long?long?sum = 0;
????for?(unsigned?i = 0; i < 100000; ++i) {
????????for?(unsigned?c = 0; c < arraySize; ++c) { // Primary loop
????????????int?t = (data[c] - 128) >> 31;
????????????sum += ~t & data[c];
????????}
????}
????double?elapsedTime = static_cast<double>(clock()-start) / CLOCKS_PER_SEC;
????std::cout?<< elapsedTime << '
';
????std::cout?<< "sum = "?<< sum << '
';
}

?

比如，我們看到的絕對(duì)值代碼，里面也用了這樣的思想。

?

/**
?* abs - return absolute value of an argument
?* @x: the value. If it is unsigned type, it is converted to signed type first.
?* char is treated as if it was signed (regardless of whether it really is)
?* but the macro's return type is preserved as char.
?*
?* Return: an absolute value of x.
?*/
#define abs(x) __abs_choose_expr(x, long long, 
????__abs_choose_expr(x, long, 
????__abs_choose_expr(x, int, 
????__abs_choose_expr(x, short, 
????__abs_choose_expr(x, char, 
????__builtin_choose_expr( 
??????__builtin_types_compatible_p(typeof(x), char), 
??????(char)({ signed?char?__x = (x); __x<0?-__x:__x; }), 
??????((void)0)))))))

#define __abs_choose_expr(x, type, other) __builtin_choose_expr( 
??__builtin_types_compatible_p(typeof(x), signed?type) || 
??__builtin_types_compatible_p(typeof(x), unsigned?type), 
??({ signed?type __x = (x); __x < 0?? -__x : __x; }), other)

?

當(dāng)然，你也可以這樣寫(xiě)：

?

int?abs(int?i){
???if(i<0)
????return?~(--i);
??return?i;
}

?

所以說(shuō)，計(jì)算機(jī)的盡頭是數(shù)學(xué)~

　　審核編輯：湯梓紅