淺談多執行緒程式設計與Unity的C# Job System
前陣子把bilibili上的Games104刷完，其中一堂有講到多執行緒與Job system，決定把一些重點記錄下來然後順便介紹一下Unity中可以實作平行處理的C# job system。
多執行緒程式設計(Multithread Programming) - 將我們的程式任務分配到多個thread去執行，來更有效率的利用硬體還並達成加速的效果，
那為何會需要Job System? 像我用的C#本身有提供Thread.Start還有像是TaskFactory.StartNew這類的API可以使用，Job System的multithreading跟我們直接呼叫這些API有哪些差異? 在討論差異之前我們要先了解寫多執行緒程式時的優缺點。
寫多執行緒程式的優勢
- 將Main thread上計算的壓力分擔到其他thread上，解掉CPU Bound。
對遊戲的客戶端來說，Main thread就是專案內所有code都在搶資源的戰場，但最終玩家也會期待main thread可以在16.66毫秒(60fps)內消化完所有的計算。 - 對近代CPU來說，單一核心的clock speed成長已經趨緩，多核心的CPU是市場的趨勢。
寫多執行緒程式時常見的問題
相較於單一執行緒，這些是寫多執行緒時常見的問題 :
- Race Condition
- Deadlock
- Context Switch
- Debug & Other
Race Condtion
當不同thread同時對一份資料做讀取&寫入時，就會產生race condtion，以下圖為例，假設原本有一份Data內的值是2，兩個thread - A與B同時對這個值做+5的動作，雖然我們身為旁觀者可以很直覺的預期結果應該是2+5(A)+5(B) = 12，但事實上Thread A跟B在讀這筆資料的時候有可能都還是2，最後寫入的時候卻把另一個thread算出的結果覆蓋掉了，輸出的結果變成7。
當程式中有race condtion時，整支程式就會變得非常不穩定而且還難以debug，因為往往是執行時的時間差造成預期外的結果。
Deadlock
為了避免race condition，常見的作法就是用lock。當某個thread要對某個資料做讀寫時，設定一個lock，其他thread如果想要更改這份資料，必須等待原本lock這份資料的thread做unlock的動作。但這又衍生出另一個問題 - 如果沒有unlock呢? 如果thread跑一跑出現exception直接死了呢? 這種情況就是deadlock，其他thread會一直等待下去。過沒多久程式就會垮了。
Context Switch
CPU的core數是有限的，程式內new出來的thread數有可能超過當前可執行的core數，這種時候CPU的core必須暫停當前執行的thread task，轉而執行更高priority的thread task﹐而CPU的core做thread的切換的動作即是context switch。
執行Context switch的時候，在切換到新的thread之前，要先將當前thread的狀態記錄下來，之後才能回頭過來繼續執行。而切換到新的thread之後，由於新的thread內所需的資料有可能不再當前的cpu cache內，CPU又必須重新在從RAM內把需要的資料抓出來。
以上的這些操作對於效能來說都是昂貴的操作，可以慢至1萬~100萬nano seconds( 從L1 cache讀取資料只需要1 nanosecond )，所以在寫遊戲的程式時，我們希望能夠盡量避免出現context switch。
Compiler的優化(Out-of-order execution/memory reordering)
很多人不會注意到，不同的CPU針對code是會做不同程度的優化的，現代CPU為了最大化執行時的效率以及提升執行指令的吞吐量，其實不一定會依序執行每行code的指令，對CPU來說，它只要能確保最終輸出的結果是一樣的就行。
以下圖來說，假設同時呼叫了func1(ThreadA)與func2(ThreadB)，func2的flag變數會是true還是false呢?
單從左邊func1的code來看，我們會預期當b為0時，a已經被設為2，所以func2內的flag一定是true。
但是在Out-of-order execution的情況下(見下圖)，b被設為0的時候，有可能a的值還沒被更新為2，就會有預期外的結果。這種情況在多執行緒的code中更容易發生。
有build過遊戲/App客戶端的人應該都對release build跟debug build這類選項不陌生，compiler針對release版常常就會自動幫你優化code 或像是strip掉多餘的code，有些專案還會做code的混淆，所以寫多執行緒的code時就會遇到一些release版才會出現的bug。
多執行緒程式的門檻這麼高，我還是繼續寫單執行緒好了?
Fiber based job system
fiber based job system這個方案解決了寫多執行緒的code時因為上述幾點產生bug或效率低下的情況，下圖是個簡單的示意圖 -
簡短概括Job System :
- 利用worker thread還有core一對一的關係來避免context switch
- 將logic放進job內，而不是thread。
- 透過scheduler來將job分配到不同的worker thread
- 利用設定Job之間的dependency來實作複雜的task組合
- 為了避免race condtion，Job執行完後會有一個sync point。sync point後可以確保此時沒有其他thread在讀寫同一份data。
C# Job System
Unity的Job system排程的部分大致上也是遵循了上面fiber based job system的概念，我們在Unity官方提供的示意圖可以看到Job Queue以及worker thread與CPU core的對應關係(見下圖，右半部)。
Safety System
Unity的Job system還有一個特點就是Job內操作的資料只能是value type，所以不會有不同thread透過reference修改資料的情況發生，利用這種機制來完全避免掉race condition的發生。
Native Container
完全使用value type的方式的缺點是資料會完全隔離在各自的job內，假設今天job 1、2、3都想針對一個物體的position進行不同的計算，使用上就會有很多不便，為了克服這一點，Unity提供了Native container這類的容器，以便讓不同Job可以共享這塊記憶體，safety system會自動去track當前所有正在讀/寫這一份native container內記憶體的Job，如果有race condition的情況發生，Unity會報錯。
1.Native Container顧名思義，它其實是一個C# Wrapper，內部封裝的是native memory，所以不會被GC偵測，使用完畢需要手動dispose。
2.Native Container允許同時間被不同job平行讀取，但負責寫入資料的job同一時間只能有一個
JobHandle and dependencies
Job system有個很重要的功能就是要能設定job間的dependency(相依)。
比如寫一個讓所有AI自動走去攻擊玩家的系統，第一個job先更新玩家位置，第二個job更新各自path finding的路徑，最後一個job則負責移動所有AI。這系統就會需要讓job之間有先後的dependency。
Unity的job system提供了JobHandle這一種結構來設定dependency，每次呼叫Job.schedule()後，會回傳一個JobHandle，可以將這個job handle當成參數在相依的job schedule時傳入。
C# Job System的用途
列一下Unity的C# job system的常見用途
- 讓某個task在背景執行，降低main thread的loading，比較常見的像是更新遊戲內AI的path finding的結果、navmesh的重建。這類task都很適合背景執行。
- 大量的計算 - 多執行緒的強項是平行處理，尤其是Unity的Job system更是，Unity提供了一些專門用於平行處理的Job。這類job可以在計算長長的array時拆分成更小份的job，同時分配到不同thread去計算，像是Cpu 的culling，骨架動畫中joint的IK計算、CPU端的布料模擬，都是常見的應用。
- Data oriented的實踐 - 讓Unity的Job system最特別的地方，是這套系統完全相容Burst compiler，Unity的Burst compiler可以將指定的C#程式碼編譯成SIMD friendly的machine code，在平行處理大量資料時，搭配像是native array這種記憶體緊密排列的data，可以讓程式的速度暴增30~100倍。
用Unity的job system時，無腦在每個job上加個[Burst Compile]，Job的處理速度就會直接翻N倍。
總結
Unity的C# job system寫起來一開始有點綁手綁腳的感覺(只能用value type的限制，native container的操作...etc)，但習慣之後會發現這套做法讓寫多執行緒code的門檻變得很低，幫我們規避掉不少寫多執行緒程式時會遇到的坑，再加上Burst的無腦加速實在是太強了。
我還沒用過Unity剛推出的ECS 1.0，但已經多次利用job system突破原先程式的效能瓶頸，如果對Unity的DOTS有興趣的人可以先從C# job system先開始熟悉。
簡單介紹就到這邊，之後有空在介紹Job system內每種Job的實際操作。
