Lua源码中字符串类型的实现
概述
Lua完全采用8位编码,Lua字符串中的字符可以具有任何数值编码,包括数值0。也就是说,可以将任意二进制数据存储到一个字符串中。Lua的字符串是不可变的值(immutablevalues)。如果修改,实质上是新建一个字符串。根据上文《Lua中数据类型的源码实现》中知道,在Lua中,字符串是自动内存管理机制所管理的对象,并且由联合体TString来实现存储字符串值的。下面将通过Lua5.2.1的源码来看字符串的实现以及总结了在Lua中使用字符串的注意事项。
源码实现
首先来看字符串对应的数据结构TString,其源码如下(lobject.h):
410/* 411**Headerforstringvalue;stringbytesfollowtheendofthisstructure 412*/ 413typedefunionTString{ 414L_Umaxaligndummy;/*ensuresmaximumalignmentforstrings*/ 415struct{ 416CommonHeader; 417lu_byteextra;/*reservedwordsforshortstrings;"hashash"forlongs*/ 418unsignedinthash; 419size_tlen;/*numberofcharactersinstring*/ 420}tsv; 421}TString;
对这个联合体定义,有几点值得说明:
I、联合体TString中成员L_Umaxaligndummy是用来保证与最大长度的C类型进行对齐,其定义如下(llimits.h):
48/*typetoensuremaximumalignment*/ 49#if!defined(LUAI_USER_ALIGNMENT_T) 50#defineLUAI_USER_ALIGNMENT_Tunion{doubleu;void*s;longl;} 51#endif 52 53typedefLUAI_USER_ALIGNMENT_TL_Umaxalign;
在其他可会回收的对象(比如table)的实现中,也可看到这个联合体成员,这样做的目的是通过内存对齐,加快CPU访问内存的速度。
II、联合体中成员tsv才是真正用来实现字符串的。其中成员CommonHeader用于GC,它会以宏的形式在所有的可回收对象中定义,代码如下(lobject.h):
74/* 75**CommonHeaderforallcollectableobjects(inmacroform,tobe 76**includedinotherobjects) 77*/ 78#defineCommonHeaderGCObject*next;lu_bytett;lu_bytemarked
这个宏对应的结构体形式如下(lobject.h):
81/* 82**Commonheaderinstructform 83*/ 84typedefstructGCheader{ 85CommonHeader; 86}GCheader;
结构体GCheader在通用的可回收对象unionGCObject的定义中有用到。
III、lu_byteextra对于短字符串,用来记录这个字符串是否为保留字,对于长字符串,可以用于惰性求Hash值;unsignedinthash成员是字符串对应的Hash值(在后面会具体讲Lua是怎么计算字符串的Hash值的);size_tlen用来表示字符串的长度。
IV、上面的结构体只是描述了一个字符串的结构,真正的字符串数据保存是紧随在结构体后面保存。
在Lua5.2.1之前,不区分字符串长和短的字符串,所有的字符串保存在一个全局的Hash表中,对于Lua虚拟机来说,相同的字符串只有一份数据,从Lua5.2.1开始,只是把短的字符串字符串(当前定义是长度小于等于40)放在全局Hash表中,而长字符串都是独立生成,同时在计算Hash值时,引入一个随机种子,这样做的目的防止HashDos——攻击者构造出非常多相同Hash值的不同字符串,从而降低Lua从外部压入字符串进入全局的字符串Hash表的效率。下面是Lua5.2.1中,生成一个新字符串的步骤,其相应的代码都在lstring.c中:
(1)若字符串长度大于LUAI_MAXSHORTLEN(默认值是40),则是长字符串,直接调用创建字符串接口的函数createstrobj(当然字符串的长度需要能保存在成员size_tlen中,否则直接返回),代码如下(lstring.c):
95/* 96**createsanewstringobject 97*/ 98staticTString*createstrobj(lua_State*L,constchar*str,size_tl, 99inttag,unsignedinth,GCObject**list){ 100TString*ts; 101size_ttotalsize;/*totalsizeofTStringobject*/ 102totalsize=sizeof(TString)+((l+1)*sizeof(char)); 103ts=&luaC_newobj(L,tag,totalsize,list,0)->ts; 104ts->tsv.len=l; 105ts->tsv.hash=h; 106ts->tsv.extra=0; 107memcpy(ts+1,str,l*sizeof(char)); 108((char*)(ts+1))[l]='\0';/*ending0*/ 109returnts; 110}
可以看到把传入的字符串具体内存放在紧随结构体TString内存后面,并且注意108行,字符串以”\0”结束与C语言字符串兼容的。
(2)若字符串是短字符串,首先计算字符串的Hash值,找到对应的链表(短字符串的全局Hash表,使用的是链接法的方法,即把所有冲突的元素放在同一个链表中),查找当前要创建的字符串是否已经在Hash表中,若已经存在,则直接返回这个字符串。否则会调用函数newshrstr,而函数newshrstr会调用上面的createstrobj函数创建新字符串,并把新创建的字符串放到Hash表中,代码如下(lstring.c)):
130/* 131**checkswhethershortstringexistsandreusesitorcreatesanewone 132*/ 133staticTString*internshrstr(lua_State*L,constchar*str,size_tl){ 134GCObject*o; 135global_State*g=G(L); 136unsignedinth=luaS_hash(str,l,g->seed); 137for(o=g->strt.hash[lmod(h,g->strt.size)]; 138o!=NULL; 139o=gch(o)->next){ 140TString*ts=rawgco2ts(o); 141if(h==ts->tsv.hash&& 142ts->tsv.len==l&& 143(memcmp(str,getstr(ts),l*sizeof(char))==0)){ 144if(isdead(G(L),o))/*stringisdead(butwasnotcollectedyet)?*/ 145changewhite(o);/*resurrectit*/ 146returnts; 147} 148} 149returnnewshrstr(L,str,l,h);/*notfound;createanewstring*/ 150}
全局的字符串Hash表是保存在虚拟机全局状态成员strt中的(lstate.h):
119stringtablestrt;/*hashtableforstrings*/
而类型stringtable是一个结构体,其定义如下(lstate.h):
59typedefstructstringtable{ 60GCObject**hash; 61lu_int32nuse;/*numberofelements*/ 62intsize; 63}stringtable;
其中成员GCObject**hash是一个指针数组,数组中每个成员实质指向TString(注意TString中包括宏CommonHeader,该宏中的next成员可以构造出Hash表中开散的链表);nuse是数组hash中已经被使用的元素个数;size是当前数组hash的大小。
在函数newshrstr插入新的字符串前,都会判断nuse值是否大于size,若大于,表明Hash表大小不够需要扩充,则把Hash表的大小扩充到原来的2倍,对应的代码如下(lstring.c):
121if(tb->nuse>=cast(lu_int32,tb->size)&&tb->size<=MAX_INT/2) 122luaS_resize(L,tb->size*2);/*toocrowded*/
在gc的时候,会判断nuse是否比size/2还小(在Lua5.1中是把nuse与size/4比较),如果是的话就重新resize这个stringtable的大小为原来的一半。对应的代码如下(lgc.c):
783inths=g->strt.size/2;/*halfthesizeofthestringtable*/ 784if(g->strt.nuse<cast(lu_int32,hs))/*usinglessthanthathalf?*/ 785luaS_resize(L,hs);/*halveitssize*/
对于字符串比较,首先比较类型,若是不同类型字符串,则肯定不相同,然后区分短字符串和长字符串,对于短字符串,若两者指针值相等,则相同,否则不相同;对应长字符串,则首先比较指针值,若不同,则比较长度值和内容逐字符比较。
总结
(1)Lua中的保留字和元方法名都是做为短字符串的,他们在虚拟机启动的时候就已经放入到全局短的字符串Hash表,并且是不回收的。
(2)查找字符是比较高效的,但是修改或插入字符串都是比较低效的,这里面除了计算外,至少要把外面的字符串拷贝到虚拟机中。
(3)对应长字符串的Hash值,Lua是不会考察每个字符的,因而能避免快速计算长字符串的散列值,其相应的代码如下(lstring.c):
51unsignedintluaS_hash(constchar*str,size_tl,unsignedintseed){ 52unsignedinth=seed^l; 53size_tl1; 54size_tstep=(l>>LUAI_HASHLIMIT)+1; 55for(l1=l;l1>=step;l1-=step) 56h=h^((h<<5)+(h>>2)+cast_byte(str[l1-1])); 57returnh; 58} 21/* 22**Luawilluseatmost~(2^LUAI_HASHLIMIT)bytesfromastringto 23**computeitshash 24*/ 25#if!defined(LUAI_HASHLIMIT) 26#defineLUAI_HASHLIMIT5 27#endif
(4)当有多个字符串连接时,不应该直接用字符串连接运算符”..”,而是用table.concat操作或者是string.format来加快字符串连接的操作。
(5)Lua中字符串Hash算法用的是JSHash,关于字符串的各种Hash函数,网络有篇文章对它进行了总结:https://www.byvoid.com/blog/string-hash-compare
以上所述谁就是本文的全部内容了,希望能对大家学习lua有所帮助。