Just In Time Compiler - Part 0. 專案說明與綜觀介紹

編譯器已經融入我們生活的每一個角落，在計算機科學上佔有一席之地，在本篇文章，先介紹本專案每一個 Part 的目的，並且介紹編譯器跟及時編譯器的目前技術發展，最後以 javascript 為例解釋及時編譯技術的應用。本專案的程式碼在我的github (opens new window)。

一、專案說明

大家有沒有看過電影小姐好白，真的是我超愛的喜劇😆，百看不膩，在戲裡面，兩個黑人警探假扮兩個千金大小姐，布蘭妮威爾森跟蒂芬妮威爾森，裡面有個橋段

布蘭妮威爾森	蒂芬妮威爾森

就用這個 BF 拉開本專案的序幕，BF 有三種意思

• Bitch Fit 女生抓狂
• Boyfriend 男朋友
• Brainfuck 程式語言，本專案的主角

回到正題，事實上，Brainfuck 語言短小精幹，是個圖靈完全的程式語言，然而可讀性極差，真的是會讓人 Bitch Fit，然而語法操作的簡單很適合拿來被我們拿來當作編譯器、及時編譯器的來源語言。經過本專案一步步的實作，由 JIT compiler 的牽線，讓 Brainfuck 語言從令人 Bitch Fit 變成我們的 Boyfriend，迫不及待了嗎 ? 接下來就是本專案的主題簡介。

Part	主題	說明
1	Simple JIT	利用 Dynasm 幫助建立簡單的 JIT
2	BF compiler	建立簡單的 Brainfuck compiler 和 interpreter
3	BF compiler interpreter comparison	比較 Brainfuck compiler interpreter 和 編譯器最佳化比較
4	BF optimization	直譯器最佳化、實作及時編譯器
5	Cross comparison	將所有的程式做一次性的結果探討
6	Threaded Code	以 Threaded Code 的手法降低 Dispatch Overhead

二、Why Compiler ?

1. 為什麼需要編譯器 ?

   • 為了更快、更有效率的使用硬體，如 CPU、GPU等

   • 程式碼可以跑在不同硬體平台上

   • 廣義的編譯器定義是把 A 語言轉換成 B 語言，這個概念可以讓我們更方便的開發程式，這個以前端為例

     • Typescript : 比 javascript 來的易除錯(因為是強型別、物件導向式)，快要變成前端的主流語言，我們需要編譯器的轉換，就可以更輕鬆撰寫前端程式

     • SASS / SCSS : 和上一點一樣，CSS 一遇到巢狀跟繼承問題，很難除錯，利用更好懂得格式再編譯成 CSS 就可以大幅減少開發負擔

     • markdown : 這個大家如果常常做筆記應該很熟悉，利用 markdown 的簡潔的語法自動生成整齊的網頁格式。

2. 哪裡有編譯器的影子 ?

   • (行程)虛擬機

     • 通常混和編譯加直譯

     • 如 Google V8 、 Pypy 、 FlaCC 、 JVM 、 .NET 、 Android ART 、 OpenGL ( where to find compiler (opens new window) )

   • 一般編譯器

     • GCC、Clang : 將不同的程式語言轉成對應指令集架構的程式碼

     • Babeljs : 將程式碼編譯成 javascript，大幅降低前端開發的成本

     • SASS / SCSS compiler : 將 SASS / SCSS 編譯成 CSS

     • markdown compiler : 將 markdown 編譯成靜態 html 網頁

3. LLVM 編譯器框架，因為統一了 IR 以及對 IR 的優化，再也不用因為執行平台的不同要花大量時間重新設計，可以幫助我們快速建立一個 Compiler，現在很多編譯器都使用 LLVM 開發，LLVM 也有豐富的編譯輸出 (ARM, x86, Alpha, PowerPC)，LLVM的出現，讓不同的前端后端使用統一的LLVM IR ,如果需要支持新的程式語言或者新的設備平台，只需要開發對應的前端和後端即可。同時基於LLVM IR我們可以很快的開發自己的程式語言。

   IR 圖一	IR 圖二

   也因此，LLVM統一的IR是它成功的關鍵之一，也充分說明了一個優秀IR的重要性。IR可以說是一種膠水語言，注重邏輯而去掉了平台相關的各種特性，這樣為了支持一種新語言或新硬體都會非常方便

4. 根據此篇文章 (opens new window)提到有限的精力跟無限的算力，深度學習編譯技術才會越來越重要，人會特定去最佳化某些算子(卷積)，而不一定適用網路的每一層。但深度學習編譯器可以幫助我們進行針對網路的每一層進行最佳化，通過（接近無限）的算力去適配每一個應用場景看到的網絡，這是深度學習編譯器比人工路線強的地方。編譯器可以達到更多的自動化，以下節錄至該文章

   當比較TVM和傳統方法的時候的時候，我們往往會發現：在標準的benchmark（如imagenet resnet）上，編譯帶來的提升可能只在10%到20%，但是一旦模型相對不標準化（如最近的OctConv，Deformable,甚至是同樣的resnet不同的輸入尺寸），編譯技術可以帶來的提升會非常巨大。原因也非常簡單，有限的精力使得參與優化的人往往關注有限的公開標準benchmark，但是我們的部署目標往往並非這些benchmark，自動化可以無差別地對我們關心的場景進行特殊優化。接近無限的算力和有限的精力的差別正是為什麼編譯技術一定會越來越重要的原因。

   

   另外，一個較新的技術 - TVM，引入 graph compiler，將深度學習的模型轉成 graph IR，對 IR 進行最佳化後，可以跑在如手機這種硬體資源較低的移動式裝置(當然會捨棄精度減少計算量，在精度和效率之間進行取捨)。和傳統編譯器不同的是，這類編譯器不光要解決跨平台，還有解決對神經網絡本身的最佳化問題，這樣原先一層的IR就顯得遠遠不夠，原因在於如果設計一個方便硬件最佳化的低階的語言，你幾乎很難從中推理一些神經網路中高階的概念進行最佳化

   TVM 圖一	TVM 圖二

   另外TVM的對手，XLA（加速線性代數）是針對線性代數的特定領域編譯器，可優化TensorFlow計算。結果是在服務器和移動平台上提高了速度，記憶體使用率和可移植性。

總結來說，因為根據摩爾定律，硬體晶片效能約每隔兩年便會增加一倍，但是近來計算能力的需求爆炸性的增加，例如深度學習，以及計算機架構的多樣性，摩爾定律逐漸跟不上計算能力的需求，所以我們需要編譯器，針對有限資源的硬體及架構產出最佳化、效率最高的程式碼

三、Compiler Language vs Interpreter Language

參考連結 (opens new window)

跟據翻譯的方式，分為編譯器和直譯器，以下為兩者比較

	編譯器	直譯器
執行	要先編譯再執行	不用事先編譯
啟動	慢 (要等編譯)	快(不用事先編譯)
執行效率	快，編譯時還可以事先優化	慢
重編譯	不用	每次啟動都要重編譯
跨平台	差，換平台需要重編譯	好
示意圖

另外像 JVM，在 編譯 和 直譯 之間做一個取捨

1. 先編譯成中間文件 ( Bytecode)
2. 再直譯執行，並搭配 JIT compiler 的 runtime 優化

四、Just-in-time Compiler : 以 Javascript 為例

JIT Compiler 引入，使我們可以達到動態編譯的技術，以下以 Javascript 為例，這裡參考 A crash course in just-in-time (JIT) compilers (opens new window)

Google V8 圖一	Google V8 圖二

先參照下列表格

	Baseline compiler	Optimizing compiler
編譯,優化單位	程式碼行（stub）	函數
編譯花費時間	短	長
程式碼是否最佳化	否	是

如上圖，JIT 會有一個監視者(monitor/profiler)，會監控程式碼執行的次數以及型別的使用

當程式碼開始"暖"起來，Baseline compiler 就會開始做事，根據此篇問答 (opens new window)

baseline compiler is to generate bytecode or machine code as fast as possible. This output code (machine code or intermediate code) however is not very optimized for a processor, hence it's very inefficient and slow in runtime.

baseline compiler 盡快幫我們產生 bytecode 或是 machine code，baseline compiler 會把函數的每一行編譯成一個 stub，換言之，是以函數的每一行為編譯單位，這些 stub 會被行號以及變數型別索引。如果監控者看到同樣的程式碼再出現一遍而且型別相同，就會把剛剛編譯過的程式碼直接丟回去執行，不用重編譯。可以加速執行時間。然而，baseline compiler 可能會做一點點最佳化處理，但是又不想耽誤執行時間太久，因此這些 code 並不是真正最佳化的code。頂多算是稍微好的code，但是執行效率仍然不夠好。 然而，如果這段程式碼真的很"燙(hot)"，甚至占了大多數執行時間，那就非常有必要花費額外時間去做最佳化處理。

如上圖，上圖左邊是 baseline compiler 編譯好的程式碼(那些像白紙的東西)，不過如果這段程式碼真的很"燙(hot)"，monitor 會把這段程式碼送去 Optimizing compiler，產生出更高效能的程式碼。但是編譯時需要符合某個假設，那就是物件一致性。舉個例子，因為 javascript 是動態語言，可以在一個陣列裡面裝不同型別的物件，可能前 99 個物件都是房子，最後一個物件卻是怪物☢，所以 compiled code 在跑之前需要確定好假設是正確的，如果是對的，就跑這個 code，如果突然變怪物，那就會把這段最佳化的程式碼給丟掉💔，然後去跑 baseline compiled 版本，這個丟掉optimize 返回baseline過程稱為 解最佳化或反優化(deoptimization)

雖然 Optimizing compiler 可以產生出更高效能的程式碼，但是可能會造成不可預期的效能問題，假設有個陣列有100個物件，這裡用虛擬碼宣告

[ 房子 * 9 + 怪物 * 1 ] * 10

當執行到第九次房子，監控者認為很熱時，送去最佳化編譯，但下一個遇到不符合假設的怪物物件，馬上又丟掉這段最佳化程式碼。這樣反覆最佳化 - 解最佳化，會嚴重影響到效能，那還不如乾脆執行 baseline compile 的程式碼就好，因此大部分的瀏覽器都會限制這段反覆次數，假設來回最佳化超過10次，就乾脆不最佳化💔

A crash course in just-in-time (JIT) compilers (opens new window)舉一個例子，Type specialization 看看簡單的程式碼背後的原理卻一大堆哲學，由於javascript 是動態弱型別語言，所以在執行時間時需要多做更多工作

function arraySum(arr) {
  var sum = 0;
  for (var i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
}

+= 看起來一個動作就好，感覺蠻簡單的，但是因為是動態型別，實際上背後偷偷執行更多東西，像是因為javascript是弱型別語言，javascript 允許字串和整數相加，例如

var a = 123 + '456'
// a is '123456'

sum += arr[i]，可能前 99 個都是整數，但是最後一個就是字串，導致剛剛最佳化程式碼不能用要捨棄，因為從整數的相加變成字串的相加，兩者的運算有本質上的不同。所以 JIT 會看這段 stub 是 monomorphic(不變的) 或是 polymorphic(變動的) (型別是否都相同)。如下圖

問題檢查樹狀圖	Compiler 檢查的過程

假設沒有 Optimizing compiler，當這段code 要執行時，JIT 就要不斷檢查這些型別問題，在一個迴圈下，必須要不斷重複檢查審視這些問題，但其實可以加速執行，就出現 Optimizing compiler，compiler 只需要把整段函數編譯，每次執行時都先檢查arr[i]的型別即可，根本不用每一行都檢查型別，如下圖

而火狐瀏覽器有做最佳化的處理，例如JIT再進入迴圈前會預先判斷是否整個陣列是整數型，減輕判斷時的負擔。

參考連結

1. Deep Learning的IR之爭 (opens new window)

2. JS 及時編譯器 Just-In-Time (JIT) compilers (opens new window)

3. What Can Compilers Do for Us? (opens new window)

4. 為什麼這麼多人喜歡寫編譯器？ (opens new window)

5. 虛擬機器設計與實作 (opens new window)

6. 深度學習編譯技術的現狀和未來 (opens new window)

7. 深度學習編譯器學習筆記和實踐體會 (好專欄!) (opens new window)

8. Jserv 演講- 窮得只剩下 compiler (opens new window)

9. A crash course in just-in-time (JIT) compilers (opens new window)

10. What is a baseline compiler? (opens new window)