lua 源码系列文章:
lua源码欣赏的第4.2.2章到第四章结束的内容,主要还是与 lua 表相关的源码。
Contents
数字类型的哈希
对于数字类型的哈希,其中说到了几个版本迭代改进的事情。
Lua5.1 中直接采用读取内存中相应块的数据相加来进行哈希,这种算法在64位系统下可能会出现相同的数字哈希结果不同的BUG:
在64位系统下,long double被认为是16字节而不是32位系统下的12字节,以保持对齐。但 其数值本身还是12字节,另4字节被填入随机的垃圾数据
Lua5.2 则改进了这种算法,变成了用户可配的两种算法。其一是利用联合体来计算数字的哈希(条件是:数字类型为 double, 目标机器使用 IEEE574 标准的浮点数),其二是性能不高,采用更为通用和标准的哈希算法。
表的迭代 (next)
表的迭代是在 lua 中经常使用的部分,在仔细阅读了源码之后,理解了之前在网上看到的 lua 查询表结构是否为空的原理。
首先说明一下 lua 中对表长度的定义:t[n] 为非空,而 t[n + 1] 为空,则 n 为表的长度。再补充一点,当表中的数组部分被填满后或者为空的时候,也会计算哈希表部分的长度。
还有之前没注意到的一点,在进行表迭代操作时,其他语言都是禁止对该表进行任何操作的。而在 lua 中,在迭代表过程中,可以对已经存在的值进行修改甚至删除(赋值为 nil),而不会影响迭代的结果。
对正在迭代表进行删除元素操作的时候,如果刚好碰到 gc 过程,被设置为 nil 的键值对会被标记为死,而 findindex
函数中对这种情况进行了处理。
如果对正在迭代的表进行新建操作时,则可能会使这个新的key不被遍历到,或者新建操作触发了 rehash
动作,则会导致重复遍历等问题。
lua 中的 next(table [,index])
函数是接受两个参数的,我在判断一个table是否为空时都是这样用的:
|
|
元方法的优化
Lua 实现复杂数据结构,大量依赖给 table 附加一个元表( metatable)来实现
于是对原表的操作是 Lua 中的热点,对热点的优化必要性不言而喻。
从 Lua 创建表开始,这些元方法就直接附加在了 lua 的表中,而利用 Table
结构中的 flags
位对元方法进行标记,也可以大大提升元方法的查询速度。在实际查询中,直接使用相应的位,直接就可以查询到相应的元方法。
在 Lua 创建原表时发现,Lua 中使用 luaS_fix
对状态机中的数据结构进行标记,当标记为 FIXEDBIT
时可以使该结构不被回收。
https://github.com/xiaocang/lua-5.2.2_with_comments/releases/tag/lua_table_metatable_04