首先看一段经典的代码，并统计它的执行时间：

1. 
   
2. // test_predict.cc
   8 X2 M5 c0 u- ~4 L% \
3. #include <algorithm>
   9 \! y4 I+ j; f# Y# \+ A2 l: c
4. #include <ctime>
   
5. #include <iostream>
   , |! ^0 R3 d  ?+ Q9 b7 d8 K, k
6. 
   
7. int main() {
   
8.     const unsigned ARRAY_SIZE = 50000;
   9 j& z$ B5 Z, d$ }; R& X7 I2 O
9.     int data[ARRAY_SIZE];
   
10.     const unsigned DATA_STRIDE = 256;
    + o5 D. m+ J) U( C8 ]) y
11. 
    
12.     for (unsigned c = 0; c < ARRAY_SIZE; ++c) data[c] = std::rand() % DATA_STRIDE;
    
13. 
    
14.     std::sort(data, data + ARRAY_SIZE);
    
15. 
    ; e' N" w3 P& D! X1 D! ?
16.     {  // 测试部分
    0 q( S2 I; I) ^6 F7 L5 S
17.         clock_t start = clock();
    
18.         long long sum = 0;
    4 j( l+ x# e$ P; p# X
19. 
    
20.         for (unsigned i = 0; i < 100000; ++i) {
      w. G+ |! R  f# e
21.             for (unsigned c = 0; c < ARRAY_SIZE; ++c) {
    
22.                 if (data[c] >= 128) sum += data[c];
      d. ~! `+ D: g$ }2 G
23.             }
    
24.         }
    
25. 
    
26.         double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
    
27. 
    
28.         std::cout << elapsedTime << "\n";
    6 p' h# O' ]3 Q
29.         std::cout << "sum = " << sum << "\n";
    
30.     }
    & O; [2 L' p/ |* G6 M
31.     return 0;
    
32. }
    2 k" r% i$ w( F( {3 a
33. ~/test$ g++ test_predict.cc ;./a.out
    
34. 7.95312
    * u5 R4 m, H; U8 a9 y9 G
35. sum = 480124300000

复制代码

此程序的执行时间是7.9秒，如果把排序那一行代码注释掉，即

1. 
   ' q8 M+ [$ }* l5 k7 T. ^
2. // std::sort(data, data + ARRAY_SIZE);

复制代码

% V6 g' i- f  {  ~

结果为：
0 V% {: E8 Q' {" i6 D

1. 
   
2. ~/test$ g++ test_predict.cc ;./a.out
   4 S" @* ]' n- X
3. 24.2188
   $ M# Z4 X7 S) T% _- V
4. sum = 480124300000

复制代码

改动后的程序执行时间变为了24秒。

* J; M1 S1 D" M9 E8 h: a

其实只改动了一行代码，程序执行时间却有3倍的差距，而且看上去数组是否排序与程序执行速度貌似没什么关系，这里面其实涉及到CPU分支预测的知识点。

提到分支预测，首先要介绍一个概念：流水线。

拿理发举例，小理发店一般都是一个人工作，一个人洗剪吹一肩挑，而大理发店分工明确，洗剪吹都有特定的员工，第一个人在剪发的时候，第二个人就可以洗头了，第一个人剪发结束吹头发的时候，第二个人可以去剪发，第三个人就可以去洗头了，极大的提高了效率。

这里的洗剪吹就相当于是三级流水线，在CPU架构中也有流水线的概念，如图：

在执行指令的时候一般有以下几个过程：

• 取指：Fetch
• 译指：Decode
• 执行：execute
• 回写：Write-back
  
    J7 t5 r8 J, N

6 v0 Y  L" ?6 ^* Z, X* [2 e2 R5 P4 S

流水线架构可以更好的压榨流水线上的四个员工，让他们不停的工作，使指令执行的效率更高。

再谈分支预测，举个经典的例子：

* c( V1 F( V. k" ?/ J8 u6 |

火车高速行驶的过程中遇到前方有个岔路口，假设火车内没有任何通讯手段，那火车就需要在岔路口前停下，下车询问别人应该选择哪条路走，弄清楚路线后后再重新启动火车继续行驶。高速行驶的火车慢速停下，再重新启动后加速，可以想象这个过程浪费了多少时间。

有个办法，火车在遇到岔路口前可以猜一条路线，到路口时直接选择这条路行驶，如果经过多个岔路口，每次做出选择时都能选择正确的路口行驶，这样火车一路上都不需要减速，速度自然非常快。但如果火车开过头才发现走错路了，就需要倒车回到岔路口，选择正确的路口继续行驶，速度自然下降很多。所以预测的成功率非常重要，因为预测失败的代价较高，预测成功则一帆风顺。

0 l9 c  k0 `6 P3 I- K

计算机的分支预测就如同火车行驶中遇到了岔路口，预测成功则程序的执行效率大幅提高，预测失败程序的执行效率则大幅下降。

CPU都是多级流水线架构运行，如果分支预测成功，很多指令都提前进入流水线流程中，则流水线中指令运行的非常顺畅，而如果分支预测失败，则需要清空流水线中的那些预测出来的指令，重新加载正确的指令到流水线中执行，然而现代CPU的流水线级数非常长，分支预测失败会损失10-20个左右的时钟周期，因此对于复杂的流水线，好的分支预测方法非常重要。

' j5 y) r- {3 d% I

预测方法主要分为静态分支预测和动态分支预测：

静态分支预测：听名字就知道，该策略不依赖执行环境，编译器在编译时就已经对各个分支做好了预测。

动态分支预测：即运行时预测，CPU会根据分支被选择的历史纪录进行预测，如果最近多次都走了这个路口，那CPU做出预测时会优先考虑这个路口。

, }; A3 ]5 `9 n& j. H) E$ e$ u: ~

tips：这里只是简单的介绍了分支预测的方法，更多的分支预测方法资料大家可关注公众号回复分支预测关键字领取。

% T1 T; A9 P7 n; d

了解了分支预测的概念，我们回到最开始的问题，为什么同一个程序，排序和不排序的执行速度相差那么多。

因为程序中有个if条件判断，对于不排序的程序，数据散乱分布，CPU进行分支预测比较困难，预测失败的频率较高，每次失败都会浪费10-20个时钟周期，影响程序运行的效率。而对于排序后的数据，CPU根据历史记录比较好判断即将走哪个分支，大概前一半的数据都不会进入if分支，后一半的数据都会进入if分支，预测的成功率非常高，所以程序运行速度很快。

如何解决此问题？总体思路肯定是在程序中尽量减少分支的判断，方法肯定是具体问题具体分析了，对于该示例程序，这里提供两个思路削减if分支。

方法一：使用位操作：

1. 
   
2. int t = (data[c] - 128) >> 31;
   4 v! Z' I4 T, K0 r/ ?0 r' V
3. sum += ~t & data[c];

复制代码

方法二：使用表结构：

1. 
   ' |" y' ]8 b" z! X& Z! c
2. #include <algorithm>
   # G* A" z" f9 R& H# C; [1 j5 U
3. #include <ctime>
   
4. #include <iostream>
   & j  Z% N; d  k" O) Z2 e. g
5. 
   
6. int main() {
   
7.     const unsigned ARRAY_SIZE = 50000;
   7 z! w" X, C; P. v4 R
8.     int data[ARRAY_SIZE];
   + b; O( t+ C; m& f
9.     const unsigned DATA_STRIDE = 256;
   . s! t6 z/ c4 G6 d2 Y7 T$ K8 @
10. 
    
11.     for (unsigned c = 0; c < ARRAY_SIZE; ++c) data[c] = std::rand() % DATA_STRIDE;
    ' X4 ]# v) {% `; X' ^) k
12. 
    
13.     int lookup[DATA_STRIDE];
    1 V' X7 h  J9 _1 j+ ?# J
14.     for (unsigned c = 0; c < DATA_STRIDE; ++c) {
    
15.         lookup[c] = (c >= 128) ? c : 0;
    
16.     }
    5 Q9 D: H) A5 a: Z8 A9 \
17. 
    9 g) c% i, O3 c( D  W
18.     std::sort(data, data + ARRAY_SIZE);
    
19. 
    
20.     {  // 测试部分
    3 V/ \8 E5 F$ w7 X+ D9 k
21.         clock_t start = clock();
    
22.         long long sum = 0;
    
23. 
    3 \' n' H7 T1 d" D
24.         for (unsigned i = 0; i < 100000; ++i) {
    
25.             for (unsigned c = 0; c < ARRAY_SIZE; ++c) {
    % J, E& U; \! O  h- F
26.                 // if (data[c] >= 128) sum += data[c];
    
27.                 sum += lookup[data[c]];
    
28.             }
    
29.         }
    ! h; K4 O9 J5 U
30. 
    7 J; O3 f1 Y/ i, i1 w
31.         double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
    
32.         std::cout << elapsedTime << "\n";
    & r( k. r. y4 r7 y, ?$ s
33.         std::cout << "sum = " << sum << "\n";
    
34.     }
    
35.     return 0;
    * U/ p! u  E) d2 m* K1 T
36. }

复制代码

. A: N0 H% y1 G  I& g

其实Linux中有一些工具可以检测出分支预测成功的次数，有valgrind和perf，使用方式如图：

图片截自下方参考资料中
# a/ }2 X2 W; m# W

条件分支的使用会影响程序执行的效率，我们平时开发过程中应该尽可能减少在程序中随意使用过多的分支，能避免则避免。

更多的分支预测方法资料大家可关注公众号回复分支预测关键字领取。

" [4 D3 L" t' a3 {; W9 \1 ]/ A# d; L

拓展阅读：

《虚函数真的就那么慢吗？它的开销究竟在哪里？来看这4段代码！》

) w) P9 g* S$ n3 }6 {& x1 o; V! Y& L

想必很多人都听说过虚函数开销大，貌似很多答案都说是因为虚函数表导致的那一次间接调用，真的如此吗？

, b( H) w" c. r2 Z. b8 L

直接看下面这两段代码：

1. 
   
2. #include <cmath>
   
3. #include "timer.h"
   
4. struct Base {
   
5.    public:
   - w! p$ }0 y, W
6.     virtual int f(double i1, int i2) { return static_cast<int>(i1 * log(i1)) * i2; }
   - e! U$ D* b8 N8 S! G7 Q. S1 F; H
7. };
   ! F9 ]3 F! h' p; d
8. 
   
9. int main() {
   
10.     TimerLog t("timer");
    
11.     Base *a = new Base();
    
12.     int ai = 0;
    
13.     for (int i = 0; i < 1000000000; i++) {
    
14.         ai += a->f(i, 10);
    
15.     }
    7 o0 R; v) Y6 _
16.     cout << ai << endl;
    $ @9 x, s$ a" e- U
17. }

复制代码

执行时间：12.895s

1. 
   
2. #include <cmath>
   
3. #include "timer.h"
     [& V/ o4 T& h/ L6 i. g
4. struct Base {
   
5.    public:
   
6.     int f(double i1, int i2) { return static_cast<int>(i1 * log(i1)) * i2; }
   
7. };
   
8. 
   3 w, D6 \( X( q' X! D8 a  c
9. int main() {
   4 \& t2 Z* j( m& w3 c1 ~
10.     TimerLog t("timer");
    
11.     Base *a = new Base();
    
12.     int ai = 0;
    
13.     for (int i = 0; i < 1000000000; i++) {
    4 U- z4 J/ e" `
14.         ai += a->f(i, 10);
    ( Q& Q  f: }1 K0 ?2 `
15.     }
    : _" D6 |9 r+ e7 b/ T5 N! R. r
16.     cout << ai << endl;
    ! u, ^/ \+ z5 ~/ e+ U
17. }
    

复制代码

* h8 T- F9 H. L# j

执行时间：12.706s

这两段代码的执行时间几乎没有区别，可见虚函数表导致的那一次函数间接调用并不浪费时间，所以虚函数的开销并不在重定向上，这一次重定向基本上不影响程序性能。

那它的开销究竟在哪里呢？看下面两段代码，这两段代码和上面相比只改动了一行：

1. 
   5 y$ e) }+ E) e1 U% i) F
2. #include <cmath>
   : d. W9 u& Z9 {6 f: k8 R+ }3 c
3. #include "timer.h"
   7 ]/ J2 I- J: p% v& w2 x
4. struct Base {
   
5.    public:
   , ^5 Z" U% }5 ?% I/ G
6.     virtual int f(double i1, int i2) { return static_cast<int>(i1 * log(i1)) * i2; }
   5 x( _0 E$ Y# Z1 C5 P  Y! G
7. };
   
8. 
   . h5 H9 F9 d7 L& K7 `. S
9. int main() {
   
10.     TimerLog t("timer");
    
11.     Base *a = new Base();
    
12.     int ai = 0;
    # c- ?1 a" ?4 s2 u( V* P( m
13.     for (int i = 0; i < 1000000000; i++) {
    % O8 X3 `! `) N% Z
14.         ai += a->f(10, i); // 这里有改动
    ( K4 I' [0 g5 [, v( u
15.     }
    ! U' I' @9 i% w/ H% g
16.     cout << ai << endl;
    
17. }

复制代码

1 [$ n- t5 P( g; }) i  |* S

执行时间：436ms

1. 
   3 @* U* M1 c& Z" C$ u% w% x2 R0 M
2. #include <cmath>
   2 y# g: |6 D& @8 G! f
3. #include "timer.h"
   + T5 Q. g2 v) y1 N* D1 {, |& x" `
4. struct Base {
   
5.    public:
   
6.     int f(double i1, int i2) { return static_cast<int>(i1 * log(i1)) * i2; }
   
7. };
   # G4 w- T2 S6 a  f1 o
8. 
   . a, h  b; U. a  D5 S
9. int main() {
   
10.     TimerLog t("timer");
    9 n. e! _! |% ^9 G4 W. u* c+ d
11.     Base *a = new Base();
    
12.     int ai = 0;
    3 y' R, A& e3 C5 z
13.     for (int i = 0; i < 1000000000; i++) {
    
14.         ai += a->f(10, i); // 这里有改动
    
15.     }
    8 t, {. d0 K# u, q
16.     cout << ai << endl;
    
17. }

复制代码

执行时间154ms

* _3 g, p4 d( z

这里看到，仅仅改变了一行代码，虚函数调用就比普通函数慢了几倍，为什么？

6 Q  z/ F. k) H0 }3 G, W4 d: i

虚函数其实最主要的性能开销在于它阻碍了编译器内联函数和各种函数级别的优化，导致性能开销较大，在普通函数中log(10)会被优化掉，它就只会被计算一次，而如果使用虚函数，log(10)不会被编译器优化，它就会被计算多次。如果代码中使用了更多的虚函数，编译器能优化的代码就越少，性能就越低。

虚函数通常通过虚函数表来实现，在虚表中存储函数指针，实际调用时需要间接访问，这需要多一点时间。

8 s5 Z9 U) v" L5 D# J1 K# s1 E

然而这并不是虚函数速度慢的主要原因，真正原因是编译器在编译时通常并不知道它将要调用哪个函数，所以它不能被内联优化和其它很多优化，因此就会增加很多无意义的指令（准备寄存器、调用函数、保存状态等），而且如果虚函数有很多实现方法，那分支预测的成功率也会降低很多，分支预测错误也会导致程序性能下降。

1 `' @, Q7 T) G+ b2 q. H+ O

如果你想要写出高性能代码并频繁的调用虚函数，注意如果用其它的方式（例如if-else、switch、函数指针等）来替换虚函数调用并不能根本解决问题，它还有可能会更慢，真正的问题不是虚函数，而是那些不必要的间接调用。

正常的函数调用：

• 复制栈上的一些寄存器，以允许被调用的函数使用这些寄存器；
  * P8 Y3 f5 p( ?2 x% @3 l. @5 C
• 将参数复制到预定义的位置，这样被调用的函数可以找到对应参数；
• 入栈返回地址；
• 跳转到函数的代码，这是一个编译时地址，因为编译器/链接器硬编码为二进制；
• 从预定义的位置获取返回值，并恢复想要使用的寄存器。
  
  

而虚函数调用与此完全相同，唯一的区别就是编译时不知道函数的地址，而是：

• 从对象中获取虚表指针，该指针指向一个函数指针数组，每个指针对应一个虚函数；
  
• 从虚表中获取正确的函数地址，放到寄存器中；
• 跳转到该寄存器中的地址，而不是跳转到一个硬编码的地址。
  
  ' _9 y$ Q, t) `; \, ~, e9 N

通常，使用虚函数没问题，它的性能开销也不大，而且虚函数在面向对象代码中有强大的作用。
0 f  ^5 }1 M+ D

/ r  Q/ U+ Z" _

但是不能无脑使用虚函数，特别是在性能至关重要的或者底层代码中，而且大项目中使用多态也会导致继承层次很混乱。

那么有什么好方法替代虚函数呢？这里提供几个思路，读者请持续关注，后续会具体讲解：

• 使用访问者模式来使类层次结构可扩展；
• 使用普通模板替代继承和虚函数；
• C++20中的concepts用来替代面向对象代码；
• 使用variants替代虚函数或模板方法。
  
  

这几种方法是Michael Spertus大佬介绍的，各有各的优缺点，作者都会用，但什么情况下使用哪个，取决于你自己的判断，这里只是教你了一个工具，什么时候用都取决于你自己。

这个知识点有点强悍

过于强悍了