如何編寫高性能的Lua代碼
前言
Lua是一門以其性能著稱的腳本語(yǔ)言，被廣泛應(yīng)用在很多方面，尤其是游戲。像《魔獸世界》的插件，手機(jī)游戲《大掌門》《神曲》《迷失之地》等都是用Lua來(lái)寫的邏輯。
所以大部分時(shí)候我們不需要去考慮性能問(wèn)題。Knuth有句名言：“過(guò)早優(yōu)化是萬(wàn)惡之源”。其意思就是過(guò)早優(yōu)化是不必要的，會(huì)浪費(fèi)大量時(shí)間，而且容易導(dǎo)致代碼混亂。
所以一個(gè)好的程序員在考慮優(yōu)化性能前必須問(wèn)自己兩個(gè)問(wèn)題：“我的程序真的需要優(yōu)化嗎？”。如果答案為是，那么再問(wèn)自己：“優(yōu)化哪個(gè)部分？”。
我們不能靠臆想和憑空猜測(cè)來(lái)決定優(yōu)化哪個(gè)部分，代碼的運(yùn)行效率必須是可測(cè)量的。我們需要借助于分析器來(lái)測(cè)定性能的瓶頸，然后著手優(yōu)化。優(yōu)化后，我們?nèi)匀灰柚诜治銎鱽?lái)測(cè)量所做的優(yōu)化是否真的有效。
我認(rèn)為***的方式是在***編寫的時(shí)候按照***實(shí)踐去寫出高性能的代碼，而不是編寫了一堆垃圾代碼后，再考慮優(yōu)化。相信工作后大家都會(huì)對(duì)事后的優(yōu)化的繁瑣都深有體會(huì)。
一旦你決定編寫高性能的Lua代碼，下文將會(huì)指出在Lua中哪些代碼是可以優(yōu)化的，哪些代碼會(huì)是運(yùn)行緩慢的，然后怎么去優(yōu)化它們。
使用local
在代碼運(yùn)行前，Lua會(huì)把源碼預(yù)編譯成一種中間碼，類似于Java的虛擬機(jī)。這種格式然后會(huì)通過(guò)C的解釋器進(jìn)行解釋，整個(gè)過(guò)程其實(shí)就是通過(guò)一個(gè)while循環(huán)，里面有很多的switch...case語(yǔ)句，一個(gè)case對(duì)應(yīng)一條指令來(lái)解析。
自Lua 5.0之后，Lua采用了一種類似于寄存器的虛擬機(jī)模式。Lua用棧來(lái)儲(chǔ)存其寄存器。每一個(gè)活動(dòng)的函數(shù)，Lua都會(huì)其分配一個(gè)棧，這個(gè)棧用來(lái)儲(chǔ)存函數(shù)里的活動(dòng)記錄。每一個(gè)函數(shù)的棧都可以儲(chǔ)存至多250個(gè)寄存器，因?yàn)闂５拈L(zhǎng)度是用8個(gè)比特表示的。
有了這么多的寄存器，Lua的預(yù)編譯器能把所有的local變量?jī)?chǔ)存在其中。這就使得Lua在獲取local變量時(shí)其效率十分的高。
舉個(gè)栗子： 假設(shè)a和b為local變量，a = a + b的預(yù)編譯會(huì)產(chǎn)生一條指令：
- ;a是寄存器0 b是寄存器1
- ADD 0 0 1
但是若a和b都沒有聲明為local變量，則預(yù)編譯會(huì)產(chǎn)生如下指令：
- GETGLOBAL 0 0 ;get a
- GETGLOBAL 1 1 ;get b
- ADD 0 0 1 ;do add
- SETGLOBAL 0 0 ;set a
所以你懂的：在寫Lua代碼時(shí)，你應(yīng)該盡量使用local變量。
以下是幾個(gè)對(duì)比測(cè)試，你可以復(fù)制代碼到你的編輯器中，進(jìn)行測(cè)試。
- a = os.clock()
- for i = 1,10000000 do
- local x = math.sin(i)
- end
- b = os.clock()
- print(b-a) -- 1.113454
把math.sin賦給local變量sin：
- a = os.clock()
- local sin = math.sin
- for i = 1,10000000 do
- local x = sin(i)
- end
- b = os.clock()
- print(b-a) --0.75951
直接使用math.sin，耗時(shí)1.11秒；使用local變量sin來(lái)保存math.sin，耗時(shí)0.76秒?？梢垣@得30%的效率提升！
關(guān)于表(table)
表在Lua中使用十分頻繁，因?yàn)楸韼缀醮媪薒ua的所有容器。所以快速了解一下Lua底層是如何實(shí)現(xiàn)表，對(duì)我們編寫Lua代碼是有好處的。
Lua的表分為兩個(gè)部分：數(shù)組(array)部分和哈希(hash)部分。數(shù)組部分包含所有從1到n的整數(shù)鍵，其他的所有鍵都儲(chǔ)存在哈希部分中。
哈希部分其實(shí)就是一個(gè)哈希表，哈希表本質(zhì)是一個(gè)數(shù)組，它利用哈希算法將鍵轉(zhuǎn)化為數(shù)組下標(biāo)，若下標(biāo)有沖突(即同一個(gè)下標(biāo)對(duì)應(yīng)了兩個(gè)不同的鍵)，則它會(huì)將沖突的下標(biāo)上創(chuàng)建一個(gè)鏈表，將不同的鍵串在這個(gè)鏈表上，這種解決沖突的方法叫做：鏈地址法。
當(dāng)我們把一個(gè)新鍵值賦給表時(shí)，若數(shù)組和哈希表已經(jīng)滿了，則會(huì)觸發(fā)一個(gè)再哈希(rehash)。再哈希的代價(jià)是高昂的。首先會(huì)在內(nèi)存中分配一個(gè)新的長(zhǎng)度的數(shù)組，然后將所有記錄再全部哈希一遍，將原來(lái)的記錄轉(zhuǎn)移到新數(shù)組中。新哈希表的長(zhǎng)度是最接近于所有元素?cái)?shù)目的2的乘方。
當(dāng)創(chuàng)建一個(gè)空表時(shí)，數(shù)組和哈希部分的長(zhǎng)度都將初始化為0，即不會(huì)為它們初始化任何數(shù)組。讓我們來(lái)看下執(zhí)行下面這段代碼時(shí)在Lua中發(fā)生了什么：
- local a = {}
- for i=1,3 do
- a[i] = true
- end
最開始，Lua創(chuàng)建了一個(gè)空表a，在***次迭代中，a[1] = true觸發(fā)了一次rehash，Lua將數(shù)組部分的長(zhǎng)度設(shè)置為2^0，即1，哈希部分仍為空。在第二次迭代中，a[2] = true再次觸發(fā)了rehash，將數(shù)組部分長(zhǎng)度設(shè)為2^1，即2。***一次迭代，又觸發(fā)了一次rehash，將數(shù)組部分長(zhǎng)度設(shè)為2^2，即4。
下面這段代碼：
- a = {}
- a.x = 1; a.y = 2; a.z = 3
與上一段代碼類似，只是其觸發(fā)了三次表中哈希部分的rehash而已。
只有三個(gè)元素的表，會(huì)執(zhí)行三次rehash；然而有一百萬(wàn)個(gè)元素的表僅僅只會(huì)執(zhí)行20次rehash而已，因?yàn)?^20 = 1048576 > 1000000。但是，如果你創(chuàng)建了非常多的長(zhǎng)度很小的表（比如坐標(biāo)點(diǎn)：point = {x=0,y=0}），這可能會(huì)造成巨大的影響。
如果你有很多非常多的很小的表需要?jiǎng)?chuàng)建時(shí)，你可以將其預(yù)先填充以避免rehash。比如：{true,true,true}，Lua知道這個(gè)表有三個(gè)元素，所以Lua直接創(chuàng)建了三個(gè)元素長(zhǎng)度的數(shù)組。類似的，{x=1, y=2, z=3}，Lua會(huì)在其哈希部分中創(chuàng)建長(zhǎng)度為4的數(shù)組。
以下代碼執(zhí)行時(shí)間為1.53秒：
- a = os.clock()
- for i = 1,2000000 do
- local a = {}
- a[1] = 1; a[2] = 2; a[3] = 3
- end
- b = os.clock()
- print(b-a) --1.528293
如果我們?cè)趧?chuàng)建表的時(shí)候就填充好它的大小，則只需要0.75秒，一倍的效率提升！
- a = os.clock()
- for i = 1,2000000 do
- local a = {1,1,1}
- a[1] = 1; a[2] = 2; a[3] = 3
- end
- b = os.clock()
- print(b-a) --0.746453
所以，當(dāng)需要?jiǎng)?chuàng)建非常多的小size的表時(shí)，應(yīng)預(yù)先填充好表的大小。
關(guān)于字符串
與其他主流腳本語(yǔ)言不同的是，Lua在實(shí)現(xiàn)字符串類型有兩方面不同。
***，所有的字符串在Lua中都只儲(chǔ)存一份拷貝。當(dāng)新字符串出現(xiàn)時(shí)，Lua檢查是否有其相同的拷貝，若沒有則創(chuàng)建它，否則，指向這個(gè)拷貝。這可以使得字符串比較和表索引變得相當(dāng)?shù)目?，因?yàn)楸容^字符串只需要檢查引用是否一致即可；但是這也降低了創(chuàng)建字符串時(shí)的效率，因?yàn)長(zhǎng)ua需要去查找比較一遍。
第二，所有的字符串變量，只保存字符串引用，而不保存它的buffer。這使得字符串的賦值變得十分高效。例如在Perl中，$x = $y，會(huì)將$y的buffer整個(gè)的復(fù)制到$x的buffer中，當(dāng)字符串很長(zhǎng)時(shí)，這個(gè)操作的代價(jià)將十分昂貴。而在Lua，同樣的賦值，只復(fù)制引用，十分的高效。
但是只保存引用會(huì)降低在字符串連接時(shí)的速度。在Perl中，$s = $s . 'x'和$s .= 'x'的效率差距驚人。前者，將會(huì)獲取整個(gè)$s的拷貝，并將’x’添加到它的末尾；而后者，將直接將’x’插入到$x的buffer末尾。
由于后者不需要進(jìn)行拷貝，所以其效率和$s的長(zhǎng)度無(wú)關(guān)，因?yàn)槭指咝А?/p>
在Lua中，并不支持第二種更快的操作。以下代碼將花費(fèi)6.65秒：
- a = os.clock()
- local s = ''
- for i = 1,300000 do
- s = s .. 'a'
- end
- b = os.clock()
- print(b-a) --6.649481
我們可以用table來(lái)模擬buffer，下面的代碼只需花費(fèi)0.72秒，9倍多的效率提升：
- a = os.clock()
- local s = ''
- local t = {}
- for i = 1,300000 do
- t[#t + 1] = 'a'
- end
- s = table.concat( t, '')
- b = os.clock()
- print(b-a) --0.07178
所以：在大字符串連接中，我們應(yīng)避免..。應(yīng)用table來(lái)模擬buffer，然后concat得到最終字符串。
#p#
3R原則
3R原則（the rules of 3R）是：減量化（reducing），再利用（reusing）和再循環(huán)（recycling）三種原則的簡(jiǎn)稱。
3R原則本是循環(huán)經(jīng)濟(jì)和環(huán)保的原則，但是其同樣適用于Lua。
Reducing
有許多辦法能夠避免創(chuàng)建新對(duì)象和節(jié)約內(nèi)存。例如：如果你的程序中使用了太多的表，你可以考慮換一種數(shù)據(jù)結(jié)構(gòu)來(lái)表示。
舉個(gè)栗子。 假設(shè)你的程序中有多邊形這個(gè)類型，你用一個(gè)表來(lái)儲(chǔ)存多邊形的頂點(diǎn)：
- polyline = {
- { x = 1.1, y = 2.9 },
- { x = 1.1, y = 3.7 },
- { x = 4.6, y = 5.2 },
- ...
- }
以上的數(shù)據(jù)結(jié)構(gòu)十分自然，便于理解。但是每一個(gè)頂點(diǎn)都需要一個(gè)哈希部分來(lái)儲(chǔ)存。如果放置在數(shù)組部分中，則會(huì)減少內(nèi)存的占用:
- polyline = {
- { 1.1, 2.9 },
- { 1.1, 3.7 },
- { 4.6, 5.2 },
- ...
- }
一百萬(wàn)個(gè)頂點(diǎn)時(shí)，內(nèi)存將會(huì)由153.3MB減少到107.6MB，但是代價(jià)是代碼的可讀性降低了。
最變態(tài)的方法是：
- polyline = {
- x = {1.1, 1.1, 4.6, ...},
- y = {2.9, 3.7, 5.2, ...}
- }
一百萬(wàn)個(gè)頂點(diǎn)，內(nèi)存將只占用32MB，相當(dāng)于原來(lái)的1/5。你需要在性能和代碼可讀性之間做出取舍。
在循環(huán)中，我們更需要注意實(shí)例的創(chuàng)建。
- for i=1,n do
- local t = {1,2,3,'hi'}
- --執(zhí)行邏輯，但t不更改
- ...
- end
我們應(yīng)該把在循環(huán)中不變的東西放到循環(huán)外來(lái)創(chuàng)建：
- local t = {1,2,3,'hi'}
- for i=1,n do
- --執(zhí)行邏輯，但t不更改
- ...
- end
Reusing
如果無(wú)法避免創(chuàng)建新對(duì)象，我們需要考慮重用舊對(duì)象。
考慮下面這段代碼：
- local t = {}
- for i = 1970, 2000 do
- t[i] = os.time({year = i, month = 6, day = 14})
- end
在每次循環(huán)迭代中，都會(huì)創(chuàng)建一個(gè)新表{year = i, month = 6, day = 14}，但是只有year是變量。
下面這段代碼重用了表：
- local t = {}
- local aux = {year = nil, month = 6, day = 14}
- for i = 1970, 2000 do
- aux.year = i;
- t[i] = os.time(aux)
- end
另一種方式的重用，則是在于緩存之前計(jì)算的內(nèi)容，以避免后續(xù)的重復(fù)計(jì)算。后續(xù)遇到相同的情況時(shí)，則可以直接查表取出。這種方式實(shí)際就是動(dòng)態(tài)規(guī)劃效率高的原因所在，其本質(zhì)是用空間換時(shí)間。
Recycling
Lua自帶垃圾回收器，所以我們一般不需要考慮垃圾回收的問(wèn)題。
了解Lua的垃圾回收能使得我們編程的自由度更大。
Lua的垃圾回收器是一個(gè)增量運(yùn)行的機(jī)制。即回收分成許多小步驟（增量的）來(lái)進(jìn)行。
頻繁的垃圾回收可能會(huì)降低程序的運(yùn)行效率。
我們可以通過(guò)Lua的collectgarbage函數(shù)來(lái)控制垃圾回收器。
collectgarbage函數(shù)提供了多項(xiàng)功能：停止垃圾回收，重啟垃圾回收，強(qiáng)制執(zhí)行一次回收循環(huán)，強(qiáng)制執(zhí)行一步垃圾回收，獲取Lua占用的內(nèi)存，以及兩個(gè)影響垃圾回收頻率和步幅的參數(shù)。
對(duì)于批處理的Lua程序來(lái)說(shuō)，停止垃圾回收collectgarbage("stop")會(huì)提高效率，因?yàn)榕幚沓绦蛟诮Y(jié)束時(shí)，內(nèi)存將全部被釋放。
對(duì)于垃圾回收器的步幅來(lái)說(shuō)，實(shí)際上很難一概而論。更快幅度的垃圾回收會(huì)消耗更多CPU，但會(huì)釋放更多內(nèi)存，從而也降低了CPU的分頁(yè)時(shí)間。只有小心的試驗(yàn)，我們才知道哪種方式更適合。
結(jié)語(yǔ)
我們應(yīng)該在寫代碼時(shí)，按照高標(biāo)準(zhǔn)去寫，盡量避免在事后進(jìn)行優(yōu)化。
如果真的有性能問(wèn)題，我們需要用工具量化效率，找到瓶頸，然后針對(duì)其優(yōu)化。當(dāng)然優(yōu)化過(guò)后需要再次測(cè)量，查看是否優(yōu)化成功。
在優(yōu)化中，我們會(huì)面臨很多選擇：代碼可讀性和運(yùn)行效率，CPU換內(nèi)存，內(nèi)存換CPU等等。需要根據(jù)實(shí)際情況進(jìn)行不斷試驗(yàn)，來(lái)找到最終的平衡點(diǎn)。
***，有兩個(gè)***武器：
***、使用LuaJIT，LuaJIT可以使你在不修改代碼的情況下獲得平均約5倍的加速。查看LuaJIT在x86/x64下的性能提升比。
第二、將瓶頸部分用C/C++來(lái)寫。因?yàn)長(zhǎng)ua和C的天生近親關(guān)系，使得Lua和C可以混合編程。但是C和Lua之間的通訊會(huì)抵消掉一部分C帶來(lái)的優(yōu)勢(shì)。
注意：這兩者并不是兼容的，你用C改寫的Lua代碼越多，LuaJIT所帶來(lái)的優(yōu)化幅度就越小。
聲明
這篇文章是基于Lua語(yǔ)言的創(chuàng)造者Roberto Ierusalimschy在Lua Programming Gems 中的Lua Performance Tips翻譯改寫而來(lái)。本文沒有直譯，做了許多刪節(jié)，可以視為一份筆記。
感謝Roberto在Lua上的辛勤勞動(dòng)和付出！
