概述
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相關標記，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/498607.html
標籤：其他
下一篇：機器學習—神經網路