# 2016q3 Homework5 (jit-compiler)

contributed by <`HaoTse`>, <`shelly4123`>

---

## 作業要求

- 提出改善內建 benchmark suite 效能的機制，並且要能夠充分解釋行為，需要一併透過 gnuplot 自動產生效能分析圖表
- 參考以下實做，對 Brainfuck 程式語言進行擴充，使其能夠支援 concurrency / parallelism。需要有程式語言的規格描述並且驗證。
- [ ] [Bukkake](https://bitbucket.org/wjmelements/bukkake): A parallel brainfuck JIT in C
- [ ] [Brainfuck Process Extensions](http://www.kjkoster.org/BFPX/Brainfuck_Process_Extensions.html)
- [ ] [Parallel Brainfuck](https://github.com/cmdli/parallel-brainfuck)
- [ ] [Concurrent Brainfuck](http://www.schabi.de/cbf/)

---

## Brainfuck 程式語言

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


在 [brainfuck optimization strategies](http://calmerthanyouare.org/2015/01/07/optimizing-brainfuck.html) 提到以下最佳化策略:
* 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`