Homework5 (jit-compiler)
沈思上一個作業有什麼沒做好
- 目標設立太大，不應該直接挑戰太難的目標，應該要 divide and conquerYen-Kuan Wu
- 閱讀不夠，應該要大略掃過閱讀資料，雖然不是每個都一定用得到，但腦海中還是會有點記憶，看不懂的就先記下來就好，然後互相幫助 :) Yen-Kuan Wu
- 應該要多多參考別人的筆記跟問問題，不是說一個人做不到，而是參考後自己在實作上會有比較觸類旁通，而且這是個注重開發時間的年代，但切記看完別人的筆記後要確認自己有沒有懂!Yen-Kuan Wu
- 每個人應該要給自己一個充裕的時間表，預估時間的為自己認為的兩倍，盡量能 keep 一個進度Yen-Kuan Wu
我自己的時間分配是思考/閱讀跟coding,每個作業的順序也是如此,先思考作業的目標(最對的事情),然後拆分工作(WBS/把事情做對),接著是閱讀相關文件,參考資料跟原始碼,最後再動手coding,雖然不見能夠完成作業XD,但在時間分配上就會比較有規律,心情也不會那麼焦慮了,提供給你參考~ kobe yu
作業要求
- 作在 github 上 fork jit-construct，注意不要跟 2015 年的作業搞錯了
- 依據上方提示，提出改善內建 benchmark suite 效能的機制，並且要能夠充分解釋行為，需要一併透過 gnuplot 自動產生效能分析圖表
- 參考以下實做，對 Brainfuck 程式語言進行擴充，使其能夠支援 concurrency / parallelism。需要有程式語言的規格描述並且驗證。
- Bukkake: A parallel brainfuck JIT in C
- Brainfuck Process Extensions
- Parallel Brainfuck
- Concurrent Brainfuck
參考資料
進度表
黃呂源
- 資料閱讀
- 參考資料的部分方法修改code
- 釐清三種compiler流程
吳彥寬
- code 觀察 + DynASM + 參考資料 (10/24 中午完成)
還有好多事要做R，搞不好會 delay，沒想到 DynASM 有點難R(汗Yen-Kuan Wu
Interpreter vs Compiler vs JIT
這次brainfuck實作有包含這兩種，首先我們先略窺這兩種的差異
節錄 <張家榮共筆>
Yen-Kuan
協助補充compiler/JIT在產生組合語言後最後執行的方式差異.kobe yu看了部份文件大部分都是提到說JIT是一個等到run time的時候才作compliation 的compiler
目前有幾個問題
- interpreter 是否是執行interpreter 然後在程式中再去作code to machine code的部分? loading time有點疑惑?
- Jit 應該是再執行時期再去做compliation的動作?
i. 是否是先在interpreter下，去做一個jit的動作?
ii. profiler 不知道是什麼
iii. jit的code scope範圍以及deadline?
Interpreter
其實就是寫一個程式將 brainf*ck 轉換成 C 語言，之後再用 C 對應的 assembly code 來執行
case '-':
--(*ptr);
break;
case '.':
putchar(*ptr);
break;
Compiler
相較之上，是編譯成 assembly code
JIT
聽到很久了，但從來沒看過，就我所知他即是將 brainf*ck 轉換成 assembly code machine code，所以他比上面 interpreter 少了一步
這邊解釋我認為可以看，張家榮同學的共筆，他寫的詳細且簡潔。Yen-Kuan Wu
有看到廖健富共筆中有寫尚未實作profiler 所以JIT 無法邊編譯邊執行
Code 觀察
實驗
Original
progs/awib.b GOOD 150.1ms
progs/mandelbrot.b GOOD 3511.0ms
progs/hanoi.b GOOD 8808.4ms
$ make bench-jit-x64
Executing Brainf*ck benchmark suite. Be patient.
progs/awib.b GOOD 99.7ms
progs/mandelbrot.b GOOD 4227.8ms
progs/hanoi.b GOOD 10583.1ms
HahaSula
Contraction
$ make bench-jit-x64
Executing Brainf*ck benchmark suite. Be patient.
progs/awib.b GOOD 67.2ms
progs/mandelbrot.b GOOD 1404.2ms
progs/hanoi.b GOOD 5440.1ms
Contraction && clean loop
$ make bench-jit-x64
Executing Brainf*ck benchmark suite. Be patient.
progs/awib.b GOOD 48.7ms
progs/mandelbrot.b GOOD 1354.6ms
progs/hanoi.b GOOD 163.3ms
資料閱讀
Virtual Machine Constructions for Dummies
- Turing complete?
還記得在看
模仿遊戲才第一次得知這咚咚，最簡易版本就是可跑在 turing machine 上，更進階一點的意思是，只要符合，就可以在上面跑任何演算法。Yen-Kuan Wu
-
- While 迴圈的 interpreter
-
- if-else-elseif
張家榮共筆
家榮大用了很精簡的方式來描述三者差別。
- Interpreter
直接執行
疑問??user執行的視compiler還是code?HahaSula- Compiler
將高階語言轉為組合語言- JIT
將生成的機器碼(透過compiler)直接放到某塊JIT執行時期的記憶體(mmap)，直接執行
- [ ]可能要到程式碼看一下怎麼用到 mmap 的Yen-Kuan Wu
三者速度比：
- Interpreter
最慢，因為要不停的來回，時間複雜度為O(n)，其他兩者為O(1)- Compiler
如果只算執行時間，是最快的，但若考慮編譯時間，比JIT慢，因為多出I/O時間，把編好的檔案存起來再執行，而JIT把編好的內容，直接放入memory內，比JIT多一步，所以差異就出來了- JIT
速度第二，但每次執行均須重編，若執行很多次也是不小的負擔。
其實JIT在於常常修改code的話，是十分方便的（前提是如果code本身不大）。Compiler: I/O 應該指的是寫成 elf 檔的時間。
- JIT: 無法理解每次重編的意思，也就是不熟 JIT QQYen-Kuan Wu
- Interpreter 不產生Object檔案??那執行的mem在哪?link?a line is a excutefile?HahaSula
- Interpreter和jit compiler 跟 bf的source code 之間的關係?HahaSula
compiler Opmization
SSA (靜態compiler 使用)
將L-value做版本編號，將程式流程作區塊的分類和簡化，以此消除掉一些參數(轉化為常數)，最後推導一些flow變數，進行判斷
How A Compiler Works的return 0的例子
Contraction
對於連加或是連減進行一個整合，原本一個+指令對應到一個asm的inc指令轉換成多個+指令對應的一個asm add指令
Ex:+++
add #3 , &ptr
下列的DynASM 已經有飯粒了
copy loop
將一些Brainf*ck迴圈或是固定流程指令對應的指令減少
Ex:[>+<-] [->+<]
*(ptr+1) = *ptr;
- [ ]all clear loop (提出想法 不知道有否違背JIT)
將 Clear Loops
想法:
將tape上的單位作區隔
分類一:
">"數量 = "<"數量 有固定的迴圈變數
頭尾視為終止條件和迴圈變數
">"數量 != "<"數量 變數在tape上變動
頭尾視為終止條件和tape變數 超過tape視為無線迴圈?
分類二:
以連續">","<"作為tape block version,將相同的block version 作結合。
DynASM
DynASM is a preprocessor and tiny runtime library for creating assemblers and JIT compilers in C or C++.
form DynAsm
- How it Dynamic?
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe