winston 发表于 2011-12-8 13:05:05

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

来自;http://blog.csdn.net/muxiqingyang/article/details/6547315
美剧《24小时》常常有这样的例子,情报部门找到一张犯罪份子的照片,然后使用人脸识别软件在数据库中进行搜索,这通常要几十分钟,在这个时间空当内,杰克·鲍尔继续跟踪另外一条线索。遇到恐怖份子袭击时,时间就是生命,如果人脸识别软件效率更高,更早搜索出结果,就能更早的防范危险,挽救生命。 服务器软件非常注重代码效率,更高效的软件,意味着更短的客户响应时间,更少的服务器成本。对于很多互联网公司,服务器成本占了公司总成本相当大一部分比例,它们的核心业务代码都是经过严格优化的,使得每台服务器能服务更多的用户。 嵌入式软件也非常注重代码效率,因为嵌入式领域对成本要求非常苛刻,老板都想拿着486的CPU做出Vista的效果,这就特别需要代码效率奇高。在战场上,我们最喜欢以少胜多的英雄,写软件,我们也要有拿着486当奔4使的霸气。PC机软件在代码效率上要相对逊色很多,反正PC机性能也强,很多程序员并不重视代码的效率。不过也有不少软件将小巧、快速作为自己软件的卖点,如QQ影音、电驴等。从消费者的角度来说,在功能一样的情况下,自然会选择小巧、快速的软件。
    作为程序员,我们应该勤俭编码,让代码使用更少的CPU运算量,做更多的活。

winston 发表于 2011-12-8 13:05:36

连载:编写高效代码(2)——代码剖析,没有调查,就没有发言权 通常我们在编写程序时,第一版总是为了实现功能,不太注重代码效率,第二版才会进行代码的优化。我们读了这么多年的书,也都明白了一个道理:100分的总分,从60分提升到80分,不是太难,而从80分提升到100分,那就很难了。成绩和努力程度常常呈现出如下曲线,越到后来,收获就越小了。
http://hi.csdn.net/attachment/201106/15/0_1308150732WOZC.gif成绩和努力程度的关系曲线
软件开发也是同样一个道理,项目开发都受到质量、成本、进度三要素的制约,尤其是在战机稍纵即逝的商界,时间更是宝贵,软件性能优化不可能无休止的进行下去,达到要求后就要收山,因此好钢必须要用在刀刃上,我们得先知道哪些代码值得优化,哪些代码不值得优化。 毛主席教导我们,没有调查就没有发言权,调查研究就像十月怀胎,解决问题就像一朝分娩。软件性能优化的第一步就是调查程序各个模块(或函数)的执行时间。
检验自己的代码是否高效。 美剧《犯罪心理》中常出现一个词:“profile”,意思是剖析犯罪份子的心理,这个词用在软件开发中,就叫软件性能剖析。性能剖析工具能分析出每个函数(有的工具能分析到每个循环)的执行时间。 我们在做软件开发时,可以使用的性能剖析软件有很多,例如IBM的Rational Quantify,Intel的VTune,AMD的CodeAnalyst,DSP的软件集成开发环境中也自带有这种工具。 http://hi.csdn.net/attachment/201106/15/0_1308150760lLnZ.gif      http://hi.csdn.net/attachment/201106/15/0_1308150768f1u1.gif   
Quantify

VTune
在没有工具时,我们也可以手工编写代码来实现profile的功能。处理器上都有计数器,每个时钟周期累加一次,操作系统会提供访问计数器的函数,通过在一段代码前后访问计数器,得到它们的差值,再配合处理器的工作频率,就可以知道这段代码执行的时间了。知道了各个模块的执行时间之后,就能优先优化占用时间长的模块。
    光说不练假把式,真刀真枪真功夫,从下节开始,我们就来介绍怎么编写高效的代码。

winston 发表于 2011-12-8 13:06:06

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

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

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

winston 发表于 2011-12-8 13:06:35

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

    Niklaus Wirth--Pascal语言之父,他提出了著名公式"算法+数据结构=程序"。当然,算法不仅仅可以用在程序上,硬件也一样用,处理器上也包含了不少算法,如分支预测算法、乱序调度算法等等。 http://www.techcn.com.cn/uploads/200905/1242834057pnMEEMEW.jpg
Niklaus Wirth

    James Cooley--FFT(快速傅里叶变换)的发明人,FFT是信号处理领域使用最为广泛的算法,语音处理,无线通信都会使用到它,图像、视频也会使用到它的变种。 http://www.ieeeghn.org/wiki/images/thumb/5/58/James_W._Cooley_3529.jpg/180px-James_W._Cooley_3529.jpg James Cooley
    Tony Hoare--快速排序算法(Quick Sort)的发明人,这个算法是当前世界上使用最广泛的算法之一。 http://www.inf.u-szeged.hu/stf/images/TonyHoare.jpg Tony Hoare

    Edsger Wybe Dijkstra--图论中最短路径算法的发明人,这个算法也称为Dijkstra算法。 http://a1.att.hudong.com/83/48/16300000044935126832480402242.jpg Edsger Wybe Dijkstra
    Don E.Knuth--著有经典著作《计算机程序设计艺术》,该书被誉为算法中的圣经。 http://www-cs-faculty.stanford.edu/~uno/don.gif Don E.Knuth

winston 发表于 2011-12-8 13:07:02

连载:编写高效代码(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即可。 http://hi.csdn.net/attachment/201106/21/0_1308668096j001.gif 汇编、 Intrinsic function 、标准 C 在性能和可移植性关系

winston 发表于 2011-12-8 13:07:28

连载:编写高效代码(6)——降低数据精度
我们知道,小数点后面的位数越多,数据越精确,例如,100.11就比100.1精确,而越精确的数据,所需要的bit数也越多。浮点数有单精度和双精度2种格式,单精度浮点数占32 bit,双精度浮点数占64 bit,处理双精度的浮点数自然要比单精度浮点数慢。
在fabsf()是计算单精度浮点数绝对值的函数,fabsf()就比<FONT style="FONT-SIZE: 10.5pt" face=""">fabs()快,很多程序员并没有注意到这个区别。如果一个数据用单精度能否表示,就不需要使用双精度。

winston 发表于 2011-12-8 13:08:01

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


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

view plaincopy to clipboardprint?

[*]int min(int a, int b)[*]
[*]{[*]
[*]
returna<b? a: b;[*]
[*]}[*]
[*]c = min(a, b);[*]
[*]
//直接写为
[*]
[*]c = a<b? a: b;
int min(int a, int b){   returna<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)[*]
[*]{[*]
[*]
returna<b? a: b;[*]
[*]}[*]
[*]c = min(a, b);[*]
[*]
//编译器会将代码优化成
[*]
[*]c = a<b? a: b;
inline int min(int a, int b){   returna<b? a: b;}c = min(a, b);//编译器会将代码优化成c = a<b? a: b;

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

winston 发表于 2011-12-8 13:09:10

连载:编写高效代码(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;[*]
[*]   }[*]
[*]
returnf(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;   }   returnf(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;[*]
[*]
int f(int n)[*]
[*]{[*]
[*]
int result;[*]
[*]
if(n <= 1)[*]
[*]   {[*]
[*]       result = 1;[*]
[*]   }[*]
[*]
else
[*]
[*]   {[*]
[*]       result = arr + arr;[*]
[*]   }[*]
[*]   arr = result;   [*]
[*]
return result;[*]
[*]}[*]
[*]
int main()[*]
[*]{[*]
[*]
int result;[*]
[*]
int i;[*]
[*]
for(i=0; i < 40; i++)[*]
[*]   {[*]
[*]       result = f(i);[*]
[*]       printf("%d\n", result);[*]
[*]   }[*]
[*]}
int arr;int f(int n){   int result;   if(n <= 1)   {       result = 1;   }   else   {       result = arr + arr;   }   arr = 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 发表于 2011-12-9 23:33:01

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

{

   if(i%2 == 0)

   {

       a = x;

   }

   else

   {

       a = y;

   }

}


如果改成如下这种形式就更好了:for(i=0; i<100; i+=2)

{

   a = x;

   a = y;

}




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

int b = 0;

if (a > 0)

{

   b = 1;

}

else

{

   b = 2;

}


我们来看看汇编语言:
4:      int a = -5;

00401028   mov         dword ptr ,0FFFFFFFBh

5:      int b = 0;

0040102F   mov         dword ptr ,0

6:      if (a > 0)

00401036   cmp         dword ptr ,0

0040103A   jle         main+35h (00401045)

7:      {

8:            b = 1;

0040103C   mov         dword ptr ,1

9:      }

10:       else

00401043   jmp         main+3Ch (0040104c)

11:       {

12:         b = 2;

00401045   mov         dword ptr ,2

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

winston 发表于 2011-12-16 12:10:19

编写高效代码(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次内存访问:
c = a
* b;

d = a + b;



如果改成如下的形式,就只有两次内存访问了:
x =
a;

y = b;
c = x * y;
d = x + y;

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

int fun_a ()
{
   int y, z;
   y = x;
   z = x + 1;
   …
}




最好改为:


intx;
int fun_a ()
{
   int y, z, temp;
   temp = x;
   y = temp;
   z = temp + 1;
   …
}



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