遊戲設計模式——面向數據編程（新）
- 2019 年 10 月 27 日
- 筆記
目錄
隨著軟體需求的日益複雜發展，遠古時期面的向過程編程思想才漸漸萌生了面向對象編程思想。
當人們發現面向對象在應對高層軟體的種種好處時，越來越沉醉於面向對象，熱衷於研究如何更加優雅地抽象出對象。
然而現代開發中漸漸發現面向對象編程層層抽象造成臃腫，導致運行效率降低，而這是性能要求高的遊戲編程領域不想看到的。
於是現代遊戲編程中，面向數據編程的思想越來越被接受（例如Unity2018更新的ECS框架就是一種面向數據思想的框架）。
面向數據編程是什麼？
先來一個簡單的比較：
面向過程思想：考慮解決問題所需的各個步驟（函數）。
面向對象思想：考慮解決問題所需的各個模型（類）。
面向數據思想：著重考慮數據的存取及布局（數據）。
那麼所謂的考慮數據存儲/布局是什麼意思呢？
這裡引入2個有關CPU處理數據的概念：
-
單指令流多數據流（SIMD）
-
CPU快取（CPU Cache）
單指令流多數據流(SIMD)
什麼是SIMD
SIMD全稱Single Instruction Multiple Data，單指令流多數據流，是一種採用一個控制器來控制多個處理器，同時對若干個數據分別執行相同的操作從而實現空間上的並行性的技術。
簡單來說，SIMD技術可以讓CPU在一個指令周期執行多個數據的操作（不過操作需要一樣），而不是一個指令周期執行一個數據的操作。
為什麼需要SIMD
在上面的介紹里，我們可以直觀的知道最大的好處在於：可以允許CPU利用並行性快速處理多個數據。
但是局限性還是有的，SIMD技術一般對矢量算術型操作（例如矢量相加，矢量相乘）支援的很好，而不支援其他類型操作（例如分支判斷和跳轉）。
所以SIMD技術常用於CPU數據計算密集型應用，例如：
- 人工智慧
- 物理計算
- 粒子系統
- 光線追蹤
- 影像處理
支援SIMD技術的指令集
X86架構的CPU所支援SSE/SSE2/SSE3指令集就是典型的重點針對/支援SIMD功能的指令集。
目前的PC的CPU架構絕大多數都是Intel的X86架構，而ARM架構的CPU可以在很多消費性電子產品上看到，從可攜式裝置（PDA、行動電話、多媒體播放器、掌上型電子遊戲，和電腦）到電腦外設（硬碟、桌上型路由器）甚至在導彈的彈載電腦等軍用設施中都有它的存在。
(vs2019里項目設置可以找到指令集設置選項)
我們可以在IDE/編譯器里設置好支援SIMD技術的指令集選項。
使用SIMD編程
使用彙編內聯
缺陷：
- 彙編程式碼需根據不同平台訂製（無跨平台特性）
- 彙編程式碼複雜，開發效率低
使用指令集庫
缺陷：
- 程式碼需根據不同平台指令集，包含不同指令集庫頭文件（無跨平台特性）
使用ISPC語言
ISPC是英特爾推出的面向CPU的著色器語言，它適用多種指令集的矢量指令（如SSE2、SSE4、AVX、AVX2等）。
ISPC是基於C語言的，所以它大部分語法和C語言是一致的，可以減少學習成本。
ISPC源程式碼，經過編譯後輸出.obj文件和.h文件。這樣我們在編寫C/C++程式時可以包含該頭文件以使用ISPC程式碼。
下面簡單提供個程式碼示例比較：
// C/C++ Code id rgb2grey(int N, float R[], float G[], float B[], float grey[]) { for (int i = 0; i < N; i++) { grey[i] = 0.3f * R[i] + 0.59f * G[i] + 0.11f * B[i]; } }// ISPC Code export void rgb2grey(uniform int N, uniform float R[], uniform float G[], uniform float B[], uniform float grey[]) { foreach(i = 0 ... N) { grey[i] = 0.3f * R[i] + 0.59f * G[i] + 0.11f * B[i]; } }ISPC語言的語法非常易學，因為它的關鍵字真的很少：
- 類似於C/C++的關鍵字：if, else, switch, for, while, do…while, goto
- 當然也有為了支援並行循環的關鍵字：foreach, foreach_active, foreach_tiled, foreach_unique
- 還有其它一些不常用關鍵字就不列舉了
更具體的ISPC語法就不多講解，可以自己自行去查看官方文檔(文章末尾參考部分會給出鏈接)。
在線編譯器godbolt，可以用於測試ISPC程式碼及調試彙編程式碼：Compiler Explorer
並行循環
// C/C++ Code void func(int N, float A[], float B[], float C[]) { for (int i = 0; i < N; i++) { C[i] = A[i] * B[i]; } }上面是一個正常的C/C++循環程式碼，這樣就是一般的分量操作，如下圖左側：
在ISPC語法里，只需簡單的寫上foreach(i = 0 … N) ，IPSC編譯器編譯時會為其編譯成圖中右側的行為，即一次循環並行處理M個元素，實際循環N/M次。
// ISPC Code export void rgb2grey(int N, uniform float A[], uniform float B[], uniform float C[]) { foreach(i = 0 ... N) { C[i] = A[i] * B[i]; } }更方便的是，ISPC會自動處理並行循環的邊界情況（例如每次並行處理4個元素時，N/4次循環後余出1~3個元素）。
避免Gather行為
這是一個正常的顏色結構，文中定義了若干個顏色對象。
struct Color{ float r,g,b; }; Color colors[1024];SIMD技術讀取變數一般都是連續若干個（在圖中為4個）變數一次性讀取，這種行為叫做矢量讀取。
而由於上文的顏色結構定義，其記憶體分布則如圖中的上部分。
要對4個紅色分量進行操作時，則需要進行多次讀取，這被稱為Gather行為。
struct VaryingColor{ float r[vectorLen]; float g[vectorLen]; float b[vectorLen]; }; Color colors[1024/vectorLen];倘若我們使用如下結構定義，則記憶體分布會如圖中下部分。這樣就能一次讀入4個紅色分量，高效地利用SIMD技術。這種結構被稱為SIMD友好型結構。
在ISPC語言里，使用varying類型可以方便的定義SIMD友好型結構。
CPU快取（CPU cache）
在組裝電腦購買CPU的時候，不知道大家是否留意過CPU的一個參數：N級快取（N一般有1/2/3）
什麼是CPU快取
簡單地剖析結構，大概會是這個關係：
CPU暫存器 <————> CPU快取 <————> 記憶體
可以看到CPU快取是介於記憶體和CPU暫存器之間的一個存儲區域。
CPU快取地存儲空間比記憶體小，比暫存器大。
為什麼需要CPU快取
CPU的運行頻率太快了，而CPU訪問記憶體的速度很慢，這樣在處理器時鐘周期內，CPU常常需要等待暫存器讀取記憶體，浪費時間。
而CPU訪問CPU快取則速度快很多。為了緩解CPU和記憶體之間速度的不匹配問題，CPU快取則預先存儲好潛在可能會訪問的記憶體數據。
CPU快取預先存的是什麼
時間局部性：如果某個數據被訪問，那麼在不久的將來它很可能再次被訪問。
空間局部性：如果某個數據被訪問，那麼與它相鄰的數據很快也能被訪問。
CPU多級快取根據這兩個特點，一般存儲的是被訪問過的數據和被訪問數據的相鄰數據。
CPU快取命中/未命中
CPU把待處理的數據或已處理的數據存入快取指定的地址中，如果即將要處理的數據已經存在此地址了，就叫作CPU快取命中，這會比直接訪問記憶體要快的多。
如果CPU快取未命中，就轉到記憶體地址訪問，也就是直接訪問記憶體。
提高CPU快取命中率
要儘可能提高CPU快取命中率，關鍵就是要盡量讓使用的數據連續在一起。
由於面向數據編程技巧很多，本文篇幅有限，只介紹部分。
使用連續數組存儲要批處理的對象
傳統的組件模式，往往讓遊戲對象持有一個或多個組件的引用數據（指針數據）。
（一個典型的遊戲對象類，包含了2種組件的指針）
class GameObject { //....GameObject的屬性 Component1* m_component1; Component2* m_component2; };下面一幅圖顯示了這種傳統模式的結構：
遊戲對象/組件往往是批處理操作較多（每幀更新/渲染/或其他操作）的對象。
這個傳統結構相應的每幀更新程式碼：
GameObject g[MAX_GAMEOBJECT_NUM]; for(int i = 0; i < GameObjectsNum; ++i) { g[i].update(); if(g[i].componet1 != nullptr)g[i].componet1->update(); if(g[i].componet2 != nullptr)g[i].componet2->update(); }而根據圖中可以看到，這種指來指去的結構對CPU快取極其不友好：為了訪問組件總是跳轉到不相鄰的記憶體。
倘若遊戲對象和組件的更新順序不影響遊戲邏輯，則一個可行的辦法是將他們都以連續數組形式存在。
注意是對象數組，而不是指針數組。如果是指針數組的話，這對CPU快取命中沒有意義（因為要通過指針跳轉到不相鄰的記憶體）。
GameObject g[MAX_GAMEOBJECT_NUM]; Component1 a[MAX_COMPONENT_NUM]; Component2 b[MAX_COMPONENT_NUM]; //連續數組存儲能讓下面的批處理中CPU快取命中率較高 for (int i = 0; i < GameObjectsNum; ++i) { g[i].update(); } for (int i = 0; i < Componet1Num; ++i) { a[i].update(); } for (int i = 0; i < Componet2Num; ++i) { b[i].update(); } 避免無效數據夾雜在連續記憶體區域
這是一個簡單的粒子系統：
const int MAX_PARTICLE_NUM = 3000; //粒子類 class Particle { private: bool active; Vec3 position; Vec3 velocity; //....其它粒子所需方法 }; Particle particles[MAX_PARTICLE_NUM]; int particleNum; 它使用了典型的lazy策略，當要刪除一個粒子時，只需改變active標記，無需移動記憶體。
然後利用標記判斷，每幀更新的時候可以略過刪除掉的粒子。
當需要創建新粒子時，只需要找到第一個被刪除掉的粒子，更改其屬性即可。
for (int i = 0; i < particleNum; ++i) { if (particles[i].isActive()) { particles[i].update(); } }表面上看這很科學，實際上這樣做CPU快取命中率不高：每次批處理CPU快取都載入過很多不會用到的粒子數據（標記被刪除的粒子）。
一個可行的方法是：當要刪除粒子時，將隊列尾的粒子記憶體複製到該粒子的位置，並記錄減少後的粒子數量。
移動記憶體（複製記憶體）操作是程式設計師最不想看到的，但是實際執行批處理帶來的速度提升相比刪除的開銷多的非常多，除非你移動的記憶體對象大小實在大到令人髮指
particles[i] = particles[particleNum]; particleNum--;這樣我們就可以保證在這個粒子批量更新操作中，CPU快取總是能以高命中率擊中。
for (int i = 0; i < particleNum; ++i) { particles[i].update(); }冷數據/熱數據分割
有人可能認為這樣能最大程度利用CPU快取：把一個對象所有要用的數據（包括組件數據）都塞進一個類里，而沒有任何用指針或引用的形式間接存儲數據。
實際上這個想法是錯誤的，我們不能忽視一個問題：CPU快取的存儲空間是有限的
於是我們希望CPU快取存儲的是經常使用的數據，而不是那些少用的數據。這就引入了冷數據/熱數據分割的概念了。
熱數據：經常要操作使用的數據，我們一般可以直接作為可直接訪問的成員變數。
冷數據：比較少用的數據，我們一般以引用/指針來間接訪問（即存儲的是指針或者引用）。
一個栗子：對於人類來說，生命值位置速度都是經常需要操作的變數，是熱數據。
而掉落物對象只有人類死亡的時候才需要用到，所以是冷數據；
class Human { private: float health; float power; Vec3 position; Vec3 velocity; LootDrop* drop; //.... }; class LootDrop{ Item[2] itemsToDrop; float chance; //.... };頻繁調用的函數儘可能不要做成虛函數
C++的虛函數機制，簡單來說是兩次地址跳轉的函數調用，這對CPU快取十分不友好，往往命中失敗。
實際上虛函數可以優雅解決很多面向對象的問題，然而在遊戲程式如果有很多虛函數都要頻繁調用（例如每幀調用），很容易引發性能問題。
解決方法是，把這些頻繁調用的虛函數儘可能去除virtual特性（即做成普通成員函數），並避免調用基類對象的成員函數，代價是這樣一改得改很多與之牽連程式碼。
所以最好一開始設計程式時，需要先想好哪些最好不要寫成virtual函數。
這實際上就是在優雅與性能之間尋求一個平衡。
重新認識C++ STL容器
STL容器，特別是set,map，有著很多O(logN)的操作速度，但並不意味著是最佳選擇，因為這種複雜度表示往往隱藏了常數很大的事實。
例如說，集合的主流實現是基於紅黑樹，基於節點存儲的，而每次插入/刪除節點都意味著調用一次系統分配記憶體/釋放記憶體函數。這相比vector等矢量容器所有操作僅一次系統分配記憶體（理想情況來說），實際上就慢了不少。
此外，矢量容器對CPU快取更加友好，遍歷該種容器容易命中快取，而節點式容器則相對容易命中失敗。
綜合上述，如果要選擇一個最適合的容器，那麼不要過度信賴時間複雜度，除非你十分徹底的了解STL容器，或對各容器進行多次效率測試。
更多小細節（不常用）
面向數據編程還有更多小細節，但是這些都不常用，就只作為一種思考面向數據編程的另類角度。
對二維數組int a[100][100]的遍歷：
for(int x=0;x<100;++x) for(int y=0;y<100;++y) a[x][y]; //do somethingfor(int y=0;y<100;++y) for(int x=0;x<100;++x) a[x][y]; //do something內循環應該是對x遞增還是對y遞增比較快？答案是：對y遞增比較快。
因為對 y 的遞增，結果是一個int大小的跳轉，也就是說容易訪問到相鄰的記憶體，即容易擊中CPU快取。
而對 x 的遞增，結果是100個int大小的跳轉，不容易擊中CPU。
而內循環如果是y的話，那麼就能內外循環總共遞增100*100次y。
但內循環如果是x的話，那麼就內外循環總共只能遞增100次y，相比上者，CPU擊中比較少。
總結
對面向對象和面向數據的看法：
先說結論：應該兼有。
因為遊戲程式是一個既需要高性能又複雜的工程。
使用面向對象的遊戲程式新手，常常就有一個問題：過度設計/過度抽象，什麼都想用設計模式封裝一下抽象一下。
這就很容易導致一些過度設計/過度抽象導致遊戲性能太差。
部落客現在的項目風格都比較偏向面向數據思想，盡量減少虛函數的使用，多利用數據組合成對象，而不是重寫各種基類虛函數。
對於一些數據結構的考量，也盡量偏多使用連續存儲的結構（例如數組）。
如何兼有兩種思想，這種玄學的問題可能得靠自己去感悟，多嘗試和測試性能差別。
參考
《Game Engine Architecture》 2014-1 作者: Jason Gregory
使用英特爾® ISPC 簡化SIMD開發 | 英特爾® 軟體
WebAssembly and SIMD – Wasmer – Medium
遊戲設計模式——面向數據編程（舊） – KillerAery – 部落格園
遊戲設計模式系列-其他文章：
https://www.cnblogs.com/KillerAery/category/1307176.html
本文使用markdown」重置「以前寫的面向數據編程文章，順便添加和修改了一些內容。吐槽一下，部落格園的博文發出去指定tinymce後就不能再修改成md類型了。
