Homework 4 開發紀錄(B)
  • 難度:中
  • 改善 JIT compiler,加入若干 optimization techniques
  • 紀錄若干效能最佳化技巧帶來的提昇
  • 建立新的 Hackpad,列在「+作業區
  • 標注「開發紀錄(B)」

Brainf*ck

Brainfuck是一種由八種指令構成的程式語言
Brainfuck
C
含義
>
++p;
指標加一
<
--p;
指標減一
+
++*p;
指標指向的位元組的值加一
-
--*p;
指標指向的位元組的值減一
.
putchar(*p);
輸出指標指向的單元內容(ASCII碼)
,
*p = getchar();
輸入內容到指標指向的單元(ASCII碼)
[
while(*p){
如果指標指向的單元值為零,向後跳轉到對應的]指令的次一指令處
]
}
如果指標指向的單元值不為零,向前跳轉到對應的[指令的次一指令處
 

Jit-construct

參考Virtual Machine Constructions for Dummies文件p.43-p.46實現了下列三種optimization方案
第一種優化方案:將重複的 + - > < 合併
第二種優化方案:將[-] 改為*ptr = 0 
第三種優化方案:將[>+<-]改為*[ptr+1] += *ptr;  *ptr = 0;  
 
Original Version
Executing Brainf*ck benchmark suite. Be patient.
 
progs/awib.b GOOD 77.1ms
progs/mandelbrot.b GOOD 3209.0ms
progs/hanoi.b GOOD 8189.4ms
 
Optimization Version 1 合併 + - > < 版本
將連續的+ - > <合併成加減法運算,執行後效能明顯的提升!!
 
Executing Brainf*ck benchmark suite. Be patient.
 
progs/awib.b GOOD 45.2ms
progs/mandelbrot.b GOOD 1066.8ms
progs/hanoi.b GOOD 4101.6ms
 
Optimization Version 2 合併 + - > <[-] 改為*ptr = 0 版本
在BF語法中[-]其實就是一個將數值不斷執行減法直到歸零的指令,所以在此優化版本中判斷當遇到[-]指令時就直接將數值歸零來減少過多的減法指令,執行後效能又更明顯的提升!!
 
Executing Brainf*ck benchmark suite. Be patient.
 
progs/awib.b GOOD 36.9ms
progs/mandelbrot.b GOOD 1024.5ms
progs/hanoi.b GOOD 123.7ms