January 5, 2020

lua源码笔记,table的实现

table是lua的灵魂,搞懂其核心还是很有必要的。
关于table的定义:

table定义

lobject.h(497:507)

TValue *array和Node *node便是分别指向数组部分和hash部分

  • array是一个单纯的一维数组
  • node是hash部分的链表
    • Node结构体中有i_key(TKey类型)
    • TKey中有nk,nk中有next
    • 注意这个next是个int,并不是个指针,保存的是地址的offset

算法

table的一个核心问题就是,什么时候什么key会进入数组部分,什么key会进入hash部分呢?

首先,什么时候
lvm的OP_SETTABLE指令执行时,对于数字的key在数组有空间时直接fastset进入数组部分,如果数组部分空间已满,则先进入luaH_newkey(ltable.c - 461:510)流程,先放进mainposition中,也就是hash部分。当table的hash部分没有空位置的时候,进行rehash操作(ltable.c - 477:482),在rehash中调整数组部分和hash部分,放一部分的key到数组部分中去。

其次,什么样的key会进入数组部分
从rehash函数(ltable.c - 395:412)看出,在numusehash中292调用countint函数发现,这个key首先是一个整数数字(LUA_TNUMINT类型)。
table的数组部分和hash部分的大小都是2的整数次幂,在rehash中分别用numusearray和numusehash统计了各个2整次幂区间段的整数key数量。

rehash函数

nums数组就是用于统计2整数次幂区间段中整数key
然后computesizes(ltable.c - 219:240)中,使用nums的信息,分析整数的占有率,计算数组部分的最佳大小。

computesizes函数

整数key的总体占有率要大于最佳大小的一半。
rehash完成之后,把hash部分所有在数组涵盖范围中所有的整数都移入数组部分。
再说两句,是整数key的总体占有率,并没有要求每个区间中都要占有率一半以上。

于是总流程如下

key判断流程图

下面这个分布也是会触发数组部分的resize

  • (0, 1]: 0个
  • (1, 2]: 0个
  • (2, 4]: 0个
  • (4, 8]: 1个
  • (8, 16]: 8个

总个数9,要求>8个

伸缩

何时扩展?
当table的hash部分满的时候,除部分情况下的主动扩展

主动扩展的情况:

  • 虚拟机中OP_SETLIST时,直接调用luaH_resizearray(lvm.c - 1276:1276)
    • 这个指令是用来初始化数组
    • 例如 local a = {1, 2, 3} - tip: 当a很长的时候还会分批次OP_SETLIST
  • 虚拟机中OP_NEWTABLE时,直接调用luaH_resize(lvm.c - 873:873)

何时收缩?
table在rehash时,key数量变小跨越2的整数次幂的时候,就会收缩

Fastget和fastset

这是在虚拟机lvm中的部分,当遇到OP_GETTABLE或者OP_GETTABUP指令时,首先尝试fastget, 如果失败再进行正常的get

fastget函数

其实就是当key不是nil的时候,跳过metatable的__index方法,直接返回
fastset也是同理,当遇到OP_SETTABLE或者OP_SETUPVAL时,首先尝试fastset,如果失败在进行正常set

fastset函数

当设置的key不是nil的时候,直接修改现有key的值,不走metatable的__newindex方法

Note

  • 为何大小都选择是2的整数次幂呢?
    • 因为取模运算会被大幅度简化变成mod = s & (size -1)
    • lmod(lobject.h - 514:515)

Base on lua 5.3.5