上一篇文章中对go语言的map做出了分析,并且(错误地)推断go中的map实际为树。之后在golang-nuts上被人指出,我所观测到的速度降低,是由于缓存缺失(cache miss)导致。不过那个对数变化,其实我说对了(少)一半:go的map是一个hash tree,所以在元素数量变多的时候,的确会表现出一些树的特性(对数变化)。这也部分地解释了为什么我会观察到访问时间成对数增长。 这篇文章,旨在继续对其它语言,或语言标准库,或语言的准标准库中的哈希表实现进行一个性能分析。 测试方法既然之前发现是缓存命中率的原因导致哈希表访问速度不一致了,那么这回就必须要考虑到缓存命中率的问题。既然是公平比较,那么就有两个方法:
提高命中率,可以通过按照哈希表key存储的自然序列访问哈希表。这样相当于顺序访问一个数组,但每次访问key对应的value时,根据key重新计算哈希值并找出value,而不是直接取出value。 降低命中率,可以采用以下两种方法:
第一种方法是实现简单,但每次运行缓存命中率未必保持一样。不过只要随机数生成得不是太差,命中率应该会保证在一定水平之上且比较稳定。第二中方式的优点是可以最小化缓存命中率,但缺点是实现困难,而且要根据不同体系结构,缓存策略,设计不同算法。所以我只实现了第一种。至于第二种,有兴趣的朋友可以考虑一下。 这次测试分别使用了go中的map,python中的dict,C++中的unordered_map和java中的HashMap进行测试。由于代码较多且实现简单,我就不在文中贴出了。但在github上可以找到全部的完整代码。 背景知识由于涉及到缓存命中问题,有必要先普及一下缓存的一些常识。 内存平均访问时间内存平均访问时间(Average Memory Access Time, AMAT)大约可以通过以下公式计算得出: AMAT = hit time + cache miss rate * cache miss penalty
在现在的计算机体系结构下,内存速度相对cache/CPU速度非常慢,导致cache miss penalty >> hit time,所以缓存缺失率就会在很大程度上影响程序运行的效率。 缓存缺失的几种类型根据缓存缺失的原因,缓存缺失可能分别由以下几个类型:
关于缓存的详细内容,可以参考wikipedia。我不多说了。看数据吧。 顺序访问前面说了,这种访问方式的目的,是最大化缓存命中率,这样得到的结果,将会约等于一个常数,并且该常数正比于哈希表的访问时间。 先看看Go的结果: Map Seq. Access. N = 10: 0.4000000000000001 us/op Map Seq. Access. N = 100: 0.14 us/op Map Seq. Access. N = 1000: 0.12300000000000001 us/op Map Seq. Access. N = 10000: 0.119 us/op Map Seq. Access. N = 100000: 0.15627000000000002 us/op Map Seq. Access. N = 1000000: 0.17811000000000002 us/op Map Seq. Access. N = 10000000: 0.2497328 us/op刚刚一开始,由于元素数量少,使得强制缺失带来的访问延迟成为主导因素。所以访问速度比较慢。之后基本稳定在0.1x us/op上。继续增加元素,由于缓存命中率降低,访问速度则逐渐变慢。其他语言的结果也基本都呈现出这样的趋势。
下面是Python的: Dict Seq. Access. N = 10 : 4.6 us/op Dict Seq. Access. N = 100 : 0.51 us/op Dict Seq. Access. N = 1000 : 0.143 us/op Dict Seq. Access. N = 10000 : 0.1143 us/op Dict Seq. Access. N = 100000 : 0.26562 us/op Dict Seq. Access. N = 1000000 : 0.331683 us/op Dict Seq. Access. N = 10000000 : 0.3797068 us/oppython的结果比go略差,只在N=10000的时候比同级别的go强出0.005 us/op。
下面是C++的: Unordered Map Seq. Access. N = 10. 0.2 us/op. Unordered Map Seq. Access. N = 100. 0.14 us/op. Unordered Map Seq. Access. N = 1000. 0.166 us/op. Unordered Map Seq. Access. N = 10000. 0.1946 us/op. Unordered Map Seq. Access. N = 100000. 0.36684 us/op. Unordered Map Seq. Access. N = 1000000. 0.392766 us/op. Unordered Map Seq. Access. N = 10000000. 0.471303 us/op.在元素数量少的时候,基本与go持平,但随着元素数量增加,效率则不如go。
最后是Java: HashMap Seq. Access. N = 10: 8.751800 us/op. HashMap Seq. Access. N = 100: 1.613250 us/op. HashMap Seq. Access. N = 1000: 0.815325 us/op. HashMap Seq. Access. N = 10000: 1.555751 us/op. HashMap Seq. Access. N = 100000: 0.219468 us/op. HashMap Seq. Access. N = 1000000: 0.073412 us/op. HashMap Seq. Access. N = 10000000: 0.061496 us/op.与其他语言的结果不同,java的访问时间,在最后增加了一步之后,竟然逐渐下降。目前我还没有一个比较满意的解释,当前我能给出的推断是:随着元素的增多,Java虚拟机有了足够的时间学习到了循环的行为(这毕竟是个非常简单的循环),由此通过乱序执行,提高了缓存命中率,并最终提高了效率。是否通过乱序执行我不知道,但我个人感觉应该是和java虚拟机脱不开干系的。否则也确实解释不了这个现象。之后的随机访问结果,也出现了类似现象。
最后总结一下,在顺序访问中,Go的表现还算令人满意,访问时间还算维持在一个常数上下。参见下图。 随机访问还是继续,先看Go的: Map Random Access. N = 10: 0.3 us/op Map Random Access. N = 100: 0.11000000000000001 us/op Map Random Access. N = 1000: 0.087 us/op Map Random Access. N = 10000: 0.1141 us/op Map Random Access. N = 100000: 0.38335 us/op Map Random Access. N = 1000000: 0.535501 us/op Map Random Access. N = 10000000: 0.6896599 us/op
然后是Python: Dict Random Access. N = 10 : 4.9 us/op Dict Random Access. N = 100 : 0.54 us/op Dict Random Access. N = 1000 : 0.13 us/op Dict Random Access. N = 10000 : 0.121 us/op Dict Random Access. N = 100000 : 0.40927 us/op Dict Random Access. N = 1000000 : 0.497939 us/op Dict Random Access. N = 10000000 : 0.6353964 us/op这里有必要说一下。Python的dict实现,是在一片连续内存上存储的哈希表。也就是经典的哈希表实现方法。这样,计算出每个key的哈希值后,实际就相当于一个数组访问。但这有一个缺点:当哈希表元素数量不断增加时,需要频繁地释放和再申请整片内存。这样会对性能有影响。在我们的测试中,则没有考虑到这部分。而Go的实现,是采用树结构的哈希表,这样每次增加元素,最多只需要重新申请和复制一部分内存。但这样带来的代价,就是访问速度的增加。一个缓解的方式就是增加树节点的度数,从而降低树的高度。从这个测试中,我们可以看到,当节点数量增加到一定程度,Go的劣势就显现出来了:由于树结构的深度增加,导致每次访问时多次缓存缺失,从而使得访问速度增加。
下面是C++的 Unordered Map Random Access. N = 10. 0.4 us/op. Unordered Map Random Access. N = 100. 0.16 us/op. Unordered Map Random Access. N = 1000. 0.168 us/op. Unordered Map Random Access. N = 10000. 0.2055 us/op. Unordered Map Random Access. N = 100000. 0.54728 us/op. Unordered Map Random Access. N = 1000000. 0.690345 us/op. Unordered Map Random Access. N = 10000000. 0.743512 us/op.
最后,是Java: HashMap Random Access. N = 10: 0.803400 us/op. HashMap Random Access. N = 100: 0.307150 us/op. HashMap Random Access. N = 1000: 0.363706 us/op. HashMap Random Access. N = 10000: 0.633317 us/op. HashMap Random Access. N = 100000: 0.298482 us/op. HashMap Random Access. N = 1000000: 0.160155 us/op. HashMap Random Access. N = 10000000: 0.178708 us/op.可以看到,继续出现了类似前面的情况,即最后访问速度反而提高了。不过有一点必须提,不是我黑Java,元素增加之后,访问速度的确快了,但是插入速度和CPU使用率实在不敢恭维。如果算上插入速度,可能Java反而是最慢的。
最后,把结果再画在图上: 总结基本说来,关于Go中map是否是性能杀手的问题:如果你能忍受C++的unordered_map,python中的dict以及元素数在100000以内的Java中的HashMap,那么Go中的map就应该还能接受。 另外还有一点让我意外的,就是Java在元素数庞大时的效率。如果你有很多很多的元素,而且数量不会增加(Java中插入元素的效率比较低),那么采用Java的HashMap应该不错。关于这部分,可以再做一些benchmark。 后续讨论我把结果发到golang-china上,有些朋友给出了更多的测试结果或建议。 Java的startuplihui指出: 不能用java的小数量的条目来恒定它的性能,因为在测试环 境中,小数量的条目不能让它热起来,而在实际环境中,由 于hashmap会在程序中多处使用,并且会循环调用使用过 hashmap的历程,因此在实际中hashmap必然是热的,从而对 小数目的hashmap而言,性能仍然是处于最优化的状态。 我的回复: 为此,我又对java做了一个测试。测试方法是:在计时开始 前,先调用一遍循环取得所有元素。这样做对于元素多的哈希 表,会增加conflict miss和capacity miss。但对于小的哈希 表,可以完全避免compulsory miss。简单说,这个循环先让 cache预热起来。 我没有测试N=1E7的时候,因为N=1E7的时候java实在太耗费时 间了。我前面说了,可能是我插入部分的代码没有做任何性能 考虑的缘故,但毕竟这部分不计时,也就没关心。 以下是Java预热启动的结果: HashMap Random Access. N = 10: 0.362500 us/op. HashMap Random Access. N = 100: 0.254190 us/op. HashMap Random Access. N = 1000: 0.219619 us/op. HashMap Random Access. N = 10000: 0.639815 us/op. HashMap Random Access. N = 100000: 0.244724 us/op. HashMap Random Access. N = 1000000: 0.159392 us/op. 作为对比,以下是Go冷启动的结果(没有cache预热): Map Random Access. N = 10: 0.3 us/op Map Random Access. N = 100: 0.14 us/op Map Random Access. N = 1000: 0.08800000000000001 us/op Map Random Access. N = 10000: 0.1157 us/op Map Random Access. N = 100000: 0.46925 us/op Map Random Access. N = 1000000: 0.520184 us/op 个人认为,Java慢的原因还是和JVM脱不开干系。成也萧何,败 也萧何。小数据量的时候,JVM本身的overhead占了主流。大数 据量的时候,JVM的预测,乱序执行和prefetch发挥了作用。 当然,以上纯粹我的推测,还请了解JVM的朋友们帮忙指正。 key值对哈希表的影响laputa指出: 测试结果,除了和这两者有关: 1、key的类型(int、string或其它) 2、key的遍历顺序(自然序还是随机序) 还和key序列的特征有关。 如果把key进行md5,然后取其中9位,Python的测试结果如下。 Dict Seq. Access. N = 10 : 0.882148742676 us/op Dict Seq. Access. N = 100 : 0.340938568115 us/op Dict Seq. Access. N = 1000 : 0.312805175781 us/op Dict Seq. Access. N = 10000 : 0.339293479919 us/op Dict Seq. Access. N = 100000 : 0.623297691345 us/op Dict Seq. Access. N = 1000000 : 0.772630929947 us/op Dict Seq. Access. N = 10000000 : 0.986476206779 us/op 这前后差异的原因是python的dict采用open addressing实现。 Go 的结果如下,变化较小: Map Seq. Access. N = 10: 0.8000000000000002 us/op Map Seq. Access. N = 100: 0.3 us/op Map Seq. Access. N = 1000: 0.239 us/op Map Seq. Access. N = 10000: 0.29430000000000006 us/op Map Seq. Access. N = 100000: 0.37426 us/op Map Seq. Access. N = 1000000: 0.371087 us/op Map Seq. Access. N = 10000000: 0.4287918 us/op 不知道Java的结果跟此有没有关系~ btw,之前忘了说,测试的环境是Linux Linux 2.6.29.3-server-1mnb SMP i686 AMD Opteron(tm) Processor 246 GNU/Linux 我的回复是: 个人认为,这取决于哈希函数。取过MD5 后,相当于 --- 虽然不能完全等效于 --- 把key做了随机化。这样哈希值相差也可能比 较大。而此时Go的tree strucutre优势就体现出来了。 |
|