Part 5. Cross Comparison

終於進入我們的最終章，一個大亂鬥的時代 ~

進到 Part 5 資料夾，執行

make

就可以自動編譯所有的程式及輸出比較表格與圖片， 首先先來看輸出的表格以及圖片，很美吧😁

Rank	program	real	user	system	Execution Time
0	interpreter	2:18.71	129.01	0.14	129.15
1	interpreter_opt1	1:02.82	61.48	0.01	61.49
2	interpreter_opt3	0:53.23	50.54	0.12	50.66
3	interpreter_opt2	0:47.69	46.79	0.03	46.82
4	sed	0:19.47	18.17	0.03	18.20
5	jit_opcode	0:04.35	3.89	0.03	3.92
6	compiler	0:04.20	3.85	0.00	3.85
7	jit_dynasm	0:04.75	3.81	0.03	3.84
8	jit_dynasm_opt2	0:01.37	1.25	0.01	1.26
9	jit_dynasm_opt1	0:01.46	1.25	0.00	1.25
10	sed_O2	0:01.21	1.20	0.00	1.20
11	sed_O1	0:01.20	1.17	0.01	1.18
12	sed_O3	0:01.18	1.17	0.00	1.17

可以發現我們從頭到尾的心路歷程，從最簡單的 interpreter 一路走到 JIT compiler，最後我們經過最佳化的JIT compiler 和 編譯器方法最佳化的速度幾乎一致，及時編譯器的效果很猛吧😁，接下來三個小節就來探討各個不同比較的組合。

5.1 Interpreter 家族

Rank	program	real	user	system	Execution Time
0	interpreter	2:18.71	129.01	0.14	129.15
1	interpreter_opt1	1:02.82	61.48	0.01	61.49
2	interpreter_opt3	0:53.23	50.54	0.12	50.66
3	interpreter_opt2	0:47.69	46.79	0.03	46.82
4	sed	0:19.47	18.17	0.03	18.20

可以發現，interpreter 先經由 jumptable 的優化後， 效率直接提升一倍 ，之後再加上contineous_count 的運算壓縮後，又快了大約 15 秒，而再加入處理 loop pattern 後，效率反而慢了一點點。但是這些都還沒有 sed 先轉成 C code 再編譯的方法快，原因是因為 interpreter 儘管最佳化，仍需要讀取 BF code 外，每個運算都要經過至少兩個 branch 的指令(for loop + switch case)，而編譯後的 sed 少了很多 branch 指令，自然而然指令數量少，執行效率也會加快很多，這就是為什麼 interpreter 仍然效率輸 sed 的方法的理由。

5.2 最佳化 Interpreter vs Simple Dynasm JIT

Rank	program	real	user	system	Execution Time
0	interpreter_opt1	1:02.82	61.48	0.01	61.49
1	interpreter_opt3	0:53.23	50.54	0.12	50.66
2	interpreter_opt2	0:47.69	46.79	0.03	46.82
3	jit_dynasm	0:04.75	3.81	0.03	3.84

將 interpreter 引入了 JIT 的技術，在執行時間產生機器碼直接執行，可以看到，無論我們的直譯器做了多少最佳化，真的就是被 JIT 屌打😂。效率直接高了近 15 倍。所以 JIT compiler 的確可以幫我們大幅加速直譯器的執行效率😀。

你可能會覺得很奇怪，為何同樣是直譯的感覺，不是都是 for loop 後再 switch 執行對應的程式碼嗎 ?

這裡我也想了很久，為何都是指令，p++ 跟 直接執行機器碼的加法執行的就差這麼多 ? 相信很多人都會誤以為就是網路上所說的「直接執行機器碼不用再重新翻譯所以比較快」，這句話是正確的，因為通常 JIT 的實作就是快取常用的機器碼，但在本篇的實作中，如同文章 Adventures in JIT compilation: Part 2 - an x64 JIT (opens new window) 所述

The reason is that the baseline performance of the JIT is vastly better. I've mentioned this briefly in part 1 - imagine what's needed to interpret a single instruction in the fastest interpreter.

1. Advance pc and compare it to program size.
2. Grab the instruction at pc.
3. Switch on the value of the instruction to the right case.
4. Execute the case.

This requires a whole sequence of machine instructions, with at least two branches (one for the loop, one for the switch). On the other hand, the JIT just emits a single instruction - no branches. I would say that - depending on what the compiler did while compiling the interpreter - the JIT is between 4 and 8 times faster at running any given BF operation. It has to run many more BF operations because it doesn't optimize, but this difference is insufficient to close the huge baseline gap. Later in this post we're going to see an optimized JIT which performs even better.

事實上， 我們的實作方法是先用 for loop 掃一遍，將機器碼存在陣列裡，再用可執行的記憶區段去執行這段陣列 ，而一般直譯器是每執行一個指令都要經過兩個 branch (for loop + switch)，才能真正執行到運算。因此假設 BF 的 code 是 +++

BF Interpreter	Our BF JIT Compiler
jmp branch(loop) jmp branch(switch) add jmp branch(loop) jmp branch(switch) add jmp branch(loop) jmp branch(switch) add	add add add

所以相當於 JIT 先幫我們快速掃了一遍跟判斷，把指令存在一個陣列，再執行一段沒有 branch 的程式碼 ， 那如同上表，在指令執行的數量上就差很多。一般直譯器可能因為邊讀邊執行，所以每只行一個動作都要多做幾個branch指令，一旦程式碼越大，效能整個就會被拖跨，而在我們 JIT 就是先一次非常快判斷掃一遍，去除所有 branch 的判斷，直接執行純粹的加減法指令，也就是在這裡 JIT 可以贏做一堆前處理、最佳化的直譯器的原因。 (備註 : Dynasm 幫我們把指令存起來再放入可執行記憶體區段執行，這篇文章 (opens new window) 對於 Dynasm 講的蠻詳細的 )

::: info 這種直譯的 for loop 搭配 switch case 的 overhead 有個專有名詞叫做 dispatch loop 或 dynamic dispatch，如果像是 BF 這種比較簡單的直譯，那 dispatch 的成本佔執行時間的比例就會較大，而傳統會使用 threaded code 手法加速，這種加速手法會更明顯。這個方法之後會加入分析。也有做法是將全部程式碼都一次展開，如同本次 JIT 一樣，用空間換時間的方法，再用 threaded code 進行最佳化。 :::

5.3 站在顛峰 - 最快的辣些人

Rank	program	real	user	system	Execution Time
0	jit_opcode	0:04.35	3.89	0.03	3.92
1	compiler	0:04.20	3.85	0.00	3.85
2	jit_dynasm	0:04.75	3.81	0.03	3.84
3	jit_dynasm_opt2	0:01.37	1.25	0.01	1.26
4	jit_dynasm_opt1	0:01.46	1.25	0.00	1.25
5	sed_O2	0:01.21	1.20	0.00	1.20
6	sed_O1	0:01.20	1.17	0.01	1.18
7	sed_O3	0:01.18	1.17	0.00	1.17

在還沒做任何最佳化前(contineous_count, loop pattern)，我們實做的方法最多只能到4秒左右，但是加入了 Part4 提到的最佳化技術後，整體又快了3秒。執行效率1秒多。使得我們實做的 just in time compiler 逼近 clang 編譯器進行程式碼最佳化後的效率。很厲害吧!😉

5.4 結尾和未來工作

我們實作了不同的方法去執行運算量大的碎形 brainfuck 程式檔，最後利用及時編譯技術加上一些最佳化方法，把 普通的 interpreter 效率提升 120 倍，執行只需要 1 秒，可以說是非常值得使用及深入探討的技術。至於未來工作是加入 LLVM 及 asmjit 這兩個工具幫我們建立 JIT 編譯器，並且加入比較，且把組合語言的基礎打穩。

5.5 參考連結 (特別感謝的網站)

1. Interpreter, Compiler, JIT (opens new window)

2. JIT 編譯器原理簡述/實現Brainfuck JIT 編譯器 (opens new window)

3. 2016q3 Homework5 - JIT compiler (opens new window)

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

5. Adventures in JIT compilation: Part 1 - an interpreter (opens new window)

6. Adventures in JIT compilation: Part 2 - an x64 JIT (opens new window)