ServerFrame::HashMap VS stl::unordered_map-性能探究之旅
1. 引言
突然就對(duì)項(xiàng)目中的HashMap有了強(qiáng)烈的好奇心，這個(gè)HashMap的實(shí)現(xiàn)夠高效嗎，和 std::unordered_map 的效率比較性能如何? 他們的插入效率、查找效率、空間使用率對(duì)比起來(lái)是分別是什么樣的?也沒(méi)有找到相關(guān)的測(cè)評(píng)，于是就自己動(dòng)手，測(cè)試了一下，并對(duì)一些影響性能的地方修改、驗(yàn)證自己的猜想，最終得到一個(gè)比較好的hashmap的實(shí)踐。整個(gè)過(guò)程還是比較有意思的，現(xiàn)記錄并分享出來(lái)。
1.1 好了別的不說(shuō)了給我結(jié)論就好
好吧，大家都很忙，先給一下簡(jiǎn)要結(jié)論，時(shí)間緊迫的同學(xué)也可以直接跳到文尾查看結(jié)論小節(jié).
- ServerFrame::HashMap 的哈希算法算出來(lái)的哈希值散列度不夠，key的長(zhǎng)度越長(zhǎng)，散列能力越差，性能越差。
- 因?yàn)闆_突處理的緣故，本文所做的幾個(gè)用例中，極端情況下 ServerFrame::HashMap 的表現(xiàn)比 stl::unordered_map 差100倍;
- 哈希算法散列程度足夠的時(shí)候，ServerFrame::HashMap 的表現(xiàn)比 stl::unordered_map 好。前者的插入效率是后者的10倍，查找效率3倍;
- 存儲(chǔ)同樣的數(shù)據(jù),HashMap 耗內(nèi)存多于 unordered_map;
1.2 show me the code
本文用到的測(cè)試代碼和測(cè)試結(jié)果全部在 git.oa.com中，有興趣的同學(xué)可以下載查看。
- 倉(cāng)庫(kù)路徑:http://git.code.oa.com/lawrencechi/hashmap-benchmark.git
- 成文時(shí)倉(cāng)庫(kù)版本 tag:v2.0
- 內(nèi)存: 12G
- cpu 2核: i7-6700 CPU 3.40GHz
- ServerFrame::HashMap: 編譯時(shí)預(yù)設(shè)的容量是 8000萬(wàn)
- 測(cè)試用例:
- lawrencechi@lawrencechi-VirtualBox /data/hashmap-benchmark/hashmap-benchmark/build ±master:zap: » ./bm_hashmap.O2
- Usage: bm_hashmap.O2 [-n count] -hijklmop
- -h: hashmap-int
- -i: hashmap-string(32 byte)
- -j: unordered-map-int
- -k: unordered-map-string
- -l: hashmap(32 byte)) idx
- -m: hash<string> idx
- -o: hashmapplus(32 byte)) idx
- -p: hashmapplus-string(32 byte))
2.int類型key
2.1用例結(jié)果
執(zhí)行./bm_hashmap.O2 -n 700 -hj,獲得數(shù)據(jù)，并繪制圖表如下(畫圖數(shù)據(jù)經(jīng)過(guò)省略，但關(guān)鍵信息還在,下同)
[圖: 2.1插入耗時(shí) ]
[ 圖:2.1查找耗時(shí) ]
總體來(lái)看，兩個(gè)實(shí)現(xiàn)的效率都很高，穩(wěn)定(斜率不變，意味著單位時(shí)間內(nèi)插入條數(shù)沒(méi)有變化)，插入8000萬(wàn)條數(shù)據(jù)最多只需要4.5s， 在使用 ServerFrame::HashMap插入數(shù)據(jù)的時(shí)候，HashMap甚至能夠達(dá)到 stl::unordered_map的10倍;當(dāng)key不存在的時(shí)候，HashMap 查找速度也比 unordered_map 快4倍， key 存在的時(shí)候，容量少于5000萬(wàn)條時(shí)，HashMap 比 unordered_map 快，只有大于5000萬(wàn)時(shí)，兩者查找的速度才相差不大。
這次測(cè)試看起來(lái) HashMap 實(shí)現(xiàn)得非常完美，很好地解決了預(yù)設(shè)需求，插入效率高、查找效率高。雖然耗費(fèi)的內(nèi)存多，僅存8000萬(wàn)個(gè)int的 HashMap 需要 3.5G 的內(nèi)存，但現(xiàn)代服務(wù)器內(nèi)存充足，這個(gè)缺點(diǎn)似乎是可以忍受的。
除了內(nèi)存之外，ServerFrame::HashMap 的實(shí)現(xiàn)就沒(méi)有其他的缺點(diǎn)了嗎? 很快，我就想到了他的 Hash 函數(shù)和沖突處理，決定從這里入手繼續(xù)分析。
2.2 隱憂:hash算法
ServerFrame::HashMap 的 hash 算法實(shí)現(xiàn)是將 key 的 buffer(sizeof(key))，按照 int 字節(jié)累加，并將其結(jié)果和哈希表容量進(jìn)行取余，簡(jiǎn)單粗暴，而且似乎也符合大道至簡(jiǎn)的理論。但是仔細(xì)想想,這個(gè)地方的實(shí)現(xiàn)違背了哈希算法的原則:均衡性。一個(gè)不夠均衡性的算法會(huì)導(dǎo)致大量沖突，最終使得HashMap在反復(fù)的沖突處理中疲于奔命。
很簡(jiǎn)單，按照這個(gè)算法下面的這些數(shù)據(jù)算得到的哈希值都是一樣的,而且這樣的數(shù)據(jù)可以輕易地構(gòu)造:
- 0xFFFFFFFF,
- 0xFFFFFFFF 00000000
- 0xFFFFFFFF 00000000 00000000
- 0xFFFFFFFF 00000000 00000000 00000000
最為對(duì)比，我們都知道構(gòu)造兩個(gè)擁有同樣MD5值的數(shù)據(jù)是何等的困難。
而且仔細(xì)分析一下可以知道 2.1 用例剛好繞過(guò)了這個(gè)算法的缺陷，取到的key都不會(huì)相互沖突! 這時(shí)候的測(cè)試結(jié)果恰恰是最優(yōu)結(jié)果!
如果沖突了會(huì)怎么樣,測(cè)試結(jié)果變成怎么樣? 在好奇心驅(qū)使下，我馬上進(jìn)行 3.1 用例的測(cè)試。
3. buffer(32byte)類型
3.1用例結(jié)果
執(zhí)行./bm_hashmap.O2 -n 700 -ik,獲得數(shù)據(jù)，并繪制圖表如下
[圖： 3.1插入耗時(shí) ]
從上圖可以看到，對(duì)于buffer類型的key,性能表現(xiàn)差異很大.
從HashMap的圖來(lái)看，越到后面斜率越大，說(shuō)明到后面的時(shí)候，插入單位條數(shù)的耗時(shí)已經(jīng)急劇增長(zhǎng)。這是符合我們的設(shè)想的，此時(shí)程序在拼命進(jìn)行沖突處理!
從圖中還可以得到一個(gè)信息，插入7000萬(wàn)條數(shù)據(jù)，HashMap的耗時(shí)是接近2500秒,也就是41分鐘!
至于unordered_map,上圖已經(jīng)分析不出什么東西來(lái)，和HashMap比起來(lái)，它的變化太緩慢了。我只能抽出來(lái)單獨(dú)分析，圖如下:
[ [圖：3.1插入耗時(shí)-unordered_map ]
unordered_map 斜率幾乎不變，可以知道每次插入的耗時(shí)是相同的,穩(wěn)定，插入7000萬(wàn)條數(shù)據(jù)，耗時(shí)25s，HashMap差不多是他的100倍。
從上面的測(cè)試結(jié)果可知 HashMap 的效率的確是急劇下降，但是這個(gè)急劇下降是 Hash 算法引起的嗎? 還是需要定量分析!
4. hash 算法比較
4.1 unordered_map
stl::unordered_map 是C++11引進(jìn)的,老版本也有，只是沒(méi)有提供接口出來(lái)供外部使用。
恰好手頭上有 gcc 4.9.3 的代碼，于是一探究竟
- //代碼片段 ==================
- //file:/data/study/gcc/gcc.4.9.3/gcc-4.9.3/libstdc++-v3/libsupc++/hash_bytes.cc +73
- size_t _Hash_bytes(const void* ptr, size_t len, size_t seed)
- {
- const size_t m = 0x5bd1e995;
- size_t hash = seed ^ len;
- const char* buf = static_cast<const char*>(ptr);
- // Mix 4 bytes at a time into the hash.
- while(len >= 4)
- {
- size_t k = unaligned_load(buf);
- k *= m;
- k ^= k >> 24;
- k *= m;
- hash *= m;
- hash ^= k;
- buf += 4;
- len -= 4;
- }
- // Handle the last few bytes of the input array.
- switch(len)
- {
- case 3:
- hash ^= static_cast<unsigned char>(buf[2]) << 16;
- case 2:
- hash ^= static_cast<unsigned char>(buf[1]) << 8;
- case 1:
- hash ^= static_cast<unsigned char>(buf[0]);
- hash *= m;
- };
- // Do a few final mixes of the hash.
- hash ^= hash >> 13;
- hash *= m;
- hash ^= hash >> 15;
- return hash;
- }
對(duì)于可以轉(zhuǎn)換成 size_t 類型的key，hash提供了幾個(gè)特化哈希函數(shù)，直接返回((size_t)key)，上面的哈希函數(shù)是buffer類型的哈希函數(shù)，傳入起始地址，得到哈希值。這個(gè)hash算法用了幾個(gè)魔數(shù)，各種位運(yùn)算得到一個(gè) int32 的值，好吧，此時(shí)我已經(jīng)不知道怎么才能構(gòu)造兩個(gè)碰撞數(shù)據(jù)了。
最為對(duì)比，HashMap的hash函數(shù)如下:
- template <typename KEY_TYPE, typename DATA_TYPE, int NODE_SIZE, typename CMP_FUNC, int HASH_SIZE>
- int CHashMap<KEY_TYPE, DATA_TYPE, NODE_SIZE, CMP_FUNC, HASH_SIZE>::HashKeyToIndex(const KEY_TYPE& rstKey, int& riIndex) const
- {
- size_t uiKeyLength = sizeof(rstKey);
- unsigned int uiHashSum = 0;
- //目前Hash算法實(shí)現(xiàn)比較簡(jiǎn)單只是將Key值的每個(gè)字節(jié)的值加起來(lái)并對(duì)SIZE取模
- unsigned int i;
- for( i = 0; i < uiKeyLength / sizeof(unsigned int); ++i)
- {
- unsigned int uiTmp = 0;
- memcpy(&uiTmp, ((char*)(&rstKey))+sizeof(uiTmp)*i, sizeof(uiTmp));
- uiHashSum += uiTmp;
- }
- if(uiKeyLength % sizeof(unsigned int) > 0)
- {
- unsigned char* pByte = (unsigned char*)&rstKey;
- pByte += (uiKeyLength - (uiKeyLength % sizeof(unsigned int)));
- unsigned int uiTemp = 0;
- memcpy((void *)&uiTemp, (const void *)pByte, uiKeyLength%sizeof(unsigned int));
- uiHashSum += uiTemp;
- }
- uiHashSum = (uiHashSum & ((unsigned int)0x7fffffff));
- riIndex = (int)(uiHashSum % HASH_SIZE);
- return 0;
- }
4.2 用例設(shè)計(jì)
4.3 用例結(jié)果
執(zhí)行./bm_hashmap.O2 -n 700 -lm,獲得數(shù)據(jù)，并繪制圖表如下
碰撞太頻繁了，為了可讀性，這里對(duì)原始數(shù)據(jù)做了二次統(tǒng)計(jì)。統(tǒng)計(jì)每一個(gè)沖突鏈表的長(zhǎng)度，以及key數(shù)量和占比。key數(shù)量之和是 7000萬(wàn)，占比之和是100%。
這個(gè)表格就一目了然了:
- 我們最期望的結(jié)果是沒(méi)有沖突，也就是鏈表長(zhǎng)度為1，僅占比0.265%!
- 絕大部分的沖突鏈表長(zhǎng)度在100以上, 占了總量的 95%.
- 最長(zhǎng)的鏈表達(dá)到了 5000以上，而且占比 有 0.705%，比我們期望的不沖突的占比還多了3倍。也就是說(shuō)最差情況的比最好情況多了3倍。
作為對(duì)比，stl::unordered_map 的結(jié)果就好看很多了,甚至都不需要進(jìn)行二次統(tǒng)計(jì)、處理:
那么，猜想一下，如果替換掉 ServerFrame::HashMap 的哈希算法，是不是測(cè)試的效果就會(huì)好很多呢?
5. 升級(jí)HashMap hash算法之后測(cè)試
開搞，把gcc4.9.3的哈希算法移植到 ServerFrame::HashMap,并放到一個(gè)新命名空間中，另存為文件 HashMapPlush.hpp。 重做3.1的測(cè)試用例 ./bm_hashmap.O2 -n 700 -lm,獲得數(shù)據(jù)，并繪制圖表如下
可見升級(jí)哈希算法之后,沖突還是存在，但是沖突鏈表過(guò)長(zhǎng)的現(xiàn)象已經(jīng)不存在了，最長(zhǎng)的沖突鏈表長(zhǎng)度也只有10。此時(shí)可以想象耗時(shí)數(shù)據(jù)肯定好了很多。
[ 圖：5.1插入耗時(shí) ]
可見，調(diào)整較小，但是效果比較明顯
ServerFrame::HashMap 的插入耗時(shí)是 unordered_map 的 1/2;
ServerFrame::HashMap 斜率很穩(wěn)，可見插入耗時(shí)比較穩(wěn)定
6. 結(jié)論
從上面的實(shí)驗(yàn)可以看出，影響 HashMap 效率的主要是 哈希算法 和 內(nèi)存分配算法,在哈希算法足夠散列的情況下，預(yù)分配方式的效率更高。
空間換時(shí)間的策略是對(duì)的，兩個(gè)影響因素，另個(gè)不夠好的時(shí)候，靠空間得到的優(yōu)勢(shì)反而會(huì)損失;
原文鏈接：https://www.qcloud.com/community/article/625434
【本文是51CTO專欄作者“騰訊云技術(shù)社區(qū)”的原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)通過(guò)51CTO聯(lián)系原作者獲取授權(quán)】
