# 2016q3 Homework5 (jit-compiler)

contributed by <`jkrvivian`>, <`vic85821`>

## 作業要求
* 參考[提示](https://hackmd.io/EYTgHAxgjA7DBMBaALMgJsFBTNAzRo8mEArAAzC5rLgCG8yQA===?view)提出改善內建 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/)
---

## Just-in-time compiler

* 在執行時期進行編譯，而非編譯後再執行
* 通常會編譯成 bytecode (也有其他的，如: VM instructions) 後，就直接執行
* **bytecode**: portable code (p-code)
* a form of instruction set designed for efficient execution by a software interpreter
* 可以直接在虛擬機上執行或再進一步轉成 machine code
* interptretation 和 AOT 的結合
* make better optimizations like inlining functions that are used frequently
* use the `mmap` system call to allocate some memory that you can write to **AND** execute
* this way of allocating memory makes it executable
* [basic JIT](https://nickdesaulniers.github.io/blog/2013/04/03/basic-jit/) --> 有趣的實做
* 模擬 JIT 利用 mmap 給要執行的 machine code 空間存放
* 使用 function pointer 轉型
* 直接傳入 arguments 就可以執行 function 了!

**Ahead-of-time compiler (AOT)**

* 編譯高階語言成 native machine code (看當下使用的機器為何)
* 只須編譯一次，執行檔可以重複執行
* 可以提供更好更複雜的優化 --> JIT 會認為這花費太多時間

**Interpreter**

* 直接執行，有以下三種:
* parse 原始碼，直接執行
* translate source code into some efficient intermediate representation and immediately execute this.
* 執行預先由編譯器編譯好的程式碼，此編譯器是 interpreter 的一部分　

## Brainfuck
* an eight instruction Turing-complete programming language
* Turing-complete:
* 直譯器是 C 語言寫的
### instructions
* `>`: 指標移到下一個 element
* `<`: 指標移到上一個 element
* `+`: 指標指的資料 +1
* `-`: 指標指的資料 -1
* `.`: 印出指標指的資料
* `,`: 存資料到指標
* `[`: 指標指的資料若不為 0，就做下一道指令; 反之跳到對應的`]`的下一道指令
* `]`: 如果指標指到的地方存在，無條件返回`[`，不然跳回`[`的下一道指令

### 閱讀 [Virtual Machine Constructions for Dummies](http://www.slideshare.net/jserv/vm-construct)

可以算 ASCII 把 Hello World! 印出來, 太帥了!

++++++++[>+++++++++<-]>.  // H
<+++++[>++++++<-]>-.      // e
+++++++..                 // ll
+++.                      // o
<++++++++[>>++++<<-]>>.   // space
<<++++[>------<-]>.       // W
<++++[>++++++<-]>.        // o
+++.                      // r
------.                   // l
--------.                 // d
>+.                       // !

* 提到的優化方法:
融會所有方法後，效能大幅提升!
* contraction：簡化連續出現的相同指令
* clear loops
* copy loops
* multiplication loops
* operation offsets
* scan loops

### 閱讀 [Interpreter, Compiler, JIT from scratch]()

## 參考資料

* Wikipedia
* [just-in-time compilation](https://en.wikipedia.org/wiki/Just-in-time_compilation)
* [ahead-of-time compilation](https://en.wikipedia.org/wiki/Ahead-of-time_compilation)
* [interpreter](https://en.wikipedia.org/wiki/Interpreter_(computing))
* [bytecode](https://en.wikipedia.org/wiki/Bytecode)
* [廖健富共筆](https://hackpad.com/2015q3-Homework-4B-5I46HyqOCGJ#:h=Jit-construct)
* [林郁寧共筆](https://embedded2015.hackpad.com/-Homework4-B-h5FfVE6RTeu)
* [Oct 16, 2015 課程紀錄](https://embedded2015.hackpad.com/Oct-16-2015--83hsxgJZcZd#:h=%E5%AF%AB%E7%A8%8B%E5%BC%8F%E7%9A%84%E8%A6%81%E9%BB%9E)