目錄
面向資料程式設計是什麼？
CPU緩存（CPU cache）
什麼是CPU緩存
為什麼需要CPU緩存
CPU緩存預先存的是什麼
CPU緩存命中/未命中
提高CPU緩存命中率
使用連續數組存儲要批處理的對象
避免無效資料夾雜在連續記憶體區域
冷資料/熱資料分割
頻繁調用的函數盡可能不要做成虛函數
重新認識C++ STL容器
更多小細節（不常用）
單指令流多資料流（SIMD）
什麼是SIMD
為什麼需要SIMD
支援SIMD技術的指令集
使用SIMD程式設計
使用彙編内聯
使用指令集庫
使用ISPC語言
并行循環
避免Gather行為
總結
參考
随着軟體需求的日益複雜發展，遠古時期面的向過程程式設計思想才漸漸萌生了面向對象程式設計思想。當人們發現面向對象在應對高層軟體的種種好處時，越來越沉醉于面向對象，熱衷于研究如何更加優雅地抽象出對象。然而現代開發中漸漸發現面向對象程式設計層層抽象造成臃腫，導緻運作效率降低，而這是性能要求高的遊戲程式設計領域不想看到的。
GDC2017上的演講 Overwatch Gameplay Architecture and Netcode 講述了《守望先鋒》所使用的 ECS 架構，這個架構實際上就是基于面向資料程式設計的思想。
之後，面向資料程式設計的思想越來越被接受，已經是現代遊戲程式設計中不可或缺的一部分，ECS架構也成了遊戲業界裡Gameplay架構的一個典中典。
例如 Unity 2018 也跟着推出了 ECS 架構的 preview版本（也有插件所支援的 Entitas 架構），盡管目前仍不完善。
先來一個簡單的比較：
面向過程：建立解決問題所需的各個步驟（函數）。
面向對象：建立解決問題所需的各個模型（類）。
面向資料：優先考慮資料的存取及布局（資料）。
也就是說，面向過程和面向對象都是解決問題的一種方法，而面向資料隻是一種優化的設計思想，而非解決問題的方法。
那麼所謂的考慮資料存取/布局是什麼意思呢？
這裡引入幾個有關處理資料的概念：
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緩存命中率，關鍵就是要盡量讓使用的資料連續在一起。
由于面向資料程式設計技巧很多，本文篇幅有限，隻介紹部分。
傳統的元件模式，往往讓遊戲對象持有一個或多個元件的引用資料（指針資料）。
（一個典型的遊戲對象類，包含了2種元件的指針）
下面一幅圖顯示了這種傳統模式的結構：
遊戲對象/元件往往是批處理操作較多（每幀更新/渲染/或其他操作）的對象。
這個傳統結構相應的每幀更新代碼：
而根據圖中可以看到，這種指來指去的結構對CPU緩存極其不友好：為了通路元件總是跳轉到不相鄰的記憶體。
倘若遊戲對象群組件的更新順序不影響遊戲邏輯，則一個可行的辦法是将他們都以連續數組形式存在。
注意是對象數組，而不是指針數組。如果是指針數組的話，這對CPU緩存命中沒有意義（因為要通過指針跳轉到不相鄰的記憶體）。
這是一個簡單的粒子系統：
它使用了典型的lazy政策，當要删除一個粒子時，隻需改變active标記，無需移動記憶體。
然後利用标記判斷，每幀更新的時候可以略過删除掉的粒子。
當需要建立新粒子時，隻需要找到第一個被删除掉的粒子，更改其屬性即可。
表面上看這很科學，實際上這樣做CPU緩存命中率不高：每次批處理CPU緩存都加載過很多不會用到的粒子資料（标記被删除的粒子）。
一個可行的方法是：當要删除粒子時，将隊列尾的粒子記憶體複制到該粒子的位置，并記錄減少後的粒子數量。
移動記憶體（複制記憶體）操作是程式員最不想看到的，但是實際執行批處理帶來的速度提升相比删除的開銷多的非常多，除非你移動的記憶體對象大小實在大到令人發指
這樣我們就可以保證在這個粒子批量更新操作中，CPU緩存總是能以高命中率命中。
有人可能認為這樣能最大程度利用CPU緩存：把一個對象所有要用的資料（包括元件資料）都塞進一個類裡，而沒有任何用指針或引用的形式間接存儲資料。
實際上這個想法是錯誤的，我們不能忽視一個問題：CPU緩存的存儲空間是有限的
于是我們希望CPU緩存存儲的是經常使用的資料，而不是那些少用的資料。這就引入了冷資料/熱資料分割的概念了。
熱資料：經常要操作使用的資料，我們一般可以直接作為可直接通路的成員變量。
冷資料：比較少用的資料，我們一般以引用/指針來間接通路（即存儲的是指針或者引用）。
一個栗子：對于人類來說，生命值位置速度都是經常需要操作的變量，是熱資料。
而掉落物對象隻有人類死亡的時候才需要用到，是以是冷資料；
C++的虛函數機制，簡單來說是兩次位址跳轉的函數調用，這對CPU緩存十分不友好，往往命中失敗。實際上虛函數可以優雅解決很多面向對象的問題，然而在遊戲程式如果有很多虛函數都要頻繁調用（例如每幀調用），很容易引發性能問題。
解決方法是，把這些頻繁調用的虛函數盡可能去除virtual特性（即做成普通成員函數），并避免調用基類對象的成員函數，代價是這樣一改得改很多與之牽連代碼。是以最好一開始設計程式時，需要先想好哪些最好不要寫成virtual函數。
這實際上就是在優雅與性能之間尋求一個平衡。
STL容器，特别是set,map，有着很多O(logN)的操作速度，但并不意味着是最佳選擇，因為這種複雜度表示往往隐藏了常數很大的事實。
例如說，集合的主流實作是基于紅黑樹，基于節點存儲的，而每次插入/删除節點都意味着調用一次系統配置設定記憶體/釋放記憶體函數。這相比vector等矢量容器所有操作僅一次系統配置設定記憶體（理想情況來說），實際上就慢了不少。
此外，矢量容器對CPU緩存更加友好，周遊該種容器容易命中緩存，而節點式容器則相對容易命中失敗。
綜合上述，如果要選擇一個最适合的容器，那麼不要過度信賴時間複雜度，除非你十分徹底的了解STL容器，或對各容器進行多次效率測試。
對二維數組int a[100][100]的周遊：
内循環應該是對x遞增還是對y遞增比較快？答案是：對y遞增比較快。
因為對 y 的遞增，結果是一個int大小的跳轉，也就是說容易通路到相鄰的記憶體，即容易命中CPU Cache。
而對 x 的遞增，結果是100個int大小的跳轉，不容易命中CPU Cache。
而内循環如果是y的話，那麼就能内外循環總共遞增100*100次y。
但内循環如果是x的話，那麼就内外循環總共隻能遞增100次y，相比上者，CPU Cache命中比較少。
SIMD全稱Single Instruction Multiple Data，單指令流多資料流，是一種采用一個控制器來控制多個處理器，同時對若幹個資料分别執行相同的操作進而實作空間上的并行性的技術。
簡單來說，SIMD技術可以讓CPU在一個指令周期執行多個資料的操作（不過操作需要一樣），而不是一個指令周期執行一個資料的操作。
在上面的介紹裡，我們可以直覺的知道最大的好處在于：可以允許CPU利用并行性快速處理多個資料。
但是局限性還是有的，SIMD技術一般對矢量算術型操作（例如矢量相加，矢量相乘）支援的很好，而不支援其他類型操作（例如分支判斷和跳轉）。
是以SIMD技術常用于CPU資料計算密集型應用，例如：
人工智能
實體計算
粒子系統
光線追蹤
圖像處理
X86架構的CPU所支援SSE/SSE2/SSE3指令集就是典型的重點針對/支援SIMD功能的指令集。
目前的PC的CPU架構絕大多數都是Intel的X86架構，而ARM架構的CPU可以在很多消費性電子産品上看到，從可攜式裝置（PDA、行動電話、多媒體播放器、掌上型電子遊戲，和計算機）到電腦外設（硬碟、桌上型路由器）甚至在飛彈的彈載計算機等軍用設施中都有它的存在。
(vs2019裡項目設定可以找到指令集設定選項)
我們可以在IDE/編譯器裡設定好支援SIMD技術的指令集選項。
缺陷：
彙編代碼需根據不同平台定制（無跨平台特性）
彙編代碼複雜，開發效率低
代碼需根據不同平台指令集，包含不同指令集庫頭檔案（無跨平台特性）
ISPC是英特爾推出的面向CPU的着色器語言，它适用多種指令集的矢量指令（如SSE2、SSE4、AVX、AVX2等）。
ISPC是基于C語言的，是以它大部分文法和C語言是一緻的，可以減少學習成本。
ISPC源代碼，經過編譯後輸出.obj檔案和.h檔案。這樣我們在編寫C/C++程式時可以包含該頭檔案以使用ISPC代碼。
下面簡單提供個代碼示例比較：
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++循環代碼，這樣就是一般的分量操作，如下圖左側：
在ISPC文法裡，隻需簡單的寫上 foreach(i = 0 ... N) ，IPSC編譯器編譯時會為其編譯成圖中右側的行為，即一次循環并行處理M個元素，實際循環N/M次。
更友善的是，ISPC會自動處理并行循環的邊界情況（例如每次并行處理4個元素時，N/4次循環後餘出1~3個元素）。
這是一個正常的顔色結構，文中定義了若幹個顔色對象。
SIMD技術讀取變量一般都是連續若幹個（在圖中為4個）變量一次性讀取，這種行為叫做矢量讀取。
而由于上文的顔色結構定義，其記憶體分布則如圖中的上部分。
要對4個紅色分量進行操作時，則需要進行多次讀取，這被稱為Gather行為。
倘若我們使用如下結構定義，則記憶體分布會如圖中下部分。這樣就能一次讀入4個紅色分量，高效地利用SIMD技術。這種結構被稱為SIMD友好型結構。
而在ISPC語言裡，使用varying類型可以友善的定義SIMD友好型結構。
對面向對象和面向資料的看法：應該兼有。
因為遊戲程式是一個既需要高性能又複雜的工程。使用面向對象的遊戲程式新手，常常就有一個問題：過度設計/過度抽象，什麼都想用設計模式封裝一下抽象一下。這就很容易導緻一些過度設計/過度抽象導緻遊戲性能太差。
部落客現在的項目風格都比較偏向面向資料思想，盡量減少虛函數的使用，多利用資料組合成對象，而不是重寫各種基類虛函數。對于一些資料結構的考量，也盡量偏多使用連續存儲的結構（例如數組）。如何兼有兩種思想，這種玄學的問題可能得靠自己去感悟，多嘗試和測試性能差别。
[1] 《Game Engine Architecture》 by Jason Gregory
[2] 【GDC2017】Overwatch Gameplay Architecture and Netcode
[3] 使用英特爾® ISPC 簡化SIMD開發 | 英特爾® 軟體
[4] WebAssembly and SIMD - Wasmer - Medium
遊戲設計模式系列-其他文章： https://www.cnblogs.com/KillerAery/category/1307176.html
作者：KillerAery
出處：http://www.cnblogs.com/KillerAery/
本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。