gold_hash_map vs google sparse map by google’s time_hash_map.cc

作者: 发表日期: 2011年10月29日 分类: C++, HashTable 评论: 1 条 阅读次数: 5,351 次

这个列表由我写的一个 perl 程序抓取 time_hash_map 的结果生成。time_hash_map 是 google 自己实现的 hash table 中的一个性能测试程序，我在其中加入了针对 gold_hash_map 的测试，没有其它任何改动。实现原理：缓存与平行数组在……

operation(byte=4) gold_hash_map DENSE
HASH_MAP		 SPARSE
HASH_MAP		 STANDARD
HASH_MAP		 STANDARD
MAP
time:fetch_empty 54.5 70 865.5 234 187
copy:fetch_empty 0 35 1 0 0
hash:fetch_empty 2000000 0 0 2000000 0
time:fetch_random 171.5 257.5 1217 366.5 741
copy:fetch_random 4000000 18485851 11355478 4000000 4000000
hash:fetch_random 4000000 6097153 7355426 7198374 0
time:fetch_sequential 140.5 265 1232 327.5 686.5
copy:fetch_sequential 4000000 18485851 11355478 4000000 4000000
hash:fetch_sequential 4000000 6097153 7355426 7198374 0
time:grow 327.5 702 3112 1981 1310.5
copy:grow 4000000 18485851 11355478 4000000 4000000
hash:grow 2000000 4097153 5355426 5198374 0
time:predict/grow 312 304 1201.5 1973.5 1349.5
copy:predict/grow 4000000 12194347 8000005 4000000 4000000
hash:predict/grow 2000000 2000000 2000000 5198374 0
time:remove 226.5 358.5 1490 2886 1474
copy:remove 4000000 20485851 13355478 4000000 4000000
hash:remove 4000000 6097153 7355426 9198373 0
time:replace 164 210.5 499.5 327.5 639.5
copy:replace 6000000 18485851 11355478 4000000 4000000
hash:replace 4000000 6097153 7355426 7198374 0
time:toggle 218 827 2816 2675.5 827
copy:toggle 4000000 14999435 10319829 4000000 4000000
hash:toggle 4000000 4124985 4079957 6000000 0
ztress:1024:1 126.1 2247.3 3964.3 1156.7
ztress:1024:1024 156.1 2685.5 8116.7 33527.3
ztress:256:1 188 1156.1 2528.2 1124.1
ztress:256:256 156 840.1 2746.2 9078.6
operation(byte=8) gold_hash_map DENSE
HASH_MAP		 SPARSE
HASH_MAP		 STANDARD
HASH_MAP		 STANDARD
MAP
time:fetch_empty 94 78 936 265 203
copy:fetch_empty 0 35 1 0 0
hash:fetch_empty 1000000 0 0 1000000 0
time:fetch_random 188 281 1310 562 764
copy:fetch_random 2000000 9242963 5677753 2000000 2000000
hash:fetch_random 2000000 3048576 3677704 3149797 0
time:fetch_sequential 171 281 1248 452 655
copy:fetch_sequential 2000000 9242963 5677753 2000000 2000000
hash:fetch_sequential 2000000 3048576 3677704 3149797 0
time:grow 359 874 3120 1404 1310
copy:grow 2000000 9242963 5677753 2000000 2000000
hash:grow 1000000 2048576 2677704 2149797 0
time:predict/grow 327 359 1248 1451 1310
copy:predict/grow 2000000 6097195 4000005 2000000 2000000
hash:predict/grow 1000000 1000000 1000000 2149797 0
time:remove 234 406 1591 1279 1435
copy:remove 2000000 10242963 6677753 2000000 2000000
hash:remove 2000000 3048576 3677704 4149796 0
time:replace 203 234 499 452 608
copy:replace 3000000 9242963 5677753 2000000 2000000
hash:replace 2000000 3048576 3677704 3149797 0
time:toggle 265 967 3011 2761 889
copy:toggle 2000000 7497755 5159741 2000000 2000000
hash:toggle 2000000 2062443 2039935 3000000 0
ztress:1024:1 124.1 2313.3 3994.3 1184.7
ztress:1024:1024 188.1 2809.6 8364.8 33779.5
ztress:256:1 188.1 1252.7 2557.5 1064.6
ztress:256:256 188.1 932.5 2873.7 9053.2
operation(byte=16) gold_hash_map DENSE
HASH_MAP		 SPARSE
HASH_MAP		 STANDARD
HASH_MAP		 STANDARD
MAP
time:fetch_empty 124 92 906 282 218
copy:fetch_empty 0 35 1 0 0
hash:fetch_empty 500000 0 0 500000 0
time:fetch_random 218 280 1280 468 780
copy:fetch_random 1000000 4621515 2838889 1000000 1000000
hash:fetch_random 1000000 1524287 1838843 1649797 0
time:fetch_sequential 188 312 1280 404 656
copy:fetch_sequential 1000000 4621515 2838889 1000000 1000000
hash:fetch_sequential 1000000 1524287 1838843 1649797 0
time:grow 406 906 3308 1654 1342
copy:grow 1000000 4621515 2838889 1000000 1000000
hash:grow 500000 1024287 1338843 1149797 0
time:predict/grow 374 376 1340 2028 1372
copy:predict/grow 1000000 3048619 2000005 1000000 1000000
hash:predict/grow 500000 500000 500000 1149797 0
time:remove 250 406 1496 1686 1436
copy:remove 1000000 5121515 3338889 1000000 1000000
hash:remove 1000000 1524287 1838843 2149796 0
time:replace 250 248 532 406 562
copy:replace 1500000 4621515 2838889 1000000 1000000
hash:replace 1000000 1524287 1838843 1649797 0
time:toggle 342 1028 3026 2900 936
copy:toggle 1000000 3747115 2579433 1000000 1000000
hash:toggle 1000000 1031177 1019858 1500000 0
operation(byte=256) gold_hash_map DENSE
HASH_MAP		 SPARSE
HASH_MAP		 STANDARD
HASH_MAP		 STANDARD
MAP
time:fetch_empty 992 0 1008 1248 240
copy:fetch_empty 0 35 1 0 0
hash:fetch_empty 62500 0 0 62500 0
time:fetch_random 992 1248 2240 1488 1008
copy:fetch_random 62500 577731 354875 125000 125000
hash:fetch_random 125000 190532 229838 206224 0
time:fetch_sequential 1248 992 2496 1248 752
copy:fetch_sequential 62500 577731 354875 125000 125000
hash:fetch_sequential 125000 190532 229838 206224 0
time:grow 1504 3488 7232 3744 1504
copy:grow 62500 577731 354875 125000 125000
hash:grow 62500 128032 167338 143724 0
time:predict/grow 1504 1488 2992 3984 1504
copy:predict/grow 62500 381115 250005 125000 125000
hash:predict/grow 62500 62500 62500 143724 0
time:remove 992 1248 2496 3488 1760
copy:remove 62500 640231 417375 125000 125000
hash:remove 125000 190532 229838 268723 0
time:replace 1008 992 1248 1504 496
copy:replace 62500 577731 354875 125000 125000
hash:replace 125000 190532 229838 206224 0
time:toggle 2000 3008 5744 5488 992
copy:toggle 62500 466655 322033 125000 125000
hash:toggle 125000 128853 127383 187500 0
作者:
该日志由 csdn-whinah 于2011年10月29日发表在C++, HashTable分类下， 你可以发表评论，并在保留原文地址及作者的情况下引用到你的网站或博客。
转载请注明: gold_hash_map vs google sparse map by google’s time_hash_map.cc
标签:
【上一篇】
【下一篇】

您可能感兴趣的文章:

1 个回复

  1. whinah说道：
    2011年11月27日 下午9:40

    gold_hash_map 的几乎所有测试项目都比其它所有map 快，除了fetch_empty 明显比 dense_hash_map 慢。
    于是认真探了一下究竟，dense_hash_map::find 的有效代码在最开始判断了一下自己是否是空 map，如果是空，就直接返回 end()，其它啥事都不干。而其它 hash_map 总是要计算 key 的 hash value，gold_hash_map 也一样。
    但是，查找空 map 不是一个 normal case，我不会仅仅为评测数据取胜，就给 gold_hash_map 加上这样的判断。

发表评论

您必须 登录 后才能发表评论。