串内存消耗。
我们服务器的表资源,转表后都是按第二种形态存在,所以一定要切记key的字符串长度不要超过40,否则产生无谓的内存浪费和大量的GC对象,影响GC效率。
在开发过程中,table是最常见的数据结构,每条记录对外都是key-value的方式来读写。他的底层是用array + hashtable的方式管理数据的,但对外是透明的。不论array还是hashtable都是连续的内存分布。在查找时:
1. 如果key是整型, 并且 key > 1 and key < max_array_size, 直接取array[key]数据
2. 其他情况,默认读取hashtable。Hashtable的管理方有些特别,当不同key hash到同一个node时,用链表来维护这些冲突节点。与stringtable 链表节点动态分配的方法不同, HashTable使用空闲链表来维护冲突节点。
首先说一种典型的情况,调用table.insert 或者table[#table + 1] 按序插入列表的,就是存放在array里面。
在插入新节点时,如果通过freelist找不到可用节点就触发rehash。在新创建table时,node节点数量为0,当插入第1条数据时触发内存分配2^0=1个内存节点。当插入第2条记录时,因为节点都已经使用,所以又触发rehash,分配2^1=2个内存节点。依次类推,在插入第3、5、9时,触发分配一个更大的内存,可以简单理解成重新分配一块oldsize * 2 的内存,把原有的hashTable的数据重新hash插入到新的内存中,再释放掉原有的内存。综上,每次内存的增长都是按2的指数倍来增长。
1、Rehash导致的cpu消耗
使用2的指数倍扩容,针对单个表扩容其实并不频繁,比如100W个节点,最多扩容20次,2^20 > 100W。只是在表的前期会相对频繁,1、2、3、5、9条记录插入会触发扩容,所以要避免小表的频繁创建插入。
分析:可以看到预填充方式可以避免频繁的表扩容,cpu消耗是动态扩容的1/3。使用预填充的方式,在创建tab时,会直接分配一个8个元素的Node节点的内存,存放数据。而采用动态扩容的方式,第一次分配1个元素,然后随着数据的插入,会扩容到2个元素的内存,把原来数据重新hash到新分配的内存,释放老内存。同理,随着数据的插入,继而扩容到4个元素、扩容到8个元素...
2、rehash导致内存消耗演示
因为hashtable数据分配是0、1、2、4、8、16、32这些内存大小,所以在插入数据时分别在1、2、3、5、9、17、33时内存不够触发扩容,如上红色标记的点。可以看到在红色标记的点上,内存会有大幅扩大,而且基本是上一次大幅扩容的2倍关系。
问题一:在上述截图中,为什么在10、18、34这些地方出现了额外的内存消耗?
以10节点来说明,这是因为在插入第9条数据后,print打印,系统创建了一个”0.2841796875”字符串,导致节点10在统计消耗的时候计算进去了,具体消耗长度为 25 + 实际长度= 25 + 12 = 37字节,与节点10的消耗吻合。同理节点18的消耗为25 + len(“0.5”) = 28
问题二:因为节点10、18、34本身也print打印了字符串,怎么它后面的11、19、35就没有消耗内存?
以11为例,理论上节点10打印的”0.0361328125”会消耗内存,但这个字符串在节点6已经创建过了,由于所有短字符串都在stringtable进行管理,只有一份拷贝,所以不再消耗内存。
问题三:为什第一个节点内存消耗明显偏高?
这是因为for循环里面local cur = collectgarbage("count")调用,触发了Lua_state->stack指向的内存空间的动态扩容,原理有点类似HashTable内存不够的再分配机制。
综上三个问题,可以把代码调整一下再看:
可以看到,在1、2、3、5、9、17等位置触发内存再分配,对应重新分配的内存是2^0=1、2^1=2、2^2=4、8、16、32大小。NewSize-OldSize差值即新增内存,分别为1-0=1、2-1=1、4-2=2、8-4=4、16-8=8、32-16=16,而单个节点大小为0.03125K,整体每次新增内存与上面截图完全吻合。
创建一个最简单的表{}, lua在调用luaH_new初始化时并不会动态分配array和hashtable指向的内存,只是创建一个最简单的table管理结构,所以消耗的内存为sizeof(Table) = 56。
1、估算table中hashtable的内存消耗
每个Node节点消耗sizeof(Node) = 32。所以对于简单数据(整型、浮点、bool)相对比较好估算,sizeof(Table) + sizeof(Node) * NodeNum。 例如上面的代码,100条记录实际分配的Node节点2^7=128,就是56 + 32 * 128 = 4152
2、估算table中有序数组的内存消耗
对于简单表tab = {}, 一般都是使用tab[#tab + 1] = xxxx 或者 table.insert(tab, xxx) 来插入数据,对于这种典型的场景,table使用的是array的方式存储数据。计算方式,sizeof(Table) + sizeof(TValue) * ArrayNum,其中sizeof(TValue) = 16。同样下面的代码,略作调整,100条记录实际的分配的Array节点也是128, 就是56 + 16 * 128 = 2104.
3、估算table嵌套类型的消耗
上面都是用的简单数据类型进行估算,现在考虑下当value是GCObject对象的情况(字符串、表、闭包)。针对一个Node节点,数据组成:
struct Node {
TValue i_val;
TKey i_key;
} Node;
因此,对于简单的