连载：编写高效代码 —编写高效代码的意义
来自;http://blog.csdn.net/muxiqingyang/article/details/6547315美剧《24小时》常常有这样的例子，情报部门找到一张犯罪份子的照片，然后使用人脸识别软件在数据库中进行搜索，这通常要几十分钟，在这个时间空当内，杰克·鲍尔继续跟踪另外一条线索。遇到恐怖份子袭击时，时间就是生命，如果人脸识别软件效率更高，更早搜索出结果，就能更早的防范危险，挽救生命。 服务器软件非常注重代码效率，更高效的软件，意味着更短的客户响应时间，更少的服务器成本。对于很多互联网公司，服务器成本占了公司总成本相当大一部分比例，它们的核心业务代码都是经过严格优化的，使得每台服务器能服务更多的用户。 嵌入式软件也非常注重代码效率，因为嵌入式领域对成本要求非常苛刻，老板都想拿着486的CPU做出Vista的效果，这就特别需要代码效率奇高。在战场上，我们最喜欢以少胜多的英雄，写软件，我们也要有拿着486当奔4使的霸气。PC机软件在代码效率上要相对逊色很多，反正PC机性能也强，很多程序员并不重视代码的效率。不过也有不少软件将小巧、快速作为自己软件的卖点，如QQ影音、电驴等。从消费者的角度来说，在功能一样的情况下，自然会选择小巧、快速的软件。
作为程序员，我们应该勤俭编码，让代码使用更少的CPU运算量，做更多的活。 连载：编写高效代码(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的功能。处理器上都有计数器，每个时钟周期累加一次，操作系统会提供访问计数器的函数，通过在一段代码前后访问计数器，得到它们的差值，再配合处理器的工作频率，就可以知道这段代码执行的时间了。知道了各个模块的执行时间之后，就能优先优化占用时间长的模块。
光说不练假把式，真刀真枪真功夫，从下节开始，我们就来介绍怎么编写高效的代码。 连载：编写高效代码(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较大时，快速排序算法所需要的指令数就远远少于冒泡排序算法。 连载：编写高效代码(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 连载：编写高效代码(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 在性能和可移植性关系 连载：编写高效代码(6)——降低数据精度
我们知道，小数点后面的位数越多，数据越精确，例如，100.11就比100.1精确，而越精确的数据，所需要的bit数也越多。浮点数有单精度和双精度2种格式，单精度浮点数占32 bit，双精度浮点数占64 bit，处理双精度的浮点数自然要比单精度浮点数慢。
在fabsf()是计算单精度浮点数绝对值的函数，fabsf()就比<FONT style="FONT-SIZE: 10.5pt" face=""">fabs()快，很多程序员并没有注意到这个区别。如果一个数据用单精度能否表示，就不需要使用双精度。 连载：编写高效代码(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 连载：编写高效代码(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章。
一台电脑要真正做到优秀，它的硬件和软件是必须紧密联系在一起的。——乔布斯 我们在介绍处理器时，已经知道了，现在的处理器都是流水线结构，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 原文链接
编写高效代码(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