Lua性能优化技巧
基本优化
在运行任何代码之前,Lua都会把源代码翻译(预编译)成一种内部的格式。这种格式是一个虚拟机指令序列,与真实的CPU所执行的机器码类似。之后,这个内部格式将会被由一个包含巨大的switch结构的while循环组成的C代码解释执行,switch中的每个case对应一条指令。
可能你已经在别处了解到,从5.0版开始,Lua使用一种基于寄存器的虚拟机。这里所说的虚拟机“寄存器”与真正的CPU寄存器并不相同,因为后者难于移植,而且数量非常有限。Lua使用一个栈(通过一个数组和若干索引来实现)来提供寄存器。每个活动的函数都有一个激活记录,也就是栈上的一个可供该函数存储寄存器的片段。因此,每个函数都有自己的寄存器<!--[if!supportFootnotes]-->[1]<!--[endif]-->。一个函数可以使用最多250个寄存器,因为每个指令只有8位用于引用一个寄存器。
由于寄存器数目众多,因此Lua预编译器可以把所有的局部变量都保存在寄存器里。这样带来的好处是,访问局部变量会非常快。例如,如果a和b是局部变量,语句a=a+b将只会生成一个指令:ADD001(假设a和b在寄存器里分别对应0和1)。作为对比,如果a和b都是全局变量,那么这段代码将会变成:
GETGLOBAL00;a
GETGLOBAL11;b
ADD001
SETGLOBAL00;a
因此,可以很简单地得出在Lua编程时最重要的性能优化方式:使用局部变量!
如果你想压榨程序的性能,有很多地方都可以使用这个方法。例如,如果你要在一个很长的循环里调用一个函数,可以预先将这个函数赋值给一个局部变量。比如说如下代码:
for i=1,1000000do
local x=math.sin(i)
end
比下面这段要慢30%:
local sin=math.sin
for i=1,1000000do
local x=sin(i)
end
访问外部局部变量(或者说,函数的上值)没有直接访问局部变量那么快,但依然比访问全局变量要快一些。例如下面的代码片段:
function foo(x)
for i=1,1000000do
x=x+math.sin(i)
end
return x
end
print(foo(10))
可以优化为在foo外声明一次sin:
local sin=math.sin
function foo(x)
for i=1,1000000do
x=x+sin(i)
end
return x
end
print(foo(10))
第二段代码比前者要0%。
尽管比起其他语言的编译器来说,Lua的编译器非常高效,但是编译依然是重体力活。因此,应该尽可能避免运行时的编译(例如使用loadstring函数),除非你真的需要有如此动态要求的代码,例如由用户输入的代码。只有很少的情况下才需要动态编译代码。
例如,下面的代码创建一个包含返回常数值1到100000的若干个函数的表:
local lim=10000
local a={}
for i=1,lim do
a[i]=loadstring(string.format("return%d",i))
end
print(a[10]())-->10
执行这段代码需要1.4秒。
通过使用闭包,我们可以避免使用动态编译。下面的代码只需要十分之一的时间完成相同的工作:
function fk(k)
return function()return k end
end
local lim=100000
local a={}
for i=1,lim do a[i]=fk(i)end
print(a[10]())-->10
关于表
一般情况下,你不需要知道Lua实现表的细节,就可以使用它。实际上,Lua花了很多功夫来隐藏内部的实现细节。但是,实现细节揭示了表操作的性能开销情况。因此,要优化使用表的程序(这里特指Lua程序),了解一些表的实现细节是很有好处的。
Lua的表的实现使用了一些很聪明的算法。每个Lua表的内部包含两个部分:数组部分和哈希部分。数组部分以从1到一个特定的n之间的整数作为键来保存元素(我们稍后即将讨论这个n是如何计算出来的)。所有其他元素(包括在上述范围之外的整数键)都被存放在哈希部分里。
正如其名,哈希部分使用哈希算法来保存和查键。它使用被称为开放地址表的实现方式,意思是说所有的元素都保存在哈希数组中。用一个哈希函数来获取一个键对应的索引;如果存在冲突的话(意即,如果两个键产生了同一个哈希值),这些键将会被放入一个链表,其中每个元素对应一个数组项。当Lua需要向表中添加一个新的键,但哈希数组已满时,Lua 将会重新哈希。重新哈希的第一步是决定新的数组部分和哈希部分的大小。因此,Lua遍历所有的元素,计数并对其进行归类,然后为数组部分选择一个大小,这个大小相当于能使数组部分超过一半的空间都被填满的2的最大的幂;然后为哈希部分选择一个大小,相当于正好能容纳哈希部分所有元素的2的最小的幂。
当Lua创建空表时,两个部分的大小都是0。因此,没有为其分配数组。让我们看一看当执行下面的代码时会发生什么:
local a={}
for i=1,3do
a[i]=true
end
这段代码始于创建一个空表。在循环的第一次迭代中,赋值语句a[1]=true触发了一次重新哈希;Lua将
数组部分的大小设为1,哈希部分依然为空;第二次迭代时a[2]=true触发了另一次重新哈希,将数组部分扩大为2.最终,第三次迭代又触发了一次重新哈希,将数组部分的大小扩大为4。
类似下面的代码
a={}
a.x=1;a.y=2;a.z=3
做的事情类似,只不过增加的是哈希部分的大小。
对于大的表来说,初期的几次重新哈希的开销被分摊到整个表的创建过程中,一个包含三个元素的表需要三次重新哈希,而一个有一百万个元素的表也只需要二十次。但是当创建几千个小表的时候,重新哈希带来的性能影响就会非常显著。
旧版的Lua在创建空表时会预选分配大小(4,如果我没有记错的话),以防止在初始化小表时产生的这些开销。但是这样的实现方式会浪费内存。例如,如果你要创建数百万个点(表现为包含两个元素的表),每个都使用了两倍于实际所需的内存,就会付出高昂的代价。这也是为什么Lua不再为新表预分配数组。
如果你使用C编程,可以通过Lua的API函数lua_createtable来避免重新哈希;除lua_State 之外,它还接受两个参数:数组部分的初始大小和哈希部分的初始大小<!--[if!supportFootnotes]-->[1]<!--[endif]-->。只要指定适当的值,就可以避免初始化时的重新哈希。需要警惕的是,Lua只会在重新哈希时收缩表的大小,因此如果在初始化时指定了过大的值,Lua可能永远不会纠正你浪费的内存空间。
当使用Lua编程时,你可能可以使用构造式来避免初始化时的重新哈希。当你写下{true,true, true}时,Lua知道这个表的数组部分将会有三个元素,因此会创建相应大小的数组。类似的,如果你写下{x=1,y=2,z=3},Lua也会为哈希部分创建一个大小为4的数组。例如,执行下面的代码需要2.0秒:
for i=1,1000000do
local a={}
a[1]=1;a[2]=2;a[3]=3
end
如果在创建表时给定正确的大小,执行时间可以缩减到0.7秒:
for i=1,1000000do
local a={true,true,true}
a[1]=1;a[2]=2;a[3]=3
end
但是,如果你写类似于{[1]=true,[2]=true,[3]=true}的代码,Lua还不够聪明,无法识别表达式(在本例中是数值字面量)指定的数组索引,因此它会为哈希部分创建一个大小为4的数组,浪费内存和CPU时间。
两个部分的大小只会在Lua重新哈希时重新计算,重新哈希则只会发生在表完全填满后,Lua需要插入新的元素之时。因此,如果你遍历一个表并清除其所有项(也就是全部设为nil),表的大小不会缩小。但是此时,如果你需要插入新的元素,表的大小将会被调整。多数情况下这都不会成为问题,但是,不要指望能通过清除表项来回收内存:最好是直接把表自身清除掉。
一个可以强制重新哈希的猥琐方法是向表中插入足够多的nil。例如:
a={}
lim=10000000
for i=1,lim do a[i]=i end--创建一个巨表
print(collectgarbage("count"))-->196626
for i=1,lim do a[i]=nil end--清除所有元素
print(collectgarbage("count"))-->196626
for i=lim+1,2*lim do a[i]=nil end--创建一堆nil元素
print(collectgarbage("count"))-->17lua字符串转数组
除非是在特殊情况下,我不推荐使用这个伎俩:它很慢,并且没有简单的方法能知道要插入多少nil才够。
你可能会好奇Lua为什么不会在清除表项时收缩表。首先是为了避免测试写入表中的内容。如果在赋值时检查值是否为nil,将会拖慢所有的赋值操作。第二,也是最重要的,允许在遍历表时将表项赋值为nil。例如下面的循环:
for k,v in pairs(t)do
if some_property(v)then
t[k]=nil–清除元素
end
end

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。