[DOD Series][GCAP09] Pitfalls of Object Oriented Programming

harmful.cat-v.org

從這篇文章起，寫一個Data Oriented Design系列，希望能拋磚引玉，給大家帶來啟發。

主要講OOP review，舉幾個例子，優化，總結

OOP老生常談了

OOP以對象和對象間的相互作用來思考問題，每個對象包含自己的方法和數據，自己是黑盒

對象的好處：復用、沒有副作用好維護，不需要知道其內部實現就可使用

又黑我詹

79年開始開發，83年命名C++，85年第一個商業版本，89年v2.0，加入了我們目前所熟知的特性，98年標準化C++98，03年升級C++03，文章寫於09年，所以還沒C++11/14/17

從79年到現在將近40年的時間，根據摩爾定律硬體發生了巨大的變化

CPU性能暴漲

CPU-Memory之間的傳輸性能增長不到10x

相對的，內存讀取速度比79年變得更慢，從~1c增加到~400c

跟OO有什麼關係呢：OO封裝了數據

從目前的硬體來看，過度封裝是有害的，數據的處理應該作為基本點考慮（OOD）

考慮一個簡單的OO場景樹，OBJ包含通用的數據，Node作為容器，Modifier用來更新坐標，Drawable用於渲染

OBJ，矩陣，bounding sphere，用於優化的dirty標誌，指向父節點的指針

其內存布局，每個grid是4B，matrix是16B aligned

Node加了兩個數據

考慮獲得WorldBoundingSphere的函數，需要更新自己的worldTransform，並對當前Node中所有的OBJ調用GetWorldBS來獲取它們的並集

葉子結點根據dirty狀態來返回BS

什麼問題？

分支判斷預測一旦失敗，會有23-24c的懲罰延遲（打斷CPU流水線）

而最主要的計算則只需要12c

所以用了dirty標誌位反而更慢（分支預測失敗的情況）

圖示L2 cache，cacheline假設128B

parentTransform之前已經在cache中了

假設cacheline從結構體頭部開始

載入m_Transform

M_worldTransform也需要預讀進cache（需要寫回內存）

讀m_Objects（已經在cache中了）

Vector需要索引實際指向的內容，存放OBJs指針的一塊內存，需要load cache

第一個指針指向的instance（part1）放入內存，需要讀取它的虛表指針，load cache

虛表load cache

虛表指向的代碼段load cache（L2不分instruction cache/data cache）

需要檢查dirty標誌，OBJ instance（part 2）load cache

返回的結果累積到expand BS上

輪到下一個OBJ了

第一個OBJ處理至少7個cache miss

接下來的OBJs每個至少2個cache miss

測試用例，1w個OBJ，5層深度的tree

就只是遍歷tree，2.79ms

為什麼這麼慢

其中Node::GetWorldBS佔了89%的sample熱點

從C++代碼上可能有些看不清楚，為什麼有這麼49多的熱點

彙編會清楚說明是compare

因為misprediction會造成前面的load流水打斷，引起CPU stall

接下來的矩陣乘法也一樣

一共47690+2731個Branch

L2 Cache miss：36345，每個~400c，一共~4.54ms

從profiler來看，每個OBJ有~3個L2 cache miss。這些cache

如何改進？

初步嘗試使用相同的（指針指向）連續數據

使用自定義的allocator，連續分配內存

35%的性能提升！

下一步，1）按照順序處理數據 2）層級關係使用隱含的結構表示，避免node間的指向（內存跳轉） 3）按照cache大小考慮來一批次的處理code邏輯 4）經常使用的virtual函數改為非虛函數

層級關係

可以改為對每個層級使用內存連續的數組

根據固定的子節點數目去index，能保證node和數據都是連續分配的

盡量讓處理操作作為全局的過程，比如把update從OBJ class中拉到全局，統一處理所有的OBJ，避免virtual，而且更容易理解函數在做什麼（更容易解釋函數的性能耗時）

OOP下面Update的過程如下：

Bounding sphere向上傳遞信息，tranform向下傳遞信息，數據access和代碼是一段一段分割的

把上述方法變成兩個pass，從上到下更新所有的transform，從下到上更新所有的bounding sphere

所有的node從上到下做一遍

所有的node從下到上做一遍

注意指針全是指向連續的內存空間操作數據（指針++）

來看看Cache

把parent node以及其tranform放進cache

接下來不需要load children node，只需要把其指向的matrix load進來即可，而且這段內存還是連續的，一個cacheline可以load多個child matrix

Bounding Sphere同理

對於下一個child，matrix/BS已經load進cache中了

接下來兩個child也只引發了2個cache miss

而且因為數據是連續的，所以我們可以預測接下來需要的數據，進行預載入（prefetch）

Profiler顯示每個node大約1.7個cache miss，而且這些miss更加集中頻繁（沒有執行代碼/cache miss的interleave，所以整套CPU流水更少被打斷）

提升4倍！

Prefetch可以預熱cache

PS3的prefetch指令（VS中可以用intrinsic _mm_prefetch）

提升6倍！

Prefetch需要考慮其他線程，線程間大量的cache use會造成thrash

整體性能提升1.3倍

現在熱點分布在render上了

Update的sample數量明顯變少，~20

Misprediction從4.7w變為2.8k，cache miss從3.6w變為1.6w

總結，需要考慮數據

OO也不是一無是處，注意不要鑽牛角尖，能否把數據/代碼跟OBJ解耦？要多關注編譯器和硬體

首先優化數據，接下來才是代碼，越簡單越好

相同的代碼/數據要聚類

記住你是在做遊戲，所有的數據必須有你控制，不要害怕去預處理它，我們是為了特殊的目的去設計，而不是去設計通用性

OOD帶來更好的性能，更好的優化實現，更簡單的代碼，更容易並行的代碼

End

注意數據結果大部分都是PS3中得到的，PS3的架構和PC不同，cache miss/branch misprediction penalty比PC要大很多，這點需要注意鑒別

多說一句，目前遊戲界流行ECS跟OOD的思想啟迪是分不開的。從底層硬體角度來看的話，Entity來取代指針的功能，索引連續的內存空間；Component代表了連續儲存的數據，cache-friendly；System代表了Global function/method，來統一分開處理各個功能，less

所以我們對設計模式的運用和熟悉都是根據真實環境一步一步演化而來的，沒有真的silver