Lua 源码解析（二）：基本数据类型 —— 字符串

前言

Lua 中共有两种字符串的变体类型，分别是短字符串和长字符串。在 Lua 中，字符串是一种不可变的数据类型，即一旦创建，就不能再被修改。因此，Lua 会维护一个字符串池，在创建字符串之前会先检查字符串是否已经存在，如果存在则直接返回，否则创建一个新的字符串。为此 Lua 会对字符串做很多额外的工作，如计算它们的哈希值，初始化字符串池等等。我们将在本文中详细讨论这些内容。

String 的定义

在 Lua 中的数据类型 中我们介绍了 Lua 中字符串的类型定义：

/* Variant tags for strings */
#define LUA_VSHRSTR	makevariant(LUA_TSTRING, 0)  /* short strings */
#define LUA_VLNGSTR	makevariant(LUA_TSTRING, 1)  /* long strings */

#define setsvalue(L,obj,x) \
  { TValue *io = (obj); TString *x_ = (x); \
    val_(io).gc = obj2gco(x_); settt_(io, ctb(x_->tt)); \
    checkliveness(L,io); }

在 Lua 中，字符串的类型标签是 LUA_TSTRING，而字符串的变体标签有两种，分别是 LUA_VSHRSTR 和 LUA_VLNGSTR。其中，LUA_VSHRSTR 用于表示短字符串，LUA_VLNGSTR 用于表示长字符串。

其中 TString 的定义如下：

/*
** Header for a string value.
*/
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;

可以看到 TString 结构体同时包含了短字符串和长字符串的信息。其中 hash 用于存放字符串的哈希值，而 contents 则指向字符串的首字符位置。

针对短字符串，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;
  struct TString *hnext;  /* linked list for hash table */
  char contents[1];
} TString;

而针对长字符串，TString 的结构为：

typedef struct TString {
  CommonHeader;
  lu_byte extra;  /* reserved words for short strings; "has hash" for longs */
  unsigned int hash;
  size_t lnglen;  /* length for long strings */
  char contents[1];
} TString;

由 TString *hnext; 的定义可以看出，Lua 仅针对短字符串做了字符串池的处理，字符串池是通过哈希表实现的，且哈希冲突的解决方式是链表法。因此短字符串需要维护一个 hnext 指针，用于指向哈希表中的下一个字符串。

此外，extra 对于短字符串与长字符串也有不同的含义。对于短字符串，extra 用于标记该字符串是否是系统的保留字符串，而对于长字符串，extra 用于标记该字符串是否已经计算过哈希值。

我们可以在 lstring.h 中找到一个宏定义：

/*
** test whether a string is a reserved word
*/
#define isreserved(s)	((s)->tt == LUA_VSHRSTR && (s)->extra > 0)

该宏用于判断一个字符串是否是系统的保留字符串。可以看出，如果一个字符串是短字符串且 extra 大于 0，则该字符串是系统的保留字符串。

关于长短字符串的界限，Lua 在 llimits.h 中定义了一个宏：

/*
** Maximum length for short strings, that is, strings that are
** internalized. (Cannot be smaller than reserved words or tags for
** metamethods, as these strings must be internalized;
** #("function") = 8, #("__newindex") = 10.)
*/
#if !defined(LUAI_MAXSHORTLEN)
#define LUAI_MAXSHORTLEN	40
#endif

这意味着默认情况下 Lua 认为 长度小于 40 的字符串是短字符串，否则是长字符串。该值也可以自行调整并重新编译 Lua，但需要注意该值必须大于系统的保留字符串长度。

String Table

前文中我们提到，Lua 会维护一个字符串池，用于存放短字符串。而该字符串池就是通过哈希表实现的。被称为 stringtable，定义在 lstate.h 中：

typedef struct stringtable {
  TString **hash;
  int nuse;  /* number of elements */
  int size;
} stringtable;

其中 hash 是一个指针数组，指向第一个哈希桶中的首个字符串。而 nuse 则表示当前字符串池中的字符串数量，size 则表示哈希表的大小。总体来看 stringtable 的结构十分简单，这是因为其哈希冲突的解决方式是链表法，且链表结构已经被 TString 中的 hnext 字段包含。

stringtable 会随着 lua 的启动而一同被初始化，并永久存在于 lua 的全局状态中。在 lstate.h 中，我们可以看到这样一个结构体：

/*
** 'global state', shared by all threads of this state
*/
typedef struct global_State {
  // ...
  stringtable strt;  /* hash table for strings */
  // ...
  TString *strcache[STRCACHE_N][STRCACHE_M];  /* cache for strings in API */
  // ...
} global_State;

/*
** 'per thread' state
*/
struct lua_State {
  // ...
  global_State *l_G;
  // ...
};

#define G(L)	(L->l_G)

global_State 即为 lua 的全局状态，其中就包含了字符串池 strt，而 global_State 又被包含在 lua_State 中。这意味着，针对每一个 Lua 线程，通过该线程的 lua_State 指针 *L，我们就可以通过 stringtable *tb = &G(L)->strt; 这样的方式来访问全局的字符串池。

此外，可以看到 global_State 中还有一个 strcache 数组，该数组的作用会放在下文说明。

与 stringtable 相关的操作函数均定义在 lstring.c 中。

stringtable 相关函数

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;
    }
  }
}

tablerehash 函数的主要作用是在字符串表大小发生变化时，重新计算每个字符串的位置，并将它们插入到新的哈希表中。这里已经假定 vect 已经经过了扩容，osize 为旧的哈希表大小，nsize 为新的哈希表大小。

/*
** 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 */
  }
}

luaS_resize 函数用于调整字符串表的大小。其中对于空间的重新分配使用到了 luaM_reallocvector 宏，这部分我们会在 Lua 的内存管理中继续讨论，此处只需要知道这个宏可以用于重新分配字符串表的空间即可。

void luaS_remove (lua_State *L, TString *ts) {
  stringtable *tb = &G(L)->strt;
  TString **p = &tb->hash[lmod(ts->hash, tb->size)];
  while (*p != ts)  /* find previous element */
    p = &(*p)->u.hnext;
  *p = (*p)->u.hnext;  /* remove element from its list */
  tb->nuse--;
}

luaS_remove 函数用于从字符串表中移除一个字符串。首先通过哈希值找到该字符串所在的哈希桶，然后遍历该哈希桶中的链表，找到该字符串的前一个字符串，将其 hnext 指向该字符串的下一个字符串，从而将该字符串从哈希表中移除。

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);
}

growstrtab 函数用于在字符串表中的字符串数量达到一定阈值时，对字符串表进行扩容。

字符串哈希方法

Lua 中对字符串的哈希方法为：以当前的时间作为起始种子，根据字符串的内容以某个步长进行逐位的异或运算，最终得到字符串的哈希值。对于短字符串而言，一般而言步长为 1，即每个字符都参与哈希计算。而对于长字符串，步长则会随字符串的长度而增加，以减少哈希冲突的概率。

/*
** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a long string to
** compute its hash
*/
#if !defined(LUAI_HASHLIMIT)
#define LUAI_HASHLIMIT		5
#endif

首先定义了一个宏 LUAI_HASHLIMIT，表示 Lua 计算哈希值时最多使用的字符数。默认情况下，这一数值为 2^5 = 32。

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;
}


unsigned int luaS_hashlongstr (TString *ts) {
  lua_assert(ts->tt == LUA_VLNGSTR);
  if (ts->extra == 0) {  /* no hash? */
    size_t len = ts->u.lnglen;
    size_t step = (len >> LUAI_HASHLIMIT) + 1;
    ts->hash = luaS_hash(getstr(ts), len, ts->hash, step);
    ts->extra = 1;  /* now it has its hash */
  }
  return ts->hash;
}

luaS_hash 函数用于计算字符串的哈希值，可以看到计算的基本流程就是由 seed 作为起始种子，然后根据字符串的内容以 step 步长进行逐位的异或运算。而 luaS_hashlongstr 函数则用于计算长字符串的哈希值，其中 step 的值会随字符串的长度而增加，以保证最多只有 2^LUAI_HASHLIMIT 个字符参与哈希计算。

此外可以看到，对于长字符串只会计算一次哈希值，计算完毕后会将 extra 置为 1，表示该字符串已经计算过哈希值。

字符串的创建

Lua 中为了提升字符串的创建及查找性能，除了 stringtable 外还做了一层额外的缓存，也就是上文提到的 strcache。strcache 利用了程序的 “时间/空间局部性” 思想，将最近使用的字符串缓存起来，下次再有创建相同字符串的需求时，可以直接从缓存中取出。相比于 stringtable，strcache 是一个结构更加简单的一级缓存，它的容量更小，更新的频率也更高。在创建字符串时，Lua 会先检查 strcache 中是否已经存在该字符串，如果存在则直接返回，否则再去 stringtable 中查找。

以下我们来看一下字符串的创建过程：

/*
** 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 *luaS_createlngstrobj (lua_State *L, size_t l) {
  TString *ts = createstrobj(L, l, LUA_VLNGSTR, G(L)->seed);
  ts->u.lnglen = l;
  return ts;
}

createstrobj 与 luaS_createlngstrobj 分别用于创建短字符串和长字符串。但这里仅仅是分配了长度为 l 的字符串的内存空间，并做了一些初始化工作，如将 ts->extra 置为 0，字符串末尾置为 \0 等，并没有赋予该对象具体的字符串内容。

/*
** 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;
}

internshrstr 函数用于创建短字符串并将其加入到 stringtable 中。首先计算字符串的哈希值，然后遍历哈希表中的链表，查找是否已经存在该字符串。如果存在则直接返回，否则创建一个新的字符串对象，并将其加入到哈希表中。

这里使用了 memcpy 将真实的字符串内容拷贝到了新创建的字符串对象中。这里的 memcpy 是安全的，因为在 createstrobj 中已经为字符串对象分配了足够的空间。

/*
** 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;
  }
}

luaS_newlstr 函数用于创建一个新的字符串对象。如果字符串长度小于等于 LUAI_MAXSHORTLEN，则调用 internshrstr 函数创建短字符串，否则调用 luaS_createlngstrobj 函数创建长字符串。可以看到，长字符串并没有被加入到 stringtable 中。

/*
** 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];
}

luaS_new 就是最终的字符串创建函数了，它首先会检查 strcache 中是否已经存在该字符串，如果存在则直接返回，否则调用 luaS_newlstr 函数创建一个新的字符串对象，并将其加入到 strcache 中。

我们也可以从中看到 strcache 的更新逻辑：首先，会通过字符串的地址直接计算出一个哈希值并存放在对应的行中；其次，每次有新的字符串创建时，会将 strcache[i] 中的所有字符串向后移动一个位置，最后将新创建的字符串放在第一个位置。

在 llimits.h 中，我们可以看到 STRCACHE_N 和 STRCACHE_M 的定义：

/*
** Size of cache for strings in the API. 'N' is the number of
** sets (better be a prime) and "M" is the size of each set (M == 1
** makes a direct cache.)
*/
#if !defined(STRCACHE_N)
#define STRCACHE_N		53
#define STRCACHE_M		2
#endif

STRCACHE_N 是一个大小适中的素数，保证了缓存的容量以及较低的哈希冲突概率。STRCACHE_M 是一个较小的值，这保证了创建时的查找效率，如果该值过大则创建字符串就会十分耗时。

lstring.c 中的其他函数

lstring.c 中还有一些其他的函数，如字符串的比较、初始化等，这里简要分析：

/*
** equality for long strings
*/
int luaS_eqlngstr (TString *a, TString *b) {
  size_t len = a->u.lnglen;
  lua_assert(a->tt == LUA_VLNGSTR && b->tt == LUA_VLNGSTR);
  return (a == b) ||  /* same instance or... */
    ((len == b->u.lnglen) &&  /* equal length and ... */
     (memcmp(getstr(a), getstr(b), len) == 0));  /* equal contents */
}

luaS_eqlngstr 函数首先会直接判断两个字符串是否是同一个实例，如果是则直接返回真。否则再比较两个字符串的长度以及内容是否相同。

/*
** Initialize the string table and the string cache
*/
void luaS_init (lua_State *L) {
  global_State *g = G(L);
  int i, j;
  stringtable *tb = &G(L)->strt;
  tb->hash = luaM_newvector(L, MINSTRTABSIZE, TString*);
  tablerehash(tb->hash, 0, MINSTRTABSIZE);  /* clear array */
  tb->size = MINSTRTABSIZE;
  /* pre-create memory-error message */
  g->memerrmsg = luaS_newliteral(L, MEMERRMSG);
  luaC_fix(L, obj2gco(g->memerrmsg));  /* it should never be collected */
  for (i = 0; i < STRCACHE_N; i++)  /* fill cache with valid strings */
    for (j = 0; j < STRCACHE_M; j++)
      g->strcache[i][j] = g->memerrmsg;
}

luaS_init 函数用于初始化字符串表和字符串缓存。首先会为字符串表分配空间，并初始化哈希表。然后会为字符串缓存填充初始值，这里填充的是一个内存错误的字符串。在 Lua 的初始化过程中，就会调用这个函数以初始化字符串表和字符串缓存。

// lstate.c

/*
** open parts of the state that may cause memory-allocation errors.
** ('g->nilvalue' being a nil value flags that the state was completely
** build.)
*/
static void f_luaopen (lua_State *L, void *ud) {
  global_State *g = G(L);
  UNUSED(ud);
  stack_init(L, L);  /* init stack */
  init_registry(L, g);
  luaS_init(L);
  luaT_init(L);
  luaX_init(L);
  g->gcrunning = 1;  /* allow gc */
  setnilvalue(&g->nilvalue);
  luai_userstateopen(L);
}

总结

字符串在 Lua 中是一种不可变对象，Lua 使用 TString 结构体来表示一个字符串对象，长字符串与短字符串分别会使用该结构中的不同字段。为了优化字符串的创建和查找性能，Lua 维护了两层字符串的缓存机制，分别是 stringtable 和 strcache。stringtable 是一个全局的哈希表，用于存放运行过程中创建的所有短字符串，stringtable 通过链表法解决哈希冲突，且对于字符串的哈希方式为逐位异或。而 strcache 则是一个容量更小、结构更简单、更新频率更高的一级缓存，用于存放最近使用的字符串，以提升字符串的创建性能，strcache 通过字符串的地址直接计算哈希值，然后将字符串放入对应的行中。