Linux 編程之C++遊戲程序優化

　　 一般而言，比起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


　　 你可以很容易的發現一個遊戲是有著許多小小的生命短暫的內存分配，你也許希望為很多小塊保留空間。為那些現在沒有使用到的東西保留大內存塊會浪費很多內存。在一定的尺寸上，你應當把內存分配交給一支不同的大內存分配函數或是直接交給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的容器則描述了盲目相信函數的演算法運行時間可以如何讓你誤入歧途。避免使用潛在的低效率的語言或類庫特性，同時花些時間來了解你的編譯器的各種選項。你會很快的學會設計高效的代碼，並且解決掉你的遊戲中的效率問題。

7、其他參考
　　 Thanks to Pete Isensee and Christopher Kirmse revIEwing this gem.
　　 Cormen, Thomas, Charles Leiserson, and Ronald Rivest, Introduction to Algorithms, Cambridge, Massachusetts, MIT Press, 1990
　　 Isensee, Peter, C++ Optimization Strategies and Techniques, www.tantalon.com/pete/cppopt/main.htm Koenig, Andrew "Pre-or Postfix Increment"
　　 The C++ Report, June,1999 Meyers, Scott, Effective C++, Second Edition, Reading, Massachusetts: Addison-Wesley Publishing Co., 1998.
　　 Sutter, Herb, Guru of the Week #54: Using Vector and Deque, www.gotw.ca/gotw/054.htm

Tags: linux system 內核