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

// 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）;

{ // 測(cè)試部分 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í)行時(shí)間是7.9秒，如果把排序那一行代碼注釋掉，即

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

結(jié)果為：

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

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

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

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

取指：Fetch

譯指：Decode

執(zhí)行：execute

回寫：Write-back

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

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

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

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

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

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

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

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

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

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

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

{ // 測(cè)試部分 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;}

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

圖片截自下方參考資料中

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

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

拓展閱讀：

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

想必很多人都聽說過虛函數(shù)開銷大，貌似很多答案都說是因?yàn)樘摵瘮?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í)行時(shí)間：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í)行時(shí)間：12.706s

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

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

#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）; // 這里有改動(dòng) } cout 《《 ai 《《 endl;}

執(zhí)行時(shí)間：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）; // 這里有改動(dòng) } cout 《《 ai 《《 endl;}

執(zhí)行時(shí)間154ms

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

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

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

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

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

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

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

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

入棧返回地址；

跳轉(zhuǎn)到函數(shù)的代碼，這是一個(gè)編譯時(shí)地址，因?yàn)榫幾g器/鏈接器硬編碼為二進(jìn)制；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

責(zé)任編輯：haq