• Lua5.4源码剖析:二. 详解String数据结构及操作算法


    概述

    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相关标记。
  • 相关阅读:
    【C++】C++调python:命令行方式(带参数)
    Java 消息策略的实现 - Kafak 是怎么设计的
    第1篇 目标检测概述 —(2)目标检测算法介绍
    C# 实现迷宫游戏
    【题解】[NOIP2015]扫雷游戏(Java & C++)
    数字人ai直播软件突破AI大模型技术,改变未来科技格局!
    zookeeper教程
    【2021集创赛】Arm杯三等奖:基于FPGA的人脸检测SoC设计
    [管理与领导-83]:IT基层管理者 - 核心技能 - 高效执行力 - 8- 提升执行力的三大方法:目标复述、任务分解、寻求帮助
    SpringBoot的Spring Security用户授权和认证
  • 原文地址:https://www.cnblogs.com/hggzhang/p/16426355.html