规则1:不要优化。
规则2:仍然不要优化(专家除外)
当用Lua编程时,这两条规则显得尤为重要。Lua以性能著称,而且在脚本语言中也因此而值得赞美。
然而,我们都知道性能是编程的一个关键因素。具有复杂指数时间的问题被称作疑难问题并不是偶然发生。太迟的结果是无用的结果。因此,每个优秀的程序员应该总是在花费资源去优化一段代码的代价和这段代码在运行代码时节约资源的收益相平衡。一个优秀的程序员关于优化的第一个问题总是会问:“程序需要优化吗?”如果答案是肯定的(仅当此时),第二个问题应该是:“哪地方?”
为了回答这两个问题我们需要些手段。我们不应该在没有合适的测量时尝试优化软件。大牛和菜鸟之前的不同不是有经验的程序员更好的指出程序的一个地方可能耗时:不同之处是大牛知道他们并不擅长那项任务。
最近几年,Noemi Rodriguez和我用Lua开发了一个CORBA ORB(Object Request Broker)原型,后来进化成OiL(Orb in Lua)。作为第一个原型,以执行简明为目标。为了避免引用额外的C语言库,这个原型用一些计算操作分离每个字节(转化成256的基数)。不支持浮点数。因为CORBA把字符串作为字符序列处理,我们的ORB第一次把Lua的字符串转化成字符序列(是Lua中的table),然后像其他序列那样处理结果。
当我们完成第一个原型,我们和用C++实现的专业的ORB的性能相比较。我们预期我们的ORB会稍微慢点,因为它是用Lua实现的,但是,慢的太让我们失望了。开始时,我们只是归咎于Lua。最后,我们猜想原因可能是每个数字序列化所需要的那些操作。因此,我们决定在分析器下下运行程序。我们用了一个非常简单的分析器,像《Programming in Lua》第23章描述的那样。分析器的结果震惊到我们。和我们的直觉不同,数字序列化对性能的影响不大,因为没有太多的数字序列化。然而,字符串序列化占用总时间的很大一部分。实际上每个CORBA消息都有几个字符串,即使我们不明确地操作字符串:对象引用,方法名字和其他的某些整数值都被编码成字符串。并且每个字符串序列化需要昂贵的代价去操作,因为这需要创建新表,用每个单独的字符填充,然后序列化这些结果的顺序,这涉及到一个接一个序列化每个字符。一旦我们重新实现字符串序列化作为特殊的事件(替换使用一般的序列代码),我们就能得到可观的速度提升。仅仅用额外的几行代码,你的执行效率就能比得上C++的执行(当然,我们的执行仍然慢,但不是一个数量级)。
因此,当优化程序性能时,我们应总是去测量。测量前,知道优化哪里。测量后,知道所谓的“优化”是否真正的提高了我们的代码。
一旦你决定确实必须优化你的Lua代码,本文可能帮助你如何去优化,主要通过展示在Lua中哪样会慢和哪样会快。在这里我不会讨论优化的一般技术,比如更好的算法。当然,你应该懂得并且会用这些技术,但是,你能从其他的地方学习到那些一般的优化技术。在这篇文章里我仅讲解Lua特有的技术。整篇文章,我将会时不时的测量小程序的时间和空间。除非另有说明,我所有的测量是在Pentium IV 2.9 GHz和主存1GB,运行在Ubuntu 7.10, Lua 5.1.1。我会频繁地给出实际的测量结果(例如,7秒),但是会依赖于不同测量方法。当我说一个程序比另一的“快X%”的意思是运行时间少“X%”。(程序快100%意味着运行不花时间。)当我说一个程序比另一个“慢X%”的意思是另一个快X%。(程序慢50%的意思是运行花费两倍时间。)
基础实例
运行任何代码前,Lua会把源码转化(预编译)成内部格式。这种格式是虚拟机指令的序列,类似于真正CPU的机器码。这种内部格式然后被必须内部有一个每个指令是一种情况大的switch的while循环的C语言解释。
可能在某些地方你已经读过从5.0版本Lua使用基于寄存器的虚拟机。这个虚拟机的“寄存器”和真正CPU的寄存器不相符,因为这种相符是不能移植并且十份限制可用寄存器的数量。取而代之的是,Lua使用堆(一个数组加上些索引来实现)容纳寄存器。每个活动函数有一个活动记录,那是个函数在其中存储其寄存器的堆片段。因此,每个函数有他自己的寄存器(这类似于在windows某些CPU创建的寄存器)。每个函数可能使用超过250个寄存器,因此每个指令仅有8位引用寄存器。
提供了大量的寄存器,Lua预编译能够在寄存器储存剩余的局部变量。结果是在Lua中访问局部变量非常快。举个例子,如果a和b都是局部变量,像a = a + b这种语句生成单条指令:ADD 0 0 1(假设a和b中分别储存0和1)。作为比较,如果a和b都是全局变量,增加的代码会像这样:
GETGLOBAL 0 0 ; aGETGLOBAL 1 1 ; bADD 0 0 1SETGLOBAL 0 0 ; a
因此,这很容易证明优化Lua程序的一个重要规则:使用局部变量!
如果你需要进一步提高你程序的性能,除了明显的那些,这里还有你能使用局部变量的地方。例如,如果你在长循环中调用函数,你可以用局部变量引用这个函数。举个例子,代码
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
访问外部的局部变量(也就是,闭包函数中的变量)不会和访问局部变量那样快,但仍然比访问全局变量快。考虑下面的代码片段:
function foo (x) for i = 1, 1000000 do x = x + math.sin(i) end return xendprint(foo(10))
我们可以通过在foo函数外声明一个sin变量来优化:
local sin = math.sinfunction foo (x) for i = 1, 1000000 do x = x + sin(i) end return xendprint(foo(10))
第二段代码运行比原先那个快30%。
尽管和其他语言的编辑器比,Lua编译器的效率非常高,编译是件繁重的任务。因此,你应该尽可能避免在程序中编译(例如,函数loadstring)。除非你必须运行动态的代码,像通过终端输入的代码,你很少需要编译动态代码。
作为例子,考虑下面的代码,创建一个返回1到10000常数值的函数的表:
local lim = 10000local a = {}for i = 1, lim do a[i] = loadstring(string.format("return %d", i))endprint(a[10]()) --> 10
这段代码运行需要1.4秒。
使用闭包,我们无需动态编译。下面的代码用1/10的时间(0.14秒)创建同样的100000个函数。
function fk (k) return function () return k endendlocal lim = 100000local a = {}for i = 1, lim do a[i] = fk(i)endprint(a[10]()) --> 10
关于表
通常,你不需要为使用表而了解Lua是如何执行表的任何事。实际上,Lua竭尽全力确保实现细节不暴露给用户。然而,这些细节通过表操作的性能展示出来。因此,要优化使用表的程序(这几乎是任何Lua程序),还是知道Lua是如何执行表的会比较好。
在Lua中表的执行涉及一些聪明的算法。Lua中的表有两部分:数组和哈希。对某些特殊的n,数组存储从1到n的整数键的条目。(稍后我们将会讲解这个n是如何计算的。)所有其他的条目(包括范围外的整数键)转到哈希部分。
顾名思义,哈希部分使用哈希计算存储和寻找他们的键。使用被称作开发地址的表,意思是所有的条目被储存在它自己的哈希数组中。哈希函数给出键的主要索引;如果存在冲突(即如何两个键被哈希到同一个位置),这些键被连接到每个元素占用一个数组条目的列表中。
当Lua在表中插入一个新键,并且哈希数组已满的时候,Lua会重新哈希。重新哈希第一步是决定新数组部分和新哈希部分的大小。因此,Lua遍历所有元素,并对其计数,分类,然后选择数组最大尺寸的2的幂次方的长度,以便超过一半的数组元素被填充。哈希大小是最小尺寸的2的幂次方,能够容纳剩余的元素(即那些在数组部分不适合的)。
当Lua创建空表时,数组和哈希这两部分的大小都为0,因此,也没有为他们分配数组。当运行下面代码让我们看看什么会发生:
local a = {}for i = 1, 3 do a[i] = trueend
从创建空表开始。在第一次循环中,a[1] = true赋值时触发重新哈希;Lua设置表的数组部分的大小为1并且让哈希部分为空。在第二次循环中,a[2] = true赋值时再一次触发重新哈希。因此现在表的数组部分的大小为2。最后,第三次再触发重新哈希,数组部分的大小增长到4。
像这样的代码
a = {}a.x = 1; a.y = 2; a.z = 3
也做类似的 操作,除了表的哈希部分增长外。
对于很大的表,初始化的开销会分摊到整个过程的创建:虽然有三个元素的表如要三次重新哈希,但有一百万个元素的表只需要20次。但是当你创建上千个小的表时,总的消耗会很大。
旧版本的Lua创建空表时会预分配几个位置(4个,如果我没记错的话),以避免这种初始化小表时的开销。然而,这种方法会浪费内存。举个例子,如果你创建一百万个坐标点(表现为只有两个元素的表)而每个使用实际需要的两倍内存,你因此会付出高昂的代价。这也是现在Lua创建空表不会预分配的原因。
如果你用C语言编程,你可以通过Lua的API中lua_createtable函数避免那些重新哈希。他在无处不在的lua_State后接受两个参数:新表数组部分的初始大小和哈希部分的初始大小。(虽然重新哈希的运算法则总会将数组的大小设置为2的幂次方,数组的大小可以是任意值。然而,哈希的大小必须是2的幂次方,因此,第二个参数总是取整为不比原值小的较小的2的幂次方)通过给出新表合适的大小,这很容易避免那些初始的再哈希。当心,无论如何,Lua只能在再哈希时候才能收缩表。因此,如果你初始大小比需要的大,Lua可能永远不会纠正你浪费的空间。
当用Lua编程时,你可以用构造器避免那些初始再哈希。当你写下{true, true, true}时,Lua会预先知道表的数组部分将会需要上三个空位,因此Lua用这个大小创建表。同样地,如果你写下{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] = 3end
如果我们创建正确大小的表,我们会将运行时间减少到0.7秒:
for i = 1, 1000000 do local a = {true, true, true} a[1] = 1; a[2] = 2; a[3] = 3end
如果我们写像{[1] = true, [2] = true, [3] = true},然而,Lua不会足够智能到检测给出的表达式(本例中是文字数字)指的是数组索引,因此会创建4个空位的哈希表,浪费了内存和CPU时间。
仅有当表重新哈希时,表的数组和哈希部分的大小才会重新计算,只有在表完全满且Lua需要插入新的元素时候发生。如果你遍历表清除所有的字段(即设置他们为空),结果是表不会收缩。然而,如果你插入一些新的元素,最后表不得不重新调整大小。通常这不是个问题:如果你一直清除元素和插入新的(在很多程序中都是有代表性的),表的大小保持不变。然而,你应该不期望通过清除大的表的字段来恢复内存:最好是释放表本身。
一个强制重新哈希的鬼把戏是插入足够多是空值到表中。看接下来的例子:
a = {}lim = 10000000for i = 1, lim do a[i] = i end -- create a huge tableprint(collectgarbage("count")) --> 196626for i = 1, lim do a[i] = nil end -- erase all its elementsprint(collectgarbage("count")) --> 196626for i = lim + 1, 2*lim do a[i] = nil end -- create many nil elementsprint(collectgarbage("count")) --> 17
我不推荐这种鬼把戏,除非在特殊情况下:这会很慢并且没有容易的方法指导“足够”是指多少元素。
你可能会好奇为什么当插入空值时Lua不会收缩表。首先,要避免测试插入表的是什么;检测赋空值会导致所有的赋值变慢。其次,更重要的是,当遍历表时允许赋空值。思考接下来的这个循环:
for k, v in pairs(t) do if some_property(v) then t[k] = nil -- erase that element endend
如果赋空值后Lua对表重新哈希,这回破坏本次遍历。
如果你想清空表中所有的元素,一个简单的遍历是实现他的正确方法:
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
然而,对于很大的表这个循环会非常慢。函数next,当不带前一个键调用时,返回表的“第一个”元素(以某种随机顺序)。这样做,next函数开始遍历表的数组,查找不为空的元素。当循环设置第一个元素为空时,next函数花更长的时间查找第一个非空元素。结果是,“聪明”的循环花费20秒清除有100,000个元素的表;使用pairs遍历循环花费0.04秒。
关于字符串
和表一样,为了更高效的使用字符串,最好知道Lua是如何处理字符串的。
不同于大多数的脚本语言,Lua实现字符串的方式表现在两个重要的方面。第一,Lua中所有的字符串都是内化的。意思是Lua对任一字符串只保留一份拷贝。无论何时出现新字符串,Lua会检测这个字符串是否已经存在备份,如果是,重用拷贝。内化使像字符串的比较和表索引操作非常快,但是字符串的创建会慢。
第二,Lua中的变量从不持有字符串,仅是引用他们。这种实现方式加快了几个字符串的操作。举个例子,在Perl语言中,当你写下类似于$x = $y,$y含有一个字符串,赋值会从$y缓冲中字符串内容复制到$x的缓冲。如果字符串很长的话,这就会变成昂贵的操作。在Lua中,这种赋值只需复制指向字符串的指针。
然而,这种带有引用实现减慢了字符串连接的这种特定形式。在Perl中,$s = $s . "x"和$s . = "x"操作使完全不一样的。在第一个中,你得到的一个$s的拷贝,并在它的末尾加上“x”。在第二个中,“x”简单地附加到由$s变量保存的内部缓冲上。因此,第二种形式和字符串的大小不相关(假设缓冲区有多余文本的空间)。如果你在循环内部用这些命令,他们的区别是线性和二次方算法的区别。举个例子,下面的循环读一个5M的文件花费了约5分钟。
$x = "";while (<>) { $x = $x . $_;}
如果我们把 $x = $x . $_ 变成 $x .= $_, 这次时间下降到0.1秒!
Lua不支持第二个,更快的那个,这是因为它的变量没有缓冲和它们相关联。因此,我们必须用显示的缓冲:字符串表做这项工作。下面的循环0.28秒读取同样的5M文件。虽然不如Perl快,但也很不错了。
local t = {}for line in io.lines() do t[#t + 1] = lineends = table.concat(t, "\n")
简化,复用,再生
当处理Lua资源时,我们应该同样用推动地球资源的3R倡议。
简化是这三个选项中最简单的。有几种方法可以避免对新对象的需要。举个例子,如果你的程序使用了很多的表,可以考虑数据表现的改动。举个简单的例子,考虑程序操作折线。在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][1]更容易理解。
另一个更经济的做法是一个列表存放坐标的x,另一个存放坐标的y:
polyline = { x = { 10.3, 10.3, 15.0, ...}, y = { 98.5, 18.3, 98.5, ...}}
原来的p[i].x 变成现在的 p.x[i]。通过使用这种做法,一百万个点的折线仅仅用了24KB的内存。
查找减少生成垃圾的好地方是在循环中。举个例子,如果在循环中不断的创建表,你可以从循环中把它移出来,甚至在外面封装创建函数。比较:
function foo (...) for i = 1, n do local t = {1, 2, 3, "hi"} -- do something without changing ’t’ ... endendlocal t = {1, 2, 3, "hi"} -- create ’t’ once and for allfunction foo (...) for i = 1, n do -- do something without changing ’t’ ... endend
闭包可以用同样的技巧,只要你不把它们移出它们所需要的变量的作用域。举个例子,考虑接下来的函数:
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") endend
我们通过把内部的函数移到循环的外面来避免为每行创建一个新的闭包:
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") endend
然而,我们不能把aux已到changenumbers函数外面,因为那样aux不能访问到limit和delta。
对于很多种字符串处理,我们可以通过操作现存字符串的索引来减少对新字符串的需要。举个例子,string,find函数返回他找到模式的位置,代替了匹配。通过返回索引,对于每次成功匹配可以避免创建一个新(子)的字符串。当必要时,程序员可以通过调用string.sub得到匹配的子字符串。(标准库有一个比较子字符串的功能是个好主意,以便我们不必从字符串提取出那个值(因而创建了一个新字符串))
当我们不可避免使用新对象时,通过重用我们任然可以避免创建那些新对象。对于字符串的重用是没有必要的,因为Lua为我们做好了:它总是内化用到的所有字符串,因此,尽可能重用它们。然而,对于表来说,重用可能非常有效。作为一个常见的例子,让我回到在循环中创建表的情况。然而,这次表里的内容不是常量。尽管如此,我们仍然可以频繁的在所有迭代中重用同一个表,仅仅改变它的内容。考虑这个代码块:
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中新的模式匹配包,对memoizing的使用很有意思。LPeg把每个模式编译成内在的形式,一个用于解析机器执行匹配的“程序”。这种编译与匹配自身相比代价非常昂贵。因此,LPeg记下它的编译结果并复用。一个简单的表将描述模式的字符串与相应的内部表示相关联。
memoizing的通常问题是储存以前结果花费的空间可能超过复用这些结果的收益。Lua为了解决这个问题,我们可以用弱表来保存结果,以便没有用过的结果最后能从表里移除。
Lua中,用高阶函数我们可以定义个通用的memoization函数:
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
给出任意的函数f,, memoize(f)返回一个新的和f返回相同结果的函数,并且记录它们。举个例子,我们可以重新定义带memoizing版本的loadstring:
loadstring = memoize(loadstring)
我们完全像之前的那个那样使用新函数,但是如果我们加载的字符串中有很多重复的,我们能获得可观的收益。
如果你的程序创建和释放太多的协程,回收再生可能是个提高性能的选择。当前的协程API不提供直接支持复用协程,但是我们可以突破这个限制。考虑下面的协程
co = coroutine.create(function (f) while f do f = coroutine.yield(f()) end end
这个协程接受一个作业(运行一个函数),返回它,并且完成后等待下一个作业。
Lua中大多数的再生由垃圾回收器自动执行。Lua用一个增量的垃圾回收器。这意味着回收器表现为以较小的步调(逐步地)与程序执行交错执行任务。这些步调的节奏正比于内存分配:Lua每分配一定量的内存,垃圾收集器就会做同样比例的工作。程序消耗内存越快,收集器回收的越快。
如果我们对程序应用简化和复用原则,通常收集器没有太多的工作可做。但是有时我们不能避免大量垃圾的产生,此时收集器就变的笨重了。Lua中垃圾收集器为一般程序做了调整,因此在多数软件中表现的相当不错。然而,有时对于特殊的情况通过调整收集器我们可以提高程序的性能。
我们可以通过Lua中collectgarbage函数或C中的lua_gc控制垃圾收集器。尽管接口不同,但两者都提供的功能基本一样。我会用Lua的接口来讨论,但是,通常这种操作用C比较好。
collectgarbage函数提供了几个功能:它可以停止和重启收集器,强制完整的收集循环,强制收集的一步,获得Lua使用的总内存,并且改变影响收集器步幅的两个参数。当调整内存不足的程序时它们各有用途。
对于某些类型的批处理程序,“永远”停止收集器是个选择,它们创建几个数据结构,基于这些数据结构产生输出,然后退出(例如编辑器)。对于这些程序,试图回收垃圾可能浪费时间,因为只有很少的垃圾被回收,并且当程序结束时所有的内存会被释放。
对于非批处理的程序,永远停止收集器并非是个选择。尽管如此,这些程序可能会收益于在某些关键时期停止收集器。如果有必要,程序可以完全控制垃圾收集器,做法是一直保持它停止,只有明确地强制一个步骤或一次完整收集来运行它运行。举个例子,有些事件驱动平台提供设置idle函数选项,当没有其他的事件处理时才会被调用。这是垃圾回收的绝佳时间。(Lua5.1中,每次当收集器停止时,强制执行某些收集。因此,强制某些收集后你必须立即调用collectgarbage("stop")来保持他们停止。)
最后,作为最后一个手段,你可以尝试更改收集器的参数。收集器有两个参数控制它的步幅。第一个叫做pause,控制收集器在完成一个收集周期和开始下一个等待多长时间。第二个参数叫做stepmul(来自step multiplier),控制每一个步骤收集器收集多少。简言之,较小的暂停和较大的步幅能提高收集器的速度。
这些参数对程序的总体性能影响是很难预料的。更快的收集器明显浪费更多的CPU周期;然而,它能减少程序使用的总的内存,从而减少分页。只有仔细的尝试才能给你这些参数的最佳值。
后记
正如我们介绍中讨论的那样,优化是有技巧的。这里有几点需要注意,首先程序是否需要优化。如果它有实际的性能问题,那么我们必须定位到哪个地方以及如何优化。
这里我们讨论的技术既不是唯一也不是最重要的一个。我们关注的是Lua特有的技术,因为有更多的针对通用技术的资料。
在我们结束前,我想提两个在提升Lua程序性能边缘的选项。因为这两个都涉及到Lua代码之外的变化。第一个是使用LUaJIT,Mike Pall开发的Lua即使编译器。他已经做了出色的工作,并且LuaJIT可能是目前动态语言最快的JIT。缺点是,他只能运行在x86架构上,而且,你需要非标准的Lua解释器(LuaJIT)来运行程序。优点是在一点也不改变代码的情况下能快5倍的速度运行你的程序。
第二个选择是把部分代码放到C中。毕竟,Lua的特点之一是与C代码结合的能力。这种情况下,最重要的一点是为C代码选择正确的粒度级别。一方面,如果你只把非常简单的函数移到C中,Lua和C通信的开销可能超过那些函数对性能提升的收益。另一方面,如果你把太大的函数移到C中,又会失去灵活性。