虛擬機二三事 - Part 1. Stack-based VM vs Register-based VM

一、兩者介紹

1-1. Stack-based VM

Stack-based VM Wiki (opens new window) 這種類型的VM，記憶體以堆疊（Stack）儲存，適用於 0-operand instruction set，因為 memory fetch data 的動作都可以由 stack push / pop 來完成。執行運算時，由堆疊的頂端取出運算元，運算結束再存回堆疊的頂端。相較於累加器（採用 1-operand instruction set），和暫存器機（ 2-operand instruction set 或 3-operand instruction set），用零位址指令（ 0-operand instruction set）實作的堆疊機器，它的好處是程式碼密度（code density）相對較大，每個指令的占用的大小很小，可以用更少空間放更多指令，因此，它的程式通常較小。虛擬機例子如: JVM, .NET, php, python, Old Javascript engine

什麼是 zero operand instruction ?

instruction 本身就是 op_code，省略所有運算元，並非所有指令都可以此種格式表示。zero operand instruction 以堆疊的資料結構來輔助運算，因此要用 stack-based machine 來運算，必須先轉成 postfix notation (後置式 - 運算子放在運算式後面)。

Ex: Y = (A-B)/(C+D*E)

先轉成後置式 : AB-CDE*+/

指令	堆疊
PUSH A	A
PUSH A	A B
SUB	R1 ; R1 <- A-B
PUSH C	R1 C
PUSH D	R1 C D
PUSH E	R1 C D E
MUL	R1 C R2; R2 <- D*E
ADD	R1 R3; R3<- C*R2
DIV	R4; R4 <- R1/R3
POP	Y <- R4

1-2. Register-based VM

Register-based 適用於 2-operands 或 3-operands 的 instruction set，它不同於 Stack-based 的地方在於資料是從 registers fetch 而不是 stack，而每個 register 有它自己獨特的 address，這種性質讓 CPU 可以直接對 registers 存取資料，而不用藉由頻繁的 push/pop 動作來存取 stacks。虛擬機例子如: Lua, Dalvik, All modern Javascript engine

Ex: A = B * C

2-operands instruction

[opcode][輸出運算元得address][第一個輸入運算元的地址][第二個輸入運算元的地址]

MOV C, A ; C <- A (先儲存A的值)
MUL C, B ; C <- C*B

3-operands instruction

[opcode][輸出運算元得address][第一個輸入運算元的地址][第二個輸入運算元的地址]
MUL A, B, C

二、兩者比較

2-1. Instruction Dispatching

Instruction Dispatching 當得到當前要執行的指令的opcode（操作碼）之後，要跳轉到實現改操作碼的處理程序的動作。從記憶體讀取資料，並且跳到相對應的程式碼片段。

假如把解釋器核心看作一個FDX循環（fetch-decode/dispatch-execute loop），那麼最簡單的實現方式：

while (true) {
  byte opcode = get_next_opcode(); // fetch
  switch (opcode) {                // dispatch
  case Op_IADD:
    int y = pop_int();             // execute
    int x = pop_int();             //
    push_int(x + y);               //
    break;
  case ...
  }
}                                  // loop

switch-case的跳轉就是指令分派。

原始程式碼	Stack-based	Register-based
a = b + c	ILOAD c ILOAD b IADD ISTORE a	IADD a b c

Stack-based 需要四次的 instruction dispatching，而 Register-based 只需要一次 instruction dispatching。所以 Register-based 可以減少 instruction dispatching cost。

2-2. Accessing the operands

Register-based 的會將 operands 儲存在不同 registers，相對地 Stack-based 會將每次要運算的operands先存到stack，要運算時就會pop 出來交給 CPU 執行，而通常 Register-based 的 code size 會大於 Stack-based 的 code size，因為 Stack-based 只要記錄放置 operands 與 stack point 的相對位置並使用 push 和 pop 的指令，而 Register-based 必須明確記住 operands 放在哪個 register。Register-based 的 code 也會因此用到較多的 memory，這也是為什麼 Stack-based 的架構會如此受到 VM 的喜愛。

2-3. Performing the computation

在運算方面，Stack-based 的架構無法重複使用一些常用的 constants，相對地，若使用 Register-based 架構就可以解決這些問題，因為一旦將 value load 進 register 之後，便可以重複使用直到 method 結束。另外，Stack-based VM 常常會有頻繁的 memory push/pop，使用 Register-based VM 可以利用一些最佳化的技術，減少不必要的 memory load。如：Forward/Backward Copy Propagation Forward/Backward Copy Propagation 主要是用來消除一些不必要的 move 指令，它的原理是看前後幾個指令有沒有 dependency 的關係，例如下面的 4 行 source code

move r10, r1
move r11, r2
iadd r10, r10, r11
move r3 , r10

因為 第 1,2 行的 move 明顯是多餘的，因為不需要將 r1、r2 的資料搬到 r10、r11，而第 4 行的 move 也是同樣的意思，經過 Forward/Backward Copy Propagation 的步驟後可以簡化成下面的程式碼

iadd r3, r1, r2

2-4. Constant optimization

在 stack-based VM 無法將常用到的 constant 保存在 stack 中，但是 register-based VM 則可以預先 scan source code，並在程式執行一開始將一些可能會常用到的 constant 預先存放在某些 registers 中，這種作法可以減少多餘的 constant 的 load。

綜合以上，

	stack-based VM	register-based VM
Instruction Dispatching	多	少
Accessing the operands	記住operand和堆疊相對位址	要記住哪個 operand 放在哪個暫存器
Code Size	小	大
Memory 使用量	少	大
Performing the computation	頻繁的 memory push/pop	Copy Propagation
Constant optimization	無法將常用到的 constant 保存在 stack 中	可預先存放在某些 registers
instruction set	0 operand	2 or 3 operand

目前以 Register-based VM 最有效率，因為可以利用一些最佳化的技術減少不必要的資料搬移指令，但是 stack-based 也可以由 top-of-stack caching 進行最佳化資料搬移的成本。就實現來說，因為 Stack-based 不用暫存器的分配(不需要指定顯式暫存器)，所以開發來說相對 Register-based VM 更容易，且 stack-based 零指令(zero operand) 使程式碼更小，更緊湊，適合應用在資源有限的環境中。

就一句話總結， Register-based 用空間換時間，執行速度較快但程式碼指令size較大，Register-based 用時間換空間，程式碼指令size較小旦資料搬移時間較多。

• JVM (stack-based)

• Dalvik VM (register-based)

最後大推 虛擬機隨談（一）：解釋器，樹遍歷解釋器，基於棧與基於寄存器，大雜燴(推薦) (opens new window)，寫的真心不錯。

三、參考連結

1. NTU 的作業(從這篇來的) (opens new window)

2. Virtual Machine Showdown: Stack Versus Registers(很多文章參考這篇論文) (opens new window)

3. Virtual machine and javascript engine (opens new window)

4. registers vs stacks (opens new window)

5. Stack based vs Register based Virtual Machine Architecture (opens new window)

6. 虛擬機隨談（一）：解釋器，樹遍歷解釋器，基於棧與基於寄存器，大雜燴(推薦) (opens new window)

7. 棧式虛擬機和寄存器式虛擬機？ (opens new window)

8. 指令集架構 計算機也跟人類一樣 (opens new window)

9. Python stack VM (opens new window)

10. Stack-based 的虛擬機有什麼常用的優化策略？ (opens new window)

11. Why do VMs need to be “stack machines” or “register machines” etc.? (opens new window)