高性能 Lua 技巧(译)

长安长夜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 中访问局部变量是很快的。举个例子, 如果 ab 是局部变量,语句 a = a + b 只生成一条指令:ADD 0 0 1(假设 ab 分别在寄存器 01 中)。对比之下,如果 ab 是全局变量,生成上述加法运算的指令便会如下:

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 个函数的表,表中的函数分别返回常量 110000

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 就不能访问变量 limitdelta 了。

很多字符串的处理,都可以通过在现有字符串上使用下标,来避免创建不必要的新字符串。例如,函数 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

对于一个给定的函数 fmemoize(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)。只有通过仔细的实验,才能为这些参数找到最佳的值。

相关推荐