Lua字符串的設(shè)計(jì)
在Lua中字符串是一種被內(nèi)化的數(shù)據(jù)類型。怎么理解被內(nèi)化的含義呢？簡單來說就是每個存放Lua字符串的變量。存儲的都不是字符串內(nèi)容的拷貝，而是它的一份引用。因此每當(dāng)創(chuàng)建新的字符串的時候，我們首先要檢查系統(tǒng)中是否已經(jīng)存在一份相同的字符串了，如果有的話，直接讓當(dāng)前的指針變量指向它，否則就創(chuàng)建一份新的字符串?dāng)?shù)據(jù)，然后讓當(dāng)前指針指向。
因?yàn)樽址⒎潜４娴氖菍?shí)際內(nèi)容的拷貝而是引用，因此Lua字符串是不可變的。我們聯(lián)想下Java或者OC中字符串不可變的原因。是否也是相同的設(shè)計(jì)，保存的只是字符串的引用，因?yàn)橐坏└淖兞俗址產(chǎn)的引用，a原來指向的內(nèi)存中的內(nèi)容并不會改變。Java和OC都推薦直接使用字面量的方式創(chuàng)建字符串，都說這樣高效。那高效體現(xiàn)在什么地方呢。
Java 字符串通過字面量創(chuàng)建首先會去字符串池去查找有無相應(yīng)的字符串，如果有則直接讓當(dāng)前變量執(zhí)行相應(yīng)的內(nèi)存。同樣OC字面量創(chuàng)建會自動去常量存儲區(qū)去查找,也是類似的機(jī)制。那么我們是否可以推斷3種語言的字符串底層設(shè)計(jì)是一樣的？
a = '1'
a = '1'..'2'
上面代碼具體的執(zhí)行過程如下圖
改變a的只是a的指向，并不會對a原先指向的內(nèi)存產(chǎn)生任何影響。
上面談到了Lua字符串是一種被內(nèi)化的數(shù)據(jù)類型。那么為了實(shí)現(xiàn)Lua字符串創(chuàng)建之前的查詢，必須有一個空間去存儲已經(jīng)創(chuàng)建而且沒有被GC的所有字符串。Lua虛擬機(jī)使用一個散列桶的方式管理字符串。
Lua在字符串實(shí)現(xiàn)上使用內(nèi)化的優(yōu)點(diǎn)在于。
- 時間上。進(jìn)行字符串的查找和比較操作的時候性能會有很大的提高。傳統(tǒng)的字符串的查找和比較，需要遍歷字符串的每一個字符，時間復(fù)雜度取決于字符串的長度，是線性遞增的。而Lua進(jìn)行字符串的比較和查詢的時候，首先去比較字符串的hash值，這一步是O(1)的時間復(fù)雜度，這一步?jīng)]有比較出來后，會對具體的兩個字符串進(jìn)行長度比較，最后仍然沒有比較出來，才會進(jìn)行逐位比較。大多情況下，前2步會對絕大多數(shù)情況進(jìn)行過濾，字符串比較和查詢很大程度是O(1)的時間復(fù)雜度。
- 空間上。因?yàn)槭且粋€內(nèi)化的方式，所有相關(guān)的字符串是共享一塊內(nèi)存。這極大的節(jié)省了相同字符串帶來的內(nèi)存消耗。
以上設(shè)計(jì)可以看到，Lua在設(shè)計(jì)之初就把性能和資源占用放到重要位置。
字符串的數(shù)據(jù)結(jié)構(gòu)如下
typedef union TString {
L_Umaxalign dummy; /* ensures maximum alignment for strings */
struct {
CommonHeader;
lu_byte reserved;
unsigned int hash;
size_t len;
} tsv;
} TString;
關(guān)于字符串的數(shù)據(jù)結(jié)構(gòu)具體幾部分上一篇有解釋，現(xiàn)在重復(fù)一遍。
- L_Umaxalign 是一個聯(lián)合體define LUAI_USER_ALIGNMENT_T union { double u; void *s; long l; } 它的類型大小會取這三種類型中最大的。在C語言中，struct/unicon會按照最大字節(jié)進(jìn)行內(nèi)存對齊的，為的降低CPU獲取數(shù)據(jù)的訪問周期，提高CPU的訪問效率。
- 內(nèi)部的結(jié)構(gòu)體tsv。CommonHeader同理，
- reserved標(biāo)注當(dāng)前字符串是否是關(guān)鍵字，標(biāo)記的關(guān)鍵字將不會在GC階段被回收
- hash 改字符串的散列值。Lua字符串比較并不會像其他的語言那種一般的做法進(jìn)行諸位比較。而是僅僅比較字符串的散列值。
- len 字符串的長度
我們剛才提到了會有一個散列桶會存儲Lua中所有的字符串。這個變量是global_state 的strt。具體的結(jié)構(gòu)
typedef struct stringtable {
GCObject **hash; // 存放的GCObject *的list
lu_int32 nuse; /* number of elements */
int size; // 散列桶的大小
} stringtable;
散列桶的結(jié)構(gòu)類似上圖。外層數(shù)組，內(nèi)層鏈表的結(jié)構(gòu)。
接下來我們看一下創(chuàng)建一個新的字符串的過程
偽代碼
根據(jù)字符串的hash值去散列桶去查找具體的桶
找到對應(yīng)的桶后，先比較長度
長度相同，逐位比較字符
均相同找到字符串，看當(dāng)前字符串處于的狀態(tài)，if isdead(o) 則改變字符串狀態(tài)并返回
沒找到直接創(chuàng)建新字符串
真實(shí)代碼
TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
GCObject *o;
// 類型轉(zhuǎn)換
unsigned int h = cast(unsigned int, l); /* seed */
//右移運(yùn)算。 比如32 二進(jìn)制表示 00100000 則右面移5位 為00000001 = 2
size_t step = (l>>5)+1; /* if string is too long, don't hash all its chars */
size_t l1;
for (l1=l; l1>=step; l1-=step) /* compute hash */
// 取出指定字符串對應(yīng)的散列值
h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1]));
// 去散列桶去查找到對應(yīng)的桶
for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)];
o != NULL;
o = o->gch.next) {
// 這里面均為對應(yīng)的桶中鏈表對應(yīng)的元素
TString *ts = rawgco2ts(o);
// 先比較長度，長度不符合繼續(xù)查找next，長度符合諸位比較
if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0)) {
/* string may be dead */
if (isdead(G(L), o)) changewhite(o);
return ts;
}
}
// 如果找不到對應(yīng)的散列桶直接去創(chuàng)建新的字符串。
return newlstr(L, str, l, h); /* not found */
}
上面具體的過程注意的地方2點(diǎn)。
- 當(dāng)字符串特別大的時候沒有必要諸位比較，每次比較取一個步長
- 獲取的當(dāng)前字符串如果處于GC階段，改變它的狀態(tài)，達(dá)到復(fù)用的目的。
下面看下如果查找不到創(chuàng)建一個新串的過程
static TString *newlstr (lua_State *L, const char *str, size_t l,
unsigned int h) {
// 一個新的字符串的指針
TString *ts;
// stringable 結(jié)構(gòu)體指針
stringtable *tb;
// 如果字符串過大，直接報錯返回NULL
if (l+1 > (MAX_SIZET - sizeof(TString))/sizeof(char))
luaM_toobig(L);
// 創(chuàng)建字符串
ts = cast(TString *, luaM_malloc(L, (l+1)*sizeof(char)+sizeof(TString)));
// 字符串的長度為l
ts->tsv.len = l;
// 字符串的散列值為h
ts->tsv.hash = h;
// 字符串為白色(標(biāo)記GC的時候回根據(jù)字符串的狀態(tài)進(jìn)行回收)
ts->tsv.marked = luaC_white(G(L));
// 數(shù)據(jù)類型
ts->tsv.tt = LUA_TSTRING;
// 不是關(guān)鍵字
ts->tsv.reserved = 0;
// 拷貝str到ts+1位置
memcpy(ts+1, str, l*sizeof(char));
// 字符串最后一位'\0'
((char *)(ts+1))[l] = '\0'; /* ending 0 */
// 獲取global_State中的散列桶
tb = &G(L)->strt;
// 計(jì)算散列通中的存儲位置
h = lmod(h, tb->size);
// 如果原來位置有元素則next指針指向它。
ts->tsv.next = tb->hash[h]; /* chain new entry */
// 類型轉(zhuǎn)換TString轉(zhuǎn)為GCObject
tb->hash[h] = obj2gco(ts);
// 數(shù)量+1
tb->nuse++;
// 散列桶每個桶的上元素過多，觸發(fā)重新分配。
if (tb->nuse > cast(lu_int32, tb->size) && tb->size <= MAX_INT/2)
luaS_resize(L, tb->size*2); /* too crowded */
return ts;
}
總結(jié)上面
- 創(chuàng)建新的字符串。填充TString上每個Value的值。
- 計(jì)算當(dāng)前字符串在散列桶上對應(yīng)的桶，如果有值，則當(dāng)前字符串的next指針指向?qū)?yīng)桶(鏈表)的首位
- 將對應(yīng)的桶的首位賦值為創(chuàng)建的TString
- 元素數(shù)量+1
- 如果每個桶上元素過多，觸發(fā)重散列。
具體的重散列的過程如下
void luaS_resize (lua_State *L, int newsize) {
// GCObject * 的列表
GCObject **newhash;
// 結(jié)構(gòu)體指針
stringtable *tb;
int I;
// GC階段則返回
if (G(L)->gcstate == GCSsweepstring)
return; /* cannot resize during GC traverse */
// 創(chuàng)建一個List
newhash = luaM_newvector(L, newsize, GCObject *);
tb = &G(L)->strt;
// 初始化
for (i=0; i<newsize; i++) newhash[i] = NULL;
/* rehash */
for (i=0; i<tb->size; i++) {
// 在散列桶中找到對應(yīng)的桶
GCObject *p = tb->hash[I];
// p為桶中的header指針
while (p) { /* for each node in the list */
GCObject *next = p->gch.next; /* save next */
// 獲取對應(yīng)的TString的hash值
unsigned int h = gco2ts(p)->hash;
// 獲取一個新的位置
int h1 = lmod(h, newsize); /* new position */
lua_assert(cast_int(h%newsize) == lmod(h, newsize));
// p->gch的next指針指向當(dāng)前位置。為了是p->gch成為header
p->gch.next = newhash[h1]; /* chain it */
// 成為header
newhash[h1] = p;
// 賦值循環(huán)取鏈表下一個節(jié)點(diǎn)
p = next;
}
}
//釋放舊的散列桶
luaM_freearray(L, tb->hash, tb->size, TString *);
tb->size = newsize;
tb->hash = newhash;
}
重散列流程如下(上面代碼摻雜防御式編程的思想,進(jìn)行具體的流程之前，對當(dāng)前的狀態(tài)及傳入的數(shù)據(jù)進(jìn)行異常判斷)
- 判斷當(dāng)前狀態(tài)，GC階段則Return
- 開辟并初始化新的GCObject **
- 遍歷原來的散列桶。遍歷每個具體的桶，根據(jù)hash算法拿到的新的散列值確定當(dāng)前元素的位置。并chain起來
- 釋放舊的散列桶，賦值新的。
