Lua解释器源码(三):Tables
目录

1. Tables

Lua中Talbes是关联数组(associative arrays)。 这也意味着Tables能被任何值(除了nil)索引,能够存储任何类型。 而且,当存入一个不存在的索引时,Tables能够自动扩展; 当删除一个索引时(置nil),Tables能够自动收缩。

不像其它脚本语言,Lua中没有数组(arrays)类型(如Python中的[]),而是用整数索引的Tables表示数组。 这也表示数组为Lua带来了一些好处:

  • Lua不需要为arrays或tables维持两种集合操作,更加简洁;
  • 程序员不用在arrays和tables之间做选择;

在Lua中实现离散的数组是无关紧要的。 如在Perl中,$a[1000000000]=1将创建10亿个对象; 而在Lua中,a={[1000000000]=1}只是创建一个包含一个元素的table。

从Lua 5.0开始,Tables由一个混合数据结构实现,包含一个哈希部分和一个数组部分。 Tables自动动态地调整这两部分内容: 数组部分尽量存储1到n之间的整数索引,而哈希部分存储其它类型的索引和超出n部分的整数索引。 当table需要增长时,Lua重新计算它的哈希部分和数组部分长度。 这两部分都可能为空。 数组部分重新计算的长度n必须符合以下条件:

  • 1到n之间至少一半的槽被使用,这样避免离散的数组浪费空间;
  • n/2+1到n之间至少有一个槽被使用,这样避免当原数组长度为n/2时就要增长;

在计算新的长度后,Lua创建新的部分,把旧的部分中的元素插入到新的部分。

这种混合机制有两个优点:

  1. 整数索引不需要哈希,因此更快;
  2. 数组部分不需要记录索引键,因此比同样情况存入哈希部分省了一半内存;

因此,当Tables被用来做数组时,无论从内存占用上还是访问速度上来说,它更像真实的数组类型。 这时哈希部分是空的。 而当Tables被用作关联数组时,只使用哈希部分,数组部分是空的。 这样内存节省是必要的,因为在Lua中创建很多小tables是很常见的,例如用table来实现对象的时候。

2. 哈希表

Tables的哈希部分使用一种Brent改进的链状发散表(chained scatter table)。 这种哈希表插入新键key1的过程是:

  1. 首先,对key1做哈希,检查其主位置(main position)是否空闲,空闲就插入;
  2. 如果主位置不空闲,被key2占用,则测试key2是否是其它碰撞节点;
  3. 如果key2是碰撞节点,则把这个碰撞节点移至空闲位置,并把插入的key1插入到这个主位置;
  4. 如果key2不是碰撞节点占用,则说明key2也在其主位置,则把key1插入到空闲位置,并把key2->next指向key1。

这样,当发生碰撞时,不需额外分配新的空间,防止内存碎片。 并且next指针关联起了索引相同的节点,这样查找起来就像链表一样。 当哈希表比较满时,插入和查找较容易发生碰撞。 当整个哈希表被填满时,扩大哈希表,重新索引表内数据,从而降低了整体的碰撞次数。

另外,哈希表结构使用一个指针指向第一个空闲位置,这样保证插入时快速找到空闲位置。

3. 源码

Table结构:

typedef union TKey {
struct {
TValuefields;
struct Node *next;  /* for chaining */
} nk;
TValue tvk;
} TKey;

typedef struct Node {
TValue i_val;
TKey i_key;
} Node;

typedef struct Table {
CommonHeader;
lu_byte flags;                                          // 元表标记
lu_byte lsizenode;  /* log2 of size of `node' array */  // 哈希部分大小
struct Table *metatable;                                // 元表
TValue *array;  /* array part */                        // 数组部分
Node *node;                                             // 哈希部分
Node *lastfree;  /* any free position is before this position */ // 第一个空闲位置指针
GCObject *gclist;
int sizearray;  /* size of `array' array */             // 数组部分大小
} Table;

每个table结构最多由三块连续内存组成:

  • Table结构
  • 数组部分是TValue类型数组,长度为sizearray。
  • 哈希部分的Node键值对是<TKey,TValue>类型。 其中TKey包含一个TValue和指向下一个Node的指针(暂时还没看出定义TKey的写法有何深意)。 哈希部分长度为2的lsizenode次幂。

当哈希表没有插入元素时,node指向如下静态全局常量dummynode。

#define dummynode       (&dummynode_)

#define isdummy(n)      ((n) == dummynode)

static const Node dummynode_ = {
{NILCONSTANT},  /* value */
{{NILCONSTANT, NULL}}  /* key */
};

table按照Lua语言的定义,需要实现四种基本操作:读、写、迭代和获取长度。 Lua中并没有删除操作,而仅仅是把对应键位的值设置为nil 。

插入一个新key(即写操作)基本就是按照上面说的流程,注释已经很多了:

TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
Node *mp;
if (ttisnil(key)) luaG_runerror(L, "table index is nil"); /* 检查key!=nil*/
else if (ttisnumber(key) && luai_numisnan(L, nvalue(key))) /* 检查key!=NaN*/
luaG_runerror(L, "table index is NaN");
mp = mainposition(t, key);
if (!ttisnil(gval(mp)) || isdummy(mp)) {  /* main position is taken? 哈希表满了 */
/* !ttisnil(gval(mp)) 说明主位置被占 */
/* isdummy(mp) 说明table的哈希部分为空 */
node *othern;
Node *n = getfreepos(t);  /* get a free place */
if (n == NULL) {  /* cannot find a free place? */
rehash(L, t, key);  /* grow table */
/* whatever called 'newkey' take care of TM cache and GC barrier */
return luaH_set(L, t, key);  /* insert key into grown table */
}
lua_assert(!isdummy(n));
othern = mainposition(t, gkey(mp));
/* 检查mp是否在其主位置上 */
if (othern != mp) {  /* is colliding node out of its main position? */
/* yes; move colliding node into free position */
while (gnext(othern) != mp) othern = gnext(othern);  /* find previous */
gnext(othern) = n;  /* redo the chain with `n' in place of `mp' */
*n = *mp;  /* copy colliding node into free pos. (mp->next also goes) */
gnext(mp) = NULL;  /* now `mp' is free */
setnilvalue(gval(mp));
}
else {  /* colliding node is in its own main position */
/* new node will go into free position */
gnext(n) = gnext(mp);  /* chain new position */
gnext(mp) = n;
mp = n;
}
}
setobj2t(L, gkey(mp), key);
luaC_barrierback(L, obj2gco(t), key);
lua_assert(ttisnil(gval(mp)));
return gval(mp);
}

再看一看table的调整部分。 在上一段代码里,如果table没有空闲位置,则要执行rehash(L, t, key)函数增长table。 Lua不会在设置key值为nil时而回收空间,而是在预先准备好的哈希空间使用完后惰性回收。 即在 lastfree 递减到哈希空间头时,做一次 rehash 操作。 rehash实现如下:

static void rehash (lua_State *L, Table *t, const TValue *ek) {
int nasize, na;
int nums[MAXBITS+1];  /* nums[i] = number of keys with 2^(i-1) < k <= 2^i */
int i;
int totaluse;
for (i=0; i<=MAXBITS; i++) nums[i] = 0;  /* reset counts */
nasize = numusearray(t, nums);  /* count keys in array part */
totaluse = nasize;  /* all those keys are integer keys */
totaluse += numusehash(t, nums, &nasize);  /* count keys in hash part */
/* count extra key */
nasize += countint(ek, nums);
totaluse++;
/* compute new size for array part */
na = computesizes(nums, &nasize);
/* resize the table to new computed sizes */
luaH_resize(L, t, nasize, totaluse - na);
}

nums数组统计了table中所有key的分布情况, 这其中分别用到了numusearraynumusehash函数。 totaluse统计了总体key的使用个数。 nasize统计了数组部分key的使用个数。 na标识新的数组部分的长度,这是使用computesizes函数在不低于50%利用率下得出的结果。

最终通过lua_resize函数调整数组部分和哈希部分大小。

参考

boyxiaolong 于 2014-04-19 20:27 时评论:
额 是云风 不是风云
Ranler 于 2014-04-19 21:05 时评论:
@boyxiaolong 感谢指出错误

发表评论