连载：编写高效代码 —编写高效代码的意义

winston

来自;http://blog.csdn.net/muxiqingyang/article/details/6547315

美剧《24小时》常常有这样的例子，情报部门找到一张犯罪份子的照片，然后使用人脸识别软件在数据库中进行搜索，这通常要几十分钟，在这个时间空当内，杰克·鲍尔继续跟踪另外一条线索。遇到恐怖份子袭击时，时间就是生命，如果人脸识别软件效率更高，更早搜索出结果，就能更早的防范危险，挽救生命。

服务器软件非常注重代码效率，更高效的软件，意味着更短的客户响应时间，更少的服务器成本。对于很多互联网公司，服务器成本占了公司总成本相当大一部分比例，它们的核心业务代码都是经过严格优化的，使得每台服务器能服务更多的用户。

嵌入式软件也非常注重代码效率，因为嵌入式领域对成本要求非常苛刻，老板都想拿着486的CPU做出Vista的效果，这就特别需要代码效率奇高。在战场上，我们最喜欢以少胜多的英雄，写软件，我们也要有拿着486当奔4使的霸气。

  PC机软件在代码效率上要相对逊色很多，反正PC机性能也强，很多程序员并不重视代码的效率。不过也有不少软件将小巧、快速作为自己软件的卖点，如QQ影音、电驴等。从消费者的角度来说，在功能一样的情况下，自然会选择小巧、快速的软件。

    作为程序员，我们应该勤俭编码，让代码使用更少的CPU运算量，做更多的活。

winston

连载：编写高效代码(2)——代码剖析，没有调查，就没有发言权

通常我们在编写程序时，第一版总是为了实现功能，不太注重代码效率，第二版才会进行代码的优化。我们读了这么多年的书，也都明白了一个道理：100分的总分，从60分提升到80分，不是太难，而从80分提升到100分，那就很难了。成绩和努力程度常常呈现出如下曲线，越到后来，收获就越小了。

成绩和努力程度的关系曲线

软件开发也是同样一个道理，项目开发都受到质量、成本、进度三要素的制约，尤其是在战机稍纵即逝的商界，时间更是宝贵，软件性能优化不可能无休止的进行下去，达到要求后就要收山，因此好钢必须要用在刀刃上，我们得先知道哪些代码值得优化，哪些代码不值得优化。

毛主席教导我们，没有调查就没有发言权，调查研究就像十月怀胎，解决问题就像一朝分娩。软件性能优化的第一步就是调查程序各个模块(或函数)的执行时间。
检验自己的代码是否高效。

美剧《犯罪心理》中常出现一个词：“profile”，意思是剖析犯罪份子的心理，这个词用在软件开发中，就叫软件性能剖析。性能剖析工具能分析出每个函数(有的工具能分析到每个循环)的执行时间。

我们在做软件开发时，可以使用的性能剖析软件有很多，例如IBM的Rational Quantify，Intel的VTune，AMD的CodeAnalyst，DSP的软件集成开发环境中也自带有这种工具。

           

Quantify

VTune

在没有工具时，我们也可以手工编写代码来实现profile的功能。处理器上都有计数器，每个时钟周期累加一次，操作系统会提供访问计数器的函数，通过在一段代码前后访问计数器，得到它们的差值，再配合处理器的工作频率，就可以知道这段代码执行的时间了。知道了各个模块的执行时间之后，就能优先优化占用时间长的模块。

    光说不练假把式，真刀真枪真功夫，从下节开始，我们就来介绍怎么编写高效的代码。

winston

连载：编写高效代码(3)——使用更快的算法

    算法，是程序设计的灵魂。
    数学家高斯小学的时候就知道了用更简洁的算法来减少计算量。高斯的老师出了道数学题：1+2+3……+100=? 在别的同学还在用一个一个加法苦算的时候，高斯很快就写出了答案5050，他的方法是用(100+1)*100/2代替了99个加法。

高斯的算法

    算法的优化，能明显的减少程序执行所需要的指令数，也即运算量。比较有名的快速算法包括：FFT算法(快速傅里叶变换)、快速排序算法等等。在数据结构与算法中，时间复杂度O用来描述算法所需要的运算量，对n个元素进行排序，冒泡排序算法的时间复杂度为O(n*n)，快速排序算法的时间复杂度为O(n*logn)。当n较大时，快速排序算法所需要的指令数就远远少于冒泡排序算法。

winston

连载：编写高效代码(4)—算法领域的牛人们

    Niklaus Wirth--Pascal语言之父，他提出了著名公式"算法+数据结构=程序"。当然，算法不仅仅可以用在程序上，硬件也一样用，处理器上也包含了不少算法，如分支预测算法、乱序调度算法等等。

Niklaus Wirth

    James Cooley--FFT(快速傅里叶变换)的发明人，FFT是信号处理领域使用最为广泛的算法，语音处理，无线通信都会使用到它，图像、视频也会使用到它的变种。

James Cooley

    Tony Hoare--快速排序算法(Quick Sort)的发明人，这个算法是当前世界上使用最广泛的算法之一。

Tony Hoare

    Edsger Wybe Dijkstra--图论中最短路径算法的发明人，这个算法也称为Dijkstra算法。

Edsger Wybe Dijkstra

    Don E.Knuth--著有经典著作《计算机程序设计艺术》，该书被誉为算法中的圣经。

Don E.Knuth

winston

连载：编写高效代码(5)——选用合适的指令

      处理器除了一些常用的加法、移位、乘法等指令外，还有一些完成复杂功能的指令，例如：DSP中的乘累加指令、求绝对值指令，x86中的SIMD指令等等。在用高级语言编程时，编译器常常不会使用到这些指令，而是用多条简单的指令去实现它们，这时就需要程序员自己去使用它们。
     使用这些复杂指令，最直接的方式当然是写汇编语言，不过汇编语言编程难度太大，还好，编译器提供了一种方便使用汇编指令的方式：Intrinsic function。例如，SSE3中的指令addsubps，它对应的Intrinsic function为_mm_addsub_ps，Intrinsic function的使用方式和普通函数一样：
w = _mm_addsub_ps ( u , v);
     虽然它看起来像个函数调用，不过它不是真正的函数，它会被编译器翻译成对应的汇编指令。u和v也不是函数的参数，u是指令addsubps的第一个操作数，v是指令addsubps的第二个操作数。数据类型是128bit。
     手工优化过的纯汇编，性能当然是最高的，不过也是最不易编程和可移植性最差的，使用标准C语言编程，易编程，可移植性高，不过性能也差，Intrinsic function是介于它们中间的一种产物。对于调用次数非常多，非常影响性能的模块，可以使用汇编对其优化，对于一般影响程序的模块，可以使用Intrinsic function对其优化，其他模块，使用标准C即可。

汇编、 Intrinsic function 、标准 C 在性能和可移植性关系

winston

连载：编写高效代码(6)——降低数据精度

我们知道，小数点后面的位数越多，数据越精确，例如，100.11就比100.1精确，而越精确的数据，所需要的bit数也越多。浮点数有单精度和双精度2种格式，单精度浮点数占32 bit，双精度浮点数占64 bit，处理双精度的浮点数自然要比单精度浮点数慢。

在fabsf()是计算单精度浮点数绝对值的函数，fabsf()就比<FONT style="FONT-SIZE: 10.5pt" face=""">fabs()快，很多程序员并没有注意到这个区别。如果一个数据用单精度能否表示，就不需要使用双精度。

winston

连载：编写高效代码(7) 减少函数调用——不要老打断我


         函数是结构化程序设计的产物，它使代码更加模块化，耦合性更低，重用性更高。不过，函数调用会带来额外的开销，除了引起跳转外，还会产生额外的指令。
        人都有这样的经验，做一件事情时，如果被人打断，重新再回来做这件事情，就需要一段恢复时间，如果老是被打断，那事情就没法做了。函数调用也是这样，要进行参数压栈出栈、寄存器保存、指令跳转等。多个步骤如果程序的性能要求较高，就可以将一些小的函数直接转换成代码。1．将小函数直接写成语句
        下面这个求最小值的函数，可以直接用函数的内容替换函数调用。

view plaincopy to clipboardprint?

• int min(int a, int b)  
• 
  
• {  
• 
  
• 
  return  a<b? a: b;  
• 
  
• }  
• 
  
• c = min(a, b);  
• 
  
• 
  //直接写为
  
• 
  
• c = a<b? a: b;  

int min(int a, int b){   return  a<b? a: b;}c = min(a, b);//直接写为c = a<b? a: b;


2．将小函数写成宏

         如果调用的地方很多，用函数调用的方式会显得代码简洁。一种即保持代码简洁又能减少函数调用的做法是将函数体声明为宏。

view plaincopy to clipboardprint?

• #define min(a,b) ((a)<(b)) ? (a) : (b)
  
• 
  
• c = min(a,b);  

#define min(a,b) ((a)<(b)) ? (a) : (b)c = min(a,b);


3．将函数声明为内联函数

        如果嫌改为宏的方法太麻烦，还有一种简单的方法，就是将函数声明为inline，编译器会自动用函数体覆盖函数调用。
view plaincopy to clipboardprint?

• inline
  int min(int a, int b)  
• 
  
• {  
• 
  
• 
  return  a<b? a: b;  
• 
  
• }  
• 
  
• c = min(a, b);  
• 
  
• 
  //编译器会将代码优化成
  
• 
  
• c = a<b? a: b;  

inline int min(int a, int b){   return  a<b? a: b;}c = min(a, b);//编译器会将代码优化成c = a<b? a: b;

          本文节选自《大话处理器》第6章。
         一台电脑要真正做到优秀，它的硬件和软件是必须紧密联系在一起的。——乔布斯
         作者微博：  weibo.com/muxiqingyang

winston

连载：编写高效代码(8) 空间换时间——我们总是在走，却忘了停留
          时间和空间的关系，是霍金这种智商的人要研究的东西，我们只需要知道，在编程时，空间是可以换时间的，时间也是可以换空间的。
         李开复在他的自传《世界因你不同》中描述了他小时候在美国学校里的一个故事，老师出了道题：“谁知道1/7等于多少？”小开复马上大声回答：“0.142857”，老师和同学们都惊呼开复是个天才，其实事实情况是，开复以前在台湾时就记下了这个答案。这就是一个典型的以空间（存储）换时间的例子。
        再举一个编程的例子：打印0～40的Fibonacci序列。
Fibonacci序列：
F(n) = 1,              n = 0 或1
F(n) = F(n–1)+F(n–2)    n >1
        代码如下：
view plaincopy to clipboardprint?

• int f(int n)  
• 
  
• {  
• 
  
• 
  if(n<=1)  
• 
  
•    {  
• 
  
• 
  return 1;  
• 
  
•    }  
• 
  
• 
  return  f(n-1) + f(n-2);  
• 
  
• }  
• 
  
• 
  int main()  
• 
  
• {  
• 
  
• 
  int result;  
• 
  
• 
  int i;  
• 
  
• 
  for(i=0; i < 40; i++)  
• 
  
•    {  
• 
  
•        result = f(i);  
• 
  
•        printf("%d\n", result);  
• 
  
•    }  
• 
  
• }  

int f(int n){   if(n<=1)   {       return 1;   }   return  f(n-1) + f(n-2);}int main(){   int result;   int i;   for(i=0; i < 40; i++)   {       result = f(i);       printf("%d\n", result);   }}
         使用这段代码，在我的电脑上需要耗费21秒，而使用下面这段代码，则耗时不到1秒。下面的代码使用了一个数组，将F的值缓存起来，这样计算F(n) = F(n–1)+F(n–2)时就不需要递归执行，直接从数组中取值相加即可。可见，空间换时间的效果是多么的明显。
view plaincopy to clipboardprint?

• int arr[40];  
• 
  
• 
  int f(int n)  
• 
  
• {  
• 
  
• 
  int result;  
• 
  
• 
  if(n <= 1)  
• 
  
•    {  
• 
  
•        result = 1;  
• 
  
•    }  
• 
  
• 
  else
  
• 
  
•    {  
• 
  
•        result = arr[n-1] + arr[n-2];  
• 
  
•    }  
• 
  
•    arr[n] = result;   
• 
  
• 
  return result;  
• 
  
• }  
• 
  
• 
  int main()  
• 
  
• {  
• 
  
• 
  int result;  
• 
  
• 
  int i;  
• 
  
• 
  for(i=0; i < 40; i++)  
• 
  
•    {  
• 
  
•        result = f(i);  
• 
  
•        printf("%d\n", result);  
• 
  
•    }  
• 
  
• }  

int arr[40];int f(int n){   int result;   if(n <= 1)   {       result = 1;   }   else   {       result = arr[n-1] + arr[n-2];   }   arr[n] = result;    return result;}int main(){   int result;   int i;   for(i=0; i < 40; i++)   {       result = f(i);       printf("%d\n", result);   }}


         在商业上最成功的空间换时间的例子是Google和百度的搜索引擎算法，当我们提交一个搜索请求时，搜索引擎并不是现场给我们搜索，要在这么短的时间内搜索全球数不尽的网页是不可能的，它只是将已经搜索好的网页呈现给我们。


附：Fibonacci其人
         Fibonacci是在越狱中指证John Abruzzi的污点证人，后被Michael发现藏匿地址的那个人吗？
         非也，此Fibonacci是意大利12世纪著名数学家Leonardo Pisano Fibonacci。在他的一本书中，他提出了这么一个有趣的问题：“假定一对兔子在它们出生整整两个月以后可以生一对小兔子，其后每隔一个月又可以再生一对小兔子。假定现在一个笼子里有一对刚生下来的小兔子，请问一年以后笼子里应该有几对兔子？”这个问题的数学建模，就是Fibonacci序列。



         本文节选自《大话处理器》第6章。
         一台电脑要真正做到优秀，它的硬件和软件是必须紧密联系在一起的。——乔布斯

winston

   我们在介绍处理器时，已经知道了，现在的处理器都是流水线结构，if和switch等语句会带来跳转，而跳转会打乱流水线的正常执行，影响程序的执行效率。
         下面这段代码，把奇数赋一个值，把偶数赋一个值，可以用这种方式实现：

1. for(i=0; i<100; i++)
3. {
5.    if(i%2 == 0)
7.    {
9.        a[i] = x;
11.    }
13.    else
15.    {
17.        a[i] = y;
19.    }
21. }

复制代码

如果改成如下这种形式就更好了：

1. for(i=0; i<100; i+=2)
3. {
5.    a[i] = x;
7.    a[i+1] = y;
9. }

复制代码

  将最可能进入的分支放在 if中，而不是else中
         Intel处理器有分支预测单元，第一次进入一个分支时，由于没有历史信息可供参考，是否跳转取决于Static Predictor（静态预测器）的预测策略，通常Static Predictor的策略是：向下跳转预测为不跳转，向上跳转预测为跳转。根据这个特性，我们在写if else语句时，也要注意。且看下面这段代码是否合适？

1. int a = -5;
3. int b = 0;
5. if (a > 0)
7. {
9.    b = 1;
11. }
13. else
15. {
17.    b = 2;
19. }

复制代码

我们来看看汇编语言：

2. 4:        int a = -5;
4. 00401028   mov         dword ptr [ebp-4],0FFFFFFFBh
6. 5:        int b = 0;
8. 0040102F   mov         dword ptr [ebp-8],0
10. 6:        if (a > 0)
12. 00401036   cmp         dword ptr [ebp-4],0
14. 0040103A   jle         main+35h (00401045)
16. 7:        {
18. 8:            b = 1;
20. 0040103C   mov         dword ptr [ebp-8],1
22. 9:        }
24. 10:       else
26. 00401043   jmp         main+3Ch (0040104c)
28. 11:       {
30. 12:           b = 2;
32. 00401045   mov         dword ptr [ebp-8],2
34. 13:       }

复制代码

       读者没必要管这么一大串汇编语言是什么意思，只需要知道jle是个条件跳转指令就可以了，它跳到地址00401045处，是向下跳，根据Static Predictor的策略，它被预测为不跳转，处理器会从0040103C地址处开始取下一条指令。再看看实际的执行情况，a<0，执行else这个分支，于是处理器发现取错了地址，又要从头来过，白白浪费了大量时间。可见，执行概率高的分支，应该放在if分支中。
作者：muxiqingyang 发表于2011-12-9 22:39:09 原文链接

winston

编写高效代码(12) 优化内存访问——别让包袱拖垮了你

从理论上看，每条运算指令的执行时间都很短，大多数指令一个Cycle就能完成，很多时候还能一个Cycle执行多条指令，可是实际上，执行指令只是处理器要做的很少一部分工作，处理器还要从存储器中取指令，从存储器中将数据导入到寄存器中，等算完后，再将结果存入到存储器中。
        处理器运算的速度像兔子赛跑一样快，但是存储器的访问速度像乌龟走路一样慢，而且越是远离内核的存储器，访问速度越慢。
        下面这个表是在几个x86处理器中，内核访问各级数据Cache和内存所需要的 Cycle数：

处理器	Level 1 data Cache	Level 2 data Cache	内存
P3	3	8	140
P4	2	19	350
PM（奔腾M）	3	10	80
Core2（酷睿）	3	14	185
Opteron（皓龙）	3	13	100

        从这张表可以看出，从L1中访问数据速度还较快，但是仍然要慢于运算的速度，从L2中访问数据速度还能将就，从内存中访问数据就无法忍受了。我们应该尽量减少内存的访问，要访问，也要尽量避免Cache miss。少使用数组，少使用指针
         由于大块数据会被放在存储器中，简单局部变量才会被放在寄存器中，因此应该尽量少用数组、指针，多用简单局部变量。
下面这段程序，需要4次内存访问：

2. c = a[i]
3. * b[i];
5. d = a[i] + b[i];

复制代码

如果改成如下的形式，就只有两次内存访问了：

2. x =
3. a[i];
5. y = b[i];
6. c = x * y;
7. d = x + y;

复制代码

少用全局变量
        全局变量因为要被多个模块使用，不会被放到寄存器中，局部变量才能被放在寄存器中，应尽量避免使用全局变量。下面这段程序：

2. int
3. x;
5. int fun_a ()
6. {
7.    int y, z;
8.    y = x;
9.    z = x + 1;
10.    …
11. }

复制代码

最好改为：

4. int  x;
5. int fun_a ()
6. {
7.    int y, z, temp;
8.    temp = x;
9.    y = temp;
10.    z = temp + 1;
11.    …
12. }

复制代码

一次多访问一些数据
        我们通常会有这样的生活常识，要去很远的地方，就会多带一些东西，要去近一点的地方，就会少带一些东西。既然数据访问速度较慢，我们就一次多访问些数据。处理器将这些为我们考虑到了，通常都提供了较大的数据带宽。
         以C64 DSP为例，通常一条指令，一次对两个32bit的数据做处理，而它却1次可以访问两个64bit数据。
        在DSP中，SIMD指令和普通指令共用寄存器，有些数据虽然不能用SIMD指令处理，我们也可以一次将内存中的多个数据搬入到寄存器中，用简单指令分别处理，当要存储时，将分散的寄存器组合在一个连续的位置，再将数据输出到内存中。由于操作寄存器远比操作存储器快，虽然多了些数据的拆分和组合的操作，代价还是值得的。