« 平安夜借机玩了一下 | 返回首页 | 基础不等于简单 »

虚拟机之比较,lua 5 的实现

前段把自己的虚拟机和编译器完成后,曾经和 lua5 做过一个比较。比较的结果很沮丧,我的虚拟机只能达到 lua 5 一半多点的速度。所以很不服气的又读了一段 lua5 的源码。而之前我是一段一段的看 lua source code 的,甚至 lua 4 和 lua5 的是在不同时期去读的,当然我也知道其间巨大的不同。

其实,对于简单程序来说,我的虚拟机是有速度优势的,而且比 lua 快很多,我把它归咎于 coding 的技巧。但是在设计方向上却败下阵来。因为 lua 5 早已经是基于寄存器的虚拟机了,而我还在用基于堆栈的虚拟机。虽然我对其做了改良,向基于寄存器方向做了靠拢,但是还是不如纯粹的寄存器虚拟机。

最近几天仔细考虑了基于寄存器的虚拟机的实现难度,虽然自己也可以继续干,但是目前项目很紧,决定先缓一阵子,多来点思考沉淀吧。

今天休假,读了一些信箱里订阅的 lua maillist ,想看看 lua 5.1 到底做了些啥改动。由于最近自己做了好些类似的工作,更容易对 lua 的进展去理解了。最后发现,lua 的改进集中在 GC 上面。这点很合我意,其实我自己实现的东西,最得意的莫过于 gc,绝对是优于 lua 的。lua 现在在做分代 gc ,我在考虑并行的方案。大约都是为了解决 gc 的一些个头痛的东西。不过 lua 的 gc 终究不是内存整理的,在受限内存环境下,表现相对不是特别好。另外,lua 为了最求速度等,在深层次递归的支持上也有些问题,会导致堆栈满。我曾经写过一个用递归算数列和的程序,递归层次过深,lua 就处理不了了,我的虚拟机是可以胜任的。当然这对一般的应用都不是问题。

毕竟 lua 发展了 10 多年,可以借鉴的东西实在太多了。我那区区三周的玩具就当是练手的开始吧。今天仔细读了一遍 <a href="http://www.tecgraf.puc-rio.br/~lhf/ftp/doc/sblp2005.pdf">the implementation of Lua 5.0</a> ,如果有人对脚本语言实现有同样的兴趣,推荐阅读。

从这个 paper 中我们可以了解几件事情,虽然通过读源码也可以了解(我就是先通过阅读源码的)但是读这个可以更休闲一些。

lua5 已经是完全 Register-based virtual machine ,可以说是世界上第一个被广泛应用的register-based 脚本虚拟机了。这点,现在的 Java JVM 还有 .NET 都还是 Stack-based 。据说 perl6 打算做成 Register-based 了 :) 当然我的语言也有此计划 ,呵呵。Registere-based 虚拟机相对难写,看来是个挑战。

lua5 优化了 table 的实现,这点我前面的 blog 里提到过,这篇 paper 也做了详细阐述。

lua5 增加了 coroutine 的实现,这点我考虑过,自从我把自己的虚拟机改成系统堆栈无关后,做多几个 thread 无非创建多一个堆栈而已,不难实现。 lua5 的 coroutine 也是每个 thread 有独立堆栈的。(实际上有两个堆栈)

lua 也是一个one-pass 的基于递归下降算法的 compiler ,paper 中提到,one-pass 的 compiler 是 hard-written 的,这点我是深有体会啊。写 compiler 那几天,脑子里翁翁乱叫,写了两整天不敢向仓库提交一行代码。不过写出来的好处是显而易见的,就和 paper 里说的一样,smaller, more efficient, more portable, and fully reentrant :)

前几天在想,一个弱类型的语言,Object 的描述信息能不能比 lua 这种更小。lua 用了一个独立的字描述类型,然后用 union 来存放不同类型的数据,这个也是我用的方法。前几天想了个办法,那就是一般指针由于对齐的原因,末两位永远都是 0 。(如果我们以 8 对齐的话,末三位都是 0)这样就有点额外的信息来保存数据类型了,整数可以用 30 或 31bit 来表示都是够的。

今天读这篇 paper 发现前人已经用过了,比如 Smalltalk80 ,不过 paper 解释了 lua 不这样做的原因。当然,我自己的语言倒是可以一试的 :)

至于 lua5 用的指令集,每个 instruction 只用 4 个字节,其实现方法还是很巧妙的,这个前几天读源码的时候已经领教过了。当时我想找到我的语言的速度究竟慢在哪里,才发现是循环中, i=i+1 这样的操作。基于寄存器的虚拟机自然可以运行的更快了。而且我的虚拟机的 instruction 是 8 字节的,而 lua 却只用 4 字节,数据短了,效率也能提高。

读完这篇 paper 感觉很多地方 lua 都是鄙视 python 的低效 :) 这点跟我在 GDC2004 上参加的 lua round table 的感觉一样,一下就可以发展成 lua 和python 的"派系斗争" :) 我想 GDC2006 上 lua 派会更理直气壮一些,毕竟两年前用 lua4 的人远不如 lua5 的人,(我发言的时候特地让用 lua5 的人举了次手 :) 这次随着 lua 5.1 的 release ,lua在游戏行业中的地位将不可动摇了。

随便提一下 LuaJIT ,感觉是个有前途的 project
<a href="mailto:http://luajit.luaforge.net/">http://luajit.luaforge.net/</a>

Comments

我觉得设计的理念必须是基于设计目标的,很难出现面面俱到的高大全设计,因此定位很重要,定位也很困难。动态语言提高效率是有意义的,但效率并不是动态语言第一位的追求,否则为什么要用动态语言呢,lua的定位和python的定位是不同的,所以实现策略也是不同的,这个没什么好类比的,对它们各自的设计目标来说,它们都是优秀的。
所有,有时候设计的难点不在于技巧,而在于决策,决策的难点在于清晰的定位和合理的划定范围。

double占8个字节,在32位机器上可以用一个特殊的double来编码其它的TValue
http://hi.baidu.com/pcall/blog/item/c83d917f5ae4003e0cd7dafe.html

我做游戏也在自己设计指令集和虚拟机,有机会能探讨一下。

也来凑两句。

采用RB的虚拟机,编译的工作量是大一些,主要原因是虚拟寄存器的合理分配,云风以前好像也指出过。要实现虚拟寄存器的合理分配,邻近的虚拟指令的operand需要无缝地吻合起来,这点是有点复杂。

Roberto关于手写编译器的原因还是蛮合理的。另外我估计使用yacc/bison之类的工具,比较难合理的分配虚拟寄存器。

Roberto 大大的解释:

- Better control over code quality. The skeletons from yacc/bison
frequently use system #ifdefs, malloc.h, etc.

- Better control over static and extern variables. We were already
planning "stateless Lua".

- Possibility of using the C stack to hold some data structures. For
instance, with nested functions, we need one structure (with lots of
fields) for each function being compiled. With a recursive descendent
parser, it is trivial to allocate them as local variables. (To use
dynamic allocation for them is tricky, because in case of errors we must
be able to free them correctly...)

- Better error messages.

On the other hand, the syntax of Lua was already quite stable, so one of the
main advantages of yacc (easy of change) was not that important.

http://lua-users.org/lists/lua-l/2002-03/msg00035.html

不过写出来的好处是显而易见的,就和 paper 里说的一样,smaller, more efficient, more portable, and fully reentrant :)

--- 再纸上谈兵一把:
从算法上来讲,我看不出手写的代码有什么可能比基于LALR文法的,基于状态机的编译器更为快捷的。在这种基于有限状态机的编译模型中,整个编译的速度几乎就没有什么冗余的操作。而且无论是源代码的清晰程度也远高许多啊。所以,这点,我对云风的论点不敢苟同。

我对虚拟机和编译也是很感兴趣,不过,一向是只读不动手。所以,我的观点纯粹是纸上谈兵。

关于register based/stack based,我的感觉是,对于脚本语言而已,采用RB,那么编译器(从源代码到字节吗),编译器的工作量会大很多,而且字节码本身相对来说会更为复杂一些。而已,从RB的字节码向机器码进行JIT我觉得也会相对简单一些,毕竟RB的模型和CPU的寄存器模型是相近的。而SB则对编译器是非常简化的,但对JIT的要求就相对复杂一些,需要再次将SB转移到RB上去(不过,这种转换基于数据流的分析是完全可行的)。

因此,从理论上说,RB与SB是等价的,如果纯粹采用解释的方式(没有JIT),那么RB的优势会明显一些,因为在RB中,指令数目明显会减少。但采用JIT模式时,则2者不会有本质的差别。Java的做法还是相当聪明的,将优化的工作集中到JVM中,使得Bytecode和编译器的工作大大简化,这样,至少使得产生一个新的语言编译器(将新的语言编译成bytecode)大大简化了。

确实开发程序语言最难的大概就是能否坚持下来。有不少语言都是开发到了一定程度就因为某些原因半途而废,比较可惜。

我也写了一个编译器+VM,虽然速度没有LUA快,但功能丝毫不逊色于它。
平时工作较忙没有时间和心情深入研究,可惜

看到有不少人还在下载那个将近一年前的版本,正好我今天又做了一次道语言的新发布,因此,我再贴上些新的链接:

dao-devel-2007-04-09:
http://downloads.sourceforge.net/daoscript/dao-devel-2007-04-09.tar.bz

文档:
http://xdao.org/weblet.dao?WIKI=document&LANG=en

与一年前的版本相比,现在的版本增加了不少比较酷的特性:如基于消息传递的同步与分布式计算,灵活的宏系统,支持与C语言的混合编程(使用TCC),支持变量类型的显式和隐式声明以及类型推断等。

只可惜道语言的中文文档的更新还没有跟进。只好让感兴趣的朋友将就一下凑合着看;-)

初步完成的道语言虚拟机。感兴趣的朋友可以去试试。不过由于这个虚拟机是短期内开发出来的,难免有很多BUGS和疏漏,而且有些部分尚未完全完成,要有一点心理准备:-)

http://www.xdao.org/chinese/daovm_2006_04_22.tar.gz

学习虚拟机的开发在哪些方面有实用性,比如在游戏开发方面的应用,请云风不吝赐教

我的看法跟前面那位匿名兄弟刚好相反。我以前看基于stack的虚拟机模型时,觉得太多的push,pop会使得虚拟机效率不高(大概也有些误解吧),因而没去尝试将我自己开发的脚本语言的解释器(基于语法树)实现为虚拟机。

前段时间看了下Lua5的实现文档,便觉得基于寄存器的虚拟机模型应该比较高效,并开始着手将我的解释器改为这种模型的虚拟机。十天下来,已基本完成算术运算条件循环控制等基本的东东。我昨天做了个简单的测试,发现这个新的虚拟机比我以前那个解释器快了近3倍!现在它比Perl5快了很多,但还比Lua5慢一点。我相信在虚拟机模型下,添加其他特性时不会损害已实现特性的性能。

虚拟机的寄存器确实就是内存。但如果你仔细研究这种虚拟机的三元操作指令模型,你会发现这种指令的表达能力很强。从脚本编译出来的指令数目,基于寄存器的要比基于栈的少很多。我觉得这是它的效率的根本来源。

这位兄弟关于register-base的虚拟机的函数调用的看法是不准确的(具体可参看Lua5的CALL指令http://luaforge.net/docman/view.php/83/82/ANoFrillsIntroToLua5VMInstructions.pdf)。
简单说,在register-base的虚拟机中,函数调用时,参数是由CALL直接从调用者的register空间拷贝到被调用者的register空间,这里并不需要额外的指令。

lua 的效率之高,是被公认的。如果你有所疑虑的话可以多读一些源码。并且做一个实际的评测。

虚拟机和实际机器的模型不太一样,从你的言论中可以看出你对其实现并不太了解。所以建议还是自己读一下代码,这样比我来解释我自己的结论更有效率。

继续
如果解释器执行函数调用,stack-base会将参数的结果逐一直接保存在堆栈中了,而register-base还需要指令将参数值从寄存器中转移到函数调用堆栈中。
本人觉得register-base并不适合复杂的解释器。

很高兴兄弟回复,不过继续提问
"
在 register base 的环境中是
mov C,A
add C,B
"
请为add C,B中B为何物?
只有当B是立即数(常量时)此写法才可以减少一条指令。如果是变量,那还不是需要一条指令用于获得B。同样如果Stack-base解释器增加一条OP_AddConst也可以达到同样目的。
本人觉得Lua的执行效率并不会太高,好像在每条运算指令的执行过程中都要判断数据的类型。
我仔细分析了Netscape的JavaScriot


计算 C=A+B 在 stack base 的环境中通常是这样做的。

push A
push B
ADD
pop C

在 register base 的环境中是

mov C,A
add C,B

或者

add C,A,B (lua5 的 VM 是这种三元操作的)

VM 解释单条指令的时间可以看成类似时长的,register base 的 VM 可以用更少的指令数完成任务。

Lua 5中的register还不就是内存,我看不出比statck有任何速度方面的优势

没有用过,了解一下

不比不知道,一比吓一跳。没想到Lua这么快。比我写的DAO脚本语言http://www.xdao.org快好多。我以前只简单地跟PERL和PYTHON比较过,结果是跟PERL差不多或慢一点(取决于编译方式),比PYTHON快,因此觉得可以满意了,没想去更进一步优化。看来还得好好优化一下。不过肯定也快不到LUA这个程度,毕竟DAO比LUA复杂很多。

DAO脚本的执行是基于语法树,我以前没仔细研究过虚拟机模型,也一直对虚拟机的效率心存疑虑。看了The Implementation of Lua 5.0之后才发现虚拟机确实可以实现的很高效。不过有些语言特性似乎在虚拟机模型里实现起来很困难,比如:string[ id1 : id2 ] = "another_string"将string中从下标id1到id2的子串由赋值的方式替换为"another_string"。我当初为了支持这个语法并保持适用于Native多线程,很费了一番脑力。

不过我还是会好好研究一下LUA,说不定我也会将DAO改为由虚拟机执行,如果在保持DAO的语法上可行的话。

如果谁有虚拟机方面的电子资料,能否发给我(phoolimin AT gmail DOT com)?先谢过了。

Register-based的脚本解释的确是比Stack-based的困难很多,尤其在VM里,Registers的数目可以做到很多,这种情况下如何充分利用这些Register(高效地分配寄存器)也是对传统编译原理提出的新课题.情况有些类似基于RISC CPU的COMPILER...当然效率优势也是显而易见的.

我的Blog里面有详细的测试结果,是用单位时间的。我有测试的程序(EXE)执行结果显示的是单位时间,如果你需要我eMail给你,因为我没有地方用来放用来下载的连接。
BLOG(http://spaces.msn.com/members/gamedeveloper)

放假结束,嘿嘿,来看看。也帮着测试了下,我是讯持1.5G的cpu local比global要快4倍以上 int 比 double快 但也就几十个百分点 不会超过很多 没奔腾D那么多 不过我觉得这个应是正常的现代cpu架构double不应该比int快太多 不知道奔腾D何以如此反差大 因为云风是给的时间单位不大好对比真实性能 我的机器跑那个global的大概4秒多 我看janhail大概是3秒多

还有个奇怪的问题
while i<100 do
local e
if a > b then
e = a
else
e = b
end
a = e * c
if a==0 then
s = (s * 28586 + 85219835) / 8131
b = s
else
b = d / a
end
i = i + 1
end
看那个local e的申明 如果将申明放在local e = a处在int方式下运行不正常,而这个申明是影响性能的在double方式下local e = a要比单独local e要快一倍,这样实际上已经超过int方式下local e的速度,因为int下local e = a 没法进一步比较了。还有把local e提出循环会快一点,呵呵,这个就要靠程序员了,one-pass是没法子把这个做预处理的吧。所以one-pass要求的不仅仅是做编译器的技术人员,也要求应用这个编译器的技术人员,在one-pass的前提下编译器级的代码优化就没法实现了。

我的CPU是AMD32的。如果测试结果正确,那就说明LUA数值为double类型的时候AMD的机器比Inter的机器最少快4倍。你的同事有没有AMD的机器,可以再试验一下,我们这里当初配机器的时候只分Inter和AMD配,没有配不同型号的AMD和Inter。或者coder也试一下?我只是感到太奇怪了

你发给我的程序跟我自己测的结果相同,大约整数可以比double快3到4倍。

我是 intel 双核的 CPU ,最近从某 intel 朋友那里得到的传言,intel 的技术已经开始跟不上 AMD 了。

amd64?

:) 评论之前,请看请我的留言先。我说对Lua不重要指的是性能方面,而不是程序的正确性。如果说程序的正确性不重要的话,那就是一个joke了:)

我也感到很奇怪,我那我同事的机器(Inter的CPU)试验,int确实比double快很多,好像正确了。但是关键的问题是,在AMD的机器上double速度比int还快一点点。这就意味着AMD的机器的double比inter机器的快近5倍。这绝对不合常理。我把一个测试程序发到你的cloudwu@263.net(你主页里面找的)里,你执行看看。

呵呵. 关于 local 的这个问题,在 maillist 上有人讨论过。有人建议默认是 local, 全局加个 global . 但是没通过 :D

对了, 那个浮点的问题, 到底是你的机器浮点太快,还是我的机器整数太快?

我觉得用 double 不可能更快。因为数据长度都从 4 字节长到 8 字节了。可能是哪里搞错了。

我想,这看应用了,总不会有人一意要写会出错的程序。在这个测试上面,如果他的局部变量和全局变量都使用比较简单的方法访问就没有这个问题。

那个测试程序没有用 local 不光是性能的问题,应该是一个错误。因为函数里面的变量不用 local 直接递归和间接递归时都会出错。
(试想一下 C 程序函数里的变量都用全局?)

所以绝对不能说 "这些对Lua并不重要"

确实如你所说,我应该用局部变量。我重新坐了一个测试,可以看我的blog,在int和float的数据结果上,我们的差别还是很大。我想可能是CPU类型不同的问题。

Cloud说的对,Lua中对全局变量的操作需要通过表来进行,因此会有额外的操作。这些对Lua并不重要,因为Lua的初衷是尽量保持一个轻巧而统一的框架,所以一些基础的代码优化技巧如cse并没有采用。

我曾经写过一个超轻量级的语言,放在sourceforget上面,网址是:http://azure-lang.sourceforge.net/

该语言实现了一些基本的功能如正则表达式匹配,coroutines, mark and sweep垃圾收集,尾递归消除,异常处理,以及本地代码调用等。主页上还提供了一个用该语言渲染OpenGL物体的例子。值得一提的是,该语言的大小只有Lua的一半。

我把你的程序抄下来用 lua5.0.2 跑了一下,然后把所有变量加上 local 再跑了一下。速度是这样的:

没改 local 的 lua 5.0.2
14103694640 (时间单位)

改了 local 后
8968978970 (时间单位)

大约可以提高 1.57 倍的速度。

偶一时性起,把这个程序放到我的脚本里跑了一下,速度是 8111484710 。 比 lua 快 1.1 倍。我想可能是因为我用的 lua 是 double 的类型的缘故了。

然后我也把 lua 的 number 类型改成了 int 测试结果跟你的大不一样喔,是 2418171042
快了整整 3.7 倍

你的测试有问题哟,你应该用 lua 的 local 关键字把中间变量全部声名成局部的。你这样用 global 对象是不公平的。 global 对象会对 global table 做 table 操作,比 local 对象要慢很多。
而你的测试本身完全不用把变量做成 global 的,而且这样用全局变量也不符合 lua 语言的设计理念

在一些特殊的应用环境,one-pass是肯定有意义的。另外,在特殊的应用中,编译速度也是至关重要的,比如某一个应用,他绝大部分都是由脚本组成,而且在使用的时候才进行编译(我一个朋友的游戏有超过50%的代码使用脚本)。
我也做了一次我的脚本和LUA执行速度的比较。在我的blog(http://spaces.msn.com/members/gamedeveloper)可以参考一下。

如果不是 one-pass , 中间的数据就一定要找个地方放起来。如果不放起来,就需要重复产生这些数据。

时间也是这样的,因为每次 pass 都需要生成一些中间数据,这些数据不可能留在 cpu cache 里,至少要放到内存中,下次 pass 的时候再读回来。而 one pass 的过程可以不用产生这些中间数据,或者产生了立刻用掉,对 cpu 的利用率是很高的。

不是one pass就不能使用有限的内存吗,不是one pass编译的时间效率就一定低吗,这个问题值得思考。我并不知道准确的答案,但我觉得这个疑问是值得提出的,让我们仔细想想。

程序扔了,就是开一个100 大小的数组,初始化成一个数列。然后用双重循环冒泡排序。这个程序再循环做 1000 次。

对了,能否把你和LUA测试速度的脚本代码贴出来。我看看我的脚本执行时间是多少。

one-pass 的一个好处是,无论多大的源文件,都可以用有限的内存,在不借助外存的环境下完成编译。这个优势有没有意义,恐怕要看具体运用环境了。

是否one-pass我想很大程度上是由语言语法的复杂度决定的。像C++,C#这种语言要一遍分析恐怕不是那么容易的。我实现的编译器虽然用了三次分析,但是前面两次的分析只是对程序结构的分析。对函数内部的代码不做任何分析,速度也是很快的。对代码的分析只需要一次就完成了。对程序结构的分析是为了让用户写的代码结构更加灵活。而且以后写IDE的时候这种分析也可以提供很多的动态信息。

one-pass 的时间效率和空间效率都很高。在受限内存下很有意义。

解释脚本的时候需要的空间开销在很多时候也是很有意义的。而且解释器本身的代码尺寸在某些环境下也需要考虑。

如果 one-pass 是没有需要的,lua 也不需要去做,这不是技巧的问题。

很多东西,意识不到问题比找不到解决方法要严重很多。比如one-pass 这个,觉得实现麻烦不去实现,和觉得实现没有意义不去实现就是不同的。

强调one-pass没什么意义 编译的效率没有运行的效率来的重要 而且你的应用估计都不会很大 何必非要one-pass呢 一切从应用考虑吧 不过如果你喜欢技巧的挑战那就是另一回事了

parrot 就是 perl6 啦 :B

hi,parrot也是基于寄存器的VM,支持线程和JIT。最近才放出0.4版本。www.parrotcode.org

很明显register-based的虚拟机显然要快于stack-based的,不过jvm用stack-based我想有它的原因,不过不知道是什么原因?

效率永远是有意义的,即使在动态语言上。不然也不会有那么多人投入到提高其效率的工作上去。

当然这个是个人理解的问题,一个人的理解和众人不同也是可以理解的,况且运用场合不同。

递归下降说起来容易,做起来难。尤其是同时有左右值的语言。如果要对 C++ 的语法做one-pass 的递归下降分析....

"lua 也是一个one-pass 的基于递归向下算法的 compiler "

是编译原理的“递归下降法”吗?
对“递归下降法”,
《程序=数控结构+算法》一书中专用了一章进行介绍,极佳。

动态类型的语言再怎么优化效率都不可能达到静态类型语言的水平的,再怎么玩代码技巧,提高了一倍效率又如何?用静态类型可以轻松提高一个数量级。在效率上耗费太多精力意义不大。

Post a comment

非这个主题相关的留言请到:留言本