2016q3 Homework5 (jit-compiler)

contributed by <jkrvivian>, <vic85821>

作業要求

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

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 –> 有趣的實做
    • 模擬 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

可以算 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

參考資料

Select a repo