概述
lua字符串通过操作算法和内存管理,有以下优点:
- 节省内存。
- 字符串比较效率高。(比较哈希值)
问题:
- 相同的字符串共享同一份内存么?
- 相同的长字符串一定不共享同一份内存么?
- lua字符串如何管理内存?
数据结构
lua字符串TString
typedef struct TString {
CommonHeader;
lu_byte extra; /* reserved words for short strings; "has hash" for longs */
lu_byte shrlen; /* length for short strings */
unsigned int hash;
union {
size_t lnglen; /* length for long strings */
struct TString *hnext; /* linked list for hash table */
} u;
char contents[1];
} TString;
- lu_byte extra的reserved words语义是否是保留字。(保留字:local,if, ...)
- char contents[1] 是存放字符串内存数据的指针。
- 与char*相比,使用char[]在struct后面一次分配内存。
全局字符串表stringtable
typedef struct stringtable {
TString **hash;
int nuse; /* number of elements */
int size;
} stringtable;
- lua会把所有字符串统一在全局的stringtable结构中管理。
- hash 使用散列表存放string。
操作算法
luaS_new 创建字符串对外接口
/*
** Create or reuse a zero-terminated string, first checking in the
** cache (using the string address as a key). The cache can contain
** only zero-terminated strings, so it is safe to use 'strcmp' to
** check hits.
*/
TString *luaS_new (lua_State *L, const char *str) {
unsigned int i = point2uint(str) % STRCACHE_N; /* hash */
int j;
TString **p = G(L)->strcache[i];
for (j = 0; j < STRCACHE_M; j++) {
if (strcmp(str, getstr(p[j])) == 0) /* hit? */
return p[j]; /* that is it */
}
/* normal route */
for (j = STRCACHE_M - 1; j > 0; j--)
p[j] = p[j - 1]; /* move out last element */
/* new element is first in the list */
p[0] = luaS_newlstr(L, str, strlen(str));
return p[0];
}
- 先在缓存中查找,命中直接返回结果,否则创建新对象并写入缓存。
- 一些文章说lua字串是全局表里的唯一对象,情况如下:
- lua5.1:不管长短串,都写入全局表和查重。
- lua5.2:只有短串写入全局表和查重。
- lua5.3&lua5.4:在lua5.2版本的基础上,先查缓存。
luaS_newlstr 创建字符串
/*
** new string (with explicit length)
*/
TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
if (l <= LUAI_MAXSHORTLEN) /* short string? */
return internshrstr(L, str, l);
else {
TString *ts;
if (unlikely(l >= (MAX_SIZE - sizeof(TString))/sizeof(char)))
luaM_toobig(L);
ts = luaS_createlngstrobj(L, l);
memcpy(getstr(ts), str, l * sizeof(char));
return ts;
}
}
- 长串or短串类型测试和处理。
- 长串长度边界测试。
internshrstr 创建短字符串
/*
** Checks whether short string exists and reuses it or creates a new one.
*/
static TString *internshrstr (lua_State *L, const char *str, size_t l) {
TString *ts;
global_State *g = G(L);
stringtable *tb = &g->strt;
unsigned int h = luaS_hash(str, l, g->seed, 1);
TString **list = &tb->hash[lmod(h, tb->size)];
lua_assert(str != NULL); /* otherwise 'memcmp'/'memcpy' are undefined */
for (ts = *list; ts != NULL; ts = ts->u.hnext) {
if (l == ts->shrlen && (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) {
/* found! */
if (isdead(g, ts)) /* dead (but not collected yet)? */
changewhite(ts); /* resurrect it */
return ts;
}
}
/* else must create a new string */
if (tb->nuse >= tb->size) { /* need to grow string table? */
growstrtab(L, tb);
list = &tb->hash[lmod(h, tb->size)]; /* rehash with new size */
}
ts = createstrobj(L, l, LUA_VSHRSTR, h);
memcpy(getstr(ts), str, l * sizeof(char));
ts->shrlen = cast_byte(l);
ts->u.hnext = *list;
*list = ts;
tb->nuse++;
return ts;
}
折叠
- 计算字符串的哈希值,找到对应的桶,在桶查找相同的串,命中进行垃圾收集测试并返回,否则创建新的串放入桶中。
- 垃圾收集测试命中则清除垃圾收集标记。
- 哈希表装填因子测试,命中哈希表生长。
createstrobj 创建字符串对象
/*
** creates a new string object
*/
static TString *createstrobj (lua_State *L, size_t l, int tag, unsigned int h) {
TString *ts;
GCObject *o;
size_t totalsize; /* total size of TString object */
totalsize = sizelstring(l);
o = luaC_newobj(L, tag, totalsize);
ts = gco2ts(o);
ts->hash = h;
ts->extra = 0;
getstr(ts)[l] = '\0'; /* ending 0 */
return ts;
}
- 动态计算内存大小,一次申请内存并填充字符串。(一次申请内存TString的char contents[1]特性)。
sizelstring 动态计算TString结构体内存
#define offsetof(s,m) ((size_t)&(((s*)0)->m))
#define sizelstring(l) (offsetof(TString, contents) + ((l) + 1) * sizeof(char))
- offsetof 语义为成员变量m相对于结构体首地址的内存偏移。
- sizelstring(l) 动态计算结构体TString内存大小 = contents内存偏移 + (size + 1)* sizeof(char))。
- (size + 1) 包含'\0'字符串结束符。
growstrtab 字符串哈希表生长
static void growstrtab (lua_State *L, stringtable *tb) {
if (unlikely(tb->nuse == MAX_INT)) { /* too many strings? */
luaC_fullgc(L, 1); /* try to free some... */
if (tb->nuse == MAX_INT) /* still too many? */
luaM_error(L); /* cannot even create a message... */
}
if (tb->size <= MAXSTRTB / 2) /* can grow string table? */
luaS_resize(L, tb->size * 2);
}
- 一系列边界测试,通过则生长为原来的2倍。
luaS_resize 重置字符串哈希表的大小
/*
** Resize the string table. If allocation fails, keep the current size.
** (This can degrade performance, but any non-zero size should work
** correctly.)
*/
void luaS_resize (lua_State *L, int nsize) {
stringtable *tb = &G(L)->strt;
int osize = tb->size;
TString **newvect;
if (nsize < osize) /* shrinking table? */
tablerehash(tb->hash, osize, nsize); /* depopulate shrinking part */
newvect = luaM_reallocvector(L, tb->hash, osize, nsize, TString*);
if (unlikely(newvect == NULL)) { /* reallocation failed? */
if (nsize < osize) /* was it shrinking table? */
tablerehash(tb->hash, nsize, osize); /* restore to original size */
/* leave table as it was */
}
else { /* allocation succeeded */
tb->hash = newvect;
tb->size = nsize;
if (nsize > osize)
tablerehash(newvect, osize, nsize); /* rehash for new size */
}
}
- 若nsize < osize 先把原来的元素重新散列到nsize长度的桶里,再内存收紧。
- 若nsize > osize 先内存扩容,若扩容成功把原来的元素散列到桶里,否则保持不变。
tablerehash 重新计算哈希
static void tablerehash (TString **vect, int osize, int nsize) {
int i;
for (i = osize; i < nsize; i++) /* clear new elements */
vect[i] = NULL;
for (i = 0; i < osize; i++) { /* rehash old part of the array */
TString *p = vect[i];
vect[i] = NULL;
while (p) { /* for each string in the list */
TString *hnext = p->u.hnext; /* save next */
unsigned int h = lmod(p->hash, nsize); /* new position */
p->u.hnext = vect[h]; /* chain it into array */
vect[h] = p;
p = hnext;
}
}
}
- 重新散列元素
- 此算法某些元素可能会重复被计算。
- 如元素E本来放在1号桶里,哈希取模后放到了2号桶里。遍历扫到2号桶,E又计算一遍位置还是放在2号桶。
luaS_hash 字符串哈希算法
unsigned int luaS_hash (const char *str, size_t l, unsigned int seed,
size_t step) {
unsigned int h = seed ^ cast_uint(l);
for (; l >= step; l -= step)
h ^= ((h<<5) + (h>>2) + cast_byte(str[l - 1]));
return h;
}
- 类似线性同余法的随机数生成算法。
lmod
/*
** 'module' operation for hashing (size is always a power of 2)
*/
#define lmod(s,size) \
(check_exp((size&(size-1))==0, (cast_int((s) & ((size)-1)))))
- 取余,size必须是2的n次幂,此算法才成立。
luaM_reallocvector 重新分配顺序表内存
#define firsttry(g,block,os,ns) ((*g->frealloc)(g->ud, block, os, ns))
/*
** Generic allocation routine.
** If allocation fails while shrinking a block, do not try again; the
** GC shrinks some blocks and it is not reentrant.
*/
void *luaM_realloc_ (lua_State *L, void *block, size_t osize, size_t nsize) {
void *newblock;
global_State *g = G(L);
lua_assert((osize == 0) == (block == NULL));
newblock = firsttry(g, block, osize, nsize);
if (unlikely(newblock == NULL && nsize > 0)) {
if (nsize > osize) /* not shrinking a block? */
newblock = tryagain(L, block, osize, nsize);
if (newblock == NULL) /* still no memory? */
return NULL; /* do not update 'GCdebt' */
}
lua_assert((nsize == 0) == (newblock == NULL));
g->GCdebt = (g->GCdebt + nsize) - osize;
return newblock;
}
#define luaM_reallocvector(L, v,oldn,n,t) \
(cast(t *, luaM_realloc_(L, v, cast_sizet(oldn) * sizeof(t), \
cast_sizet(n) * sizeof(t))))
- g->frealloc 内存分配器,在创建状态机的时候可以由用户自己指定。
- 很多内存管理器依据目前内存大小优化内存分配,故传入目前内存大小参数。
- 尝试分配内存,若分配失败则进行GC后再次尝试。
- GCdebt GC相关标记。