深圳网站设计推广,重庆公司建站,做网站设计注意什么细节,凡科快图官网制作规则1#xff1a;不要优化。 规则2#xff1a;仍然不要优化#xff08;专家除外#xff09; 当用Lua编程时#xff0c;这两条规则显得尤为重要。Lua以性能著称#xff0c;而且在脚本语言中也因此而值得赞美。 然而#xff0c;我们都知道性能是编程的一个关键因素。具有复… 规则1不要优化。 规则2仍然不要优化专家除外 当用Lua编程时这两条规则显得尤为重要。Lua以性能著称而且在脚本语言中也因此而值得赞美。 然而我们都知道性能是编程的一个关键因素。具有复杂指数时间的问题被称作疑难问题并不是偶然发生。太迟的结果是无用的结果。因此每个优秀的程序员应该总是在花费资源去优化一段代码的代价和这段代码在运行代码时节约资源的收益相平衡。一个优秀的程序员关于优化的第一个问题总是会问“程序需要优化吗”如果答案是肯定的仅当此时第二个问题应该是“哪地方” 为了回答这两个问题我们需要些手段。我们不应该在没有合适的测量时尝试优化软件。大牛和菜鸟之前的不同不是有经验的程序员更好的指出程序的一个地方可能耗时不同之处是大牛知道他们并不擅长那项任务。 最近几年Noemi Rodriguez和我用Lua开发了一个CORBA ORBObject Request Broker原型后来进化成OiLOrb 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) doif some_property(v) thent[k] nil -- erase that elementendend 如果赋空值后Lua对表重新哈希这回破坏本次遍历。 如果你想清空表中所有的元素一个简单的遍历是实现他的正确方法 for k in pairs(t) dot[k] nilend “聪明”的选择是这个循环 while true dolocal k next(t) if not k then break endt[k] nilend 然而对于很大的表这个循环会非常慢。函数next当不带前一个键调用时返回表的“第一个”元素以某种随机顺序。这样做next函数开始遍历表的数组查找不为空的元素。当循环设置第一个元素为空时next函数花更长的时间查找第一个非空元素。结果是“聪明”的循环花费20秒清除有100000个元素的表使用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() dot[#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 dot[i] os.time({year i, month 6, day 14})end 下边这个是等同的但是它重用了表 local t {}local aux {year nil, month 6, day 14}for i 1970, 2000 doaux.year it[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 rendend 给出任意的函数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代码之外的变化。第一个是使用LUaJITMike Pall开发的Lua即使编译器。他已经做了出色的工作并且LuaJIT可能是目前动态语言最快的JIT。缺点是他只能运行在x86架构上而且你需要非标准的Lua解释器LuaJIT来运行程序。优点是在一点也不改变代码的情况下能快5倍的速度运行你的程序。 第二个选择是把部分代码放到C中。毕竟Lua的特点之一是与C代码结合的能力。这种情况下最重要的一点是为C代码选择正确的粒度级别。一方面如果你只把非常简单的函数移到C中Lua和C通信的开销可能超过那些函数对性能提升的收益。另一方面如果你把太大的函数移到C中又会失去灵活性。 本文转自 bxst 51CTO博客原文链接:http://blog.51cto.com/13013670/1943995
