2016q3 Homework5 (jit-compiler)

contributed by <tundergod>, <tempo jiji>

作業內容

開發環境

• Ubuntu 16.04 LTS
• L1d cache: 32K
• L1i cache: 32K
• L2 cache: 256K
• L3 cache: 3072K
• Architecture: x86_64
• CPU op-mode(s): 32-bit, 64-bit
• Byte Order: Little Endian
• CPU(s): 4
• Model name: Intel® Core™ i5-4200U CPU @ 1.60GHz

---

jit-construct

測試程式前安裝套件

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 bench-jit-x64
progs/awib.b            GOOD	111.3ms
progs/mandelbrot.b      GOOD	4241.5ms
progs/hanoi.b           GOOD	10967.4ms

1. 中英文字間記得以空白隔開!
2. 請更新分組頁面中的 github 連結
   課程助教

Compiler, Interpreter, Jit-compiler

• Compiler:

  • compiler 一次過將高階語言轉換爲低階語言
  • 如果程式碼有任何的錯誤會無法編譯成功並回報錯誤的地方

• Interpreter:

  • 類似 python,ruby 等,直譯器會一行接着一行的編譯並直接執行,如果程式碼中間有錯誤才報錯
  • 直譯器並不會產生任何目標檔(.o)或是執行檔(.exe)
  • 需要在程式碼與 memory 裏來回做 I/O ,所以它是非常慢的

• Jit-compiler(Just-in-time compiler):

  • 有些編譯器如java會先把程式語言通過interpreter轉換成bytecode,需要執行時JVM(JAVA Virtual Machine)會編譯這份bytecode.但是利用interpreter只是執行並產生對應的bytecode,這會增加整個編譯的過程和開銷
  • JAVA利用了just-in-time compiler的概念,會在interpreter的執行階段就先找出程式的hotspot並對他進行優化,之後compiler真正執行的時候就會執行相對少的程式以提高執行時間
  • JIT的執行效率最好可以接近compiler.compiler在編譯的時候需要產生目標檔,執行檔並使用linker等I/O,JIT則是直接對程式碼進行直譯並放去memory裏

BrainFuck研究

認識BrainFuck

• BrainFuck 是一種符合圖靈完全思想的語言
  • 圖靈完全思想是圖靈在1936年提出的一種抽象的模擬人工作的計算模型,他的運作分爲4個步驟:
    1.一條無限長的紙帶TAPE。紙帶被劃分為一個接一個的小格子，每個格子上包含一個來自有限字母表的符號，字母表中有一個特殊的符號 ◻ 表示空白。紙帶上的格子從左到右依次被編號為0, 1, 2, …，紙帶的右端可以無限伸展。
    2.一個讀寫頭HEAD。該讀寫頭可以在紙帶上左右移動，它能讀出當前所指的格子上的符號，並能改變當前格子上的符號。
    3.一套控制規則TABLE。它根據當前機器所處的狀態以及當前讀寫頭所指的格子上的符號來確定讀寫頭下一步的動作，並改變狀態寄存器的值，令機器進入一個新的狀態。
    4.一個狀態暫存器。它用來保存圖靈機當前所處的狀態。圖靈機的所有可能狀態的數目是有限的，並且有一個特殊的狀態，稱為停機狀態。

BrainFuck透過一個data pointer在一連串的data cell裏進行不同的指令：
>: data pointer往右移動
<: data pointer往左移動
+: 對data pointer目前所在的位置的資料加上1 byte
-: 對data pointer目前所在的位置的資料減去1 byte
.: 輸出data pointer目前所在位置的資料
,: 輸入資料並存入data pointer目前的所在位置
[: 如果data pointer目前的資料是0,那就跳到對應的]的後一條指令。如果不是0,就繼續執行
]: 無條件跳往之前對應的[

了解BrainFuck

Hello World!

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

• 一開始的++++++++++[>+++++++>++++++++++>+++>+<<<<-]先把第一個元素的值+10再跑while迴圈
• 在接下來的4個格子分別加上10次的7,10,3,1,在跳出迴圈後分別會 = 70 100 30 10
• 之後就是位移,加減和輸出的事情了.可以對照acsii code

加法

[->+<]

• 減掉第一個元素的值加到第二個知道第一個的值爲0

優化

• 作業上提到了6種的優化建議:

  • contraction:

    • 把連續的+,-,<,>都整合成一條指令
    ​​for (char *p = read_file(argv[1]); *p; p++) {
    ​​​​​​​​	unsigned int count = 1;//count at least be 1 because read an sym first
    ​​​​​​​​	switch (*p) {
    ​​	case '>':
    ​​​​​​​​    while(*(++p) == '>')
    ​​​​​​​​        count++;
    ​​​​​​​​    *p--;
    ​​​​​​​​    |  add  PTR, count
    ​​​​​​​​    break;
    ​​	......
    ​​	}
    ​​}
    

    • 把+,-,<,>的case都依照上面的方法改進之後的效能:
      ​​​progs/awib.b            GOOD	59.9ms
      ​​​progs/mandelbrot.b      GOOD	1396.4ms
      ​​​progs/hanoi.b           GOOD	5478.8ms
      

  • Clear loops

    • 把迴圈[-]的迭代改寫成*ptr = 0
      ​​​case '[':
      ​​​​​​​​​​​​if (top == limit) err("Nesting too deep.");
      
      ​​​if( *(p+1) == '-' && *(p+2) == ']'){
      ​​​​​​​​​​​​    p += 2;
      ​​​​​​​​​​​​|   mov   byte[PTR], 0
      ​​​​​​​​​​​​}
      

      修改後的效能爲:
      ​​​progs/awib.b            GOOD	91.9ms
      ​​​progs/mandelbrot.b      GOOD	4154.4ms
      ​​​progs/hanoi.b           GOOD	4606.7ms
      

      由於只有hanoi.b中有非常多的[-],所以它的效能提升也非常明顯

  • Copy loops

    • 把[->+<]運算式(第一個cell的值加到第二個去)改寫成
    ​​	if( *(p+1) == '-' && *(p+2) == '>' && *(p+3)=='+' && *(p+4) == '<' && *(p+5) == ']'){
    ​​​​​​​​        p += 5;
    ​​​​​​​​        |  mov  al, byte[PTR]
    ​​​​​​​​        |  add  byte[PTR+1], al
    ​​​​​​​​        |  mov  byte[PTR], 0
    ​​​​​​​​        break;
    ​​​​​​​​    }
    

    修改後的效能爲:

    ​​progs/awib.b            GOOD	103.4ms
    ​​progs/mandelbrot.b      GOOD	4271.1ms
    ​​progs/hanoi.b           GOOD	10785.5ms
    

    完全看不到任何的效果,這是因爲在測試程式中的[->+<]太少了,分別爲12個,13個和53個

  • 查看程式碼發現[->+<]的數量非常少,反而位移兩次以上的非常多,就嘗試把所有[->>....+<<....]都整合起來

    ​​//[->>...+...<<]
    ​​if( *(p+1) == '-' && *(p+2) == '>'){
    ​​	unsigned int countsym = 1;
    ​​	int n = 3;
    ​​	while( *(p + n) == '>'){
    ​​		countsym++;
    ​​		n++;
    ​​	}
    
    ​​	if( *(p+2+countsym+1) == '+' && *(p + 2*countsym + 3) == ']'){
    ​​		p = p + 3 + 2 * countsym;
    ​​		|  mov al, byte[PTR]
    ​​		|  add byte[PTR + countsym], al
    ​​		|  mov byte[PTR], 0
    ​​		break;
    ​​	}
    

    發現執行時間更加慢了:

    ​​progs/awib.b            GOOD	100.4ms
    ​​progs/mandelbrot.b      GOOD	4274.0ms
    ​​progs/hanoi.b           GOOD	11279.5ms
    

  • Multiplication loops

    • 直接用乘法代替+++[->+++<]

  • Operation offsets

  • Scan loops

• 先把contraction,clear,copy的結合起來,執行時間爲:

  ​progs/awib.b            GOOD	48.7ms
  ​progs/mandelbrot.b      GOOD	1332.3ms
  ​progs/hanoi.b           GOOD	162.1ms
  

參考資料

• Virtual Machine Constructions for Dummies
• How A Compiler Works
• 廖健富共筆
• 林郁寧共筆
• 作業共筆彙整
• Introduction to x64 Assembly
• An Optimising BF Compiler

tags: tundergod tempo jiji sysprog21 jit-compiler