首先看一段經(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 《《 “

”; std：：cout 《《 “sum = ” 《《 sum 《《 “

”; } return 0;}~/test$ g++ test_predict.cc ;。/a.out7.95312sum = 480124300000

此程序的執(zhí)行時間是7.9秒，如果把排序那一行代碼注釋掉，即

// std：：sort（data， data + ARRAY_SIZE）;

結(jié)果為：

~/test$ g++ test_predict.cc ;。/a.out24.2188sum = 480124300000

改動后的程序執(zhí)行時間變?yōu)榱?4秒。

其實只改動了一行代碼，程序執(zhí)行時間卻有3倍的差距，而且看上去數(shù)組是否排序與程序執(zhí)行速度貌似沒什么關(guān)系，這里面其實涉及到CPU分支預(yù)測的知識點。

提到分支預(yù)測，首先要介紹一個概念：流水線。

拿理發(fā)舉例，小理發(fā)店一般都是一個人工作，一個人洗剪吹一肩挑，而大理發(fā)店分工明確，洗剪吹都有特定的員工，第一個人在剪發(fā)的時候，第二個人就可以洗頭了，第一個人剪發(fā)結(jié)束吹頭發(fā)的時候，第二個人可以去剪發(fā)，第三個人就可以去洗頭了，極大的提高了效率。

這里的洗剪吹就相當(dāng)于是三級流水線，在CPU架構(gòu)中也有流水線的概念，如圖：

在執(zhí)行指令的時候一般有以下幾個過程：

取指：Fetch

譯指：Decode

執(zhí)行：execute

回寫：Write-back

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

再談分支預(yù)測，舉個經(jīng)典的例子：

火車高速行駛的過程中遇到前方有個岔路口，假設(shè)火車內(nèi)沒有任何通訊手段，那火車就需要在岔路口前停下，下車詢問別人應(yīng)該選擇哪條路走，弄清楚路線后后再重新啟動火車?yán)^續(xù)行駛。高速行駛的火車慢速停下，再重新啟動后加速，可以想象這個過程浪費了多少時間。

有個辦法，火車在遇到岔路口前可以猜一條路線，到路口時直接選擇這條路行駛，如果經(jīng)過多個岔路口，每次做出選擇時都能選擇正確的路口行駛，這樣火車一路上都不需要減速，速度自然非常快。但如果火車開過頭才發(fā)現(xiàn)走錯路了，就需要倒車回到岔路口，選擇正確的路口繼續(xù)行駛，速度自然下降很多。所以預(yù)測的成功率非常重要，因為預(yù)測失敗的代價較高，預(yù)測成功則一帆風(fēng)順。

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

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

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

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

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

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

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

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

如何解決此問題？總體思路肯定是在程序中盡量減少分支的判斷，方法肯定是具體問題具體分析了，對于該示例程序，這里提供兩個思路削減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 《《 “

”; std：：cout 《《 “sum = ” 《《 sum 《《 “

”; } return 0;}

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

圖片截自下方參考資料中

條件分支的使用會影響程序執(zhí)行的效率，我們平時開發(fā)過程中應(yīng)該盡可能減少在程序中隨意使用過多的分支，能避免則避免。

更多的分支預(yù)測方法資料大家可關(guān)注公眾號回復(fù)分支預(yù)測關(guān)鍵字領(lǐng)取。

拓展閱讀：

《虛函數(shù)真的就那么慢嗎？它的開銷究竟在哪里？來看這4段代碼！》

想必很多人都聽說過虛函數(shù)開銷大，貌似很多答案都說是因為虛函數(shù)表導(dǎo)致的那一次間接調(diào)用，真的如此嗎？

直接看下面這兩段代碼：

#include 《cmath》#include “timer.h”struct Base { public： virtual int f（double i1， int i2） { return static_cast《int》（i1 * log（i1）） * i2; }};

int main（） { TimerLog t（“timer”）; Base *a = new Base（）; int ai = 0; for （int i = 0; i 《 1000000000; i++） { ai += a-》f（i， 10）; } cout 《《 ai 《《 endl;}

執(zhí)行時間：12.895s

#include 《cmath》#include “timer.h”struct Base { public： int f（double i1， int i2） { return static_cast《int》（i1 * log（i1）） * i2; }};

int main（） { TimerLog t（“timer”）; Base *a = new Base（）; int ai = 0; for （int i = 0; i 《 1000000000; i++） { ai += a-》f（i， 10）; } cout 《《 ai 《《 endl;}

執(zhí)行時間：12.706s

這兩段代碼的執(zhí)行時間幾乎沒有區(qū)別，可見虛函數(shù)表導(dǎo)致的那一次函數(shù)間接調(diào)用并不浪費時間，所以虛函數(shù)的開銷并不在重定向上，這一次重定向基本上不影響程序性能。

那它的開銷究竟在哪里呢？看下面兩段代碼，這兩段代碼和上面相比只改動了一行：

#include 《cmath》#include “timer.h”struct Base { public： virtual int f（double i1， int i2） { return static_cast《int》（i1 * log（i1）） * i2; }};

int main（） { TimerLog t（“timer”）; Base *a = new Base（）; int ai = 0; for （int i = 0; i 《 1000000000; i++） { ai += a-》f（10， i）; // 這里有改動 } cout 《《 ai 《《 endl;}

執(zhí)行時間：436ms

#include 《cmath》#include “timer.h”struct Base { public： int f（double i1， int i2） { return static_cast《int》（i1 * log（i1）） * i2; }};

int main（） { TimerLog t（“timer”）; Base *a = new Base（）; int ai = 0; for （int i = 0; i 《 1000000000; i++） { ai += a-》f（10， i）; // 這里有改動 } cout 《《 ai 《《 endl;}

執(zhí)行時間154ms

這里看到，僅僅改變了一行代碼，虛函數(shù)調(diào)用就比普通函數(shù)慢了幾倍，為什么？

虛函數(shù)其實最主要的性能開銷在于它阻礙了編譯器內(nèi)聯(lián)函數(shù)和各種函數(shù)級別的優(yōu)化，導(dǎo)致性能開銷較大，在普通函數(shù)中l(wèi)og（10）會被優(yōu)化掉，它就只會被計算一次，而如果使用虛函數(shù)，log（10）不會被編譯器優(yōu)化，它就會被計算多次。如果代碼中使用了更多的虛函數(shù)，編譯器能優(yōu)化的代碼就越少，性能就越低。

虛函數(shù)通常通過虛函數(shù)表來實現(xiàn)，在虛表中存儲函數(shù)指針，實際調(diào)用時需要間接訪問，這需要多一點時間。

然而這并不是虛函數(shù)速度慢的主要原因，真正原因是編譯器在編譯時通常并不知道它將要調(diào)用哪個函數(shù)，所以它不能被內(nèi)聯(lián)優(yōu)化和其它很多優(yōu)化，因此就會增加很多無意義的指令（準(zhǔn)備寄存器、調(diào)用函數(shù)、保存狀態(tài)等），而且如果虛函數(shù)有很多實現(xiàn)方法，那分支預(yù)測的成功率也會降低很多，分支預(yù)測錯誤也會導(dǎo)致程序性能下降。

如果你想要寫出高性能代碼并頻繁的調(diào)用虛函數(shù)，注意如果用其它的方式（例如if-else、switch、函數(shù)指針等）來替換虛函數(shù)調(diào)用并不能根本解決問題，它還有可能會更慢，真正的問題不是虛函數(shù)，而是那些不必要的間接調(diào)用。

正常的函數(shù)調(diào)用：

復(fù)制棧上的一些寄存器，以允許被調(diào)用的函數(shù)使用這些寄存器；

將參數(shù)復(fù)制到預(yù)定義的位置，這樣被調(diào)用的函數(shù)可以找到對應(yīng)參數(shù)；

入棧返回地址；

跳轉(zhuǎn)到函數(shù)的代碼，這是一個編譯時地址，因為編譯器/鏈接器硬編碼為二進制；

從預(yù)定義的位置獲取返回值，并恢復(fù)想要使用的寄存器。

而虛函數(shù)調(diào)用與此完全相同，唯一的區(qū)別就是編譯時不知道函數(shù)的地址，而是：

從對象中獲取虛表指針，該指針指向一個函數(shù)指針數(shù)組，每個指針對應(yīng)一個虛函數(shù)；

從虛表中獲取正確的函數(shù)地址，放到寄存器中；

跳轉(zhuǎn)到該寄存器中的地址，而不是跳轉(zhuǎn)到一個硬編碼的地址。

通常，使用虛函數(shù)沒問題，它的性能開銷也不大，而且虛函數(shù)在面向?qū)ο蟠a中有強大的作用。

但是不能無腦使用虛函數(shù)，特別是在性能至關(guān)重要的或者底層代碼中，而且大項目中使用多態(tài)也會導(dǎo)致繼承層次很混亂。

那么有什么好方法替代虛函數(shù)呢？這里提供幾個思路，讀者請持續(xù)關(guān)注，后續(xù)會具體講解：

使用訪問者模式來使類層次結(jié)構(gòu)可擴展；

使用普通模板替代繼承和虛函數(shù)；

C++20中的concepts用來替代面向?qū)ο蟠a；

使用variants替代虛函數(shù)或模板方法。

這幾種方法是Michael Spertus大佬介紹的，各有各的優(yōu)缺點，作者都會用，但什么情況下使用哪個，取決于你自己的判斷，這里只是教你了一個工具，什么時候用都取決于你自己。

原文標(biāo)題：少寫點if-else吧，它的效率有多低你知道嗎？

文章出處：【微信公眾號：嵌入式ARM】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。

責(zé)任編輯：haq