2016q3 Homework5 (jit-compiler)

contributed by <HaoTse>, <shelly4123>

---

作業要求

• 提出改善內建 benchmark suite 效能的機制，並且要能夠充分解釋行為，需要一併透過 gnuplot 自動產生效能分析圖表
• 參考以下實做，對 Brainfuck 程式語言進行擴充，使其能夠支援 concurrency / parallelism。需要有程式語言的規格描述並且驗證。
  • Bukkake: A parallel brainfuck JIT in C
  • Brainfuck Process Extensions
  • Parallel Brainfuck
  • Concurrent Brainfuck

---

Brainfuck 程式語言

Brainfuck 程式語言只有八個運算字元，但不論基本數學運算，或是迴圈等等他都能勝任，以下是此語言的運算符號及意義。

在 brainfuck optimization strategies 提到以下最佳化策略:

• Contraction
• Clear loops
• Copy loops
• Multiplication loops
• Operation offsets
• Scan loops

---

程式執行

按照 README 指示，安裝以下套件

sudo apt-get update
sudo apt-get install build-essential
sudo apt-get install gcc-5-multilib
sudo apt-get install lua5.2 lua-bitop
sudo apt-get install gcc-arm-linux-gnueabihf
sudo apt-get install qemu-user

執行結果

$ make
$ ./interpreter progs/hello.b 
Hello World!

未優化效能

$ make bench-jit-x64 

Executing Brainf*ck benchmark suite. Be patient.

progs/awib.b            GOOD	101.7ms
progs/mandelbrot.b      GOOD	4257.1ms
progs/hanoi.b           GOOD	10897.8ms
make bench-jit-x64  15.27s user 0.00s system 98% cpu 15.464 total

• hello.b 程式碼解釋
  執行結果會印出 Hello World!

  以印出 Hello 為例：

  • 假設有無限多個array，都初始化成0。
  • 從 ASCII 來看 H = 72、e = 101、l = 108、o = 111。
  • code 是從一個 array[0] 開始，最前面的 10 個 + 就是將 array[0] 的值加了 10。
  • 到了 [ 判斷 array[0] 是否為 0，否所以繼續執行 [ 之後的東西。
  • 進到回圈將目前位置移到 array[1] 並將他加了 7，再將 array[2] 加 10，array[3] 加 3，array[4] 加 1。
  • 接著 4 個 < 和 1 個 - 表示將目前位置移回 array[0] 並減 1。
  • 也就是說 [] 裡的動作會重複 10 遍(直到 array[0] 的值等於0為止)，執行完後 array[0] = 0、array[1] = 70、array[2] = 100、array[3] = 30、array[4] = 10。
  • 接著將 array[1] 加 2 並印出來 (72)、array[2] 加 1 並印出來 (101)、array[2] 再加 7 印出來 2 次 (108)、array[2] 再加 3 再印出來 (111)。

++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>

翻譯為對應的 c code 如下

array[5] = {0};
array[0] = 10;
do {
	array[1] += 7;
	array[2] += 10;
	array[3] += 3;
	array[4] += 1;
} while(array[0]--);

//array[1] = 70, array[2] = 100, array[3] = 30, array[4] = 10

array[1] += 2;
//print("H");
array[2] += 1;
//print("e");
array[2] += 7;
//print("l");
//print("l");
array[2] += 3;
//print("o");

---

參考資料

tags: HaoTse shelly4123 team11 sysprog21 jit-compiler