栈式虚拟机和寄存器式虚拟机？

前面有回答提到了俺的老文：

俺就王婆卖瓜自己也发一次吧。

备注：本回答全文原创，未经许可不允许转载。特别不允许清华大学出版社以任何形式转载本文。此备注背景请参考：

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

太长不读（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的

演讲里，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文件应用了类似的压缩思路：

格式。它也是把JAR包里的所有Class文件的常量池汇总为一个，以此压缩掉其中的冗余。以pack200格式打包的Java应用就不会比用Dex格式打包大了。

之前在Oracle的HotSpot JVM组工作时，跟同事们讨论一些与此相关的话题，大家的共识是如果JVM的指令集是在20年后的今天设计的话，很有可能也会跟现在的潮流相似，基于寄存器。不过就算保持现在这样用基于栈的指令集也挺好。

目前Class文件/JAR文件的真正让大家头疼的问题并不是基于栈还是基于寄存器的设计，而是别的地方，例如：

Class文件方面：

• 各种人为的大小限制都跟不上时代了，例如每个方法的字节码最多65535字节；
• 要生成StackMapTable太闹心；
• 常量池的组织方式不便于直接从文件映射到内存然后高效执行；可以有更高效的组织方式。

JAR文件方面：

• 如前文提的，多个Class文件之间的常量池冗余；
• 缺少带有强语义的描述模块的信息；
• 等等…

一切都有待未来版本的Java继续改进。

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

Lua的选择

官方版Lua的设计可以从经典文章

一窥究竟。

它提到：

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编译器，也还是想让解释器尽量快的心情也是可以理解的。