云风的 BLOG: lua 的 table 处理

lua 的整体效率是很高的，其中，它的 table 实现的很巧妙为这个效率贡献很大。

lua 的 table 充当了数组和映射表的双重功能，所以在实现时就考虑了这些，让 table 在做数组使用时尽量少效率惩罚。

lua 是这样做的。它把一个 table 分成数组段和 hash 段两个部分。数字 key 一般放在数组段中，没有初始化过的 key 值全部设置为 nil 。当数字 key 过于离散的时候，部分较大的数字 key 会被移到 hash段中去。这个分割线是以数组段的利用率不低于 50% 为准。 0 和负数做 key 时是肯定放在 hash 段中的。

string 和 number 都放在一起做 hash ，分别有各自的算法，但是 hash 的结果都在一个数值段中。hash 段采用闭散列方法，即，所有的值都存在于表中。如果hash 发生碰撞，额外的数据记在空闲槽位里，而不额外分配空间存放。当整个个表放满后，hash 段会扩大，所有段内的数据将被重新 hash ，重新 hash 后，冲突将大大减少。

这种 table 的实现策略，首先保证的是查找效率。对于把 table 当数组使用时将和 C 数组一样高效。对于 hash 段的值，查找几乎就是计算 hash 值的过程（其中string 的 hash 值是事先计算好保存的），只有在碰撞的时候才会有少许的额外查找时间，而空间也不至于过于浪费。在 hash 表比较满时，插入较容易发生碰撞，这个时候，则需要在表中找到空的插槽。lua 在table 的结构中记录了一个指针顺次从一头向另一头循序插入来解决空槽的检索。每个槽点在记录 next 指针保存被碰撞的 key 的关联性。

整个来说，这种解决方法是非常不错的。

关于映射表的实现，我前段时间也做过一个别的研究。贴在留言本上：
<a href="http://www.codingnow.com/2004/board/view.php?paster=777&reply=0">树表结合的一种映射表实现</a>
<a href="http://www.codingnow.com/2004/board/view.php?paster=776&reply=0">在 vector , map , list 间取得平衡</a>

Comments

分析的不错，很精彩

Posted by: army | (13) August 6, 2011 03:23 PM

博主的文章确实精彩，赞请教一个问题，lua源码中，有个函数int arrayindex(Tvalue* key)；它有一行代码，是对两个double（也就是lua的number）数据进行==比较，请问这是怎么回事，不太理解？谢谢

Posted by: bert | (12) June 1, 2011 03:12 PM

哇，我以为写一个操作系统很难，不过真的写了一个以后觉得也不过如此！

Posted by: pootow | (11) January 20, 2008 02:40 PM

我记得是的，不过你可以查 lua 的 source 看一下确认。因为那个程序我编译运行过(lua 5.0.2)，当不会有错。书的那一节写的很早，那个时候我还没太仔细看 lua 的 source，所以代码写的并不好。有些遗憾，现在再写那章的话会写的好一些。

Posted by: Cloud | (10) March 22, 2006 01:04 AM

很冒昧的想请教云风大侠一个问题，看了你的《编程感悟》关于Lua的那段，对于你在书中的对那个例子的stack注释不是很理解。想请问，当调用Luaopen_base时，会在stack里生成一个coroutine的table吗，其中的元素的key是“resume”，“yield”吗？否则为什么在gettable后，原本在stack中的resume变成coroutine.resume了？

Posted by: duotemplar | (9) March 22, 2006 12:50 AM

>>>>要想不被单一的思想左右，就应该多读。lua python ruby 这些都值得一读的。>>>lua 会出现语法混淆，是因为它不强求语句以 ; 结尾。>>>递归向下是最简单的编译算法，简单的往往也是优美的。如果 C 语言的语法当初设计的更好一些，用递归向下的算法编译也会很美妙。< 同意。但是我因为没有能力把Lua5.0的语法修改成LL(1)型的，所以不得已用了SLR解析方法。难怪有人说为一种语言定义好一个优美的语法就完成了语言设计的一半工作了。

Posted by: Anonymous | (8) November 8, 2005 10:22 PM

要想不被单一的思想左右，就应该多读。lua python ruby 这些都值得一读的。 lua 会出现语法混淆，是因为它不强求语句以 ; 结尾。递归向下是最简单的编译算法，简单的往往也是优美的。如果 C 语言的语法当初设计的更好一些，用递归向下的算法编译也会很美妙。

Posted by: Cloud | (7) November 8, 2005 06:32 PM

还是不对，Lua4.0的指令还是基于栈顶操作的，只不过这个栈顶不一定只是指栈最顶端的那个元素，而是栈顶部的若干个元素。下面是 while i还是不对，Lua4.0的指令还是基于栈顶操作的，只不过这个栈顶不一定只是指栈最顶端的那个元素，而是栈顶部的若干个元素。下面是 while i<lim do a[i] = 0 end 这条语句的4.0字节码: -- Lua 4.0 2 GETLOCAL 2 ; i 3 GETLOCAL 1 ; lim 4 JMPGE 5 ; to 10 5 GETLOCAL 0 ; a 6 GETLOCAL 2 ; i 7 PUSHINT 0 8 SETTABLE 9 JMP -8 ; to 2

Posted by: soloist | (6) November 8, 2005 02:31 PM

是我弄错了，Lua4.0以前的指令要求的是待操作的对象位于栈中，而非一定在栈顶。这种操作模式与Lua提供的API很类似。 Lua的官方实现是值得学习的，只不过目前我是有意不读，为了避免沿着发明者的思路去实现它。待我自己从头走一遍以后，会反过来再阅读它的源码，对比二者的优缺点。当然完全不参考标准实现确实会遇到一些障碍。比如Roberto Ierusalimschy 说他们的语法解析部分用的是简单的递归下降方法，可是我根据5.0手册上的语法定义却改不出LL(1)语法，只能写出一个准SLR语法。不过这让我找到了编译器的一个错误。如下的代码: print (3) 是一个完全合法的函数调用，可是编译器却会报错:ambiguous syntax (function call x new statement) near `(' 我认为实现一个虚拟机最难的部分是为它设计一个良好的指令系统，这个开头开好了，接下来的路就会顺很多。

Posted by: soloist | (5) November 8, 2005 01:15 PM

lua 的源码是开放的，何不读之？比道听徒说要好的多。lua 从一开始就不是基于栈定操作的，我从 lua5才开始仔细读 source code，不清楚 lua4 对 local 变量的实现。但local 变量以专有指令来实现而不直接用堆栈是很自然的实现方法，lua4应该也是的，这点从 lua4 到 lua5 应该没太大改变。写虚拟机并不难，我花了1周时间完成它。或许每个科班学生，学习编译原理的课程后，做课程设计都应该有能力自己在课程设计上完成它，否则编译原理的课程不能给及格吧 :)

Posted by: Cloud | (4) November 7, 2005 10:48 PM

据我所知Lua4.0及以前的虚拟机是基于栈的，而语言发明人说Lua5.0已经改进为寄存器型的了。但是，我觉得LuaVM5.0实际上是一种寄存器与堆栈型的混合体。寄存器默认的序号是1到250，而每个函数的stack fram就由这一组寄存器组成，操作码可以是任意一个寄存器标号，也就是说栈中任意位置的值都可作为操作数，而不仅仅局限于栈顶元素。这样的话，一个Lua函数对local变量个数是有限制的，我用Lua5.04试过有256个参数的函数定义，编译器那就被否决了，说local变量个数限制在200个之内。我没读过Lua的源码，不知道可读性如何，但是Lua程序的“汇编码”可读性却不好。个人认为这是每条指令的语义不够直观、有点晦涩，side effect太多所致。我没接触过其它脚本，或许这是所有虚拟机指令系统的共同特点？

Posted by: soloist | (3) November 7, 2005 05:45 PM

我最近在写自己的虚拟机，也是基于堆栈的。一开始想用 C 写，写了大约 1500 行（大约花了两个晚上和一个白天的时间编写和调试），可以基本工作了后，发现写到 GC 的环节，C 代码不太容易表达的优雅，为以后扩展带来了极大的困难。这也是 lua 的代码不那么容易看懂的原因之一吧。这周一一赌气，把所有代码推翻重新写了，这次用的 C++。感觉清晰了很多。实现了原来已经实现的所有功能后，加了 gc 模块，大约 1900 行。这次又了上次的经验，知道会碰到的一些问题，和考虑过改进算法，所以速度快了很多。因为我以前读过 lua 的 source code，这次写的虚拟机，虽然还没能比较，但是我想运行效率上会比 lua 高很多的。而且我用的是真正物理内存上的 gc 。虚拟机用到所有内存都会放在一个整块的连续内存上，整理内存时会有数据移动。所以我想内存利用率上能好一些，至少保证没有内存碎片。这次的感受是，如果能把一个比较大的 C 代码写的优美，需要的功底比 C++ 要高许多。而且经过这样的练习，感觉自己写 C++ 的水平也有所提高。 ltable.c 的比较难读倒不是完全因为虚拟机是基于栈的，主要可能还是因为是 C 代码吧。我的 table 的实现类似于 lua 。因为用的 C++ 写，读起来清楚很多。

Posted by: Cloud | (2) November 1, 2005 04:48 PM

相应的代码主要在ltable.c中。不过因为LuaVM是基于栈的虚拟机，代码看上去不那么直观。

Posted by: myan | (1) November 1, 2005 01:57 PM

云风的 BLOG

思绪来得快去得也快，偶尔会在这里停留

lua 的 table 处理

Comments

Post a comment