我们写程序的目的就是使它在任何情况下都可以稳定工作。一个运行的很快但是结果错误的程序并没有任何用处。在程序开发和优化的过程中，我们必须考虑代码使用的方式，以及影响它的关键因素。通常，我们必须在程序的简洁性与它的运行速度之间做出权衡。今天我们就来聊一聊如何优化程序的性能。

• 1. 减小程序计算量
  
  6 J) Z! {. @; X7 z3 [  H7 K0 n# o
  • 1.1 示例代码
  • 1.2 分析代码
  • 1.3 改进代码
    
    ) H, k3 o( n* ]1 T' c3 X) e" u  e0 C
• 2. 提取代码中的公共部分
  
  2 b9 u' b0 B# t; Y. `- Z- \% H
  • 2.1 示例代码
  • 2.2 分析代码
  • 2.3 改进代码
    
    1 _5 i% b; d" D9 Q2 _
• 3. 消除循环中低效代码
  
  . W4 |% q& B  k9 l  W. f% T
  • 3.1 示例代码
  • 3.2 分析代码
  • 3.3 改进代码
    
    
• 4. 消除不必要的内存引用
  
  - E. J8 Q; q) ?
  • 4.1 示例代码
  • 4.2 分析代码
  • 4.3 改进代码
    
    
• 5.  减小不必要的调用
  
  
  • 5.1 示例代码
  • 5.2 分析代码
  • 5.3 改进代码
    
    1 _, a/ K% n9 n7 h, N: z# F
• 6. 循环展开
  
  
  • 6.1 示例代码
  • 6.2 分析代码
  • 6.3 改进代码
    
    , p, p& l& W$ }1 B9 M, Z
• 7. 累计变量，多路并行
  
  1 }7 n# ~& N6 W$ c
  • 7.1 示例代码
  • 7.2 分析代码
  • 7.3 改进代码
    
    
• 8. 重新结合变换
  
  
  • 8.1 示例代码
  • 8.2 分析代码
  • 8.3 改进代码
    
    
• 9 条件传送风格的代码
  
  
  • 9.1 示例代码
  • 9.2 分析代码
  • 9.3 改进代码
    
    . I  l$ M! t6 Y8 S/ ~* h8 n1 Y  u
• 10. 总结
  
  9 P0 l2 @: A: n2 ^7 u$ C8 Q+ E" }) x

1. 减小程序计算量1.1 示例代码
" O8 X- t; A0 Mfor (i = 0; i < n; i++) {
/ ]  H0 d  z7 W) y  int ni = n*i;
! C7 j, x7 k/ F  for (j = 0; j < n; j++)
    a[ni + j] = b[j];
$ q8 H' R; J# H8 d, G8 H* p}
1.2 分析代码

  代码如上所示，外循环每执行一次，我们要进行一次乘法计算。i = 0，ni = 0；i = 1，ni = n；i = 2，ni = 2n。因此，我们可以把乘法换成加法，以n为步长，这样就减小了外循环的代码量。

1.3 改进代码
3 ~3 v! n, @. p8 G5 \: iint ni = 0;
for (i = 0; i < n; i++) {
  for (j = 0; j < n; j++)
    a[ni + j] = b[j];
  ni += n;         //乘法改加法
}

计算机中乘法指令要比加法指令慢得多。

2. 提取代码中的公共部分
2.1 示例代码

  想象一下，我们有一个图像，我们把图像表示为二维数组，数组元素代表像素点。我们想要得到给定像素的东、南、西、北四个邻居的总和。并求他们的平均值或他们的和。代码如下所示。

up =    val[(i-1)*n + j  ];
down =  val[(i+1)*n + j  ];
) E; R( f5 |2 f/ F( E" uleft =  val[i*n     + j-1];
right = val[i*n     + j+1];
2 }0 S) U2 X6 y7 r+ y$ _: Qsum = up + down + left + right;
2.2 分析代码

  将以上代码编译后得到汇编代码如下所示，注意下3,4,5行，有三个乘以n的乘法运算。我们把上面的up和down展开后会发现四格表达式中都有i*n + j。因此，可以提取出公共部分，再通过加减运算分别得出up、down等的值。

leaq   1(%rsi), %rax  # i+1
, y7 {: y+ |- y5 V0 }9 nleaq   -1(%rsi), %r8  # i-1
imulq  %rcx, %rsi     # i*n
2 k5 Y% B- U7 B" X4 w- T1 cimulq  %rcx, %rax     # (i+1)*n
imulq  %rcx, %r8      # (i-1)*n
addq   %rdx, %rsi     # i*n+j
addq   %rdx, %rax     # (i+1)*n+j
addq   %rdx, %r8      # (i-1)*n+j
7 M" g* G' k; p( t& o2.3 改进代码
long inj = i*n + j;
; J: U) b; C7 g3 G7 Lup =    val[inj - n];
' O4 T# M3 p! G1 Y% ?down =  val[inj + n];
left =  val[inj - 1];
& b" Z5 C% R$ N& w  u* Z7 ~right = val[inj + 1];
sum = up + down + left + right;
! i- X  [: W: `5 c

  改进后的代码的汇编如下所示。编译后只有一个乘法。减少了6个时钟周期（一个乘法周期大约为3个时钟周期）。

imulq %rcx, %rsi  # i*n
addq %rdx, %rsi  # i*n+j
movq %rsi, %rax  # i*n+j
/ p. Y' h0 l1 P. l; [' Ysubq %rcx, %rax  # i*n+j-n
leaq (%rsi,%rcx), %rcx # i*n+j+n
+ e, }6 ]2 g# Q3 d0 n3 ^' z, ?- Y...

  对于GCC编译器来说，编译器可以根据不同的优化等级，有不同的优化方式，会自动完成以上的优化操作。下面我们介绍下，那些必须是我们要手动优化的。

3. 消除循环中低效代码
3.1 示例代码

  程序看起来没什么问题，一个很平常的大小写转换的代码，但是为什么随着字符串输入长度的变长，代码的执行时间会呈指数式增长呢？

void lower1(char *s)
{
  size_t i;
  for (i = 0; i < strlen(s); i++)
8 [; n* [& s# X: ?' C6 m. n( @    if (s >= 'A' && s <= 'Z')
      s -= ('A' - 'a');
}
3.2 分析代码

  那么我们就测试下代码，输入一系列字符串。

lower1代码性能测试

  当输入字符串长度低于100000时，程序运行时间差别不大。但是，随着字符串长度的增加，程序的运行时间呈指数时增长。

  我们把代码转换成goto形式看下。

void lower1(char *s)
{
" s2 s6 B  R/ a, w. u7 V0 a   size_t i = 0;
( E4 r; c% H* s, \; K) l   if (i >= strlen(s))
4 A/ L5 U4 h! M" g$ Q% r" @     goto done;
loop:
   if (s >= 'A' && s <= 'Z')
/ o0 A; M2 D4 R% x$ B9 u0 _       s -= ('A' - 'a');
   i++;
   if (i < strlen(s))
     goto loop;
% G, R$ I/ \5 }* [. g/ n done:
}

8 _0 L0 f8 H7 r& h% t

  以上代码分为初始化（第3行），测试（第4行），更新（第9，10行）三部分。初始化只会执行一次。但是测试和更新每次都会执行。每进行一次循环，都会对strlen调用一次。

  下面我们看下strlen函数的源码是如何计算字符串长度的。

size_t strlen(const char *s)
{
    size_t length = 0;
8 a- ]9 }- n% z- w7 V' N; ]    while (*s != '\0') {
s++;
7 q* _4 r$ z1 v7 b* F) V length++;
    }
    return length;
* a+ {! w0 ^, t}
9 x$ e# p& l; c3 C

  strlen函数计算字符串长度的原理为：遍历字符串，直到遇到‘\0’才会停止。因此，strlen函数的时间复杂度为O（N）。lower1中，对于长度为N的字符串来说，strlen 的调用次数为N,N-1,N-2 ... 1。对于一个线性时间的函数调用N次，其时间复杂度接近于O（N2）。

3.3 改进代码

  对于循环中出现的这种冗余调用，我们可以将其移动到循环外。将计算结果用于循环中。改进后的代码如下所示。

void lower2(char *s)
{
/ z9 E3 L: C& v, F  r  size_t i;
4 k! y2 C9 ^( v% A7 B+ c  size_t len = strlen(s);
  for (i = 0; i < len; i++)
    if (s >= 'A' && s <= 'Z')
      s -= ('A' - 'a');
}
# W3 `# a, ]0 P. w  D; c

  将两个函数对比下，如下图所示。lower2函数的执行时间得到明显提升。

lower1和lower2代码效率
. R+ J+ Y5 k8 c% s7 Y! x0 V# S7 |

4. 消除不必要的内存引用
4.1 示例代码

  以下代码作用为，计算a数组中每一行所有元素的和存在b中。

void sum_rows1(double *a, double *b, long n) {
    long i, j;
    for (i = 0; i < n; i++) {
b = 0;
for (j = 0; j < n; j++)
! l  m0 ?( v4 P$ _8 i. c+ l     b += a[i*n + j];
    }
! b0 |. B  ?9 E6 q" h}
1 Q" Z  p( {2 w7 S% T7 C. C" U  Y5 U( c4.2 分析代码

  汇编代码如下所示。

# sum_rows1 inner loop
.L4:
+ N$ |) T% Z" i* }8 }        movsd   (%rsi,%rax,8), %xmm0 # 从内存中读取某个值放到%xmm0
        addsd   (%rdi), %xmm0      # %xmm0 加上某个值
        movsd   %xmm0, (%rsi,%rax,8) # %xmm0 的值写回内存，其实就是b
        addq    $8, %rdi
        cmpq    %rcx, %rdi
        jne     .L4

  这意味着每次循环都需要从内存中读取b，然后再把b写回内存 。b +=  b + a[i*n + j]; 其实每次循环开始的时候，b就是上一次的值。为什么每次都要从内存中读取出来再写回呢？

4.3 改进代码
/* Sum rows is of n X n matrix a
   and store in vector b  */
void sum_rows2(double *a, double *b, long n) {
    long i, j;
3 R' g( X- u, z! G  x    for (i = 0; i < n; i++) {
' i! A, u' K- \+ z8 U1 U double val = 0;
for (j = 0; j < n; j++)
     val += a[i*n + j];
" J8 e0 D  ~. ]' V7 a* v; g+ u         b = val;
/ C' I5 o7 b8 x" s6 E9 M    }
- W8 b1 e' \2 y- I9 J2 A}

! q. B! x) }. H4 b+ Y  e* C

  汇编如下所示。

# sum_rows2 inner loop
1 e9 C! r7 B, c* L4 e: T1 S.L10:
        addsd   (%rdi), %xmm0 # FP load + add
        addq    $8, %rdi
4 n+ ^1 u# @, x* M: ~0 ]        cmpq    %rax, %rdi
" b( X* G; ~+ ^* K- Y  X& C        jne     .L10
7 @0 ^  P: [" r3 a7 c# V

  改进后的代码引入了临时变量来保存中间结果，只有在最后的值计算出来时，才将结果存放到数组或全局变量中。

5.  减小不必要的调用
5.1 示例代码

  为了方便举例，我们定义一个包含数组和数组长度的结构体，主要是为了防止数组访问越界，data_t可以是int，long等类型。具体如下所示。

typedef struct{
; I% {' A8 ?# N+ L3 i size_t len;
data_t *data;  
} vec;
3 u+ P+ Z, m9 _3 D vec向量示意图

  get_vec_element函数的作用是遍历data数组中元素并存储在val中。

int get_vec_element (*vec v, size_t idx, data_t *val)
{
if (idx >= v->len)
  return 0;
*val = v->data[idx];
( a7 x0 N) u$ \5 }( I" I return 1;
}
( _, T( d2 m& @' H, Z

  我们将以以下代码为例开始一步步优化程序。

void combine1(vec_ptr v, data_t *dest)
3 h  ^. N( y: ?. e$ |, q{
$ z2 s0 U# O0 [* I1 s* `% a    long int i;
    *dest = NULL;
    for (i = 0; i < vec_length(v); i++) {
data_t val;
get_vec_element(v, i, &val);
: ~. Y1 E; p& Z( n' q *dest = *dest * val;
8 j/ J5 m0 a3 e! {/ }1 v/ x5 t    }
}
5.2 分析代码

  get_vec_element函数的作用是获取下一个元素，在get_vec_element函数中，每次循环都要与v->len作比较，防止越界。进行边界检查是个好习惯，但是每次都进行就会造成效率降低。

5.3 改进代码

  我们可以把求向量长度的代码移到循环体外，同时抽象数据类型增加一个函数get_vec_start。这个函数返回数组的起始地址。这样在循环体中就没有了函数调用，而是直接访问数组。

data_t *get_vec_start(vec_ptr v)
4 S. C- o2 c. \4 l. F8 i{
. ~0 V/ ^! r! e  L) r0 b return v-data;
}
) E* n: ~3 \" t# q# F
void combine2 (vec_ptr v, data_t *dest)
6 u5 k! _* t' I5 T3 P9 v& \{
long i;
# d, M3 J" z; ?3 Q* M/ U% u, \1 _ long length  = vec_length(v);
- Z. V; |, y) s0 Z+ S- H9 E    data_t *data = get_vec_start(v);
" Y8 w4 a* y; S: n8 X4 p *dest = NULL;
for (i=0;i < length;i++)
{
* L+ B4 [% E2 d  *dest = *dest * data;
+ i2 p  i8 N9 _ }
}
$ r0 O) V: }, O7 r: h6. 循环展开
" f* ~! a  V' f4 o7 h  s4 F6.1 示例代码

  我们在combine2的代码上进行改进。

6.2 分析代码

  循环展开是通过增加每次迭代计算的元素的数量，减少循环的迭代次数。

6.3 改进代码
% G7 j' j  `3 d" H; W9 O. }( Qvoid combine3(vec_ptr v, data_t *dest)
) H0 R& m8 T; o- x: t! F{
; C) d: w9 ]7 L) P6 K    long i;
, ~$ |! u5 q- V9 K- Y4 ~    long length = vec_length(v);
$ h$ |' X! b: x7 h- M8 s! E3 g4 ^7 a    long limit = length-1;
/ x1 a0 m. D6 C, F% f" u8 S# B    data_t *data = get_vec_start(v);
. u3 P& q2 E7 ~8 |    data_t acc = NULL;
1 Y$ O1 ?/ l! j$ ^3 B) o+ l   
: s4 l  e: A8 w' }* X    /* 一次循环处理两个元素 */
0 Z+ k( ~& J& F0 z    for (i = 0; i < limit; i+=2) {
    acc = (acc * data) * data[i+1];
$ r( g5 p4 o3 W; Z    }
/ q9 @  J: J2 s6 ?* v    /*     完成剩余数组元素的计算    */
0 F; T& P6 w% ~) w5 d    for (; i < length; i++) {
  acc = acc * data;
    }
+ p( U- A8 X. x    *dest = acc;
- A+ @! ]5 p* V}
7 @6 |+ p0 Z2 a- y- ~% C* q; _; j) K

  在改进后的代码中，第一个循环每次处理数组的两个元素。也就是每次迭代，循环索引i加2，在一次迭代中，对数组元素i和i+1使用合并运算。一般我们称这种为2×1循环展开，这种变换能减小循环开销的影响。

注意访问不要越界，正确设置limit，n个元素，一般设置界限n-1

7. 累计变量，多路并行7.1 示例代码

  我们在combine3的代码上进行改进。

7.2 分析代码

  对于一个可结合和可交换的合并运算来说，比如说整数加法或乘法，我们可以通过将一组合并运算分割成两个或更多的部分，并在最后合并结果来提高性能。

特别注意：不要轻易对浮点数进行结合。浮点数的编码格式和其他整型数等都不一样。

7.3 改进代码
void combine4(vec_ptr v, data_t *dest)
{
long i;
" g+ W' |9 K( x' G; E    long length = vec_length(v);
    long limit = length-1;
    data_t *data = get_vec_start(v);
, ]+ c+ Z! H8 P5 F) d5 v: ?    data_t acc0 = 0;
& N( X6 b8 b, E/ d% g% q    data_t acc1 = 0;
+ l% @/ ^5 k( @3 D) V8 V. X   
    /* 循环展开，并维护两个累计变量 */
: h. Z1 l. G9 k$ k3 a    for (i = 0; i < limit; i+=2) {
* t& e$ }' o- H1 n$ e  S    acc0 = acc0 * data;
/ }1 c1 f' ]! k7 ~& x5 i) y    acc1 = acc1 * data[i+1];
    }
    /*     完成剩余数组元素的计算    */
5 S# i$ I5 d6 ?) w; m" j9 @: z    for (; i < length; i++) {
& \7 v' K3 F2 D$ X! `8 S8 |  y        acc0 = acc0 * data;
9 N' W' H7 K+ y8 S1 \1 T4 L1 ~# f" O    }
5 w5 |$ N: r# `0 B& f5 G    *dest = acc0 * acc1;
: X% H  Y) u1 v, |: L}

  上述代码用了两次循环展开，以使每次迭代合并更多的元素，也使用了两路并行，将索引值为偶数的元素累积在变量acc0中，而索引值为奇数的元素累积在变量acc1中。因此，我们将其称为”2×2循环展开”。运用2×2循环展开。通过维护多个累积变量，这种方法利用了多个功能单元以及它们的流水线能力

8. 重新结合变换
( u8 Z" u6 D" [# z5 Y  j/ ]8.1 示例代码

  我们在combine3的代码上进行改进。

8.2 分析代码

  到这里其实代码的性能已经基本接近极限了，就算做再多的循环展开性能提升已经不明显了。我们需要换个思路，注意下combine3代码中第12行的代码，我们可以改变下向量元素合并的顺序（浮点数不适用）。重新结合前combine3代码的关键路径如下图所示。

combine3代码的关键路径
+ h6 y) U: c  [& r; g  D

8.3 改进代码
4 T) l# x# }  _$ j, ?void combine7(vec_ptr v, data_t *dest)
{
1 Z" _4 \" B( d$ A; z long i;
    long length = vec_length(v);
    long limit = length-1;
- M  I, [, W/ X+ f    data_t *data = get_vec_start(v);
    data_t acc = IDENT;
   
    /* Combine 2 elements at a time */
/ Q9 Q* f; J6 X& @    for (i = 0; i < limit; i+=2) {
! r3 H/ D5 h4 |   acc = acc OP (data OP data[i+1]);
$ i! O+ J9 K: Y* q5 f7 U8 L/ A5 A    }
    /* Finish any remaining elements */
    for (; i < length; i++) {
  F4 }, N  n# Z1 ?        acc = acc OP data;
    }
    *dest = acc;
2 n6 ^* _- ?3 l% h5 i}

  重新结合变换能够减少计算中关键路径上操作的数量，这种方法增加了可以并行执行的操作数量了，更好地利用功能单元的流水线能力得到更好的性能。重新结合后关键路径如下所示。

combine3重新结合后关键路径

- d$ q& s; _/ o
$ r7 t! [$ q7 U9 条件传送风格的代码
5 {) N: z2 A; H8 B3 ]" Q7 [9.1 示例代码
void minmax1(long a[],long b[],long n){
long i;
& O! Y( ]- `6 f' b# A! U" Y% M7 F for(i = 0;i,n;i++){
        if(a>b){
            long t = a;
            a = b;
            b = t;
9 O$ Y2 r! k: s# B6 W* C# |        }
" ^: {( {8 }1 S: v: n   }
}
( {8 ^8 L5 X/ d' r7 Q3 _4 G6 j5 B  D9.2 分析代码

  现代处理器的流水线性能使得处理器的工作远远超前于当前正在执行的指令。处理器中的分支预测在遇到比较指令时会进行预测下一步跳转到哪里。如果预测错误，就要重新回到分支跳转的原地。分支预测错误会严重影响程序的执行效率。因此，我们应该编写让处理器预测准确率提高的代码，即使用条件传送指令。我们用条件操作来计算值，然后用这些值来更新程序状态，具体如改进后的代码所示。

9.3 改进代码
0 a2 w" J' n" n. svoid minmax2(long a[],long b[],long n){
long i;
: p1 P, y) \4 P/ V( G/ R for(i = 0;i,n;i++){
long min = a < b ? a:b;
+ W6 J7 P( v  H3 m2 W, U4 K long max = a < b ? b:a;
a = min;
b = max;
}
}

  在原代码的第4行中，需要对a和b进行比较，再进行下一步操作，这样的后果是每次都要进行预测。改进后的代码实现这个函数是计算每个位置i的最大值和最小值，然后将这些值分别赋给a和b，而不是进行分支预测。

10. 总结

  我们介绍了几种提高代码效率的技巧，有些是编译器可以自动优化的，有些是需要我们自己实现的。现总结如下。

• 消除连续的函数调用。在可能时，将计算移到循环外。考虑有选择地妥协程序的模块性以获得更大的效率。

• 消除不必要的内存引用。引入临时变量来保存中间结果。只有在最后的值计算出来时，才将结果存放到数组或全局变量中。

• 展开循环，降低开销，并且使得进一步的优化成为可能。

• 通过使用例如多个累积变量和重新结合等技术，找到方法        提高指令级并行。

• 用功能性的风格重写条件操作，使得编译采用条件数据传送。

  
  

) h6 N* v/ m7 }, G