[DOD Series][CppCon14] Data-Oriented Design and C++

github.com

Mike是insomnia的主程，這是我看過最nb的演講之一，這個PPT甩PPT架構師們不知道幾條街，而且是CppCon這種級別的會議，真是飛上天了。。。

像大多數遊戲一樣，關閉Exceptioins，不推薦使用Templates，在debug時使用std

不使用STL，因為之前template和編譯時間的考量，另外specific的structures對於遊戲特定的問題更加有效。不用allocates，自己接管所有的內存分配。一堆debug tools。

他們做的相當徹底，一般沒有點技術積累的工作室可不敢這麼做，碰的釘子比可預計的性能提升還要可怕。

嗯，深信不疑

本質上所有的問題都是數據的問題

所以在不同的數據上面臨的問題也不同

硬體才是解決問題的關鍵

數據才是主要的變化，延遲和吞吐量是不會變的

不好翻譯，自己看視頻吧

所以OOD只是一種編程時的提醒，來警惕C++常用的編程思想

3大謊言

1. 軟體平台

明顯硬體才是平台

不同的硬體，解決方法完全不同

單片機6502，x86，arm，cell等等

對於high performance coding來說，不要抽象、提到理論層面來解決問題，要直面現實的問題

2. 用真實的世界模型給代碼建模，就像OOP提倡的那樣

使用世界模型建模，毫無疑問會隱藏底層數據

OOP對於maintenance來說挺好，從數據層面來看，它可以有效的管理data access的變化（抽象出了物體與介面）；但是另一方面，屏蔽了真正底層data屬性（什麼樣，有多大等）的理解，這對於解決問題至關重要。

建模暗示了數據之間的關係或者變化

但現實中，『class』本質上都一樣

但是從數據的角度來看，『class』只是表面上相似

對於physics/static/breakableChair，從數據的觀點來看實際上它們都不一樣，它們如何被處理，怎麼管理，數據如何變化，就因為模擬了世界的模型，所以把它們歸類到了一起。

對世界建模造就了一坨臃腫的、毫無聯繫的數據結構和變化。

建模試圖去抽象一個理想化問題，但是事實上越抽象越複雜。。。

OOP建模像一本5天精通C++的書一樣，告訴你一些故事，讓你去模仿。。。不好意思，沒有銀彈。

3. 代碼比數據重要，讓我們花大量時間來設計/優化代碼，而不是去考慮數據

代碼的本質就是操作數據

編程的本質是解決問題，而不是代碼秀

只寫有意義的代碼，做有意義的data transform

對於每個specific的問題，去理解specific的數據，然後想specific的解決方案

沒有永不過時的解決方案，不會一勞永逸，別指望著抽象總結問題

這3大謊言造成了一堆問題

理解數據解決問題需要熟悉當前平台的底層，所以nm優化是最難做的（其他相比起來簡直跟玩似的）

來例子了

字典

從代碼角度考慮，key<->value成雙成對

但實際上從數據層面看，它們並沒有關聯關係。當查找key時，不需要value的值，它只是1hit，大部分情況我們不需要value

字典的規模越大，情況越糟

Load value會浪費帶寬，cache等

Key和value最好分開存儲

對於keys，cache load大部分全是需要的

Value cache大部分是cold，但是value的access很少

先處理最常用的case

編譯器不能做嗎

Review

CPU指令的延遲cycle

隨著cpu的計算性能爆髮式增長，memory的增長一直很緩慢

Mem與cache的區別大概有100x

動畫來演示一下

L2 Cache miss是最明顯拖慢程序的地方

Shared memory mode考慮GPU<->CPU之間的內存管理

考慮一個例子，gameobject是一個monolithic的實現，有一堆屬性和方法，典型的OOP抽象。

UpdateFoo的彙編

Velocity 2個float的fetch，mem->cpu，~200cycles

FPU計算~10cycles

Sqrt ~30cycles

形參在L1中，~3cycles

M_Foo和velocity不在一個cacheline（64B）中（184-12=172B），所以L2 cache miss，~200cycles

L2 cache miss和實際的運算時間 ~10:1，而這1/11才是compiler最大能優化的時間。大部分情況下，compiler的優化空間在1-10%左右，其他大部分是compiler無能為力的。

Compiler不是魔法棒，沒法解決最顯著的問題

我們需要幫助compiler解決問題

通過粗略的計算能提升一大截性能

Cache中浪費了56B（cacheline 64B，2個float 8B）

浪費了60B

浪費了90%的cache

只用了10%的空間

從data上考慮的話，為了用滿cache，只建立Input和Output的structures，UpdateFoos函數用來處理所有的input和output，這種構建數據的方式即使用AOS（Array of Structures）來代替SOA（Structures of Array）

5個Input 60B，5個output 20B

如果是32個，那麼正好都是cacheline的整數倍，這樣整個cache totally full

~5.33個loop會用到一個cacheline，每個loop的FPU

好處：1）code更容易維護；2）code更容易debug；3）可以更簡單的解釋性能消耗。

Bool的有效信息位很少，依然佔用1B，對於Foo.ojbectWorld來說，需要2個cacheline才能讀取到

來看看compiler怎麼優化

MSVC O2

基本上沒優化，是因為考慮了aliasing rules？needParentUpdate會改變？

Clang做的不錯

試試稍微複雜一些的

嗯，至少它inline了。。。

MSVC還是老樣子

獲得結果之後，不需要重新在讀成員變數或者調用函數

Got it

MSVC…

嗯。。。

VC總算懂了

所以教訓是，對於所有member都這麼搞一搞

*我真的懷疑compiler其實是考慮了多線程，當然這還是需要end user去告訴他，restrict指針同理，所以多給變數加約束還是有不少優化上的好處的

一個簡單的update操作，來處理每幀生成物體的邏輯

那麼is_spawn的信息密度是多少

列印出來

把結果zip壓縮，10000 frames 915B，平均一幀0.732b。當然這是個粗略的有效信息的估計，精確的要根據香農熵自己算。

實際情況是，假設大約2個L2 cache miss（128B） per frame，10000幀就是1280000B

浪費的信息99.9%

其他的替代方案？

對於每幀的處理，a）每512次（8個cacheline）做一次邏輯判斷，b）pack bool 1bit with other data you must read

對於跨幀處理，可以pack幾幀的信息到command buffer，一起集中處理

開始噴別人了。。。

為什麼受傷的總是你。。。

5倍性能提升。。。

成員變數太多，造成cacheline/memory的浪費，引發cachemiss

很多bool暗示了有很多last-minute decision

Node這個名字就表示了這個class太籠統了，node就是我們根據OOP經驗建模出來的，每個node的產生和銷毀就如同實際世界中的一樣，一大堆數據跟著構造/析構，實際上大多數情況node在引擎中是作為骨骼傳遞的一種數據hierarchy，我們只用關心骨骼的數據是如何變化的即可。一堆的構造暗示了read就是unmanaged，因為沒有區分成員變數何時、如何read；沒必要的析構的讀寫；unmanaged instruction cache，因為籠統的node類，加上其派生的一系列類，多態的濫用等等造成的；複雜的狀態機模型，因為bool的濫用，7個bool就是2^7個狀態。根據狀態的不同來管理數據，這樣就根本不需要狀態的值。

Generate a name… 暗示了更多的read，因為你總是假裝不知道他是啥。最好的代碼就是不用寫的代碼，所以最好做法就是offline/once去生成這些信息，比如預編譯等等。

計算太多，對於構造函數不需要再調用如此重量級的計算，所有的初始化數據我們應該提前就全部了解，即使它很複雜也可以用tools來計算，比如預乘好的matrix等等。

優化

Last-minute decision

1. 重新組織每個方法；2.對於每種做法單獨分析

3.進行優化

每個loop需要2個cacheline（node->pos, m_Orient）

把它們pack到一起，一個cacheline能放下2.28個loop數據

四元數重載了乘法，這樣就能比較底層的分析了

對於worldTranslate重新組織防止last-minute decision，是不是root，根據context caller可以分辨

這兒數據太多，不太好分析cost

Pack所有計算的data，然後iteration所有的數據

問題變得更簡單去分析

把data的問題處理好了，compiler也會變得更聰明

維護，debug，並發更簡單

瞎說什麼大實話

1. 硬體是平台

2. 根據數據來設計，而不是理想的世界

3. 主要職責是操作數據，而不是設計代碼

好處是有很多工具可以幫助我們分析問題

先入為主的理念認為忽略真正的問題是好事

設計模式填鴨式地灌輸給無法獨立思考的無腦程序員，他們用設計模式指導編寫中庸的代碼來解決問題。夠腹黑。。。

Q&A 1）如果不用template，那麼代碼的復用如何：template不是唯一的解決方法，還有其他很多工具能幫忙生成代碼 2）硬體太多，如何了解每種：不可能了解每個的詳細參數，但是大概能知道common case，range等 3）有沒有工具幫我們分析：有很多熱點、miss rate分析工具等，但是本身cacheline這種問題就很簡單看代碼就行

真挺佩服他在C++的會議上講這些的，一堆C++ ISO的人估計都吐血了，辛辛苦苦出新標準做優化為了什麼！

更新一下，看評論貌似大家陷入一個誤區：DOD慢工出細活，開發效率太低，coding的時候想著怎麼優化數據能寫個毛線速度。。。

DOD和寫代碼快慢應該是沒有任何關係的，一開始不是太熟悉的時候可能寫的時候考慮會多一些，但是深入理解和實踐之後編碼瓶頸應該還是在個人能力上，就像是OOP一樣，它只是一種代碼思維，不熟悉面向對象的人一開始寫封裝繼承多態等也會亦步亦趨。

可能在協作上不如OOP封裝那樣適合大團隊開發，其實這也是一個雙刃劍。如果團隊的人都培訓或者熟知OOD，那麼整個工程反而更容易maintain/debug/upgrade，因為OOD特別好reason。這個還是主要看specific項目，如果time-critical的項目->spacecraft等，OOD明顯要高於其他優先順序；如果是Office這種code-base動輒幾百G、人員幾百數量級以上項目的話，可能封裝的意義更大一些。