LuaJIT 2 beta 3 is out: Support both x32 & x64(为什么会如此快?)

LuaJIT's interpreter is fast, because:

•It's written in assembler.
•It keeps all important state in registers. No C compiler manages to do that on x86.
•It uses indirect threading (aka labeled goto in C).
•It has a very small I-cache footprint (the core of the interpreter fits in 6K).
•The parser generates a register-based bytecode.
•The bytecode is really a word-code (32 bit/ins) and designed for fast decoding.
•Bytecode decode and dispatch is heavily optimized for superscalar CPUs.
•The bytecode is type-specialized and patched on-the-fly.
•The dispatch table is patched to allow for debug hooks and trace recording. No need to check for these cases in the fast paths.
•It uses NaN tagging for object references. This allows unboxed FP numbers with a minimal cache footprint for stacks/arrays. FP stores are auto-tagging.
•It inlines all fast paths.
•It uses special calling conventions for built-ins (fast functions).
•Tons more tuning in the VM ... and the JIT compiler has it's own bag of tricks.
E.g. x=x+1 is turned into the ADDVN instruction. This means it's specialized for the 2nd operand to be a constant. Here's the x86 code (+ SSE2 enabled) for this instruction:

// Prologue for type ABC instructions (others have a zero prologue).
movzx  ebp, ah                  Decode RC (split of RD)
movzx  eax, al                  Decode RB (split of RD)

// The instruction itself.
cmp    [edx+ebp*8+0x4], -13     Type check of [RB]
ja     ->lj_vmeta_arith_vn
movsd  xmm0, [edx+ebp*8]        Load of [RB]
addsd  xmm0, [edi+eax*8]        Add to [RC]
movsd  [edx+ecx*8], xmm0        Store in [RA]

// Standard epilogue: decode + dispatch the next instruction.
mov    eax, [esi]               Load next bytecode
movzx  ecx, ah                  Decode RA
movzx  ebp, al                  Decode opcode
add    esi, 0x4                 Increment PC
shr    eax, 0x10                Decode RD
jmp    [ebx+ebp*4]              Dispatch to next instruction
Yes, that's all of it. I don't think you can do this with less instructions. This code reaches up to 2.5 ipc on a Core2 and takes 5-6 cycles (2 nanoseconds on a 3 GHz machine).

评论

17 楼 linkerlin 2010-04-15  

Lua的软肋还是在GC上。
我上次和LuaJIT的开发者聊，他说，目前的Lua C API导致无法更新GC.
指针被暴露啊。GC没法改进成 拷贝分代GC.

16 楼 mryufeng 2010-03-09  

RednaxelaFX 写道

mryufeng 写道

你说的是翻译源码还是opcode?

翻译opcode，将opcode翻译为machine instruction。

解释与翻译的界限有点模糊。
如果以是否进行native code generation来界定是编译还是解释，那么编译是做native code generation的，而解释不做。
如果以是否直接利用硬件支持来进行instruction dispatch来界定，那么编译后生成的代码是直接靠硬件来做instruction dispatch，而解释器是用自己写的代码来做。
但这些都不是特别的精确，到底界限在哪里我也没有见到过什么好的定义。总之从程度上说，趋近于解释执行的方式在得到运行结果前对程序预先做的分析和处理较少，而趋近于编译的方式正好相反，在得到运行结果前对程序做了较多的分析和处理。

这帖里的代码可以看到很明显的用于instruction dispatch的代码：

jmp  [ebx+ebp*4]    Dispatch to next instruction

而如果是通过硬件支持直接做instruction dispatch的话，dispatch本身就是隐含在每条机器指令中的。

这个肯定是这样的. 提升的地方就是原来lua vm的dispatch代码下岗了, 等价的native code上岗了.

jit的用处就是产生更好的等价代码...

15 楼 RednaxelaFX 2010-03-09  

mryufeng 写道

你说的是翻译源码还是opcode?

翻译opcode，将opcode翻译为machine instruction。

解释与翻译的界限有点模糊。
如果以是否进行native code generation来界定是编译还是解释，那么编译是做native code generation的，而解释不做。
如果以是否直接利用硬件支持来进行instruction dispatch来界定，那么编译后生成的代码是直接靠硬件来做instruction dispatch，而解释器是用自己写的代码来做。
但这些都不是特别的精确，到底界限在哪里我也没有见到过什么好的定义。总之从程度上说，趋近于解释执行的方式在得到运行结果前对程序预先做的分析和处理较少，而趋近于编译的方式正好相反，在得到运行结果前对程序做了较多的分析和处理。

这帖里的代码可以看到很明显的用于instruction dispatch的代码：

jmp  [ebx+ebp*4]    Dispatch to next instruction

而如果是通过硬件支持直接做instruction dispatch的话，dispatch本身就是隐含在每条机器指令中的。

14 楼 mryufeng 2010-03-09  

RednaxelaFX 写道

mryufeng 写道

wkoffee 写道

好像通篇都是intepreter，没有jit什么事

jit做什么的 不就是把lua opcode intepret成x86码吗 那你以为jit做什么的?

同样是翻译语言，有口译和书面译的区别；同样是执行程序，也有解释（interpret）与编译（compile）的区别。《虚拟机 系统与进程的通用平台》一书中指出一类加速虚拟机执行程序的方式就是“动态翻译”（dynamic translation），而在高级语言虚拟机中这一般就被叫做编译。
这帖中引用的资料确实只是讲了LuaJIT中的解释器部分。LuaJIT是混合执行模式的虚拟机，同时具有解释器与JIT编译器的部分。

你说的是翻译源码还是opcode?

13 楼 wkoffee 2010-03-09  

mryufeng 写道

wkoffee 写道

好像通篇都是intepreter，没有jit什么事

jit做什么的 不就是把lua opcode intepret成x86码吗 那你以为jit做什么的?

这个就是个用汇编写的解释器，用c写就是一个大的switch case,用汇编写就是一个dispatch table。

12 楼 RednaxelaFX 2010-03-09  

mryufeng 写道

wkoffee 写道

好像通篇都是intepreter，没有jit什么事

jit做什么的 不就是把lua opcode intepret成x86码吗 那你以为jit做什么的?

同样是翻译语言，有口译和书面译的区别；同样是执行程序，也有解释（interpret）与编译（compile）的区别。《虚拟机 系统与进程的通用平台》一书中指出一类加速虚拟机执行程序的方式就是“动态翻译”（dynamic translation），而在高级语言虚拟机中这一般就被叫做编译。
这帖中引用的资料确实只是讲了LuaJIT中的解释器部分。LuaJIT是混合执行模式的虚拟机，同时具有解释器与JIT编译器的部分。

11 楼 mryufeng 2010-03-09  

wkoffee 写道

好像通篇都是intepreter，没有jit什么事

jit做什么的 不就是把lua opcode intepret成x86码吗 那你以为jit做什么的?

10 楼 wkoffee 2010-03-09  

好像通篇都是intepreter，没有jit什么事

9 楼 mryufeng 2010-03-08  

多谢指教 跟你学了很多东西! 俺是你的粉丝哦...

8 楼 RednaxelaFX 2010-03-08  

mryufeng 写道

我记得1.x就有呀 根据代码的hot度 来加速的 不知道是不是叫 trace compiler, 时间长了 记得不太清楚了...

adaptive compilation跟trace compilation不是同一种概念。根据代码热的程度做不同程度优化的是adaptive compilation；以trace为单元（相对于其它编译单元，例如函数/方法为单元）来编译的是trace compilation ^_^

7 楼 mryufeng 2010-03-08  

RednaxelaFX 写道

mryufeng 写道

lua 1.x的时候就只有trace compiler技术是个亮点.印象最深的是dynasm. 2.0的变化太大了 一下子就爆发出来了...

LuaJIT 1.x貌似没有用trace compiler，JIT编译的方式就是很常见的以函数为单位的。在2.0才开始转用trace compiler。用了trace compiler最有名的大概是TraceMonkey了吧，很多人都应该听说过这个；Android的Dalvik里的JIT也有用；其它一些研究性质的VM也有用，不过还不是很普及。

我记得1.x就有呀 根据代码的hot度 来加速的 不知道是不是叫 trace compiler, 时间长了 记得不太清楚了...

6 楼 RednaxelaFX 2010-03-08  

mryufeng 写道

lua 1.x的时候就只有trace compiler技术是个亮点.印象最深的是dynasm. 2.0的变化太大了 一下子就爆发出来了...

LuaJIT 1.x貌似没有用trace compiler，JIT编译的方式就是很常见的以函数为单位的。在2.0才开始转用trace compiler。用了trace compiler最有名的大概是TraceMonkey了吧，很多人都应该听说过这个；Android的Dalvik里的JIT也有用；其它一些研究性质的VM也有用，不过还不是很普及。

5 楼 mryufeng 2010-03-08  

lua 1.x的时候就只有trace compiler技术是个亮点.印象最深的是dynasm. 2.0的变化太大了 一下子就爆发出来了...

4 楼 RednaxelaFX 2010-03-08  

啊，上面码字的时候被打了个岔写漏了……我是想说标记为红色的是Strongtalk与HotSpot也有的特性，而绿色的是Strongtalk中存在但HotSpot中没有的特性——因为Java（早期被认为）不需要tagged pointer

3 楼 RednaxelaFX 2010-03-08  

mryufeng 写道

LuaJIT's interpreter is fast, because:

•It's written in assembler.
•It keeps all important state in registers. No C compiler manages to do that on x86.
•It uses indirect threading (aka labeled goto in C).
•It has a very small I-cache footprint (the core of the interpreter fits in 6K).
•The parser generates a register-based bytecode.
•The bytecode is really a word-code (32 bit/ins) and designed for fast decoding.
•Bytecode decode and dispatch is heavily optimized for superscalar CPUs.
•The bytecode is type-specialized and patched on-the-fly.
•The dispatch table is patched to allow for debug hooks and trace recording. No need to check for these cases in the fast paths.
•It uses NaN tagging for object references. This allows unboxed FP numbers with a minimal cache footprint for stacks/arrays. FP stores are auto-tagging.
•It inlines all fast paths.
•It uses special calling conventions for built-ins (fast functions).
•Tons more tuning in the VM ... and the JIT compiler has it's own bag of tricks.

标为红色的那些在Strongtalk里也是如此。
Strongtalk中有自己实现的汇编器，其解释器是通过代码控制汇编器在启动VM时生成出来的，也可以认为是“用汇编写的”。
它也是用indirect-threading（或者说token-threading），跟LuaJIT 2不同的是它的指令的操作码是字节码（只占8位）。
Strongtalks的字节码是基于栈的指令集，但通过“栈顶缓存”优化（top-of-stack caching）它比基于寄存器版本的同类实现只慢一点（而占用的内存空间小一些）。
Strongtalk也用tagged pointer来直接在指针里存放小整数等对象的值，减少了GC的压力。
Strongtalk也对直接调用VM内部函数有优化。

而Strongtalk是1994年到1996年在做的，后来则演化进了HotSpot里，将一些Java用不到的动态特性去除了，解释器稍微简化了些并且更快了。这些都并不是特别新的技术了，不过除了几家大厂的JVM外，其它VM就在近两三年才开始慢慢跟上时代的步伐……
看看HotSpot的解释器的一张截图：http://rednaxelafx.iteye.com/picture/52954
也是非常简洁的……

LuaJIT比较新的部分是它的trace compiler。这种技术现在只在很少的VM中得到了应用。

另外：打个广告，之前在JavaEye开了个高级语言虚拟机的圈子，欢迎来讨论相关话题。这帖就很合适，哈哈～

2 楼 dennis_zane 2010-03-08  

高科技，太牛了

1 楼 mryufeng 2010-03-08  

真牛B的技术!!!