Lua性能优化译文

关于性能优化的两条格言：
规则 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：这段代码运行了 1.4 秒。
local a = {}
for i = 1, lim do
    a[i] = loadstring(string.format(“return %d”, i))
end
print(a10) --> 10
使用闭包，可以避免动态编译。下面的代码创建同样的 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(a10) --> 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 元素。示例如下：
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 – c插入大量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 分钟：
KaTeX parse error: Expected '}', got 'EOF' at end of input: …ile (<>) {
    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”} – 一次性创建好全部
function foo (…)
    for i = 1, n do
    – 做一些不改变t的操作
    …
    end
end

同样的技巧也可以用于闭包，只要移动时不致越出闭包所需变量的作用域。例如，考虑以下函数：

function changenumbers (limit, delta)
    for line in 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 line in 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）。只有通过仔细的实验，才能为这些参数找到最佳的值。