社区应用 最新帖子 精华区 社区服务 会员列表 统计排行 银行

  • 15599阅读
  • 26回复

C++性能优化要点

级别: 管理员
发帖
8532
金币
2762
威望
3231
贡献值
0
元宝
0

l         大部分程序的90%执行时间仅花费在大约1020个不同的函数上。如果费力气所优化的是被执行频率很低的函数,那么这个优化工作不会对程序性能有明显提高。所以有好钢就一定要用在刀刃上。
l         在优化时可能会对程序的可读性及可维护性造成损失。要权衡得失。并做好注释。
l         不要过早的进行优化工作。当一个函数已经被优化到紧凑且几近完美的程度时,如再遇到需要改动或重用时会发现无从下手。
l         算法的选择是决定性能的关键。所以要认真考虑算法,避免不必要的计算。
l         要避免在循环中每次为查找同一个元素就便利整个列表或数组。可以通过优化数据结构或者使用变量来保存这个元素的方法来进行优化。
l         虚函数可能会产生额外的开销。
l         将较简单且被频繁调用的函数设为内联可以有效提高程序性能。内联函数inline:当函数做上内联标记以后,编译器会在调用此函数时将函数的内容复制到此处。这样做的好处是可以减小函数调用时的开销。但是因为每次调用之处都会复制,所以生成的可执行代码会变得庞大。注意:有时内联函数太复杂编译器会拒绝内联,将inline忽略掉而不提示警告或错误;内联函数只能出现在.h文件中。建议将其紧跟在类定义之后。
l         当调用函数的参数为一个较大的数据类型或一个对象时,切忌使用值传递方式,要使用指针或引用的方式传递。因为值传递需要创建一个临时的对象备份,不要忘了,对象的创建会调用构造函数,然后还需要复制对象的内容到新创建的对象中,用完之后还要调用析构函数。更甚者如果此对象类中又包含了其他类型的对象


>这开销可是够大的!当然,
l         不使用的空函数注释掉。
l         下面的情况看看编译器背着你做了什么:
如有函数
void SetRotation(const Rotation & rot);
Rotation类定义如下:
Class Rotation
{//…..
Public:
              Rotation();
              Rotation(float fdegree, int iDirection=1,float fRoll=0.0);//注意此构造函数
//…


span\u003e\u003cfont face\u003d\"宋体\"\u003e\u003cspan\u003e类型的。虽然编译能够通过并且执行结果也没错,可编译器是怎么做的\u003cWBR\u003e呢?虽然它知道这个\u003c/span\u003e\u003c/font\u003e\u003cspan lang\u003d\"EN-US\"\u003efloat\u003c/span\u003e\u003cfont face\u003d\"宋体\"\u003e\u003cspan\u003e类型的参数不是它想要的,但它还知道使用这个\u003c/span\u003e\u003c/font\u003e\u003cspan lang\u003d\"EN-US\"\u003efloat\u003c/span\u003e\u003cfont face\u003d\"宋体\"\u003e\u003cspan\u003e型参数可以创建出一个\u003c/span\u003e\u003c/font\u003e\u003cspan lang\u003d\"EN-US\"\u003eRotation\u003c/span\u003e\u003cfont face\u003d\"宋体\"\u003e\u003cspan\u003e类型变量,于是它就这么做了。接下来又得构造又得析构\u003cWBR\u003e。这个函数如果位于执行频率较高的代码段。那岂不又影响执行效率了\u003cWBR\u003e?所以不要为了少敲几下键盘图省事儿。\u003c/span\u003e\u003c/font\u003e\u003cspan lang\u003d\"EN-US\"\u003e\u003c/span\u003e\u003c/p\u003e\n\n\u003cp style\u003d\"border:none;padding:0cm\"\u003e\u003cfont size\u003d\"2\" face\u003d\"Times New Roman\"\u003e\u003cspan lang\u003d\"EN-US\"\u003e?\u003c/span\u003e\u003c/font\u003e\u003c/p\u003e\n\n\u003c/div\u003e\n\n\u003cp style\u003d\"text-indent:21.0pt\"\u003e\u003cfont size\u003d\"2\" face\u003d\"宋体\"\u003e\u003cspan style\u003d\"font-size:10.5pt\"\u003e参考资料:(美)\u003c/span\u003e\u003c/font\u003e\u003cspan lang\u003d\"EN-US\"\u003eNoel\nLlopis\u003c/span\u003e\u003cfont face\u003d\"宋体\"\u003e\u003cspan\u003e。李鹏\u003c/span\u003e\u003c/font\u003e \u003cfont face\u003d\"宋体\"\u003e\u003cspan\u003e贾传俊译。《\u003c/span\u003e\u003c/font\u003e\u003cspan lang\u003d\"EN-US\"\u003eC++\u003c/span\u003e\u003cfont face\u003d\"宋体\"\u003e\u003cspan\u003e游戏编程》(\u003c/span\u003e\u003c/font\u003e\u003cspan lang\u003d\"EN-US\"\u003eC++\nfor Game Programmers\u003c/span\u003e\u003cfont face\u003d\"宋体\"\u003e\u003cspan\u003e)。清华大学出版社\u003c/span\u003e\u003c/font\u003e\u003cfont size\u003d\"1\" face\u003d\"Arial\"\u003e\u003cspan lang\u003d\"EN-US\" style\u003d\"font-size:9.0pt;font-family:Arial\"\u003e\u003c/span\u003e\u003c/font\u003e\u003c/p\u003e\n\n\u003c/div\u003e\n\n\u003c/div\u003e\n\n\n",0]);//-->}
当执行如下代码时:
float fDegree=90.0;
SetrRotation(fDegree);

SetrRotation函数需要一个Rotation类形的参数,但是得到的却是float类型的。虽然编译能够通过并且执行结果也没错,可编译器是怎么做的呢?虽然它知道这个float类型的参数不是它想要的,但它还知道使用这个float型参数可以创建出一个Rotation类型变量,于是它就这么做了。接下来又得构造又得析构。这个函数如果位于执行频率较高的代码段。那岂不又影响执行效率了?所以不要为了少敲几下键盘图省事儿。

参考资料:(美)Noel Llopis。李鹏 贾传俊译。《C++游戏编程》(C++ for Game Programmers)。清华大学出版社


关键词: C++ 性能
QQ: 378890364 微信:wwtree(省短信费) 紧急事宜发短信到0061432027638  本站微博:http://t.qq.com/wwtree QQ群:122538123
级别: 管理员
发帖
8532
金币
2762
威望
3231
贡献值
0
元宝
0
只看该作者 沙发  发表于: 2010-09-05

1. 一般来说,一个程序使用的栈的大小是固定的,由编译器决定的。而且栈的大小都不会太大,开发人员可以通过编译器的选项来指定栈的大小。所以当程序变量生成太多的情况下是会造成栈溢出的。

栈的内存是系统分配的,并且出栈入栈都有CPU相应的指令进行操作。并且分配的空间一般是连续的,而且使用的时候效率较高,不会产生内存碎片。

堆的大小一般只受限制于操作系统的虚拟内存大小,因此可以用来分配创建一些占用内存较大的对象或数据。堆的大小由程序员动态的分配和回收。系统需要按照一定的算法在堆的空间中寻找合适大小的空闲堆。

2. 在函数传值调用的时候,那么会调用到拷贝构造函数;并且在函数返回的时候,如果返回值不是地址(指针或者引用)时候,那么也会调用相应类的拷贝构造函数。

3. 对于静态函数和非静态成员函数,C++编译器采用与普通C函数类似的方式进行编译,只不过对函数名进行了名称修饰,用来支持重载。并且在参数列表中增加了一个this指针,用来表明是哪一个对象调用了该函数。静态函数和非静态成员函数不会影响对象内存的大小,虽然其实现会占用相应的内存空间,同样不会随对象数目的增加而增加。

4. 虚函数用来支持OOP中的多态特性,只有在程序运行时,才决定一个父类对象的指针调用的函数是父类还是具体的那一个子类。为了支持这一个特性,C++编译器在遇到有虚函数的类的时候,分配一个指针指向一个函数地址列表,叫做“虚函数表”,这个指针占据4个字节的空间。

5. 如果编译器指定打开RTTI开关时,vtable中的第一个指针是个typeinfo结构,每个类只产生一个typeinfo结构的实例。程序可以调用typeid()来取得类的信息,实际上就是通过vtable中的第一个指针获得了typeinfo

6. 说到继承那么就要说一下,虚析构函数:

昨天面试的时候,一个面试管问我,为什么在工程中一般要把基类的析构函数设置为虚函数。当时反正一个傻了,大脑空空~回来四下查寻终于找到了答案:

大部分的答案只有一个:防止内存泄露!为什么能防止内存泄露呢?

写两个例子:

实例一:

#include

class CFunction

{

public:

CFunction()

{

data = new char[64];

};

~CFunction()

{

delete [] data;

};

char *data;

};

class CFunctionEx : public CFunction

{

public:

CFunctionEx()

{

m_data = new char[64];

};

~CFunctionEx()

{

delete [] m_data;

};

private:

char *m_data;

};

void main()

{

CFunction *pCFun = new CFunctionEx;

delete pCFun;

}

实例二:

#include

class CBase

{

public:

CBase()

{

data = new char[64];

};

~CBase()

{

delete [] data;

};

char *data;

};

class CFunction

{

public:

CFunction(){};

~CFunction(){};

};

class CFunctionEx : public CFunction

{

public:

CFunctionEx(){};

~CFunctionEx(){};

private:

CBase m_cbase;

};

void main()

{

CFunction *pCFun = new CFunctionEx;

delete pCFun;

}

上面两个例子中最后的delete调用都回出现问题,问题都一样:内存泄露。两个pCFun指针都是指向基类的,那么当delete执行的时候也只会调用基类的析构函数。那么子类中从堆中申请到的那片内存空间便无法再释放了,因此造成了内存的泄漏。

7. 在每个派生类的头部都会存在一个基类的实例(这个实例甚至包括了父类中的private成员变量,但是这些成员变量在派生类中也是不可访问的)。派生类的实例是用在创建基类实例时建立的虚函数列表。但是这个vtable的内容在建立派生类的实例时候发生了变化。

8. 与单继承不同,派生类对象创建时,要首先创建基类的对象。创建基类时候按照一定顺序,这个顺序是由派生类声明时候决定的。

class derivedClass: public simpleClass1, public simpleClass2

那么simpleClass1对象会被首先创建,而:

class derivedClass: public simpleClass2, public simpleClass1

那么simpleClass2对象会被首先创建。析构函数执行的顺序刚好和创建的方向相反。

9. 注意在多继承中还要避免二义性。如果发生了菱形继承,那么基类中的成员变量在新的派生类中便有两个备份。这样在用到这个成员变量的时候,很多情况是未知了。容易造成很隐蔽的bug。为了避免这种情况发生,C++语言提供了虚拟继承(virtual),使用这个虚拟继承那么公共的基类中只存在一个实例。

10. 拷贝构造函数,这个东西主要是为了避免系统提供默认的拷贝构造函数时候使用位拷贝(按照对象的内存空间逐个字节进行复制)时候造成的问题。

如:class A中有一个指针*a,在构造函数中指向一块新开辟的内存空间。当实例化了一个a1,并且实例化b1时候采用了:

 A b1 = a1;

那么这个时候调用系统默认的构造函数,这个构造函数会把指针*a做一个复制给对象b1

那么这个时候内存情况:

如果当b1对象析构了,那么*a指向的这片内存空间便已经释放了,当对象a1对这块区域的任何操作便都将出错。如果对象a1析构时候,也将会对这片空间造成二次释放。


Second Chapter

1. 创建一个对象有两种方式:一种是从线程运行栈中创建:Object obj;此类对象称为局部对象;销毁这种对象不需要程序显示的调用析构函数,而是当程序运行出该对象所属的作用域时自动调用。

另一种创建对象的方式为从全局堆中动态创建:Object* obj = new Object;从全局堆中创建的对象需要显示的调用delete对象给予销毁,并将该对象所占用的全局堆内存空间返回给全局堆。

*当程序调用了delete时候,obj指针仍然指向刚才被回收的那片空间,如果使用了该指针会造成系统不可预测的结果。

2. 构造函数是一个递归的操作;析构函数也是一个递归函数;

3. 再谈虚函数:

每个支持虚函数的类(基类或派生类)都会有一个包含其所有支持的虚函数指针的vtable。另外每一个类生成的对象都会隐含了一个虚函数指针,此指针指向其所属类的虚拟函数表。

空间:

*每个支持虚拟函数的类都有一个虚拟函数表,这个表的大小和类中虚拟函数的多少成正比。

*类生成的每一个对象都有一个指向该类对应虚函数表的指针,无论类中虚函数的的多少都只有一个函数指针。但是每个对象中都有这样的一个指针,对象数量的增多,那么这个指针占有的空间也增加。

4.内联函数:编译器将调用内联函数的地方用内联函数的代码体进行代替~此处要注意:虚函数是不能内联化!因为:虚函数的调用是到了真正的执行期才能确定,而内联函数的替换展开是在编译器执行的。

5.为了防止类的构造函数自动的类型转化的发生,可以在构造函数前面加上explicit的声明。

6. 当一个函数返回的是某个非内建类型的对象时,这时因为返回结果(一个对象)必须要有一个地方存放。所以编译器会从调用该函数的栈桢中开辟新的空间,并用返回值作为参数调用该对象所属类型的拷贝构造函数在此空间中生成该对象。在被调用函数结束并返回后,可以继续利用此对象。

7. 非内建类型对象的声明,应该尽量将对象延迟到已经确切知道其有效状态时,这样可以减少临时对象的生成。

8. 如果需要重载operator+,最好也重载operator +=,并且考虑到维护性,operator+可以用operator+=来实现。

9. 注意的问题:(一个程序的片断)

string a,b;

const char* str;

...

if( strlen( str = ( a+b ).c_str() ) > 5 )

{

 printf(“%s\n”,str);

 ...;

}

这里的str 是不合法的,原因:

a+b的临时对象的生命周期在strlen( str = ( a+b ).c_str() ) > 5 语句执行结束后也结束了,那么在以后的访问都是非法的了。此处需要把a+b的计算结果放入临时变量中:

const string& c = a + b;

10. 如果有多个编译单位会调用到某同一个内联函数,C++规范要求这多个编译单元中该内联函数的定义必须是完全一致的,就是ODR(one-definition-rule)原则。应该把内联函数的定义都放到一个头文件中,这样如果要用到该函数的时候只要#include这个文件就可以了。

*内联函数最好在开发的后期引入,这样可以避免可能不必要的大量编译时间。

*发布给别人的代码最好不要用使用内联函数,如果内联的函数发生了变动(接口没有变化),那么别人在使用的时候还是要重新编译全部代码。

QQ: 378890364 微信:wwtree(省短信费) 紧急事宜发短信到0061432027638  本站微博:http://t.qq.com/wwtree QQ群:122538123
级别: 管理员
发帖
8532
金币
2762
威望
3231
贡献值
0
元宝
0
只看该作者 板凳  发表于: 2010-09-12
C++用移位实现乘除法运算,提高性能
用移位实现乘除法运算 
  a=a*4; 
  b=b/4; 
  可以改为: 
  a=a<<2; 
  b=b>>2; 
  
说明: 
  除2 = 右移1位 乘2 = 左移1位 
  除4 = 右移2位 乘4 = 左移2位 
  除8 = 右移3位 乘8 = 左移3位 
  ... ... 
  通常如果需要乘以或除以2的n次方
都可以用移位的方法代替。 
  大部分的C编译器,用移位的方法得到代码比调用乘除法子程序生成的代码效率高。 
  实际上,只要是乘以或除以一个整数,均可以用移位的方法得到结果,如: 
  a=a*9 
  分析a*9可以拆分成a*(8+1)即a*8+a*1, 因此可以改为: a=(a<<3)+a 
  a=a*7 
  分析a*7可以拆分成a*(8-1)即a*8-a*1, 因此可以改为: a=(a<<3)-a 
  关于除法读者可以类推, 此略. 
QQ: 378890364 微信:wwtree(省短信费) 紧急事宜发短信到0061432027638  本站微博:http://t.qq.com/wwtree QQ群:122538123
级别: 管理员
发帖
8532
金币
2762
威望
3231
贡献值
0
元宝
0
只看该作者 地板  发表于: 2010-09-15
性能调优--永远超乎想象

多年以前,我在开发一个C++的应用程序。我的同伴Jim Newkirk(当时的)过来告诉说,我们的一个公用函数运行得非常的缓慢。这个函数是用来转换二进制的树结构数据为普通文本,并存储到文件中的。(这是在XML出现之前,但概念类似于XML)

我审视了这个函数一会儿,发现了一个线性查找算法,于是毫无疑问的将这个线性查找算法替换为二分查找法(译注:binary search),然后就把这个函数交回给了Jim。Jim几小时后就回来了,问我是否有做过任何的改进,因为这个函数还是迟缓如初。

看来是我没找到关键,于是就一遍又一遍的研究了这个函数,然后发现并改进了一些其它很明显的算法问题,可是性能依然没有丝毫改进。函数依然缓慢,看到我对这个函数的无计可施,Jim也越来越沮丧。

最后,Jim终于找到了一个能够去分析这个函数性能的办法,就发现这个问题出自一个底层的叫strstream的C++库(译注1)。这个库函数随着文本数据的不断增加,它不停的一次又一次的申请内存块。这个函数单纯根据即将读入的文本数据大小来预先申请内存块,速度也迅速的随之以数量级的趋势降低。


很久以前,曾有一次我要写一个计算任意多边形面积的算法。我想出了一个不断的把这个任意多边形细分为三角形的主意。每次细分一个三角形,多边形就会减少一个顶点,而它的面积就可以由此累加起来。由于不得不处理很多不规则的形状,好久我才把这个功能写好。一、两天后,我就完成了这个厉害的算法,它能计算任意的多边形的面积。

几天后,我的一个同事过来找我,说:“我新画了多边形的一条边,可它花了45分钟才计算出面积。所以,我要是重新绘制这条线断或是调整它,面积都显示不出。”45分钟啊,很长的时间了,所以我就问她这个多边形有多少个顶点,她告诉我有超过1,000个的。

看了看算法,我认识到这个算法的复杂度是O(N^3)的(译注2),所以对于小多边形来说很快,但对于大型的来说速度就慢得无法忍受了。我一遍又一遍的思考着这个问题,但却找不到一个更好的算法。(现今我们只要用google搜索就好了,可那是现在而这是那时...)于是我们就把这个自动显示面积的功能去掉,然后告诉客户这太耗时了。

两周之后,纯属偶然机会, 我正翻阅一本关于prolog编程语言的书(一个可爱又另类的编程语言,我建议你也学习学习它),然后就发现了一个计算多边形面积的算法。它优雅,简单,而且是线性阶(译注2)的,我是从来都没写出过这么漂亮的算法。我用了几分钟时间就实现了它,哇!即使拖动多边形一个顶点绕着屏幕乱转,面积竟然也可以及时更新。


 昨天晚上,我坐在一辆豪华轿车里,从O'Hare驶向我在芝加哥北部郊区的家。I-294公路正在施工,而我们凑好赶上交通阻塞。于是我拿出我的Macbook Pro,然后开始即兴的编写Ruby程序。为了好玩,我开始编写埃拉托色尼质数过滤算法(译注:Sieve of Eratosthenes)。我想让程序一跑起来就能看到Ruby有多快,所以就在程序中增加了benchmark模块来度量速度。它相当快!能在两秒钟内算出所有在百万以内的素数!对于一个解释型语言来说还不错。

我想知道这个算法的复杂度O(x)是什么样的。坐在车里不好算出来,于是我决定通过一些设定点采样的方法来测出它。我从100,000开始到5,000,000,每间隔100,000运行一次这个算法采样,然后把这些采样点绘在了一个图上。竟然是线性阶!

这个算法怎能是线性阶呢?它有一个嵌套的循环!难道不应该是复杂度类似于O(N^2),或者至少也应该是O(N log N)啊?这里就是代码,你自己来看看:

 require 'benchmark'
def sievePerformance(n)
  r = Benchmark.realtime() do 
    sieve = Array.new(n,true)
    sieve[0..1] = [false,false]
    
    2.upto(n) do |i|
      if sieve 
        (2*i).step(n,i) do |j|
          sieve[j] = false
        end
      end
    end
  end
  r
end

我的儿子Micah就坐在我旁边,他看了看然后说:“这个循环最多只应做到n平方根。”我惭愧的意识到这一定是导致线性阶的原因。这个循环本应该在它刚到n平方根的时候就结束了的,可却陷入了无用的线性迭代之中一直到n。

这个简单的改变应该不仅仅能在采样图表上展现出原本的曲线形状,算法的性能也应能提高不少。如下:

require 'benchmark'
def sievePerformance(n)
  r = Benchmark.realtime() do 
    sieve = Array.new(n,true)
    sieve[0..1] = [false,false]
    
    2.upto(Integer(Math.sqrt(n)) do |i|
      if sieve 
        (2*i).step(n,i) do |j|
          sieve[j] = false
        end
      end
    end
  end
  r

我把这两幅采样图表拼接在了一起,如下:

真令人失望。首先,在图上的sqrt(n)没有展现出曲线来;其次,sqrt(n)的性能仅仅是原先的两倍!一个函数的外循环上限在指数级别上变为的一半(即原来的平方根),可是速度的提升却怎能只有2倍?

随着我对这个算法理解的加深,我认识到外层循环的迭代次数的增加,内层循环所耗用时间会因为两个因素而减少。首先,步长增大了;其次,在筛选过程中出现了更多的'false'值,因此判断语句会更少频率的被执行。这两个导致时间耗用降低的因素一定是导致算法保持线性阶的某种平衡因素。

我不是计算机科学家,而且对鉴别这个算法到底是线性与否的数学问题我也不是非常感兴趣。谁能猜出当外部循环的范围缩小到原来上限值的平方根而性能却只有2倍增长的原因?谁能猜到算法本身竟然是线性阶的?!


六年前,当大家刚开始沉迷于XP的时候,Kent Beck(译注3)要在一组学生(大概30个左右)前示意一个算法,我就为他写了这个埃拉托色尼质数过滤算法的Java例程。我惊讶的看到他从函数中把n的平方根删掉,并替换成了n。他说“我不知道这是不是真的能让算法加快,不管如何,把上限设为n使得可读性更好。”于是,他删掉了这个特别的注释,那是我在平方根周围注释来解释为何不把上限设为n的聪明之处。

那时我眼珠子乱转而且还在一旁偷偷傻笑。我确信,如果n很大的时候,上限是n平方根会让算法的效率在数量级上大于n的,我还深信n每扩大一百倍,它所耗费的时间只会随之增加大概十倍。六年后(昨晚),我终于知道了程序的结果,而且知道了增幅是2倍线性阶的,而对此Kent一直都是对的。

译注:

1,strstream,标准C/C++的字符串流类,派生自iostream。因性能问题,C++标准委员会做了修补,用stringstream替换之,因此也不建议再使用strstream。

2,复杂度(本文指时间复杂度),以算法中基本运算的重复执行次数作为算法时间复杂度的时间量度,并以符号O(x)来表示。通常,时间复杂度由小到大分为几个等级,a)常量阶 O(c),b)对数阶 O(log2n),c)线性阶 O(n),d)多项式阶 O(nm)等

3,Kent Beck,是软件开发方法学的泰斗、XP的创始人,长期致力于软件工程的理论研究和实践,并具有讲授XP的丰富经验。作为软件业内最富创造,哇和最有口碑的领导人之一,KentBeck极力推崇模式、极限编程和测试驱动开发。他现在加盟于ThreeRivers研究所,是多部畅销书如《Smalltalk Best PracticePatterns》、《解析极限编程——拥抱变化》和《规划极限编程》(和Martin Fowler合著)的作者,并且是超级畅销书《重构——改善既有代码的设计》(中国电力出版社出版中英文版)的特约撰稿人。

 (原文链接网址:http://www.butunclebob.com/ArticleS.UncleBob.PerformanceTuning; Robert C. Martin的英文blog网址: http://www.butunclebob.com/ArticleS.UncleBob 

作者简介:Robert C. MartinObject Mentor公司总裁,面向对象设计、模式、UML、敏捷方法学和极限编程领域内的资深顾问。他不仅是Jolt获奖图书《敏捷软件开发:原则、模式与实践》(中文版)(《敏捷软件开发》(英文影印版))的作者,还是畅销书Designing Object-Oriented C++ Applications Using the Booch Method的作者。MartinPattern Languages of Program Design 3More C++ Gems的主编,并与James Newkirk合著了XP in Practice。他是国际程序员大会上著名的发言人,并在C++ Report杂志担任过4年的编辑。

QQ: 378890364 微信:wwtree(省短信费) 紧急事宜发短信到0061432027638  本站微博:http://t.qq.com/wwtree QQ群:122538123
级别: 管理员
发帖
8532
金币
2762
威望
3231
贡献值
0
元宝
0
只看该作者 4楼 发表于: 2010-10-11
最基本的代码优化技术
Dr. Dobb’s Blogger的Walter Bright曾写了一篇博文《Overlooked Essentials For Optimizing Code》,为我们总结了两个最容易被人忽略的基本代码优化技术。酷壳个人网站版主陈皓对本文进行了翻译,现转载于此,供大家学习。全文如下:


我编写程序至今有35年了,我做了很多关于程序执行速度方面优化的工(一个示例),我也看过其它人做的优化。我发现有两个最基本的优化技术总是被人所忽略。
注意,这两个技术并不是避免时机不成熟的优化。并不是把冒泡排序变成快速排序(算法优化)。也不是语言或是编译器的优化。也不是把 i*4写成i<<2 的优化。
这两个技术是:
使用 一个profiler。
查看程序执行时的汇编码。
使用这两个技术的人将会成功地写出运行快的代码,不会使用这两个技术的人则不行。下面让我为你细细道来。
使用一个 Profiler
我们知道,程序运行时的90%的时间是用在了10%的代码上。我发现这并不准确。一次又一次地,我发现,几乎所有的程序会在1%的代码上花了99% 的运行时间。但是,是哪个1%?一个好的Profiler可以告诉你这个答案。就算我们需要使用100个小时在这1%的代码上进行优化,也比使用100个 小时在其它99%的代码上优化产生的效益要高得多得多。


问题是什么?人们不用profiler?不是。我工作过的一个地方使用了一个华丽而奢侈的Profiler,但是自从购买这个Profiler后, 它的包装3年来还是那么的暂新。为什么人们不用?我真的不知道。有一次,我和我的同事去了一个负载过大的交易所,我同事坚持说他知道哪里是瓶颈,毕竟,他是一个很有经验的专家。最终,我把我的Profiler在他的项目上运行了一下,我们发现那个瓶颈完全在一个意想不到的地方。


就像是赛车一样。团队是赢在传感器和日志上,这些东西提供了所有的一切。你可以调整一下赛车手的裤子以让其在比赛过程中更舒服,但是这不会让你赢得 比赛,也不会让你更有竞争力。如果你不知道你的速度上不去是因为引擎、排气装置、空体动力学、轮胎气压,或是赛车手,那么你将无法获胜。编程为什么会不同呢?只要没有测量,你就永远无法进步。


这个世界上有太多可以使用的Profiler了。随便找一个你就可以看到你的函数的调用层次,调用的次数,以前每条代码的时间分解表(甚至可以到汇编级)。我看过太多的程序员回避使用Profiler,而是把时间花在那些无用的,错误的方向上的“优化”,而被其竞争对手所羞辱。(译者陈皓注:使用Profiler时,重点需要关注:1)花时间多的函数以优化其算法,2)调用次数巨多的函数——如果一个函数每秒被调用300K次,你只需要优化出0.001毫秒,那也是相当大的优化。这就是作者所谓的1%的代码占用了99%的CPU时间)


查看汇编代码
几年前,我有一个同事,Mary Bailey,她在华盛顿大学教矫正代数(remedial algebra),有一次,她在黑板上写下:
x + 3 = 5
然后问他的学生“求解x”,然后学生们不知道答案。于是她写下:
__ + 3 = 5
然后,再问学生“填空”,所有的学生都可以回答了。未知数x就像是一个有魔法的字母让大家都在想“x意味着代数,而我没有学过代数,所以我就不知道这个怎么做”。
汇编程序就是编程世界的代数。如果某人问我“inline函数是否被编译器展开了?”或是问我“如果我写下i*4,编译器会把其优化为左移位操作吗?”。这个时候,我都会建议他们看看编译器的汇编码。这样的回答是不是很粗暴和无用?通常,在我这样回答了提问者后,提问都通常都会说,对不起,我不知道什么是汇编!甚至C++的专家都会这么回答。
汇编语言是最简单的编程语言了(就算是和C++相比也是这样的),如:
ADD ESI,x
就是(C风格的代码)
ESI += x;
而:
CALL foo
则是:
foo();


细节因为CPU的种类而不同,但这就是其如何工作的。有时候,我们甚至都不需要细节,只需要看看汇编码的长啥样,然后和源代码比一比,你就可以知道汇编代码很多很多了。


那么,这又如何帮助代码优化?举个例子,我几年前认识一个程序员认为他应该去发现一个新的更快的算法。他有一个benchmark来证明这个算法,并且其写了一篇非常漂亮的文章关于他的这个算法。但是,有人看了一下其原来算法以及新算法的汇编,发现了他的改进版本的算法允许其编译器把两个除法操作变 成了一个。这和算法真的没有什么关系。我们知道除法操作是一个很昂贵的操作,并且在其算法中,这俩个除法操作还在一个内嵌循环中,所以,他的改进版的算法当然要快一些。但,只需要在原来的算法上做一点点小的改动——使用一个除法操作,那么其原来的算法将会和新的一样快。而他的新发现什么也不是。


下一个例子,一个D用户张贴了一个 benchmark 来显示 dmd (Digital Mars D 编译器)在整型算法上的很糟糕,而ldc (LLVM D 编译器) 就好很多了。对于这样的结果,其相当的有意见。我迅速地看了一下汇编,发现两个编译器编译出来相当的一致,并没有什么明显的东西要对2:1这么大的不同而 负责。但是我们看到有一个对long型整数的除法,这个除法调用了运行库。而这个库成为消耗时间的杀手,其它所有的加减法都没有速度上的影响。出乎意料 地,benchmark 和算法代码生成一点关系也没有,完全就是long型整数的除法的问题。这暴露了在dmd的运行库中的long型除法的实现很差。修正后就可以提高速度。所 以,这和编译器没有什么关系,但是如果不看汇编,你将无法发现这一切。


查看汇编代码经常会给你一些意想不到的东西让你知道为什么程序的性能是那样。一些意想不到的函数调用,预料不到的自傲,以及不应该存在的东西,等等其实所有的一切。但也不需要成为一个汇编代码的黑客才能干的事。


结论
如果你觉得需要程序有更好的执行速度,那么,最基本的方法就是使用一个profiler和愿意去查看一下其汇编代码以找到程序的瓶颈。只有找到了程序的瓶颈,此时才是真正在思考如何去改进的时候,比如思考一个更好的算法,使用更快的语言优化,等等。


常规的做法是制胜法宝是挑选一个最佳的算法而不是进行微优化。虽然这种做法是无可异议的,但是有两件事情是学校没有教给你而需要你重点注意的。第一 个也是最重要的,如果你优化的算法没没有参与到你程序性能中的算法,那么你优化他只是在浪费时间和精力,并且还转移了你的注意力让你错过了应该要去优化的部分。第二点,算法的性能总和处理的数据密切相关的,就算是冒泡排序有那么多的笑柄,但是如果其处理的数据基本是排好序的,只有其中几个数据是未排序的, 那么冒泡排序也是所有排序算法里性能最好的。所以,担心没有使用好的算法而不去测量,只会浪费时间,无论是你的还是计算机的。




就好像赛车零件的订购速底是不会让你更靠进冠军(就算是你正确安装零件也不会),没有Profiler,你不会知道问题在哪里,不去看汇编,你可能知道问题所在,但你往往不知道为什么。
原文链接:Overlooked Essentials For Optimizing Code
译文链接:http://coolshell.cn/articles/2967.html

Overlooked Essentials For Optimizing Code


Sep 10, 2010
I've been programming for 35 years now, and I've done a lot of work optimizing programs for speed (an example), and watching others optimize. Two essential techniques are consistently ignored.
Nope, it isn't avoiding premature optimization. It isn't replacing bubble sort with quicksort (i.e. algorithmic improvements). It's not what language used, nor is it how good the compiler is. It isn't writing i<<2 instead of i*4.
It is:
Using a profiler
Looking at the assembly code being executed
The people who do those are successful in writing fast code, the ones who do not are not. Let me explain.

Using A Profiler


The old programming saw is that a program spends 90% of its time in 10% of the code. I've found that to not be true. Over and over, I've found that programs spends 99% of its time in 1% of the code. But which 1%? A profiler will tell you. Spending 100 hours of dev time on that 1% will yield real benefits, while 100 hours on the other 99% will not produce much of anything worthwhile.
What's the problem? Don't people use profilers? Nope. One place I worked at had a fancy expensive profiler that was still in its shrink wrap 3 years after purchase. Why don't people use profilers? I don't really know. I once got into a heated exchange with a colleague who insisted he knew where the bottlenecks were; after all, he was an experienced professional. I finally ran the profiler myself on his project, and of course the bottleneck was in a completely unexpected place.
Consider auto racing. The team that wins has sensors and logging on just about everything they can stick a sensor on. You can race using seat-of-the-pants tuning and have a jolly good time on the track, but you won't win and you won't even be competitive. You won't know if your poor speeds are caused by the engine, the exhaust, the aerodynamics, the tire pressure, or the driver. Why should programming be any different? You can't improve what you can't measure.
There are lots of profilers available. You can get ones that look at the hierarchy of function calls, function times, times broken down for each statement, and even at the instruction level. I've seen too many programmers eschew profilers, preferring instead to whittle away their time with useless and misdirected "optimizations" and getting trounced by their competitors.

Looking At The Assembly Code


Years ago, I had a colleague, Mary Bailey, who taught remedial algebra at the University of Washington. She told me once that when she wrote on the board:
x + 3 = 5
and asked her students to "solve for x", they couldn't answer. But, if she wrote:
__ + 3 = 5
and asked the students to "fill in the blank" all of them could do it. It seems that the magic word "x" seemed to cause them to reflexively think "x means algebra, I don't understand algebra, I can't do this."
Assembler is the algebra of the programming world. If someone asks me "was my function inlined by the compiler" or "if I write i*4, will the compiler optimize it to a left shift" I'll suggest they look at the asm output of the compiler. The reaction is how rude and unhelpful could I be? The person will follow up by saying he doesn't know assembler. Even C++ experts will say this.
Assembler is the simplest language (especially compared with C++!). For example,
ADD ESI,x
is (expressed in C style):
ESI += x;
and:
CALL foo
is:
foo();
Details vary among CPUs, but that's how it works. It's not even really necessary to know that. Just looking at the assembler output and comparing it to the source code will tell a LOT.
How does this help optimization? For example, I knew a programmer years ago who thought he'd discovered a new, faster algorithm to do X. I'm being deliberately vague to protect him. He had the benchmarks to prove it, and wrote a nice article about it. But then someone looked at the assembler output of the regular way, and his new fast way. It turns out that the way he'd written his improved version had allowed the compiler to replace two DIV instructions with one. This had really nothing to do with his algorithm. But DIV is an expensive instruction, and this was in the inner loop, and so his algorithm appeared to be faster. The regular implementation could also be recoded slightly to use only one DIV, too, and it would perform just as fast as the new algorithm. He had discovered nothing.
For my next example, a D user posted a benchmark showing that dmd (Digital Mars D compiler) was lousy at integer arithmetic, while ldc (LLVM D compiler) was much better. Being very concerned about such a result, I promptly looked at the assembler output. It was pretty much equivalent, nothing stood out as being accountable for a 2:1 difference. But there was a long divide in there, done with a call to a runtime library function. That function call completely dominated the timing results, all the adds and subtracts in the benchmark had no significant impact on the speed. Unexpectedly, the benchmark wasn't about arithmetic code generation at all, it was about long division only. It turns out that dmd's runtime library function had a crummy implementation of long division in it. Fixing that brought the speed up to par. It wasn't the code generation at fault at all, but this was not discoverable without looking at the assembler.
Looking at the assembler often gives unexpected insight into why a program performs as it does. Unexpected function calls, unanticipated bloat, things that shouldn't be there, etc., all are exposed when looking at it. It isn't necessary to be an assembler crackerjack to be able to pick that up.
Conclusion


If you feel the need for speed, the way to get it is to use a profiler and be willing to examine the assembler for the bottlenecks. Only then is it time to think about better algorithms, faster languages, etc.
Conventional wisdom has it that choosing the best algorithm trumps any micro-optimizations. Though that is undeniably true, there are two caveats that don't get taught in schools. First and most importantly, choosing the best algorithm for a part of the program that has no participation to the performance profile has a negative effect on optimization because it wastes your time that could be better invested in making actual progress, and diverts attention from the parts that matter. Second, algorithms' performance always varies with the statistics of the data they operate on. Even bubble sort, the butt of all jokes, is still the best on almost-sorted data that has only a few unordered items. So worrying about using good algorithms without measuring where they matter is a waste of time - your's and computer's.
Just like ordering speed parts from an auto racing catalog isn't going to put you anywhere near the winner's circle (even if you get them installed right), without profiling, you won't know where the problems are without a profiler. Without looking at the assembler, you may know where the problem is, but often won't know why.
Thanks to Bartosz Milewski, David Held, and Andrei Alexandrescu for their helpful comments on a draft of this.
QQ: 378890364 微信:wwtree(省短信费) 紧急事宜发短信到0061432027638  本站微博:http://t.qq.com/wwtree QQ群:122538123
级别: 管理员
发帖
8532
金币
2762
威望
3231
贡献值
0
元宝
0
只看该作者 5楼 发表于: 2011-06-10
Google推出C++基准性能测试

Google推出 C++ Go Java Scala的基准性能测试,结果依次是:C++ Go Scala Java ,报告显示,C++提供了最快的运行性能,报告也认为性能微调努力付出是高昂的。
Go没有这些微调的限制,但是它太年轻,Go编译时间快于Java Scala,Java Scala是编译到Java字节码,而C++和Go编译到机器码,该报告并没有测试并发性能。

Scala性能要快于Java,报告推出时也恰逢Scala Day,所以对Scala有特别意义。
QQ: 378890364 微信:wwtree(省短信费) 紧急事宜发短信到0061432027638  本站微博:http://t.qq.com/wwtree QQ群:122538123
级别: 管理员
发帖
8532
金币
2762
威望
3231
贡献值
0
元宝
0
只看该作者 6楼 发表于: 2011-09-16
算法优化

朋友曾经给我推荐了一个有关代码优化的pdf文档《让你的软件飞起来》,看完之后,感受颇深。为了推广其,同时也为了自己加深印象,故将其总结为word文档。下面就是其的详细内容总结,希望能于己于人都有所帮助。

速度取决于算法
同样的事情,方法不一样,效果也不一样。比如,汽车引擎,可以让你的速度超越马车,却无法超越音速;涡轮引擎,可以轻松 超越音障,却无法飞出地球;如果有火箭发动机,就可以到达火星。

代码的运算速度取决于以下几个方面
1、  算法本身的复杂度,比如MPEGJPEG复杂,JPEGBMP图片的编码复杂。
2、  CPU自身的速度和设计架构
3、  CPU的总线带宽
4、  您自己代码的写法
本文主要介绍如何优化您自己的code,实现软件的加速。

先看看我的需求
我们一个图象模式识别的项目,需要将RGB格式的彩色图像先转换成黑白图像。
图像转换的公式如下:
Y = 0.299 * R + 0.587 * G + 0.114 * B;
图像尺寸640*480*24bitRGB图像已经按照RGBRGB顺序排列的格式,放在内存里面了。

我已经悄悄的完成了第一个优化
以下是输入和输出的定义:
#define XSIZE 640
#define YSIZE 480
#define IMGSIZE XSIZE * YSIZE
typedef struct RGB
{
       unsigned char R;
       unsigned char G;
       unsigned char B;
}RGB;
struct RGB in[IMGSIZE]; //需要计算的原始数据
unsigned char out[IMGSIZE]; //计算后的结果

第一个优化
优化原则:图像是一个2D数组,我用一个一维数组来存储。编译器处理一维数组的效率要高过二维数组。

先写一个代码:
Y = 0.299 * R + 0.587 * G + 0.114 * B;

void calc_lum()
{
    int i;
    for(i = 0; i < IMGSIZE; i++)
    {
       double r,g,b,y;
       unsigned char yy;
        r = in.r;
        g = in.g;
        b = in.b;
        y = 0.299 * r + 0.587 * g + 0.114 * b;
        yy = y;
        out = yy;
    }
}
这大概是能想得出来的最简单的写法了,实在看不出有什么毛病,好了,编译一下跑一跑吧。
第一次试跑
这个代码分别用vc6.0gcc编译,生成2个版本,分别在pc上和我的embedded system上面跑。
速度多少?
PC上,由于存在硬件浮点处理器,CPU频率也够高,计算速度为20秒。
我的embedded system,没有以上2个优势,浮点操作被编译器分解成了整数运算,运算速度为120秒左右。

去掉浮点运算
上面这个代码还没有跑,我已经知道会很慢了,因为这其中有大量的浮点运算。只要能不用浮点运算,一定能快很多。

Y = 0.299 * R + 0.587 * G + 0.114 * B;
这个公式怎么能用定点的整数运算替代呢?
0.299 * R可以如何化简?
Y = 0.299 * R + 0.587 * G + 0.114 * B;
Y = D + E + F;
D = 0.299 * R;
E = 0.587 * G;
F = 0.114 * B;
我们就先简化算式D吧!
RGB的取值范围都是0~255,都是整数,只是这个系数比较麻烦,不过这个系数可以表示为:0.299 = 299 / 1000;
所以 D = ( R * 299) / 1000;
Y = (R * 299 + G * 587 + B * 114) / 1000;

这一下,能快多少呢?
Embedded system上的速度为45秒;
PC上的速度为2秒;
0.299 * R可以如何化简
Y = 0.299 * R + 0.587 * G + 0.114 * B;
Y = (R * 299 + G * 587 + B * 114) / 1000;
这个式子好像还有点复杂,可以再砍掉一个除法运算。
前面的算式D可以这样写:
0.299=299/1000=1224/4096
所以 D = (R * 1224) / 4096
Y=(R*1224)/4096+(G*2404)/4096+(B*467)/4096
再简化为:
Y=(R*1224+G*2404+B*467)/4096
这里的/4096除法,因为它是2N次方,所以可以用移位操作替代,往右移位12bit就是把某个数除以4096了。

void calc_lum()
{
    int i;
    for(i = 0; i < IMGSIZE; i++)
    {
       int r,g,b,y;
        r = 1224 * in.r;
        g = 2404 * in.g;
        b = 467 * in.b;
        y = r + g + b;
        y = y >> 12; //这里去掉了除法运算
        out = y;
    }
}
这个代码编译后,又快了20%
虽然快了不少,还是太慢了一些,20秒处理一幅图像,地球人都不能接受。

仔细端详一下这个式子!
Y = 0.299 * R + 0.587 * G + 0.114 * B;
Y=D+E+F;
D=0.299*R;
E=0.587*G;
F=0.114*B;

RGB的取值有文章可做,RGB的取值永远都大于等于,小于等于255,我们能不能将DEF都预先计算好呢?然后用查表算法计算呢?
我们使用3个数组分别存放DEF256种可能的取值,然后。。。

查表数组初始化
int D[256],F[256],E[256];
void table_init()
{
    int i;
    for(i=0;i<256;i++)
    {
        D=i*1224;
        D=D>>12;
        E=i*2404;
        E=E>>12;
        F=i*467;
        F=F>>12;
    }
}
void calc_lum()
{
    int i;
    for(i = 0; i < IMGSIZE; i++)
    {
       int r,g,b,y;
        r = D[in.r];//查表
        g = E[in.g];
        b = F[in.b];
        y = r + g + b;
        out = y;
    }
}

这一次的成绩把我吓出一身冷汗,执行时间居然从30秒一下提高到了2秒!在PC上测试这段代码,眼皮还没眨一下,代码就执行完了。一下提高15倍,爽不爽?
继续优化
很多embedded system32bit CPU,都至少有2ALU,能不能让2ALU都跑起来?

void calc_lum()
{
    int i;
    for(i = 0; i < IMGSIZE; i += 2) //一次并行处理2个数据
    {
       int r,g,b,y,r1,g1,b1,y1;
        r = D[in.r];//查表 //这里给第一个ALU执行
        g = E[in.g];
        b = F[in.b];
        y = r + g + b;
        out = y;
        r1 = D[in[i + 1].r];//查表 //这里给第二个ALU执行
        g1 = E[in[i + 1].g];
        b1 = F[in[i + 1].b];
        y = r1 + g1 + b1;
        out[i + 1] = y;
    }
}
2ALU处理的数据不能有数据依赖,也就是说:某个ALU的输入条件不能是别的ALU的输出,这样才可以并行。
这次成绩是1秒。

查看这个代码
int D[256],F[256],E[256]; //查表数组
void table_init()
{
    int i;
    for(i=0;i<256;i++)
    {
        D=i*1224;
        D=D>>12;
        E=i*2404;
        E=E>>12;
        F=i*467;
        F=F>>12;
    }
}
到这里,似乎已经足够快了,但是我们反复实验,发现,还有办法再快!
可以将int D[256],F[256],E[256]; //查表数组
更改为
unsigned short D[256],F[256],E[256]; //查表数组

这是因为编译器处理int类型和处理unsigned short类型的效率不一样。
再改动
inline void calc_lum()
{
    int i;
    for(i = 0; i < IMGSIZE; i += 2) //一次并行处理2个数据
    {
       int r,g,b,y,r1,g1,b1,y1;
        r = D[in.r];//查表 //这里给第一个ALU执行
        g = E[in.g];
        b = F[in.b];
        y = r + g + b;
        out = y;
        r1 = D[in[i + 1].r];//查表 //这里给第二个ALU执行
        g1 = E[in[i + 1].g];
        b1 = F[in[i + 1].b];
        y = r1 + g1 + b1;
        out[i + 1] = y;
    }
}
将函数声明为inline,这样编译器就会将其嵌入到母函数中,可以减少CPU调用子函数所产生的开销。
这次速度:0.5秒。

其实,我们还可以飞出地球的!
如果加上以下措施,应该还可以更快:
1、  把查表的数据放置在CPU的高速数据CACHE里面;
2、  把函数calc_lum()用汇编语言来写

其实,CPU的潜力是很大的
1、  不要抱怨你的CPU,记住一句话:“只要功率足够,砖头都能飞!”
2、  同样的需求,写法不一样,速度可以从120秒变化为0.5秒,说明CPU的潜能是很大的!看你如何去挖掘。
3、  我想:要是Microsoft的工程师都像我这样优化代码,我大概就可以用489windows XP了!

以上就是对《让你的软件飞起来》的摘录,下面,我将按照这位牛人的介绍,对RGBYCbCr的转换算法做以总结。

Y =   0.299R + 0.587G + 0.114B
U = -0.147R - 0.289G + 0.436B
V =  0.615R - 0.515G - 0.100B



#deinfe SIZE 256
#define XSIZE 640
#define YSIZE 480
#define IMGSIZE XSIZE * YSIZE
typedef struct RGB
{
       unsigned char r;
       unsigned char g;
       unsigned char b;
}RGB;
struct RGB in[IMGSIZE]; //需要计算的原始数据
unsigned char out[IMGSIZE * 3]; //计算后的结果

unsigned short Y_R[SIZE],Y_G[SIZE],Y_B[SIZE],U_R[SIZE],U_G[SIZE],U_B[SIZE],V_R[SIZE],V_G[SIZE],V_B[SIZE]; //查表数组
void table_init()
{
    int i;
    for(i = 0; i < SIZE; i++)
    {
        Y_R = (i * 1224) >> 12; //Y对应的查表数组
        Y_G = (i * 2404) >> 12;
        Y_B = (i * 467)  >> 12;
        U_R = (i * 602)  >> 12; //U对应的查表数组
        U_G = (i * 1183) >> 12;
        U_B = (i * 1785) >> 12;
        V_R = (i * 2519) >> 12; //V对应的查表数组
        V_G = (i * 2109) >> 12;
        V_B = (i * 409)  >> 12;
    }
}

inline void calc_lum()
{
    int i;
    for(i = 0; i < IMGSIZE; i += 2) //一次并行处理2个数据
    {    
        out               = Y_R[in.r] + Y_G[in.g] + Y_B[in.b]; //Y
        out[i + IMGSIZE]     = U_B[in.b] - U_R[in.r] - U_G[in.g]; //U
        out[i + 2 * IMGSIZE] = V_R[in.r] - V_G[in.g] - V_B[in.b]; //V
        out[i + 1]                = Y_R[in[i + 1].r] + Y_G[in[i + 1].g] + Y_B[in[i + 1].b]; //Y
        out[i  + 1 + IMGSIZE]     = U_B[in[i + 1].b] - U_R[in[i + 1].r] - U_G[in[i + 1].g]; //U
        out[i  + 1 + 2 * IMGSIZE] = V_R[in[i + 1].r] - V_G[in[i + 1].g] - V_B[in[i + 1].b]; //V
    }
}

根据牛人的观点,这种算法应该是非常快的了,以后可直接使用了。
QQ: 378890364 微信:wwtree(省短信费) 紧急事宜发短信到0061432027638  本站微博:http://t.qq.com/wwtree QQ群:122538123
级别: 管理员
发帖
8532
金币
2762
威望
3231
贡献值
0
元宝
0
只看该作者 7楼 发表于: 2011-10-21
C/C++与各种语言的速度比较
以下比较均是在同一台计算机上进行的,在其他计算机上结果会有所不同。


1 Lu与C/C++、Forcal、Lua的数值计算速度比较


    C/C++代码:


z=0.0;
for(x=0.0;x<=1.0;x=x+0.0011)
{
  for(y=1.0;y<=2.0;y=y+0.0011)
  {
    z=z+cos(1.0-sin(1.2*pow(x+0.1,y/2.0-x)+cos(1.0-sin(1.2*pow(x+0.2,y/3.0-x))))-cos(1.0-sin(1.2*pow(x+0.3,y/4.0-x)))-cos(1.0-sin(1.2*pow(x+0.4,y/5.0-x)+cos(1.0-sin(1.2*pow(x+0.5,y/6.0-x))))-cos(1.0-sin(1.2*pow(x+0.6,y/7.0-x)))));
  }
}


    以上C/C++代码运行结果:z=19160.536601703152,耗时约1.328秒。


    Forcal计算结果z=19160.536601703152,耗时约1.828秒。


    Lua代码:


view plain
function f(x,y)  
    return math.cos(1-math.sin(1.2*(x+0.1)^(y/2-x)+math.cos(1-math.sin(1.2*(x+0.2)^(y/3-x))))-math.cos(1-  
math.sin(1.2*(x+0.3)^(y/4-x)))-math.cos(1-math.sin(1.2*(x+0.4)^(y/5-x)+math.cos(1-math.sin(1.2*(x+0.5)^(y/6-x))))-  
math.cos(1-math.sin(1.2*(x+0.6)^(y/7-x)))))  
end  
  
function z()  
    local t = os.clock()  
  
    local x=0  
    local y=0  
    local z=0  
    for x=0,1,0.0011 do  
        for y=1,2,0.0011 do      
            z=z+f(x,y)  
        end  
  
    end  
    io.write(z)  
  
    io.write(string.format(" Time Elapsed %f\n", os.clock() - t))  
end  
  
z()  


    Lua运行结果:


19160.536601703 Time Elapsed 3.234000


    Lu代码:


main(:x,y,z,t)=
{
  t=clock(), z=0.0, x=0.0,
  while{x<=1.0,
    y=1.0,
    while{y<=2.0,
      z=z+cos(1.0-sin(1.2*(x+0.1)^(y/2.0-x)+cos(1.0-sin(1.2*(x+0.2)^(y/3.0-x))))-cos(1.0-sin(1.2*(x+0.3)^(y/4.0-x)))-cos(1.0-sin(1.2*(x+0.4)^(y/5.0-x)+cos(1.0-sin(1.2*(x+0.5)^(y/6.0-x))))-cos(1.0-sin(1.2*(x+0.6)^(y/7.0-x))))),
      y=y+0.0011
    },
    x=x+0.0011
  },
  o{"z=",z,",耗时约",[clock()-t]/1000.0,"秒。\r\n"}
};


    Lu运行结果:


z=19160.536601703152,耗时约2.656秒。


2 八皇后问题


    据测定,以下八皇后问题,Lu的运行速度约为C++的1/23,而Forcal的运行速度约为C++的1/10。


// 在运行不同的程序时,Lu的速度,从接近C++到只有C++速度的几十分之一。
// Lu的建议是:对运行时间较长的程序,如确有必要,设计成二级函数由Lu调用,从而获得接近C++速度的性能。
// Lu与C++是无缝链接的。故C++能实现的功能,借助二级函数,Lu完全可以实现。
// 但没有Lu支持的C++程序,将无法获得高效率地实时编译计算字符串表达式的功能。


// 据测定,以下八皇后问题,Lu的运行速度约为C++的1/23。
// 八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。
// 该问题是19世纪著名的数学家高斯1850年提出:在8×8格的国际象棋盘上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
// 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。
// 以下算法是从网上搜来的,该算法没有最终给出排列组合,仅仅给出有多少种组合,但是算法确实十分奥妙。


//Lu源程序
(::sum,upperlim)= sum=0, upperlim=1, SetStackMax(1000);
test(row, ld, rd : pos,p : sum,upperlim)=
{
    which
    {
        row != upperlim,
        {
            pos = {upperlim && [!!(row||ld||rd)]},
            while{ pos,
                p = pos&&(-pos),
                pos = pos -p,
                test[row+p, (ld+p)<<1, (rd+p)>>1]
            }
        },
        sum++
    }
};
main(:tm,n:sum,upperlim)=
{
    tm=clock(), n=15,
    upperlim=(upperlim<<n)-1,
    test(0,0,0),
    o["Queens=",n,",sum=",sum,",耗时约",[clock()-tm]/1000.0,"秒。\r\n"]
};


Lu运行结果:


    Queens=15,sum=2279184,耗时约136.703秒。


完成相同功能的C++程序:


#include <stdio.h>
#include <stdlib.h>
#include <time.h>


long sum=0,upperlim=1;


void test(long row, long ld, long rd)
{
    if (row != upperlim)
        {
            long pos = upperlim & ~(row | ld | rd);
            while (pos){
                long p = pos& -pos;
                pos -= p;
                test(row+p, (ld+p)<<1, (rd+p)>>1);
            }
        }
    else
        sum++;
}


int main(int argc, char *argv[])
{
    time_t tm;
    int n=15;


    if(argc!=1)n=atoi(argv[1]);
    tm=time(0);
    if((n<1)||(n>32))
    {
        printf(" heh..I can’t calculate that.\n");
        exit(-1);
    }
    printf("%d Queens\n",n);
    upperlim=(upperlim<<n)-1;


    test(0,0,0);
    printf("Number of solutions is %ld, %d seconds\n", sum,(int)(time(0)-tm));
}


    VC运行结果:


15 Queens
Number of solutions is 2279184, 6 seconds


3 Matlab与Lu普通函数调用效率


    Matlab 2009a的测试代码:


f=@(x,y,z,t)x+y+z;
tic;
s=0;
for x=0:1000
    for y=0:100
        for z=0:100
            s=s+f(x,y,z);
        end
    end
end
s
toc


s =


6.126720600000000e+009


Elapsed time is 9.546717 seconds.


    将函数写成m文件后效率会提高,如下例:


%file xyz.m
function c=xyz(x,y,z)
c=x+y+z;
end


    测试代码:


tic;
s=0;
for x=0:1000
    for y=0:100
        for z=0:100
            s=s+xyz(x,y,z);
        end
    end
end
s
toc


s =


6.126720600000000e+009


Elapsed time is 4.724592 seconds.


    Lu代码:


f(x,y,z)=x+y+z;
main(:t,s,x,y,z)=
t=clock(),
s=0,
x=0, while{x<=1000,
    y=0, while{y<=100,
        z=0, while{z<=100,
            s=s+f(x,y,z),
            z++
        },
        y++
    },
    x++
},
o{"s=",s,", time=",[clock()-t]/1000.};


    Lu运行结果:


s=6126720600, time=4.015


4 Matlab与Lu的递归函数调用效率


    以Fibonacci递归程序为例进行比较。


    Matlab 2009a的Fibonacci函数定义:


function k=fib(n)


if n == 0
    k=0;
    return;
else if n == 1
    k=1;
    return;
else
    k=fib(n - 1) + fib(n - 2);
    return;
end


end


    运行结果:


tic;
fib(30)
toc


ans =


    832040


Elapsed time is 26.315245 seconds.


    Lu的Fibonacci函数及代码:


SetStackMax(1000);
F(n)= which{
    n == 0,
        return(0),
    n == 1,
        return(1),
    return [F(n - 1) + F(n - 2)]
};
main(:t)= t=clock(), o{"F(30)=",F(30),", time=",[clock()-t]/1000.};


    Lu运行结果:


F(30)=832040, time=0.875


5 变步长辛卜生二重求积法


    C/C++代码:


#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include "time.h"
#include "math.h"


double simp1(double x,double eps);
void fsim2s(double x,double y[]);
double fsim2f(double x,double y);


double fsim2(double a,double b,double eps)
{
    int n,j;
    double h,d,s1,s2,t1,x,t2,g,s,s0,ep;


    n=1; h=0.5*(b-a);
    d=fabs((b-a)*1.0e-06);
    s1=simp1(a,eps); s2=simp1(b,eps);
    t1=h*(s1+s2);
    s0=1.0e+35; ep=1.0+eps;
    while (((ep>=eps)&&(fabs(h)>d))||(n<16))
    {
        x=a-h; t2=0.5*t1;
        for (j=1;j<=n;j++)
        {
            x=x+2.0*h;
            g=simp1(x,eps);
            t2=t2+h*g;
        }
        s=(4.0*t2-t1)/3.0;
        ep=fabs(s-s0)/(1.0+fabs(s));
        n=n+n; s0=s; t1=t2; h=h*0.5;
    }
    return(s);
}


double simp1(double x,double eps)
{
    int n,i;
    double y[2],h,d,t1,yy,t2,g,ep,g0;


    n=1;
    fsim2s(x,y);
    h=0.5*(y[1]-y[0]);
    d=fabs(h*2.0e-06);
    t1=h*(fsim2f(x,y[0])+fsim2f(x,y[1]));
    ep=1.0+eps; g0=1.0e+35;
    while (((ep>=eps)&&(fabs(h)>d))||(n<16))
    {
        yy=y[0]-h;
        t2=0.5*t1;
        for (i=1;i<=n;i++)
        {
            yy=yy+2.0*h;
            t2=t2+h*fsim2f(x,yy);
        }
        g=(4.0*t2-t1)/3.0;
        ep=fabs(g-g0)/(1.0+fabs(g));
        n=n+n; g0=g; t1=t2; h=0.5*h;
    }
    return(g);
}


void fsim2s(double x,double y[])
{
    y[0]=-sqrt(1.0-x*x);
    y[1]=-y[0];
}


double fsim2f(double x,double y)
{
    return exp(x*x+y*y);
}


int main(int argc, char *argv[])
{
    int i;
    double a,b,eps,s;
    clock_t tm;


    a=0.0; b=1.0; eps=0.0001;
    tm=clock();
    for(i=0;i<100;i++)
    {
    s=fsim2(a,b,eps);
    }
    printf("s=%e , 耗时 %d 毫秒。\n", s, (clock()-tm));
}


    C/C++结果:


    s=2.698925e+000 , 耗时 78 毫秒。


    -------


    matlab 2009a代码:


%file fsim2.m
function s=fsim2(a,b,eps)
    n=1; h=0.5*(b-a);
    d=abs((b-a)*1.0e-06);
    s1=simp1(a,eps); s2=simp1(b,eps);
    t1=h*(s1+s2);
    s0=1.0e+35; ep=1.0+eps;
    while ((ep>=eps)&&(abs(h)>d))||(n<16),
        x=a-h; t2=0.5*t1;
        for j=1:n
            x=x+2.0*h;
            g=simp1(x,eps);
            t2=t2+h*g;
        end
        s=(4.0*t2-t1)/3.0;
        ep=abs(s-s0)/(1.0+abs(s));
        n=n+n; s0=s; t1=t2; h=h*0.5;
    end
end


function g=simp1(x,eps)
    n=1;
    [y0,y1]=f2s(x);
    h=0.5*(y1-y0);
    d=abs(h*2.0e-06);
    t1=h*(f2f(x,y0)+f2f(x,y1));
    ep=1.0+eps; g0=1.0e+35;
    while (((ep>=eps)&&(abs(h)>d))||(n<16))
        yy=y0-h;
        t2=0.5*t1;
        for i=1:n
            yy=yy+2.0*h;
            t2=t2+h*f2f(x,yy);
        end
        g=(4.0*t2-t1)/3.0;
        ep=abs(g-g0)/(1.0+abs(g));
        n=n+n; g0=g; t1=t2; h=0.5*h;
    end
end


%file f2s.m
function [y0,y1]=f2s(x)
    y0=-sqrt(1.0-x*x);
    y1=-y0;
end


%file f2f.m
    function c=f2f(x,y)
    c=exp(x*x+y*y);
end


%%%%%%%%%%%%%


>> tic
for i=1:100
a=fsim2(0,1,0.0001);
end
a
toc


a =


    2.6989


Elapsed time is 0.995575 seconds.


    -------


    Lu代码:


fsim2s(x,y0,y1)=
{
    y0=-sqrt(1.0-x*x),
    y1=-y0
};
fsim2f(x,y)=exp(x*x+y*y);
//////////////////
simp1(x,eps : n,i,y0,y1,h,d,t1,yy,t2,g,ep,g0)=
{
    n=1,
    fsim2s(x,&y0,&y1),
    h=0.5*(y1-y0),
    d=abs(h*2.0e-06),
    t1=h*(fsim2f(x,y0)+fsim2f(x,y1)),
    ep=1.0+eps, g0=1.0e+35,
    while {((ep>=eps)&(abs(h)>d))|(n<16),
        yy=y0-h,
        t2=0.5*t1,
        i=1, while{i<=n,
            yy=yy+2.0*h,
            t2=t2+h*fsim2f(x,yy),
            i++
        },
        g=(4.0*t2-t1)/3.0,
        ep=abs(g-g0)/(1.0+abs(g)),
        n=n+n, g0=g, t1=t2, h=0.5*h
    },
    g
};


fsim2(a,b,eps : n,j,h,d,s1,s2,t1,x,t2,g,s,s0,ep)=
{
    n=1, h=0.5*(b-a),
    d=abs((b-a)*1.0e-06),
    s1=simp1(a,eps), s2=simp1(b,eps),
    t1=h*(s1+s2),
    s0=1.0e+35, ep=1.0+eps,
    while {((ep>=eps)&(abs(h)>d))|(n<16),
        x=a-h, t2=0.5*t1,
        j=1, while{j<=n,
            x=x+2.0*h,
            g=simp1(x,eps),
            t2=t2+h*g,
            j++
        },
        s=(4.0*t2-t1)/3.0,
        ep=abs(s-s0)/(1.0+abs(s)),
        n=n+n, s0=s, t1=t2, h=h*0.5
    },
    s
};


//////////////////


main(:t0,i,a)=
t0=clock(),
i=0, while{i<100, a=fsim2(0,1,0.0001), i++},
o{"a=",a,", time=",[clock()-t0]/1000.};


    Lu结果:


a=2.6989250006243033, time=0.657


    ---------


    本例C/C++、matlab、Lu运行耗时之比为 1:12.7:8.5 。


    =========


    以下将变步长辛卜生二重求积算法写成通用的函数。不再给出C/C++代码,因其效率不会发生变化。


    注意函数fsim2中增加了两个参数,函数句柄fsim2s用于计算二重积分时内层的上下限,函数句柄fsim2f用于计算积分函数的值。


    Matlab 2009a代码:


%file fsim2.m
function s=fsim2(a,b,eps,fsim2s,fsim2f)
    n=1; h=0.5*(b-a);
    d=abs((b-a)*1.0e-06);
    s1=simp1(a,eps,fsim2s,fsim2f); s2=simp1(b,eps,fsim2s,fsim2f);
    t1=h*(s1+s2);
    s0=1.0e+35; ep=1.0+eps;
    while ((ep>=eps)&&(abs(h)>d))||(n<16),
        x=a-h; t2=0.5*t1;
        for j=1:n
            x=x+2.0*h;
            g=simp1(x,eps,fsim2s,fsim2f);
            t2=t2+h*g;
        end
        s=(4.0*t2-t1)/3.0;
        ep=abs(s-s0)/(1.0+abs(s));
        n=n+n; s0=s; t1=t2; h=h*0.5;
    end
end


function g=simp1(x,eps,fsim2s,fsim2f)
    n=1;
    [y0,y1]=fsim2s(x);
    h=0.5*(y1-y0);
    d=abs(h*2.0e-06);
    t1=h*(fsim2f(x,y0)+fsim2f(x,y1));
    ep=1.0+eps; g0=1.0e+35;
    while (((ep>=eps)&&(abs(h)>d))||(n<16))
        yy=y0-h;
        t2=0.5*t1;
        for i=1:n
            yy=yy+2.0*h;
            t2=t2+h*fsim2f(x,yy);
        end
        g=(4.0*t2-t1)/3.0;
        ep=abs(g-g0)/(1.0+abs(g));
        n=n+n; g0=g; t1=t2; h=0.5*h;
    end
end


%file f2s.m
function [y0,y1]=f2s(x)
    y0=-sqrt(1.0-x*x);
    y1=-y0;
end


%file f2f.m
function c=f2f(x,y)
    c=exp(x*x+y*y);
end


%%%%%%%%%%%%%%%%


>> tic
for i=1:100
a=fsim2(0,1,0.0001,@f2s,@f2f);
end
a
toc


a =


    2.6989


Elapsed time is 1.267014 seconds.


    --------


    Lu代码:


simp1(x,eps,fsim2s,fsim2f : n,i,y0,y1,h,d,t1,yy,t2,g,ep,g0)=
{
    n=1,
    fsim2s(x,&y0,&y1),
    h=0.5*(y1-y0),
    d=abs(h*2.0e-06),
    t1=h*(fsim2f(x,y0)+fsim2f(x,y1)),
    ep=1.0+eps, g0=1.0e+35,
    while {((ep>=eps)&(abs(h)>d))|(n<16),
        yy=y0-h,
        t2=0.5*t1,
        i=1, while{i<=n,
            yy=yy+2.0*h,
            t2=t2+h*fsim2f(x,yy),
            i++
        },
        g=(4.0*t2-t1)/3.0,
        ep=abs(g-g0)/(1.0+abs(g)),
        n=n+n, g0=g, t1=t2, h=0.5*h
    },
    g
};


fsim2(a,b,eps,fsim2s,fsim2f : n,j,h,d,s1,s2,t1,x,t2,g,s,s0,ep)=
{
    n=1, h=0.5*(b-a),
    d=abs((b-a)*1.0e-06),
    s1=simp1(a,eps,fsim2s,fsim2f), s2=simp1(b,eps,fsim2s,fsim2f),
    t1=h*(s1+s2),
    s0=1.0e+35, ep=1.0+eps,
    while {((ep>=eps)&(abs(h)>d))|(n<16),
        x=a-h, t2=0.5*t1,
        j=1, while{j<=n,
            x=x+2.0*h,
            g=simp1(x,eps,fsim2s,fsim2f),
            t2=t2+h*g,
            j++
        },
        s=(4.0*t2-t1)/3.0,
        ep=abs(s-s0)/(1.0+abs(s)),
        n=n+n, s0=s, t1=t2, h=h*0.5
    },
    s
};


//////////////////


f2s(x,y0,y1)=
{
    y0=-sqrt(1.0-x*x),
    y1=-y0
};
f2f(x,y)=exp(x*x+y*y);


main(:t0,i,a)=
  t0=clock(),
  i=0, while{i<100, a=fsim2(0,1,0.0001,HFor("f2s"),HFor("f2f")), i++},
  o{"a=",a,", time=",[clock()-t0]/1000.};


    Lu运行结果:


a=2.6989250006243033, time=0.719


    --------


    本例matlab与Lu耗时之比为1.267014 :0.719。


6 Matlab与Lu动态内存管理效率


    matlab 2009a代码:


clear all
tic
s=0;
for k=1:1000
    for i=1:1000
        a={2,2,2,2};
        s=s+a{1};
    end
end
s
toc


s =


    2000000


Elapsed time is 5.030599 seconds.


    Lu代码:


main(:a,t0,s,k,i)=
t0=clock(),
s=0,
k=0, while{k<1000,
    i=0, while{i<1000, a=lu(2,2,2,2), s=s+a[1], i++},
    k++
},
o{"s=",s,", time=",[clock()-t0]/1000.};


    Lu运行结果:


s=2000000, time=0.703


7 Lu与VC动态数组存取效率测试


    VC源程序:


#include "stdafx.h"
#include <iostream>
#include <iomanip>
#include <math.h>
#include <time.h>


using namespace std;


int _tmain(int argc, _TCHAR* argv[])
{
    clock_t old,now;
    __int64 i,k;
    __int64 *p;
    char ch;


    old=clock();
    for(i=0,k=0;i<=1000000;i++)
    {
        p=new __int64[5];
        p[3]=i; k=k+p[3];
        delete[] p;
    }
    now=clock();
    cout<<"vc++:"<<setprecision(20)<<k;
    cout<<" 运行时间:"<<now-old<<" 即: "<<(double)(now-old)/CLOCKS_PER_SEC<<"秒"<<endl<<endl;
    cin>>ch;


    return 0;
}


    VC运行结果:


vc++:500000500000 运行时间:218 即: 0.218秒


    Lu源程序:


(:i,k,p,t)=
{   t=clock(),i=0,k=0,
    (i<=1000000).while
    {
        p=new[ints,5],
        A[p,3]=i, k=k+A[p,3],
        del[p],    //实际上在这里不需要使用del函数,去掉此语句将更快
        i++
    },
    o{"结果=",k,", 时间=",[clock()-t]/1000.,"秒。\r\n"}
};


    Lu运行结果:


结果=500000500000, 时间=0.86秒。


    在该例子中,Lu的效率为VC的0.86/0.218=3.95分之一。若将new和del这两个函数移到循环体的外边,Lu的效率如下:


    VC源程序:  


#include "stdafx.h"
#include <iostream>
#include <iomanip>
#include <math.h>
#include <time.h>




using namespace std;


int _tmain(int argc, _TCHAR* argv[])
{
    clock_t old,now;
    __int64 i,k;
    __int64 *p;
    char ch;


    old=clock(); p=new __int64 [5];
    for(i=0,k=0;i<=20000000;i++)
    {
        p[3]=i; k=k+p[3];
    }
    delete[] p; now=clock();
    cout<<"vc++:"<<setprecision(20)<<k;
    cout<<" 运行时间:"<<now-old<<" 即: "<<(double)(now-old)/CLOCKS_PER_SEC<<"秒"<<endl<<endl;
    cin>>ch;


    return 0;
}


    VC运行结果:


vc++:200000010000000 运行时间:125 即: 0.125秒


    Lu源程序:


(:i,k,p,t)=
{   t=clock(),p=new[ints,5],i=0,k=0,
    (i<=20000000).while
    {
        A[p,3]=i, k=k+A[p,3],
        i++
    },
    del[p],    //实际上在这里不需要使用del函数
    o{"结果=",k,", 时间=",[clock()-t]/1000.,"秒。\r\n"}
};


    Lu运行结果:


结果=200000010000000, 时间=7.922秒。


    在该例子中,Lu的速度为VC的7.922/0.125=63.376分之一。注意循环次数都增加到了20000000次。


8 一段有趣的程序


    在这个网页看到一篇各种语言运行速度比较的文章,摘抄如下:


— Erik Wrenholt (erik -at- timestretch.com) 2005-09-20


Language    Time         Relative Speed
C gcc-4.0.1    0.05 seconds         1.00 x
ocaml compiled 3.09.2    0.05 seconds         1.00 x
SBCL 1.0.2    0.13 seconds         2.55 x
Java 1.4.2    0.40 seconds         8.00 x
Io 20070410 Vector    1.40 seconds         28.09 x
Lua 5.1    1.50 seconds         30.00 x
ocaml bytecode 3.09.2    3.76 seconds         75.15 x
Python 2.5.1    9.99 seconds         199.80 x
Ghostscript 8.51    11.66 seconds         233.12 x
Perl 5.8.6 Optimized    12.37 seconds         247.34 x
TCL 8.4 Optimized    16.00 seconds         320.00 x
Perl 5.8.6    21.75 seconds         435.00 x
PHP 5.1.4    23.12 seconds         462.40 x
Javascript SpiderMonkey v1.6    31.06 seconds         621.27 x
Ruby 1.8.4    34.31 seconds         686.18 x
Emacs Lisp    47.25 seconds         945.00 x
Applescript    71.75 seconds         1435.00 x
Io 20070410    85.26 seconds         1705.13 x
用以上网址提供的c代码与Lu比较,c代码改写为vs 2008可接受的形式,编译运行,结果如下:
view plain
#include "stdafx.h"  
#include <math.h>  
#include <time.h>  
  
#define BAILOUT 16  
#define MAX_ITERATIONS 1000  
  
int mandelbrot(double x, double y)  
{  
    double cr = y - 0.5;  
    double ci = x;  
    double zi = 0.0;  
    double zr = 0.0;  
    int i = 0;  
  
    while(1) {  
        i ++;  
        double temp = zr * zi;  
        double zr2 = zr * zr;  
        double zi2 = zi * zi;  
        zr = zr2 - zi2 + cr;  
        zi = temp + temp + ci;  
        if (zi2 + zr2 > BAILOUT)  
            return i;  
        if (i > MAX_ITERATIONS)  
            return 0;  
    }  
      
}  
  
int _tmain (int argc, _TCHAR* argv[]) {  
  
    clock_t old,now;  
  
    old=clock();  
  
    int x,y;  
    for (y = -39; y < 39; y++) {  
        printf("\n");  
        for (x = -39; x < 39; x++) {  
            int i = mandelbrot(x/40.0, y/40.0);  
            if (i==0)  
                printf("*");  
            else  
                printf(" ");  
        }    
    }  
    printf ("\n");  
      
    now=clock();  
    double query_time = ((double)(now-old))/CLOCKS_PER_SEC;  
    printf ("C Elapsed %0.2f\n", query_time);  
    return 0;  
}  
运行结果:


view plain
                                   *  
                                   *  
                                   *  
                                   *  
                                   *  
                                  ***  
                                 *****  
                                 *****  
                                  ***  
                                   *  
                               *********  
                             *************  
                            ***************  
                         *********************  
                         *********************  
                          *******************  
                          *******************  
                          *******************  
                          *******************  
                        ***********************  
                          *******************  
                          *******************  
                         *********************  
                          *******************  
                          *******************  
                           *****************  
                            ***************  
                             *************  
                               *********  
                                   *  
                            ***************  
                        ***********************  
                     * ************************* *  
                     *****************************  
                  * ******************************* *  
                   *********************************  
                  ***********************************  
                ***************************************  
           *** ***************************************** ***  
           *************************************************  
            ***********************************************  
             *********************************************  
             *********************************************  
            ***********************************************  
            ***********************************************  
          ***************************************************  
           *************************************************  
           *************************************************  
          ***************************************************  
          ***************************************************  
     *    ***************************************************    *  
   *****  ***************************************************  *****  
   ****** *************************************************** ******  
  ******* *************************************************** *******  
***********************************************************************  
********* *************************************************** *********  
   ****** *************************************************** ******  
   *****  ***************************************************  *****  
          ***************************************************  
          ***************************************************  
          ***************************************************  
          ***************************************************  
           *************************************************  
           *************************************************  
          ***************************************************  
            ***********************************************  
            ***********************************************  
              *******************************************  
               *****************************************  
             *********************************************  
            **** ****************** ****************** ****  
             ***  ****************   ****************  ***  
              *    **************     **************    *  
                     ***********       ***********  
                     **  *****           *****  **  
                      *   *                 *   *  


C Elapsed 0.25


    Forcal用的时间与c++相比,为1.078:0.25=4.312:1。


    Lua的代码及运行时间。


view plain
#!/usr/local/bin/lua  
  
-- By Erik Wrenholt  
  
local BAILOUT = 16  
local MAX_ITERATIONS = 1000  
  
function iterate(x,y)  
  
    local cr = y-0.5  
    local ci = x  
    local zi = 0.0  
    local zr = 0.0  
    local i = 0  
      
    while 1 do  
        i = i+1  
        local temp = zr * zi  
        local zr2 = zr*zr  
        local zi2 = zi*zi  
        zr = zr2-zi2+cr  
        zi = temp+temp+ci  
        if (zi2+zr2 > BAILOUT) then  
            return i  
        end  
          
        if (i > MAX_ITERATIONS) then  
            return 0  
        end  
    end  
  
end  
  
function mandelbrot()  
    local t = os.clock()  
    for y = -39, 38 do  
        for x = -39, 38 do  
            if (iterate(x/40.0, y/40) == 0) then  
                io.write("*")  
            else  
                io.write(" ")  
            end  
        end  
        io.write("\n")  
    end  
    io.write(string.format("Time Elapsed %f\n", os.clock() - t))  
end  
  
mandelbrot()  


    运行输出图形与前面相同,仅给出运行时间:


Time Elapsed 0.860000


    Python的代码及运行时间。


view plain
#!/usr/local/bin/python  
# by Daniel Rosengren  
  
import sys, time  
stdout = sys.stdout  
  
BAILOUT = 16  
MAX_ITERATIONS = 1000  
  
class Iterator:  
  def __init__(self):  
    stdout.write('Rendering...')  
    for y in range(-39, 39):  
      stdout.write('\n')  
      for x in range(-39, 39):  
        i = self.mandelbrot(x/40.0, y/40.0)  
          
        if i == 0:  
          stdout.write('*')  
        else:  
          stdout.write(' ')  
      
  def mandelbrot(self, x, y):  
    cr = y - 0.5  
    ci = x  
    zi = 0.0  
    zr = 0.0  
    i = 0  
  
    while True:  
      i += 1  
      temp = zr * zi  
      zr2 = zr * zr  
      zi2 = zi * zi  
      zr = zr2 - zi2 + cr  
      zi = temp + temp + ci  
            
      if zi2 + zr2 > BAILOUT:  
        return i  
      if i > MAX_ITERATIONS:  
        return 0  
  
t = time.time()  
Iterator()  
stdout.write('\nPython Elapsed %.02f' % (time.time() - t))  


    运行结果:


Python Elapsed 2.84


    =======================


    完成相同功能的Lu代码如下:


view plain
mandelbrot(x, y : cr,ci,zi,zr,i,temp,zr2,zi2) =  
{  
    cr = y - 0.5,  
    ci = x,  
    zi = 0.0,  
    zr = 0.0,  
    i = 0,  
  
    (1).while {  
        i ++,  
        temp = zr * zi,  
        zr2 = zr * zr,  
        zi2 = zi * zi,  
        zr = zr2 - zi2 + cr,  
        zi = temp + temp + ci,  
        if [zi2 + zr2 > 16, return (i)],  
        if [i > 1000, return (0)]  
    }  
      
};  
  
main (:i,x,y,old,now) = {  
  
    old=clock(),  
    y = -39,  
    while{  y < 39,  
        o("\r\n"),  
        x = -39,  
        while{  x < 39,  
            i = mandelbrot(x/40.0, y/40.0),  
            which{  i==0,  
                o("*"),  
                o(" ")  
            },  
            x++  
        },  
        y++  
    },  
    now=clock(),  
    o["\r\nLu Elapsed ",(now-old)/1000.0]  
};  


    运行时输出的图形与C程序相同,在演示程序DemoLu32.exe(这是个windows程序)中的运行时间为:


        Lu Elapsed 5.657


    从运行结果可看出,Lu用的时间与c++相比,为5.657:0.25=22.628:1。


    因C/C++、Forcal、Lua等均使用控制台程序,故设计加载Lu并演示以上程序的C/C++控制台程序如下:


view plain
#include <windows.h>  
#include <iostream>  
#include <math.h>  
#include "lu32.h"  
  
#pragma comment( lib, "lu32.lib" )  
  
using namespace std;  
  
void _stdcall LuMessage(wchar_t *pch) //输出动态库信息,该函数注册到Lu,由Lu二级函数调用  
{  
    wcout<<pch;  
}  
void main(void)  
{  
    void *hFor;            //表达式句柄  
    luINT nPara;           //存放表达式的自变量个数  
    LuData *pPara;         //存放输入自变量的数组指针  
    luINT ErrBegin,ErrEnd; //表达式编译出错的初始位置和结束位置  
    int ErrCode1,ErrCode2; //错误代码  
    void *v;  
    wchar_t mandelbrot[]=L"mandelbrot(x, y : cr,ci,zi,zr,i,temp,zr2,zi2) =\r\n{\r\n cr = y - 0.5,\r\n ci = x,\r\n zi = 0.0,\r\n zr = 0.0,\r\n i = 0,\r\n (1).while {\r\n i ++,\r\n temp = zr * zi,\r\n zr2 = zr * zr,\r\n zi2 = zi * zi,\r\n zr = zr2 - zi2 + cr,\r\n zi = temp + temp + ci,\r\n if [zi2 + zr2 > 16, return (i)],\r\n if [i > 1000, return (0)]\r\n }\r\n }";//字符串表达式  
    wchar_t mymain[]=L"mymain (:i,x,y,old,now) = {\r\n old=clock(),\r\n y = -39,\r\n while{ y < 39,\r\n o(\"\r\n\"),\r\n x = -39,\r\n while{ x < 39,\r\n i = mandelbrot(x/40.0, y/40.0),\r\n which{ i==0,\r\n o(\"*\"),\r\n o(\" \")\r\n },\r\n x++\r\n },\r\n y++\r\n },\r\n now=clock(),\r\n o[\"\r\nLu Elapsed \",(now-old)/1000.0]\r\n}";           //字符串表达式  
  
    if(!InitLu()) return;  //初始化Lu  
    InsertKey("\0\0\0\0",4,luPubKey_User,LuMessage,NULL,NULL,1,v); //使Lu运行时可输出函数信息  
  
    ErrCode1=LuCom(mandelbrot,0,0,0,hFor,nPara,pPara,ErrBegin,ErrEnd); //编译表达式  
    ErrCode2=LuCom(mymain,0,0,0,hFor,nPara,pPara,ErrBegin,ErrEnd); //编译表达式  
    if(ErrCode1 || ErrCode2)  
    {  
        cout<<"表达式有错误!错误代码:"<<ErrCode1<<" "<<ErrCode2<<endl;  
    }  
    else  
    {  
        LuCal(hFor,pPara); //计算表达式的值  
    }  
    FreeLu();              //释放Lu  
}  


    运行时输出的图形与C程序相同,运行时间为:


Lu Elapsed 2.063


    从运行结果可看出,Lu用的时间与c++相比,为2.063:0.25=8.252:1。


9 Lu与Python比较的测试例子


    Python程序:


Python code>>> def f(k):
n=0
i=0
while i <=k:
    n=n+i
    i=i+1
    return n


>>> f(100000000)
5000000050000000


    耗时约32秒(用秒表测量)。


    Lu程序:


f(k:i,n)= i=0,n=0, while{i<=k, n=n+i++}, n;
(:t)= t=clock(), o{"f(100000000)=",f(100000000),", time=",[clock()-t]/1000.};


    Lu运行结果:


f(100000000)=5000000050000000, time=14.797


    ======


    另一个测试程序:


    Python 程序:


Python code>>> def f(x,y):
    return math.cos(1-math.sin(1.2*(x+0.1)**(y/2-x)+math.cos(1-math.sin(1.2*(x+0.2)**(y/3-x))))-math.cos(1-math.sin(1.2*(x+0.3)**(y/4-x)))-math.cos(1-math.sin(1.2*(x+0.4)**(y/5-x)+math.cos(1-math.sin(1.2*(x+0.5)**(y/6-x))))-math.cos(1-math.sin(1.2*(x+0.6)**(y/7-x)))))


>>> def g(m,n):
x=0
i=0
while i <=m:
    j=0
    while j <=n:
        x=x+f(i,j)
        j=j+0.01
    i=i+0.01
    return x


>>> g(12.3,7.89)
404005.29176341009


    Python运行约10秒(用秒表测量)。


    Lu程序:


f(x,y)=cos(1-sin(1.2*(x+0.1)^(y/2-x)+cos(1-sin(1.2*(x+0.2)^(y/3-x))))-cos(1-sin(1.2*(x+0.3)^(y/4-x)))-cos(1-sin(1.2*(x+0.4)^(y/5-x)+cos(1-sin(1.2*(x+0.5)^(y/6-x))))-cos(1-sin(1.2*(x+0.6)^(y/7-x)))));
g(m,n:i,j,x)=
    x=0,i=0,
        (i<=m).while{
            j=0,
            (j<=n).while{
                x=x+f(i,j),
                j=j+0.01
            },
            i=i+0.01
        },
    x;
main(:t)= t=clock(), o{"g(12.3,7.89)=",g(12.3,7.89),", time=",[clock()-t]/1000.};


    Lu结果:


g(12.3,7.89)=404005.29176341009, time=3.43
QQ: 378890364 微信:wwtree(省短信费) 紧急事宜发短信到0061432027638  本站微博:http://t.qq.com/wwtree QQ群:122538123
级别: 管理员
发帖
8532
金币
2762
威望
3231
贡献值
0
元宝
0
只看该作者 8楼 发表于: 2011-11-20
C++代码优化方案
目录
C代码优化方案
1、选择合适的算法和数据结构
2、使用尽量小的数据类型
3、减少运算的强度
(1)、查表(游戏程序员必修课)
(2)、求余运算
(3)、平方运算
(4)、用移位实现乘除法运算
(5)、避免不必要的整数除法
(6)、使用增量和减量操作符
(7)、使用复合赋值表达式
(8)、提取公共的子表达式
4、结构体成员的布局
(1)按数据类型的长度排序
(2)把结构体填充成最长类型长度的整倍数
(3)按数据类型的长度排序本地变量
(4)把频繁使用的指针型参数拷贝到本地变量
5、循环优化
(1)、充分分解小的循环
(2)、提取公共部分
(3)、延时函数
(4)、while循环和do…while循环
(6)、循环展开
(6)、循环嵌套
(7)、Switch语句中根据发生频率来进行case排序
(8)、将大的switch语句转为嵌套switch语句
(9)、循环转置
(10)、公用代码块
(11)提升循环的性能
(12)、选择好的无限循环
6、提高CPU的并行性
(1)使用并行代码
(2)避免没有必要的读写依赖
7、循环不变计算
8、函数
(1)Inline函数
(2)不定义不使用的返回值
(3)减少函数调用参数
(4)所有函数都应该有原型定义
(5)尽可能使用常量(const)
(6)把本地函数声明为静态的(static)
9、采用递归
10、变量
(1)register变量
(2)、同时声明多个变量优于单独声明变量
(3)、短变量名优于长变量名,应尽量使变量名短一点
(4)、在循环开始前声明变量
11、使用嵌套的if结构
1、选择合适的算法和数据结构


选择一种合适的数据结构很重要,如果在一堆随机存放的数中使用了大量的插入和删除指令,那使用链表要快得多。数组与指针语句具有十分密切的关系,一般来说,指针比较灵活简洁,而数组则比较直观,容易理解。对于大部分的编译器,使用指针比使用数组生成的代码更短,执行效率更高。


在许多种情况下,可以用指针运算代替数组索引,这样做常常能产生又快又短的代码。与数组索引相比,指针一般能使代码速度更快,占用空间更少。使用多维数组时差异更明显。下面的代码作用是相同的,但是效率不一样?


    数组索引                指针运算


    For(;;){                p=array


    A=array[t++];          for(;;){


                                a=*(p++);


    。。。。。。。。。                  。。。。。。


    }                      }


指针方法的优点是,array的地址每次装入地址p后,在每次循环中只需对p增量操作。在数组索引方法中,每次循环中都必须根据t值求数组下标的复杂运算。


2、使用尽量小的数据类型


能够使用字符型(char)定义的变量,就不要使用整型(int)变量来定义;能够使用整型变量定义的变量就不要用长整型(long int),能不使用浮点型(float)变量就不要使用浮点型变量。当然,在定义变量后不要超过变量的作用范围,如果超过变量的范围赋值,C编译器并不报错,但程序运行结果却错了,而且这样的错误很难发现。


在ICCAVR中,可以在Options中设定使用printf参数,尽量使用基本型参数(%c、%d、%x、%X、%u和%s格式说明符),少用长整型参数(%ld、%lu、%lx和%lX格式说明符),至于浮点型的参数(%f)则尽量不要使用,其它C编译器也一样。在其它条件不变的情况下,使用%f参数,会使生成的代码的数量增加很多,执行速度降低。


3、减少运算的强度


(1)、查表(游戏程序员必修课)


一个聪明的游戏大虾,基本上不会在自己的主循环里搞什么运算工作,绝对是先计算好了,再到循环里查表。看下面的例子:


旧代码:


    long factorial(int i)


    {


        if (i == 0)


            return 1;


        else


            return i * factorial(i - 1);


    }


新代码:


    static long factorial_table[] =


        {1, 1, 2, 6, 24, 120, 720  /* etc */ };


    long factorial(int i)


    {


        return factorial_table;


    }


如果表很大,不好写,就写一个init函数,在循环外临时生成表格。


(2)、求余运算


    a=a%8;


可以改为:


    a=a&7;


说明:位操作只需一个指令周期即可完成,而大部分的C编译器的“%”运算均是调用子程序来完成,代码长、执行速度慢。通常,只要求是求2n方的余数,均可使用位操作的方法来代替。


(3)、平方运算


a=pow(a, 2.0);


可以改为:


a=a*a;


说明:在有内置硬件乘法器的单片机中(如51系列),乘法运算比求平方运算快得多,因为浮点数的求平方是通过调用子程序来实现的,在自带硬件乘法器的AVR单片机中,如ATMega163中,乘法运算只需2个时钟周期就可以完成。既使是在没有内置硬件乘法器的AVR单片机中,乘法运算的子程序比平方运算的子程序代码短,执行速度快。


如果是求3次方,如:


a=pow(a,3。0);


更改为:


a=a*a*a;


则效率的改善更明显。


(4)、用移位实现乘除法运算


    a=a*4;


    b=b/4;


可以改为:


    a=a<<2;


    b=b>>2;


通常如果需要乘以或除以2n,都可以用移位的方法代替。在ICCAVR中,如果乘以2n,都可以生成左移的代码,而乘以其它的整数或除以任何数,均调用乘除法子程序。用移位的方法得到代码比调用乘除法子程序生成的代码效率高。实际上,只要是乘以或除以一个整数,均可以用移位的方法得到结果,如:


    a=a*9


可以改为:


a=(a<<3)+a


采用运算量更小的表达式替换原来的表达式,下面是一个经典例子:


旧代码:


    x = w % 8;


    y = pow(x, 2.0);


    z = y * 33;


    for (i = 0;i < MAX;i++)


    {


        h = 14 * i;


        printf("%d", h);


    }


新代码:


    x = w & 7;              /* 位操作比求余运算快*/


    y = x * x;               /* 乘法比平方运算快*/


    z = (y << 5) + y;          /* 位移乘法比乘法快 */


    for (i = h = 0; i < MAX; i++)


    {


        h += 14;                /* 加法比乘法快 */


        printf("%d",h);


}


(5)、避免不必要的整数除法


整数除法是整数运算中最慢的,所以应该尽可能避免。一种可能减少整数除法的地方是连除,这里除法可以由乘法代替。这个替换的副作用是有可能在算乘积时会溢出,所以只能在一定范围的除法中使用。


不好的代码:


int i, j, k, m;


m = i / j / k;


推荐的代码:


int i, j, k, m;


m = i / (j * k);


(6)、使用增量和减量操作符


在使用到加一和减一操作时尽量使用增量和减量操作符,因为增量符语句比赋值语句更快,原因在于对大多数CPU来说,对内存字的增、减量操作不必明显地使用取内存和写内存的指令,比如下面这条语句:


x=x+1;


模仿大多数微机汇编语言为例,产生的代码类似于:


move A,x      ;把x从内存取出存入累加器A


add A,1        ;累加器A加1


store x          ;把新值存回x


如果使用增量操作符,生成的代码如下:


incr x           ;x加1


显然,不用取指令和存指令,增、减量操作执行的速度加快,同时长度也缩短了。


(7)、使用复合赋值表达式


复合赋值表达式(如a-=1及a+=1等)都能够生成高质量的程序代码。


(8)、提取公共的子表达式


在某些情况下,C++编译器不能从浮点表达式中提出公共的子表达式,因为这意味着相当于对表达式重新排序。需要特别指出的是,编译器在提取公共子表达式前不能按照代数的等价关系重新安排表达式。这时,程序员要手动地提出公共的子表达式(在VC.NET里有一项“全局优化”选项可以完成此工作,但效果就不得而知了)。


不好的代码:


float a, b, c, d, e, f;


。。。


e = b * c / d;


f = b / d * a;


推荐的代码:


float a, b, c, d, e, f;


。。。


const float t(b / d);


e = c * t;


f = a * t;


不好的代码:


float a, b, c, e, f;


。。。


e = a / c;


f = b / c;


推荐的代码:


float a, b, c, e, f;


。。。


const float t(1.0f / c);


e = a * t;


f = b * t;


4、结构体成员的布局


很多编译器有“使结构体字,双字或四字对齐”的选项。但是,还是需要改善结构体成员的对齐,有些编译器可能分配给结构体成员空间的顺序与他们声明的不同。但是,有些编译器并不提供这些功能,或者效果不好。所以,要在付出最少代价的情况下实现最好的结构体和结构体成员对齐,建议采取下列方法:


(1)按数据类型的长度排序


把结构体的成员按照它们的类型长度排序,声明成员时把长的类型放在短的前面。编译器要求把长型数据类型存放在偶数地址边界。在申明一个复杂的数据类型 (既有多字节数据又有单字节数据) 时,应该首先存放多字节数据,然后再存放单字节数据,这样可以避免内存的空洞。编译器自动地把结构的实例对齐在内存的偶数边界。


(2)把结构体填充成最长类型长度的整倍数


把结构体填充成最长类型长度的整倍数。照这样,如果结构体的第一个成员对齐了,所有整个结构体自然也就对齐了。下面的例子演示了如何对结构体成员进行重新排序:


不好的代码,普通顺序:


struct


{


char a[5];


long k;


double x;


} baz;


推荐的代码,新的顺序并手动填充了几个字节:


struct


{


double x;


long k;


char a[5];


char pad[7];


} baz;


这个规则同样适用于类的成员的布局。


(3)按数据类型的长度排序本地变量


当编译器分配给本地变量空间时,它们的顺序和它们在源代码中声明的顺序一样,和上一条规则一样,应该把长的变量放在短的变量前面。如果第一个变量对齐了,其它变量就会连续的存放,而且不用填充字节自然就会对齐。有些编译器在分配变量时不会自动改变变量顺序,有些编译器不能产生4字节对齐的栈,所以4字节可能不对齐。下面这个例子演示了本地变量声明的重新排序:


不好的代码,普通顺序


short ga, gu, gi;


long foo, bar;


double x, y, z[3];


char a, b;


float baz;


推荐的代码,改进的顺序


double z[3];


double x, y;


long foo, bar;


float baz;


short ga, gu, gi;


(4)把频繁使用的指针型参数拷贝到本地变量


避免在函数中频繁使用指针型参数指向的值。因为编译器不知道指针之间是否存在冲突,所以指针型参数往往不能被编译器优化。这样数据不能被存放在寄存器中,而且明显地占用了内存带宽。注意,很多编译器有“假设不冲突”优化开关(在VC里必须手动添加编译器命令行/Oa或/Ow),这允许编译器假设两个不同的指针总是有不同的内容,这样就不用把指针型参数保存到本地变量。否则,请在函数一开始把指针指向的数据保存到本地变量。如果需要的话,在函数结束前拷贝回去。


不好的代码:


// 假设 q != r


void isqrt(unsigned long a, unsigned long* q, unsigned long* r)


{


  *q = a;


  if (a > 0)


  {


    while (*q > (*r = a / *q))


    {


      *q = (*q + *r) >> 1;


    }


  }


  *r = a - *q * *q;


}


推荐的代码:


// 假设 q != r


void isqrt(unsigned long a, unsigned long* q, unsigned long* r)


{


  unsigned long qq, rr;


  qq = a;


  if (a > 0)


  {


    while (qq > (rr = a / qq))


    {


      qq = (qq + rr) >> 1;


    }


  }


  rr = a - qq * qq;


  *q = qq;


  *r = rr;


}


5、循环优化


(1)、充分分解小的循环


要充分利用CPU的指令缓存,就要充分分解小的循环。特别是当循环体本身很小的时候,分解循环可以提高性能。注意:很多编译器并不能自动分解循环。 不好的代码:


// 3D转化:把矢量 V 和 4x4 矩阵 M 相乘


for (i = 0; i < 4; i ++)


{


  r = 0;


  for (j = 0; j < 4; j ++)


  {


    r += M[j]*V[j];


  }


}


推荐的代码:


r[0] = M[0][0]*V[0] + M[1][0]*V[1] + M[2][0]*V[2] + M[3][0]*V[3];


r[1] = M[0][1]*V[0] + M[1][1]*V[1] + M[2][1]*V[2] + M[3][1]*V[3];


r[2] = M[0][2]*V[0] + M[1][2]*V[1] + M[2][2]*V[2] + M[3][2]*V[3];


r[3] = M[0][3]*V[0] + M[1][3]*V[1] + M[2][3]*V[2] + M[3][3]*v[3];
(2)、提取公共部分


对于一些不需要循环变量参加运算的任务可以把它们放到循环外面,这里的任务包括表达式、函数的调用、指针运算、数组访问等,应该将没有必要执行多次的操作全部集合在一起,放到一个init的初始化程序中进行。


(3)、延时函数


通常使用的延时函数均采用自加的形式:


    void delay (void)


    {


unsigned int i;


    for (i=0;i<1000;i++) ;


    }


将其改为自减延时函数:


    void delay (void)


    {


unsigned int i;


        for (i=1000;i>0;i--) ;


    }


两个函数的延时效果相似,但几乎所有的C编译对后一种函数生成的代码均比前一种代码少1~3个字节,因为几乎所有的MCU均有为0转移的指令,采用后一种方式能够生成这类指令。在使用while循环时也一样,使用自减指令控制循环会比使用自加指令控制循环生成的代码更少1~3个字母。但是在循环中有通过循环变量“i”读写数组的指令时,使用预减循环有可能使数组超界,要引起注意。


(4)、while循环和do…while循环


用while循环时有以下两种循环形式:


unsigned int i;


    i=0;


    while (i<1000)


    {


        i++;


           //用户程序


    }


或:


unsigned int i;


    i=1000;


do


{


          i--;


          //用户程序


}


while (i>0);


在这两种循环中,使用do…while循环编译后生成的代码的长度短于while循环。


(6)、循环展开


这是经典的速度优化,但许多编译程序(如gcc -funroll-loops)能自动完成这个事,所以现在你自己来优化这个显得效果不明显。


旧代码:


for (i = 0; i < 100; i++)


{
do_stuff(i);


}


新代码:
for (i = 0; i < 100; )


{


do_stuff(i); i++;


do_stuff(i); i++;


do_stuff(i); i++;


do_stuff(i); i++;


do_stuff(i); i++;


do_stuff(i); i++;


do_stuff(i); i++;


do_stuff(i); i++;


do_stuff(i); i++;


do_stuff(i); i++;


}


可以看出,新代码里比较指令由100次降低为10次,循环时间节约了90%。不过注意:对于中间变量或结果被更改的循环,编译程序往往拒绝展开,(怕担责任呗),这时候就需要你自己来做展开工作了。


还有一点请注意,在有内部指令cache的CPU上(如MMX芯片),因为循环展开的代码很大,往往cache溢出,这时展开的代码会频繁地在CPU 的cache和内存之间调来调去,又因为cache速度很高,所以此时循环展开反而会变慢。还有就是循环展开会影响矢量运算优化。


(6)、循环嵌套


把相关循环放到一个循环里,也会加快速度。


旧代码:


for (i = 0; i < MAX; i++)         /* initialize 2d array to 0's */


    for (j = 0; j < MAX; j++)


        a[j] = 0.0;


    for (i = 0; i < MAX; i++)        /* put 1's along the diagonal */


        a = 1.0;


新代码:


for (i = 0; i < MAX; i++)         /* initialize 2d array to 0's */


{


    for (j = 0; j < MAX; j++)


        a[j] = 0.0;


    a = 1.0;                            /* put 1's along the diagonal */


}


(7)、Switch语句中根据发生频率来进行case排序


Switch 可能转化成多种不同算法的代码。其中最常见的是跳转表和比较链/树。当switch用比较链的方式转化时,编译器会产生if-else-if的嵌套代码,并按照顺序进行比较,匹配时就跳转到满足条件的语句执行。所以可以对case的值依照发生的可能性进行排序,把最有可能的放在第一位,这样可以提高性能。此外,在case中推荐使用小的连续的整数,因为在这种情况下,所有的编译器都可以把switch 转化成跳转表。


不好的代码:


int days_in_month, short_months, normal_months, long_months;


。。。。。。


switch (days_in_month)


{


  case 28:


  case 29:


    short_months ++;


    break;


  case 30:


    normal_months ++;


    break;


  case 31:


    long_months ++;


    break;


  default:


    cout << "month has fewer than 28 or more than 31 days" << endl;


    break;


}


推荐的代码:


int days_in_month, short_months, normal_months, long_months;


。。。。。。


switch (days_in_month)


{


  case 31:


    long_months ++;


    break;


  case 30:


    normal_months ++;


    break;


  case 28:


  case 29:


    short_months ++;


    break;


  default:


    cout << "month has fewer than 28 or more than 31 days" << endl;


    break;


}  


(8)、将大的switch语句转为嵌套switch语句


当switch语句中的case标号很多时,为了减少比较的次数,明智的做法是把大switch语句转为嵌套switch语句。把发生频率高的case 标号放在一个switch语句中,并且是嵌套switch语句的最外层,发生相对频率相对低的case标号放在另一个switch语句中。比如,下面的程序段把相对发生频率低的情况放在缺省的case标号内。


pMsg=ReceiveMessage();


        switch (pMsg->type)


        {


        case FREQUENT_MSG1:


        handleFrequentMsg();


        break;


        case FREQUENT_MSG2:


        handleFrequentMsg2();


        break;


        。。。。。。


        case FREQUENT_MSGn:


        handleFrequentMsgn();


        break;


        default:                     //嵌套部分用来处理不经常发生的消息


        switch (pMsg->type)


        {


        case INFREQUENT_MSG1:


        handleInfrequentMsg1();


        break;


        case INFREQUENT_MSG2:


        handleInfrequentMsg2();


        break;


        。。。。。。


        case INFREQUENT_MSGm:


        handleInfrequentMsgm();


        break;


        }


        }


如果switch中每一种情况下都有很多的工作要做,那么把整个switch语句用一个指向函数指针的表来替换会更加有效,比如下面的switch语句,有三种情况:


    enum MsgType{Msg1, Msg2, Msg3}


        switch (ReceiveMessage()


        {


        case Msg1;


        。。。。。。


        case Msg2;


        。。。。。


        case Msg3;


        。。。。。


        }


为了提高执行速度,用下面这段代码来替换这个上面的switch语句。


        /*准备工作*/


        int handleMsg1(void);


        int handleMsg2(void);


        int handleMsg3(void);


        /*创建一个函数指针数组*/


        int (*MsgFunction [])()={handleMsg1, handleMsg2, handleMsg3};


        /*用下面这行更有效的代码来替换switch语句*/


        status=MsgFunction[ReceiveMessage()]();


(9)、循环转置


有些机器对JNZ(为0转移)有特别的指令处理,速度非常快,如果你的循环对方向不敏感,可以由大向小循环。


旧代码:


for (i = 1; i <= MAX; i++)


{


   。。。


}


新代码:


i = MAX+1;


while (--i)


{


。。。


}


不过千万注意,如果指针操作使用了i值,这种方法可能引起指针越界的严重错误(i = MAX+1;)。当然你可以通过对i做加减运算来纠正,但是这样就起不到加速的作用,除非类似于以下情况:


旧代码:


char a[MAX+5];


for (i = 1; i <= MAX; i++)


{


*(a+i+4)=0;


}


新代码:


i = MAX+1;


while (--i)


{


      *(a+i+4)=0;


}


(10)、公用代码块


一些公用处理模块,为了满足各种不同的调用需要,往往在内部采用了大量的if-then-else结构,这样很不好,判断语句如果太复杂,会消耗大量的时间的,应该尽量减少公用代码块的使用。(任何情况下,空间优化和时间优化都是对立的--东楼)。当然,如果仅仅是一个(3==x)之类的简单判断,适当使用一下,也还是允许的。记住,优化永远是追求一种平衡,而不是走极端。


(11)提升循环的性能


要提升循环的性能,减少多余的常量计算非常有用(比如,不随循环变化的计算)。


不好的代码(在for()中包含不变的if()):


for( i 。。。 )


{


  if( CONSTANT0 )


  {


    DoWork0( i ); // 假设这里不改变CONSTANT0的值


  }


  else


  {


    DoWork1( i ); // 假设这里不改变CONSTANT0的值


  }


}


推荐的代码:


if( CONSTANT0 )


{


  for( i 。。。 )


  {


    DoWork0( i );


  }


}


else


{


  for( i 。。。 )


  {


    DoWork1( i );


  }


}


如果已经知道if()的值,这样可以避免重复计算。虽然不好的代码中的分支可以简单地预测,但是由于推荐的代码在进入循环前分支已经确定,就可以减少对分支预测的依赖。


(12)、选择好的无限循环


在编程中,我们常常需要用到无限循环,常用的两种方法是while (1) 和 for (;;)。这两种方法效果完全一样,但那一种更好呢?然我们看看它们编译后的代码:


编译前:


while (1);


编译后:


mov eax,1


test eax,eax


je foo+23h


jmp foo+18h


编译前:


for (;;);


编译后:


jmp foo+23h


显然,for (;;)指令少,不占用寄存器,而且没有判断、跳转,比while (1)好。
6、提高CPU的并行性


(1)使用并行代码


尽可能把长的有依赖的代码链分解成几个可以在流水线执行单元中并行执行的没有依赖的代码链。很多高级语言,包括C++,并不对产生的浮点表达式重新排序,因为那是一个相当复杂的过程。需要注意的是,重排序的代码和原来的代码在代码上一致并不等价于计算结果一致,因为浮点操作缺乏精确度。在一些情况下,这些优化可能导致意料之外的结果。幸运的是,在大部分情况下,最后结果可能只有最不重要的位(即最低位)是错误的。


不好的代码:


double a[100], sum;


int i;


sum = 0.0f;


for (i=0; i<100; i++)


sum += a


推荐的代码:


double a[100], sum1, sum2, sum3, sum4, sum;


int i;


sum1 = sum2 = sum3 = sum4 = 0.0;


for (i = 0; i < 100; i += 4)


{


  sum1 += a


  sum2 += a[i+1];


  sum3 += a[i+2];


  sum4 += a[i+3];


}


sum = (sum4+sum3)+(sum1+sum2);


要注意的是:使用4路分解是因为这样使用了4段流水线浮点加法,浮点加法的每一个段占用一个时钟周期,保证了最大的资源利用率。


(2)避免没有必要的读写依赖


当数据保存到内存时存在读写依赖,即数据必须在正确写入后才能再次读取。虽然AMD Athlon等CPU有加速读写依赖延迟的硬件,允许在要保存的数据被写入内存前读取出来,但是,如果避免了读写依赖并把数据保存在内部寄存器中,速度会更快。在一段很长的又互相依赖的代码链中,避免读写依赖显得尤其重要。如果读写依赖发生在操作数组时,许多编译器不能自动优化代码以避免读写依赖。所以推荐程序员手动去消除读写依赖,举例来说,引进一个可以保存在寄存器中的临时变量。这样可以有很大的性能提升。下面一段代码是一个例子:


不好的代码:


float x[VECLEN], y[VECLEN], z[VECLEN];


。。。。。。


for (unsigned int k = 1; k < VECLEN; k ++)


{


  x[k] = x[k-1] + y[k];


}


for (k = 1; k <VECLEN; k++)


{


  x[k] = z[k] * (y[k] - x[k-1]);


}


推荐的代码:


float x[VECLEN], y[VECLEN], z[VECLEN];


。。。。。。


float t(x[0]);


for (unsigned int k = 1; k < VECLEN; k ++)


{


  t = t + y[k];


  x[k] = t;


}


t = x[0];


for (k = 1; k <; VECLEN; k ++)


{


  t = z[k] * (y[k] - t);


  x[k] = t;


}


7、循环不变计算


对于一些不需要循环变量参加运算的计算任务可以把它们放到循环外面,现在许多编译器还是能自己干这件事,不过对于中间使用了变量的算式它们就不敢动了,所以很多情况下你还得自己干。对于那些在循环中调用的函数,凡是没必要执行多次的操作通通提出来,放到一个init函数里,循环前调用。另外尽量减少喂食次数,没必要的话尽量不给它传参,需要循环变量的话让它自己建立一个静态循环变量自己累加,速度会快一点。


还有就是结构体访问,东楼的经验,凡是在循环里对一个结构体的两个以上的元素执行了访问,就有必要建立中间变量了(结构这样,那C++的对象呢?想想看),看下面的例子:


旧代码:


    total =


    a->b->c[4]->aardvark +


    a->b->c[4]->baboon +


    a->b->c[4]->cheetah +


    a->b->c[4]->dog;


新代码:


    struct animals * temp = a->b->c[4];


    total =


    temp->aardvark +


    temp->baboon +


    temp->cheetah +


    temp->dog;


一些老的C语言编译器不做聚合优化,而符合ANSI规范的新的编译器可以自动完成这个优化,看例子:


    float a, b, c, d, f, g;


    。。。


    a = b / c * d;


    f = b * g / c;


这种写法当然要得,但是没有优化


    float a, b, c, d, f, g;


    。。。


    a = b / c * d;


    f = b / c * g;


如果这么写的话,一个符合ANSI规范的新的编译器可以只计算b/c一次,然后将结果代入第二个式子,节约了一次除法运算。


8、函数优化


(1)Inline函数


在C++中,关键字Inline可以被加入到任何函数的声明中。这个关键字请求编译器用函数内部的代码替换所有对于指出的函数的调用。这样做在两个方面快于函数调用:第一,省去了调用指令需要的执行时间;第二,省去了传递变元和传递过程需要的时间。但是使用这种方法在优化程序速度的同时,程序长度变大了,因此需要更多的ROM。使用这种优化在Inline函数频繁调用并且只包含几行代码的时候是最有效的。


(2)不定义不使用的返回值


函数定义并不知道函数返回值是否被使用,假如返回值从来不会被用到,应该使用void来明确声明函数不返回任何值。


(3)减少函数调用参数


    使用全局变量比函数传递参数更加有效率。这样做去除了函数调用参数入栈和函数完成后参数出栈所需要的时间。然而决定使用全局变量会影响程序的模块化和重入,故要慎重使用。


(4)所有函数都应该有原型定义


一般来说,所有函数都应该有原型定义。原型定义可以传达给编译器更多的可能用于优化的信息。


(5)尽可能使用常量(const)


尽可能使用常量(const)。C++ 标准规定,如果一个const声明的对象的地址不被获取,允许编译器不对它分配储存空间。这样可以使代码更有效率,而且可以生成更好的代码。


(6)把本地函数声明为静态的(static)


如果一个函数只在实现它的文件中被使用,把它声明为静态的(static)以强制使用内部连接。否则,默认的情况下会把函数定义为外部连接。这样可能会影响某些编译器的优化——比如,自动内联。


9、采用递归


与LISP之类的语言不同,C语言一开始就病态地喜欢用重复代码循环,许多C程序员都是除非算法要求,坚决不用递归。事实上,C编译器们对优化递归调用一点都不反感,相反,它们还很喜欢干这件事。只有在递归函数需要传递大量参数,可能造成瓶颈的时候,才应该使用循环代码,其他时候,还是用递归好些。


10、变量


(1)register变量


在声明局部变量的时候可以使用register关键字。这就使得编译器把变量放入一个多用途的寄存器中,而不是在堆栈中,合理使用这种方法可以提高执行速度。函数调用越是频繁,越是可能提高代码的速度。


在最内层循环避免使用全局变量和静态变量,除非你能确定它在循环周期中不会动态变化,大多数编译器优化变量都只有一个办法,就是将他们置成寄存器变量,而对于动态变量,它们干脆放弃对整个表达式的优化。尽量避免把一个变量地址传递给另一个函数,虽然这个还很常用。C语言的编译器们总是先假定每一个函数的变量都是内部变量,这是由它的机制决定的,在这种情况下,它们的优化完成得最好。但是,一旦一个变量有可能被别的函数改变,这帮兄弟就再也不敢把变量放到寄存器里了,严重影响速度。看例子:


a = b();


c(&d);


因为d的地址被c函数使用,有可能被改变,编译器不敢把它长时间的放在寄存器里,一旦运行到c(&d),编译器就把它放回内存,如果在循环里,会造成N次频繁的在内存和寄存器之间读写d的动作,众所周知,CPU在系统总线上的读写速度慢得很。比如你的赛杨300,CPU主频300,总线速度最多66M,为了一个总线读,CPU可能要等4-5个周期,得。。得。。得。。想起来都打颤。


(2)、同时声明多个变量优于单独声明变量


(3)、短变量名优于长变量名,应尽量使变量名短一点


(4)、在循环开始前声明变量


11、使用嵌套的if结构


在if结构中如果要判断的并列条件较多,最好将它们拆分成多个if结构,然后嵌套在一起,这样可以避免无谓的判断。


说明:


上面的优化方案由王全明收集整理。很多资料来源与网上,出处不祥,在此对所有作者一并致谢!


该方案主要是考虑到在嵌入式开发中对程序执行速度的要求特别高,所以该方案主要是为了优化程序的执行速度。


注意:优化是有侧重点的,优化是一门平衡的艺术,它往往要以牺牲程序的可读性或者增加代码长度为代价。


(任何情况下,空间优化和时间优化都是对立的--东楼)。  
QQ: 378890364 微信:wwtree(省短信费) 紧急事宜发短信到0061432027638  本站微博:http://t.qq.com/wwtree QQ群:122538123
级别: 管理员
发帖
8532
金币
2762
威望
3231
贡献值
0
元宝
0
只看该作者 9楼 发表于: 2011-12-20
程序性能优化
1. 故事
    背景:线上流式计算,某个关键模块Mario一个大业务版本(带来输入数据double)升级上线
    注:流式计算的典型范式之一是不确定数据速率的事件流流入系统,系统处理能力必须与事件流量匹配。
    故事分为3个阶段
    1)上线后,线上报警,Mario出现数据积压(处理能力无法满足当前线上流量)。
         经查:Mario中经过处理后的数据需要进入远程数据库,处理线程以同步的方式将数据插入远程数据库,这种方式,使得线程处理能力急剧下降。
         解决:数据写入磁盘,另外一个程序入库
    2)第一个问题解决后,再次出现性能问题
         解决:使用Tcmalloc(参考:http://blog.csdn.net/yfkiss/article/details/6902269
    3)使用Tcmalloc之后,发现线上CPU抖动非常厉害,并且有一定概率程序hang住
         经查:一个求去重后的数据个数的算法,采用字典进行计算,频繁的对字典进行构建和删除,使得系统频繁申请、释放内存,从而导致cpu抖动。
         解决:对于小数据,采用O(n^2)的算法,对于大数据,采取O(n)的算法(http://blog.csdn.net/yfkiss/article/details/6754786)。


2. 原理
程序性能优化可以做三个层次的事情。
1)设计
2)算法&数据结构
3)代码
当然,以上三个层面只是一般程序员可以做的优化,之上还有架构,之下还有运行系统和硬件。
设计:个人理解是最重要的一块,包括:数据如何处理?多线程还是单线程?多线程之间如何同步?锁粒度多大?是否使用内存池?同步还是异步等等
算法和数据结构:对算法优化往往可以使得程序性能有数据级的飞跃。
代码调优:运行中的程序有一种典型情况:20%的代码占了80%的运行时间,优化的重点是这20%的代码。
回到story,第一个阶段的问题,很明显是设计出现问题,在出现需要网络交互的时候的,考虑异步方案。
第二个阶段使用了tcmalloc,本质上是从设计、算法、代码多个角度对内存分配做了优化,只是这个优化是别人帮你做的~
第三个阶段属于算法优化,原有算法非常快,但带来了内存操作的过大开销,我们的应用中,数据集99%都非常小(数据集平均大小为2),因此,对于小数据集,采用O(n^2)的算法,对于大数据集,采用O(n)的算法,实际证明非常有效。所以,没有最好的算法,只有最适合的算法。


3. 如何找出热点代码
1)梳理程序,找出执行热点。很土,但是很有效
2)辅助工具:Google Cpu Profiler
方法1更多的是依靠经验,辅助工具Google Cpu Profiler简要介绍下。
Google Cpu Profiler是 google-perftools的一部分(google-perftools还包括Tcmalloc、Heap checkedr、Heap profiler)
其使用非常简单:
链接 profiler库及设置环境变量CPUPROFILE


4.使用Google Cpu Profiler进行性能分析的一个实例(使用 LD_PRELOAD,懒人法,不需要重编译)
code:


view plain
#include <iostream>  
#include <time.h>  
using namespace std;  
  
const int MAX_OPERATION = 2;  
enum TYPE{MINUS = 0, PLUS};  
  
int random(unsigned int n)  
{  
        if(n != 0)  
        {  
                return rand() % n;  
        }  
        else  
        {  
                return 0;  
        }  
}  
  
void make_expression(int n)  
{  
        int left = random(n);  
        int operation = random(MAX_OPERATION);  
        int right = (PLUS==operation ? random(left) : random(n));  
        cout << left << (operation==PLUS ? "-" : "+") << right << "=";  
}  
  
void make(int n, int max)  
{  
        for(int i = 1; i <= n; i++)  
        {  
                make_expression(max);  
                if(0 != i % 3)  
                {  
                        cout << "\t" << "\t";  
                }  
                else  
                {  
                        cout << endl;  
                }  
        }  
}  
  
int main(int argc, char** argv)  
{  
        srand((int)time(0));  
  
        if(argc != 3)  
        {  
                cout << "we need 3 argc" << endl;  
                return 1;  
        }  
  
        make(atoi(argv[1]), atoi(argv[2]));  
        cout << endl;  
  
        return 0;  
}  
设置环境变量 LD_PRELOAD和CPUPROFILE
export "LD_PRELOAD=/home/work/zhouxm/google-perf_1.8.3/lib/libprofiler.so"
export "CPUPROFILE=/home/work/zhouxm/google-perf_1.8.3/bin/myprofiler"
注:LD_PRELOAD指定在程序运行前优先加载的动态链接库。这个功能主要就是用来有选择性的载入不同动态链接库中的相同函数。通过这个环境变量,我们可以在主程序和其动态链接库的中间加载别的动态链接库,甚至覆盖正常的函数库。这个环境变量相当危险,慎用
CPUPROFILE指定profiler文件保存位置及文件名
运行:
$./test 10000000 10000  1>/dev/null
PROFILE: interrupts/evictions/bytes =508/228/12704
分析:
1)文本分析:
$ ./pprof -text ./test ./myprofiler
Using local file ./test.
Using local file ./myprofiler.
Removing killpg from all stack traces.
Total: 508 samples
     149  29.3%  29.3%      149  29.3% __write_nocancel
      47   9.3%  38.6%       47   9.3% fwrite
      41   8.1%  46.7%       41   8.1% _IO_file_xsputn@@GLIBC_2.2.5
      41   8.1%  54.7%       41   8.1% random
      33   6.5%  61.2%       33   6.5% std::operator<<
      32   6.3%  67.5%       32   6.3% std::basic_ostream::operator<<
      29   5.7%  73.2%       29   5.7% std::has_facet
      26   5.1%  78.3%       26   5.1% std::num_put::_M_insert_int
      15   3.0%  81.3%       15   3.0% std::basic_ostream::sentry::sentry
      14   2.8%  84.1%       97  19.1% make_expression
      13   2.6%  86.6%       73  14.4% std::num_put::do_put
      11   2.2%  88.8%       11   2.2% random_r
       9   1.8%  90.6%        9   1.8% strlen
       7   1.4%  91.9%        7   1.4% CXXABI_1.3
       7   1.4%  93.3%        7   1.4% std::basic_ostream::put
       6   1.2%  94.5%      135  26.6% make
       4   0.8%  95.3%        4   0.8% _IO_do_write@@GLIBC_2.2.5
       4   0.8%  96.1%        4   0.8% _init
       4   0.8%  96.9%        4   0.8% std::time_put::put
       3   0.6%  97.4%        3   0.6% _IO_file_write@@GLIBC_2.2.5
       3   0.6%  98.0%        3   0.6% fflush
       3   0.6%  98.6%        3   0.6% std::__numpunct_cache::_M_cache
       2   0.4%  99.0%        2   0.4% __gnu_cxx::stdio_sync_filebuf::file
       2   0.4%  99.4%        2   0.4% std::basic_ios::widen
       2   0.4%  99.8%        2   0.4% std::endl
       1   0.2% 100.0%        1   0.2% rand
       0   0.0% 100.0%        1   0.2% _DYNAMIC
       0   0.0% 100.0%        8   1.6% __bss_start
       0   0.0% 100.0%      143  28.1% __libc_start_main
       0   0.0% 100.0%      143  28.1% main
2)图形分析
$ ./pprof -dot ./test ./myprofiler > test.dot
可是使用Graphviz打开dot文件
QQ: 378890364 微信:wwtree(省短信费) 紧急事宜发短信到0061432027638  本站微博:http://t.qq.com/wwtree QQ群:122538123
描述
快速回复

您目前还是游客,请 登录注册
如果您在写长篇帖子又不马上发表,建议存为草稿