实时阴影绘制技术研究

C++博客 首页 新随笔 联系 聚合 管理
  48 Posts :: 20 Stories :: 57 Comments :: 0 Trackbacks
作者:amure
原文地址:http://www.azure.com.cn/article.asp?id=190

一般而言,比起C程序来说,C++游戏程序是可重用和可维护的。可这真的有价值吗?复杂的C++可以在速度上与传统的C程序相提并论吗?
  如果有一个好的编译器,再加上对语言的了解,真的有可能用C++写出一些有效率的游戏程序来。本文描述了典型的几种你可以用来加速游戏的技术。它假设你已经非常肯定使用C++的好处,并且你也对优化的基本概念相当熟悉。
  第一个经常让人获益的基本概念显然是剖析(profiling)的重要性。缺乏剖析的话,程序员将犯两种错误,其一是优化了错误的代码:如果一个程序的主要指标不是效率,那么一切花在使其更高效上的时间都是浪费。靠直觉来判断哪段代码的主要指标是效率是不可信的,只有直接去测量。第二个概念是程序员经常“优化”到降低了代码的速度。这在C++是一个典型问题,一个简单的指令行可能会产生巨大数量的机器代码,你应当经常检查你的编译器的输出,并且剖析之。

1、对象的构造与析构
  对象的构造与析构是C++的核心概念之一,也是编译器背着你产生代码的一个主要地方。未经认真设计的程序经常花费不少时间在调用构造函数,拷贝对象以及初始化临时对象等等。幸运的是,一般的感觉和几条简单的规则可以让沉重的对象代码跑得和C只有毫厘之差。
  除非需要否则不构造。
  最快的代码是根本不运行的代码。为什么要创建一个你根本不去使用的对象呢?在后面的代码中:

  voide Function(int arg)
  {
    Object boj;
    If(arg==0)
      Return;
    ...
  }

  即便arg为0,我们也付出了调用Object的构造函数的代价。特别是如果arg经常是0,并且Object本身还分配内存,这种浪费会更加严重。显然的,解决方案就是把obj的定义移到判断之后。
  小心在循环中定义复杂变量,如果在循环中按照除非需要否则不构造的原则构造了复杂的对象,那么你在每一次循环的时候都要付出一次构造的代价。最好在循环外构造之以只构造一次。如果一个函数在内循环中被调用,而该函数在栈内构造了一个对象,你可以在外部构造并传递一个应用给它。

  1.1 采用初始化列表
  考虑下面的类:

  class Vehicle
  {
  public
    Vehicle(const std::string &name)
    {
      mName=name
    }
  private:
    std::string mName;
  }

  因为成员变量会在构造函数本体执行前构造,这段代码调用了string mName的构造函数,然后调用了一个=操作符,来拷贝其值。这个例子中的一个典型的不好之处在于string的缺省构造函数会分配内存,但实际上都会分配大大超过实际需要的空间。接下来的代码会好些,并且阻止了对=操作符的调用,进一步的来说,因为给出了更多的信息,非缺省构造函数会更有效,并且编译器可以在构造函数函数体为空的情况下将其优化掉。

  class Vehicle
  {
  public
    Vehicle(const std::string &name):mName(name)
    { }
  private:
    std::string mName;
  }

  1.2 要前自增不要后自增(即要++I不要I++)
  当写x=y++时产生的问题是自增功能将需要制造一个保持y的原值的拷贝,然后y自增,并把原始的值返回。后自增包括了一个临时对象的构造,而前自增则不要。对于整数,这没有额外的负担,但对于用户自定义类型,这就是浪费,你应该在有可能的情况下运用前自增,在循环变量中,你会常遇到这种情形。
  不使用有返回值的操作符 在C++中经常看到这样写顶点的加法:

  Vector operator+(const Vector &v1,const Vector &v2)

  这个操作将引起返回一个新的Vector对象,它还必须被以值的形式返回。虽然这样可以写v=v1+v2这样的表达式,但象构造临时对象和对象的拷贝这样的负担,对于象顶点加法这样常被调用的事情来说太大了一点。有时候是可以好好规划代码以使编译器可以把临时对象优化掉(这一点就是所谓的返回值优化)。但是更普遍的情形下,你最好放下架子,写一点难看但更快速的代码:

  void Vector::Add(const Vector &v1,const Vector &v2)

  注意+=操作符并没有同样的问题,它只是修改第一个参数,并不需要返回一个临时对象,所以,可能的情况下,你也可以用+=代替+。

  1.3 使用轻量级的构造函数
  在上一个例子中Vector的构造函数是否需要初始化它的元素为0?这个问题可能在你的代码中会有好几处出现。如果是的话,它使得无论是否必要,所有的调用都要付初始化的代价。典型的来说,临时顶点以及成员变量就会要无辜的承受这些额外的开销。
  一个好的编译器可以很好的移除一些这种多余的代码,但是为什么要冒这个险呢?作为一般的规则,你希望构造函数初始化所有的成员变量,因为未初始化的数据将产生错误。但是,在频繁实例化的小类中,特别是一些临时对象,你应该准备向效率规则妥协。首选的情况就是在许多游戏中有的vector和Matrix类,这些类显然应当提供一些方法置0和识别,但它的缺省构造函数却应当是空的。
  这个概念的推论就是你应当为这种类提供另一个构造函数。如果我们的第二个例子中的Vebicle类是这样写的话:

  class Vehicle
  {
  public:
    vehicle()
    {
    }
    void SetName(const std::string &name)
    {
      mName=name;
    }
  private:
    std::string mName
  };

  我们省去了构造mName的开销,而在稍后用SetName方法设置了其值。相似的,使用拷贝构造函数将比构造一个对象然后用=操作符要好一些。宁愿这样来构造:Vebicle V1(V2)也不要这样来构造:

  Vehicle v1;v1=v2;

  如果你需要阻止编译器帮你拷贝对象,把拷贝构造函数和操作符=声明为私有的,但不要实现其中任何一个。这样,任何企图对该对象的拷贝都将产生一个编译时错误。最好也养成定义单参数构造函数的习惯,除非你是要做类型转换。这样可以防止编译器在做类型转换时产生的隐藏的临时对象。

  1.4 预分配和Cache对象
  一个游戏一般会有一些类会频繁的分配和释放,比如武器什么的。在C程序中,你会分配一个大数组然后在需要的时候使用。在C++中,经过小小的规划以后,你也可以这样干。这个方法是不要一直构造和析构对象而是请求一个新而把旧的返回给Cache。Cache可以实现成一个模板,它就可以为所有的有一个缺省构造函数的类工作。Cache模板的Sample可以在附带的CD中找到。
  你也可以在需要时分配一些对象来填充Cache,或者预先分配好。如果你还要对这些对象维护一个堆栈的话(表示在你删除对象X之前,你先要删除所有在X后面分配的对象),你可以把Cache分配在一个连续的内存块中。

2、内存管理
  C++应用程序一般要比C程序更深入到内存管理的细节。在C中,所有的分配都简单的通过malloc和free来进行,而C++则还可以通过构造临时对象和成员变量来隐式的分配内存。很多C++游戏程序需要自己的内存管理程序。 由于C++游戏程序要执行很多的分配,所以要特别小心堆的碎片。一个方法是选择一条复杂的路:要么在游戏开始后根本不分配任何内存,要么维护一个巨大的连续内存块,并按期释放(比如在关卡之间)。在现代机器上,如果你想对你的内存使用很警惕的话,很严格的规则是没必要的。
  第一步是重载new和Delete操作符,使用自己实现的操作符来把游戏最经常的内存分配从malloc定向到预先分配好的内存块去,例如,你发现你任何时候最多有10000个4字节的内存分配,你可以先分配好40000字节,然后在需要时引用出来。为了跟踪哪些块是空的,可以维护一个由每一个空的块指向下一个空的块的列表free list。在分配的时候,把前面的block移掉,在释放的时候,把这个空块再放到前面去。图1描述了这个free list如何在一个连续的内存块中,与一系列的分配和释放协作的情形。

图1 A linked free list
[img]http://http://www.linuxeden.com/edu/mays.soage.com/develop/optimize/200112/image/Other/OptFORCGame.gif[/img]

  你可以很容易的发现一个游戏是有着许多小小的生命短暂的内存分配,你也许希望为很多小块保留空间。为那些现在没有使用到的东西保留大内存块会浪费很多内存。在一定的尺寸上,你应当把内存分配交给一支不同的大内存分配函数或是直接交给malloc()。

3、虚函数
  C++游戏程序的批评者总是把矛头对准虚函数,认为它是一个降低效率的神秘特性。概念性的说,虚函数的机制很简单。为了完成一个对象的虚函数调用,编译器访问对象的虚函数表,获得一个成员函数的指针,设置调用环境,然后跳转到该成员函数的地址上。相对于C程序的函数调用,C程序则是设置调用环境,然后跳转到一个既定的地址上。一个虚函数调用的额外负担是虚函数表的间接指向;由于事先并不知道将要跳转的地址,所以也有可能造成处理器不能命中Cache。
  所有真正的C++程序都对虚函数有大量的使用,所以主要的手段是防止在那些极其重视效率的地方的虚函数调用。这里有一个典型的例子:

  Class BaseClass
  {
  public:
    virtual char *GetPointer()=0;
  };

  Class Class1: public BaseClass
  {
    virtual char *GetPointer();
  };

  Class Class2:public BaseClass
  {
    virtual char *GetPointer();
  };

  void Function(BaseClass *pObj)
  {
    char *ptr=pObj->GetPointer();
  }

  如果Function()极其重视效率,我们应当把GetPointer从一个虚函数改成内联函数。一种方式是给BaseClass增加一个新的保护的数据成员,在每一个类中设置该成员的值,在GetPointer这个内联函数中返回该成员给调用者:

  Class BaseClass
  {
  public:
    inline char GetPointerFast()
    {
      return mpPointer;
    }
  protected:
    inline void SetPointer(char *pData)
    {
      mpData = pData;
    }
  private:
    char *mpData;
  };

  void Function(BaseClass *pObj)
  {
    char *ptr= pObj->GetPointerFast();
  }

  一个更激进的方法是重新规划你的类继承树,如果Class1和Class2只有一点点不同,那么可以把它们捆绑到同一个类中去,而用一个Flag来表明它将象Class1还是象Class2一样工作,同时在BaseClass中把纯虚函数去掉。这样的话,也可以象前面的例子一样把GetPointer写成内联。这种变通看起来不是很高雅,但是在缺少Cache的机器上跑内循环时,你可能会很愿意为了去掉虚函数调用而把事情做得更加难看。
  虽然每一个新的虚函数都只给每个类的虚表增加了一个指针的尺寸(通常是可以忽略的代价),第一个虚函数还是在每一个对象上要求了一个指向虚表的指针。这就是说你在很小的、频繁使用的类上使用任何虚函数而造成了额外的负担,这些都是不能接受的。由于继承一般都要用到一个或几个虚函数(至少有一个虚的析构函数),所以你没必要在小而频繁使用的对象上使用任何继承。

4、代码尺寸
  编译器因为C++产生冗长的代码而臭名昭著。由于内存有限,而小的东西往往是快的,所以使你的可执行文件尽可能的小是非常重要的。首先可以做的事情是拿一个编译器来研究。如果你的编译器会在可执行文件中保存Debug信息的话,那么把它们移除掉。(注意MS VC会把Debug信息放在可执行文件外部,所以没关系)异常处理会产生额外的代码,尽可能的去除异常处理代码。确保连接器配置为去除无用的函数和类。开启编译器的最高优化级别,并尝试设置为尺寸最小化而不是速度最大化 — 有时候,由于Cache命中的提高,会产生更好的运行效果。(注意在使用这项设置时检查instrinsic功能是否也处于打开状态)去掉所有Debug输出状态下的浪费空间的字符串,使编译器把多个相同的字符串捆绑成一个实例。
  内联通常是造成大函数的首犯。编译器可以自由的选择注意或忽略你写的inline关键字,而且它们还会背着你制造一些内联。这是另一个要你保持轻量级的构造函数的原因,这样堆栈中的对象就不会因为有大量的内联代码而膨胀。同时也要小心重载运算符,即使是最简短的表达式如m1=m2*m3如果m2和m3是矩阵的话,也可能产生大量的内联代码。一定要深入了解你的编译器对于内联的设置。
  启用运行时类型信息(RTTI)需要编译器为每一个类产生一些静态信息。RTTI一般来说是缺省启用的,这样我们的代码可以调用dynamic_cast以及检测一个对象的类型,考虑完全禁止使用RTTI和dynamic_cast以节省空间(进一步的说,有时候dynamic_cast在某些实现中需要付出很高的代价)另一方面,当你真的需要有基于类型的不同行为的时候,增加一个不同行为的虚函数。这是更好的面向对象设计(注意static_cast与这不同,它的效率和C语言的类型转换一样)。

5、标准类库(STL)
  标准类库是一套实现了常见的结构和算法的模板,例如dynamic arrays(称为vector),set,map等等。使用STL可以节省你很多时间来写和调试那些容器。和之前谈到的一样,如果希望系统的效率最大化,你必须要注意你的STL的具体实现的细节。
  为了能够对应于最大范围的应用,STL标准在内存分配这个领域保持了沉默。在STL容器中的每一个操作都有一定的效率保证,例如,给一个set进行插入操作只要O(log n)的时间,但是,对一个容器的内存使用没有任何保证。
  让我们来仔细了解游戏开发中的一个非常普遍的问题:你希望保存一组对象,(我们会称其为对象列表,虽然不一定要保存在STL的列表中)通常你会要求每个对象在这个表有且仅有一个,这样你就不用担心一个偶然产生的在容器中插入一个已存在单元的操作了。STL的set忽略副本,所有的插入、删除和查询的速度都是O(log n),这是不是就是很好的选择呢?
  虽然在set上的大多数操作的速度都是O(log n),但是这里面依然存在着潜在的危机。虽然容器的内存使用依赖于实现,但很多实现还是在红黑树的基础上实现的。在红黑树上,树的每一个节点都是容器的一个元素。常见的实现方法是在每一个元素被加入到树时,分配一个节点,而当每个元素被移出树时,释放一个节点。根据你插入和删除的频繁程度,在内存管理器上所花费的时间将或多或少的影响你通过使用set而获得的好处。
  另外一个解决方案是使用vector来存储元素,vector保证在容器的末端添加元素有很高的效率。这表示实际上vector只在很偶然的情况下才重新分配内存,也就是说,当满的时候扩容一倍。当使用vector来保存一个不同元素列表的时候,你首先要检查元素是否已经存在,如果没有,那么加入。而对整个vector检查一遍需要花费O(n)的时间,但是但实际牵涉到的部分应该比较少,这是因为vector的每个元素都在内存中连续存放,所以检查整个vector实际上是一个易于cache的操作。检查整个set将造成cache不命中,这是因为在红黑树上分别存放的元素可能散布在内存的各个角落。同时,我们也注意到set必须额外维护一组标记以设置整个树。如果你要保存的是对象的指针,set可能要花费vector所要花费的内存的3到4倍。
  Set的删除操作消耗时间O(log n),看起来是很快,如果你不考虑可能对free()的调用的话。Vector的删除操作消耗O(n),这是因为从被删除的那个元素开始到结尾处的元素,每一个元素都要被拷贝到前一个位置上。如果元素都只是指针的话,那么这个拷贝将可以依靠一个简单的memcpy()来完成,而这个函数是相当快的。(这也是为什么通常都把对象的指针储存在STL的容器中的一个原因,而不是储存对象本身。如果你直接保存了对象本身,将会在很多操作中造成许多额外的构造函数的调用,例如删除等)。
  set和map通常来说麻烦大于有用,如果你还没有意识到这一点的话,考虑遍历一个容器的代价,例如:

  for(Collection::iterator it = Collection.begin(); it != Collection.end(); ++it)

  如果Collection是vector,那么++it就是一个指针自增。但是当Collection是一个set或者是一个map的话,++it包括了访问红黑树上的下一个节点。这个操作相当复杂而且很容易造成cache不命中,因为树的节点几乎遍布内存的各处。
  当然,如果你要在容器中保存大量的元素,并且进行许多的成员请求,那么set的O(log n)的效率完全可以抵消那些内存方面的消耗。近似的,如果你偶尔才使用容器,那么这里的效率差别就非常的小。你应该做一些效率评估以了解多大的n会使set变得更快。也许你会惊奇的发现在游戏的大多数典型应用下vector的所有效率都比set要高。
  这还不是STL内存使用的全部。一定要了解当你使用clear方法时,容器是否真的释放掉了它的内存。如果没有,就可能产生内存碎片。比如,如果你开始游戏的时候建立了一个空的vector,在游戏过程中增加元素,然后在游戏restart时调用clear,这时vector未必释放它的全部内存。这个空的vector,可能依然占据了堆中的内存,并使其变成碎片。如果你真的需要这样来实现游戏的话,对这个问题有两种解法。一是你可以在创建vector时调用reserve(),为你可能需要的最大数量的元素保留足够的空间。如果这不可行的话,你可以强迫vector完全释放内存:

  Vector V;
  // … elements are inserted into V here
  Vector().swap(v);  // causes v to free its memory

  Set、list以及map都没有这个问题,这是因为他们为每个元素分别分配和释放内存。

6、高级特性
  编程语言的某些特性你可能没必要用到。看上去简单的特性可能会导致低下的效率。而看起来复杂的特性没准执行得很好。C++的这些黑暗角落异常依赖于编译器。当你要使用它们时,必须了解它们的代价。
  C++的string就是一个看起来不错的例子,但是在效率极其重要的场合应该避免使用,考虑下面的代码。

  Void Function(const std::string &str)
  {
  }
  Function("hello");

  对Function()的调用包括了对给定const char*参数的构造函数的调用。在普遍的实现中,这个构造函数执行了一个malloc(),一个strlen(),以及一个memcpy(),而析构函数立刻上来做了一些无意义的事情。(由于该例子中的string没有被更多的应用)然后又跟了一个free()。这里的内存分配完全是浪费,因为字符串“hello”早就在程序的数据段中了。我们早就有它在内存中的副本了。如果Function定义了一个const char*的参数,那么完全没有了上面所说的那些额外的调用。这就是为了使用方便的string而付出的高昂代价。
  模板是效率的对立面的一个例子,根据语言标准,编译器在模板实例化为一个具体的类型时产生代码。理论上,看上去是声明了一个模板,但却实际产生了大量的相似的代码。如果你有了class1的指针的vector,也有class2的指针的vector,你就在你的可执行文件中做了两份的vector的拷贝。
  事实上,大多数的编译器做得更好,首先,只有实际被使用到的模板成员函数被产生代码。其次,如果事先了解了正确的行为,编译器可以只产生一份代码的拷贝。你可以从vector的例子发现这一点,确实只产生了一份代码(一般是vector)。有了好的编译器,模板还是可以在保持高效的同时提供你一般编程的好处。
  C++的一些特性,比如初始化列表以及前自增,一般来说可以提高效率。而象其它的一些特性比如运算符重载以及RTTI则看起来似乎是清白的,但却有时带来严重的效率问题。STL的容器则描述了盲目相信函数的算法运行时间可以如何让你误入歧途。避免使用潜在的低效率的语言或类库特性,同时花些时间来了解你的编译器的各种选项。你会很快的学会设计高效的代码,并且解决掉你的游戏中的效率问题。

谈到优化,很多人都会直接想到汇编。难道优化只能在汇编层次吗?当然不是,C++层次一样可以作代码优化,其中有些常常是意想不到的。在C++层次进行优化,比在汇编层次优化具有更好的移植性,应该是优化中的首选做法。
  确定浮点型变量和表达式是 float 型

  为了让编译器产生更好的代码(比如说产生3DNow! 或SSE指令的代码),必须确定浮点型变量和表达式是 float 型的。要特别注意的是,以 ";F"; 或 ";f"; 为后缀(比如:3.14f)的浮点常量才是 float 型,否则默认是 double 型。为了避免 float 型参数自动转化为 double,请在函数声明时使用 float。

  使用32位的数据类型

  编译器有很多种,但它们都包含的典型的32位类型是:int,signed,signed int,unsigned,unsigned int,long,signed long,long int,signed long int,unsigned long,unsigned long int。尽量使用32位的数据类型,因为它们比16位的数据甚至8位的数据更有效率。

  明智使用有符号整型变量

  在很多情况下,你需要考虑整型变量是有符号还是无符号类型的。比如,保存一个人的体重数据时不可能出现负数,所以不需要使用有符号类型。但是,如果是要保存温度数据,就必须使用到有符号的变量。

  在许多地方,考虑是否使用有符号的变量是必要的。在一些情况下,有符号的运算比较快;但在一些情况下却相反。

  比如:整型到浮点转化时,使用大于16位的有符号整型比较快。因为x86构架中提供了从有符号整型转化到浮点型的指令,但没有提供从无符号整型转化到浮点的指令。看看编译器产生的汇编代码:

  不好的代码:

编译前 编译后

double x; mov [foo + 4], 0
unsigned int i; mov eax, i
x = i; mov [foo], eax
flid qword ptr [foo]
fstp qword ptr [x]

  上面的代码比较慢。不仅因为指令数目比较多,而且由于指令不能配对造成的FLID指令被延迟执行。最好用以下代码代替:
推荐的代码:

编译前 编译后

double x; fild dword ptr [i]
int i; fstp qword ptr [x]
x = i;

  在整数运算中计算商和余数时,使用无符号类型比较快。以下这段典型的代码是编译器产生的32位整型数除以4的代码:

  不好的代码 推荐的代码

编译前 编译后

int i; mov eax, i
i = i / 4; cdq
and edx, 3
add eax, edx
sar eax, 2
mov i, eax

编译前 编译后

unsigned int i; shr i, 2
i = i / 4;

  总结:
   无符号类型用于:
   除法和余数
   循环计数
   数组下标
   有符号类型用于:
   整型到浮点的转化
   while VS. for

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

编译前 编译后

while (1); mov eax,1
test eax,eax
je foo+23h
jmp foo+18h

编译前 编译后

for (;;); jmp foo+23h

  一目了然,for (;;)指令少,不占用寄存器,而且没有判断跳转,比while (1)好。

使用数组型代替指针型

  使用指针会使编译器很难优化它。因为缺乏有效的指针代码优化的方法,编译器总是假设指针可以访问内存的任意地方,包括分配给其他变量的储存空间。所以为了编译器产生优化得更好的代码,要避免在不必要的地方使用指针。一个典型的例子是访问存放在数组中的数据。C++ 允许使用操作符 [] 或指针来访问数组,使用数组型代码会让优化器减少产生不安全代码的可能性。比如,x[0] 和x[2] 不可能是同一个内存地址,但 *p 和 *q 可能。强烈建议使用数组型,因为这样可能会有意料之外的性能提升。

不好的代码 推荐的代码

typedef struct
{
   float x,y,z,w;
} VERTEX;
typedef struct
{
   float m[4][4];
} MATRIX;
void Xform(float* res, const float* v, const float* m, int nNumVerts)
{
   float dp;
   int i;
    const VERTEX* vv = (VERTEX *)v;
    for (i = 0; i <; nNumVerts; i++)
   {
     dp = vv->;x * *m ++;
     dp += vv->;y * *m ++;
     dp += vv->;z * *m ++;
     dp += vv->;w * *m ++;
     *res ++ = dp;      // 写入转换了的 x
     dp = vv->;x * *m ++;
     dp += vv->;y * *m ++;
     dp += vv->;z * *m ++;
     dp += vv->;w * *m ++;
     *res ++ = dp;     // 写入转换了的 y
     dp = vv->;x * *m ++;
     dp += vv->;y * *m ++;
     dp += vv->;z * *m ++;
     dp += vv->;w * *m ++;
     *res ++ = dp;    // 写入转换了的 z
     dp = vv->;x * *m ++;
     dp += vv->;y * *m ++;
     dp += vv->;z * *m ++;
     dp += vv->;w * *m ++;
     *res ++ = dp;    // 写入转换了的 w
     vv ++;        // 下一个矢量
     m -= 16;
   }
}
typedef struct
{
   float x,y,z,w;
} VERTEX;
typedef struct
{
   float m[4][4];
} MATRIX;
void Xform (float* res, const float* v, const float* m, int nNumVerts)
{
   int i;
   const VERTEX* vv = (VERTEX*)v;
   const MATRIX* mm = (MATRIX*)m;
   VERTEX* rr = (VERTEX*)res;
   for (i = 0; i <; nNumVerts; i++)
   {
     rr->;x = vv->;x * mm->;m[0][0] + vv->;y * mm->;m[0][1]
         + vv->;z * mm->;m[0][2] + vv->;w * mm->;m[0][3];
     rr->;y = vv->;x * mm->;m[1][0] + vv->;y * mm->;m[1][1]
         + vv->;z * mm->;m[1][2] + vv->;w * mm->;m[1][3];
     rr->;z = vv->;x * mm->;m[2][0] + vv->;y * mm->;m[2][1]
         + vv->;z * mm->;m[2][2] + vv->;w * mm->;m[2][3];
     rr->;w = vv->;x * mm->;m[3][0] + vv->;y * mm->;m[3][1]
         + vv->;z * mm->;m[3][2] + vv->;w * mm->;m[3][3];
   }
}

  注意: 源代码的转化是与编译器的代码发生器相结合的。从源代码层次很难控制产生的机器码。依靠编译器和特殊的源代码,有可能指针型代码编译成的机器码比同等条件下的数组型代码运行速度更快。明智的做法是在源代码转化后检查性能是否真正提高了,再选择使用指针型还是数组型。

[充分分解小的循环]

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

不好的代码 推荐的代码

// 3D转化:把矢量 V 和 4x4 矩阵 M 相乘
for (i = 0; i <; 4; i ++)
{
   r[i] = 0;
   for (j = 0; j <; 4; j ++)
   {
     r[i] += M[j][i]*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];

  [避免没有必要的读写依赖]

  当数据保存到内存时存在读写依赖,即数据必须在正确写入后才能再次读取。虽然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;
}

  Switch 的用法

  Switch 可能转化成多种不同算法的代码。其中最常见的是跳转表和比较链/树。推荐对case的值依照发生的可能性进行排序,把最有可能的放在第一个,当switch用比较链的方式转化时,这样可以提高性能。此外,在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;
}

  所有函数都应该有原型定义

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

  [尽可能使用常量(const)]

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

提升循环的性能

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

  不好的代码(在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()的值,这样可以避免重复计算。虽然不好的代码中的分支可以简单地预测,但是由于推荐的代码在进入循环前分支已经确定,就可以减少对分支预测的依赖。   把本地函数声明为静态的(static)

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

  考虑动态内存分配

  动态内存分配(C++中的";new";)可能总是为长的基本类型(四字对齐)返回一个已经对齐的指针。但是如果不能保证对齐,使用以下代码来实现四字对齐。这段代码假设指针可以映射到 long 型。

  例子

  double* p = (double*)new BYTE[sizeof(double) * number_of_doubles+7L];
double* np = (double*)((long(p) + 7L) &; –8L);

  现在,你可以使用 np 代替 p 来访问数据。注意:释放储存空间时仍然应该用delete p。

  使用显式的并行代码

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

  不好的代码 推荐的代码

double a[100], sum;
int i;
sum = 0.0f;
for (i=0; i<;100; i++)
   sum += a[i];

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[i];
   sum2 += a[i+1];
   sum3 += a[i+2];
   sum4 += a[i+3];
}
sum = (sum4+sum3)+(sum1+sum2);

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

提出公共子表达式

  在某些情况下,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;

  结构体成员的布局

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

  按类型长度排序

  把结构体的成员按照它们的类型长度排序,声明成员时把长的类型放在短的前面。

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

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

  不好的代码,普通顺序 推荐的代码,新的顺序并手动填充了几个字节

struct
{
   char a[5];
   long k;
   double x;
} baz;
struct
{
   double x;
   long k;
   char a[5];
char pad[7];
} baz;

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

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

  当编译器分配给本地变量空间时,它们的顺序和它们在源代码中声明的顺序一样,和上一条规则一样,应该把长的变量放在短的变量前面。如果第一个变量对齐了,其它变量就会连续的存放,而且不用填充字节自然就会对齐。有些编译器在分配变量时不会自动改变变量顺序,有些编译器不能产生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;

  避免不必要的整数除法

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

  不好的代码 推荐的代码

int i, j, k, m;
m = i / j / k;
int i, j, k, m;
m = i / (j * k);

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

  避免在函数中频繁使用指针型参数指向的值。因为编译器不知道指针之间是否存在冲突,所以指针型参数往往不能被编译器优化。这样是数据不能被存放在寄存器中,而且明显地占用了内存带宽。注意,很多编译器有“假设不冲突”优化开关(在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;
}

赋值与初始化
先看看以下代码:

class CInt
{
   int m_i;

public:
   CInt(int a = 0):m_i(a) { cout <;<; ";CInt"; <;<; endl; }
   ~CInt() { cout <;<; ";~CInt"; <;<; endl; }

  CInt operator + (const CInt&; a) { return CInt(m_i + a.GetInt()); }

  void SetInt(const int i)  { m_i = i; }
   int GetInt() const      { return m_i; }
};
不好的代码 推荐的代码
void main()
{
   CInt a, b, c;
   a.SetInt(1);
   b.SetInt(2);
   c = a + b;
}
void main()
{
   CInt a(1), b(2);
   CInt c(a + b);
}

  这两段代码所作的事都一样,但那一个更好呢?看看输出结果就会发现,不好的代码输出了四个";CInt";和四个";~CInt";,而推荐的代码只输出三个。也就是说,第二个例子比第一个例子少生成一次临时对象。Why? 请注意,第一个中的c用的是先声明再赋值的方法,第二个用的是初始化的方法,它们有本质的区别。第一个例子的";c = a + b";先生成一个临时对象用来保存a + b的值,再把该临时对象用位拷贝的方法给c赋值,然后临时对象被销毁。这个临时对象就是那个多出来的对象。第二个例子直接用拷贝构造函数的方法对c初始化,不产生临时对象。所以,尽量在需要使用一个对象时才声明,并用初始化的方法赋初值。

  尽量使用成员初始化列表

  在初始化类的成员时,尽量使用成员初始化列表而不是传统的赋值方式。

  不好的代码 推荐的代码

籧lass CMyClass
{
   string strName;

public:
   CMyClass(const string&; str);
};

CMyClass::CMyClass(const string&; str)
{
   strName = str;
}
class CMyClass
{
   string strName;
   int i;

public:
   CMyClass(const string&; str);
};

CMyClass::CMyClass(const string&;str)
   : strName(str)
{
}

  不好的例子用的是赋值的方式。这样,strName会先被建立(调用了string的默认构造函数),再由参数str赋值。而推荐的例子用的是成员初始化列表,strName直接构造为str,少调用一次默认构造函数,还少了一些安全隐患。
posted on 2006-03-18 00:03 苦行僧 阅读(1352) 评论(2)  编辑 收藏 引用 所属分类: 转载

Feedback

# re: C++ 代码优化 2006-08-06 20:59 jiffwan
楼主前面所说的优化大概还能算得上一些基本常识。
后面越说越糊涂了,哪能用编译后的汇编来说明"C++"的优化?要知道C++代码被编译成什么样的汇编,是编译器决定的,这意味着你所谓的"优化"没有任何意义,或是离开你所用的那个牌子、那个版本的编译后没有任何意义,所以谈不上优化。  回复  更多评论
  

# re: C++ 代码优化 2007-04-06 10:23 jaogoy
的确,就像for和while比较:

4: for(; i<2; ++i);
0040102F jmp main+2Ah (0040103a)
00401031 mov eax,dword ptr [ebp-4]
00401034 add eax,1
00401037 mov dword ptr [ebp-4],eax
0040103A cmp dword ptr [ebp-4],2
0040103E jge main+32h (00401042)
00401040 jmp main+21h (00401031)
5: while(i<2)++i;
00401042 cmp dword ptr [ebp-4],2
00401046 jge main+43h (00401053)
00401048 mov ecx,dword ptr [ebp-4]
0040104B add ecx,1
0040104E mov dword ptr [ebp-4],ecx
00401051 jmp main+32h (00401042)

基本没区别,不能拿些不对称的来说明问题  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理