STLPort 哈希表 hash_map/hash_multim

KeyWords: STLPort hash_map hash_multimap erase操作慢

本文使用的STL版本是STLPort5.2.1的最新release版本，配合G++4.5版本使用。我在项目中发现一个性能的瓶颈，最终定位到的原因是使用STLPort的hash_multimap(C++11之后哈希表改为unordered_map和unordered_multimap)中erase函数消耗时间长导致的。STLPort目前已经基本不怎么更新了，C++新标准C++11/14/17基本是不支持了。对比了STL的其他版本，G++4.5自带的版本和G++7.2自带的版本发现，STLPort的erase操作和G++自带的STL unordered_multimap::erase 有200倍的执行时间的差距。

测试的方法是使用了20W节点的哈希表，然后在循环中遍历删除每一个节点。G++自带STL库，开启了O3优化，在i7 6700K的平台上面执行时间大约只有0.02S，而STLPort的执行时间有4S之多。

说个题外话，如果使用STLPort5.2.1版本的哈希表的话，最好自己打一个patch。这个版本的哈希表存在一个BUG，在删除节点时，会减少哈希表的桶的数量，有些情况会rehash，造成迭代器的失效。在循环中删除哈希表的迭代器节点，有可能得到和预期不一致的结果。BUG的地址：https://sourceforge.net/p/stlport/bugs/148/

STLPort hash_multimap数据结构

STLPort哈希表底层使用的数据结构是slist(C++11中为forward_list)，是一种单向链表的结构。所有哈希表的节点都保存在这个链式的结构上，哈希表的桶使用vector<_Slist_node_base*> _BucketVector来表示，桶的每一个节点保存了slist类型的基类指针。该指针指向了桶内第一个元素在slist中的位置。所以这个桶是一个逻辑的概念，只是一个类似于游标或者迭代器的东西，并没有在原始的数据结构中单独拿出一条链表来保存桶。获取桶内元素(假设第n个桶)的方式就是使用_BucketVector[n],_BucketVector[n + 1]确定slist中桶内元素的首尾指针，这两个指针类似于begin(),end()迭代器的概念。然后遍历该区间就可以找到桶内的所有元素。下图是一个哈希表的示意图。

hashtable.png

通过Key来查找的过程，首先需要将Key转换为桶的索引，知道数据位于哪个桶内。转换的过程是hash(Key)%bucket_count()，先用哈希函数算出Key的哈希值，然后模上桶的数量得到桶的索引(桶的数量一般是一个素数，在STLPort中也保存了一张素数表来决定桶需要分配的大小)。得到桶的索引后，就执行上面一段讲到的内容，通过首尾指针遍历桶内元素，然后比较桶内元素的Key和查找元素的Key是否相等，返回第一个相等的元素。

hash_map和hash_multimap其实并没有太多区别，都是对STLPort底层数据结构hashtable的封装，区别只是插入元素时，使用insert_unique函数还是insert_equal函数而已。

STLPort hash_multimap erase操作

template <class _Val, class _Key, class _HF,
  class _Traits, class _ExK, class _EqK, class _All>
void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
  ::erase(const_iterator __it) {
  const size_type __n = _M_bkt_num(*__it);//通过迭代器来获取桶的索引
  _ElemsIte __cur(_M_buckets[__n]);//cur节点指向桶__n的第一个元素

  size_type __erased = 0; //删除节点的个数
  if (__cur == __it._M_ite) { //如果删除的节点是桶内第一个元素
size_type __prev_b = __n;
_ElemsIte __prev = _M_before_begin(__prev_b)._M_ite; //获取__n桶的前一个节点，__prev_b返回第一个和__n桶指向同一节点的索引，这里具体后面解释
fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1,
 _M_elems.erase_after(__prev)._M_node);//将该节点删除，并且将所有指向该节点的桶，更新指向的节点。后面具体解释
++__erased;//增加删除节点计数
  }
  else { //删除的节点不是桶内第一个元素
/* 遍历__n桶，删除与入参__it相同的节点，这部分比较好理解，也没什么毛病 */
_ElemsIte __prev = __cur++;
_ElemsIte __last(_M_buckets[__n + 1]);
for (; __cur != __last; ++__prev, ++__cur) {
  if (__cur == __it._M_ite) {
_M_elems.erase_after(__prev);
++__erased;
break;
  }
}
  }

  _M_num_elements -= __erased;      //哈希节点计数更新
}

上面是STLPort的erase迭代器的过程，有两个分支，删除节点如果不是桶的首节点的话比较容易，直接找到要删除的节点删掉就好了。复杂的是要删除的节点是桶的首节点，需要找到该节点的前一个节点，并且要更新桶的首指针的指向，具体内容已经在注释中写出了。经过分析和加入调试信息打印，耗时的根源在查找待删除节点前一个节点这个函数上，_M_before_begin。

让我们一起看一下这个函数的代码。

template <class _Val, class _Key, class _HF,
  class _Traits, class _ExK, class _EqK, class _All>
__iterator__
hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
  ::_M_before_begin(size_type &__n) const {
  return _S_before_begin(_M_elems, _M_buckets, __n);　//实际的执行函数是_S_before_begin
}  

template <class _Val, class _Key, class _HF,
  class _Traits, class _ExK, class _EqK, class _All>
__iterator__
hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
  ::_S_before_begin(const _ElemsCont& __elems, const _BucketVector& __buckets,
size_type &__n) {
  _ElemsCont &__mutable_elems = __CONST_CAST(_ElemsCont&, __elems);//哈希的slist链表去除const标记
  typename _BucketVector::const_iterator __bpos(__buckets.begin() + __n);//指向__n桶的迭代器，这个迭代器是vector存储的桶的迭代器

  _ElemsIte __pos(*__bpos);//__n桶首元素指向的slist节点的迭代器，该迭代器是指向哈希表slist链表的
  if (__pos == __mutable_elems.begin()) {//该函数就是如果删除的元素是整个slist的首节点，就把slist的首节点之前的虚拟节点返回。因为slist是单链表，只有erase_after操作，如果要删除链表节点，必须找到前面的元素。
__n = 0;
return __mutable_elems.before_begin();
  }

  typename _BucketVector::const_iterator __bcur(__bpos);//__bcur指向__n桶的迭代器。
  _BucketType *__pos_node = __pos._M_node; //__pos_node是指向slist中__n桶首元素的指针。该类型和桶内存储的指针是同一类型。
  for (--__bcur; __pos_node == *__bcur; --__bcur);//向前遍历桶，找到第一个和桶指向不同元素的节点。为什么这样做，下面讲。这里是耗时的根源

  __n = __bcur - __buckets.begin() + 1;//更新入参__n的位置，返回与__n桶指向同一slist节点的第一个桶的索引。
  _ElemsIte __cur(*__bcur);//后面的过程就是从找到的前一个桶的指针开始往回遍历，找到待删除节点的前一个节点。
  _ElemsIte __prev = __cur++;
  for (; __cur != __pos; ++__prev, ++__cur);
  return __prev;
}  

上面这部分代码主要是找到待删除节点的前一个节点，但是为什么这么复杂，而且在我的项目中执行这么慢呢？最后在for (--__bcur; __pos_node == *__bcur; --__bcur);这一行代码中加了一个计数发现，在哈希节点20W时，循环删除迭代器，在删除到后面的节点时，该循环每次删除要执行5W次以上。最后考虑了一下发现这样做的原因是，因为有可能临近的很多桶中没有任何元素，所以这些临近的桶都指向了一个节点。如下图所示，是一种多个桶中没有元素指向同一节点的状态。

查找before.png

上图中，1-39999桶都没有元素，如果本次删除第40000桶的节点时，for (--__bcur; __pos_node == *__bcur; --__bcur);该循环__bcur节点要循环40000次左右查找，才能找到桶0的位置，也就是第一个与40000桶指向不同元素的桶。所以这种情况下再使用erase操作，性能会极具下降。

为什么要找到桶1并且返回呢？因为如果将__pos所指向的slist节点删除掉了，1--40000桶的指针全部都失效了，所以要找到第一个和40000桶相同指向的桶，然后把1号索引也返回。
fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1,_M_elems.erase_after(__prev)._M_node);

这句代码就是把1号到40000号桶的指向全部更新为__pos的下一个节点。

总结

STLPort的哈希表设计决定了如果哈希表过大时，而且存在很多空桶的情况下，删除效率会下降明显。因为每个桶并不是单独一条链表，而且通过一个索引共享一条链表，如果空桶过多时，会有很多桶指向同一节点，将这个节点删除时，需要将所有指向该节点的桶全部更新。由于历史以及和其他组件结合等原因，在我的项目中，更换STL库或者更改STL代码几乎不太可能了。明白了效率低的具体原因之后，我们将可以规避掉这个做法，不要在循环中频繁遍历删除节点，导致空桶过多。