我們是如何優化英雄聯盟的代碼的

原文鏈接： RANDOM ACTS OF OPTIMIZATION

譯者：杰微刊--張帆

對于像英雄聯盟這樣不斷演進的產品的開發者而言，需要不斷的致力于與系統的熵作斗爭，因為他們將越來越多的內容添加到資源有限的服務器中。新的內容帶了新的隱性成本——不僅是更多的實施成本，同時也包括由于創造了更多的紋理、仿真和處理造成的內存和性能成本。如果我們忽略（或者錯誤估算）了這些成本，則整體游戲性能不佳，可玩性減少。故障使人厭惡，延遲使人憤怒，幀率下降讓人沮喪。

我是致力于提高英雄聯盟性能團隊中的一員。我們為客戶端和服務器做快照，發現問題 (性能相關和其他)，然后修復問題。同時，我們將在這個過程中學到的東西反饋其他團隊，并且給他們提供工具，使他們在影響用戶之前來檢測并定位他們自己的性能問題。我們不斷的提高英雄聯盟的性能為藝術家和設計師添加新的東西提供了空間：當他們使游戲更龐大更優秀的同時，我們使之更快。

這是關于我們團隊如何優化英雄聯盟性能系列的第一篇文章，后續我們將不斷持續更新。這是一項回報豐厚的挑戰，這篇文章將深入介紹我們在粒子系統中遇到的一些有趣的挑戰——正如在下圖中，你可以看到粒子系統在游戲中扮演了十分重要的角色。

上圖是在英雄聯盟游戲中高粒子密度的一個例子。

優化，并不是在程序集中重寫大量的代碼——盡管有些時候是這樣的。我們僅變更那些不僅能夠提高性能，而且維護正確性的代碼，如果有可能的話，還會提高代碼質量。最后一項略顯挑剔：任何不易讀、不易維護的代碼都會產生技術債務，這個我們稍后再談。

優化已有的代碼庫，我們采用了三個基本步驟：鑒別、理解和迭代。

• 步驟一鑒別

  在開始之前，我們首先需要確認哪些代碼需要進行優化。即使有些代碼看起來明顯性能較差，但是由于其對整體性能影響極小，優化這類代碼收益極少（尤其當花費在上面的時間和精力在其他方面可以做到更好的收益）。我們使用代碼檢測工具和采樣分析器來幫助識別非性能部分的基本代碼。 

• 步驟二理解

  一旦我們得知代碼庫的哪部分代碼性能較差，我們便會詳細的查看這部分代碼以求完全理解代碼。理解代碼意味著理解這些代碼的含義及原本的目的。接著，我們就能知悉為何這些代碼產生瓶頸了。

• 步驟三迭代

  當我們理解了為何特定部分代碼執行較慢及代碼本意要執行的內容，我們就有了足夠的信息來設計和開發一套可行的解決方案。使用鑒別步驟中的工具和得到的快照數據，我們將新代碼和舊代碼的性能做了比較。如果解決方案效果出眾，我們會徹底的進行測試以確保不引入來新的bug，那么接下來就可以擊掌慶賀了，因為我們已經為其他內部測試做好了充分的準備。在大多數情況下，新的代碼不見得足夠快，所以我們不斷迭代解決方案，知道新的代碼能達到優化的目的。

現在，讓我們看下在英雄聯盟代碼庫中這幾個步驟的實施細節，并以最近優化的粒子系統逐步介紹。

Waffles截圖

Waffles提供了一個實時展示界面，并提供詳細的性能信息。上圖是Waffles如何展現客戶端性能表現的經典例子，上邊圖形（綠色柱狀圖）以毫秒為單位表示了幀率——越高的柱狀圖表示越低的幀率。非常慢的幀率在游戲中是可以感受得到的。柱狀圖下面是重要功能的分層視圖，通過點擊任何綠色柱狀圖，工程師都會看到影響該幀率的詳細信息。通過這里，我們可以看出些端倪，即哪部分代碼運行時導致性能較差的關鍵。

我們使用一個簡單的宏在代碼庫內手工檢測一些重要函數來提供這份性能相關的信息。在對外發布的游戲版本中，這個宏并沒有被打包編譯，但在測試版本打包中，這個宏作為一個很小的class存在，它創建了一個事件，存放于配置文件緩沖區。該事件包含一個字符串識別碼、一個線程ID、一個時間戳和其他必要的信息（比如它還可以存儲在其生命周期內所有發生的內存配置數）。當對象超出范圍后，析構器會在配置緩沖區中更新該事件自構造以來的運行時間。在隨后的時間，可以輸出和解析此配置文件緩沖區——理想的情況是在另一個進程進行以盡量減少對游戲本身的影響。

在這個例子中，我們將分析緩沖區輸出到文件，并且讀入到構建在Chrome瀏覽器中可視化工具中（關于跟蹤工具的更多信息，可以點擊這里，你可以在自己的Chrome瀏覽器中通過在地址欄敲入"chrome://tracing/"進行嘗試。這個擴展程序被設計用來進行網頁性能分析，輸入格式是JSON，所以你可以輕松的根據你自己的數據構造輸入）。通過圖形化后的結果，我們可以看到哪些是執行較慢的函數，或者在那里不斷有大量的小函數被調用：這些都是次優代碼的跡象。

讓我來展示詳細操作：上面的視圖是Chrome Tracing的視圖，圖中展示了客戶端上兩個運行的線程。上部分的是主線程，執行大多數的處理工作，底部的是粒子線程，用來執行粒子處理。每一個著色的橫條均對應一個函數，橫條的長度指示了其執行時間。被調用的函數由豎直棧結構展示，父函數在子函數之上。這個工具提供給我們一種非常神奇方式來可視化執行復雜度以及幀的簽名時間。當我們發現一個次優代碼區域，我們可以放大粒子區域以求查看更多細節.

Chrome Tracing放大效果圖

讓我們放大圖形中間部分。從上面的線程中我可以看到一個非常長的等待，只有當下面的粒子模擬函數執行完畢才結束。模擬功能包含大量不同函數（著色的橫條）的調用。每一類都是粒子系統的更新功能，用于將位置、 方向和每個粒子在該系統中其他可見性狀態進行更新。一個明顯的優化方式是將模擬函數改造成多線程方式，即可運行在主線程中，也可以在粒子線程中執行，對于本例，我們僅關注優化模擬代碼本身。

既然現在我們知道去何處查看性能問題，我們可以切換到樣本分析。這類分析周期性的讀取和存儲程序計數器和運行中的進程的棧信息（可選）。一段時間后，這個信息可以給出一個隨機概述，概述中描述了代碼庫內的耗時。較慢的函數會得到更多的樣本，更有用的是，用時最長的單個函數會累積更多的樣本。在這里，我們不僅可以看到哪些函數執行最慢，同時可以看到哪幾行代碼執行最慢。如今有很多不錯的樣本分析工具可供選擇，從免費的Very Sleepy到更多特性支持的商業軟件，如Intel的VTune。

通過在游戲客戶端上運行VTune來檢查粒子線程，我們可以看到如下列表中運行最慢的函數。

VTune中的Hot Functions

上面的表格展現了一些粒子相關的函數。作為參考，最上面兩個較大的函數用于為每個粒子更新矩陣和位置、方向相關的狀態。舉例來說，我們來看在第三和第九項AnimatedVariableWithRandomFactor<>中的Evaluate函數，函數很小（并且容易理解），但是相對而言比較耗時。

這個類其實已經做過了優化，通過查表的方式，對每個timestep所需要的值都預先計算過并存儲在一個數組中，所以在讀取這些數值時不必再次計算，所以減少了計算的耗時。這是一個明智的選擇，因為曲線的一階和二次集成是一個昂貴的進程。為每個系統中的每個粒子上的動畫變量進行這個操作會使得處理過程大大減少。

動畫變量曲線的查詢表

在查詢性能問題時，通過找到最壞的場景來放大問題往往是一個十分有用的技巧。為了模擬粒子處理減緩，我開始了一場單個玩家的游戲，游戲中有9個中期級別的電腦，并且在下路挑起了一場混亂的團戰。接著，我在團戰期間在客戶端上運行了VTune，記錄了大量的數據用于分析。這些數據給出了在Evaluate代碼中的歸因樣本（如下圖所示）。

下圖中我截取了第91-95行代碼，為了更好的說明第90行調用Evaluate的情形。

VTune中的分析樣本

對于不熟悉VTune的人來說，其實這個試圖展示的就是解析期間所收集的代碼。右側的紅色橫條指示了命中次數，橫條越長就意味著命中次數越多，而命中次數越多表示這一行執行越慢。挨著橫條的時間是處理這行代碼所用的預估時間。你也可以就某個特定函數的到一個準確視圖來查看是什么因素“貢獻”了執行緩慢。

如果就紅色的橫條來看，第95行代碼就是問題所在。但是這段代碼所做的僅僅是在Vector3f中復制出拼寫錯誤的查詢表，為什么這個函數成為最慢的部分呢？為什么12字節的復制這么慢？

答案在于現代CPU訪問內存的方式中。CPU非常忠實的遵循了摩爾定律，每年都會提速60%，而內存速度每年的增速只有可憐的10%。

圖出自《計算機體系結構：量化研究方法》By John L. Hennessy, David A. Patterson, Andrea C. Arpaci-Dusseau

緩存可以減小性能差距，運行英雄聯盟的大多數CPU都有3級緩存，一級緩存最快但容量最小，三級緩存最慢但容量相對最大。從一級緩存讀取數據只需要4個周期，而讀取主內存卻需要大約300個周期甚至更多。你可以在300個周期內做大量處理工作。

最初查詢表的解決方案的問題在于，雖然從查詢表中的順序讀取值的操作是非常快的(由于硬件預取)，但是我們正在處理的顆粒并不是按照時間順序存儲，所以實際查找順序是隨機的。這通常會導致CPU等待從主存儲設備讀取數據時產生延遲。雖然300個周期比一級或者二級集成代價更低，但我們還是需要知道這個函數在游戲中的使用頻率如何，因為畢竟這個函數在游戲中被大量的使用。

為了探求真相，我們在代碼中添加一些額外的內容來收集AnimatedVariables的數量和類型。結果表示，在38000個AnimatedVariables中：

①37500個是線性插值；100個是一級，400個是二級②31500個僅有一個關鍵值；2500個有3個關鍵值；1500有2個或者4個關鍵值

所以最常見的途徑是針對單鍵值。因為代碼總是生成查詢表，這就產生了一個不需要傳播的單數值表。也就意味著每次查詢（總是返回相同值）一般會產生緩存丟失，進而導致大量的內存和CPU周期浪費。

通常來講，代碼成為瓶頸一般有四個原因：

這里產生的問題原因不是由于代碼設計不好或者開發質量導致。解決方案是好的，但是在被美術師大量使用之后，普通路徑是針對單值的，而這些簡單的問題在使用過程中是很不明顯的。

順便說一句，我學會了作為一名程序員最重要的事情之一便是尊重你正在處理的代碼。代碼有可能看起很瘋狂，但是這樣寫的目的可能是基于一個好的出發點。在沒有完全理解代碼如何使用和其為何設計之前不要錯誤的認為這些代碼是丑陋愚蠢的。

來自：http://codesoftly.com/2010/03/ha-code-entropy-explained.html

在某些情況下，當我們不使用查詢表時，首先構造這些表是沒有意義的，所以會釋放大量意義非凡的內存（大多數表具有256個條目或者更多，每個條目可達12字節的大小，這相當于大約每張表3kb）。所以現在，我們可以使用額外的一些內存來添加緩存的條目和存儲的單值的數量。

之前的代碼看起來是這個樣子的：

templateclass AnimatedVariable
{
    //private:
    std::vectormTimes;
    std::vectormValues;
};

templateclass AnimatedVariablePrecomputed
{
    //private:
    std::vectormPrecomutedValues;
};</pre> 
 
AnimatedVariablePrecomputed對象在AnimatedVariable中進行構造，從它的指定大小插值和構建一個表。Evaluate()僅在預計算對象中被調用。我們修改了一下AnimatedVariable類，現在看起來是這個樣子的： 

templateclass AnimatedVariable
{
    //private:
    int mNumValues;
    T mSingleValue;


struct Key
{
    float mTime;
    T     mvalue;
};
std::vectormKeys;
AnimatedVariablePrecomputed*mPrecomputed;

};</pre> 
 
我們添加了一個緩存值mSingleValue，和一個整數mNumValues，用于告訴我們何時才使用mSingleValue。如果mNumValues是1（即對應單值的情況），Evaluate()會直接返回mSingleValue的值——不需要其他多余的處理。你還可以注意到插入時間和值構造的Key能夠減少緩存未命中的情況。

指向此類的數據向量大小現在范圍從24到36個字節不等，具體取決于模板類型（同時也依賴與平臺，std::vector<>的大小也會不同）。
Evaluate()之前的代碼看起來是這樣子的：
templateT AnimatedVariablePrecomputed::Evaluate(float time) const
{
    in numValues = mPrecomputedValues.size();
    RIOT_ASSERT(numValues > 1);


int index = static_cast(time * numValues);
// clamp to valid table entry to handle the 1.0 boundary or out of bounds input
index = Clamp(index, 0, numValues - 1);
return mPrecomputedValues[index];

}</pre> 
 
修改后的Evaluate()方法代碼如下，這是在VTune中展示的。你可以看到三個可能的執行case：單值（紅色部分），線性插值（藍色部分）和預計算查詢（綠色部分）。

  
在VTune中展示的優化過的代碼片段
修改后的代碼執行速度大約快了3倍：在最慢的函數列表中該函數從第三位降到了第22位！不僅執行更快，同時還降低了內存的使用，大約減少了750kb。這還不算完，不僅函數執行更快，占內存更少，同時提高了線性插值的準確度。可謂一石三鳥。
這里并沒有提到的內容（盡管文章已經足夠長了）是我如何通過不斷迭代找到了這個解決方案。我最初的嘗試減少在粒子生命周期內樣本表的大小。這個方案幾乎有效——但有些移動較快的粒子由于樣本表的減少，變的參差不齊。幸運的是，這個現象很快就被發現了，使得我依然能夠將方案更換為本文中提到的方法。當然還有一些其他的代碼修改，但是對于性能提高并沒有直接效果，也有些代碼的修改甚至造成了代碼執行更慢。
總結
本文中介紹的是英雄聯盟游戲代碼庫中代碼優化的一個典型案例。雖然變動很小，但是這個改動使得內存節約了750kb，粒子線程比較之前運行快了1到2毫秒，這使得主線程執行的更快。
 
  
當程序員尋求優化的時候，雖然看似顯而易見，但這里提到的三個階段都常常會被忽視。這里只是為了強調一下：

  
1.鑒別：分析應用并找出性能最差的部分

  
2.理解：理解代碼的本意和執行緩慢的原因

  
3.迭代：基于上面兩個階段的到的成果進行代碼的修改、迭代，并重新分析。重復這三個步驟直到足夠快。

 
上面提到的解決方案不見得是最快的解決方案，但至少方向是正確的——性能提升的安全路徑是通過迭代改進。
 </div>