A09: jit-compiler
主講人: jserv / 課程討論區: 2016 年系統軟體課程
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
返回「進階電腦系統理論與實作」課程進度表
預期目標
- 學習設計 JIT 編譯器
- 運用計算機組織的背景知識,進行深入效能評估和提出改善方案
- 延展程式語言,提供 concurrency 能力
Brainfuck 程式語言
Brainfuck 程式語言由 Urban Müller 在1993年建立,比C語言大約問世於1972年還來晚的多,此語言中雖然簡易,只有八個運算字元,但不論基本數學運算,或是迴圈等等他都能勝任,是個麻雀雖小五臟俱全的語言,以下是此語言的運算符號及意義。
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
接著我們就來探討要如何改善此Complier,在此語言上因為極其簡易,因此許多的運算是累贅的,例如乘法、初始值等,又或是迴圈的使用,因為 Brainfuck 的迴圈終止都是仰賴 Array[0] 來判斷,在 Index 的運算上其實會有很多的不必要。在 brainfuck optimization strategies 提到以下最佳化策略:
- Contraction
- Clear loops
- Copy loops
- Multiplication loops
- Operation offsets
- Scan loops
在這些改善方法上也可參考 打造 Brainfuck 的 JIT compiler ,探討 Brainfuck Xbyak JIT Assembler。
Optimization
在開始進行最佳化前,先記錄未最佳化之數據。
- progs/awib.b GOOD 70.1ms
- progs/mandelbrot.b GOOD 2924.2ms
- progs/hanoi.b GOOD 7308.1ms
Contraction
此方法是將多餘運算整併,例如 +++++ ,其實就是+=5,此改善方法雖然直覺簡單,但實質效益也不差,而實作方法可在遇到+ - > < 時即檢查是否為連續出現。而在此我們保留 inc 在只有出現一次的時候,可使效能最佳化。
執行結果
- progs/awib.b GOOD 41.5ms
- progs/mandelbrot.b GOOD 1018.0ms
- progs/hanoi.b GOOD 3799.4ms
Clear loops & Copy loops & Multiplication loops
此部分是將值 Copy 到其他位置上,而 Multiplication loops 是多了一個乘數,Copy loops 則是直接複製,我們現在這段function可涵蓋眾多pattern,只要開頭是 [- 然後是單一迴圈無巢狀,迴圈內也無其他的減法,就能被涵蓋在內,因此標題上的 **Clear loops & Copy loops & Multiplication loops **皆可被涵蓋其中。
執行結果
- progs/awib.b GOOD 37.0ms
- progs/mandelbrot.b GOOD 2526.5ms
- progs/hanoi.b GOOD 2929.1ms
Operation offsets
Scan loops
此部分在 Hint 中提到用 memchr() 來最佳化,可 parallel 比對8 bits 之字串,而處理的 pattern 如 [<<<] 等。在下圖中,我們可看到 awib 以及 mandelbrot 有著較多的 Scan loops ,但進一步分析,可發現 awib 的 Scans loops 都以 [<], [>] 居多,而 mandelbrot 則以較多的offset 如 [<<<<<<<<<] ,在此部分上的差距可能對效能上也會有所影響。
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
移除換行符號
為了能更有效率的判斷,我們加入移除換行符號的 function,如此我們可以降低換行所帶來的影響,也方便之後的演算法方便寫作,不須多考慮換行的差異,如原本是連續的+,有可能會因為換行而截斷,變成兩次add。在這裡補上測試數據,若以完成上述最佳化方法的情況下來測試。
原本
- progs/awib.b GOOD 18.3ms
- progs/mandelbrot.b GOOD 721.9ms
- progs/hanoi.b GOOD 61.4ms
調整後
- progs/awib.b GOOD 15.3ms
- progs/mandelbrot.b GOOD 684.1ms
- progs/hanoi.b GOOD 45.3ms
可發現在時間越大的 test bench 上其效果會更加顯著。
綜合分析
在針對 Brainfuck Compiler 的效能改善上,其實可分為兩個方向來作增進
Contraction
在此我們可分析 **Contraction **所改善之數量,意即透過 **Contraction **減少多少指令,此採計對象是以未被其他優化方式優化之部分,即是真實有使用到 **Contraction **部分之程式碼,其壓縮比例都相當不錯,尤其在 hanoi 上有極明顯之效率,此數據與執行時˙間也有對應之,但若要能更精確的來探討執行時˙間,可能要多加入上述兩方向的實際所占執行時間比例,能更清楚分析其所占比例,因迴圈必須在實際執行上來估計,若透過此數據能完整呈現此作業的面貌,也能更加清楚可改進之部分。
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
Reduce Loops
以下我們就以 Loops 來作分析,我將 test bench 個別作分析,可看到我們所作的改善其實包含範圍只有50%左右,其他可能是巢狀迴圈或試其他特殊迴圈,以致於不被包含在我們所訂定的制式迴圈中,而針對上面在對我們所定義的迴圈格式改善中,可看到執行時間上在 mandelbrot 並不太顯著,此問題在這裡可被凸顯出來,在 Scan loops 他所佔據之比例大約有五分之一,而 Scan loops 又是極耗費時間之動作,因此改善效果就沒其他兩者 bench 來的好。而 hanoi 的改善效能極好,因其 Loops 被優化範圍高達 80%,而 awib 的改善範圍則只有 45%,但在 other loops 中其運算並不算太複雜,且 multiplication loops 比例也快有 20%,所以改善效能狀況也還不太差。
所以若我們能改善 Scan loops 那其實對 mandelbrot 應該能有顯著之改善,而若能針對巢狀迴圈或其他迴圈上改進,那對於 awib 應該也能有明顯的加速。
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
問題與討論
在這裡我們可發現 hanoi.b 的改善效能最好,有155倍的差異,而其他兩者則改善4倍,mandelbrot.b 有跑出漂亮的684ms,我們可探討一下為何 hanoi 的改善效果能如此漂亮。
其實打開檔案來觀察,不難發現hanoi 的>
<
極多,看起來非常整齊,這些都是可以被降低的,再者也有許多的Loops可以被簡略,這些都是我們改善的重點,也因此原本長約的700行test bench,168134行的組合語言,改善到42742行;在 mandelbrot.b 中則有許多的 [<<<<<<<]
,且也無 hanoi 來的多累贅運算。
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
上圖是對於改善的程式碼長度,下面則放上執行時間的統計圖,方便大家做一比較。可發現mandelbrot 對於 **Contraction **較有反應,此部分感覺是因為一些特殊pattern目前無法用Remove Loops 去除,因此產生此對比性。
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
除錯提示
Brainfuck 以及指令集都不是我們所熟悉的,而且不容易 print 值debug,在這裡我是用在 Makefile 內的 run-jit-x64 ,此動作可 dump assembly code,對作業的debug上有相當之益處,可發現問題的癥結點;另外我也有印出在 file 中也會方便使用者來檢查,若直接 print 出有時會影響到結果值,或是可能直接不 print 出 ( 在有bug的狀況下 )。
( 未優化前滿滿的dec )
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
作業要求
- 作在 github 上 fork jit-construct,注意不要跟 2015 年的作業搞錯了
- 依據上方提示,提出改善內建 benchmark suite 效能的機制,並且要能夠充分解釋行為,需要一併透過 gnuplot 自動產生效能分析圖表
- 參考以下實做,對 Brainfuck 程式語言進行擴充,使其能夠支援 concurrency / parallelism。需要有程式語言的規格描述並且驗證。
參考資料