咖啡's blog

专心 专注 专业

0%

Lua源码笔记(3)--Table的rehash

发表于 更新于 分类于 ， Valine：

上一篇文章提到在设置一个新的键值时，当没有可用的空间时，会出发rehash操作，而上文也提到设置键值是关乎Lua在宿主语言中运行的性能最重要的操作,而当设置键值newkey操作触发rehash时，rehash的性能又关乎到newkey的性能，具体过程参看下列详细的分析过程，其中rehash函数中的computesizes和resize函数需要重点理解。

rehash的目的

触发rehash的原因就是哈希列表没有空闲节点供新的键值设置，说明要扩展哈希列表，那么存在的问题是扩展多长的哈希列表的长度是合适的呢？这个问题就是rehash函数主要解决的问题。

rehash函数分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static void rehash (lua_State *L, Table *t, const TValue *ek) {
  int nasize, na;
  //#define MAXBITS		26
  int nums[MAXBITS+1];  
  int i;
  int totaluse;
  // 初始化nums数组[1,MAXBITS]
  // 注意一下0分片其实没有使用
  for (i=0; i<=MAXBITS; i++) nums[i] = 0;  
  // 计算数组部分的已经使用(不为nil)的节点
  nasize = numusearray(t, nums);  
  totaluse = nasize;  
  // 计算哈希表部分键值为数值的节点的数量
  totaluse += numusehash(t, nums, &nasize);  
  // 统计额外的新的节点(ek)所在分片的值(0或者1)
  nasize += countint(ek, nums);
  totaluse++;
  // 重新计算Table表的数组部分的长度
  na = computesizes(nums, &nasize);
  // 重新分配Table的数组部分长度和哈希列表的长度
  // nasize为数组的最佳容量值(2的倍数容量)
  // 哈希列表的长度为totaluse(总长度)-na(实际的数组长度)
  resize(L, t, nasize, totaluse - na);
}

countint函数分析

需要强调的是numusehash函数也是调用countint函数，以统计节点中key为数值的节点数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static int countint (const TValue *key, int *nums) {
  // 判断key是不是数值型且数值
  int k = arrayindex(key);
  // #define MAXASIZE	(1 << MAXBITS)
  // 2^MAXBITS  => 2^26
  if (0 < k && k <= MAXASIZE) { 
    // nums数组是哈希列表的分片统计数组
    // 如果K落在这个分片则加1 
    nums[ceillog2(k)]++;  
    return 1;
  }
  else
    return 0;
}

numusehash函数分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// totaluse是哈希列表非空节点的长度
// ause是哈希列表中可以放到Table表数组部分的长度
static int numusehash (const Table *t, int *nums, int *pnasize) {
  int totaluse = 0;  /* total number of elements */
  int ause = 0;  /* summation of `nums' */
  int i = sizenode(t);
  while (i--) {
    Node *n = &t->node[i];
    if (!ttisnil(gval(n))) {
      // 参见countint函数分析
      // 判断key是数值并且在哈希长度范围内countint返回1
      ause += countint(key2tval(n), nums);
      totaluse++;
    }
  }
  // 统计可移往数组的数量
  *pnasize += ause;
  return totaluse;
}

computesizes函数分析

在查看这个函数的注释前，可以参考这篇文章的说明;computesizes这个函数是重新计算Table表中数组部分和哈希部分的长度，其中computesizes的参数nums数组是分片的统计数组，分片数组的统计值是分别在numusearray和countint中统计的，如下所示

分片 -1 2 4 8 16 32
数组 nums[0] nums[1] nums[2] nums[3] nums[4] nums[5] 
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
static int computesizes (int nums[], int *narray) {
  int i;
  int twotoi;  /* 2^i */
  int a = 0;  /* number of elements smaller than 2^i */
  int na = 0;  /* number of elements to go to array part */
  int n = 0;  /* optimal size for array part */
  for (i = 0, twotoi = 1; twotoi/2 < *narray; i++, twotoi *= 2) {
    if (nums[i] > 0) {
      // a表示分片数组的累加值
      // twotoi代表分片的右区间值
      // 以下逻辑表示当累计值大于当前容量的一半
      // 则记录下当前最佳容量值n,以及当前实际使用的容量值na
      a += nums[i];
      if (a > twotoi/2) {  /* more than half elements present? */
        n = twotoi;  /* optimal size (till now) */
        na = a;  /* all elements smaller than n will go to array part */
      }
    }
    if (a == *narray) break;  /* all elements already counted */
  }
  // 这里*narray表示最佳容量值
  // 返回的na表示当前实际容量值
  *narray = n;
  lua_assert(*narray/2 <= na && na <= *narray);
  return na;
}

resize函数分析

resize函数相对逻辑简单，只是需要注意的是重新扩容以后的赋值操作跟长度正相关。

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
static void resize (lua_State *L, Table *t, int nasize, int nhsize) {
  int i;
  int oldasize = t->sizearray;
  int oldhsize = t->lsizenode;
  Node *nold = t->node;  /* save old hash ... */
  // 扩展数组长度
  // 扩展的时候已经将原数组外的节点值设置成nil
  if (nasize > oldasize)  /* array part must grow? */
    setarrayvector(L, t, nasize);
  // 重新设置哈希列表部分
  setnodevector(L, t, nhsize);  
  // 缩小数组长度的处理
  if (nasize < oldasize) {  /* array part must shrink? */
    t->sizearray = nasize;
    /* re-insert elements from vanishing slice */
    for (i=nasize; i<oldasize; i++) {
      if (!ttisnil(&t->array[i]))
        setobjt2t(L, luaH_setnum(L, t, i+1), &t->array[i]);
    }
    /* shrink array */
    luaM_reallocvector(L, t->array, oldasize, nasize, TValue);
  }
  // 哈希部分的节点重新插入
  for (i = twoto(oldhsize) - 1; i >= 0; i--) {
    Node *old = nold+i;
    if (!ttisnil(gval(old)))
      setobjt2t(L, luaH_set(L, t, key2tval(old)), gval(old));
  }
  // 释放原来的哈希数组的空间
  if (nold != dummynode)
    luaM_freearray(L, nold, twoto(oldhsize), Node); 
}

这里要分析以下setnodevector函数的实现，这里需要说的两个重点，一个是Table表哈希部分的长度lsizenode，记录的是以2为基的次数，而实际长度是2^lsizenode,而实际lsizenode的长度也不能超过MAXBITS(26),另外Table表的lastfree是在这个函数里设置为哈希列表的最后一个节点，getfreepos函数要寻找空闲节点时是从最后一个节点向前查找。

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
static void setnodevector (lua_State *L, Table *t, int size) {
  int lsize;
  if (size == 0) {  /* no elements to hash part? */
    t->node = cast(Node *, dummynode);  /* use common `dummynode' */
    lsize = 0;
  }
  else {
    int i;
    // 得到size的以2为底的对数
    lsize = ceillog2(size);
    if (lsize > MAXBITS)
      luaG_runerror(L, "table overflow");
    // 得到实际长度 2^lsize
    size = twoto(lsize);
    t->node = luaM_newvector(L, size, Node);
    for (i=0; i<size; i++) {
      Node *n = gnode(t, i);
      gnext(n) = NULL;
      setnilvalue(gkey(n));
      setnilvalue(gval(n));
    }
  }
  t->lsizenode = cast_byte(lsize);
  // 为得到空闲节点设置
  // 参考getfreepos函数
  t->lastfree = gnode(t, size);  /* all positions are free */
}