面经-Lua高性能编程

本文最后更新于：2025年1月21日 凌晨

Local

在代码运行前，Lua会把源码预编译成一种中间码，类似于Java的虚拟机。这种格式然后会通过C的解释器进行解释，整个过程其实就是通过一个while循环，里面有很多的switch…case语句，一个case对应一条指令来解析。

自Lua 5.0之后，Lua采用了一种类似于寄存器的虚拟机模式。Lua用栈来储存其寄存器。每一个活动的函数，Lua都会其分配一个栈，这个栈用来储存函数里的活动记录。每一个函数的栈都可以储存至多250个寄存器，因为栈的长度是用8个比特表示的。

有了这么多的寄存器，Lua的预编译器能把所有的local变量储存在其中。这就使得Lua在获取local变量时其效率十分的高。

使用local引用global变量

Lua对本地局部变量的访问是一个O(1)的操作（等价于一个数组地址+偏移），而global变量的获取需要一次hash查找。local比global快很多（特别是在计算比较简单时，hash查找的开销反而是大头），比如：

1
2
3
4
5
6
7
8
9
10
-- bad
for i = 1, 1000000 do
    local x = math.sin(i)
end
 
-- good: 30% faster
local sin = math.sin
for i = 1, 1000000 do
    local x = sin(i)
end
LUA

除了本地local变量以外，upvalue的访问也比global快很多（访问上一层upvalue，等价于一次间接跳转之后再访问上一层函数的局部变量，基本还是一个O(1)的开销），比如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
-- bad
function foo (x)
    for i = 1, 1000000 do
        x = x + math.sin(i)
    end
    return x
end
 
-- good: 30% faster
local sin = math.sin
function foo (x)
    for i = 1, 1000000 do
        x = x + sin(i)
    end
    return x
end
LUA

使用local缓存table查找结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
-- bad
function foo (x)
    for i = 1, 1000000 do
        x = x + math.sin(i)
    end
    return x
end
 
-- good: 30% faster
local sin = math.sin
function foo (x)
    for i = 1, 1000000 do
        x = x + sin(i)
    end
    return x
end
LUA

3R原则

Reducing

避免创建新对象和节约内存

把table变成数组

把常量对象的创建放在循环的外面

xxxxxxxxxx void Awake(){    objects = new List();}​void CreateObject(){    Transform t = Instantiatie(prefab);    t.loactionPosition = Random.insideUnitSphere * 5f;    t.locationRotation = Random.rotation;    t.localScale = Vector3.one * Random.Range(0.1f, 1f);    objects.Add(t);}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
-- bad
for i = 1, n do
    local t = { 1, 2, 3, "hi" } --unnecessary redeclare
    local v = t[1] + 1
end
 
-- good: 1000% faster
local t = { 1, 2, 3, "hi" }
for i = 1, n do
    local v = t[1] + 1
end
 
-- bad
local func1 = function(a,b,func)
    return func(a+b)
end
 
for i=1,1000000 do
    local x = func1(1, 2, function(a) return a*2 end) --这里每次循环会创建一个匿名函数对象
end
 
-- good: 1000% faster
local func1 = function(a,b,func)
    return func(a+b)
end
 
local func2 = function(a)
    return a*2
end
 
for i=1,1000000 do
    local x = func1(1, 2, fun2) --重用循环外定义的func2
end
LUA

Reusing

复用对象

1
2
3
4
5
6
7
8
9
10
11
12
13
-- bad
local t = {}
for i = 1970, 2000 do
    t[i] = os.time({ year = i, month = 6, day = 14 }) --每次循环创建一个表
end
 
-- good: 1000% faster
local t = {}
local aux = { year = nil, month = 6, day = 14 }
for i = 1970, 2000 do
    aux.year = i -- 重用循环外定义的aux
    t[i] = os.time(aux)
end
LUA

Recycling

避免GC对象的创建

string有intenalize管理的开销，table需要开辟内存，lua中所有的function都是闭包，创建开销也不低，此外它们都会增加gc的开销。

传参时避免构造table

参数的数量不多时，尽量用独立的变量传递参数，而非构造一个table。

宿主语言接口调用

尽量在lua内部完成计算，调用宿主语言接口会带来明显的上下文切换开销，如果不是一个复杂的计算过程，不值的浪费这个开销。

table

Lua的表分为两个部分：数组(array)部分和哈希(hash)部分。数组部分包含所有从1到n的整数键，其他的所有键都储存在哈希部分中。

哈希部分其实就是一个哈希表，哈希表本质是一个数组，它利用哈希算法将键转化为数组下标，若下标有冲突(即同一个下标对应了两个不同的键)，则它会将冲突的下标上创建一个链表，将不同的键串在这个链表上，这种解决冲突的方法叫做：链地址法。

当我们把一个新键值赋给表时，若数组和哈希表已经满了，则会触发一个再哈希(rehash)。再哈希的代价是高昂的。首先会在内存中分配一个新的长度的数组，然后将所有记录再全部哈希一遍，将原来的记录转移到新数组中。新哈希表的长度是最接近于所有元素数目的2的乘方。

创建table时初始化数据

为了减少不必要的内存开销，table在创建时不会分配任何额外内存，早期几个元素的插入都必然导致rehash操作，这个特性对小table的创建影响特别显著，创建时一并指定初始化数据可以避免rehash的开销。

1
2
3
4
5
6
7
8
-- bad
local t = {}
t[1] = 1
t[2] = 2
t[3] = 3
 
-- good: 200% faster
local t = { 1, 2, 3}
LUA

高效的遍历*

paris和iparis有函数调用的开销，因此效率不高。在性能敏感的场合，最好缓存table的size，然后使用for loop。

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
-- pairs: 3.078 (217%)
for j,v in pairs(a) do
    x=v
end
 
--- ipairs: 3.344 (236%)
for j,v in ipairs(a) do
    x=v
end
 
-- for i=1,x do: 1.422 (100%)
for i=1,100 do
    x=a[i]
end
 
-- for i=1,#atable do 1.422 (100%)
for i=1,#a do
    x=a[i]
end
 
-- for i=1,atable_length do: 1.562 (110%)
local length = #a
for i=1,length do
    x=a[i]
end
LUA

高效的插入*

table.insert有函数调用的开销，因此性能不高。在性能敏感的场合，最好缓存table的size，然后指定下标赋值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
-- table.insert: 1.250 (727%)
local tinsert = table.insert
for i=1,1000000 do
    tinsert(a,i)
end
 
-- a[i]: 0.172 (100%)
for i=1,1000000 do
    a[i]=i
end
 
-- a[#a+1]=x: 0.453 (263%)
for i=1,1000000 do
    a[#a+1]=i
end
 
-- a[count++]=x: 0.203 (118%)
local count = 1
for i=1,1000000 do
    d[count]=i
    count=count+1
end
LUA

高效的unpack*

性能敏感的场合不要使用unpack，选择手动展开。

1
2
3
4
5
6
7
8
9
10
-- with [ ]: 0.485 (100%)
for i=1,1000000 do
    local x = min( a[1],a[2],a[3],a[4] )
end
 
-- unpack(): 1.093 (225%)
local unpack = table.unpack
for i=1,1000000 do
    local x = min( unpack(a) )
end
LUA

array或者hash*

table有array和hash两部分存储，一般来讲array的存储开销要比hash小一些，访问速度也比hash查找要快，可能的话尽量选array。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
-- 使用hash，内存开销最大 400%
polyline = {
  {x= 10.3, y = 98.5},
  {x= 10.3, y = 18.3},
  {x= 15.0, y = 98.5},
}  --(tables used: 1 + n)
 
-- 使用数组，内存开销降低 250%
polyline = {
  { 10.3, 98.5 },
  { 10.3, 18.3 },
  { 15.0, 98.5 },
  ...
} --(tables used: 1 + n)
 
-- 还可以进一步减少table本身的内存开销，只3个table 100%
polyline = {
  x = { 10.3, 10.3, 15.0, ... },
  y = { 98.5, 18.3, 98.5, ... }
} --(tables used: 3)
LUA

string

与其他主流脚本语言不同的是，Lua在实现字符串类型有两方面不同。

所有的字符串在Lua中都只储存一份拷贝。当新字符串出现时，Lua检查是否有其相同的拷贝，若没有则创建它，否则，指向这个拷贝。这可以使得字符串比较和表索引变得相当的快，因为比较字符串只需要检查引用是否一致即可；但是这也降低了创建字符串时的效率，因为Lua需要去查找比较一遍。

第二，所有的字符串变量，只保存字符串引用，而不保存它的buffer。这使得字符串的赋值变得十分高效。例如在Perl中，$x = $y，会将$y的buffer整个的复制到$x的buffer中，当字符串很长时，这个操作的代价将十分昂贵。而在Lua，同样的赋值，只复制引用，十分的高效。

但是只保存引用会降低在字符串连接时的速度。在Perl中，$s = $s . ‘x’和$s .= ‘x’的效率差距惊人。前者，将会获取整个$s的拷贝，并将’x’添加到它的末尾；而后者，将直接将’x’插入到$x的buffer末尾。

由于后者不需要进行拷贝，所以其效率和$s的长度无关，因为十分高效。

缓存字符串

避免在运行时构造字符串，尽量缓存那些常量字符串。

拼接字符串

大字符串的拼接，使用table.concat。

在lua中可以用table来模拟buffer

1
2
3
4
5
6
local s = ''
local t = {}
for i = 1,30000 do
    t[#t+1] = 'a'
end
s = table.concat(t, '')
LUA

语言之外的东西

使用LuaJIT，LuaJIT可以使你在不修改代码的情况下获得平均约5倍的加速。查看LuaJIT在x86/x64下的性能提升比。

第二、将瓶颈部分用C/C++来写。因为Lua和C的天生近亲关系，使得Lua和C可以混合编程。但是C和Lua之间的通讯会抵消掉一部分C带来的优势。

找工作
面经-Lua高性能编程
https://rorschachandbat.github.io/找工作/面经-Lua高性能编程/
作者
R
发布于
2024年12月22日
许可协议