精华 给lua写一个高效split过程中所犯的错误(附v8实现简要分析)。
发布于 1 年前 作者 coordcn 2134 次浏览 来自 分享

javascript里的string.split很好用,半个月之前想给lua实现一个,最初的版本:

function split(text, pattern)
    local i = 0
    local parts = {}
    for part in string.match(text, pattern) do
      i = i + 1
      parts[i] = part
    end
    return parts, i
end

这个版本只能支持正则表达式,不支持普通字符串,不支持utf-8编码,pattern也不支持传入空字符串(将字符串以字符为单位分割成数组),最让人心碎的是性能,跟javascript比,正则表达式性能差距将进10倍,如果分割单个字符如 “/”,性能差距更是近百倍,这么巨大的差距我当时就傻眼了,难道我选择lua错了?短暂的蒙逼之后开始优化。很快我用c撸了一个split出来,单字符串的,算法就是暴力的一个一个字符比较。用了c,lua的split也支持了普通字符,同样的 split(text, ‘/’),比正则性能提升4-5倍,但跟javascript差距还是巨大。

在巨大的差距面前,我失去了理智,决定死磕到底,我不相信自己如此低能,同样是编译代码,lua与javascript代码竟然有这么大的差距?难道传说中的v8一些代码性能超过c是真的?难道lua5.3的效率跟javascript比差距如此之大?这种纯粹函数调用,字符串分割即便用luajit我认为提升效果也是有限的。luajit提升的主要是数值计算性能,对字符串有成倍的性能提升就很好了。

接下来的c版本 105行我用void *memchr(void *s, int c, n)代替逐个字符比较,但测试结果提升非常有限,分析原因,主要是被分割的子串太短,memchr的原理是先对内存地址进行对齐,对64系统而言就是内存地址如果不是8的倍数,前面几个内存还是逐个字符比较,直到内存地址为8的倍数,然后以64位整数读取后面的数据比较(具体实现参看strlen的源代码解析,strlen本质上是memchr的特例 http://www.cppblog.com/ant/archive/2007/10/12/32886.html ),显而易见,这种方式对长度小于8的子串是不会有提升的,子串长度超过8,且对齐良好的才有提升,也就是说至少要16个字符才勉强核算,越长性能越好。

c改进版本对长字串还是有用的,但整体效果比较下来还是有20倍以上的差距,面对这些差距,我只能将单字符分割先放一放,实现utf-8字符串的空字符串分割。下面是utf-8编码规则:

/* U-00000000 - U-0000007F: 0xxxxxxx 
 * U-00000080 - U-000007FF: 110xxxxx 10xxxxxx 
 * U-00000800 - U-0000FFFF: 1110xxxx 10xxxxxx 10xxxxxx 
 * U-00010000 - U-001FFFFF: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx 
 * U-00200000 - U-03FFFFFF: 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 
 * U-04000000 - U-7FFFFFFF: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 
 */

了解了编码规则,将字符提取出来就简单了,编码完成 77行 ,性能测试与javascript差距为一倍,看到这个结果,虽然不满意,但是心里的石头总算落下来了,这此至少不是数量极的差距。

单字符和空字符完成,接下来搞按字符串分割,字符串分割暴力比较是最显而易见的,strstr就能干,但为了性能,为了自己心灵不再受到javascript变太性能的伤害,我要选择一个性能优秀的算法,可选的有KMP,Boyer-Moore,Sunday,鉴于自己智商不足,最终选择了Sunday,Sunday是Boyer-Moore的简化版本,相对容易实现,性能上比其他两个不算差,编码实现 158行后性能差距在10倍左右。

把三种需求都用c实现一遍之后,我不得不承认javascript的性能是太强悍了,即便javascript用正则,lua用字符打个平手也勉强。痛定思通,我要知道为什么,知道自己怎么会这么搓的?

为了知道为什么?我们需要召唤 valgrind,最初接触valgrind是在libuv的测试代码里,我当时还不知道这东西是什么,只看到每个测试函数末尾都会加一句MAKE_VALGRIND_HAPPY();,我当时就在想,这个VALGRIND是个什么东西,为什么要让他happy,他是程序员的大爷?后来我了解到,这货果然是程序员的大爷,内存检测,性能分析,这货无所不能。

性能分析用的是valgrind的工具callgrind,用它运行debug版本的程序,可以生成函数调用性能分析,每个函数被调用了多少次,耗费性能比例都能够分析出来,更妙的是,搭配 gprof2dot.py(centos安装:yum install graphviz)这个图形化工具,你还能将callgrind的分析数据生成简单易懂的图片

用valgrind对单字符split进行分析后发现,性能主要是损失在子字符串生成上,当子字符串比较短时,小于40个字符,字符串hash占了大头,当字符串长度超过40,lua给字符串内存分配占了大头。出现这种状况的主要原因是lua默认对长度小于40的字符串重复使用,不重新分配内存生成,所有相同的字符串都指向一个内存,这个时候字符串查找比较进行hash计算是主要矛盾,而当大于40长度之后,重新生成分配内存就成了主要矛盾。经过测试,lua所作的小字符优化工作可以将性能提高一倍左右,原因是相对hash计算,生成重复的对像,消耗的内存分配,GC上的性能损失更大。经过分析,显然,性能的瓶颈并不在c,而在c将字符串给lua生成字符串,这样,死磕c代码的意义已经不大了。至此,我们可以得出一个结论,对lua而言,从c向lua传递字符串的代价是很大的,只要涉及到传递字符串,最好的情况也要承受hash带来的性能损失。结论是能不传字符串就不传,能传短的就传短的。lua如此,对于javascript是不是也是这样呢?

带着这些疑问我进入了v8的源代码,这东西的源代码我看fibjs的时候看过几眼,当时就觉得看完之后眼冒金星,完全没有头绪,这是标准的智商欠费表现,从此之后我便再也没有敢去看,这次为了一探究竟只好豁出去了。正所谓智商不足勤劳补,多看几次也许能明白,况且这次目的性很强,高精尖的编译,jit看不懂就随它去了,一个runtime函数搞定应该不成问题。

带着问题,我找到了三个关键文件:

https://github.com/nodejs/node/blob/master/deps/v8/src/js/regexp.js 300行

https://github.com/nodejs/node/blob/master/deps/v8/src/runtime/runtime-regexp.cc 683行

https://github.com/nodejs/node/blob/master/deps/v8/src/string-search.h

源码之下无秘密,javascript为什么那么快?这个结果我先不说。我们先来回顾下memchr,KMP,Boyer-Moore,Sunday,lua对短字符串生成优化,这些算法的本质是什么?这些算法的本质是尽量不做无谓的计算,如果可以,就不计算,再不行,尽量少计算。javascript单字符查找分割跟我的算法差不多,字符串查找分割用的是Boyer-Moore,比我高级那么一点点,utf-8字符分割大家也是差不多。难道真是v8强悍到无以复加的地步?v8jit强悍在数值时是成立的,但字符串能够跟lua5.3拉开这么大差距可能有这么大的差距么?测试结果答案是肯定的,但源代码告诉我们了一切,javascript对相同字符串分割结进行了cache 695行,也就是说,javascript对同样的字符串分割只会进行一次计算,自然也就没有子串的生成问题和GC压力,这才是优化的真谛,不必要的计算,不计算才是最快的。

因为这个问题,死磕了半个月,找到原因后,我才意识到自己犯了个大错误,过早的优化是有害的,浪费时间,打击士气,一度我都怀疑自己的选择,lua虽然在异步编程模型上比javascript好,但如果性能差距太大的话,谁会去用呢?我担心这个问题,却被一个显而易见的道理蒙蔽了,我怎么就肯定split就是性能的关键呢,那个1毫秒都不到的差距真的那么重要么?先做一个堪用的东西出来,然后一步步完善才是正途。

4 回复

源代码链接更新了。

@alsotang @i5ting 建议链接颜色改成蓝色的,灰色不太显眼。

@alsotang 谢谢,辛苦了。

回到顶部