lyharthur's HW4(B)
 

作業要求 (B)

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

投影片

Brainfuck Instructions
>     指到下一個位置            ptr++
<     指到前一個位置            ptr--
+     將目前位置的值+1      *ptr++
-      將目前位置的值 - 1       *ptr--
.      印出目前位置的值 
,      輸入一個數值並將之存入目前位置
[      如果目前位置的值為零,跳到 ] 之後一道指令
]      無條件跳回到對應的 [ 後一道指令
 
優化方法
在閱讀完投影片之後,知道了以下幾種優化的方法:
  1. 將連續的重複指令合併
 2. 對 pattern [-] 做特殊處理,可以看成 *ptr=0 (set to zero)
 3. 對 pattern [>+<-] 以及 [->+<]做特殊處理,可以看成 *(ptr+1) += *ptr , *ptr=0 
 
參考資料
x64 Architecture 裡面標示出來的是可使用暫存器。像是bl , cl 等等
 

結果

  1. 未優化版本
progs/awib.b             GOOD
95.4ms
progs/mandelbrot.b       GOOD
3942.1ms
progs/hanoi.b            GOOD
10241.8ms
2. 將連續的重複指令合併
progs/awib.b             GOOD
57.0ms
progs/mandelbrot.b       GOOD
1481.8ms
progs/hanoi.b            GOOD
5205.3ms
很明顯的可以看到執行時間大幅縮短,幾乎都縮短將近一半的執行時間。
 
3. 重複指令合併+case [-]
progs/awib.b             GOOD
48.6ms
progs/mandelbrot.b       GOOD
1404.8ms
progs/hanoi.b            GOOD
151.6ms
可以發現hanoi 幾乎只剩下原來1.4%的執行時間,由此可推論hanoi.b 中有大量的 [-] pattern
4. 重複指令合併+case [-] + case [>+<-] [->+<] 
progs/awib.b             GOOD
47.3ms
progs/mandelbrot.b       GOOD
1419.2ms