January 5, 2020

lua源码笔记,table的实现

table是lua的灵魂,table是lua中最基础的数据结构,它可以像字典/数组一样往里放入键值对元素,并自动增长,搞懂其核心还是很有必要的。这次就从源码的层面来看看table是如何实现的。

数组,在c语言中本质上是一段固定长度的连续内存,无法自动增长。自动变长的数据结构实现方式往往都是通过在空间不足时,重新分配一片更大的连续内存,把原来数组中的内容(引用)复制一份过来,也同时能达到均摊复杂度O(1)的水平。

lua的table既可以成为一个数组使用,也可以作为一个字典使用,这是因为lua中把table分成了两个存储部分,一个是数组,一个是hash字典。

关于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(这里涉及一个优化,后面再聊)

实现

对于键值存储类的数据结构,从接口层面主要是实现get和set方法,就可以实现其功能。

首先看get,有一系列的get函数如luaH_getstr,luaH_get,luaH_getint,getgeneric等,其返回值都是一个TValue *

在getint中给出的key如果在table的数组范围内,则直接从数组中返回,否则再求hash从hash部分取出。

更普通的getgeneric方法,则直接把key进行hash找出对应value(拉链查找)

在set方法中,则首先使用上述一系列的get方法获取TValue *对应指针,然后再直接修改这个指针指向的值。如果这个key找不到呢?则会进入luaH_newkey为这个key创建一个位置存储。

lua的table支持各种类型的key,每一种key是如何进行hash的,具体可以查看mainposition(ltable.c - 117:137)的实现代码,这里就不赘述了。

算法

但是如上所述,table是由两部分组成,一部分是数组,一部分是hash,那么问题来了,什么时候什么key会进入数组部分,什么key会进入hash部分呢?

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

其次,什么样的key会进入数组部分?

必须是一个正整数,并且从1开始。

总流程如下

key判断流程图

接着问题就来了?table是如何调配数组部分和hash部分的呢?

调配的过程在rehash中展现。

首先table的数组部分和hash部分的大小都是2的整数次幂,在rehash中分别用numusearray和numusehash统计了各个2整次幂区间段的整数key数量。

rehash函数

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

computesizes函数

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

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

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

总个数9,要求>8个

伸缩

伸缩算法对于一个自动变长数据结构的均摊性能至关重要。从代码反推,luaH_resize由rehash调用,而rehash又只在luaH_newkey中调用(ltable.c 479),也就是说当table的hash部分满的时候,会自动扩展。

而显而易见的一种优化方式便是,当能预知这个table中放多少key时就可以直接初始化成对应的大小。

  • 虚拟机中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

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方法

内存亲和

在开头提到一下的hash部分Node的设计,实际上是为了内存亲和。CPU是有多级缓存的,当我们代码发起访问内存操作时并不是直接拉取主存中的内容,如果访问的地址已经在CPU的缓存中时,就直接从缓存拿取,提高了效率。

当拿取内存时,CPU会把请求地址周围的连续内存也给全部缓存下来,这就意味着如果我们需要的内存都是连续存放的,将大大提高缓存的使用效率,提高性能。

hash部分Node的设计就是为了紧凑内存,首先分配一个连续的Node数组,当拉链法hash遇上冲突的键时直接从Node数组的末尾拿到一个空闲的Node,直接使用,并保存这两个Node之间的位置差值,保存在next中。如果实现的拉链法hash遇上冲突时分配新内存势必会破坏内存连续性。

Note

  • 为何大小都选择是2的整数次幂呢?
    • 因为取模运算会被大幅度简化变成mod = s & (size -1)
    • lmod(lobject.h - 514:515)
  • lua的这种table设计虽然在使用上极大方便了程序员,不用考虑使用列表还是字典。但是也无可避免的带来了实现上的复杂度。我觉得得不偿失,因为在选择使用列表还是字典的语言中,程序员的编码心智负担并没有明显的增加,增加的这一点便利性却让更多深度优化lua的人想方设法避免多重点访问,metatable问题,避免rehash问题上。

Base on lua 5.3.5