高性能 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：

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，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 秒！

local t = {}
for line in io.lines() do
  t[#t + 1] = line
end
s = table.concat(t,"\n")
           

Lua 并沒有提供這第二種較快的方法，因為 Lua 的變量并沒有與之關聯的緩沖區。是以，我們必須使用一個顯式的緩沖區：包含字元串片段的表就行。以下循環還是讀 5MB 的檔案，費時 0.28 秒。沒 Perl 那麼快，不過也不賴。

減少，重用，回收

當處理 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 函數的一個記憶化版本：

新函數的使用方式和老函數一樣，但是如果我們加載的字元串中有很多重複的字元串，便會獲得很大的性能提升。

如果你的程式建立和釋放過多的協程（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）。隻有通過仔細的實驗，才能為這些參數找到最佳的值。