lua字符串 | losophy

内化的字符串

Lua

虚拟机中存在一个 全局的数据区 ，用来存放当前系统中的所有字符串

同一个字符串数据，在

Lua

虚拟机中 只可能有一份副本 ，一个字符串一旦创建，将是不可变更的

变量 存放的仅是字符串的引用 ，而不是其实际内容

Lua 在字符串实现上使用内化这种方案 （hash） 的优点在于，进行字符串数据的比较和查找操作时，性能会提升不少，因为这两个操作的核心都是字符串的比较。传统的字符串比较算法是根据字符串长度逐位来进行对比，这个时间复杂度与字符串长度线性相关；而内化之后，在已知字符串散列值的情况下，只需要一次整数的比较即可（lua字符串的比较是检测字符串的hash是否一样来判断两个字符串是否相等）。这个实现还有另一大好处，那就是空间优化，多份。
相同的字符串在整个系统中只存在一份副本。 Lua 是一个在设计之初就把性能、资源占用等放在重要位置的语言，这里再一次得到了体现。
当然，这个实现并不是完全没有缺陷的。以前面描述的创建字符串的过程来说，在创建一个新的字符串时，首先会检查系统中是否有相同的数据，只有不存在的情况下才创建，这与直接创建字符串相比，多了一次查找过程。

实现

typedef union TString {
  L_Umaxalign dummy;  /* ensures maximum alignment for strings */
  struct {
    CommonHeader;
    lu_byte reserved;//是否是Lua虚拟机中的保留字符串，1不会在GC阶段被回收
    unsigned int hash;//字符串的散列值
    size_t len;//字符串长度 
  } tsv;
} TString;

可以看到，这是一个联合体，其目的是为了让 TString 数据类型按照 L_Umaxalign 类型来对齐。

1 2	#define LUAI_USER_ALIGNMENT_T union { double u; void *s; long l; } typedef LUAI_USER_ALIGNMENT_T L_Umaxalign;

在 C 语言中， struct/union 这样的复合数据类型是按照这个类型中最大对齐量的数据来对齐的，所以这里就是按照 double 类型的对齐量来对齐的。之所以要进行对齐操作，是为了在 CPU 读取数据时性能更高。

Lua 会把系统中的所有字符串存在一个全局的地方，这个全局变量就是 global_state 的 strt 成员。

typedef struct global_State {
  stringtable strt;  /* hash table for strings */
  ...
} global_State;

typedef struct stringtable {
  GCObject **hash;//这是一个散列数组，专门用于存放字符串
  ...
} stringtable;

union GCObject {
  GCheader gch;
  union TString ts;
  ...
};

当新创建一个字符串 TString 时，首先根据散列算法算出散列值，这就是 strt 数组的索引值。如果这里已经有元素，则使用链表串接起来。

TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
  ...
  for (l1=l; l1>=step; l1-=step)  /* compute hash */
    h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1]));
  ...
    for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)];
       o != NULL;
       o = o->gch.next) {//如果这里已经有元素，则使用链表串接起来
    TString *ts = rawgco2ts(o);
    if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0)) {
      /* string may be dead */
      if (isdead(G(L), o)) changewhite(o);
      return ts;
    }
  }
  return newlstr(L, str, l, h);  /* not found */
}

static TString *newlstr (lua_State *L, const char *str, size_t l,
                                       unsigned int h) {
  ...
  ts = cast(TString *, luaM_malloc(L, (l+1)*sizeof(char)+sizeof(TString)));
  ts->tsv.len = l;
  ts->tsv.hash = h;
  ts->tsv.marked = luaC_white(G(L));
  ts->tsv.tt = LUA_TSTRING;
  ts->tsv.reserved = 0;
  memcpy(ts+1, str, l*sizeof(char));
  ((char *)(ts+1))[l] = '\0';  /* ending 0 */
  tb = &G(L)->strt;
  h = lmod(h, tb->size);
  ts->tsv.next = tb->hash[h];  /* chain new entry */
  tb->hash[h] = obj2gco(ts);
  tb->nuse++;
  ...
}

resize

当数据量非常大时，分配到每个桶上的数据也会非常多，这样一次查找也退化成了一次线性的查找过程。 Lua 中也考虑了这种情况，所以有一个重新散列 （ rehash ） 的过程，这就是当字符串数据非常多时，会重新分配桶的数量，降低每个桶上分配到的数据数量，这个过程在函数 luaS_resize 中。

有两处关于 luaS_resize 函数的调用：


      lgc.c

的


      checkSizes

函数：这里会进行检查，如果此时桶的数量太大，比如是实际存放的字符串数量的4倍，那么会将散列桶数组减少为原来的一半。


      lstring.c

的


      newlstr

函数：如果此时字符串的数量大于桶数组的数量，且桶数组的数量小于


      MAX_INT/2

，那么就进行翻倍的扩容。

从lua-5.1.1中分离出来的字符串实现代码

lstring

reference

《Lua设计与实现》

Ayúdate que Dios te ayudará. A quien madruga Dios le ayuda.