lua 去除小数点有效数字后面的0_Lua设计与实现--字符串篇
![78c8240d03048a31c2f58b0bba17ce23.png](https://img-blog.csdnimg.cn/img_convert/78c8240d03048a31c2f58b0bba17ce23.png)
本篇文章是Lua设计与实现专栏的第二篇,主要结合了《Lua设计与实现》书中的第三章(字符串),以及lua5.3源码进行一些总结,由于原书中主要是基于lua5.1进行书写的,所以可能会有跟书中列举代码不一致的地方,不过大体上是保持一致的。
长串和短串
在讲String的数据结构和重要函数前,先强调一点,出于对性能和内存等方面的考虑,lua对String实现的方方面面,都把短字符串和长字符串区分开来处理了。比如短串会走一个先查询再创建的路子,而长串不查询,直接创建。我个人的理解大概是出于以下两个方面考虑:
- 复用度。短串复用度会比长串要高,或者说短串在全局的引用计数一般会比长串高。比如obj["id"] = 12, obj["type"] = 0,类似"id"、"type"这种短串可能会在程序很多处地方使用到,如果开辟多份就有点浪费了。而长串则很少会有重复的,比如我一篇文章的文本,一般不会在两个地方重复打出来。
- 哈希效率。由于长串的字符串比较多,如果要把组成它的字符序列进行哈希,耗时会比短串长。
以下是lua对于短串长度最大值的定义:
![920a680e9b0a877eec5b9d570ac46194.png](https://img-blog.csdnimg.cn/img_convert/920a680e9b0a877eec5b9d570ac46194.png)
从定义可以看出,长度大于40的,在lua中处理为长串,反之则为短串。
String的基本数据结构
TString Struct
lua中string的实现为TString结构体:
![e680681a978cfc2ffb897b7b92bd03e8.png](https://img-blog.csdnimg.cn/img_convert/e680681a978cfc2ffb897b7b92bd03e8.png)
从代码中可以看出,它主要包含了以下字段:
- CommonHeader。GC对象通用的CommonHeader,如果不熟悉可以参考专栏的数据类型篇。
- extra。对于短串,主要用于实现保留字符串;对于长串,作为一个标识,来表示该串有没有进行过hash,这点可以结合hash字段来理解。
- shrlen。短串的长度,对于长串没有意义。
- hash。该字符串的hash值,如果是短串,该hash值是在创建时就计算出来的,这是因为短串会加入到全局的stringtable这个hashmap结构中;而对于长串来说,这个hash字段是按需的,只有真正需要它的hash值时,手动调用luaS_hashlongstr函数,才会生成该值,lua内部现在只有在把长串作为table的key时,才会去计算它。当extra字段为0时,表示该长串的hash还没计算过,否则表示已经计算过了。
- union{lnglen, hnext}。当是短串时,由于会被加入到全局stringtable的链表中,所以在该结构中保存了指向下一个TString的指针;当是长串时,表示该长串的长度。注意长串和短串没有共用一个字段来表示它们的长度,主要是长串的长度可以很长,而短串最长就为40,一个byte就够用了,这边也体现了lua实现是很抠细节的,反倒是把这两个不相关的字段打包到一个union里来节约内存了。
UTString Union
为了实现TString结构的内存对齐,lua又在其上wrap了一层UTString结构:
![ac092f7842e55bee1c55f2941b13f2c6.png](https://img-blog.csdnimg.cn/img_convert/ac092f7842e55bee1c55f2941b13f2c6.png)
看lua的注释,指的是保证该结构后面的内存是满对齐的,由于lua在创建字符串时,会把实际的char数组紧挨着该UTString结构来存储,所以我这边的理解是lua是为了加速对该结构后面char数组的访问。关于C的内存对齐,我不是很熟悉,参考了一篇网上的帖子,如有不正确的地方欢迎指出~
stringtable
最后一个相关的结构,是lua对短串实现的一个全局的hashmap,叫做stringtable,结构如下:
![ac4d8c54aa3c039f397c565466d112e7.png](https://img-blog.csdnimg.cn/img_convert/ac4d8c54aa3c039f397c565466d112e7.png)
可以发现结构很简单,只有三个字段:
- hash。基于TString的hashmap,也叫做散列桶。基本结构是一个数组,每个数组里存的是相同hash值的TString的链表。
- nuse。当前实际的元素数。
- size。当前的桶大小。
stringtable主要会有一个resize操作,在下文的luaS_resize函数中会具体解释。
string实现中的重要函数
luaS_newlstr函数
创建给定长度的string接口,由于lua内部对短串和长串的处理采用了两套方案,所以该函数会根据string的实际长度来决定调用短串处理函数(internshrstr)还是长串处理函数(luaS_createlngstrobj)。
internshrstr函数
辅助函数,短string的getOrCreate函数。主要分为以下几个步骤:
- hash查找。会先调用luaS_hash来得到字符串的hash值,然后去全局stringtable里查找,如果有就直接返回该TString对象。hash的具体实现可以参照luaS_hash函数,为了对长度较长的字符串不逐位hash,内部也是根据长度的2次幂计算出了一个步长step,来加速hash的过程。
- hashtable按需resize。如果第一步查找失败了,并且stringtable的元素数量已经大于桶数,那么以两倍的尺寸对stringtable进行resize。具体调用的是luaS_resize函数。
- 实际的TString创建工作。主要是调用createstrobj函数来实现。其中包括了内存的分配,CommonHeader的填充,TString特化字段的填充等。
- 更新stringtable信息。比如更新stringtable的链表,以及对stringtable的元素数量加1。
![ab6b10a9f455218fb193ba425e3574c0.png](https://img-blog.csdnimg.cn/img_convert/ab6b10a9f455218fb193ba425e3574c0.png)
luaS_reisze函数
实际改变stringtable桶数量的函数。它目前只会被两个地方调用到:
- 短string创建时(internshrstr函数),如果发现桶数量小于了元素数量,说明散列比较拥挤了,会对桶进行两倍的扩容。
- 在gc时,如果发现桶数量大于了4倍的元素数量,说明散列太稀疏了,会对桶数量进行减半操作。
我们跟到该函数内部实现来看,可以发现它其实分为两种情况:
- newsize>oldsize。这个时候的顺序是,先进行扩容,然后进行rehash。扩容跟到里面去调用的就是realloc函数。而rehash的代码也很简洁,就是简单的遍历每个桶,把每个桶里的元素再哈希到正确的桶里去,代码如下:
![c4f1e1c9eec08ba5455a72e3badfd612.png](https://img-blog.csdnimg.cn/img_convert/c4f1e1c9eec08ba5455a72e3badfd612.png)
- newsize < oldsize。顺序是倒过来的,需要先根据newsize进行rehash,然后在保证所有元素已经收缩到newsize个数的桶里以后,才能进行shrink操作,这里也是调用的realloc函数来实现。
luaS_createlngstrobj函数
辅助函数,长串的create函数。因为长串在lua里是不走stringtable这一层的,也就是说它是每请求一个就是一个新的副本,内存是允许重复的。因此它的实现就是直接调用createstrobj函数来创建一个新的TString对象。
createstrobj函数
真正创建string对象的内部函数。它主要分为几个步骤:
- 计算该string需要占用的内存大小size。lua实际把string的char数组紧贴UTString结构来存储,所以一个string实例实际占用内存大小其实是UTString结构占用,再加上(charlength+1)个char大小:
![2fad235147ab6e825beeef36cb7ab427.png](https://img-blog.csdnimg.cn/img_convert/2fad235147ab6e825beeef36cb7ab427.png)
在取TString关联的char数组时,lua定义了getstr宏来完成:
![77d275c3292f87c732f22b52ad9a7631.png](https://img-blog.csdnimg.cn/img_convert/77d275c3292f87c732f22b52ad9a7631.png)
- 调用luaC_newobj来创建一个GC对象,该函数也是lua中相当重要的函数了。它负责了所有GCObject子类的创建,它会根据实际传入的内存大小来开辟空间,并帮忙填充掉CommonHeader的数据。最后,它还会把该obj挂接到global_State中的allgc列表中,以供GC模块使用。
![c6228fd1017581ce8a2b3786688614fa.png](https://img-blog.csdnimg.cn/img_convert/c6228fd1017581ce8a2b3786688614fa.png)
- 填充对象的TString特化字段。并且给char数组末尾添'0'。
以上三个步骤结合代码的情况如下:
![c6b96f5c3ed2ab65acb766cb827cd7d0.png](https://img-blog.csdnimg.cn/img_convert/c6b96f5c3ed2ab65acb766cb827cd7d0.png)
总结
在理完了string牵涉的主要数据结构和函数以后。从整个宏观的情况来理解lua的string:
- 首先,它是一个GCObject的子类,也就意味着它是被垃圾回收模块所管理的。
- 其次,它的长度决定了它的内部实现机制:短串意味着hashtable管理和内存去重;长串意味着内存副本。
- 最后,全局的hashtable大小,取决于string的创建和gc的sizecheck检查。