losophy

lua字符串

发表于 更新于

c语言没有自带字符串类型，这导致有非常多的用c写的软件都自己实现一个处理字符串的类型。
一般来说，要表示一个字符串，核心就是以下两个数据：

  • 字符串长度
  • 指向存放字符串内存数据的指针

Lua自己的字符串类型的实现也没有绕过这两个核心内容。

内化的字符串

  • 在Lua虚拟机中存在一个全局的数据区，用来存放当前系统中的所有字符串
  • 同一个字符串数据，在Lua虚拟机中只可能有一份副本，一个字符串一旦创建，将是不可变更的
  • 变量存放的仅是字符串的引用，而不是其实际内容

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

实现

1
2
3
4
5
6
7
8
9
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成员。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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数组的索引值。如果这里已经有元素，则使用链表串接起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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.

相关文章