Fiber based job system
Preface
工作上使用unity開發遊戲時，在效能有瓶頸的區塊時常會使用到Job System來提升效能，
去年因為興趣使然稍微研究了Job System的底層實作，在公司內部報告使用過，
藉著最近有點時間將這些資訊整理起來發成部落格文章。
寫完之後回頭來看，必須先提醒一下，這篇會使用到相當多作業系統的背景知識，
建議讀者需要先具備作業系統的基礎再做閱讀。
What is Job System
Job system是一種管理多執行緒(multi-thread)程式的封裝，藉由將執行的程式碼打包成一個個任務，來抽象化執行續本身的使用。
Job System藉由管理一組 worker thread進行跨CPU core的資源使用，通常使用與CPU core數量相同的worker thread數量，來避免頻繁的上下文交換(context switching)所帶來的效能損失。(即使作業系統或其他程序可能會使用到一些核心的資源)
Job System 藉由將 Job 推入一個 Queue (或是priority queue)，將他們依序放入worker thread執行，同時Job System會管理他們之間的依賴關係來確保 Job 依照邏輯順序進行。(像是NPC走到定點後，才開始進行巡邏)
Naive Job System Structure
- Worker threads : 使用std::thread::hardware_concurrency() 獲得CPU核心數，生成對應數量worker thread
- Job queue : 由各個worker thread在空閒時自己抓取，所以需要是thread safe的資料結構
- Counter : 紀錄目前還在進行的job數量，可以使用 std::atomic
Fiber
About Fiber-based Job System
Naughty Dog在GDC 2015的演講是提出這個實作並且推進遊戲使用的非常重要的一篇文章，非常推薦大家閱讀。
What is Fiber?
根據 Microsoft Win32 的 Manaul 所述:
A fiber is a unit of execution that must be manually scheduled by the application.
Fibers run in the context of the threads that schedule them.
Fiber具有以下特性：
- 一個小型的 thread，由使用者提供stack space，並且具有更小的 context，可以將register暫存在stack上
- 由 worker thread 執行
- Cooperative (合作性) 的多執行緒執行，由fiber之間yield做切換，而不主動搶佔
- 極小成本，不會有thread的context switching在fiber切換時發生 (只有register的save/load必然發生)，因為context都還在stack上
同上所述，Fiber 之間的切換是使用yield進行，也就是所謂的cooperative scheduling，Fiber將這個cpu scheudling和context switching(kernel-space)的操作拉到使用者(user-space)進行，並且讓這些操作成為寫程式的基本步驟。
這使得工程師可以在多執行緒的程式設計中取得更多的操縱權。
在各式各樣的語言中都有著類似的東西，更多時候被稱為User-space thread或是green thread(Ruby, Java)。
有些語言也有著coroutine的概念，fiber和coroutine也有相當程度的相似，只不過coroutine通常是語言層級的概念，而fiber通常做為系統層(system-level)的概念存在。
Fiber 的實作
Fiber的實作是在組合語言層級進行，將所需的register存放到對應的stack空間，再藉由jmp跳到其他的上下文執行。
如果沒有瘋到想自己實作，大可使用OS Support的Library來使用
例如：Win32、Unix、boost/context
FTL (fiber-based tasking library)
為了進行實作練習，我找到一個滿完整的fiber job system開源專案進行參考
FTL使用上面提到的boost作為fiber的實作
FTL 的 Fiber 實作
Yield to other task
分成兩個區塊進行，如圖：
第一部分是使用boost/context的api，將context打包成fiber bundle，儲存到stack上，並且將目前的task丟進等待 queue 中
第二部分則是從queue中找尋目前等候執行的task，將他填入目前的TLS (thread local storage)
最後使用fiber api進行user-space的context switch就完成切換
如何使用FTL
- Caller
呼叫Job執行的部分，需要執行底下步驟
- 初始化 job scheduler (in stack)
- 創造task陣列 (也是stack)
- 初始化job的參數
- 將job kick到scheduler中
- 等待atomic counter歸零 (job執行完成)
程式碼如圖：
- Callee
作為Job的function必須符合底下格式：
如圖所示，送入目標的task scehduler以及參數來執行job化的程式碼
簡單的一個例子如下：
這是簡單對數字進行加法的程式，
第一塊是主要邏輯進行的部分，也就是我們要平行化的部分
第二塊是假如後面程式碼需要依賴其他task的結果，可以將目前context暫存，把執行資源yield給其他task執行，
等待依賴的task執行完畢
第三塊則是可以從這個job中開始其他的job的執行。
實作
我使用了FTL進行經典的flocking演算法boid的實作，
2000隻的鳥群，在單核心的執行如下：
使用job system優化後如下：
還有進行一些kick now, gather later，以及double buffering之類的技巧優化
以及將render thread和game logic thread拆開，因為不是這篇主題的重點，就不細講，
有興趣的可以參考實作的Repo：
別忘了幫我留下一顆星星！
Reference
Job concept
Fiber Concept
MS Fiber
Naughty Dog’s Slide
Fiber Tasking lib
Fiber vs Coroutine