Lua 笔记 string/table/function知识点

本文涉及到一些关于stringtablefunction的细碎知识点,一些常用操作的背后逻辑。本文是用于记录一次技术分享,部分内容与之前的一篇Lua的笔记有重叠。

本文参考和使用的lua源码基于Lua 5.3.5,编写的lua脚本运行于OSX系统,使用的是64位的lua运行库。

评估方法

纯lua侧的对于代码执行耗时的评估和执行过程中产生的堆内存的分析。

时间分析

对应于cpu负载,借助os.clock()函数,以下是一个示例:

1
2
3
4
5
local a, b
a = os.clock()
-- do something
b = os.clock()
print(b-a)

空间分析

对应于内存占用,借助collectgarbage()函数,这个函数传入不同的参数可以对lua的gc机制进行不同的操作控制,具体不再展开,这里主要是对堆内存的占用进行评估,用到的是以下的一套组合三连,即先强制一轮完整的gc(collect),然后禁用gc(stop),在执行完一些待测试的代码之后获取对内存占用的千字节数(count):

1
2
3
4
collectgarbage("collect")
collectgarbage("stop")
-- do something
print(collectgarbage("count"))

来一个简单的gc演示,三次获取堆内存,分配前、分配后、gc后:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
collectgarbage("collect")
collectgarbage("stop")
local a = collectgarbage("count") * 1024

local t = {}
t = nil

local b = collectgarbage("count") * 1024

collectgarbage("collect")

local c = collectgarbage("count") * 1024

print("before alloc " .. a)
print("after alloc " .. b)
print("after collect " .. c)

上边输出的内容,a和c是相等的,b会多出来56个字节(这是一个空表的内存占用)。

通用的lua类型

值类型

Lua中通用的值类型,TValue,使用一个联合体保存数据,和一个枚举值区分该值的类型,定义在lobject.h第100行:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
** Union of all Lua values
*/
typedef union Value {
GCObject *gc; /* collectable objects */
void *p; /* light userdata */
int b; /* booleans */
lua_CFunction f; /* light C functions */
lua_Integer i; /* integer numbers */
lua_Number n; /* float numbers */
} Value;


#define TValuefields Value value_; int tt_


typedef struct lua_TValue {
TValuefields;
} TValue;

GC信息

gc相关的通用数据,table、string和function都是受gc管理的类型,它们的结构中都是以一个CommonHeader开始,其定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
** Common type for all collectable objects
*/
typedef struct GCObject GCObject;


/*
** Common Header for all collectable objects (in macro form, to be
** included in other objects)
*/
#define CommonHeader GCObject *next; lu_byte tt; lu_byte marked


/*
** Common type has only the common header
*/
struct GCObject {
CommonHeader;
};

string

先从一段简单短Lua代码开始,尝试得到一个空字符串""所占用的堆内存:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
collectgarbage("collect")
collectgarbage("stop")

-- -------------------------------------------------------

local before = collectgarbage("count")

local s = table.concat({})
collectgarbage("collect")

-- -------------------------------------------------------

local after = collectgarbage("count")
print(1024 * (after - before))

输出25,即一个空字符串会产生25字节的堆内存。此处之所以使用table.concat({})而不是直接使用"",是因为代码中直接存在的字面字符串不会再单独分配堆内存。

来看一看一个空字符串的25个字节分别是什么内容,并以此为基础计算任意一个字符串占用的内存。

结构和定义

字符串的类型的定义在lobject.h第303行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
** Header for string value; string bytes follow the end of this structure
** (aligned according to 'UTString'; see next).
*/
typedef struct TString {
CommonHeader;
lu_byte extra; /* reserved words for short strings; "has hash" for longs */
lu_byte shrlen; /* length for short strings */
unsigned int hash;
union {
size_t lnglen; /* length for long strings */
struct TString *hnext; /* linked list for hash table */
} u;
} TString;

为确保内存对齐使用结构体UTString又套了一层:

1
2
3
4
5
6
7
/*
** Ensures that address after this type is always fully aligned.
*/
typedef union UTString {
L_Umaxalign dummy; /* ensures maximum alignment for strings */
TString tsv;
} UTString;

lstring.c中有创建字符串的函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
** creates a new string object
*/
static TString *createstrobj (lua_State *L, size_t l, int tag, unsigned int h) {
TString *ts;
GCObject *o;
size_t totalsize; /* total size of TString object */
totalsize = sizelstring(l);
o = luaC_newobj(L, tag, totalsize);
ts = gco2ts(o);
ts->hash = h;
ts->extra = 0;
getstr(ts)[l] = '\0'; /* ending 0 */
return ts;
}

其中包含一个宏sizelstring,定义于lstring.h,拆开是:

1
#define sizelstring(l)  (sizeof(union UTString) + ((l) + 1) * sizeof(char))

也就是说,要创建一个长度为l的字符串,实际上会分配sizelstring(l)的内存。结合前边UTStringCommonHeader的结构定义,不难得出UTString占用24字节。所以对于一个空字符串,加上1个char,一共是25字节。多出来的一个char是为了分配\0

可以得到如下结论:Lua中的string由两部分组成,字符串头和字符数组。字符串头即是前边的UString,字符数组就是传统的c中的数组,最终需要有\0作为结尾。

lobject.h中还定义了获取string的字符数组部分的宏:

1
2
3
4
5
6
7
8
9
10
/*
** Get the actual string (array of bytes) from a 'TString'.
** (Access to 'extra' ensures that value is really a 'TString'.)
*/
#define getstr(ts) \
check_exp(sizeof((ts)->extra), cast(char *, (ts)) + sizeof(UTString))


/* get the actual string (array of bytes) from a Lua value */
#define svalue(o) getstr(tsvalue(o))

短字符串和长字符串

执行下边的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
collectgarbage("collect")
collectgarbage("stop")

-- -------------------------------------------------------
local before = collectgarbage("count")

local s1 = "1234567890123456789012345678901234567890" -- 长度 40
-- local s1 = "123456789012345678901234567890123456789" -- 长度 39

for i = 1, 9 do
local s = s1 .. " "
end

-- -------------------------------------------------------

local after = collectgarbage("count")
print(1024 * (after - before))

发现当s1长度为39或者40时,产生的堆内存会有巨大的差异(适用于Lua 5.3.5 未必适用于更早版本的lua)。

原因是在Lua中有长短字符串之分,字符串有两种子类型:

lobject.h 52

1
2
3
/* Variant tags for strings */
#define LUA_TSHRSTR (LUA_TSTRING | (0 << 4)) /* short strings */
#define LUA_TLNGSTR (LUA_TSTRING | (1 << 4)) /* long strings */

短字符串的最大长度为40,定义于llimits.h

1
2
3
4
5
6
7
8
9
/*
** Maximum length for short strings, that is, strings that are
** internalized. (Cannot be smaller than reserved words or tags for
** metamethods, as these strings must be internalized;
** #("function") = 8, #("__newindex") = 10.)
*/
#if !defined(LUAI_MAXSHORTLEN)
#define LUAI_MAXSHORTLEN 40
#endif

在上边的示例代码中,分别在循环内部创建相同的字符串。两种情况下创建的分别是短字符串和长字符串。二者的本质区别如下:

  • 短字符串保存在全局的字符串表stringtable中,产生时会立即计算hash;
  • 长字符串单独保存,只有在需要时才lazy计算hash;

以下是创建字符串的逻辑,在lstring.c中:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
** new string (with explicit length)
*/
TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
if (l <= LUAI_MAXSHORTLEN) /* short string? */
return internshrstr(L, str, l);
else {
TString *ts;
if (l >= (MAX_SIZE - sizeof(TString))/sizeof(char))
luaM_toobig(L);
ts = luaS_createlngstrobj(L, l);
memcpy(getstr(ts), str, l * sizeof(char));
return ts;
}
}

在创建时会判断是否短字符串,如果是短字符串,那么走internshrstr,否则luaS_createlngstrobj。先来看短字符串的内部化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
** checks whether short string exists and reuses it or creates a new one
*/
static TString *internshrstr (lua_State *L, const char *str, size_t l) {
TString *ts;
global_State *g = G(L);
unsigned int h = luaS_hash(str, l, g->seed);
TString **list = &g->strt.hash[lmod(h, g->strt.size)];
lua_assert(str != NULL); /* otherwise 'memcmp'/'memcpy' are undefined */
for (ts = *list; ts != NULL; ts = ts->u.hnext) {
if (l == ts->shrlen &&
(memcmp(str, getstr(ts), l * sizeof(char)) == 0)) {
/* found! */
if (isdead(g, ts)) /* dead (but not collected yet)? */
changewhite(ts); /* resurrect it */
return ts;
}
}
if (g->strt.nuse >= g->strt.size && g->strt.size <= MAX_INT/2) {
luaS_resize(L, g->strt.size * 2);
list = &g->strt.hash[lmod(h, g->strt.size)]; /* recompute with new size */
}
ts = createstrobj(L, l, LUA_TSHRSTR, h);
memcpy(getstr(ts), str, l * sizeof(char));
ts->shrlen = cast_byte(l);
ts->u.hnext = *list;
*list = ts;
g->strt.nuse++;
return ts;
}

计算hash并到字符串表&g->strt中查找,如果找到了则返回已有的引用,否则createstrobj创建新字符串。

而对于长字符串,直接走创建新字符串的流程:

1
2
3
4
5
TString *luaS_createlngstrobj (lua_State *L, size_t l) {
TString *ts = createstrobj(L, l, LUA_TLNGSTR, G(L)->seed);
ts->u.lnglen = l;
return ts;
}

字符串的拼接

对于字符串..拼接和使用table.concat两种方式,都是通用的底层原理,重点在于减少过程中产生的临时字符串,以避免额外的gc开销,详见这里

使用string.format避免不必要的gc

使用string.format,避免数字产生的短字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
collectgarbage("collect")
collectgarbage("stop")

-- -------------------------------------------------------
local before = collectgarbage("count")

local title1 = "attack: "
local title2 = "defence: "

for i = 1, 100 do
-- local s = string.format("%s%d%s%d",title1,i,title2,i)
local s = title1 .. i .. title2 .. i
end

-- -------------------------------------------------------

local after = collectgarbage("count")
print(1024 * (after - before))

拼接字符串时,会自动调用tostring,将数字转为字符串,而使用format则可以避免创建这些短字符串。

table

先来一段Lua代码,尝试获取一个空表的堆内存占用:

1
2
3
4
5
6
7
8
9
10
collectgarbage("collect")
collectgarbage("stop")
local before = collectgarbage("count")
-- -------------------------------------------------------

local a = {}

-- -------------------------------------------------------
local after = collectgarbage("count")
print(1024 * (after - before))

得到的结果是56个字节,一个空表的内存占用。

结构和定义

表的类型定于与lobject.h第497行:

1
2
3
4
5
6
7
8
9
10
11
typedef struct Table {
CommonHeader;
lu_byte flags; /* 1<<p means tagmethod(p) is not present */
lu_byte lsizenode; /* log2 of size of 'node' array */
unsigned int sizearray; /* size of 'array' array */
TValue *array; /* array part */
Node *node;
Node *lastfree; /* any free position is before this position */
struct Table *metatable;
GCObject *gclist;
} Table;

对于一个空的表,数组部分和字典部分都为空,易知其结构中各成员直接加和得到的总的内存占用。

对于不为空的表,数组部分的数据存储于TValue *array,每个元素作为一个TValue存储;字典部分的数据存储于Node *nodeNode的定义如下:

1
2
3
4
typedef struct Node {
TValue i_val;
TKey i_key;
} Node;
1
2
3
4
5
6
7
typedef union TKey {
struct {
TValuefields;
int next; /* for chaining (offset for next node) */
} nk;
TValue tvk;
} TKey;

对于一个表来说,数组部分的数据,每个数据在表中占用16字节,字典部分的数据,每个数据在表中占用32字节。

获取表的长度

使用#取表的长度,会调用luaH_getn,其定义和涉及到的函数如下,在ltable.c中:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
static lua_Unsigned unbound_search (Table *t, lua_Unsigned j) {
lua_Unsigned i = j; /* i is zero or a present index */
j++;
/* find 'i' and 'j' such that i is present and j is not */
while (!ttisnil(luaH_getint(t, j))) {
i = j;
if (j > l_castS2U(LUA_MAXINTEGER) / 2) { /* overflow? */
/* table was built with bad purposes: resort to linear search */
i = 1;
while (!ttisnil(luaH_getint(t, i))) i++;
return i - 1;
}
j *= 2;
}
/* now do a binary search between them */
while (j - i > 1) {
lua_Unsigned m = (i+j)/2;
if (ttisnil(luaH_getint(t, m))) j = m;
else i = m;
}
return i;
}


/*
** Try to find a boundary in table 't'. A 'boundary' is an integer index
** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
*/
lua_Unsigned luaH_getn (Table *t) {
unsigned int j = t->sizearray;
if (j > 0 && ttisnil(&t->array[j - 1])) {
/* there is a boundary in the array part: (binary) search for it */
unsigned int i = 0;
while (j - i > 1) {
unsigned int m = (i+j)/2;
if (ttisnil(&t->array[m - 1])) j = m;
else i = m;
}
return i;
}
/* else must find a boundary in hash part */
else if (isdummy(t)) /* hash part is empty? */
return j; /* that is easy... */
else return unbound_search(t, j);
}

获取表的长度,涉及到数组部分和哈希部分。如果数组部分未满,在数组内二分查找,数组为空或数组满则在哈希部分查找。

在使用#获取数组长度,当数组部分有空洞(nil)时,可能出现与预期不一致的结果:

数组部分满时:

1
2
3
4
5
6
7
8
9
10
11
12
13
local a = {}

for i = 1,8 do
table.insert(a, i)
end

-- 数组部分 8/8

for i = 1,7 do
a[i] = nil
end

print(#a) -- 输出8

数组部分不满时,二分查找可能出现的于预期不符的情况:

1
2
3
4
5
6
7
8
9
10
11
12
13
local a = {}

for i = 1,7 do
table.insert(a,i)
end

-- 数组部分 7/8

a[1] = nil
print(#a) -- 输出7

a[6] = nil
print(#a) -- 输出5

插入数据

详见这里,插入数据过程中应避免表长度的获取。

rehash

数组扩容

向数组中插入新的元素时,数组部分会动态扩容,以下是一段动态扩容的演示代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
collectgarbage("collect")
collectgarbage("stop")

-- -------------------------------------------------------

local a = {}

for i = 1,20 do

local before = collectgarbage("count")
table.insert(a,i)
local after = collectgarbage("count")
print(i, 1024 * (after - before))

end

将输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1	16.0
2 16.0
3 32.0
4 0.0
5 64.0
6 0.0
7 0.0
8 0.0
9 128.0
10 0.0
11 0.0
12 0.0
13 0.0
14 0.0
15 0.0
16 0.0
17 256.0
18 0.0
19 0.0
20 0.0

在每次插入数据时,如果数组部分已满,就将数组部分重新分配,长度是原来的2倍。

字典部分rehash

演示字典部分扩容的代码,字典填满后会扩容并rehash:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
collectgarbage("collect")
collectgarbage("stop")

-- -------------------------------------------------------

local a = {}

for i = 1,20 do

local key = tostring(i)
local before = collectgarbage("count")
a[key] = i
local after = collectgarbage("count")
print(i, 1024 * (after - before))

end

将输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1	32.0
2 32.0
3 64.0
4 0.0
5 128.0
6 0.0
7 0.0
8 0.0
9 256.0
10 0.0
11 0.0
12 0.0
13 0.0
14 0.0
15 0.0
16 0.0
17 512.0
18 0.0
19 0.0
20 0.0

字典部分扩容的规则与数组相似。由于字典保存的是Node,而数组保存的是TValue,因此字典部分单位元素的存储空间也会比数组大。

收缩

前边提到了数组部分的扩张和字典的rehash扩张,某些情况下,数组和字典部分分配的空间会收缩:

当数组中的元素置为nil时,数组不会立即收缩,而是在字典部分触发rehash时,才重新计算数组部分的长度,下边的代码演示rehash引起的数组部分的收缩:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
collectgarbage("collect")
collectgarbage("stop")

-- -------------------------------------------------------

local a = {}

for i = 1, 8 do
table.insert(a,i)
end

-- 此时 数组部分8/8 字典部分0/0

for i = 2, 7 do
a[i] = nil
end

-- 此时 数组只有1和8有值 2-7都是空值
-- 数组2/8 哈希0/0
local before = collectgarbage("count")
a[9] = 9
-- 数组部分 1/1 字典部分 2/2
local after = collectgarbage("count")

print((after - before) * 1024)

local arrayElement = 16
local hashElement = 32

print(1 * arrayElement + 2 * hashElement - 8 * arrayElement)

在触发字典rehash的时候,将字典部分的数据并入数组:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
collectgarbage("collect")
collectgarbage("stop")

-- -------------------------------------------------------

local a = {}

for i = 5, 8 do
a[i] = i
end

-- 此时 数组部分0/0 字典部分4/4

local before = collectgarbage("count")

a[1] = 1

local after1 = collectgarbage("count")

a[2] = 2
a[3] = 3
a[4] = 4

-- 数组部分 8/8 哈希部分 0/0
local after2 = collectgarbage("count")

print((after1 - before) * 1024)
print((after2 - before) * 1024)

当触发rehash的时候,首先计算新的array部分和hash部分的尺寸。计算出可使数组部分填充率大于1/2的数组部分的长度,其余的key存入字典部分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i
*/
static void rehash (lua_State *L, Table *t, const TValue *ek) {
unsigned int asize; /* optimal size for array part */
unsigned int na; /* number of keys in the array part */
unsigned int nums[MAXABITS + 1];
int i;
int totaluse;
for (i = 0; i <= MAXABITS; i++) nums[i] = 0; /* reset counts */
na = numusearray(t, nums); /* count keys in array part */
totaluse = na; /* all those keys are integer keys */
totaluse += numusehash(t, nums, &na); /* count keys in hash part */
/* count extra key */
na += countint(ek, nums);
totaluse++;
/* compute new size for array part */
asize = computesizes(nums, &na);
/* resize the table to new computed sizes */
luaH_resize(L, t, asize, totaluse - na);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
** Count keys in array part of table 't': Fill 'nums[i]' with
** number of keys that will go into corresponding slice and return
** total number of non-nil keys.
*/
static unsigned int numusearray (const Table *t, unsigned int *nums) {
int lg;
unsigned int ttlg; /* 2^lg */
unsigned int ause = 0; /* summation of 'nums' */
unsigned int i = 1; /* count to traverse all array keys */
/* traverse each slice */
for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) {
unsigned int lc = 0; /* counter */
unsigned int lim = ttlg;
if (lim > t->sizearray) {
lim = t->sizearray; /* adjust upper limit */
if (i > lim)
break; /* no more elements to count */
}
/* count elements in range (2^(lg - 1), 2^lg] */
for (; i <= lim; i++) {
if (!ttisnil(&t->array[i-1]))
lc++;
}
nums[lg] += lc;
ause += lc;
}
return ause;
}


static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) {
int totaluse = 0; /* total number of elements */
int ause = 0; /* elements added to 'nums' (can go to array part) */
int i = sizenode(t);
while (i--) {
Node *n = &t->node[i];
if (!ttisnil(gval(n))) {
ause += countint(gkey(n), nums);
totaluse++;
}
}
*pna += ause;
return totaluse;
}

构造一个表

如果已知表中需要有哪些key,可以预先分配,详见这里,可以有效减少rehash的次数。

除此之外,预先指定key还能避免额外的内存分配:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
collectgarbage("collect")
collectgarbage("stop")

-- -------------------------------------------------------

local before1 = collectgarbage("count")

local a = {}

a[1] = 1
a[2] = 2
a[3] = 3

local after1 = collectgarbage("count")
print((after1 - before1) * 1024)

-- 56 + 16 * 4

-- -------------------------------------------------------

local before2 = collectgarbage("count")

local b = {1,2,3}

local after2 = collectgarbage("count")
print((after2 - before2) * 1024)

-- 56 + 16 * 3

遍历

在lua中使用ipairspairs对表进行遍历时,内部实际上调用的是next函数来获取下一个key。优先遍历数组部分,接下来遍历字典部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int luaH_next (lua_State *L, Table *t, StkId key) {
unsigned int i = findindex(L, t, key); /* find original element */
for (; i < t->sizearray; i++) { /* try first array part */
if (!ttisnil(&t->array[i])) { /* a non-nil value? */
setivalue(key, i + 1);
setobj2s(L, key+1, &t->array[i]);
return 1;
}
}
for (i -= t->sizearray; cast_int(i) < sizenode(t); i++) { /* hash part */
if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */
setobj2s(L, key, gkey(gnode(t, i)));
setobj2s(L, key+1, gval(gnode(t, i)));
return 1;
}
}
return 0; /* no more elements */
}

赋值:数组还是哈希

Q&A环节的一个问题,当我们向table中使用t[i] = v这样的操作插入一对键值且键i是整数的时候,这组值会保存在数组部分还是字典部分呢?

1
2
3
4
5
6
7
8
9
10
11
12
void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) {
const TValue *p = luaH_getint(t, key);
TValue *cell;
if (p != luaO_nilobject)
cell = cast(TValue *, p);
else {
TValue k;
setivalue(&k, key);
cell = luaH_newkey(L, t, &k);
}
setobj2t(L, cell, value);
}

当插入一个整数key时,先使用luaH_getint去获取TValue,如果找到则直接修改其值,否则走luaH_newkey在字典段创建新的键值对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
** search function for integers
*/
const TValue *luaH_getint (Table *t, lua_Integer key) {
/* (1 <= key && key <= t->sizearray) */
if (l_castS2U(key) - 1 < t->sizearray)
return &t->array[key - 1];
else {
Node *n = hashint(t, key);
for (;;) { /* check whether 'key' is somewhere in the chain */
if (ttisinteger(gkey(n)) && ivalue(gkey(n)) == key)
return gval(n); /* that's it */
else {
int nx = gnext(n);
if (nx == 0) break;
n += nx;
}
}
return luaO_nilobject;
}
}

在使用luaH_getint获取值时,先判断是否在数组段,如果是则直接返回对应位置的TValue,否则在字典部分找,找到返回,找不到则返回nil。

function

结构和定义

我们平时所说的函数,在lua中统一认为是闭包。闭包由函数原型和闭包变量组成。函数原型Proto和闭包Closures定义于lobject.h第407行和460行:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
** Function Prototypes
*/
typedef struct Proto {
CommonHeader;
lu_byte numparams; /* number of fixed parameters */
lu_byte is_vararg;
lu_byte maxstacksize; /* number of registers needed by this function */
int sizeupvalues; /* size of 'upvalues' */
int sizek; /* size of 'k' */
int sizecode;
int sizelineinfo;
int sizep; /* size of 'p' */
int sizelocvars;
int linedefined; /* debug information */
int lastlinedefined; /* debug information */
TValue *k; /* constants used by the function */
Instruction *code; /* opcodes */
struct Proto **p; /* functions defined inside the function */
int *lineinfo; /* map from opcodes to source lines (debug information) */
LocVar *locvars; /* information about local variables (debug information) */
Upvaldesc *upvalues; /* upvalue information */
struct LClosure *cache; /* last-created closure with this prototype */
TString *source; /* used for debug information */
GCObject *gclist;
} Proto;



/*
** Lua Upvalues
*/
typedef struct UpVal UpVal;


/*
** Closures
*/

#define ClosureHeader \
CommonHeader; lu_byte nupvalues; GCObject *gclist

typedef struct CClosure {
ClosureHeader;
lua_CFunction f;
TValue upvalue[1]; /* list of upvalues */
} CClosure;


typedef struct LClosure {
ClosureHeader;
struct Proto *p;
UpVal *upvals[1]; /* list of upvalues */
} LClosure;


typedef union Closure {
CClosure c;
LClosure l;
} Closure;


#define isLfunction(o) ttisLclosure(o)

#define getproto(o) (clLvalue(o)->p)

函数原型中保存函数相关的参数、指令、变量、内嵌函数、调试信息等。单个函数占用的堆内存很大程度上依赖于指令数量、参数和变量数量等。

不同的闭包可以共享同一份函数原型。当通过函数原型和upvalue得到闭包时,会比较新的闭包所持有的upvalue是否和原型中缓存的闭包的upvalue完全一致,如果完全一致,则直接使用同一个闭包。

闭包变量

闭包变量UpVal定义于lfunc.h第35行:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
** Upvalues for Lua closures
*/
struct UpVal {
TValue *v; /* points to stack or to its own value */
lu_mem refcount; /* reference counter */
union {
struct { /* (when open) */
UpVal *next; /* linked list */
int touched; /* mark to avoid cycles with dead threads */
} open;
TValue value; /* the value (when closed) */
} u;
};

多个闭包可以共享同一个upvalue。在外层函数返回之前,内层的闭包访问upvalue时更像是访问栈上的变量,v指向栈上的变量,所有的开放状态的upvalue以链表的形式存储于全局的虚拟机中(openupval)。当外层函数返回,调用栈收缩后,v会指向内部的value。

Upvalue的内存生命周期使用引用计数来管理。

参数类型

在函数内部使用的变量,有几种类型:作用域内的变量(调用栈内)、upvalue、全局变量。

lparser.c中获取变量的逻辑(第270行):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
Find variable with given name 'n'. If it is an upvalue, add this
upvalue into all intermediate functions.
*/
static void singlevaraux (FuncState *fs, TString *n, expdesc *var, int base) {
if (fs == NULL) /* no more levels? */
init_exp(var, VVOID, 0); /* default is global */
else {
int v = searchvar(fs, n); /* look up locals at current level */
if (v >= 0) { /* found? */
init_exp(var, VLOCAL, v); /* variable is local */
if (!base)
markupval(fs, v); /* local will be used as an upval */
}
else { /* not found as local at current level; try upvalues */
int idx = searchupvalue(fs, n); /* try existing upvalues */
if (idx < 0) { /* not found? */
singlevaraux(fs->prev, n, var, 0); /* try upper levels */
if (var->k == VVOID) /* not found? */
return; /* it is a global */
/* else was LOCAL or UPVAL */
idx = newupvalue(fs, n, var); /* will be a new upvalue */
}
init_exp(var, VUPVAL, idx); /* new or old upvalue */
}
}
}

优先访问局部变量和参数,其次逐层查找upvalue,最后查找全局变量。

尾调用

详见之前的文章,使用尾调用提高函数执行效率,避免溢出。

REFERENCE

https://www.lua.org/source/5.3/