1

源代码 → 词法分析 → 语法分析 → 字节码生成 → VM 执行

1
2
3
4
5
6
7

-- test.lua
function add(a, b)
    return a + b
end

local result = add(3, 5)
print(result)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

main <test.lua:0,0> (5 instructions)
0+ params, 3 slots, 2 upvalues, 1 local, 3 constants, 0 functions

    1   [1] CLOSURE         0       0       ; 将闭包放入 R(0)
    2   [1] SETTABUP        0 0     0       ; 设置 upvalue _ENV["add"] = R(0)
    3   [4] GETTABUP        0 0     0       ; R(0) = _ENV["add"]
    4   [4] LOADI           1       3       ; R(1) = 3
    5   [4] LOADI           2       5       ; R(2) = 5
    6   [4] CALL            0 3     2       ; R(0..2) = R(0)(R(1), R(2))
    7   [5] GETTABUP        1 0     1       ; R(1) = _ENV["print"]
    8   [5] MOVE            2       0       ; R(2) = R(0)
    9   [5] CALL            1 2     1       ; R(1) = R(1)(R(2))
   10   [5] RETURN          0       1       ; return

function <test.lua:1,3> (2 instructions)
2 params, 3 slots, 0 upvalues, 2 locals, 0 constants, 0 functions

    1   [2] ADD             2       0 1     ; R(2) = R(0) + R(1)
    2   [3] RETURN          2       2       ; return R(2), 2 个返回值

 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

// Lua 源码 lvm.c 中 dispatch 循环的简化版
void luaV_execute(lua_State *L) {
    Instruction i;  // 当前指令（4字节）
    
    while (1) {  // 主循环
        i = *pc++;  // 取指令，PC 自增
        
        switch (GET_OPCODE(i)) {  // 根据操作码分发
            case OP_MOVE: {
                int a = GETARG_A(i);
                int b = GETARG_B(i);
                setobjs2s(L, ra + a, rb + b);  // R(A) = R(B)
                break;
            }
            case OP_ADD: {
                int a = GETARG_A(i);
                int b = GETARG_B(i);
                int c = GETARG_C(i);
                setfltvalue(ra + a, fltvalue(rb + b) + fltvalue(rc + c));
                break;  // R(A) = R(B) + R(C)
            }
            case OP_CALL: {
                // 函数调用——最复杂的指令之一
                // ...
                break;
            }
            // ... 几十种指令
        }
    }
}

1
2
3
4

┌─────────┬──────────┬──────────┬──────────┐
│ Opcode  │   A      │   B      │   C      │
│ (6 bit) │ (8 bit)  │ (9 bit)  │ (9 bit)  │
└─────────┴──────────┴──────────┴──────────┘

1
2
3

// 实际源码（lopcodes.h）中的实现
#define GET_OPCODE(i)   cast(OpCode, (i) >> 26)
// 把 32 位整数右移 26 位，剩下的 6 位就是操作码

1
2

// 对应到 Lua 代码就是：
R(A) = R(B)  // 把 R(b) 处的值复制到 R(a)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// Lua 源码 lobject.h 中的类型定义（简化）
typedef struct TValue {
    Value value_;       // 实际值（联合体，可能是 number/pointer/...）
    lu_byte tt_;        // 类型标记（当前存的是 number、string、table...）
} TValue;

typedef union Value {
    struct GCObject *gc;    // 需要 GC 的对象（table, function, string...）
    void *p;                // 裸指针
    lua_Number n;           // 双精度浮点数（Lua 里的 number）
    // ...
} Value;

1
2
3
4
5

// fltvalue(x) — 取出浮点数
// 就像 Lua 代码里的 local v = t[i]，取到的值是个 number

// setfltvalue(x, v) — 写入浮点数
// 就像 Lua 代码里的 t[i] = 3.14

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

case OP_ADD: {
    int a = GETARG_A(i);  // 解析操作数：目标槽索引（比如 2）
    int b = GETARG_B(i);  // 解析操作数：第一个加数槽索引（比如 0）
    int c = GETARG_C(i);  // 解析操作数：第二个加数槽索引（比如 1）
    
    // 1. fltvalue(rb + b) → 到 R0 槽读值（比如 100.0）
    // 2. fltvalue(rc + c) → 到 R1 槽读值（比如 50.0）
    // 3. 100.0 + 50.0 = 150.0
    // 4. setfltvalue(ra + a, ...) → 把 150.0 写入 R2 槽
    setfltvalue(ra + a, 
        fltvalue(rb + b) + fltvalue(rc + c));
    break;
}

1
2
3
4
5
6

Table 对象
├── 数组部分 (array part)  —— 存连续整数键 1..n
│   └── 一块连续内存，索引直接算偏移
│
└── 哈希部分 (hash part)   —— 存其他所有键
    └── 开放地址法的哈希表，键 -> 探测查找

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// lobject.h 中 Table 的定义（简化）
typedef struct Table {
    CommonHeader;           // GC 头（所有 GC 对象都有，包含 GC 标记位、类型等）
    lu_byte flags;          // 一些元方法的缓存标记
    lu_byte lsizenode;      // 哈希部分的 2^n 大小（即实际大小 = 2^lsizenode）
    unsigned int alimit;    // 数组部分的逻辑大小上限（见下方说明）
    TValue *array;          // 数组部分指针
    Node *node;             // 哈希部分指针
    Node *lastfree;         // 哈希自由链表的游标
    struct Table *metatable; // 元表
    GCObject *gclist;       // GC 链表
} Table;

1
2
3
4

local t = {}
t[1] = "a"
t[2] = "b"
t[3] = "c"

1
2
3
4
5
6

哈希表结构：
┌─────┬─────┬─────┬─────┐
│  0  │  1  │  2  │  3  │  ← 哈希槽位
└─────┴─────┴─────┴─────┘
   ↑                    ↑
  node              lastfree ← 从尾部往前搜索空位

1
2
3
4

#define CommonHeader struct GCObject *next; lu_byte tt; lu_byte marked
// next   = GC 链表指针（把所有 GC 对象串起来）
// tt     = 类型标记（这是 Table 还是 Function 还是 String...）
// marked = GC 标记位（用于标记-清除算法的白色/灰色/黑色标记）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

-- 场景 A：连续整数键，从 1 开始 → 全部进入数组部分 ✓
local t = {}
for i = 1, 100 do
    t[i] = i * 2  -- t[1]..t[100] 都在数组部分
end

-- 场景 B：从 0 开始 → 全进哈希部分 ✗
local t = {}
for i = 0, 99 do
    t[i] = i * 2  -- t[0] 不满足 1 <= i，进哈希部分
end

-- 场景 C：先插字符串键，再插整数键 → 整数键也可能进哈希 ✗
local t = {}
t["name"] = "张三"
t["age"] = 25
t[1] = "第一个"  -- 此时 Table 已分配哈希部分但可能没数组部分
t[2] = "第二个"  -- 也进哈希

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

-- 初始时 Table 是空的
local t = {}
-- Lua 内部：array = NULL, hash = NULL, alimit = 0

-- 插入第一个元素
t[1] = "a"
-- Lua：数组部分分配 1 个槽位
-- 内部状态：array = [a], hash = NULL, alimit = 1

-- 插入第二个元素
t[2] = "b"
-- Lua：数组部分可能要扩容到 2
-- 因为当前大小=1，装不下第 2 个
-- 内部状态：array = [a, b], alimit = 2

-- 插入第三个元素
t[3] = "c"
-- 数组部分又要扩容，2→4
-- 内部状态：array = [a, b, c, nil], alimit = 3

 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

// ltable.c 中 luaH_resize 的伪代码——每一步干什么
void luaH_resize(lua_State *L, Table *t, 
                 unsigned int new_array_size, 
                 unsigned int new_hash_size) {
    
    // 第一步：分配新内存（此时新旧并存）
    TValue *new_array = malloc(new_array_size * sizeof(TValue));
    Node *new_hash = malloc(new_hash_size * sizeof(Node));
    
    // 第二步：初始化新内存（所有槽位置为 nil）
    for (int i = 0; i < new_array_size; i++)
        new_array[i] = nil;
    for (int i = 0; i < new_hash_size; i++)
        new_hash[i] = nil;
    
    // 第三步：遍历旧数组部分，一个一个搬到新位置
    for (int i = 0; i < old_array_size; i++) {
        if (old_array[i] != nil) {
            // 根据 50% 规则决定放数组还是哈希
            if (应该放入新数组 & 新数组范围内) {
                new_array[i] = old_array[i];  // 直接搬
            } else {
                // 需要放入哈希部分——重新计算哈希位置
                int pos = hash(key) & (new_hash_size - 1);
                // 如果冲突，线性探测找空位（详情见2.5 节）
                while (new_hash[pos] != nil) 
                    pos = (pos + 1) & (new_hash_size - 1);
                new_hash[pos] = old_array[i];
            }
        }
    }
    
    // 第四步：遍历旧哈希部分，一个个重新插入
    for (int i = 0; i < old_hash_size; i++) {
        if (old_hash[i] != nil) {
            // 同样要重新计算：放数组还是放哈希？
            // 规则和第三步完全一样
            // ...
        }
    }
    
    // 第五步：替换指针，释放旧内存
    t->array = new_array;      
    t->node = new_hash;
    t->alimit = new_array_size;
    t->lsizenode = log2(new_hash_size);
    free(old_array);
    free(old_hash);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

local t = {}

-- 情况 1：数组部分满了，要插入新的整数键
for i = 1, 4 do
    t[i] = i  -- 第 4 次插入时可能触发 rehash（当前数组大小=4→8）
end

-- 情况 2：哈希部分满了，要插入新的非整数键
-- 哈希部分的装载因子达到 100% 左右触发
t["name"] = "张三"  -- 如果哈希部分已满，触发 rehash
t["age"] = 25

-- 情况 3：从数组部分移入哈希部分（破坏数组连续性时）
t[100] = "新元素"  -- 当前数组部分只有 4 个元素（1..4）
-- 插入 t[100] 后，Lua 检查 50% 规则：
-- 数组部分要扩展到 100？
-- 但 5/100 = 5% < 50%，不满足数组条件
-- 所以 t[100] 进哈希部分
-- 但这次操作可能会触发一次 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
31
32
33
34
35

-- 让我们逐步看一个 Table 从空到插入 7 个元素的完整过程
local t = {}

-- 初始状态：array = NULL, hash = NULL
-- 什么都没分配

t[1] = "a"
-- 第一次插入 → 分配 1 个数组槽
-- 状态：array[4]? 实际上 Lua 最小数组 = 4

t[2] = "b"
-- alimit = 2，还在范围内，不需要 rehash

t[3] = "c"
-- alimit = 3，不需要 rehash

t[4] = "d"
-- alimit = 4 === 当前数组大小，下一次插入需要 rehash

t[5] = "e"
-- ⚠ 插入第 5 个 → rehash 触发！
-- 旧状态：array[1..4] 满了
-- rehash 后：array 扩展到 8（2 倍）
-- 状态：array[1..5] = a,b,c,d,e, nil,nil,nil
-- 这次 rehash 搬了 4 个元素

-- 继续插入...
t[6] = "f"
t[7] = "g"
t[8] = "h"
-- alimit = 8 == 数组大小，下一次又要触发

t[9] = "i"
-- ⚠ rehash 触发！array 8→16
-- 搬了 8 个元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

插入次数     数组大小    是否 rehash     搬了多少元素
───────────────────────────────────────────────
t[1]          4         初始分配        0
t[2]          4         否              0
t[3]          4         否              0
t[4]          4         否              0
t[5]          8         ⚠ rehash       4
t[6..8]       8         否              0
t[9]         16         ⚠ rehash       8
t[10..16]    16         否              0
t[17]        32         ⚠ rehash       16

1
2
3
4
5

-- 重新看最开始的例子
local t = {}
for i = 1, 100000 do
    t[i] = i
end

1
2
3
4
5
6
7

数组扩容序列：4 → 8 → 16 → 32 → 64 → 128 → 256 → 512 → 1024 → 2048 → 4096 → 8192 → 16384 → 32768 → 65536 → 131072

从 4 到 131072（>=100000），一共扩容了 15 次
每次搬移的元素数量：4+8+16+32+64+128+256+512+1024+2048+4096+8192+16384+32768+65536 = 131068

总搬移量 ≈ 130,000 个单元
单位搬移成本：创建 TValue + 类型赋值

 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

-- 问题场景：频繁创建大 Table 的函数
function create_big_table()
    local t = {}
    for i = 1, 100000 do
        t[i] = i * 2
    end
    return t
end

-- 每秒被调用 10 次！
for frame = 1, 600 do  -- 60 秒 × 10fps = 600 帧
    local t = create_big_table()  -- 每帧创建 + 15 次 rehash
    process(t)
end
-- 总耗时：600 帧 × 15 次 rehash × ~0.2ms = 1800ms
-- 其中 1.8 秒花在 rehash 上！

-- 优化：复用同一个 Table
local t = {}
for frame = 1, 600 do
    for i = 1, 100000 do
        t[i] = i * 2  -- 重用 Table，不再触发 rehash
    end
    process(t)
end
-- 只需要第一次循环时的 15 次 rehash
-- 后续帧：0 次 rehash

1
2
3
4
5
6
7

// rehash 中创建的新数组和哈希表
TValue *new_array = malloc(...);   // 新内存 ← GC 要追踪
Node *new_hash = malloc(...);      // 新内存 ← GC 要追踪

// rehash 完成后旧内存被释放
free(old_array);  // 旧内存 ← GC 标记清除
free(old_hash);

 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

-- 方法一：用 dummy 值填充（最可靠）
local function prealloc_array(n)
    local t = {}
    for i = 1, n do
        t[i] = 0  -- 先填 0 占位，后续再覆盖
    end
    return t
end

-- 使用
local arr = prealloc_array(100000)
for i = 1, 100000 do
    arr[i] = compute(i)  -- 覆盖，零 rehash
end

-- 方法二：构造时直接初始化（如果值已知）
local arr = {}
for i = 1, 100000 do
    arr[i] = i  -- 边初始化边扩，反正只有 15 次 rehash
end

-- 方法三：多次复用同一个 Table（最佳实践）
local cache = {}  -- 只创建一次

function process_items(items)
    local n = #items
    
    -- 确保容量足够（如果 cache 太小，只补到够用，不缩）
    -- 利用 Table 只扩不缩的特性
    for i = 1, n do
        cache[i] = process(items[i])
    end
    -- 清理尾部多余的元素（上轮留下的）
    for i = n + 1, #cache do
        cache[i] = nil
    end
    return cache
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

-- 记住几条经验法则：

-- 规则 1：对纯数组 Table，扩容 15 次 vs 预分配
-- 差异大约只有几毫秒。如果你的函数不是 hot path，不需要纠结。

-- 规则 2：rehash 真正吃性能的地方是哈希部分
-- 因为数组部分就是"建立新数组，memcpy 旧数据"
-- 而哈希部分要对每个元素重新计算哈希位！有 O(n) 的哈希开销

-- 规则 3：大 Table 的 rehash 对 GC 的影响可能比 rehash 本身更大
-- 频繁创建大 Table → 大量 GC 对象 → GC 变慢

-- 规则 4：复用 Table 是性价比最高的优化
-- 不是省 rehash，是省 GC

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

拉链法（如 Java HashMap）：
┌─────┐
│ [0] │──→ [key1] → [key2] → ...  ← 每个槽位挂一个链表
├─────┤
│ [1] │──→ null                    ← 空槽位不占链表
├─────┤
│ [2] │──→ [key3] → ...
└─────┘

开放地址法（Lua Table）：
┌─────┬─────┬─────┬─────┐
│ [0] │ [1] │ [2] │ [3] │          ← 所有元素存在数组里，链表为 0
│ k1  │ k3  │ k2  │     │          ← 冲突了就往后放
└─────┴─────┴─────┴─────┘

1
2
3
4
5
6
7
8

// lobject.h 中的定义（简化）
typedef struct Node {
    TValue i_val;    // 值（和 TValue 一样，可以存任何类型）
    TKey i_key;      // 键（TKey 比 TValue 多一个 hash 缓存字段）
} Node;

// 哈希表：Node nodes[2^lsizenode]
// 比如 lsizenode = 3，则 nodes[0..7] 一共 8 个槽位

1
2

local t = {}
t["hello"] = "world"

1
2
3
4
5
6
7
8
9

// lstring.c 中字符串哈希的简化
unsigned int luaS_hash(const char *str, size_t len) {
    // Lua 使用改良的 Jenkins 哈希算法
    unsigned int h = (unsigned int)len;
    for (size_t i = 0; i < len; i++) {
        h ^= ((h << 5) + (h >> 2) + (unsigned char)str[i]);
    }
    return h;
}

1
2
3
4

// 假设当前哈希表大小是 4（2^2，lsizenode = 2）
int mainpos = hash("hello") & (size - 1);
// 等价于：0xABCD1234 & 3 = 2（取最后 2 位）
// 所以主位置是 index = 2

1
2
3
4
5
6
7
8

Node *main = &nodes[2];  // 取 index=2 的 Node

if (main->i_key.tt_ == LUA_TNIL) {
    // 主位置为空，直接占用
    main->i_key = "hello";
    main->i_val = "world";
    return;  // 插入完成！
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// 主位置 2 已经被其他 key（比如 "abc"）占了
// 开始"线性探测"：

// 检查位置 3
if (nodes[3].i_key.tt_ == LUA_TNIL) {
    // 空位，放入
    nodes[3].i_key = "hello";
    nodes[3].i_val = "world";
    return;
}

// 位置 3 也被占了？检查位置 0（绕回开头）
if (nodes[0].i_key.tt_ == LUA_TNIL) {
    nodes[0].i_key = "hello";
    nodes[0].i_val = "world";
    return;
}

// 位置 0 也被占了？检查位置 1
// 如果全部检查完都没空位 → 触发 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

哈希表（大小 = 4）：
┌─────┬─────┬─────┬─────┐
│ [0] │ [1] │ [2] │ [3] │
└─────┴─────┴─────┴─────┘
                ↑
               "hello" 的主位置 2

占用情况：
┌─────┬─────┬─────┬─────┐
│     │  k3 │  k1 │     │  ← k1 占了主位置 2
└─────┴─────┴─────┴─────┘

"hello" 插入过程：
┌─────┬─────┬─────┬─────┐
│     │  k3 │  k1 │     │
└─────┴─────┴─────┴─────┘
                ↑ 冲突！检查 2 已被 k1 占

┌─────┬─────┬─────┬─────┐
│     │  k3 │  k1 │ ←？ │  → 位置 3 为空，放入 "hello"
└─────┴─────┴─────┴─────┘

最终：
┌─────┬─────┬─────┬─────┐
│     │  k3 │  k1 │hel lo│
└─────┴─────┴─────┴─────┘

1

local v = t["hello"]  -- 查找 key = "hello"

 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

// ltable.c 中 luaH_get 的简化流程

// 1. 计算哈希值，定位主位置
unsigned int hash = luaS_hash("hello");
int pos = hash & (size - 1);  // 主位置 = 2

// 2. 检查主位置
Node *n = &nodes[pos];
if (n->i_key == "hello") {
    return &n->i_val;  // 找到了！一步到位
}

// 3. 主位置不是要找的 key → 线性探测
for (int i = 1; i < size; i++) {
    int probe = (pos + i) & (size - 1);  // 下一个探测位置
    n = &nodes[probe];
    
    if (n->i_key.tt_ == LUA_TNIL) {
        return NULL;  // 遇到空位 → key 不存在，结束查找
    }
    if (n->i_key == "hello") {
        return &n->i_val;  // 找到了！
    }
}

// 4. 整个表找遍了没有 → 返回 nil
return NULL;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

-- 用一个简单的实验来看装载因子的影响
-- 假设我们有 1000 个数据，分别用不同大小的哈希表

-- 情况 A：装载因子 50%（哈希表大小 2000）
-- 每 2 个位置里只有 1 个有数据
-- 探测的平均次数 ≈ 1.5 次
-- 性能：接近 O(1)

-- 情况 B：装载因子 80%（哈希表大小 1250）
-- 每 5 个位置里 4 个有数据
-- 探测的平均次数 ≈ 4~5 次
-- 性能：明显下降

-- 情况 C：装载因子 95%（哈希表大小 ~1053）
-- 几乎满了
-- 探测链可能很长，极端情况接近 O(n)！
-- 这就是为什么 Lua 在 rehash 时保持约 50% 空闲

1
2
3
4
5
6

装载因子和探测次数的关系（近似）：
 50% → 平均 1.5 次探测
 60% → 平均 2.0 次探测
 70% → 平均 3.0 次探测
 80% → 平均 5.0 次探测
 90% → 平均 10+ 次探测（性能骤降）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

-- 正常情况：哈希分布均匀，查找快
local t = {}
for i = 1, 1000 do
    t["key_" .. i] = i  -- 不同的哈希值均匀分布在表中
end
-- 每次查找平均 1~2 次探测

-- 极端情况：刻意构造哈希碰撞
-- Lua 字符串哈希对不同长度的字符串分布较好
-- 但数字（整数）作为哈希键时：
local t = {}
t[1] = "a"
t[2] = "b"
-- 整数键会先检查是否要进数组部分（见 2.3 的 50% 规则）
-- 如果进了哈希部分，哈希冲突情况取决于整数的分布

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

-- 弱引用表：key 或 value 是弱引用，不影响 GC 回收
local weak = setmetatable({}, {__mode = "v"})  -- value 弱引用

-- 不加弱引用的话，即使其他地方不再引用，table 里的引用会阻止 GC
local normal = {}
do
    local obj = {data = "large"}
    normal[1] = obj  -- obj 被 table 持有，不会 GC
end
-- 这里 obj 虽然超出作用域，但因为 normal[1] 还引用着它，内存不释放

-- 用弱引用 table 就不会阻止 GC
do
    local obj = {data = "large"}
    weak[1] = obj  -- 弱引用，obj 超出作用域后可被回收
end

 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

-- 写法一：动态增长（差）✗
-- 每次都 append，会触发多次 rehash
local function collect_items(items)
    local t = {}
    for i = 1, #items do
        table.insert(t, process(items[i]))  -- 可能每次都得扩容
    end
    return t
end

-- 写法二：预分配（好）✓
-- 减少 rehash 次数
local function collect_items(items)
    local n = #items
    local t = {}
    -- 预先写入 n 个 nil，强制数组扩展到 n
    for i = 1, n do
        t[i] = nil  -- Lua 5.4 中这个写法有效
    end
    -- 或者更直接的写法：预先填一个值
    -- for i = 1, n do t[i] = false end
    for i = 1, n do
        t[i] = process(items[i])  -- 不会再触发 rehash
    end
    return t
end

-- 写法三：提前知道大小就用 table.create（Lua 5.3+ 无此 API）
-- 可以用一个简单的辅助函数
local function new_table(narray, nhash)
    local t = {}
    if narray and narray > 0 then
        for i = 1, narray do
            t[i] = false  -- 预占位
        end
    end
    return t, narray  -- 返回数组大小，让调用方知道接着写
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

-- 错误示范：中间跳号 → 数组部分被破坏 ✗
local t = {}
t[1] = "A"
t[2] = "B"
t[4] = "D"  -- 跳过了 3！看看会怎样？
-- 此时数组部分是第 1~2 个元素，哈希部分存 (4 -> "D")
-- 但如果再插入 t[3] = "C"：
t[3] = "C"  -- 数组部分扩充到 4（填充率 4/4 = 100% > 50%）
-- t[1]..t[4] 全部进数组部分了

-- 但如果先写 t[4] 再写 t[2]：
local t = {}
t[4] = "D"  -- 数组大小 4，只有 1/4 = 25% < 50%，全进哈希！
t[2] = "B"  -- 也进哈希

1
2
3
4
5
6
7
8

-- 这是最有效的优化技巧，没有之一

-- 慢版本：反复从全局表查找 ✗
function slow_version()
    for i = 1, 100000 do
        math.sin(i)  -- 每次都要查 _ENV["math"]，再查 math["sin"]
    end
end

1
2

GETTABUP  R(0) _ENV "math"     -- R(0) = _ENV["math"]，即全局的 math 表
GETTABLE R(1)  R(0) "sin"      -- R(1) = R(0)["sin"]，即 math.sin 函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

-- 快版本：局部化引用 ✓
function fast_version()
    local sin = math.sin  -- 只查一次：_ENV["math"] → math["sin"] → 存到 local 变量
    for i = 1, 100000 do
        sin(i)  -- 直接调用 local 变量，零 Table 查找
    end
end

-- 测试结果（Lua 5.3）：
-- slow_version: 约 15ms
-- fast_version: 约 8ms
-- 快了近一倍！

 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

-- 复杂的数据结构访问 ✗
function update_player_slow(player)
    player.hp = player.hp - player.damage
    if player.hp <= 0 then
        player.state = "dead"
        player.death_time = os.time()
    end
    player.mp = player.mp + player.mp_regen
    if player.mp > player.max_mp then
        player.mp = player.max_mp
    end
end

-- 局部化优化 ✓
function update_player_fast(player)
    local hp = player.hp
    local damage = player.damage
    local mp = player.mp
    local mp_regen = player.mp_regen
    local max_mp = player.max_mp
    
    hp = hp - damage
    if hp <= 0 then
        player.state = "dead"
        player.death_time = os.time()
        player.hp = 0
    else
        player.hp = hp
    end
    
    mp = mp + mp_regen
    if mp > max_mp then
        mp = max_mp
    end
    player.mp = mp
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

-- table.insert 式写法 ✗
local t = {}
for i = 1, 1000 do
    table.insert(t, i)  -- 函数调用开销 + 边界检查 + 可能的 rehash
end

-- 直接赋值 ✓
local t = {}
for i = 1, 1000 do
    t[i] = i  -- 直接赋值，少了一次函数调用
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

-- 数组部分的 #t 是 O(1)
local arr = {1, 2, 3, 4, 5}
print(#arr)  -- 5，直接从 Table 头部的 alimit 字段读
-- 回顾第 2.2 节：alimit 是"逻辑大小上限"
-- 这里数组部分 5 个元素连续，alimit = 5，直接返回
-- 相当于：#t 就是 "intuitional array length"

-- 但如果数组部分有"空洞"（nil），Lua 需要二分查找
local arr = {1, 2, nil, 4, 5}
print(#arr)  -- ? 结果不确定！
-- Lua 的规则是：如果最后一个元素是 nil，# 会向前找第一个非 nil 的"边界"
-- 这里的结果可能是 2 或 5，取决于具体实现
-- 因为 alimit=5 但 t[5]=5 存在，但中间有 nil，二分后结果可能是 2（连续部分）或 5（最后一个非 nil）

-- 哈希表用 #t 几乎总是 O(n)
local dict = {a = 1, b = 2, c = 3}
print(#dict)  -- 0（哈希表没有数组部分，alimit = 0，# 返回 0）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

-- 自己维护长度的模式
local function create_queue()
    local queue = {}
    local size = 0  -- 自己记长度
    return {
        push = function(item)
            size = size + 1
            queue[size] = item
        end,
        pop = function()
            if size <= 0 then return nil end
            local item = queue[1]
            -- 前移（如果要保证 O(1) pop，应该用环形缓冲区）
            for i = 2, size do
                queue[i - 1] = queue[i]
            end
            queue[size] = nil
            size = size - 1
            return item
        end,
        size = function() return size end
    }
end

 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

-- 不好的写法：每次调用都创建新 Table ✗
function get_skill_info(skill_id)
    return {
        id = skill_id,
        name = get_skill_name(skill_id),
        cd = get_skill_cd(skill_id),
        damage = get_skill_damage(skill_id)
    }
end

-- 频繁调用：比如每秒 60 帧的战斗循环中
for _, skill in ipairs(player.skills) do
    local info = get_skill_info(skill.id)  -- 每秒创建 60 个 Table！
    process_skill(info)
end

-- 更好的做法：复用 Table ✓
local skill_info_pool = {}

local function fill_skill_info(info, skill_id)
    info.id = skill_id
    info.name = get_skill_name(skill_id)
    info.cd = get_skill_cd(skill_id)
    info.damage = get_skill_damage(skill_id)
    return info
end

-- 预先创建好
for i = 1, 10 do
    skill_info_pool[i] = {}
end

local pool_idx = 1
for _, skill in ipairs(player.skills) do
    local info = skill_info_pool[pool_idx]
    pool_idx = pool_idx + 1
    fill_skill_info(info, skill.id)
    process_skill(info)
end
-- 用完归还（或 pool_idx 重置回 1）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

-- 多返回值替代 Table ✗→✓
-- 差：用 Table 包装返回值
function get_position()
    return {x = 100, y = 200, z = 300}
end
local pos = get_position()
print(pos.x, pos.y, pos.z)  -- 创建了临时 Table

-- 好：多返回值
function get_position_fast()
    return 100, 200, 300  -- 零分配
end
local x, y, z = get_position_fast()
print(x, y, z)

1
2
3
4
5
6
7

纯解释执行：
  源码 → 字节码 → [读取 → 分发 → 执行] × N 条指令

JIT 执行：
  源码 → 字节码 → [解释执行，同时统计热度]
                 → 热点达到阈值 → 编译为机器码
                 → 直接执行机器码（相当于在内存里生成了 C 代码编译后的结果）

1
2
3

for i = 1, 1000000 do
    sum = sum + arr[i]  -- 这条路径被反复执行
end

1
2
3
4
5
6
7

1. 解释执行，同时记录每条指令的执行次数（hot count）
2. 某个循环入口 hot count 达到阈值（默认 1000）
3. 开始录制（Record）：记录当前 Trace 执行的所有操作
4. 一路录到循环结束，生成 SSA IR（中间表示）
5. 优化 IR（常量折叠、死代码消除等）
6. 生成机器码（Emit）
7. 下次再走到这个入口，直接跳转执行机器码

1
2
3
4
5
6
7
8
9

-- Lua 源码
x = a + b
x = x * 2
y = x + c

-- SSA 形式（每个变量只赋值一次，重命名多次赋值）
x1 = a + b     -- 第一次赋值：x1
x2 = x1 * 2    -- 第二次赋值：用新名字 x2，明确知道 x1 === a + b
y1 = x2 + c    -- 只用 x2，不会误用旧值

1
2
3
4

普通写法（非 SSA）：                     SSA 写法：
  x = a + b                               x1 = a + b
  ...   ← 万一这里有人改了 x？              ...   ← x1 不可能被改（只赋一次值）
  y = x * 2    ← 这个 x 是哪个？            y1 = x1 * 2  ← 明确就是 a+b

1
2
3
4
5
6
7

for i = 1, 1000000 do
    if arr[i] > 0 then
        sum = sum + arr[i]   -- 热点路径 A（95% 的情况）
    else
        other_sum = other_sum + arr[i]  -- 分支 B（5% 的情况）
    end
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

    ┌──────────┐
    │ 主 Trace  │  ← 循环入口（热）
    └────┬─────┘
         │
    ┌────▼──────┐
    │ arr[i]>0? │——否——→ ┌───────────┐
    └────┬──────┘        │ Side Trace │
         │ 是            └─────┬─────┘
    ┌────▼─────┐              │
    │ sum +=   │              │
    │ arr[i]   │              │
    └────┬─────┘              │
         │                    │
         └─────────┬──────────┘
                   ▼
            ┌──────────┐
            │ 循环尾    │
            │ 跳回开头  │
            └──────────┘

 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

-- 以下操作会导致 Trace 中止（NYI），退回解释执行
-- 你的代码再热也不会被 JIT 编译！

-- 1. 使用不支持的库函数
local r = math.fmod(10, 3)  -- math.fmod 是 NYI！用 % 运算符代替

-- 2. 字符串连接太复杂
local s = "a" .. "b" .. "c"  -- 简单连接没问题
local s = table.concat({"a", "b", "c"})  -- 这个更好

-- 3. 创建新函数（闭包）
funcs = {}
for i = 1, 1000 do
    funcs[i] = function() return i end  -- 每次迭代创建闭包 → 中止 Trace！
end
-- 优化：在外面创建函数
function make_counter(i)
    return function() return i end
end
for i = 1, 1000 do
    funcs[i] = make_counter(i)  -- 虽然也创建闭包，但不阻塞 JIT
    -- 实际上这也中止... 更好的做法是重构设计
end

-- 4. 协程操作
coroutine.yield()  -- NYI

-- 5. pcall / xpcall 内部的长循环
-- pcall 内部代码很难被 JIT 编译

-- 6. FFI callback（回调 C 函数）
ffi.cdef("void cb(int);")
local cbfunc = ffi.cast("void (*)(int)", function(i) 
    -- 这里的代码不会被 JIT
end)

1
2
3
4
5
6
7

# 启动 LuaJIT 并开启 JIT 日志
luajit -jdump=ix mycode.lua
# -j 表示 JIT 控制
# dump 表示 dump 编译结果
# i 显示 IR（中间表示）
# x 显示机器码
# mycode.lua 是你要分析的脚本

1

luajit -jv mycode.lua

1
2
3
4
5
6
7
8

-- 代码里查看 JIT 状态
local jit = require("jit")

-- 打印当前 JIT 状态
print(jit.status())

-- 查看某个函数是否被 JIT 编译
-- 用 jit.util 模块（只有开启了 -j 才能用）

 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

-- ✅ 好：简单的数值循环
local sum = 0
for i = 1, 1000000 do
    sum = sum + i
end

-- ✅ 好：简单的 Table 遍历
local arr = {}
for i = 1, 10000 do
    arr[i] = i
end
local sum = 0
for i = 1, #arr do
    sum = sum + arr[i]
end

-- ❌ 差：频繁创建 Table
local sum = 0
for i = 1, 10000 do
    local t = {a = i, b = i * 2}
    sum = sum + t.a + t.b
end
-- 如果可以，把 t 挪到外面复用

-- ❌ 差：使用 string 库的部分函数
local s = "hello world"
for i = 1, 10000 do
    s = string.gsub(s, "l", "x")  -- string.gsub 是 NYI，会中止 JIT
end
-- 用 LuaJIT 的 FFI 调用 C 的 str_replace 会更快

-- ❌ 差：混用不同类型的值
local t = {}
for i = 1, 10000 do
    t[i] = i  -- 全是 number
end
t[5000] = "hello"  -- 突然变成 string！→ JIT 编译器要生成 guard
-- LuaJIT 会为 number 生成一条 Trace，但遇到 string 要退出到解释器
-- 尽量保持类型稳定！

 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

-- 纯 Lua 版本（慢）
local x = 0
for i = 1, 1000000 do
    x = x + math.sqrt(i)
end

-- FFI 版本（快 10 倍+）
local ffi = require("ffi")
ffi.cdef("double sqrt(double);")  -- 声明 C 函数

local x = 0
for i = 1, 1000000 do
    x = x + ffi.C.sqrt(i)  -- 直接调 C 的 sqrt，通过 JIT 内联成一条机器码
end

-- 更极致：用 C 结构体代替 Lua Table
local ffi = require("ffi")

-- 声明一个 C 结构体
ffi.cdef[[
    typedef struct {
        double x;
        double y;
        double z;
    } vec3;
]]

-- 创建 C 结构体数组（连续内存，不是 Table 数组！）
local points = ffi.new("vec3[?]", 10000)

-- 访问比 Table 快很多
for i = 0, 9999 do  -- C 数组从 0 开始
    points[i].x = points[i].x + 1.0
    -- 编译后就是几条 CPU 指令：mov [eax+offset], ...
    -- 而 Table 需要查哈希、调 GC 保护...
end

1
2
3
4
5
6
7
8

影响从大到小排列：

1. 算法优化（O(n²) → O(n log n)）：收益最大，先做
2. 减少 Table 创建（对象池 / 复用）：减少 GC 压力
3. local 缓存引用（math.sin → local sin）：几乎零成本，收益明显
4. Table 布局优化（预分配、连续索引）：对大数据集有效
5. JIT 友好（避免 NYI、保持类型稳定）：用 LuaJIT 时才有关
6. 微优化（用 for 代替 ipairs、用 + 代替 concat）：最后考虑

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

-- 写完代码后，对照检查：

-- [ ] 热点路径上的全局函数/变量是否 local 化了？
-- [ ] 循环内有没有创建新 Table/闭包？
-- [ ] 大的 Table 是否预分配了？
-- [ ] 整数键是否从 1 开始连续？
-- [ ] 频繁调用的 C API 是否在初始化时缓存了引用？
-- [ ] 用 LuaJIT 时：有无 NYI 函数阻塞 JIT？
-- [ ] 用 LuaJIT 时：循环内类型是否稳定？
-- [ ] 是否可以用多返回值代替临时 Table？
-- [ ] 字符串拼接用 .. 还是 table.concat？（大量拼接用 concat）