原文 https://segmentfault.com/a/1190000004372649 吐槽下csdn的轉(zhuǎn)載工具好麻煩
此為 Lua PRogramming Gems 一書的第二章：Lua Performance Tips，作者為 Roberto Ierusalimschy。
我的翻譯以 網(wǎng)上別人的翻譯 為基礎(chǔ)，做了比較大的修改，讀起來更通順。
關(guān)于性能優(yōu)化的兩條格言：
規(guī)則 1：不要優(yōu)化
規(guī)則 2：還是不要優(yōu)化（僅限專家）
不要在缺乏恰當(dāng)度量（measurements）時試圖去優(yōu)化軟件。編程老手和菜鳥之間的區(qū)別不是說老手更善于洞察程序的性能瓶頸，而是老手知道他們并不善于此。
做性能優(yōu)化離不開度量。優(yōu)化前度量，可知何處需要優(yōu)化。優(yōu)化后度量，可知「優(yōu)化」是否確實改進(jìn)了代碼。
運行代碼之前，Lua 會把源代碼翻譯（預(yù)編譯）成一種內(nèi)部格式，這種格式由一連串虛擬機(jī)的指令構(gòu)成，與真實 CPU 的機(jī)器碼很相似。接下來，這一內(nèi)部格式交由 C 代碼來解釋，基本上就是一個 while 循環(huán)，里面有一個很大的 switch，一種指令對應(yīng)一個 case。
也許你已從他處得知，自 5.0 版起，Lua 使用了一個基于寄存器的虛擬機(jī)。這些「寄存器」跟 CPU 中真實的寄存器并無關(guān)聯(lián)，因為這種關(guān)聯(lián)既無可移植性，也受限于可用的寄存器數(shù)量。Lua 使用一個棧（由一個數(shù)組加上一些索引實現(xiàn)）來存放它的寄存器。每個活動的（active）函數(shù)都有一份活動記錄（activation record），活動記錄占用棧的一小塊，存放著這個函數(shù)對應(yīng)的寄存器。因此，每個函數(shù)都有其自己的寄存器。由于每條指令只有 8 個 bit 用來指定寄存器，每個函數(shù)便可以使用多至 250 個寄存器。
Lua 的寄存器如此之多，預(yù)編譯時便能將所有的局部變量存到寄存器中。所以，在 Lua 中訪問局部變量是很快的。舉個例子， 如果 a 和 b 是局部變量，語句 a = a + b 只生成一條指令：ADD 0 0 1（假設(shè) a 和 b 分別在寄存器 0 和 1 中）。對比之下，如果 a 和 b 是全局變量，生成上述加法運算的指令便會如下：
所以，不難證明，要想改進(jìn) Lua 程序的性能，最重要的一條原則就是：使用局部變量（use locals）！
除了一些明顯的地方外，另有幾處也可使用局部變量，可以助你擠出更多的性能。比如，如果在很長的循環(huán)里調(diào)用函數(shù)，可以先將這個函數(shù)賦值給一個局部變量。這個代碼：
for i = 1, 1000000 do local x = math.sin(i)end比如下代碼慢 30%：
local sin = math.sinfor i = 1, 1000000 do local x = sin(i)end訪問外層局部變量（也就是外一層函數(shù)的局部變量）并沒有訪問局部變量快，但是仍然比訪問全局變量快?？紤]如下代碼：
function foo(x) for i = 1, 1000000 do x = x + math.sin(i) end return xendprint(foo(10))我們可以通過在 foo 函數(shù)外面定義一個 sin 來優(yōu)化它：
第二段代碼比第一段快 30%。
與其他語言的編譯器相比，Lua 的編譯器算是比較高效的，盡管如此，編譯仍是一項繁重的任務(wù)。所以，應(yīng)盡量避免在程序中編譯代碼（比如，使用 loadstring 函數(shù)）。除非需要真正動態(tài)地執(zhí)行代碼，比如代碼是由用戶輸入的，其他情況則很少需要編譯動態(tài)的代碼。
舉個例子，下面的代碼創(chuàng)建一個包含 10000 個函數(shù)的表，表中的函數(shù)分別返回常量 1 到 10000：
這段代碼運行了 1.4 秒。
使用閉包，可以避免動態(tài)編譯。下面的代碼創(chuàng)建同樣的 10000 個函數(shù)只用了 1/10 的時間（0.14秒）：
function fk (k) return function () return k endendlocal lim = 100000local a = {}for i = 1, lim do a[i] = fk(i) endprint(a[10]()) --> 10通常，使用表（table）時并不需要知道它的實現(xiàn)細(xì)節(jié)。事實上，Lua 盡力避免把實現(xiàn)細(xì)節(jié)暴露給用戶。然而這些細(xì)節(jié)還是在表操作的性能中暴露出來了。所以，為了高效地使用表，了解一些 Lua 實現(xiàn)表的方法，不無益處。
Lua 實現(xiàn)表的算法頗為巧妙。每個表包含兩部分：數(shù)組（array）部分和哈希（hash）部分，數(shù)組部分保存的項（entry）以整數(shù)為鍵（key），從 1 到某個特定的 n，（稍后會討論 n 是怎么計算的。）所有其他的項（包括整數(shù)鍵超出范圍的）則保存在哈希部分。
顧名思義，哈希部分使用哈希算法來保存和查找鍵值。它使用的是開放尋址（open address）的表，意味著所有的項都直接存在哈希數(shù)組里。鍵值的主索引由哈希函數(shù)給出；如果發(fā)生沖突（兩個鍵值哈希到相同的位置），這些鍵值就串成一個鏈表，鏈表的每個元素占用數(shù)組的一項。
當(dāng) Lua 想在表中插入一個新的鍵值而哈希數(shù)組已滿時，Lua 會做一次重新哈希（rehash）。重新哈希的第一步是決定新的數(shù)組部分和哈希部分的大小。所以 Lua 遍歷所有的項，并加以計數(shù)和分類，然后取一個使數(shù)組部分用量過半的最大的 2 的指數(shù)值，作為數(shù)組部分的大小。而哈希部分的大小則是一個容得下剩余項（即那些不適合放在數(shù)組部分的項）的最小的 2 的指數(shù)值。
當(dāng) Lua 創(chuàng)建一個空表時，兩部分的大小都是 0，因此也就沒有為它們分配數(shù)組空間?？纯慈缦麓a運行時會發(fā)生些什么：
local a = {}for i = 1, 3 do a[i] = trueend一開始創(chuàng)建一個空表。循環(huán)的第一次迭代時，賦值語句 a[1] = true 觸發(fā)了一次重新哈希；Lua 將表中的數(shù)組部分大小設(shè)為 1，而哈希部分仍為空。循環(huán)的第二次迭代時，賦值語句 a[2] = true 又觸發(fā)了一次重新哈希，現(xiàn)在，表中的數(shù)組部分大小為 2。最后，第三次迭代還是觸發(fā)了一次重新哈希，數(shù)組部分的大小增至 4。
像下面這樣的代碼：
a = {}a.x = 1; a.y = 2; a.z = 3做的事情類似，大小增長的卻是表的哈希部分。
對于大型的表，這些初始的開銷將會被整個創(chuàng)建過程平攤：創(chuàng)建 3 個元素的表需要進(jìn)行 3 次重新哈希，而創(chuàng)建一百萬個元素的表只需要 20 次。但是當(dāng)你創(chuàng)建幾千個小表時，總開銷就會很顯著。
老版的 Lua 在創(chuàng)建空表時會預(yù)分配一些空位（如果沒記錯，是 4），來避免這種創(chuàng)建小表時的初始開銷。不過，這樣又有浪費內(nèi)存之嫌。比如，以僅有兩個項的表來表示點，每個點使用的內(nèi)存就是真正所需內(nèi)存的兩倍，那么創(chuàng)建幾百萬個點將會使你付出高昂的代價。這就是現(xiàn)在 Lua 不為空表預(yù)分配空位的原因。
如果你用的是 C，可以通過 Lua 的 API 函數(shù) lua_createtable 來避免這些重新哈希。這個函數(shù)除了司空見慣的參數(shù) lua_State 外，另接受兩個參數(shù)：新表數(shù)組部分的初始大小和哈希部分的初始大小。只要這兩個參數(shù)給得恰當(dāng)，就能避免初始時的重新哈希。不過需要注意的是，Lua 只在重新哈希時才有機(jī)會去收縮（shrink）表。所以，如果你指定的初始大小大于實際所需，空間的浪費 Lua 可能永遠(yuǎn)都不會為你糾正。
如果你用的是 Lua，可以通過構(gòu)造器（constructors）來避免那些初始的重新哈希。當(dāng)你寫下 {true, true, true} 時，Lua 就會事先知道新表的數(shù)組部分需要 3 個空位，并創(chuàng)建一個相應(yīng)大小的表。與此類似，當(dāng)你寫下 {x = 1, y = 2, z = 3} 時，Lua 就創(chuàng)建一個哈希部分包含 4 個空位的表。舉例來說，下面的循環(huán)運行了 2.0 秒：
如果以正確的大小來創(chuàng)建這個表，運行時間就降到了 0.7 秒：
for i = 1, 1000000 do local a = {true, true, true} a[1] = 1; a[2] = 2; a[3] = 3end然而，當(dāng)你寫下形如 {[1] = true, [2] = true, [3] = true} 這樣的語句時，Lua 并沒有聰明到能夠檢測出給定的表達(dá)式（指那些字面數(shù)字）是在描述數(shù)組下標(biāo)，所以它創(chuàng)建了一個哈希部分有 4 個空位的表，既浪費內(nèi)存也浪費 CPU 時間。
表的兩個部分的大小只在表重新哈希時計算，而重新哈希只在表已全滿而又需要插入新元素時才會發(fā)生。因此，當(dāng)你遍歷一個表并把個中元素逐一刪除時（即設(shè)它們?yōu)?nil），表并不會縮小。你得往表里插些新的元素，然后表才會真正去調(diào)整大小。通常這不是一個問題：當(dāng)你持續(xù)地刪除和插入元素時（很多程序的典型情況），表的大小將保持穩(wěn)定。不過，你不該期望通過從一個大表里刪除一些數(shù)據(jù)來回收內(nèi)存，更好的做法是刪除這個表本身。
有一則強(qiáng)制重新哈希的奇技淫巧，即往表里插入足夠的 nil 元素。示例如下：
除非特殊情況需要，我并不推薦這種手法，因為這樣做很慢，而且要知道多少元素才算「足夠」，也沒有簡單易行的方法。
你可能會想，Lua 為什么不在我們插入 nil 時收縮表的大小呢？首先，是為了避免對插入元素的檢查；一條檢查 nil 賦值的語句將會拖慢所有的賦值語句。其次，也是更重要的，是為了允許在遍歷表時對元素賦 nil 值?？紤]如下循環(huán)：
如果 Lua 在 nil 賦值后進(jìn)行重新哈希，那么這個遍歷就被破壞了。
如果你想刪除表中的所有元素，正確的方法是使用一個簡單的循環(huán)：
for k in pairs(t) do t[k] = nilend或者使用”聰明”一點的方法：
while true do local k = next(t) if not k then break end t[k] = nilend不過，這個循環(huán)在表很大時會很慢。調(diào)用函數(shù) next 時，如果沒有傳入前一個鍵值，返回的便是表的「第一個」元素（以某種隨機(jī)順序）。（譯：「第一個」之所以加引號，是指就表內(nèi)部的數(shù)組結(jié)構(gòu)而言的第一個元素，「以某種隨機(jī)順序」則是從表的角度或用戶使用表的角度來說。）為此，next 從頭遍歷表的數(shù)組空間（譯：包含數(shù)組和哈希兩部分），查找一個非 nil 元素。隨著循環(huán)逐一將這些第一個元素設(shè)為 nil，查找第一個非 nil 元素變得越來越久。結(jié)果是，為了清除一個有 100000 個元素的表，這個“聰明”的循環(huán)用了 20 秒，而使用 pairs 遍歷表的循環(huán)只用了 0.04 秒。
和表一樣，了解 Lua 實現(xiàn)字符串的細(xì)節(jié)對高效地使用字符串也會有所幫助。
Lua 實現(xiàn)字符串的方式和大多數(shù)其他的腳本語言有兩點重要的區(qū)別。其一，Lua 的字符串都是內(nèi)化的（internalized）；這意味著字符串在 Lua 中都只有一份拷貝。每當(dāng)一個新字符串出現(xiàn)時，Lua 會先檢查這個字符串是否已經(jīng)有一份拷貝，如果有，就重用這份拷貝。內(nèi)化（internalization）使字符串比較及表索引這樣的操作變得非常快，但是字符串的創(chuàng)建會變慢。
其二，Lua 的字符串變量從來不會包含字符串本身，包含的只是字符串的引用。這種實現(xiàn)加快了某些字符串操作。比如，對 Perl 來說，如果你寫下這樣的語句：$x = $y ，$y 包含一個字符串，這個賦值語句將復(fù)制 $y 緩沖區(qū)里的字符串內(nèi)容到 $x 的緩沖區(qū)中。如果字符串很長，這一操作代價將非常高。而對 Lua 來說，這樣的賦值語句只不過復(fù)制了一個指向?qū)嶋H字符串的指針。
這種使用引用的實現(xiàn)，使某種特定形式的字符串連接變慢了。在 Perl 里，$s = $s . "x" 和 $s .= "x" 這兩者是很不一樣的。前一個語句，先得到一份 $s 的拷貝，然后往這份拷貝的末尾加上 "x"。后一個語句，只是簡單地把 "x" 追加到變量 $s 所持有的內(nèi)部緩沖區(qū)上。所以，第二種連接形式跟字符串大小是無關(guān)的（假設(shè)緩沖區(qū)有足夠的空間來存放連接的字符串）。如果在循環(huán)中執(zhí)行這兩條語句，那么它們的區(qū)別就是算法復(fù)雜度的線性階和平方階的區(qū)別了。比如，以下循環(huán)讀一個 5MB 的文件，幾乎用了 5 分鐘：
如果將 $x = $x . $_ 替換成 $x .= $_ 則只要 0.1 秒！
Lua 并沒有提供這第二種較快的方法，因為 Lua 的變量并沒有與之關(guān)聯(lián)的緩沖區(qū)。所以，我們必須使用一個顯式的緩沖區(qū)：包含字符串片段的表就行。以下循環(huán)還是讀 5MB 的文件，費時 0.28 秒。沒 Perl 那么快，不過也不賴。
local t = {}for line in io.lines() do t[#t + 1] = lineends = table.concat(t,"/n")當(dāng)處理 Lua 資源時，我們應(yīng)當(dāng)遵守跟利用地球資源一樣的 3R 原則。
減少（reduce）是最簡單的一種途徑。有幾種方法可以避免創(chuàng)建對象。例如，如果你的程序使用了大量的表，或許可以考慮改變它的數(shù)據(jù)表示。舉個簡單的例子，假如你的程序需要處理折線（polyline）。在 Lua 里，折線最自然的表示是使用一個點的列表，像這樣：
polyline = { { x = 10.3, y = 98.5 }, { x = 10.3, y = 18.3 }, { x = 15.0, y = 98.5 }, ...}這種表示雖然自然，折線較大時卻不經(jīng)濟(jì)，因為每個點都要用一個表。下面這種表示改用數(shù)組，內(nèi)存略為節(jié)?。?/p>polyline = { { 10.3, 98.5 }, { 10.3, 18.3 }, { 15.0, 98.5 }, ...}
對于一條有一百萬個點的折線，這種改變使內(nèi)存用量從 95KB 降到 65KB。當(dāng)然，作為代價，程序的可讀性有所損失：p[i].x 要比 p[i][4] 易懂得多。
還有一個更經(jīng)濟(jì)的方法，用兩個列表，一個存 x 坐標(biāo)的值，一個存 y 坐標(biāo)的值：
之前的 p[i].x 現(xiàn)在就是 p.x[i]。使用這種方式，一條有一百萬個點的折線只需 24KB 的內(nèi)存。
循環(huán)是尋找降低不必要資源創(chuàng)建的好地方。例如，如果在循環(huán)中創(chuàng)建了一個常量的（constant）表，便可以把表移到循環(huán)之外，或者甚至可以移到外圍函數(shù)之外。比較如下兩段代碼：
function foo (...) for i = 1, n do local t = {1, 2, 3, "hi"} -- 做一些不改變 t 的操作 ... endendlocal t = {1, 2, 3, "hi"} -- 一次性地創(chuàng)建 tfunction foo (...) for i = 1, n do -- 做一些不改變 t 的操作 ... endend同樣的技巧也可以用于閉包，只要移動時不致越出閉包所需變量的作用域。例如，考慮以下函數(shù)：
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") endend只要將內(nèi)部（inner）函數(shù)移到循環(huán)之外，就可避免為每一行都創(chuàng)建一個新的閉包：
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") endend不過，不能將函數(shù) aux 移到函數(shù) changenumbers 之外，那樣的話，函數(shù) aux 就不能訪問變量 limit 和 delta 了。
很多字符串的處理，都可以通過在現(xiàn)有字符串上使用下標(biāo)，來避免創(chuàng)建不必要的新字符串。例如，函數(shù) string.find 返回的是給定模式出現(xiàn)的位置，而不是一個與之匹配的字符串。返回下標(biāo)，就避免了在成功匹配時創(chuàng)建一個新的（子）字符串。若有需要，可以再通過函數(shù) string.sub 來獲取匹配的子字符串。
即使不能避免使用新的對象，也可以通過 重用（reuse）來避免創(chuàng)建新的對象。對字符串來說，重用是沒有必要的，因為 Lua 已經(jīng)替我們這樣做了：所有的字符串都是內(nèi)化的（internalized），因此只要可能就會重用。對表來說，重用就顯得卓有成效了。舉一個常見的例子，讓我們回到在循環(huán)內(nèi)創(chuàng)建表的情況。不同的是，這次的表是可變的（not constant）。不過，往往只需簡單的改變內(nèi)容，還是可以在所有的迭代中重用同一個表的?？紤]以下代碼：
local t = {}local aux = {year = nil, month = 6, day = 14}for i = 1970, 2000 do aux.year = i t[i] = os.time(aux)end實現(xiàn)重用的一種特別有效的方法是記憶化（memoizing）?；鞠敕ǚ浅：唵危簩τ谝粋€給定的輸入，保存其計算結(jié)果，當(dāng)遇到同樣的輸入時，程序只需重用之前保存的結(jié)果。
來看看 LPeg（Lua 中一個新的模式匹配的包），它使用記憶化的方式頗為有趣。LPeg 把每個模式都編譯成一種內(nèi)部表示，對負(fù)責(zé)匹配的分析器來說，這種表示就是一種「程序」。這種編譯相對于匹配本身來說是比較費時的。因此為了重用，LPeg 便記住編譯的結(jié)果，方式是用一個表，把描述模式的字符串和相應(yīng)的內(nèi)部表示關(guān)聯(lián)起來。
記憶化方法的一個比較普遍的問題是，保存之前結(jié)果而在空間上的花費可能會甚于重用這些結(jié)果的好處。為了解決這個問題，我們可以使用弱表（weak table），這樣，不用的結(jié)果最后就會從表中刪除。
借助于高階函數(shù)（higher-order functions），我們可以定義一個通用的記憶化函數(shù)：
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 endend對于一個給定的函數(shù) f，memoize(f) 返回一個新的函數(shù)，這個函數(shù)會返回跟 f 一樣的結(jié)果，但是會把結(jié)果記錄下來。例如，我們可以重新定義 loadstring 函數(shù)的一個記憶化版本：
新函數(shù)的使用方式和老函數(shù)一樣，但是如果我們加載的字符串中有很多重復(fù)的字符串，便會獲得很大的性能提升。
如果你的程序創(chuàng)建和釋放過多的協(xié)程（coroutines），也許可以通過 回收（recycle）來提高它的性能。目前協(xié)程的 API 并沒有直接提供重用協(xié)程的方法，但是我們可以設(shè)法克服這一限制。考慮以下協(xié)程：
co = coroutine.create(function (f) while f do f = coroutine.yield(f()) endend這個協(xié)程接受一個作業(yè)（job）（一個待執(zhí)行的函數(shù)），執(zhí)行這個作業(yè)，結(jié)束后等待下一個作業(yè)。
Lua 中的大多數(shù)回收都是由垃圾收集器自動完成的。Lua 使用一個增量（incremental）的垃圾收集器，逐步（in small steps）回收（增量地），跟程序一起交錯執(zhí)行。每一步回收多少，跟內(nèi)存分配成正比：Lua 分配了多少內(nèi)存，垃圾收集器就做多少相應(yīng)比例的工作。程序消耗內(nèi)存越快，收集器嘗試回收內(nèi)存也就越快。
如果我們在程序中遵守減少和重用的原則，收集器通常沒有太多的事情可做。但是有時候我們不能避免創(chuàng)建大量的垃圾，這時收集器就可能變得任務(wù)繁重了。Lua 的垃圾收集器是為一般的程序而設(shè)的，對大多數(shù)應(yīng)用來說，它的表現(xiàn)都是相當(dāng)不錯的。但是有時候，某些特殊的應(yīng)用場景，適當(dāng)?shù)卣{(diào)整收集器還是可以提高性能的。
要控制垃圾收集器，可以調(diào)用 Lua 的函數(shù) collectgarbage，或者 C 函數(shù) lua_gc。盡管接口不同，這兩個函數(shù)的功能基本一致。接下來的討論我會使用 Lua 函數(shù)，雖然這種操作往往更適合在 C 里面做。
函數(shù) collectgarbage 提供了這樣幾種功能：它可以停止和重啟收集器，強(qiáng)制進(jìn)行一次完整的收集，強(qiáng)制執(zhí)行一步收集（collection step），得到當(dāng)前內(nèi)存使用總量，更改兩個影響收集效率（pace）的參數(shù)。所有這些操作在缺乏內(nèi)存的程序里都有其用武之地。
對于某些批處理程序（batch programs），可以考慮「永遠(yuǎn)」地停止收集器。這些批處理程序通常都是先創(chuàng)建一些數(shù)據(jù)結(jié)構(gòu)，并根據(jù)那些結(jié)構(gòu)體產(chǎn)生一些輸出，然后就退出（比如編譯器）。對于那些程序，試圖去收集垃圾也許就比較浪費時間了，因為沒什么垃圾可回收的，并且程序一旦退出，所有的內(nèi)存就會得到釋放。
對于非批處理的程序，永遠(yuǎn)停止收集器并不可取。不過，在一些關(guān)鍵的時間點，停止收集器對程序可能卻是有益的。如有必要，還可以由程序來完全控制垃圾收集器，讓它總是處于停止?fàn)顟B(tài)，只在程序顯式地要求執(zhí)行一個步驟或者執(zhí)行一個完整的回收時，收集器才開始工作。例如，有些事件驅(qū)動的平臺會提供一個 idle 函數(shù)，這個函數(shù)會在沒有事件可以處理時被調(diào)用。這是執(zhí)行垃圾收集的最佳時刻。（Lua5.1 中，在收集器停止時去強(qiáng)制執(zhí)行一些收集操作，都會使收集器自動重啟。所以為了保持它停止的狀態(tài)，必須在強(qiáng)制執(zhí)行一些收集操作之后馬上調(diào)用 collectgarbage (“stop”)。）
最后一個方法，可以試著改變收集器的參數(shù)。收集器由兩個參數(shù)控制其收集的步長（pace）。第一個是 pause，控制收集器在一輪回收結(jié)束后隔多久才開始下一輪的回收。第二個參數(shù)是 stepmul，控制收集器每一步要做多少工作。粗略地講，pause 越小，stepmul 越大，收集器工作就越快。
這些參數(shù)對一個程序的總體性能的影響是很難預(yù)測的。收集器越快，其每秒耗費的 CPU 周期顯然也就越多；但是另一方面，或許這樣能減少程序的內(nèi)存使用總量，從而減少換頁（paging）。只有通過仔細(xì)的實驗，才能為這些參數(shù)找到最佳的值。
新聞熱點
疑難解答
