棧式虛擬機和寄存器式虛擬機？

01-05

這兩者究竟有什麼大的區別？為什麼JVM是基於前者，Lua是後者呢？是因為作者當初自己按喜歡決定？還是另有原因？

前面有回答提到了俺的老文：虛擬機隨談（一）：解釋器，樹遍歷解釋器，基於棧與基於寄存器，大雜燴

俺就王婆賣瓜自己也發一次吧。

備註：本回答全文原創，未經許可不允許轉載。特別不允許清華大學出版社以任何形式轉載本文。此備註背景請參考：http://www.douban.com/doulist/42057979/

===========================================

太長不讀（TL;DR）版定性分析：

對於解釋器來說，解釋器開銷主要來自解釋器循環（fetch-decode/dispatch-execute循環）中的fetch與decode/dispatch，反而真正用於執行程序邏輯的execute部分並不是大頭。每條指令都要經歷一輪FDX循環。因而減少指令條數可以導致F與D的開銷減少，於是就提升了解釋器速度。

基於棧與基於寄存器的指令集，用在解釋器里，籠統說有以下對比：

從源碼生成代碼的難度：基於棧 &< 基於寄存器，不過差別不是特別大
表示同樣程序邏輯的代碼大小（code size）：基於棧 &< 基於寄存器
表示同樣程序邏輯的指令條數（instruction count）：基於棧 &> 基於寄存器
簡易實現中數據移動次數（data movement count）：基於棧 &> 基於寄存器；不過值得一提的是實現時通過棧頂緩存（top-of-stack caching）可以大幅降低基於棧的解釋器的數據移動開銷，可以讓這部分開銷跟基於寄存器的在同等水平。請參考另一個回答：寄存器分配問題？ - RednaxelaFX 的回答
採用同等優化程度的解釋器速度：基於棧 &< 基於寄存器
交由同等優化程度的JIT編譯器編譯後生成的代碼速度：基於棧 === 基於寄存器

因而，籠統說可以有以下結論：要追求

盡量實現簡單：選擇基於棧
傳輸代碼的大小盡量小：選擇基於棧
純解釋執行的解釋器的速度：選擇基於寄存器
帶有JIT編譯器的執行引擎的速度：隨便，兩者一樣；對簡易JIT編譯器而言基於棧的指令集可能反而更便於生成更快的代碼，而對比較優化的JIT編譯器而言輸入是基於棧還是基於寄存器都無所謂，經過parse之後就變得完全一樣了。

===========================================

JVM的選擇

JVM當初設計的時候非常重視代碼傳輸和存儲的開銷，因為假定的應用場景是諸如手持設備（PDA）、機頂盒之類的嵌入式應用，所以要代碼盡量小；外加基於棧的實現更簡單（無論是在源碼編譯器的一側還是在虛擬機的一側），而且主要設計者James Gosling的個人經驗上也對這種做法非常熟悉（例如他之前實現過PostScript的虛擬機，也是基於棧的指令集），所以就選擇了基於棧。

回頭看，這個決定也還算OK，可惜的是基於棧的設計並沒有讓Java的代碼傳輸大小減小多少。

這是因為：Java代碼是以Class文件為單位來傳輸與存儲的。Java從設計之初就非要支持分離編譯（separate compilation）與按需動態類載入（on-demand dynamic class loading），導致Java的Class文件必須獨立的（self-contained）——每個Class文件必須自己攜帶自己的常量池，其主要信息是字元串與若干其它常量的值，以及用於符號鏈接的符號引用信息（symbolic reference）。

如果大家關注過Class文件的內容的話，會知道其實通常Class文件里表示程序邏輯的代碼部分——「位元組碼」——只佔Class文件大小的小頭；而大頭都被常量池佔了。而且多個Class文件的常量池內容之間常常有重疊，所以當程序涉及多個Class文件時，就容易有冗餘信息，不利於減少傳輸/存儲代碼的大小。

大家或許還記得Google在Google I/O 2008的Dalvik VM Internals演講里，Dan得意的介紹到Dalvik的Dex格式在未壓縮的情況下都比壓縮了的JAR文件還小么？

（下面數據引用自演示稿第22頁）

common system libraries
(U) 21445320 — 100%
(J) 10662048 — 50%
(D) 10311972 — 48%
web browser app

(U) 470312 — 100%
(J) 232065 — 49%
(D) 209248 — 44%
alarm clock app
(U) 119200 — 100%
(J) 61658 — 52%
(D) 53020 — 44%
(U) uncompressed jar file

(J) compressed jar file
(D) uncompressed dex file

Dan準確的介紹了Dex體積更小的原因：一個Dex相當於一個或多個JAR包，裡面可以包含多個Class文件對應的內容。一個Dex文件里的所有Class都共享同一個常量池，因而不會像Class文件那樣在多個常量池之間有冗餘。這樣Dex文件就等同於在元數據層面上對JAR文件做了壓縮，所以前者比後者更小。

但是很明顯後來有不少群眾不明就裡，以為Dalvik的Dex文件更小是跟基於寄存器的選擇相關的——其實正好相反，在位元組碼部分，Dalvik的位元組碼其實比JVM的位元組碼更大。只要仔細讀了同一個演示稿就會看到

（第37頁）

The Register Machine

30% fewer instructions

35% fewer code units

35% more bytes in the instruction stream

but we get to consume two at a time

而其實Java世界裡早就發現了這個問題，並且有一個傳輸/存儲格式跟Dex文件應用了類似的壓縮思路：pack200格式。它也是把JAR包里的所有Class文件的常量池匯總為一個，以此壓縮掉其中的冗餘。以pack200格式打包的Java應用就不會比用Dex格式打包大了。

之前在Oracle的HotSpot JVM組工作時，跟同事們討論一些與此相關的話題，大家的共識是如果JVM的指令集是在20年後的今天設計的話，很有可能也會跟現在的潮流相似，基於寄存器。不過就算保持現在這樣用基於棧的指令集也挺好。

目前Class文件/JAR文件的真正讓大家頭疼的問題並不是基於棧還是基於寄存器的設計，而是別的地方，例如：

Class文件方面：

各種人為的大小限制都跟不上時代了，例如每個方法的位元組碼最多65535位元組；
要生成StackMapTable太鬧心；
常量池的組織方式不便於直接從文件映射到內存然後高效執行；可以有更高效的組織方式。

JAR文件方面：

如前文提的，多個Class文件之間的常量池冗餘；
缺少帶有強語義的描述模塊的信息；
等等…

一切都有待未來版本的Java繼續改進。

===========================================

Lua的選擇

官方版Lua的設計可以從經典文章 The Implementation of Lua 5.0 一窺究竟。

它提到：

For ten years (since 1993, when Lua was first released), Lua used a stack-based virtual machine, in various incarnations. Since 2003, with the release of Lua 5.0, Lua uses a register-based virtual machine.

也就是說Lua 5.0之前的Lua其實是用基於棧的指令集，到5.0才改為用基於寄存器的。

接下來：

Register-based code avoids several 「push」 and 「pop」 instructions that stack-based code needs to move values around the stack. Those instructions are particularly expensive in Lua, because they involve the copy of a tagged value, as discussed in Section 3. So, the register architecture both avoids excessive copying of values and reduces the total number of instructions per function. Davis et al. [6] argue in defense of register-based virtual machines and provide hard data on the improvement of Java bytecode. Some authors also defend register-based virtual machines based on their suitability for on-the-fly compilation (see [24], for instance).

所以Lua 5.0開始改為選用基於寄存器的指令集設計，主要是出於 (1) 減少數據移動次數，降低由數據移動帶來的拷貝開銷，和 (2) 減少虛擬指令條數這兩點考慮。

從純解釋器的角度看，這兩點考慮是非常合理的。

不過如果官方版Lua有JIT編譯器的話，它就沒必要這麼做了——基於棧和基於寄存器的指令集只要經過合理的編譯，得到的結果會是一模一樣的。

至於LuaJIT，

LuaJIT 1.x的位元組碼設計源於Lua 5.1.x系列，因而也是基於寄存器的；

LuaJIT 2.x系列的位元組碼雖然重新設計了，但應該還是受到之前設計的影響而繼續採用了基於寄存器的設計。像Mike Pall那種想榨乾一切性能的思路，即便有優化的JIT編譯器，也還是想讓解釋器盡量快的心情也是可以理解的。

探索Lua5.2內部實現:虛擬機指令(1) 概述

RednaxelaFX 的回答很好，這裡補充一些。雖然不做虛擬機好久了，但是從目前跟蹤的論文和項目情況看，應該知識沒有太過時，畢竟hotspot以後虛擬機發展不多。

基於棧的代碼在hotspot虛擬機代碼優化時候會帶來一些麻煩，主要是引入不必要的數據依賴。這些依賴，hotspot運行時間優化比較難辨識，不像基於寄存器的代碼，數據依賴比較少，運行時間優化自由度大。
基於棧的實現也簡單，intel x86架構早期的數學處理器x87就是基於棧的，只操作棧頭的兩個數據。但是實際實現已經早就不用這種架構，如果你看編譯器生成的浮點代碼，也是更多用SSE指令來做浮點運算了。

自問自答一下先，發現了虛擬機隨談（一）：解釋器，樹遍歷解釋器，基於棧與基於寄存器，大雜燴這個好文，我先慢慢看，若大家想回答，無任歡迎