编写高性能的Lua代码

标签: 性能 lua 代码 | 发表时间:2014-04-17 18:13 | 作者:Tim's Blog
出处:http://9.douban.com/channel/technology

前言

Lua是一门以其性能著称的脚本语言,被广泛应用在很多方面,尤其是游戏。像《魔兽世界》的插件,手机游戏《大掌门》《神曲》《迷失之地》等用Lua来写游戏逻辑。

所以大部分时候我们不需要去考虑性能问题。Knuth有句名言:“过早优化是万恶之源”。其意思就是过早优化是不必要的,会浪费大量时间,而且容易导致代码混乱。

所以一个好的程序员在考虑优化性能前必须问自己两个问题:“我的程序真的需要优化吗?”。如果答案为是,那么再问自己:“优化哪个部分?”。

我们不能靠臆想和凭空猜测来决定优化哪个部分,代码的运行效率必须是 可测量的。我们需要借助于分析器来测定性能的瓶颈,然后着手优化。优化后,我们仍然要借助于分析器来测量所做的优化是否真的有效。

我认为最好的方式是在首次编写的时候按照最佳实践去写出高性能的代码,而不是在编写了一堆垃圾代码,然后再考虑优化。相信工作后大家都会对事后的优化的繁琐都深有体会。

一旦你决定编写高性能的Lua代码,下文将会指出在Lua中哪些代码是可以优化的,哪些代码会是缓慢的然后怎么去优化它们。

使用Local

在代码运行前,Lua会把源码预编译成一种中间码,类似于Java的虚拟机。这种格式然后会通过C的解释器进行解释,整个过程其实就是通过一个 while循环,里面有很多的 switch...case语句,一个 case对应一条指令来解析。

自Lua 5.0之后,Lua采用了一种类似于寄存器的虚拟机模式。Lua用 来储存其寄存器。每一个活动的函数,Lua都会其分配一个栈,这个栈用来储存函数里的活动记录。每一个函数的栈都可以储存至多250个寄存器,因为栈的长度是用8个比特表示的。

有了这么多的寄存器,Lua的预编译器能把所有的local变量储存在其中。这就使得Lua在获取local变量时其效率十分的高。

举个栗子: 假设a和b为local变量, a = a + b的预编译会产生一条指令:

;a是寄存器0 b是寄存器1
ADD 0 0 1

但是若a和b都没有声明为local变量,则预编译会产生如下指令:

GETGLOBAL    0 0    ;get a
GETGLOBAL    1 1    ;get b
ADD          0 0 1  ;do add
SETGLOBAL    0 0    ;set a

所以你懂的:在写Lua代码时, 你应该尽量使用local变量

以下是几个对比测试,你可以复制代码到你的编辑器中,进行测试。

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,耗时1.11秒;使用local变量 sin来保存 math.sin,耗时0.76秒。可以获得30%的效率提升!

关于表(table)

表在Lua中使用十分频繁,因为表几乎代替了Lua的所有容器。所以快速了解一下Lua底层是如何实现表,对我们编写Lua代码是有好处的。

Lua的表分为两个部分:数组(array)部分和哈希(hash)部分。数组部分包含所有从1到n的整数键,其他的所有键都储存在哈希部分中。

哈希部分其实就是一个哈希表,哈希表本质是一个数组,它利用哈希算法将键转化为数组下标,若下标有冲突(即同一个下标对应了两个不同的键),则它会将冲突的下标上创建一个 链表,将不同的键串在这个链表上,这种解决冲突的方法叫做:链地址法。

当我们把一个新键值赋给表时,若数组和哈希表已经满了,则会触发一个再哈希(rehash)。再哈希的代价是高昂的。首先会在内存中分配一个新的长度的数组,然后将所有记录再全部哈希一遍,将原来的记录转移到新数组中。新哈希表的长度是最接近于所有元素数目的2的乘方。

当创建一个空表时,数组和哈希部分的长度都将初始化为0,即不会为它们初始化任何数组。让我们来看下执行下面这段代码时在Lua中发生了什么:

local a = {}
for i=1,3 do
    a[i] = true
end

最开始,Lua创建了一个空表a,在第一次迭代中, a[1] = true触发了一次rehash,Lua将数组部分的长度设置为 2^0,即1,哈希部分仍为空。在第二次迭代中, a[2] = true再次触发了rehash,将数组部分长度设为 2^1,即2。最后一次迭代,又触发了一次rehash,将数组部分长度设为 2^2,即4。

下面这段代码:

a = {}
a.x = 1; a.y = 2; a.z = 3

与上一段代码类似,只是其触发了三次表中哈希部分的rehash而已。

只有三个元素的表,会执行三次rehash;然而有一百万个元素的表仅仅只会执行20次rehash而已,因为 2^20 = 1048576 > 1000000。但是,如果你创建了非常多的长度很小的表(比如坐标点: point = {x=0,y=0}),这可能会造成巨大的影响。

如果你有很多非常多的很小的表需要创建时,你可以将其初始化以避免rehash。比如: {true,true,true},Lua知道这个表有三个元素,所以Lua直接创建了三个元素长度的数组。类似的, {x=1, y=2, z=3},Lua会在其哈希部分中创建长度为4的数组。

以下代码执行时间为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

如果我们在创建表的时候就规定好它的大小,则只需要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

所以, 当需要创建非常多的小size的表时,预先填充好表的大小

关于字符串

与其他主流脚本语言不同的是,Lua在实现字符串类型有两方面不同。

第一,所有的字符串在Lua中都只储存一份拷贝。当新字符串出现时,Lua检查是否有其相同的拷贝,若没有则创建它,否则,指向这个拷贝。这可以使得字符串比较和表索引变得相当的快,因为比较字符串只需要检查引用是否一致即可;但是这也降低了创建字符串时的效率,因为Lua需要去查找比较一遍。

第二,所有的字符串变量,只保存字符串引用,而不保存它的buffer。这使得字符串的赋值变得十分高效。例如在Perl中, $x = $y,会将$y的buffer整个的复制到$x的buffer中,当字符串很长时,这个操作的代价将十分昂贵。而在Lua,同样的赋值,只复制引用,十分的高效。

但是只保存引用会降低在字符串连接时的速度。在Perl中, $s = $s . 'x'$s .= 'x'的效率差距惊人。前者,将会获取整个$s的拷贝,并将’x’添加到它的末尾;而后者,将直接将’x’插入到$x的buffer末尾。

由于后者不需要进行拷贝,所以其效率和$s的长度无关。

在Lua中,并不支持第二种更快的操作。以下代码将花费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来模拟buffer,下面的代码只需花费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

所以: 在大字符串连接中,我们应避免 ..。应用table来模拟buffer,然后concat得到最终字符串

3R原则

3R原则(the rules of 3R)是:减量化(reducing),再利用(reusing)和再循环(recycling)三种原则的简称。

3R原则本是循环经济和环保的原则,但是其同样适用于Lua。

Reducing

有许多办法能够避免创建新对象和节约内存。例如:如果你的程序中使用了太多的表,你可以考虑换一种数据结构来表示。

举个栗子。 假设你的程序中有多边形这个类型,你用一个表来储存多边形的顶点:

polyline = {
    { x = 1.1, y = 2.9 },
    { x = 1.1, y = 3.7 },
    { x = 4.6, y = 5.2 },
    ...
}

以上的数据结构十分自然,便于理解。但是每一个顶点都需要一个哈希部分来储存。如果放置在数组部分中,则会减少内存的占用:

polyline = {
    { 1.1, 2.9 },
    { 1.1, 3.7 },
    { 4.6, 5.2 },
    ...
}

一百万个顶点时,内存将会由95KB减少到65KB,但是代价是代码的可读性降低了。

最变态的方法是:

polyline = {
    x = {1.1, 1.1, 4.6, ...},
    y = {2.9, 3.7, 5.2, ...}
}

一百万个顶点,内存将只占用24KB,你需要在性能和代码可读性之间做出取舍。

在循环中,我们更需要注意实例的创建。

for i=1,n do
    local t = {1,2,3,'hi'}
    --执行逻辑,但t不更改
    ...
end

我们应该把在循环中不变的东西放到循环外来创建:

local t = {1,2,3,'hi'}
for i=1,n do
    --执行逻辑,但t不更改
    ...
end

Reusing

如果无法避免创建新对象,我们需要考虑重用旧对象。

考虑下面这段代码:

local t = {}
for i = 1970, 2000 do
    t[i] = os.time({year = i, month = 6, day = 14})
end

在每次循环迭代中,都会创建一个新表 {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

另一种方式的重用,则是在于缓存之前计算的内容,以避免后续的重复计算。后续遇到相同的情况时,则可以直接查表取出。这种方式实际就是 动态规划效率高的原因所在,其本质是用空间换时间。

Recycling

Lua自带垃圾回收器,所以我们一般不需要考虑垃圾回收的问题。

了解Lua的垃圾回收能使得我们编程的自由度更大。

Lua的垃圾回收器是一个增量运行的机制。即回收分成许多小步骤(增量的)来进行。

频繁的垃圾回收可能会降低程序的运行效率。

我们可以通过Lua的 collectgarbage函数来控制垃圾回收器。

collectgarbage函数提供了多项功能:停止垃圾回收,重启垃圾回收,强制执行一次回收循环,强制执行一步垃圾回收,获取Lua占用的内存,以及两个影响垃圾回收频率和步幅的参数。

对于批处理的Lua程序来说,停止垃圾回收 collectgarbage("stop")会提高效率,因为批处理程序在结束时,内存将全部被释放。

对于垃圾回收器的步幅来说,实际上很难一概而论。更快幅度的垃圾回收会消耗更多CPU,但会释放更多内存,从而也降低了CPU的分页时间。只有小心的试验,我们才知道哪种方式更适合。

结语

我们应该在写代码时,按照高标准去写,尽量避免在事后进行优化。

如果真的有性能问题,我们需要用工具量化效率,找到瓶颈,然后针对其优化。当然优化过后需要再次测量,查看是否优化成功。

在优化中,我们会面临很多选择:代码可读性和运行效率,CPU换内存,内存换CPU等等。需要根据实际情况进行不断试验,来找到最终的平衡点。

最后,有两个终极武器:

第一、使用 LuaJIT,LuaJIT可以使你在不修改代码的情况下获得平均约5倍的加速。查看LuaJIT在 x86/x64下的性能提升比

第二、将瓶颈部分用C/C++来写。因为Lua和C的天生近亲关系,使得Lua和C可以混合编程。但是C和Lua之间的通讯会抵消掉一部分C带来的优势。

注意:这两者并不是兼容的,你用C改写的Lua代码越多,LuaJIT所带来的优化幅度就越小。

声明

这篇文章是基于Lua语言的创造者Roberto Ierusalimschy在 Lua Programming Gems 中的 Lua Performance Tips翻译改写而来。本文没有直译,做了许多删节,可以视为一份笔记。

感谢Roberto在Lua上的辛勤劳动和付出!

相关 [性能 lua 代码] 推荐:

编写高性能的Lua代码

- - 九点 科技
Lua是一门以其性能著称的脚本语言,被广泛应用在很多方面,尤其是游戏. 像《魔兽世界》的插件,手机游戏《大掌门》《神曲》《迷失之地》等用Lua来写游戏逻辑. 所以大部分时候我们不需要去考虑性能问题. Knuth有句名言:“过早优化是万恶之源”. 其意思就是过早优化是不必要的,会浪费大量时间,而且容易导致代码混乱.

5本Lua免费电子书

- sospartan - 读写网 ReadWriteWeb
在最新的编程语言排名中,Lua超过了JavaScript进入了前十名──许多人使用Lua进行“魔兽世界”的脚本编写. 所以,在本周的免费资源推荐中我们找到了一些免费的学习Lua的电子书,无论你想使.

Lua 下实现抢占式多线程

- Coder(码农) - 云风的 BLOG
Lua 5.2 的开发进度可以回溯到 2010 年 1 月. 漫长的流程到今天已经快两年过去,终于等到了 beta 版. 我十分期待它可以在 2011 年内正式发布. 在这几经折腾的两年里,许多新特性企图挤进 5.2 版,又最终被否决. 当我们审视改进列表,似乎看不到太多耳目一新的东西. 但如果仔细阅读一下源代码,就会发现,大部分地方都重新实现过了,以配合这些表面上看起来不大的修改.

nginx+lua+memcache实现灰度发布

- - 开源软件 - ITeye博客
灰度发布在百度百科中解释:. 灰度发布是指在黑与白之间,能够平滑过渡的一种发布方式. AB test就是一种灰度发布方式,让一部分用户继续用A,一部分用户开始用B,如果用户对B没有什么反对意见,那么逐步扩大范围,把所有用户都迁移到B上面 来. 灰度发布可以保证整体系统的稳定,在初始灰度的时候就可以发现、调整问题,以保证其影响度.

Java 代码性能优化

- - IT瘾-geek
代码 优化,一个很重要的课题. 可能有些人觉得没用,一些细小的地方有什么好修改的,改与不改对于代码的运行效率有什么影响呢. 这个问题我是这么考虑的,就像大海里面的鲸鱼一样,它吃一条小虾米有用吗. 没用,但是,吃的小虾米一多之后,鲸鱼就被喂饱了. 代码优化也是一样,如果项目着眼于尽快无BUG上线,那么此时可以抓大放小,代码的细节可以不精打细磨;但是如果有足够的时间开发、维护代码,这时候就必须考虑每个可以优化的细节了,一个一个细小的优化点累积起来,对于代码的运行效率绝对是有提升的.

采访 Lua 发明人的一篇文章

- KK - 云风的 BLOG
《Masterminds of Programming: Conversations with the Creators of Major Programming Languages》是本相当不错的书. 博文翻译出版了这本书,中文名叫做《编程之魂》. 书是好书,可惜翻译这本书需要对各种语言的深入研究,看起来译者有点力不从心.

lua中处理变参数的一些技巧

- return - 为着理想勇敢前进
从lua 5.1开始,就不鼓励用隐含的arg来处理可变变量了,推荐做法是使用递归来处理.... 在lua中,不论多返回值还是函数调用,...都只能用于最后剩下的参数,例如下列代码中. 这是因为第一个print调用是把...作为剩余的所有参数传进去,而第二次调用,...则被调整为1个参数. 如果要想把参数添加到...后面,有两种做法.

开发愤怒的小鸟的Lua语言:Wax框架详解

- sun - Starming星光社最新更新
摘要:我们都知道Objective-C和Cocoa语言可以开发iOS应用,但是一年前,苹果决定在 iOS系统上使用Lua语言. Wax框架的想法很简单:凡是Objective-C能做的,Lua也能做. 考虑使用像Lua这样一门简单而高效的编程语 言,构建原生iPhone应用程序有许多充分的理由,而本文将深入探讨Wax具有的一些好处,同时演示把Lua与Xcode 4和iOS软件开发工具包(SDK)集成起来必不可少的实际步骤.

使用varnish + nginx + lua搭建网站的降级系统

- - 博学无忧
通常一个网站数据库挂掉后,后果将是非常严重的. 对于一些网站来说,当数据库挂掉后,如果能提供基本的浏览服务,也是不错的. 本文将尝试使用varnish + nginx + lua 搭建网站降级系统来实现整个目标. 降级方案的目标是,当网站出现致命故障时(如出现500错误,不能提供服务),可以把缓存的页面数据展现给用户.

使用 Lua 编写一个 Nginx 认证模块

- - 开源软件 - ITeye博客
我考虑了几种解决方案,罗列如下:. 用一个简单的Python/Flask模块来做代理和验证. 一个使用subrequests做验证的nginx模块(nginx目前可以做到这一点). 使用Lua编写一个nginxren认证模块. 很显然,给整个系统添加额外请求将执行的不是很好,因为这将会增加延迟(特别是给每一个页面文件都增加一个请求是很让人烦恼的).这就意味着我们把 subrequest模块排除在外了.