Lua源码简析及使用技巧

lua是一款非常小巧的开源的脚本语言，5.1版本的的压缩包仅208KB，代码仅有17000多行。
使用标准c编写的它可以很方便的嵌入到各个平台系统中，深得游戏开发者的青睐。
你可以很方便的在github中查看它的源代码：https://github.com/lua/lua

数据类型

lua的数据类型定义在lua.h中

// lua.h
#define LUA_TNONE (-1)          // 无类型
#define LUA_TNIL 0              // 空类型
#define LUA_TBOOLEAN 1          // 布尔
#define LUA_TLIGHTUSERDATA 2    // 指针 (void *)
#define LUA_TNUMBER 3           // 数字 (lua_Number)
#define LUA_TSTRING 4           // 字符串 (TString)
#define LUA_TTABLE 5            // 表 (Table)
#define LUA_TFUNCTION 6         // 函数 (CClosure)
#define LUA_TUSERDATA 7         // 指针 (void *)
#define LUA_TTHREAD 8           // LUA虚拟机 (lua_State)

我们可以看到LUA_TLIGHTUSERDATA和LUA_TUSERDATA都是void类型，但LUA_TLIGHTUSERDATA由lua外部使用者自行管理，不需要GC。

上述定义中，LUA_TTABLE及之后的类型均由GC进行管理。

字符串

Lua的字符串与其他语言不同，在Lua虚拟机中有一个哈希数组变量，用来存储所有字符串
同一个字符串只会有一份，一旦创建不可更改，Lua中使用的均是该字符串的引用

这个哈希数组存放在global_state.strt中

每当使用一个字符串时，会进行以下操作：

• 计算该字符串的哈希值
• 找到对应的哈希桶，遍历该哈希桶，如果找到同样的字符串，则返回
• 否则，在该哈希桶中新插入该字符串
• 当一个哈希桶中数量过多时，执行一次重新哈希
• GC阶段时会找到没有使用的字符串进行回收

使用技巧

我们知道每次设置字符串时，都会有一次哈希和查找操作，如果是新的字符串，还会新增到全局数组中，所以我们应该尽可能减少临时字符串以及字符串连接操作

-- 低性能
local str = ""
for i = 1, 99999 do
    str = str .. "."
end
-- 高性能 大约提升10倍
local t = {}
for i = 1, 99999 do
    t[#t + 1] = "."
end
local str = table.concat(t, "")

Table

Lua的table是一个非常灵活的数据类型，它定义在lobject.h中，实现在ltable.c中。

typedef struct Table {
  CommonHeader;
  lu_byte flags;
  lu_byte lsizenode;  // 以2的lsizenode次方作为哈希表长度
  unsigned int sizearray;  // 数组部分大小
  TValue *array;  // 数组部分
  Node *node; // 哈希表部分
  Node *lastfree;  // 指向最后一个闲置的链表空间
  struct Table *metatable; // 元表
  GCObject *gclist;
} Table;

Lua中的table分为数组和哈希表两个部分

• 当key为正整数时，在数组空间满足时会优先使用数组部分
• 哈希表部分则可以存放任意key和非nil的所有类型value

访问流程

• 当输入key为正整数且小于等于数组部分大小时，尝试在数组部分查找
• 否则计算哈希值，找到对应哈希桶，遍历该哈希桶直到找到该key

这里可以看出，如果key大于数组部分大小时，即使是正整数，也会存放在哈希表中

local t = {1}
t[1] = 0 -- 数组部分
t[100] = 0 -- 哈希表部分

Table空间动态扩展

• local t = {}数组部分和哈希部分没有分配空间
• 在添加元素会优先往哈希表部分添加
• 哈希表空间不足时执行rehash和resize 操作，重新分配数组部分和哈希部分大小
• Lua申请内存时以 2 的整数次幂边界对齐

static void rehash (lua_State *L, Table *t, const TValue *ek)

table重新分配内存有个原则：数组段的利用率不低于 50%

为此在rehash函数中调用了numusehash函数

目的：计算正整数key在(2^(i - 1), 2^i]之间的元素数量，存放在num[i]中

static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna)

举个例子：

tb = {1,2,3, 20}
num[0] = 1   -- 1在此范围 2^0，范围内元素个数1个
num[1] = 1   -- 2在此范围 2^1，范围内元素个数1个
num[2] = 1   -- 3在此范围 2^2，范围内元素个数1个
num[3] = 0
num[4] = 0
num[5] = 1   -- 20在此范围 2^5，范围内元素个数1个

而后rehash函数调用了computesizes

目的：判断每个2次方位置num[i]的总元素个数都超过该范围的50%

static unsigned int computesizes (unsigned int nums[], unsigned int *pna)

举例例子：

-- 在之前的例子中我们已经统计出了各二次幂分段的元素数量
-- 接着我们判断是否每个二次幂分段使用率超过50%
num[0]分段：元素个数 1 > 0.5 * 2^0 满足利用率
num[1]分段：元素个数 1+1 = 2 > 0.5 * 2^1 满足
num[2]分段：元素个数 1+1+1 = 3 > 0.5 * 2^2 满足利用率
num[3]，num[4]分段无元素，跳过
num[5]分段：元素个数 1+1+1 = 3 < 0.5 * 2^5 不满足，舍弃

最终数组部分分配的大小为2^2，也就是1，2，3均存在数组部分，20存放在哈希表部分

使用技巧

• 预分配策略

对于空表而言，前三个元素会执行三次rehash操作，而100万个元素仅执行了20次(2^20 > 100万)，对于已知元素大于3个的表来说，建议采用预分配策略

-- 低性能
local a = {}
for i = 1, 3 do
    a[i] = true
end

-- 高性能，大约提升一倍
local a= {1,1,1}
for i = 1, 3 do
    a[i] = true
end

• 尽量复用临时table

Table表的取长度操作

我们都知道lua可以使用#符号，来取table的长度，但是其中有很多的限制
举个例子，猜猜看下面这段代码的输出结果

print(#{1,2,nil,4,5,6,7,nil}) -- 输出7
print(#{1,2,3,nil,5,6,7,nil}) -- 输出3

为什么会出现这种结果呢，我们就要看看lua的取长度函数了

lua_Unsigned luaH_getn (Table *t) {
  unsigned int j = t->sizearray;
  if (j > 0 && isempty(&t->array[j - 1])) {
    unsigned int i = 0;
    while (j - i > 1u) {  /* binary search */
      unsigned int m = (i + j) / 2;
      if (isempty(&t->array[m - 1])) j = m;
      else i = m;
    }
    return i;
  }
  else {  /* 'j' is zero or present in table */
    if (isdummy(t) || isempty(luaH_getint(t, l_castU2S(j + 1))))
      return j;  /* 'j + 1' is absent... */
    else  /* 'j + 1' is also present */
      return hash_search(t, j);
  }
}

取长度一般经过以下几个步骤：

• 数组部分末位为空，二分法找空值

print(#{1,2,nil,4,5,6,7,nil}) -- 输出7
数组大小为8，二分中值4，key=4存在的，会向右边二分查找，返回长度7

print(#{1,2,3,nil,5,6,7,nil}) -- 输出3
数组大小为8，二分中值4，key=4不存在的，向左二分，返回长度3

• 哈希部分为空，或者数组末位+1不存在，直接返回数组部分大小

-- 哈希部分为空
print(#{nil,nil,nil,nil,nil,nil,nil,8}) -- 输出8

-- 数组末位+1不存在
-- 数组大小4，哈希部分key=5不存在，所以直接返回4
local t = {nil, 2, 3, 4}
t[6] = 6 -- 若t[1]不为nil时，根据利用率大于50%原则，t[6]会被分到数组部分
print(#t) -- 输出4

-- 另一个故事
local t = {1,2,3,4}
t[6] = 6
print(#t) -- 输出6
-- 根据利用率大于50%原则，2^3次方区间总个数为5，满足条件，t[6]会被分到数组部分

• 数组末位+1存在时，数组size翻倍找空值，再二分查找最大key
  这一部分的代码是在hash_search函数中

local t = {nil, 2, 3, 4} -- 数组部分
t[5] = 5 -- 哈希部分
print(#t) -- 输出5
-- key = 5存在时，数组大小=4，翻倍找空值，key = 8不存在，找到空值
则大小落在4-8之间，二分...
最终找到key = 5

---

原创文章，仅发布于我的简书与我的博客中，禁止转载!