KeyWords: STLPort hash_map hash_multimap erase操作慢
本文使用的STL版本是STLPort5.2.1的最新release版本，配合G++4.5版本使用掩宜。我在項(xiàng)目中發(fā)現(xiàn)一個(gè)性能的瓶頸蔫骂，最終定位到的原因是使用STLPort的hash_multimap(C++11之后哈希表改為unordered_map和unordered_multimap)中erase函數(shù)消耗時(shí)間長(zhǎng)導(dǎo)致的。STLPort目前已經(jīng)基本不怎么更新了锭亏，C++新標(biāo)準(zhǔn)C++11/14/17基本是不支持了纠吴。對(duì)比了STL的其他版本，G++4.5自帶的版本和G++7.2自帶的版本發(fā)現(xiàn)慧瘤，STLPort的erase操作和G++自帶的STL unordered_multimap::erase 有200倍的執(zhí)行時(shí)間的差距戴已。
測(cè)試的方法是使用了20W節(jié)點(diǎn)的哈希表，然后在循環(huán)中遍歷刪除每一個(gè)節(jié)點(diǎn)锅减。G++自帶STL庫糖儡，開啟了O3優(yōu)化，在i7 6700K的平臺(tái)上面執(zhí)行時(shí)間大約只有0.02S怔匣，而STLPort的執(zhí)行時(shí)間有4S之多握联。
說個(gè)題外話桦沉，如果使用STLPort5.2.1版本的哈希表的話，最好自己打一個(gè)patch金闽。這個(gè)版本的哈希表存在一個(gè)BUG纯露，在刪除節(jié)點(diǎn)時(shí)，會(huì)減少哈希表的桶的數(shù)量代芜，有些情況會(huì)rehash埠褪，造成迭代器的失效。在循環(huán)中刪除哈希表的迭代器節(jié)點(diǎn)挤庇，有可能得到和預(yù)期不一致的結(jié)果钞速。BUG的地址：https://sourceforge.net/p/stlport/bugs/148/
STLPort hash_multimap數(shù)據(jù)結(jié)構(gòu)
STLPort哈希表底層使用的數(shù)據(jù)結(jié)構(gòu)是slist(C++11中為forward_list)，是一種單向鏈表的結(jié)構(gòu)嫡秕。所有哈希表的節(jié)點(diǎn)都保存在這個(gè)鏈?zhǔn)降慕Y(jié)構(gòu)上渴语，哈希表的桶使用vector<_Slist_node_base*> _BucketVector來表示，桶的每一個(gè)節(jié)點(diǎn)保存了slist類型的基類指針昆咽。該指針指向了桶內(nèi)第一個(gè)元素在slist中的位置驾凶。所以這個(gè)桶是一個(gè)邏輯的概念，只是一個(gè)類似于游標(biāo)或者迭代器的東西潮改，并沒有在原始的數(shù)據(jù)結(jié)構(gòu)中單獨(dú)拿出一條鏈表來保存桶狭郑。獲取桶內(nèi)元素(假設(shè)第n個(gè)桶)的方式就是使用_BucketVector[n],_BucketVector[n + 1]確定slist中桶內(nèi)元素的首尾指針，這兩個(gè)指針類似于begin(),end()迭代器的概念汇在。然后遍歷該區(qū)間就可以找到桶內(nèi)的所有元素翰萨。下圖是一個(gè)哈希表的示意圖。
通過Key來查找的過程糕殉，首先需要將Key轉(zhuǎn)換為桶的索引亩鬼，知道數(shù)據(jù)位于哪個(gè)桶內(nèi)。轉(zhuǎn)換的過程是hash(Key)%bucket_count()阿蝶，先用哈希函數(shù)算出Key的哈希值雳锋，然后模上桶的數(shù)量得到桶的索引(桶的數(shù)量一般是一個(gè)素?cái)?shù)，在STLPort中也保存了一張素?cái)?shù)表來決定桶需要分配的大小)羡洁。得到桶的索引后玷过，就執(zhí)行上面一段講到的內(nèi)容，通過首尾指針遍歷桶內(nèi)元素筑煮，然后比較桶內(nèi)元素的Key和查找元素的Key是否相等辛蚊，返回第一個(gè)相等的元素。
hash_map和hash_multimap其實(shí)并沒有太多區(qū)別真仲，都是對(duì)STLPort底層數(shù)據(jù)結(jié)構(gòu)hashtable的封裝袋马，區(qū)別只是插入元素時(shí)，使用insert_unique函數(shù)還是insert_equal函數(shù)而已秸应。
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節(jié)點(diǎn)指向桶__n的第一個(gè)元素
size_type __erased = 0; //刪除節(jié)點(diǎn)的個(gè)數(shù)
if (__cur == __it._M_ite) { //如果刪除的節(jié)點(diǎn)是桶內(nèi)第一個(gè)元素
size_type __prev_b = __n;
_ElemsIte __prev = _M_before_begin(__prev_b)._M_ite; //獲取__n桶的前一個(gè)節(jié)點(diǎn)虑凛，__prev_b返回第一個(gè)和__n桶指向同一節(jié)點(diǎn)的索引碑宴，這里具體后面解釋
fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1,
_M_elems.erase_after(__prev)._M_node);//將該節(jié)點(diǎn)刪除，并且將所有指向該節(jié)點(diǎn)的桶桑谍，更新指向的節(jié)點(diǎn)延柠。后面具體解釋
++__erased;//增加刪除節(jié)點(diǎn)計(jì)數(shù)
}
else { //刪除的節(jié)點(diǎn)不是桶內(nèi)第一個(gè)元素
/* 遍歷__n桶，刪除與入?yún)_it相同的節(jié)點(diǎn)锣披，這部分比較好理解捕仔，也沒什么毛病 */
_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; //哈希節(jié)點(diǎn)計(jì)數(shù)更新
}
上面是STLPort的erase迭代器的過程，有兩個(gè)分支盈罐，刪除節(jié)點(diǎn)如果不是桶的首節(jié)點(diǎn)的話比較容易，直接找到要?jiǎng)h除的節(jié)點(diǎn)刪掉就好了闪唆。復(fù)雜的是要?jiǎng)h除的節(jié)點(diǎn)是桶的首節(jié)點(diǎn)盅粪，需要找到該節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，并且要更新桶的首指針的指向悄蕾，具體內(nèi)容已經(jīng)在注釋中寫出了票顾。經(jīng)過分析和加入調(diào)試信息打印，耗時(shí)的根源在查找待刪除節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)這個(gè)函數(shù)上帆调，_M_before_begin奠骄。
讓我們一起看一下這個(gè)函數(shù)的代碼。
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); //實(shí)際的執(zhí)行函數(shù)是_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標(biāo)記
typename _BucketVector::const_iterator __bpos(__buckets.begin() + __n);//指向__n桶的迭代器番刊，這個(gè)迭代器是vector存儲(chǔ)的桶的迭代器
_ElemsIte __pos(*__bpos);//__n桶首元素指向的slist節(jié)點(diǎn)的迭代器含鳞，該迭代器是指向哈希表slist鏈表的
if (__pos == __mutable_elems.begin()) {//該函數(shù)就是如果刪除的元素是整個(gè)slist的首節(jié)點(diǎn)，就把slist的首節(jié)點(diǎn)之前的虛擬節(jié)點(diǎn)返回芹务。因?yàn)閟list是單鏈表蝉绷，只有erase_after操作，如果要?jiǎng)h除鏈表節(jié)點(diǎn)枣抱，必須找到前面的元素熔吗。
__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桶首元素的指針佳晶。該類型和桶內(nèi)存儲(chǔ)的指針是同一類型桅狠。
for (--__bcur; __pos_node == *__bcur; --__bcur);//向前遍歷桶，找到第一個(gè)和桶指向不同元素的節(jié)點(diǎn)轿秧。為什么這樣做中跌，下面講。這里是耗時(shí)的根源
__n = __bcur - __buckets.begin() + 1;//更新入?yún)_n的位置淤刃，返回與__n桶指向同一slist節(jié)點(diǎn)的第一個(gè)桶的索引晒他。
_ElemsIte __cur(*__bcur);//后面的過程就是從找到的前一個(gè)桶的指針開始往回遍歷，找到待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)逸贾。
_ElemsIte __prev = __cur++;
for (; __cur != __pos; ++__prev, ++__cur);
return __prev;
}
上面這部分代碼主要是找到待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)陨仅，但是為什么這么復(fù)雜津滞，而且在我的項(xiàng)目中執(zhí)行這么慢呢？最后在for (--__bcur; __pos_node == *__bcur; --__bcur);這一行代碼中加了一個(gè)計(jì)數(shù)發(fā)現(xiàn)灼伤，在哈希節(jié)點(diǎn)20W時(shí)触徐，循環(huán)刪除迭代器，在刪除到后面的節(jié)點(diǎn)時(shí)狐赡，該循環(huán)每次刪除要執(zhí)行5W次以上撞鹉。最后考慮了一下發(fā)現(xiàn)這樣做的原因是，因?yàn)橛锌赡芘R近的很多桶中沒有任何元素颖侄，所以這些臨近的桶都指向了一個(gè)節(jié)點(diǎn)鸟雏。如下圖所示，是一種多個(gè)桶中沒有元素指向同一節(jié)點(diǎn)的狀態(tài)览祖。
上圖中孝鹊，1-39999桶都沒有元素，如果本次刪除第40000桶的節(jié)點(diǎn)時(shí)展蒂，for (--__bcur; __pos_node == *__bcur; --__bcur);該循環(huán)__bcur節(jié)點(diǎn)要循環(huán)40000次左右查找又活，才能找到桶0的位置，也就是第一個(gè)與40000桶指向不同元素的桶锰悼。所以這種情況下再使用erase操作柳骄，性能會(huì)極具下降。
為什么要找到桶1并且返回呢箕般？因?yàn)槿绻麑_pos所指向的slist節(jié)點(diǎn)刪除掉了耐薯，1--40000桶的指針全部都失效了，所以要找到第一個(gè)和40000桶相同指向的桶隘世，然后把1號(hào)索引也返回可柿。
fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1,_M_elems.erase_after(__prev)._M_node);
這句代碼就是把1號(hào)到40000號(hào)桶的指向全部更新為__pos的下一個(gè)節(jié)點(diǎn)忆畅。
總結(jié)
STLPort的哈希表設(shè)計(jì)決定了如果哈希表過大時(shí)馏予，而且存在很多空桶的情況下，刪除效率會(huì)下降明顯澄步。因?yàn)槊總€(gè)桶并不是單獨(dú)一條鏈表械媒，而且通過一個(gè)索引共享一條鏈表目锭，如果空桶過多時(shí)，會(huì)有很多桶指向同一節(jié)點(diǎn)纷捞，將這個(gè)節(jié)點(diǎn)刪除時(shí)痢虹，需要將所有指向該節(jié)點(diǎn)的桶全部更新。由于歷史以及和其他組件結(jié)合等原因主儡，在我的項(xiàng)目中奖唯，更換STL庫或者更改STL代碼幾乎不太可能了。明白了效率低的具體原因之后糜值，我們將可以規(guī)避掉這個(gè)做法丰捷，不要在循環(huán)中頻繁遍歷刪除節(jié)點(diǎn)坯墨，導(dǎo)致空桶過多。
