少寫點if-else吧，它的效率有多低你知道嗎？
if-else涉及到分支預測的概念，關(guān)于分支預測上篇文章《虛函數(shù)真的就那么慢嗎?它的開銷究竟在哪里?來看這4段代碼!》程序喵就粗略提到過，這里詳細講解一下。
首先看一段經(jīng)典的代碼，并統(tǒng)計它的執(zhí)行時間：
- // 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);
- { // 測試部分
- 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í)行時間是7.9秒，如果把排序那一行代碼注釋掉，即
- // std::sort(data, data + ARRAY_SIZE);
結(jié)果為：
- ~/test$ g++ test_predict.cc ;./a.out
- 24.2188
- sum = 480124300000
改動后的程序執(zhí)行時間變?yōu)榱?4秒。
其實只改動了一行代碼，程序執(zhí)行時間卻有3倍的差距，而且看上去數(shù)組是否排序與程序執(zhí)行速度貌似沒什么關(guān)系，這里面其實涉及到CPU分支預測的知識點。
提到分支預測，首先要介紹一個概念：流水線。
拿理發(fā)舉例，小理發(fā)店一般都是一個人工作，一個人洗剪吹一肩挑，而大理發(fā)店分工明確，洗剪吹都有特定的員工，第一個人在剪發(fā)的時候，第二個人就可以洗頭了，第一個人剪發(fā)結(jié)束吹頭發(fā)的時候，第二個人可以去剪發(fā)，第三個人就可以去洗頭了，極大的提高了效率。
這里的洗剪吹就相當于是三級流水線，在CPU架構(gòu)中也有流水線的概念，如圖：
在執(zhí)行指令的時候一般有以下幾個過程：
- 取指：Fetch
- 譯指：Decode
- 執(zhí)行：execute
- 回寫：Write-back
流水線架構(gòu)可以更好的壓榨流水線上的四個員工，讓他們不停的工作，使指令執(zhí)行的效率更高。
再談分支預測，舉個經(jīng)典的例子：
火車高速行駛的過程中遇到前方有個岔路口，假設(shè)火車內(nèi)沒有任何通訊手段，那火車就需要在岔路口前停下，下車詢問別人應(yīng)該選擇哪條路走，弄清楚路線后后再重新啟動火車繼續(xù)行駛。高速行駛的火車慢速停下，再重新啟動后加速，可以想象這個過程浪費了多少時間。
有個辦法，火車在遇到岔路口前可以猜一條路線，到路口時直接選擇這條路行駛，如果經(jīng)過多個岔路口，每次做出選擇時都能選擇正確的路口行駛，這樣火車一路上都不需要減速，速度自然非常快。但如果火車開過頭才發(fā)現(xiàn)走錯路了，就需要倒車回到岔路口，選擇正確的路口繼續(xù)行駛，速度自然下降很多。所以預測的成功率非常重要，因為預測失敗的代價較高，預測成功則一帆風順。
計算機的分支預測就如同火車行駛中遇到了岔路口，預測成功則程序的執(zhí)行效率大幅提高，預測失敗程序的執(zhí)行效率則大幅下降。
CPU都是多級流水線架構(gòu)運行，如果分支預測成功，很多指令都提前進入流水線流程中，則流水線中指令運行的非常順暢，而如果分支預測失敗，則需要清空流水線中的那些預測出來的指令，重新加載正確的指令到流水線中執(zhí)行，然而現(xiàn)代CPU的流水線級數(shù)非常長，分支預測失敗會損失10-20個左右的時鐘周期，因此對于復雜的流水線，好的分支預測方法非常重要。
預測方法主要分為靜態(tài)分支預測和動態(tài)分支預測：
靜態(tài)分支預測：聽名字就知道，該策略不依賴執(zhí)行環(huán)境，編譯器在編譯時就已經(jīng)對各個分支做好了預測。
動態(tài)分支預測：即運行時預測，CPU會根據(jù)分支被選擇的歷史紀錄進行預測，如果最近多次都走了這個路口，那CPU做出預測時會優(yōu)先考慮這個路口。
tips：這里只是簡單的介紹了分支預測的方法，更多的分支預測方法資料大家可關(guān)注公眾號回復分支預測關(guān)鍵字領(lǐng)取。
了解了分支預測的概念，我們回到最開始的問題，為什么同一個程序，排序和不排序的執(zhí)行速度相差那么多。
因為程序中有個if條件判斷，對于不排序的程序，數(shù)據(jù)散亂分布，CPU進行分支預測比較困難，預測失敗的頻率較高，每次失敗都會浪費10-20個時鐘周期，影響程序運行的效率。而對于排序后的數(shù)據(jù)，CPU根據(jù)歷史記錄比較好判斷即將走哪個分支，大概前一半的數(shù)據(jù)都不會進入if分支，后一半的數(shù)據(jù)都會進入if分支，預測的成功率非常高，所以程序運行速度很快。
如何解決此問題?總體思路肯定是在程序中盡量減少分支的判斷，方法肯定是具體問題具體分析了，對于該示例程序，這里提供兩個思路削減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);
- { // 測試部分
- 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;
- }
其實Linux中有一些工具可以檢測出分支預測成功的次數(shù)，有valgrind和perf，使用方式如圖：
圖片截自下方參考資料中
條件分支的使用會影響程序執(zhí)行的效率，我們平時開發(fā)過程中應(yīng)該盡可能減少在程序中隨意使用過多的分支，能避免則避免。
更多的分支預測方法資料大家可關(guān)注公眾號回復分支預測關(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
