ServerFrame::HashMap VS stl::unordered_map-性能探究之旅

作者:池育龙

1. 引言

突然就对项目中的HashMap有了强烈的好奇心,这个HashMap的实现够高效吗,和 std::unordered_map 的效率比较性能如何? 他们的插入效率、查找效率、空间使用率对比起来是分别是什么样的?也没有找到相关的测评,于是就自己动手,测试了一下,并对一些影响性能的地方修改、验证自己的猜想,最终得到一个比较好的hashmap的实践。整个过程还是比较有意思的,现记录并分享出来。

1.1 好了别的不说了给我结论就好

好吧,大家都很忙,先给一下简要结论,时间紧迫的同学也可以直接跳到文尾查看结论小节.

  1. ServerFrame::HashMap 的哈希算法算出来的哈希值散列度不够,key的长度越长,散列能力越差,性能越差。
  2. 因为冲突处理的缘故,本文所做的几个用例中,极端情况下 ServerFrame::HashMap 的表现比 stl::unordered_map 差100倍;
  3. 哈希算法散列程度足够的时候,ServerFrame::HashMap 的表现比 stl::unordered_map 好。前者的插入效率是后者的10倍,查找效率3倍;
  4. 存储同样的数据,HashMap 耗内存多于 unordered_map;

1.2 show me the code

本文用到的测试代码和测试结果全部在 git.oa.com中,有兴趣的同学可以下载查看。

仓库路径:http://git.code.oa.com/lawrencechi/hashmap-benchmark.git
成文时仓库版本 tag:v2.0
内存: 12G
cpu 2核:   i7-6700 CPU 3.40GHz
ServerFrame::HashMap: 编译时预设的容量是 8000万

测试用例:
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

项目

说明

key

int,递增: 0~7000万

value

value==key

用例1

分别顺序插入8000万条数据,每10万条记录一次耗时

用例2

搜索部分存在的key,获得每次检索的耗时

用例3

搜索不存在的key,获得每次检索的耗时

2.1用例结果

执行./bm_hashmap.O2 -n 700 -hj,获得数据,并绘制图表如下(画图数据经过省略,但关键信息还在,下同)

[图: 2.1插入耗时 ]

[ 图:2.1查找耗时 ]

总体来看,两个实现的效率都很高,稳定(斜率不变,意味着单位时间内插入条数没有变化),插入8000万条数据最多只需要4.5s, 在使用 ServerFrame::HashMap插入数据的时候,HashMap甚至能够达到 stl::unordered_map的10倍;当key不存在的时候,HashMap 查找速度也比 unordered_map 快4倍, key 存在的时候,容量少于5000万条时,HashMap 比 unordered_map 快,只有大于5000万时,两者查找的速度才相差不大。

这次测试看起来 HashMap 实现得非常完美,很好地解决了预设需求,插入效率高、查找效率高。虽然耗费的内存多,仅存8000万个int的 HashMap 需要 3.5G 的内存,但现代服务器内存充足,这个缺点似乎是可以忍受的。

除了内存之外,ServerFrame::HashMap 的实现就没有其他的缺点了吗? 很快,我就想到了他的 Hash 函数和冲突处理,决定从这里入手继续分析。

2.2 隐忧:hash算法

ServerFrame::HashMap 的 hash 算法实现是将 key 的 buffer(sizeof(key)),按照 int 字节累加,并将其结果和哈希表容量进行取余,简单粗暴,而且似乎也符合大道至简的理论。但是仔细想想,这个地方的实现违背了哈希算法的原则:均衡性。一个不够均衡性的算法会导致大量冲突,最终使得HashMap在反复的冲突处理中疲于奔命。

很简单,按照这个算法下面的这些数据算得到的哈希值都是一样的,而且这样的数据可以轻易地构造:

0xFFFFFFFF,
0xFFFFFFFF 00000000
0xFFFFFFFF 00000000 00000000
0xFFFFFFFF 00000000 00000000 00000000

最为对比,我们都知道构造两个拥有同样MD5值的数据是何等的困难。

而且仔细分析一下可以知道 2.1 用例刚好绕过了这个算法的缺陷,取到的key都不会相互冲突! 这时候的测试结果恰恰是最优结果!

如果冲突了会怎么样,测试结果变成怎么样? 在好奇心驱使下,我马上进行 3.1 用例的测试。

3. buffer(32byte)类型

项目

说明

key

int,递增: 0~7000万,buffer:snprintf(key,sizeof(key),”%d”,++i);

value

int,value==i

用例2

分别顺序插入7000万条数据,每10万条记录一次耗时

3.1用例结果

执行./bm_hashmap.O2 -n 700 -ik,获得数据,并绘制图表如下

[图: 3.1插入耗时 ]

从上图可以看到,对于buffer类型的key,性能表现差异很大.

从HashMap的图来看,越到后面斜率越大,说明到后面的时候,插入单位条数的耗时已经急剧增长。这是符合我们的设想的,此时程序在拼命进行冲突处理

从图中还可以得到一个信息,插入7000万条数据,HashMap的耗时是接近2500秒,也就是41分钟!

至于unordered_map,上图已经分析不出什么东西来,和HashMap比起来,它的变化太缓慢了。我只能抽出来单独分析,图如下:

[ [图:3.1插入耗时-unordered_map ]

unordered_map 斜率几乎不变,可以知道每次插入的耗时是相同的,稳定,插入7000万条数据,耗时25s,HashMap差不多是他的100倍。

从上面的测试结果可知 HashMap 的效率的确是急剧下降,但是这个急剧下降是 Hash 算法引起的吗? 还是需要定量分析!

4. hash 算法比较

4.1 unordered_map

stl::unordered_map 是C++11引进的,老版本也有,只是没有提供接口出来供外部使用。

恰好手头上有 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;
    }

对于可以转换成 size_t 类型的key,hash提供了几个特化哈希函数,直接返回((size_t)key),上面的哈希函数是buffer类型的哈希函数,传入起始地址,得到哈希值。这个hash算法用了几个魔数,各种位运算得到一个 int32 的值,好吧,此时我已经不知道怎么才能构造两个碰撞数据了。

最为对比,HashMap的hash函数如下:

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算法实现比较简单只是将Key值的每个字节的值加起来并对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 用例设计

项目

说明

key

int,递增: 0~7000万,buffer:snprintf(key,sizeof(key),”%d”,++i);

用例1

分别用两个hash函数计算上面的7000万个key的哈希值,并统计碰撞次数的数量

4.3 用例结果

执行./bm_hashmap.O2 -n 700 -lm,获得数据,并绘制图表如下 碰撞太频繁了,为了可读性,这里对原始数据做了二次统计。统计每一个冲突链表的长度,以及key数量和占比。key数量之和是 7000万,占比之和是100%。

冲突处理链表长度

key数量

占比

1

12496

0.018%

2-10

185424

0.265%

11-100

3457040

4.939%

100-1000

31699008

45.284%

1000-2000

18560208

26.515%

2000-3000

9751504

13.931%

3000-4000

4203600

6.005%

4000-5000

1637120

2.339%

5000以上

493600

0.705%

这个表格就一目了然了:

  • 我们最期望的结果是没有冲突,也就是链表长度为1,仅占比0.265%!
  • 绝大部分的冲突链表长度在100以上, 占了总量的 95%.
  • 最长的链表达到了 5000以上,而且占比 有 0.705%,比我们期望的不冲突的占比还多了3倍。也就是说最差情况的比最好情况多了3倍。

作为对比,stl::unordered_map 的结果就好看很多了,甚至都不需要进行二次统计、处理:

冲突处理链表长度

key数量

占比

1

68867795

98.383%

2

1123058

1.604%

3

9099

0.013%

4

48

那么,猜想一下,如果替换掉 ServerFrame::HashMap 的哈希算法,是不是测试的效果就会好很多呢?

5. 升级HashMap hash算法之后测试

开搞,把gcc4.9.3的哈希算法移植到 ServerFrame::HashMap,并放到一个新命名空间中,另存为文件 HashMapPlush.hpp。 重做3.1的测试用例 ./bm_hashmap.O2 -n 700 -lm,获得数据,并绘制图表如下

冲突处理链表长度

key数量

占比

1

29174797

41.6783%

2

25536674

36.4810%

3

11171340

15.9591%

4

3256948

4.6528%

5

715185

1.0217%

6

124962

0.1785%

7

17703

0.0253%

8

2152

0.0031%

9

189

0.0003%

10

50

0.0001%

可见升级哈希算法之后,冲突还是存在,但是冲突链表过长的现象已经不存在了,最长的冲突链表长度也只有10。此时可以想象耗时数据肯定好了很多。

[ 图:5.1插入耗时 ]

可见,调整较小,但是效果比较明显

  • ServerFrame::HashMap 的插入耗时是 unordered_map 的 1/2;
  • ServerFrame::HashMap 斜率很稳,可见插入耗时比较稳定

6. 结论

从上面的实验可以看出,影响 HashMap 效率的主要是 哈希算法 和 内存分配算法,在哈希算法足够散列的情况下,预分配方式的效率更高。

空间换时间的策略是对的,两个影响因素,另个不够好的时候,靠空间得到的优势反而会损失;

原创声明,本文系作者授权云+社区-专栏发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏听雨堂

从MapX到MapXtreme2004[6]-标点心得

在Web上标点,首先要将图层所在文件夹的写权限放开。如果是普通的标点,可以这样:    MapInfo.Data.Table tb=MapInfo.Engine...

1858
来自专栏听雨堂

Pandas对行情数据的预处理

库里是过去抓取的行情数据,间隔6秒,每分钟8-10个数据不等,还有开盘前后的一些数据,用Pandas可以更加优雅地进行处理。 ? 需要把当前时间设置为index...

19010
来自专栏嵌入式程序猿

mscan VS flexcan

在嵌入式程序猿的公众号里,曾多次介绍过NXP的flexcan以及基于flexcan的一些其他协议和开发,最近在用NXP的另外一款片子,使用的是mscan,这两种...

3429
来自专栏专知

【干货】TensorFlow中那些鲜为人知却又极其实用的知识

TensorFlow的生态圈极其强大,覆盖了科研、工程中的各种流程,其中一些特别好用的模块和技巧可以使你的工作效率大幅度提升,也可以让你的产品变得非常稳定。本文...

880
来自专栏斑斓

编码 | 并非Null Object这么简单

在大多数程序语言中,我们都需要与Null打交道,并且纠缠于对它的检查中。一不小心让它给溜出来,就可能像打开潘多拉的盒子一般,给程序世界带来灾难。说起来,在我们人...

3327
来自专栏软件开发 -- 分享 互助 成长

组合模式

一、简介 1、组合模式将对象组合成树形结构以表示‘部分和整体’的层次结构。组合模式使得用户对单个对象和组合对象的使用具有一致性。 2、模式中的几个重要的类 Co...

1807
来自专栏Aloys的开发之路

OOAD与UML笔记

UML基础介绍 1.UML的定义 统一建模语言(UML)是一种图形化的语言,它可以帮助我们在OOAD过程中标识元素、构建模块、分析过程并可通过文档说明系统中的重...

1778
来自专栏飞雪无情的博客

Go语言实战笔记(二十二)| Go 基准测试

基准测试,是一种测试代码性能的方法,比如你有多种不同的方案,都可以解决问题,那么到底是那种方案性能更好呢?这时候基准测试就派上用场了。

813
来自专栏高性能服务器开发

libevent源码深度剖析一 序

(1)libevent源码深度剖析一 序 (2)libevent源码深度剖析二 Reactor模式 (3)libevent源码深度剖析三 libevent基本使...

1163
来自专栏Golang语言社区

【go语言】Goroutines 并发模式(一)

摘要 这一篇主要是对GO语言中的并发编程模式做一个粗略的归纳总结,文中示例参考自golang conference中的一些演讲和博客,go涉及到的Go语言的语法...

3126

扫码关注云+社区