這篇文章主要講解了“如何理解if-else涉及到分支預(yù)測”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“如何理解if-else涉及到分支預(yù)測”吧！

撫順ssl適用于網(wǎng)站、小程序/APP、API接口等需要進(jìn)行數(shù)據(jù)傳輸應(yīng)用場景，ssl證書未來市場廣闊！成為創(chuàng)新互聯(lián)的ssl證書銷售渠道，可以享受市場價(jià)格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：13518219792（備注：SSL證書合作）期待與您的合作！

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

// test_predict.cc #include  #include  #include   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);      {  // 測試部分         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(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ù)測的知識(shí)點(diǎn)。

提到分支預(yù)測，首先要介紹一個(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è)過程：

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

2. 取指：Fetch

3. 譯指：Decode

4. 執(zhí)行：execute

5. 回寫：Write-back

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

再談分支預(yù)測，舉個(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ù)測的成功率非常重要，因?yàn)轭A(yù)測失敗的代價(jià)較高，預(yù)測成功則一帆風(fēng)順。

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

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

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

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

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

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

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

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

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

方法一：使用位操作：

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

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

#include  #include  #include   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);      {  // 測試部分         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(clock() - start) / CLOCKS_PER_SEC;         std::cout << elapsedTime << "\n";         std::cout << "sum = " << sum << "\n";     }     return 0; }

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

感謝各位的閱讀，以上就是“如何理解if-else涉及到分支預(yù)測”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對如何理解if-else涉及到分支預(yù)測這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！