[GDC15]Parallelizing the Naughty Dog Engine using Fibers

gdcvault.com

Christian Gyrling頑皮狗的主程，在神海1的時候加入ND，至2015年已經8年半了

本次主要講從PS3到PS4升級過程中架構的改變，主要是Last of Us Remastered，以及fibers如何利用多核CPU100%的計算能力

PS3時期，Engine的主線程主要是game logic + commad buffer的設置，SPU用作worker thread，大部分的引擎系統模塊運行在spu上，少部分gameplay的代碼才能在SPU上運行

PS3的job system有很多問題：沒法在運行到一半時yield，必須把整個job執行完畢；User必須自己管理job內存的分配以及釋放；job的狀態模糊不清，submit之後可能會被立即執行也有可能等待一會才能運行；job之間的同步依賴marker index，整個array沒法reuse，滿了必須整個clear引發stall。

新的job system的設計目標：1）可以jobify任何代碼； 2）job可以中途yield，比如玩家需要等待碰撞檢測ray-cast的結果，在一個很深的callstack中yeild給其他任務進行等待； 3）簡單的API使用； 4）不需要user管理job的內存； 5）簡單的同步/連接job的方法； 6）API的簡單實用第一考慮，第二考慮性能

Fiber可以認為是一部分的thread，用戶提供給它stack空間，當sleep時用來保存context部分register的空間，還有一些保存priority以及affinity信息，fiber只是一種數據結構，並不包含調度器（scheduler）的設計。Thread回來執行它，簡單的你可以認為只要每次切換stack pointer（esp/ebp）、以及program pointer（eip）和通用寄存器（gprs）。Fiber之間不是搶佔式的時間片分配，每次切換必須主動的調用yield（對於PS4是sceFiberSwitch）。開銷很小，不需要線程之間的context switch，只需要切換必要的register。

6個woker線程鎖定在6個CPU cores上（很遺憾windows並不能這樣，即使設置affinity只會讓線程性能更慢，除非特殊使用否則別指望你比windows更了解如何輪轉時間片…所以windows上會帶來不可控的額外開銷，thread的cs超級耗而且即使ready也不能馬上獲得time slice），thread作為執行單元載體，fiber是其執行內容的context，job始終在fiber中執行，作為一個函數指針入口，fiber提供stack等context，唯一的同步方式就是原子計數，他們使用了160個fibers（128個64kb stack，32個512kb stack，我只能說你們太省了…），意味著可以同時有160個沒有執行完成的jobs（包括yield的），線程同步和競爭時沒有太多複雜的技術，只是簡單的使用3個全局job queues（Low/Normal/High prio），沒有job stealing。

圖示一下

開始執行

Fiber從job queue中pull一個job

在執行的任意時間都可以添加新的jobs，push到job queue的尾部

當運行時發現需要等待某些資源counter時，立即把fiber移到wait list中，並且關聯到counter上，例子中黃色的job想讓counter變為0，我們把context做一個snapshot保存起來。

為了啟動一個新job，我們從fiber

Fiber取下一個藍色的job

在這個例子中，當藍色的任務完成它會decrease關聯的counter，藍色的job就是黃色job的依賴項，counter減到0，黃色的job可以繼續運行了。

Worker線程意識到可以繼續之前job，它將fiber歸還到fiber pool中

然後switch到就緒的fiber上繼續運行。

Job system的細節：worker線程鎖定對應的core，為了避免cs以及core switch，每次遷移一個thread會引發連鎖反應，所有正在運行的線程全部進行遷移；WaitForCounter，當wait的時候，會把當前fiber放到wait list中，job會sleep，code沒有察覺自己已經被置換出去了；在The Last of Us：Remastered中，每幀大概800-1000個jobs。

所以engine中所有的一切都是job，沒有了主線程的概念，只有一個超小的job用來生成所有的初始狀態並且繼續以後的每幀邏輯渲染；只有一個例外：IO線程（socket，file，system calls…），所有需要單一實例的操作，它們的實現和interrupt handler差不多，大部分時間在sleep等待，一旦有任務便執行，比如讀取數據到global space，然後kick新的處理數據的jobs，再次進入sleep。

Ingame profiler

舉個animation的例子：原來的代碼相當簡單

Job化：在stack上創建jobs，user可以自己管理其生命周期（注意這是job的life scope）

把入口函數地址和相關參數填充到job中

創建完job之後，可以RunJobs，並且指定你需要等待的counter

等待counter變為0，當前的job會進行sleep

這個例子kick出大量的jobs，然後自己進入wait list

派發出100個small jobs並行執行，自己在sleep

每個small job完成時會對counter-1s，等counter變為0時，它會從wait list喚醒並繼續執行

好處：非常簡單來job化遊戲邏輯；對於同步等待非常直觀，不需要信號量或者各種barriers，只需要waitforcounter；切換fiber代價超輕。

壞處：不能使用系統的同步原語，因為他們是綁定在特定的線程上的，一旦進入臨界區，fiber進行sleep，等它wakeup的時候很有可能遷移到了另外的線程，那麼mutex永遠不會被free，相當於死鎖；同步需要使用硬體級的鎖，原子spin lock可以使用，但是如果需要鎖比較長的時間，會使用特殊mutex。

Debugger支持fibers（ExceptionFilter好像不支持。。。）；fiber可以命名；Fiber的callstack可以像線程一樣dump。

TLS是個問題，切換Fiber但是TLS依然綁定在原thread上，MSVC compiler有fiber-safe tls優化，但是clang不支持，應急解決方法是利用cpp分割tls，使得互相不可見；因為有io線程所以會有這樣的問題，interrupt的線程會搶佔core，而且很有可能之前的thread在holding一個mutex，如果它kick一個job，需要acquire mutex，但是這個mutex永遠不會被之前的thread釋放從而造成死鎖。解決的方法是先嘗試之前的spin lock，如果不行則fallback到系統的mutex，因為系統的mutex具有priority inversion的特性可以解決死鎖。

其他的job systems比如TBB，它能解決依賴關係但是如果不用cs沒法在中途切換job，否則可以使用job nesting（但是這會造成job stack過於深，佔用內存不說，它還需要從棧頂依次順序恢復job）；fiber都不存在這些問題。

繼續

如果在綠色區域就結束了一幀，大概可以跑60fps

在藍色區域結束，可以有30fps

在紅色線程結束，跑不到30fps（11fps…）

一開始132ms，因為ps4使用了新的rendering

Job化所有的代碼，55ms

根據dataflow減少locks，36ms

離ship只有3個月了

拉上人花了幾周做優化，25ms

嚴峻的意識到，所有的系統已經job化了；GPU優化的很好；CPU bound；依然cpu有不少空閑；只有2個月ship了。（看來大家都一樣啊，死到臨頭才知道亡羊補牢，不過明顯人家有這個金剛鑽的技術…）

有很多中等/小型的cpu時間片沒有利用到

每幀先運行game logic，然後rendering logic

整個一幀的工作大概100ms，分配在6cores上大概16.66ms。所以理論上可以60fps。

一砍兩半

邏輯和渲染分離

上幀的rendering和本幀的logic一起運行

每個階段都是完全獨立的；可以立即處理下個階段；更少的lock，只在一個階段內部使用同步。

舊的設計

Ship兩周前搞定（架構也是好到一定程度才能這麼搞，邏輯渲染分離哪有這麼好做的…）

PS3的內存管理：線性內存管理，跨幀就蛋疼了

跨幀時，內存的釋放、分配都是問題，非常棘手而且處處是坑。

到底什麼是幀

ND認為幀是一段數據（還是DOD的思維），不是時間的長度

FrameParameters：用來完成整個顯示過程的數據，在每個stage之間傳遞；包含frame state；每個stage獲取數據的入口。

不需要加鎖；每幀都會拷貝數據；保存每個stage的開始/結束時間。

簡單的測試是否結束一個stage的方法；簡單的內存生命周期跟蹤；保存最近16的FrameParams數據reuse。

整個就是數據流

根據生命周期和stage transfer的不同，大概有10中不同的allocator。

很容易OOM，100-200MB的浪費。

引入Tagged Heap：Block allocator大小2MB，這是PS4上1個TLB查找最大的頁表大小；每個block有一個uint64的tag；沒有Free介面；因為只能通過tag來free。

Allocator有2MB的block tagged Game，用來分配內存申請

當這個block用完了

會向Tagged Heap後端申請一個新的block，tagged Game

那麼當一個特定的stage結束後，我們需要清理它所用的內存，比如Game全清

那麼Heap中的Game都會被清理

所有的Allocator都是用tagged heap，99%的內存申請都是小於2MB的，對於大於2MB的直接分配連續的tagged heap blocks；共用block pool的好處是可以動態的改變allocator的分配大小。

圖示說明

3個fiber需要使用Game tagged block，分配時需要加鎖；stage結束時，只需要統一清理Game tagged heap就可以，簡單迅速。

為了更快一些：對每個thread都保存一份2MB block，沒有線程間競爭，避免加鎖。

每個線程一個Game block

分配時不需要加鎖（灰色的block）

Job sleep後喚醒在其他線程上

之後再申請內存也沒問題（藍色/紅色的block）

而且回收的時候，依然是game tag

總結：Fiber很吊；集中處理Frame設計；Tagged非常利於多幀的GC。

Q&A：1）Input到Display延遲多少：16*3ms； 2）其他平台的Fiber Lib推薦：一開始在Win上實現的Fiber，非常簡單不需要用庫； 3）在VS2012上safe-fiber TLS優化依然有問題，marker的使用還是有問題 4）Cache：ND相比於Cache更急切的想要利用起多核計算性能，所以沒有特別優化（這個提問很好，我覺得還是有很多可以深入挖掘的）；5）每幀會判斷是否還有上一幀的相同stage在運行，來決定是否clear tag heap，特殊情況會lazy clear，隔個2、3幀； 6）stackless fiber：Christian沒大聽懂？ 7）可以改變每個stage的跨度長度，不一定要分logic/render; 8）GPU bound的話，下一個render會等待，因為並發的只有一個stage的instance；如果某一個stage運行過快，不可能讓他把16個Frame都運行掉，會帶來huge input latency，所以最多快3幀。

Naughty Dog的這個分享應該業內盡知吧，技術上我們除了崇拜也不能多說啥評價，反正就我知道的一票引擎開始學習（抄）fiber-job啥啥啥的了，對於ND這種無私的分享精神和這種引領技術的魄力（分享出去也沒啥，我們吊又不只靠這個）真是各種羨慕嫉妒恨。。。