长安长夜Saint 2019-06-20
此为 Lua Programming Gems 一书的第二章:Lua Performance Tips,作者为 Roberto Ierusalimschy。
我的翻译以 网上别人的翻译 为基础,做了比较大的修改,读起来更通顺。
关于性能优化的两条格言:
规则 1:不要优化
规则 2:还是不要优化(仅限专家)
不要在缺乏恰当度量(measurements)时试图去优化软件。编程老手和菜鸟之间的区别不是说老手更善于洞察程序的性能瓶颈,而是老手知道他们并不善于此。
做性能优化离不开度量。优化前度量,可知何处需要优化。优化后度量,可知「优化」是否确实改进了代码。
运行代码之前,Lua 会把源代码翻译(预编译)成一种内部格式,这种格式由一连串虚拟机的指令构成,与真实 CPU 的机器码很相似。接下来,这一内部格式交由 C 代码来解释,基本上就是一个 while
循环,里面有一个很大的 switch
,一种指令对应一个 case
。
也许你已从他处得知,自 5.0 版起,Lua 使用了一个基于寄存器的虚拟机。这些「寄存器」跟 CPU 中真实的寄存器并无关联,因为这种关联既无可移植性,也受限于可用的寄存器数量。Lua 使用一个栈(由一个数组加上一些索引实现)来存放它的寄存器。每个活动的(active)函数都有一份活动记录(activation record),活动记录占用栈的一小块,存放着这个函数对应的寄存器。因此,每个函数都有其自己的寄存器。由于每条指令只有 8 个 bit 用来指定寄存器,每个函数便可以使用多至 250 个寄存器。
Lua 的寄存器如此之多,预编译时便能将所有的局部变量存到寄存器中。所以,在 Lua 中访问局部变量是很快的。举个例子, 如果 a
和 b
是局部变量,语句 a = a + b
只生成一条指令:ADD 0 0 1
(假设 a
和 b
分别在寄存器 0
和 1
中)。对比之下,如果 a
和 b
是全局变量,生成上述加法运算的指令便会如下:
GETGLOBAL 0 0 ; a GETGLOBAL 1 1 ; b ADD 0 0 1 SETGLOBAL 0 0 ; a
所以,不难证明,要想改进 Lua 程序的性能,最重要的一条原则就是:使用局部变量(use locals)!
除了一些明显的地方外,另有几处也可使用局部变量,可以助你挤出更多的性能。比如,如果在很长的循环里调用函数,可以先将这个函数赋值给一个局部变量。这个代码:
for i = 1, 1000000 do local x = math.sin(i) end
比如下代码慢 30%:
local sin = math.sin for i = 1, 1000000 do local x = sin(i) end
访问外层局部变量(也就是外一层函数的局部变量)并没有访问局部变量快,但是仍然比访问全局变量快。考虑如下代码:
function foo(x) for i = 1, 1000000 do x = x + math.sin(i) end return x end print(foo(10))
我们可以通过在 foo
函数外面定义一个 sin
来优化它:
local sin = math.sin function foo(x) for i = 1, 1000000 do x = x + sin(i) end return x end print(foo(10))
第二段代码比第一段快 30%。
与其他语言的编译器相比,Lua 的编译器算是比较高效的,尽管如此,编译仍是一项繁重的任务。所以,应尽量避免在程序中编译代码(比如,使用 loadstring
函数)。除非需要真正动态地执行代码,比如代码是由用户输入的,其他情况则很少需要编译动态的代码。
举个例子,下面的代码创建一个包含 10000 个函数的表,表中的函数分别返回常量 1
到 10000
:
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 秒。
使用闭包,可以避免动态编译。下面的代码创建同样的 10000 个函数只用了 1/10 的时间(0.14秒):
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
通常,使用表(table)时并不需要知道它的实现细节。事实上,Lua 尽力避免把实现细节暴露给用户。然而这些细节还是在表操作的性能中暴露出来了。所以,为了高效地使用表,了解一些 Lua 实现表的方法,不无益处。
Lua 实现表的算法颇为巧妙。每个表包含两部分:数组(array)部分和哈希(hash)部分,数组部分保存的项(entry)以整数为键(key),从 1 到某个特定的 n,(稍后会讨论 n 是怎么计算的。)所有其他的项(包括整数键超出范围的)则保存在哈希部分。
顾名思义,哈希部分使用哈希算法来保存和查找键值。它使用的是开放寻址(open address)的表,意味着所有的项都直接存在哈希数组里。键值的主索引由哈希函数给出;如果发生冲突(两个键值哈希到相同的位置),这些键值就串成一个链表,链表的每个元素占用数组的一项。
当 Lua 想在表中插入一个新的键值而哈希数组已满时,Lua 会做一次重新哈希(rehash)。重新哈希的第一步是决定新的数组部分和哈希部分的大小。所以 Lua 遍历所有的项,并加以计数和分类,然后取一个使数组部分用量过半的最大的 2 的指数值,作为数组部分的大小。而哈希部分的大小则是一个容得下剩余项(即那些不适合放在数组部分的项)的最小的 2 的指数值。
当 Lua 创建一个空表时,两部分的大小都是 0,因此也就没有为它们分配数组空间。看看如下代码运行时会发生些什么:
local a = {} for i = 1, 3 do a[i] = true end
一开始创建一个空表。循环的第一次迭代时,赋值语句 a[1] = true
触发了一次重新哈希;Lua 将表中的数组部分大小设为 1,而哈希部分仍为空。循环的第二次迭代时,赋值语句 a[2] = true
又触发了一次重新哈希,现在,表中的数组部分大小为 2。最后,第三次迭代还是触发了一次重新哈希,数组部分的大小增至 4。
像下面这样的代码:
a = {} a.x = 1; a.y = 2; a.z = 3
做的事情类似,大小增长的却是表的哈希部分。
对于大型的表,这些初始的开销将会被整个创建过程平摊:创建 3 个元素的表需要进行 3 次重新哈希,而创建一百万个元素的表只需要 20 次。但是当你创建几千个小表时,总开销就会很显著。
老版的 Lua 在创建空表时会预分配一些空位(如果没记错,是 4),来避免这种创建小表时的初始开销。不过,这样又有浪费内存之嫌。比如,以仅有两个项的表来表示点,每个点使用的内存就是真正所需内存的两倍,那么创建几百万个点将会使你付出高昂的代价。这就是现在 Lua 不为空表预分配空位的原因。
如果你用的是 C,可以通过 Lua 的 API 函数 lua_createtable
来避免这些重新哈希。这个函数除了司空见惯的参数 lua_State
外,另接受两个参数:新表数组部分的初始大小和哈希部分的初始大小。只要这两个参数给得恰当,就能避免初始时的重新哈希。不过需要注意的是,Lua 只在重新哈希时才有机会去收缩(shrink)表。所以,如果你指定的初始大小大于实际所需,空间的浪费 Lua 可能永远都不会为你纠正。
如果你用的是 Lua,可以通过构造器(constructors)来避免那些初始的重新哈希。当你写下 {true, true, true}
时,Lua 就会事先知道新表的数组部分需要 3 个空位,并创建一个相应大小的表。与此类似,当你写下 {x = 1, y = 2, z = 3}
时,Lua 就创建一个哈希部分包含 4 个空位的表。举例来说,下面的循环运行了 2.0 秒:
for i = 1, 1000000 do local a = {} a[1] = 1; a[2] = 2; a[3] = 3 end
如果以正确的大小来创建这个表,运行时间就降到了 0.7 秒:
for i = 1, 1000000 do local a = {true, true, true} a[1] = 1; a[2] = 2; a[3] = 3 end
然而,当你写下形如 {[1] = true, [2] = true, [3] = true}
这样的语句时,Lua 并没有聪明到能够检测出给定的表达式(指那些字面数字)是在描述数组下标,所以它创建了一个哈希部分有 4 个空位的表,既浪费内存也浪费 CPU 时间。
表的两个部分的大小只在表重新哈希时计算,而重新哈希只在表已全满而又需要插入新元素时才会发生。因此,当你遍历一个表并把个中元素逐一删除时(即设它们为 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")) --> 17
除非特殊情况需要,我并不推荐这种手法,因为这样做很慢,而且要知道多少元素才算「足够」,也没有简单易行的方法。
你可能会想,Lua 为什么不在我们插入 nil
时收缩表的大小呢?首先,是为了避免对插入元素的检查;一条检查 nil
赋值的语句将会拖慢所有的赋值语句。其次,也是更重要的,是为了允许在遍历表时对元素赋 nil
值。考虑如下循环:
for k, v in pairs(t) do if some_property(v) then t[k] = nil -- 删除这个元素 end end
如果 Lua 在 nil
赋值后进行重新哈希,那么这个遍历就被破坏了。
如果你想删除表中的所有元素,正确的方法是使用一个简单的循环:
for k in pairs(t) do t[k] = nil end
或者使用"聪明"一点的方法:
while true do local k = next(t) if not k then break end t[k] = nil end
不过,这个循环在表很大时会很慢。调用函数 next
时,如果没有传入前一个键值,返回的便是表的「第一个」元素(以某种随机顺序)。(译:「第一个」之所以加引号,是指就表内部的数组结构而言的第一个元素,「以某种随机顺序」则是从表的角度或用户使用表的角度来说。)为此,next
从头遍历表的数组空间(译:包含数组和哈希两部分),查找一个非 nil
元素。随着循环逐一将这些第一个元素设为 nil
,查找第一个非 nil
元素变得越来越久。结果是,为了清除一个有 100000 个元素的表,这个“聪明”的循环用了 20 秒,而使用 pairs
遍历表的循环只用了 0.04 秒。
和表一样,了解 Lua 实现字符串的细节对高效地使用字符串也会有所帮助。
Lua 实现字符串的方式和大多数其他的脚本语言有两点重要的区别。其一,Lua 的字符串都是内化的(internalized);这意味着字符串在 Lua 中都只有一份拷贝。每当一个新字符串出现时,Lua 会先检查这个字符串是否已经有一份拷贝,如果有,就重用这份拷贝。内化(internalization)使字符串比较及表索引这样的操作变得非常快,但是字符串的创建会变慢。
其二,Lua 的字符串变量从来不会包含字符串本身,包含的只是字符串的引用。这种实现加快了某些字符串操作。比如,对 Perl 来说,如果你写下这样的语句:$x = $y
,$y
包含一个字符串,这个赋值语句将复制 $y
缓冲区里的字符串内容到 $x
的缓冲区中。如果字符串很长,这一操作代价将非常高。而对 Lua 来说,这样的赋值语句只不过复制了一个指向实际字符串的指针。
这种使用引用的实现,使某种特定形式的字符串连接变慢了。在 Perl 里,$s = $s . "x"
和 $s .= "x"
这两者是很不一样的。前一个语句,先得到一份 $s
的拷贝,然后往这份拷贝的末尾加上 "x"
。后一个语句,只是简单地把 "x"
追加到变量 $s
所持有的内部缓冲区上。所以,第二种连接形式跟字符串大小是无关的(假设缓冲区有足够的空间来存放连接的字符串)。如果在循环中执行这两条语句,那么它们的区别就是算法复杂度的线性阶和平方阶的区别了。比如,以下循环读一个 5MB 的文件,几乎用了 5 分钟:
$x = ""; while (<>) { $x = $x . $_; }
如果将 $x = $x . $_
替换成 $x .= $_
,则只要 0.1 秒!
Lua 并没有提供这第二种较快的方法,因为 Lua 的变量并没有与之关联的缓冲区。所以,我们必须使用一个显式的缓冲区:包含字符串片段的表就行。以下循环还是读 5MB 的文件,费时 0.28 秒。没 Perl 那么快,不过也不赖。
local t = {} for line in io.lines() do t[#t + 1] = line end s = table.concat(t,"\n")
当处理 Lua 资源时,我们应当遵守跟利用地球资源一样的 3R 原则。
减少(reduce)是最简单的一种途径。有几种方法可以避免创建对象。例如,如果你的程序使用了大量的表,或许可以考虑改变它的数据表示。举个简单的例子,假如你的程序需要处理折线(polyline)。在 Lua 里,折线最自然的表示是使用一个点的列表,像这样:
polyline = { { x = 10.3, y = 98.5 }, { x = 10.3, y = 18.3 }, { x = 15.0, y = 98.5 }, ... }
这种表示虽然自然,折线较大时却不经济,因为每个点都要用一个表。下面这种表示改用数组,内存略为节省:
polyline = { { 10.3, 98.5 }, { 10.3, 18.3 }, { 15.0, 98.5 }, ... }
对于一条有一百万个点的折线,这种改变使内存用量从 95KB 降到 65KB。当然,作为代价,程序的可读性有所损失:p[i].x
要比 p[i][4]
易懂得多。
还有一个更经济的方法,用两个列表,一个存 x
坐标的值,一个存 y
坐标的值:
polyline = { x = { 10.3, 10.3, 15.0, ...}, y = { 98.5, 18.3, 98.5, ...} }
之前的 p[i].x
现在就是 p.x[i]
。使用这种方式,一条有一百万个点的折线只需 24KB 的内存。
循环是寻找降低不必要资源创建的好地方。例如,如果在循环中创建了一个常量的(constant)表,便可以把表移到循环之外,或者甚至可以移到外围函数之外。比较如下两段代码:
function foo (...) for i = 1, n do local t = {1, 2, 3, "hi"} -- 做一些不改变 t 的操作 ... end end
local t = {1, 2, 3, "hi"} -- 一次性地创建 t function foo (...) for i = 1, n do -- 做一些不改变 t 的操作 ... end end
同样的技巧也可以用于闭包,只要移动时不致越出闭包所需变量的作用域。例如,考虑以下函数:
function changenumbers (limit, delta) for linein io.lines() do line = string.gsub(line, "%d+", function (num) num = tonumber(num) if num >= limit then return tostring(num + delta) end -- else return nothing, keeping the original number end) io.write(line, "\n") end end
只要将内部(inner)函数移到循环之外,就可避免为每一行都创建一个新的闭包:
function changenumbers (limit, delta) local function aux (num) num = tonumber(num) if num >= limit then return tostring(num + delta) end end for linein io.lines() do line = string.gsub(line, "%d+", aux) io.write(line, "\n") end end
不过,不能将函数 aux
移到函数 changenumbers
之外,那样的话,函数 aux
就不能访问变量 limit
和 delta
了。
很多字符串的处理,都可以通过在现有字符串上使用下标,来避免创建不必要的新字符串。例如,函数 string.find
返回的是给定模式出现的位置,而不是一个与之匹配的字符串。返回下标,就避免了在成功匹配时创建一个新的(子)字符串。若有需要,可以再通过函数 string.sub
来获取匹配的子字符串。
即使不能避免使用新的对象,也可以通过 重用(reuse)来避免创建新的对象。对字符串来说,重用是没有必要的,因为 Lua 已经替我们这样做了:所有的字符串都是内化的(internalized),因此只要可能就会重用。对表来说,重用就显得卓有成效了。举一个常见的例子,让我们回到在循环内创建表的情况。不同的是,这次的表是可变的(not constant)。不过,往往只需简单的改变内容,还是可以在所有的迭代中重用同一个表的。考虑以下代码:
local t = {} for i = 1970, 2000 do t[i] = os.time({year = i, month = 6, day = 14}) end
以下代码与之等价,但是重用了表:
local t = {} local aux = {year = nil, month = 6, day = 14} for i = 1970, 2000 do aux.year = i t[i] = os.time(aux) end
实现重用的一种特别有效的方法是记忆化(memoizing)。基本想法非常简单:对于一个给定的输入,保存其计算结果,当遇到同样的输入时,程序只需重用之前保存的结果。
来看看 LPeg
(Lua 中一个新的模式匹配的包),它使用记忆化的方式颇为有趣。LPeg
把每个模式都编译成一种内部表示,对负责匹配的分析器来说,这种表示就是一种「程序」。这种编译相对于匹配本身来说是比较费时的。因此为了重用,LPeg
便记住编译的结果,方式是用一个表,把描述模式的字符串和相应的内部表示关联起来。
记忆化方法的一个比较普遍的问题是,保存之前结果而在空间上的花费可能会甚于重用这些结果的好处。为了解决这个问题,我们可以使用弱表(weak table),这样,不用的结果最后就会从表中删除。
借助于高阶函数(higher-order functions),我们可以定义一个通用的记忆化函数:
function memoize (f) local mem = {} -- memoizing table setmetatable(mem, {__mode = "kv"}) -- make it weak return function (x) -- new version of 'f', with memoizing local r = mem[x] if r == nil then -- no previous result? r = f(x) -- calls original function mem[x] = r -- store result for reuse end return r end end
对于一个给定的函数 f
,memoize(f)
返回一个新的函数,这个函数会返回跟 f
一样的结果,但是会把结果记录下来。例如,我们可以重新定义 loadstring
函数的一个记忆化版本:
loadstring = memoize(loadstring)
新函数的使用方式和老函数一样,但是如果我们加载的字符串中有很多重复的字符串,便会获得很大的性能提升。
如果你的程序创建和释放过多的协程(coroutines),也许可以通过 回收(recycle)来提高它的性能。目前协程的 API 并没有直接提供重用协程的方法,但是我们可以设法克服这一限制。考虑以下协程:
co = coroutine.create(function (f) while f do f = coroutine.yield(f()) end end
这个协程接受一个作业(job)(一个待执行的函数),执行这个作业,结束后等待下一个作业。
Lua 中的大多数回收都是由垃圾收集器自动完成的。Lua 使用一个增量(incremental)的垃圾收集器,逐步(in small steps)回收(增量地),跟程序一起交错执行。每一步回收多少,跟内存分配成正比:Lua 分配了多少内存,垃圾收集器就做多少相应比例的工作。程序消耗内存越快,收集器尝试回收内存也就越快。
如果我们在程序中遵守减少和重用的原则,收集器通常没有太多的事情可做。但是有时候我们不能避免创建大量的垃圾,这时收集器就可能变得任务繁重了。Lua 的垃圾收集器是为一般的程序而设的,对大多数应用来说,它的表现都是相当不错的。但是有时候,某些特殊的应用场景,适当地调整收集器还是可以提高性能的。
要控制垃圾收集器,可以调用 Lua 的函数 collectgarbage
,或者 C 函数 lua_gc
。尽管接口不同,这两个函数的功能基本一致。接下来的讨论我会使用 Lua 函数,虽然这种操作往往更适合在 C 里面做。
函数 collectgarbage
提供了这样几种功能:它可以停止和重启收集器,强制进行一次完整的收集,强制执行一步收集(collection step),得到当前内存使用总量,更改两个影响收集效率(pace)的参数。所有这些操作在缺乏内存的程序里都有其用武之地。
对于某些批处理程序(batch programs),可以考虑「永远」地停止收集器。这些批处理程序通常都是先创建一些数据结构,并根据那些结构体产生一些输出,然后就退出(比如编译器)。对于那些程序,试图去收集垃圾也许就比较浪费时间了,因为没什么垃圾可回收的,并且程序一旦退出,所有的内存就会得到释放。
对于非批处理的程序,永远停止收集器并不可取。不过,在一些关键的时间点,停止收集器对程序可能却是有益的。如有必要,还可以由程序来完全控制垃圾收集器,让它总是处于停止状态,只在程序显式地要求执行一个步骤或者执行一个完整的回收时,收集器才开始工作。例如,有些事件驱动的平台会提供一个 idle
函数,这个函数会在没有事件可以处理时被调用。这是执行垃圾收集的最佳时刻。(Lua5.1 中,在收集器停止时去强制执行一些收集操作,都会使收集器自动重启。所以为了保持它停止的状态,必须在强制执行一些收集操作之后马上调用 collectgarbage
("stop")。)
最后一个方法,可以试着改变收集器的参数。收集器由两个参数控制其收集的步长(pace)。第一个是 pause
,控制收集器在一轮回收结束后隔多久才开始下一轮的回收。第二个参数是 stepmul
,控制收集器每一步要做多少工作。粗略地讲,pause
越小,stepmul
越大,收集器工作就越快。
这些参数对一个程序的总体性能的影响是很难预测的。收集器越快,其每秒耗费的 CPU 周期显然也就越多;但是另一方面,或许这样能减少程序的内存使用总量,从而减少换页(paging)。只有通过仔细的实验,才能为这些参数找到最佳的值。