WFU

2018年4月23日 星期一

無所不在的位元組碼直譯器 (Bytecode interpreter) 是怎麼運作的?


這份筆記將提及 Bytecode Interpreter 1 如何運作及應用，最後引用 Steve Kemp 的實作來說明。從中了解當時一個困擾的問題，如何從無到有被克服，而其中的解法又如此漂亮。

Why Bytecode Interpreter?

1991 年在 Sun Microystems 工作的 James Gosling 希望找到一種方式讓程式可以在不同的平台運作且不用再重新編譯。 也就是 “Write once, run anywhere!”。在1995 年，第一版 JAVA 釋出了。

而其中的精髓就是 Bytecode Interpreter，如下圖所示，任何語言程式一旦能夠編譯成制定好的 Bytecode，就能夠透過 Interpreter 對應到不同平台的指令集，運行程式。

enter image description here

現在 2018 年，已有很多應用都是使用 Bytecode Interpreter ，涉及的領域廣泛，附上三個應用供大家參考：

How does it work?

接下來我們就用 Steve Kemp 寫的範例 simple-vm 來說明實作的部份。整個流程如下：將自訂的原始碼編譯成 Bytecode ，而 Bytecode 再透過 Inpterpreter 找到平台對應的指令執行。

enter image description here

這裡就用其中一個加法的範例 ( #0 = #1 + #2 ) 來展示流程。

  • write script:add.in
        store #1, 10
        store #2, 20
        add #0, #1, #2
        print_int #0

        # add newline to the output
        store #1, "\n"
        print_str #1
  • 編譯成 Bytecode
hpchang@IlhaFormosa:~/code/github/vm$ ./compiler ./examples/add.in
  • 透過 od 指令一窺 Bytecode 內部資料
hpchang@IlhaFormosa:~/code/github/vm$ od -t x1 -An ./examples/add.raw
 01 01 0a 00 01 02 14 00 21 00 01 02 02 00 30 01
 01 00 0a 31 01
  • 直譯器運行 Bytecode，得到正確的答案 10 + 20 = 30 (0x1E)
hpchang@IlhaFormosa:~/code/github/vm$ ./simple-vm ./examples/add.raw
0x001E
  • 使用 Debug 模式，將 Interpreter 內部運作的過程列印出來，在對照上面 od 指令看到的 Bytecode，可以清楚了解執行的步驟。
    – 01 01 0a 00 代表 STORE_INT(Reg:01) 0x0a
    – 01 02 14 00 代表 STORE_INT(Reg:02) 0x14
hpchang@IlhaFormosa:~/code/github/vm$ DEBUG=1 ./simple-vm ./examples/add.raw
0000 - Parsing OpCode Hex:01
STORE_INT(Reg:01) => 0010 [Hex:000a]
0004 - Parsing OpCode Hex:01
STORE_INT(Reg:02) => 0020 [Hex:0014]
0008 - Parsing OpCode Hex:21
op_add(Register:0 = Register:1 + Register:2)
000c - Parsing OpCode Hex:02
INT_PRINT(Register 0)
[STDOUT] Register R00 => 30 [Hex:001e]
000e - Parsing OpCode Hex:30
STRING_STORE(Register 1) = '
'
0013 - Parsing OpCode Hex:31
STRING_PRINT(Register 1)
[stdout] register R01 =>

0015 - Parsing OpCode Hex:00
Executed 7 instructions

以上就是整個 Bytecode Interpreter 的運作流程，供大家參考。

How to implement it in c?

此時，我們大致了解 Interpreter 實際上就是讀取 Bytecode 並對應到正確的指令執行。換句話說，就是 Dispatch table。

那實現 Dispatch table 的方法裡，c 語言中可用 switch-case 實作，上面的範例則是使用 array of function pointer。但在 CPython 中用 computed goto + lable as values 的方式，且對此方法 Eli Bendersky 的分析驗證了它比 switch-case 快了近 25%。

int main(void)
{
  int i = 0;
  static void * ptr[3]={&&do_add, &&do_sub, &&do_store};

  goto *ptr[i];

  do_add:
  .........

  do_sub:
  .........
  
  do_store:
  .........
}

到此，希望這份文章給大家一個宏觀的視野去體驗 Interpreter，並從中了解程式如何運作，透過編譯或直譯的過程去執行程式運算。

  1. 文中有些連結的文章會以 VM(virtual machine) 代表 Interpreter。 ↩︎

標籤： , , ,