Go中map性能分析后续
mon...@gmail.com
总结一句话：如果你能忍受C++的unordered_map，python中的dict以及元素数在
100000以内的Java中的HashMap，那么Go中的map就应该还能接受。
欢迎讨论
-Monnand
Uhioins Dell
受教了，不管怎样就是喜欢go简单的语法。
--
来自: Golang-China ~ 中文Go语言技术邮件列表
详情: http://groups.google.com/group/golang-china
官网: http://golang-china.org/
IRC: irc.freenode.net #golang-china
@golangchina
saber
lihui
lihui
laputa
lihui
minux
如果这个测试是可靠的话，可能需要重新看一下google的那篇论文并且验证一下，因为当时我记得各语言是采用类似的数据结构（不像russ一样优化后使用了不同的数据结构），然后得出go的性能很菜的结论。如果map不是瓶颈，为什么优化掉了map后才与c++一样呢？
lihui
--
minux
如果我没有记错的话，那篇论文的主旨不是说最佳优化，而是说一般用法，它花了很大的篇幅来说明为什么如此选择数据结构。
Liigo Zhuang
从楼主的文章中（尤其是两幅图片）分析得到如下一些信息：无论是顺序访问还是随机乱序访问，当哈希表成员数超过1000以后，c++/python/go三者的运行效率都趋于一致变慢、并且互相之间没有拉开明显的距离，反而是java在哈希表成员数越来越大时展现了越来越快的运行效率（因而可能更加适应长期运行的服务器程序）。在这个层面上，没有体现出静态编译型语言(go/c++)相对于脚本语言(python)和虚拟机语言(java)的运行效率方面的优势，反而体现出虚拟机语言(Java)在长期运行过程中自主优化运行效率的优势。这或许会对未来新的（服务器端）编程语言运行模型的选型有所启发。（另：疑惑：哈希表还有顺序访问一说？）
mon...@gmail.com
> 这个测试结果有点儿诡异。
>
目前我还在继续察看这个benchmark是不是有什么其他问题。github上有代码[1]，
有兴趣的朋友最好能自己再做一下测试。可能的话把结果给我（还有测试环境）。
> 我以前测的是插入(没有查询，可能不太纯粹，其中有一个除法操作)，数量是1e7
> 个条目，结果是java比Go快数倍。
>
我还没有测试插入效率。但是java在我这里（感觉上）插入耗费的时间很多。当
然，插入部分我都是随便写的代码，所以效率可能不是最优。关于Go的插入，你是
在make的时候申请了多少元素？
> 对于hash表的性能测试是应该要结合查询和插入同时测试，因为在小对象的时候，
> 插入和查询用得差不多频繁。
>
> 但是，不能用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的朋友们帮忙指正。
mon...@gmail.com
> +1
>
> Python顺序访问的结果，和之前有差异？
>
> Dict Seq. Access. iterations: 1000 . 0.123 us/op
> Dict Seq. Access. iterations: 10000 . 0.1137 us/op
> Dict Seq. Access. iterations: 100000 . 0.14328 us/op
> Dict Seq. Access. iterations: 1000000 . 0.163299 us/op
> Dict Seq. Access. iterations: 10000000 . 0.1822816 us/op
>
> 在英文组讨论的时候，仔细看了下数据，之前python顺序访问的这个结果最符合O(lgn)
这个比较乱。关键原因是：我也不知道python咋能获得它的自然顺序 -_-||
以前的那个结果，是通过和插入顺序一样的顺序访问的。现在，我是以a.keys()返
回的顺序访问的。我觉得keys()怎么也给返回给好用的顺序吧。
哪位朋友再帮忙看看。
-Monnand
Liigo Zhuang
就好比两辆车比赛。a起跑很快，前面一段也很快，但是耐力一般，越往后跑越有慢的趋势；b起步较慢，但是越跑越快，耐力也很好，最终超过了a。这样来说，a适合跑客户端程序，b适合跑服务器端程序。
minux
以下是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的朋友们帮忙指正。
mon...@gmail.com
> 从楼主的文章中（尤其是两幅图片）分析得到如下一些信息：无论是顺序访问还是
> 随机乱序访问，当哈希表成员数超过1000以后，c++/python/go三者的运行效率都
> 趋于一致变慢、并且互相之间没有拉开明显的距离，反而是java在哈希表成员数越
> 来越大时展现了越来越快的运行效率（因而可能更加适应长期运行的服务器程
> 序）。在这个层面上，没有体现出静态编译型语言(go/c++)相对于脚本语言
> (python)和虚拟机语言(java)的运行效率方面的优势，反而体现出虚拟机语言
> (Java)在长期运行过程中自主优化运行效率的优势。这或许会对未来新的（服务器
> 端）编程语言运行模型的选型有所启发。（另：疑惑：哈希表还有顺序访问一说？）
>
1. 之所以越来越慢，我文中提到，是由于cache miss的结果。随着元素数量增
多，主要的时间都花费在cache miss带来的内存访问时间上。这个时间和计算哈希
值的时间相比，完全不在一个数量级。
我文中给出了公式：
AMAT = hit time + cache miss rate * cache miss penalty
当cache miss rate很大的时候，主要的访问时间都是cache miss penalty了。换
句话说，谁访问内存的次数少，谁就占优势。这就是为什么Python在随机访问的测
试中可以在后期达到一路领先于go的原因。因为Python使用的是一个一维的数组来
存储哈希表，这样计算出哈希值后，访问元素只需要一次内存访问。而go使用的是
树结构哈希表，访问元素需要O(log(N))次。go通过大度数的树节点，来增加log的
底数，从而在小数据量面前让树效应不是很明显。但当数量增多，结果就可以看出
来了。
另外还需要注意的一点是，我使用的python是2.7.2版本。而此版本的python中，
哈希值的计算没有引入任何随机函数。这也是导致它速度快的原因之一。但这样的
代价还是很大的，因为这样会带来很大的安全隐患。详细内容我不多说了，算法导
论里面就有。
2. 关于Java在大量数据面前的效率。这部分从我的测试中，随机访问时的优势是
最明显的。但在这个比较中，有几个前提需要注意：
- 访问是随机的，换句话说，可以假设认为缓存命中率非常低。这与常见的
workload不同，常见的workload一般都会呈现出2-8法则（长尾分布），而随机访
问的workload则完全没有这样的模式。java此时之所以快，（我推测）是因为JVM
在运行的时候，在后期已经得到了我访问的顺序（存在seq数组中），所以可以通
过乱序执行提高缓存命中率。
- 数据量在1e5以上的数量级的时候才能体现出java的优势。
对于实际的负载，以上两个条件很少满足：
- 对于一般的负载，往往符合2-8法则，缓存作用比较明显
- 对于一般负载，循环比较复杂，JVM是否能够通过乱絮来提高缓存命中率是个问
题。很多时候，甚至无法预测下一次循环要访问哪个元素（比如要访问哪个元素是
用户指定的），这样JVM就必须一个循环一个循环地执行
- 实际中使用哈希表，元素数量很少在1E5以上数量级。即便是大型程序，如果让*
一个*哈希表存储百万个元素，那么不如把它分在几个表中 ---- 可能更常见的做
法是分散在几个机器上。关于未来的大型应用，主要还是集中在如何能够容易地
scale-out上，而不是继续scale-up的模型。
3. 关于哈希表的顺序。哈希表本质是利用了随机访问的优势，一次计算出要取出
元素所在的地址。所以元素存储也是有顺序的。详细参见算法导论。
mon...@gmail.com
<snip>
> 直觉觉得这个结果很奇怪。我有时间了仔细看看这个问题。 对于random
> access，prefetch感觉不会起作用呀。
当初我也卡在这里好久。后来看看代码，我明白了：
当时我为了避免随机数发生器产生的作用，我在计时开始前，已经把随机产生的访
问顺序存储在一个数组中。然后开始计时，然后循环开始。
换句话说，JVM在执行过程中，是通过一个数组来取得下一个要访问的key的。这样
的话，在循环执行过程中，对于JVM来说，没有任何随机因素在其中。
我曾想过使用真随机数发生器在循环里面，但是这个真随机数发生器产生随机数的
效率（不是质量）确实不敢保证。怕是测了半天，测得不是哈希表效率，而是真随
机数发生器的效率。这样就悲剧了。
> 要说预测和乱序执行倒不如解释成发现sum没有副作用被优化掉了。
>
> 要不你试试打印出来sum的值？
>
这个打印出来过。的确有值。
mon...@gmail.com
> 就好比两辆车比赛。a起跑很快，前面一段也很快，但是耐力一般，越往后跑越有
> 慢的趋势；b起步较慢，但是越跑越快，耐力也很好，最终超过了a。这样来说，a
> 适合跑客户端程序，b适合跑服务器端程序。
>
这个有必要澄清一下，前面说了，我的两个benchmark测试的是极端情况下（缓存
命中率最高和缓存命中率很低）的运行结果。并且，实际当中，是否可能在一个哈
希表内放入1E以上数量级的元素数，则有待考察。
同时需要注意的，是Java在元素数量少的时候运行效率明显低于C++和go；而在数
据多的时候，优势并没有比它（在小数据集上）的劣势明显。
最后，目前在我的机器上，没有任何一个benchmark可以跑1E8个元素。换句话说，
元素数量再多也就到1E7这个数量级了。当然，未来服务器会怎么发展我不知道
（现在服务器能不能跑1E8我都没测试过）。不过还是那个问题：是否真的会有人
在一个哈希表里存1E6这个数量级的元素数，我觉得是个问题。以后即便计算规模
变大，大家也会逐渐倾向于使用scale-out这个模型，而非scale-up。这样每个节
点的负载量并不是很大。也就是基于这个原因，才有人提出使用ARM一类的处理器
构建cluster。
关于Java，我个人认为最大的优势是在于JVM对于潜在并行的处理。[1]中就指
出，JVM可以在运行的时候发现程序中潜在的并行方案，然后通过多线程来提高效
率。这对于未来的多核CPU是有很大帮助的。因为传统的程序员往往会习惯性的使
用串行方式编写程序，而Java则不必要求程序员修改习惯，进而提高效率。
1. Looking Back on the Language and Hardware Revolutions: Measured
Power, Performance, and Scaling
http://www.cs.utexas.edu/~mckinley/papers/power-v-perf-asplos-2011.pdf
lihui
我还没有测试插入效率。但是java在我这里（感觉上）插入耗费的时间很多。当 然，插入部分我都是随便写的代码，所以效率可能不是最优。关于Go的插入，你是 在make的时候申请了多少元素？
mon...@gmail.com
> 我在make时申请了N个元素，相应地，java的hashmap也是初始申请N个原始。
>
> 除了适当的外部配置，测试的时候注意不要在代码中对gc做任何特殊处理。因为我
> 一个推测就是认为go的map之所以速度慢（插入操作在一般的使用场景中对“慢”有
> 贡献），可能在于gc，如果不是gc，应该不用太担心，因为go的map是c语言实现的。
>
之所以加入GC的控制，是因为我想测试的是哈希表访问速度，不是垃圾回收器的效
率。以下是不对GC做任何处理的内存顺序访问时间：
Map Seq. Access. N = 10: 0.4000000000000001 us/op
Map Seq. Access. N = 100: 0.31 us/op
Map Seq. Access. N = 1000: 0.153 us/op
Map Seq. Access. N = 10000: 0.1322 us/op
Map Seq. Access. N = 100000: 0.16683 us/op
Map Seq. Access. N = 1000000: 0.18495 us/op
Map Seq. Access. N = 10000000: 0.4793002 us/op
以下是随机访问：
Map Random Access. N = 10: 0.4000000000000001 us/op
Map Random Access. N = 100: 0.25 us/op
Map Random Access. N = 1000: 0.22 us/op
Map Random Access. N = 10000: 0.2415 us/op
Map Random Access. N = 100000: 0.57119 us/op
Map Random Access. N = 1000000: 0.7392000000000001 us/op
Map Random Access. N = 10000000: 0.8847884 us/op
这个性能，基本在C++上下。
> 以前以为go在小数据时没有优化，现在看来go的map的层次结构让go在小数据量时
> 得到了优化。
>
> ps：我说map在go中是个性能杀手，还有就是源于对去年reflect的GetField方法的
> 性能分析，从直觉上觉得GetField方法不至于那么慢，经过测试和分析，发现里面
> 使用了map，它耗费了很多时间，其中它耗费的大部分时间在于对内存分配方法的
> 调用，以及gc里面对时间函数的调用（尚不清楚到今日，是否得到了改善）。这导
> 致了该方法比我用简单的遍历策略获得field要慢很多（当然我的方案不完整，只
> 是示意，但足以说明性能问题的来源，并且这个简单的方案可以用来加速struct在
> 简单情况下的性能）。
你可以写一些简单的benchmark来验证一下你的推断。
lihui
laputa
-Monnand
lihui
laputa
laputa
Liigo Zhuang
--
来自: Golang-China ~ 中文Go语言技术邮件列表
详情: http://groups.google.com/group/golang-china
官网: http://golang-china.org/
IRC: irc.freenode.net #golang-china
@golangchina
Liigo Zhuang
3. 关于哈希表的顺序。哈希表本质是利用了随机访问的优势，一次计算出要取出 元素所在的地址。所以元素存储也是有顺序的。详细参见算法导论。
Liigo Zhuang
laputa
laputa
Liigo Zhuang
使用者当然不需要了解这些。但是JIT的优化结果是明显可见的。当然不是掷骰子，当然不是聊胜于无。你这种臆测是没道理的。
laputa
mon...@gmail.com
先感谢laputa提供的python测试结果。关于是否有必要和python做对比，我觉得看
看运行效率就能看出来了。这种简单的哈希表操作，大部分时间实际耗费在了哈希
表的操作，而python这部分的代码，是C写的，在解释器中的。在元素数量相对比
较多的时候，解释器本身的overhead所占比例就少了，效率未必会比C++，Java这
样的语言低多少。这一点从测试结果本身就能看出来。
Liigo Zhuang:
> 元素存储是否有序取决于哈希表的具体实现，例如Go基于Tree的map就可能(?)只
> 是局部有序整体无序。但是作为用户，很难做到通过调整key的顺序而保证顺序访
> 问value，因为map接口通常对用户隐藏内部实现细节（map内成员的顺序对用户而
> 言是不重要的也是不可知的）。非要顺序访问成员，也不符合大多数日常应用实际
> 需求。测试最好还是模拟大多数真实应用的情况。
关于哈希表的访问顺序laputa已经做了解释。我再加一条：
在Go1的preview中[1]，特意提到了map的访问顺序问题（这部分实际已经在
weekly.2011-10-18中实现了）
The language leaves map iteration order undefined and in practice it
differs across hardware platforms.
Go 1 will define that map iteration order may change even from one
iteration to the next. This allows the map implementation to ensure
better map balancing even when programs are using range loops to select
an element from a map.
这意味着，Go1以后，go（可能）会在运行过程中，调整哈希表元素的存储顺序，
从而提高效率。一种可能是把常被一起访问的元素放在一起，方便CPU的prefetch。
最后，关于“测试最好还是模拟大多数真是应用的情况”。我想这多少对benchmark
有些误解。
一般情况下，benchmark可以分两类，一类是利用实际的trace/程序，或者以实际
trace为基础建立的模型，来做benchmark。这种benchmark的优势是有实际trace做
基础。但是劣势也很明显：需要证明那些真的是实际的trace，而且具备足够的普
遍性。我想后者对于很多paper的作者来说，才是最头疼的地方。
另一类是创造极端情况，从而找到上/下界。这种benchmark的优势是以理论为基
础，具备足够的说服力。劣势是这个上/下界可能与实际偏离太远。一种缓解这个
问题的方法，是同时在理论上下界出现环境下进行测试，如果这个上下界之间相差
不大，则可以说明这个上下界实际是有意义的。
我的benchmark倾向于后者。我文中之所以放上那几个公式，就是为了解释，我实
际测试了缓存命中率很低和缓存命中率最高的情况。至于说使用第一类的
benchmark，我一来没有具备足够标杆作用的测试程序；二来也还没找出在这些程
序中如何衡量map效率的方法。
关于缓存命中率最高的情况，我假设，语言/库提供的自然序访问是保证缓存命中
率最高——至少是编程人员可能达到的最高命中率。如果这个假设不成立，那么意味
着这个语言/库存在设计缺陷。因为编程人员不可能深入每个语言的编译器/解释器
/虚拟机/库，研究代码，最后自己找出一个命中率最高的访问序列。
关于缓存命中率很低的情况，我这里有个保留。因为我实际测试的不是理论最低
点。可能存在一个序列，比我使用的随机序列产生更低的缓存命中率。但是相比较
常见的符合2-8法则的程序，这种随机序列已经足够产生比大多数实际程序更低的
缓存命中率了。所以我也假定，这个情况是实际程序的最下界。
从最后的测试结果看，上下界之间的空间在多数情况下足够小，在一定程度上具备
一些指导作用。
在[2]中给出了各种已知缓存命中，不命中的访问时间，从而推测程序运行效率的
量化方法。我就不多说了。
先说这么多，下面一封讨论JIT。
1.
https://docs.google.com/document/pub?id=1ny8uI-_BHrDCZv_zNBSthNKAMX_fR_0dc6epA6lztRE
2. Computer Architecture: A Quantitative Approach
http://www.amazon.com/Computer-Architecture-Quantitative-Approach-4th/dp/0123704901
mon...@gmail.com
> Java等虚拟机语言在程序*运行时*会尽可能智能的采取各种优化策略方法（参考
> JIT的实现），程序运行时间越长优化越深入，所以说它更加适合编写服务器端程
> 序。而编译型语言在*编译*完成的那一刻起优化就结束了，但可悲的是还有许多优
> 化策略只有在运行时才能确定是否有效（如对虚函数的inline处理）。这两种编译
> 模型孰优孰劣并不鲜明，完全取决于设计者的取舍。
我不是做编译器方面的研究，所以这方面的详细内容不敢做轻易断言。Liigo
Zhuang所指出的，只能说明这种Managed programming language的确可以使用这类
优化技术，并且使用这类优化技术比不使用这类优化技术，在其他条件相同的情况
下，具备优势。
换句话说，如果有个JVM不使用JIT，那么可能会比使用了JIT的JVM效率低。并且很
多论文中都可以看到这样的结果。
但是至于和其他非managed programming language相比是否也能在效率上体现出优
势，在什么情况下能够体现出优势，我就不清楚了。
在讨论这个问题之前，我有必要再强调一下我的benchmark中的局限：
实际被计时的那个循环，是非常简单的。在运行过程中发现这类循环的特点并且进
行相应优化，并不是一个非常困难的事情。老实说，这类优化甚至用不到
dynamical analysis，用static analysis就足以对它进行优化 --- 比如发现循环
级并行，然后做并行处理。但是实际当中这样简单易见的可能优化的地方究竟有多
少，运行时优化的代价又如何，这本身还有待考察。
我前面说了，实际我想测试的是上下界。但是JVM这样的优化实际让我没能得到这
样的结果。更具体说，我想测试的是：
hash time + AMAT + epsilon
hash time由于输入的字符串定长，所以可以认为是常数。而AMAT我在文中给出了
定义，是和缓存命中率相关。详细推导我不说了。简单说，java的benchmark本身
并没能给出实际的上下界，所以java的benchmark的结果，对于上下界来说，意义
不大。
的确，JIT技术可以发现很多运行时的特性，从而提供优化。但是编译器研究的人
也许会知道，在设计编译器算法的时候，会碰见各种图灵不可解问题。这些问题即
便在运行时，也同样是图灵不可解的。更不必说JIT还要面临各种限制（编译时间
需要保证），在这些条件限制下，究竟能否为普通程序优化到直接运行静态编译器
几级优化后代码的级别，就有待考察了。
另外还需要注意的是，我的C++编译器用的是gcc，不是llvm，不是icc。换句话
说，还不是已知的最/较好的C++编译器。
还有，关于运行时优化。这并非只有JVM在做。底层硬件无时无刻不在运行时进行
各种优化。乱序执行, 各种转移预测，早就是常见处理器的必备技术。硬件本身的
高效使得哪怕是简单算法也可以使程序运行效率得到很大提升。以转移预测为例，
对于很多程序，预测准确度也达到了不错的水平[1]。哪怕JVM可以有更高的预测准
确度，但这种准确度的提高能否弥补它预测失败的代价和预测算法的耗时，就要再
经过一份考虑了。
生产级别使用的处理器和我们的处理器是否一样也需要考虑。比如IA64的处理器就
考虑了很多并行的可能[2]。比如循环级并行等等。
JVM的优势是在于它可以获得更多的循环/进程/线程级别的信息，从而可以利用这
些信息进行优化。而个人认为，这部分的优化主要会在以后多核处理器上体现出
来，因为JVM可以通过这样的方式发现潜在的并行代码，从而动态的使用多个核来
处理本身是串行的程序。至于说在单个核上能够优化到什么程序，我就不太清楚了。
的确，动态编译技术是编译器研究领域的主流，但能否与现有的C/C++程序进行对
比，就有必要分类讨论了。这方面我不是专家，不好多说。
1. Computer Architecture: A Quantitative Approach
http://www.amazon.com/Computer-Architecture-Quantitative-Approach-4th/dp/0123704901
2. INTRODUCING THE IA-64 ARCHITECTURE
http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CCMQFjAA&url=http%3A%2F%2Fusers.ece.gatech.edu%2F~sudha%2Facademic%2Fclass%2Fece4100-6100%2FPapers%2FVLIW%2Fia64intro.pdf&ei=zItrT_zoMpPUgAeDjM3MBg&usg=AFQjCNHja7Kolf5k1GZPawFdTMkQl6zSrw&sig2=XNij-hbFL-R2RNo0xHx1MA
laputa
Liigo Zhuang
在 2012-3-23 上午3:56，"mon...@gmail.com" <mon...@gmail.com>写道：
>
> 在Go1的preview中[1]，特意提到了map的访问顺序问题（这部分实际已经在 weekly.2011-10-18中实现了）
>
> The language leaves map iteration order undefined and in practice it differs across hardware platforms.
>
> Go 1 will define that map iteration order may change even from one iteration to the next. This allows the map implementation to ensure better map balancing even when programs are using range loops to select an element from a map.
>
> 这意味着，Go1以后，go（可能）会在运行过程中，调整哈希表元素的存储顺序， 从而提高效率。一种可能是把常被一起访问的元素放在一起，方便CPU的prefetch。
>
对于你引用的这段英文，我以为Go 1的本意是，为了运行效率不惜调整map内部的元素存储顺序，实际上就是在警告用户不要依赖元素的存储顺序。事实上大多数语言都如此，依赖成员顺序的地方可以采用list或set。
你说的一种可能“把常被一起访问的元素放在一起“，如果成真，估计是准备采用类似java JIT的方案在 *运行时* 优化了，当然目前只是猜测。运行时优化可以比编译时优化做的工作更多更有效，不一定绝对有效，但对通常常见情况有效，就知足了。这也算是对楼上某人的回复吧。
Liigo Zhuang
为什么要保证呢，为什么要绝对呢，就算是只能做到某些情况下某种程度的运行时优化（优化成果大于优化损耗），也好于没有优化。JIT的优化效果是看得见的，你完全可以去了解，无必要凭空质疑。
laputa
mon...@gmail.com
> 测试结果，除了和这两者有关：
> 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的结果跟此有没有关系~
感谢！我会把这个结果更新到文章中。个人认为，这取决于哈希函数。取过MD5
后，相当于——虽然不能完全等效于——把key做了随机化。这样哈希值相差也可能比
较大。而此时Go的tree strucutre优势就体现出来了。
关于JIT的讨论：
1. 动态的调整map中元素的顺序提高访问效率这个技术应该不能算作是JIT。JIT是
一种编译技术，而调整map元素的行为并没有对编译出来的代码做任何调整，只是
map的一种行为而已。倘若这也算JIT技术，那么所有在线学习算法都能算作JIT的
一部分了。
2. 我看过一些编译器的paper，大概思路是把C/C++编译出来的代码在一个准生产
环境下运行并且做profiling。把运行结果出来的profile再给（经过修改后的）编
译器，编译器利用这个profile，得到代码运行时的行为再做更近一部优化，如此
循环几次。这种思路类似JIT。但编译阶段是在一个准生产环境下进行，而且是线
下编译。一方面是因为profiling的阶段overhead比较大（印象中好像是30%上
下），另一方面，这样的线下编译可以在没有时间限制的情况下，尽量采用最优化
的技术。这两点和JIT还是有些区别的。因为JIT中，很常见的一个做法是：由于时
间复杂度，某些优化算法不能使用，所以只能采用次优算法[1]。这样，可能出现
的问题是（我没实际测试过，只是推测），哪怕运行时间再久，由于算法本身的问
题，依然无法优化到最佳状态。实际上，时间限制对于JIT来说是很强的。
由于当时看paper是随便翻的（身边有做编译器相关的朋友），所以也没记下名
字。当时还有个问题：那些paper针对的优化点，与其说是具有优化潜力的代码，
不如更直白地说是编程人员的疏漏。比如在没有考虑cache miss的情况下对数组进
行操作等等。当然，也有些值得注意的，比如locality方面的优化，可以达到针对
目标体系结构做到优化等等。这样程序员就可以写出更具移植性的代码，而把优化
问题交给编译器。
3. 我觉得关于JIT问题的讨论，可以暂时停止一下了。一来，我看不到更多有意义
的benchmark和针对benchmark的讨论。单纯地列举各种优化技术和其限制条件并没
有任何实际意义。二来，这毕竟是关于go的列表。哪怕真的讨论，也最好加上OT。
1. http://blogs.msdn.com/b/davidnotario/archive/2004/11/01/250398.aspx
laputa
Liigo Zhuang
概念都没搞清楚。jit也好，（楼主提出的）调整map元素顺序也好，都是属于运行时优化。争论是不是jit是无聊的。有人前面还讲什么jit的优化是“聊胜于无“，真该好好补补课了，用好google搜索引擎。在没有正确认识jit之前，我建议停止参与讨论jit的话题。
如果go也在乎运行效率的优化（必然的），也打算实施运行时优化的话（楼主提出的猜想），jit作为运行时优化的成功代表之一，go也有理由参考或评估其做法。至少没必要排斥。
> 2. 我看过一些编译器的paper，大概思路是把C/C++编译出来的代码在一个准生产 环境下运行并且做profiling。把运行结果出来的profile再给（经过修改后的）编 译器，编译器利用这个profile，得到代码运行时的行为再做更近一部优化，如此 循环几次。这种思路类似JIT。但编译阶段是在一个准生产环境下进行，而且是线 下编译。一方面是因为profiling的阶段overhead比较大（印象中好像是30%上 下），另一方面，这样的线下编译可以在没有时间限制的情况下，尽量采用最优化 的技术。这两点和JIT还是有些区别的。因为JIT中，很常见的一个做法是：由于时 间复杂度，某些优化算法不能使用，所以只能采用次优算法[1]。这样，可能出现 的问题是（我没实际测试过，只是推测），哪怕运行时间再久，由于算法本身的问 题，依然无法优化到最佳状态。实际上，时间限制对于JIT来说是很强的。
>
> 由于当时看paper是随便翻的（身边有做编译器相关的朋友），所以也没记下名 字。当时还有个问题：那些paper针对的优化点，与其说是具有优化潜力的代码， 不如更直白地说是编程人员的疏漏。比如在没有考虑cache miss的情况下对数组进 行操作等等。当然，也有些值得注意的，比如locality方面的优化，可以达到针对 目标体系结构做到优化等等。这样程序员就可以写出更具移植性的代码，而把优化 问题交给编译器。
>
> 3. 我觉得关于JIT问题的讨论，可以暂时停止一下了。一来，我看不到更多有意义 的benchmark和针对benchmark的讨论。单纯地列举各种优化技术和其限制条件并没 有任何实际意义。二来，这毕竟是关于go的列表。哪怕真的讨论，也最好加上OT。
>
> 1. http://blogs.msdn.com/b/davidnotario/archive/2004/11/01/250398.aspx
>
>
mon...@gmail.com
> 概念都没搞清楚。jit也好，（楼主提出的）调整map元素顺序也好，都是属于运行
> 时优化。争论是不是jit是无聊的。有人前面还讲什么jit的优化是 “聊胜于无“，
> 真该好好补补课了，用好google搜索引擎。在没有正确认识jit之前，我建议停止
> 参与讨论jit的话题。
“聊胜于无”不是我说的。
> 估计是准备采用类似java JIT的方案在 *运行时* 优化了
我道歉，是我之看到JIT就直接回复了，如果你说的是运行时优化，那么map的确
（可能）会如此。
但是希望你能否注意一下列表礼仪，别动不动就说什么“真该好好补补课了”之类
的。我觉得我个人的专业水平不是大伙关注的焦点。
我一切讨论的论调都是：关于JVM，我不是做编译器研究的，不是我的研究方向我
不多说。我一切指出来的，都是可能存在的优化和使用相应优化技术可能带来的限
制。我希望你能仔细读读我的邮件，我没有*任何*说法，*明确*指出哪个会更快。
我不希望列表里面吵吵闹闹。我只希望你能再注意一下自己说话的方式。
-Monnand