手机版
你好,游客 登录 注册
背景:
阅读新闻

Lua数据结构和内存占用分析

[日期:2018-10-23] 来源:cnblogs.com/liao0001  作者:liao0001 [字体: ]

  由于lua是一个跨平台的脚本语言,会根据平台位数(16bit\32bit)、平台类型(Linux\Windows)、语言标准(C89\C99)、以及编译参数等开启预编译选项,导致基本数据结构的字长和类型会动态变化,以linux_ x86_64 进行编译为基础进行分析介绍,lua版本5.3.4。并根据我们开发过程中一些常见的情景进行分析:

1、基础数据结构

  Lua的基本数据表示方式是type + union的方式,根据不同类型映射到union的不同结构上面统一的表示结构lua_TValue

   typedef union Value {
     GCObject *gc;    /* collectable objects */
     void *p;        /* light userdata */
     int b;          /* booleans */
     lua_CFunction f; /* light C functions */
     lua_Integer i;  /* integer numbers */
     lua_Number n;    /* float numbers */
   } Value;
   
   struct lua_TValue {
     Value value_;
      int tt_;
   } TValue;

  但由于lua_Integerlua_Number在当前平台预处理后,分别定义成long long 和 double类型,所以为方便理解,上述结构经过转义:

   typedef union Value {
     GCObject *gc;    /* collectable objects */
     void *p;        /* light userdata */
     int b;          /* booleans */
     lua_CFunction f; /* light C functions */
     long long i;    /* integer numbers */
     double n;      /* float numbers */
   } Value;
   
   struct lua_TValue {
     Value value_;
      int tt_;
   } TValue;

  在lua5.1版本中,统一使用lua_Number来表示整数和浮点数,而double能够表示的整数大小有限,大概2^52的长度,所以用lua_Number表示一些类型为int64_t的全局唯一id长度不够,类似物品id、角色id。在lua5.3中,上述问题不再存在。

  lua简单数据类型bool、整型、浮点型都是统一用lua_TValue来表示,消耗内存为sizeof(lua_TValue) = 16字节。因此相对C\C++表示整型的char\short\int\int64_t来说,这种数据结构的表示法虽然比较统一,但比较消耗内存。还有一些复杂的数据结构,统一封装在GCObject中。由于5.15.3表示法略有差异,5.1方便理解,如下:

   union GCObject {
     GCheader gch;
     union TString ts;
     union Udata u;
     union Closure cl;
     struct Table h;
     struct Proto p;
     struct UpVal uv;
     struct lua_State th;  /* thread */
   };

2、数据结构的内存占用

  在开发过程中,最常用的数据结构是stingtable类型,那么现在主要分析这两种数据结构的内存占用。

2.1 string 类型

  String又细分为短字符串LUA_TSHRSTR和长字符串LUA_TLNGSTR两种,默认长度小于40的为LUA_TSHRSTR,使用全局stringtable进行管理。即所有短字符串都在stringtable中存放,相同字符串只会有一份实际数据拷贝,每份相同的TString对象只是存放一个hash值,用来索引stringtable。而长字符串则跟普通的GCObject没有差别,相同字符串在内存都是单独一份数据拷贝。在Lua5.1中,没有区分长短字符串,所有的字符串统一在stringtable中存在唯一拷贝。猜想这种改变一是因为长字符串出现相同的情况比较少,二是lua5.1的方式长字符串TString计算Hash是抽取部分字符进行运算,这样的计算方式可能被伪造导致不同字符串的hash值一样,但要是所有字符全用来计算hash又比较耗时。

  下面是一个string类型的GCObject的内存表示,根据长短字符串表示方式不一样:

 

 

2.1.1 内存占用分析实践

下面分别对比四种情景来分析内存占用的不同。因为lua在使用 .. 连接字符串时,底层会调用luaV_concat -> luaS_newStr新建字符串,这里对比下在创建短字符串和长字符串后的内存消耗:

 

Lua5.3.4

情景1

相同短字符串

collectgarbage("stop");      --close auto gc

collectgarbage("collect")     --full gc

local before = collectgarbage("count");

for i = 1, 10000 do

    local string = "100000000000000000000000" .. "0"

end

 

local after = collectgarbage("count");

print("short same mem cost:" .. (after - before) .. "K" )

short same mem cost:0.580078125K

情景2

相同长字符串

 

collectgarbage("stop");     --close auto gc

collectgarbage("collect")    --full gc

before = collectgarbage("count");

for i = 1, 10000 do

    local string = "10000000000000000000000000000000000000000000000000000" .. "0"

end

 

after = collectgarbage("count");

print("long same mem cost:" .. (after - before) .. "K" )

 

 

long same mem cost:771.48K


通过对比:在创建相同字符串时,因为短字符串在StringTable只有一份拷贝,而长字符串每次都会产生新的数据拷贝,所以消耗内存差异明显。 0.58K  VS  771.48K 

Lua5.3.4

情景3

不同短字符串

 

collectgarbage("stop");      --close auto gc

collectgarbage("collect")    --full gc

local before = collectgarbage("count");

for i = 1, 10000 do

    local string = "100000000000000000000000" .. i

end

 

local after = collectgarbage("count");

print("short diff mem cost:" .. (after - before) .. "K" )

 

 

short diff mem cost:1052.62109375K

情景4

不同长字符串

 

collectgarbage("stop");      --close auto gc

collectgarbage("collect")    --full gc

for i = 1, 10000 do

    local string = "10000000000000000000000000000000000000000000000000000" .. i

end

 

after = collectgarbage("count");

print("long diff mem cost:" .. (after - before) .. "K" )

 

 

long diff mem cost:1145.82421875K


通过对比:在创建不同字符串时,不论长短字符串,都会有一份不同字符串的拷贝,所以都需要消耗大量内存。1052K  VS  1145K

问题一在对比情景2和情景4时,长字符串都是一份拷贝,为什么内存消耗差异较大?(791K vs 1145K)

答:这是因为使用连字符 .. 时,情景4里面的变量i转为字符串,相当于生成了10000份不同的短字符串拷贝,导致多消耗了300K左右内存,所以在开发中可以适当避免 .. 产生大量字符串的产生。可以考虑使用string.format来格式化字符串。具体效果如下:

Lua5.3.4

 

collectgarbage("stop");      --close auto gc

collectgarbage("collect")    --full gc

for i = 1, 10000 do

    local string = string.format("100000000000000000000000000000000000000000%d", i)

end

 

local after = collectgarbage("count");

print("mem cost:" .. (after - before) .. "K" )

 

 

mem cost:799.7K (结果比较接近情景2)

 

2.1.2 预估字符串消耗

问题二:以情景2为例,最终内存消耗771.48K,这个可以在开发前估算吗?

答:string实际是GCObject对象,所以有些公共的字段。以”Lua”这个字符串为例,TString的内存结构:

在情景2中,实际字符串长度为54。那么内存占用 = sizeof(TString) + 1 + 实际长度 = 25 + 实际长度 = 25 + 54 = 79。理论内存:10000 * 79/ 1024 = 771.48K, 理论跟实际消耗值几乎一致。

 

2.1.3 与lua5.1.4的对比

  但由于我们之前也用过lua5.1.4,这个版本所有字符串均引用StringTable一份数据拷贝,理论上不论长短字符串,只要相同的数据只会有一份拷贝。(由于lua5.1.4版本在调用collectgarbage("collect")进行一次完整gc后,luaC_fullgc会调用setthreshold打开自动gc,这里容易踩坑,上述代码运行发现内存消耗明显低于lua5.3版本,非常困惑。所以修改代码在collectgarbage("collect")后,重新调用collectgarbage("stop")关闭自动gc)。修改后在lua5.1.4下面执行对比如下:

 

Lua5.3.4内存消耗

Lua5.1.4内存消耗

情景1

相同短字符串

0.580078125K

0.048828125K

情景2

相同长字符串

 

771.48K

0.0966796875K

情景3

不同短字符串

 

1052.62109375K

1052.62109375K

情景4

不同长字符串

 

1145.82421875K

1305.828125K


最大差别在于相同长字符串创建的内存消耗,Lua5.1.4由于统一用stringtable保存一份拷贝,所以内存消耗可以忽略不记,但Lua5.3.4由于会产生不同副本拷贝,消耗明显。

 

2.1.4 table重复字符串key对内存影响?

对于短字符串,只会在stringtable中存在一份拷贝,对内存没有什么影响。对于长字符串,需要分两种场合看:

for i =1, 1000 do

Tab[i] = {ccccccccccccccccccccccccccccccccccccccc=i}

end

或者

Tab[1] = {ccccccccccccccccccccccccccccccccccccccc=1}

Tab[2] = {ccccccccccccccccccccccccccccccccccccccc=2}

Tab[3] = {ccccccccccccccccccccccccccccccccccccccc=3}

...

Tab[100] = {ccccccccccccccccccccccccccccccccccccccc=100}

对于这两种情况,由于lua程序进行代码文件词法分析时,第一种调用一次luaS_newlstr创建”ccccccccccccccccccccccccccccccccccccccc”, 而第二种会调用100次。正如我们前面的分析,长字符串每次调用都会生成一份新的拷贝,所以第二种情况会有N份的字符串内存消耗。

我们服务器的表资源,转表后都是按第二种形态存在,所以一定要切记key的字符串长度不要超过40,否则产生无谓的内存浪费和大量的GC对象,影响GC效率。

 

2.2 table类型

在开发过程中,table是最常见的数据结构,每条记录对外都是key-value的方式来读写。他的底层是用array + hashtable的方式管理数据的,但对外是透明的。不论array还是hashtable都是连续的内存分布。在查找时:

1. 如果key是整型并且 key > 1 and key < max_array_size, 直接取array[key]数据

2. 其他情况,默认读取hashtableHashtable的管理方有些特别,当不同key hash到同一个node时,用链表来维护这些冲突节点。与stringtable 链表节点动态分配的方法不同, HashTable使用空闲链表来维护冲突节点。

 

2.2.1  Array or HashTable

首先说一种典型的情况,调用table.insert 或者table[#table + 1] 按序插入列表的,就是存放在array里面。

 

2.2.2 rehash动态扩容原理

  在插入新节点时,如果通过freelist找不到可用节点就触发rehash。在新创建table时,node节点数量为0,当插入第1条数据时触发内存分配2^0=1个内存节点。当插入第2条记录时,因为节点都已经使用,所以又触发rehash,分配2^1=2个内存节点。依次类推,在插入第359时,触发分配一个更大的内存,可以简单理解成重新分配一块oldsize * 2 的内存,把原有的hashTable的数据重新hash插入到新的内存中,再释放掉原有的内存。综上,每次内存的增长都是按2的指数倍来增长。

1Rehash导致的cpu消耗

使用2的指数倍扩容,针对单个表扩容其实并不频繁,比如100W个节点,最多扩容20次,2^20 > 100W。只是在表的前期会相对频繁,12359条记录插入会触发扩容,所以要避免小表的频繁创建插入。

预先填充方式

a = os.clock()

for i = 1, 1000000 do

    local tab = {["1"] = 1, ["2"] = 2, ["3"] = 3, ["4"] = 4, ["5"] = 5}

end

b = os.clock()

print(“timediff:”, b - a)

 

timediff: 0.53

动态扩容方式

a = os.clock()

for i = 1, 1000000 do

    local tab = {}

    tab["1"] = 1

    tab["2"] = 2

    tab["3"] = 3

    tab["4"] = 4

    tab["5"] = 5

end

b = os.clock()

print(“timediff:”, b - a)

 

timediff: 1.68

分析:可以看到预填充方式可以避免频繁的表扩容,cpu消耗是动态扩容的1/3。使用预填充的方式,在创建tab时,会直接分配一个8个元素的Node节点的内存,存放数据。而采用动态扩容的方式,第一次分配1个元素,然后随着数据的插入,会扩容到2个元素的内存,把原来数据重新hash到新分配的内存,释放老内存。同理,随着数据的插入,继而扩容到4个元素、扩容到8个元素...

 

2rehash导致内存消耗演示

tab = {}

text = "diff mem"

collectgarbage("stop")

before = collectgarbage("count");

for i = 1, 100 do

    tab[10000 + i] = i

 

    local cur = collectgarbage("count")

    print(text, cur - before)

    before = cur ;

end

 

 

因为hashtable数据分配是012481632这些内存大小,所以在插入数据时分别在123591733时内存不够触发扩容,如上红色标记的点。可以看到在红色标记的点上,内存会有大幅扩大,而且基本是上一次大幅扩容的2倍关系。

 

问题一:在上述截图中,为什么在101834这些地方出现了额外的内存消耗?

10节点来说明,这是因为在插入第9条数据后,print打印,系统创建了一个”0.2841796875”字符串,导致节点10在统计消耗的时候计算进去了,具体消耗长度为 25 + 实际长度= 25 + 12 = 37字节,与节点10的消耗吻合。同理节点18的消耗为25 + len(“0.5”) = 28

 

问题二:因为节点101834本身也print打印了字符串,怎么它后面的111935就没有消耗内存?

11为例,理论上节点10打印的”0.0361328125”会消耗内存,但这个字符串在节点6已经创建过了,由于所有短字符串都在stringtable进行管理,只有一份拷贝,所以不再消耗内存。

 

问题三:为什第一个节点内存消耗明显偏高?

这是因为for循环里面local cur = collectgarbage("count")调用,触发了Lua_state->stack指向的内存空间的动态扩容,原理有点类似HashTable内存不够的再分配机制。

综上三个问题,可以把代码调整一下再看:

tab = {}

text = "diff mem"

collectgarbage("stop")

before = collectgarbage("count");

for i = 1, 100 do

    if i == 1 then before = collectgarbage("count"); end

    tab[10000 + i] = i

 

    local cur = collectgarbage("count")

    print(text, cur - before)

    before = collectgarbage("count");

end

 

可以看到,在1235917等位置触发内存再分配,对应重新分配的内存是2^0=12^1=22^2=481632大小。NewSize-OldSize差值即新增内存,分别为1-0=12-1=14-2=28-4=416-8=832-16=16,而单个节点大小为0.03125K,整体每次新增内存与上面截图完全吻合。

 

2.2.3 估算table的内存消耗

创建一个最简单的表{}, lua在调用luaH_new初始化时并不会动态分配arrayhashtable指向的内存,只是创建一个最简单的table管理结构,所以消耗的内存为sizeof(Table) = 56

1、估算tablehashtable的内存消耗

每个Node节点消耗sizeof(Node) = 32。所以对于简单数据(整型、浮点、bool)相对比较好估算,sizeof(Table) + sizeof(Node) * NodeNum。 例如上面的代码,100条记录实际分配的Node节点2^7=128,就是56 + 32 * 128 = 4152

collectgarbage("stop");

before = collectgarbage("count");

tab = {}

for i = 1, 128 do

    tab[10000+i] = i

end

after = collectgarbage("count");

print("total mem:", (after - before)*1024)

 

total mem:      4152.0

 

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.

collectgarbage("stop");

before = collectgarbage("count");

tab = {}

for i = 1, 128 do

    tab[#tab + 1] = i

end

after = collectgarbage("count");

print("total mem:", (after - before)*1024)

 

total mem:      2104.0

 

3、估算table嵌套类型的消耗

上面都是用的简单数据类型进行估算,现在考虑下当valueGCObject对象的情况(字符串、表、闭包)。针对一个Node节点,数据组成:

struct Node {

TValue i_val;

  TKey i_key;

} Node;

因此,对于简单的数据类型,TValue里面的结构字段足以存储,但对于复杂类型,TValue里面只是存了一个对象指针GCObject*,而对象本身的内存大小还得单独核算。先看一个简单:

collectgarbage("stop");

before = collectgarbage("count");

tab = {}

tab[10000] = {i}

after = collectgarbage("count");

print("total mem:", (after - before)*1024)

total mem:      160.0

A、tab表 sizeof(Table) + sizeof(Node) * 1 = 88

B、{i}使用array来存储,实际消耗 sizeof(Table) + sizeof(TValue) * 1 = 72

C、所以整体消耗: 88 + 72 = 160

 

4、估算复杂table的数据内存消耗以及与C语言的对比

以一个简单的排行榜列表来进行多维度计算,预计10000条数据,以玩家uid作为key,每条记录存积分和名次。分多个场景进行评估。

场景一:

collectgarbage("stop");

before = collectgarbage("count");

tab = {}

for i = 1, 10000 do

    tab[100000+i] = {score = 100000+i, rank = i}

end

after = collectgarbage("count");

print("total mem:", (after - before)*1024)

total mem:      1724344.0

 

A,首先涉及两个字符串”score” “rank” 的消耗。分别是25 + 5 = 30, 25 + 4 = 29 

B,每个小表{score = 100000+i, rank = i}, sizeof(Table) + sizeof(Node) * 2 = 120

C,大表有1W条记录,2^14 = 16384 > 10000sizeof(Table) + sizeof(Node) * 16384 = 524344

D,最终内存占用:30 + 29 + 120 * 10000 + 524344 = 1724403

理论计算出来的内存占用比实际消耗多了1724403-1724344 = 59字节,似乎两个字符串的消耗没有计算进来。那么这两个字符串”score” ”rank” 是否真正存在于stringTable答案是yes。只是在更早阶段,lua程序对代码文件进行词法分析,生成指令码的过程中,就已经调用luaS_newlstr创建了”score”和”rank”字符串了,因此不在上述代码的统计范围内,有兴趣的可以调试lua程序验证。

 

场景二:

去掉每条子表记录里面的key,直接按有序列表存储。

collectgarbage("stop");

before = collectgarbage("count");

tab = {}

for i = 1, 10000 do

    tab[100000+i] = {100000+i, i}

end

after = collectgarbage("count");

print("total mem:", (after - before)*1024)

total mem:      1404344.0

 

A,每个小表{100000+i, i}, sizeof(Table) + sizeof(TValue) * 2 = 88

B,大表有1W条记录,2^14 = 16384 > 10000sizeof(Table) + sizeof(Node) * 16384 = 524344

C,最终内存占用:88* 10000 + 524344 = 1404344

 

场景三:

如果列表只有2个变量,可以把两个数值合并,减少一层表的分配,那么就会减少场景二A子表的内存消耗。

collectgarbage("stop");

before = collectgarbage("count");

tab = {}

for i = 1, 10000 do

    tab[100000+i] = (100000 + i) << 14 + i

end

after = collectgarbage("count");

print("total mem:", (after - before)*1024)

total mem:      524344.0

由于value只是普通的数值,那么Node节点的TValue足够存储,不在单独分配额外内存,所以内存大小:sizeof(Table) + sizeof(Node) * 16384 = 524344

 

场景四:

如果还要继续压缩内存使用,可以考虑不要存1W条记录,存8192条记录如果也满足要求的话,这样可以减少一次hashtable的预分配。

collectgarbage("stop");

before = collectgarbage("count");

tab = {}

for i = 1, 8192 do

    tab[100000+i] = (100000 + i) << 14 + i

end

after = collectgarbage("count");

print("total mem:", (after - before)*1024)

total mem:      262200.0

A、大表的hashtable记录数2^13 = 8192, 那么刚好把节点使用完,没有浪费。

B、总体内存:sizeof(Table) + sizeof(Node) * 8192= 262200

所以,如果对lua table的动态内存管理比较清楚,可以在满足需求的情况进行一些优化,能够大幅压缩内存的占用,如上可以看到内存从最早的1724344 优化到262200 大概只有原来内存占用的1/7。当然了,也不能只考虑内存的占用,也要结合扩展性综合考虑,比如场景四里面由于少了一层表,会导致单条记录没法扩展字段。因此,不论是节省内存还是兼顾扩展性,是综合评估的结果,只有各方面利弊能够准确评估,才能做很好的tradeofff

 

场景五:

对比C/C++的实现

struct rankitem

{

     Uint64_t uid;

     Int score;

     Short rank_no;

};

 

struct ranklist

{

short num;

struct rankitem list[8192];

};

 

 

  在C/C++里面内存比较方便计算:sizeof(struct ranklist) = 114690。可以看到,即使luatable做了较好的优化,内存优化到早期的1/7, 实际的消耗还是C/C++2倍。如果记录再增加1条,这个倍数立刻扩大到C/C++内存占用的4倍。所以可以大概认为lua table的一般是C/C++2 ~ 28(4 * 7) 的范围,当然随着记录条数、table层次不同,这个范围浮动较大,简单可以取个中值算平均数。

正如我们前面分析,luatable占用内存明显高于C/C++,主要有以下几个因为:

1、lua table支持动态插入,所以为了性能必须要预分配更大内存,减少因为每次的插入而导致重新分配。这样极端情况就会多耗掉一倍的内存。

2、lua table的节点使用的是Node,为了追求通用性,对应kv字段基本都是TValue类型, 而这个类型占用16字节,kv消耗加起来就是32,明显高于C/C++里面简单字段类型的消耗。 当然lua table引入array可以不需要key字段,内存接近省一半。

3、Lua table本身的管理数据有固定56字节,如果是一个很大的表,这个占用比率并不明显。但如果是很多个小表,例如情景1里面的,占用比例就会很大。

4、在实际开发过程中,一般都会表嵌套表,很多层,由于每层都有内存冗余和浪费,这样嵌套下来消耗就会叠加的更明显。

 

2.2.4 rehash数据重新分布

  上面只是描述节点不够用时触发内存扩容,数据重新进行hash分布。但如果既有Array数据,又有HashTable数据时,会怎么进行rehash呢?

  系统会把所有的key为整数的节点进行统计(包含在arrayHashTable),同时数组最大内存Max_Aarry_Size2的指数倍增长,然后计算满足条件Key <=Max_Aarry_Size的整数节点数量,当数量 > Max_Aarry_Size/2 就认为array内存能充分利用,使用率超过50%,直到系统找到一个最大的符合条件的Max_Aarry_Size为止。剩下的节点数量进入HashTable, HashTable也是按2的指数倍增长,直到能够装下剩余节点数为止。

  因此,通过这个也验证上面的例子中,for i=1, 10000 do tab[10000+i] = 10000+i end为什么使用的HashTable存储的原因了。当Max_Aarry_Size = 2^13=8196时,没有Key落在这个[1, 8196]区间。当Max_Aarry_Size= 2^14=16392时,只有6392条数据落入区间[1, 16392], 区间利用率小于50%。当Max_Aarry_Size= 2^15=32784时,只有10000落入区间[1, 32784], 也不满足利用率的要求。

 

Linux公社的RSS地址https://www.linuxidc.com/rssFeed.aspx

 

本文永久更新链接地址https://www.linuxidc.com/Linux/2018-10/154971.htm

 

linux
相关资讯       Lua数据结构  Lua内存占用 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款