Stack-based 的虛擬機有什麼常用的優化策略？

01-06

1. 虛擬機實現的是CIL (Common Intermediate Language) ;
2. 一個stack slot的數據結構如下：

struct value { int type; // tag union { int32_t as_i32; int64_t as_i64; double as_f64; // ... } v; };
3. 解釋執行.

R大最近很忙（R大懂的），小弟試著基礎地幫他回復一下吧。

通常一個解釋器，不管是stack-based還是register-based常見的開銷有如下三個部分：

指令分派(instruction dispatch)
讀取操作數(operand accessing)
對操作數進行相應的指令計算(computation)

對於指令分派來說，兩種VM指令設計都是一樣的。對於第二部分而言，相對於register-based VM，stack-based VM中的操作數多半放在內存棧中。現代CPU對這種非常局部的內存訪問的的優化已經非常非常好，延遲甚至到了可以忽略不計的地步。故在性能上兩都相差應該不大。而對於第三部分的指令計算，通常每個虛擬機指令都非常簡單，所以它常常是整個解釋過程中開銷最小的一部分（這也是為什麼JIT編譯可以極大地提高性能）。

故在設計的解釋器時，使用哪種結構(stack-based還是register-based)對單純的解釋器的性能影響並不大，它的影響可能更多在於虛擬指令的長度，數量和程序的大小上。具體內容可以參考R大的相應回答。（edit)但是實際上，Anton Ertl et al.等將基於棧的位元組碼轉換成基於寄存器的位元組碼之後發現，同樣的程序指令數量減少了約一半，執行時間減少了約三分之一到四分之一之間，但是程序長度增加了四分之一。(Shi et al. "Virtual Machine Showdown: Stack Versus Registers")。所以說，兩者的性能是有區別的，但是對解釋器解釋單條指令的性能來說，兩者差別不大。

故這篇回答可能只會針對於指令分派講解，因為它通常是解釋器中開銷較大的一環。

實現指令分派的最簡單的方法是用switch語句：

switch (opcode) { case IADD: executeIADD(op1, op2); break; case ILOAD: executeILOAD(op1); break; ... default: assert(false); }

但是switch指令的優化是一件很頭疼的事情：switch通常被翻譯成跳錶(jump table)，因為解釋器的switch通常有非常多的case，CPU執行時做跳轉地址預測（jump target prediction）時不知道應該選擇哪個目標地址跳轉，效果奇差，成了最大的性能瓶頸。

一種改進是把executeIADD/executeILOAD這樣的函數入口地址當成是opcode，那麼每條指令都自帶了解釋本指令的方法，在執行一條指令的時候其實是直接從指令的opcode中找到與其相對應的解釋函數。這樣執行的方式就變成了call threading：

void executeIADD() {...} void executeILOAD() {...} void interpret_function(void **program, void *sp) { opcode = start_opcode_address; while(true) { (*opcode++)(); } }

這樣的改變免去了switch語句生成的跳轉表。注意到每條指令我們都要調用函數，對於指令分派這一步驟來說，性能的瓶頸還是在函數調用上面。將這些函數調用全部內聯，就是現代解釋器最常用的優化手段: threading了。

void interpret_function(void **program, void *sp) { void **pc = program; goto **pc; _iadd: int a = pop(sp); int b = pop(sp); push(sp, a+b); goto **(++pc); _iload: ... }

對每一個指令來說，在解釋執行完的末尾都有++PC的操作，實際上是將call threading中的opcode++分配到了每一個解釋函數裡面，注意到這其實是用了CPS（continuation passing style）這種編程範式（聽上去好像很牛逼！但是然並卵已經過時了）。對CPU來說，雖然還是要做一次跳轉(indirect jump)，但是我們已經知道跳轉目標地址存放在哪個變數（寄存器）中，因此硬體對這種跳轉結構的預測遠比跳轉表要準確得多。（想要了解threading更多的，請閱讀Anton Ertl的Stack caching for interpreters PLDI"95，或者Virtual Machines: Versatile Platforms for Systems and Processes這本書）。

當然，如果想要更進一步地提高性能，就可能需要JIT了。一個簡單的做法是使用模板JIT （templating JIT），即對應一個虛擬指令，固定生成對應的機器指令序列。實際上這樣做相當於把解釋的過程緩存起來了，對於一個stack-based VM來說實現也非常簡單。如果機器的budget足夠，這也許是最快速的解釋方法了。

我聽說過的優化有「Top-of-Stack Cashing」和「Computed goto」。還可以把stack-based位元組碼轉化為register-based。建議後端用LLVM，這樣就不需要處理複雜的事情了。