Golang 中使用 Slice + 索引 Map 替代 Map 获得性能提升
秦川 · · 4781 次点击 · · 开始浏览起因
在我们的多个线上游戏项目中,很多模块和服务为了提高响应速度,都在内存中存放了大量的(缓存)数据以便获得最快的访问速度。
通常情况下,为了使用方便,使用了 go 自身的 map 作为存放容器。当有超过几十万 key 值,并且 map 的 value 是一个复杂的 struct 时,额外引入的 GC 开销是无法忽视的。在 cpu 使用统计图中,我们总是观测到较为规律的短时间峰值。这个峰值在使用 1.3 版本的 go 中显得特别突出(stop the world 问题)。后续版本 go gc 不断优化,到我们现在使用的 1.10 已经是非常快速的并发 gc 并且只会有很短暂的 stw。
不过在各种 profile 的图中,我们依然观察到了大量的 runtime.scanobject 开销!
在一个14年开始的讨论中,就以及发现了 大 map 带来(特别是指针作为 value 的 map)的 gc 开销。遗憾的是在 2019 年的今天这个问题仍然存在。
在上述的讨论帖子中,有一个 Contributor randall77 提到:
Hash tables will still have overflow pointers so they will still need to be scanned and there are no plans to fix that.
不明白他的 overflow pointers 指的什么,但是看起来如果你有一个大的,指针作为 value 的 map 时,gc 的 scanobject 耗时就不会少。
处理
所以我们项目里面自己弄了一个名为 slice_map 的东西来专门优化内存中巨大的 map。这个 map 的实现机制是基于一下几个观察到的现象:
-
map[int]*objgc 极慢 -
map[int]intgc非常快 -
[]*objgc 也很快
于是我们使用一个 []interface 来存放数据,map[int]int 做一个 key -> slice 来映射 key 到存放数据的 slice 的下标的索引。
最初的版本,删除 key 之后,留下的 slice 的空间资源,使用了一个 freelist 来维护管理,但这个方案的问题在于:一旦系统中爆发大量突发性的插入将 slice 撑大,后面就再也没有机会回收内存了。
所以后面的版本使用了 挪动代替删除 的操作,将腾出的空间移动到末尾(一个 O(1) 的操作),再在合适的时机回收 slice 后面没有使用的空间(Shrink操作),可以防止内存的浪费。
这样,既得到了 便宜 的 gc,又获得了 map 的便利性。
这个项目放到了 github 上: legougames/slice_map
在自带的性能测试中,额外收获了几点:
- 插入效率比原生 map 快了一倍。
- 如果使用
FastIter,遍历的速度快1个数量级(而且还是稳定的)。 - 如果使用普通的
Iter,那么可以在遍历的过程中删除 key。
有疑问加站长微信联系(非本文作者)
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传
收入到我管理的专栏 新建专栏
起因
在我们的多个线上游戏项目中,很多模块和服务为了提高响应速度,都在内存中存放了大量的(缓存)数据以便获得最快的访问速度。
通常情况下,为了使用方便,使用了 go 自身的 map 作为存放容器。当有超过几十万 key 值,并且 map 的 value 是一个复杂的 struct 时,额外引入的 GC 开销是无法忽视的。在 cpu 使用统计图中,我们总是观测到较为规律的短时间峰值。这个峰值在使用 1.3 版本的 go 中显得特别突出(stop the world 问题)。后续版本 go gc 不断优化,到我们现在使用的 1.10 已经是非常快速的并发 gc 并且只会有很短暂的 stw。
不过在各种 profile 的图中,我们依然观察到了大量的 runtime.scanobject 开销!
在一个14年开始的讨论中,就以及发现了 大 map 带来(特别是指针作为 value 的 map)的 gc 开销。遗憾的是在 2019 年的今天这个问题仍然存在。
在上述的讨论帖子中,有一个 Contributor randall77 提到:
Hash tables will still have overflow pointers so they will still need to be scanned and there are no plans to fix that.
不明白他的 overflow pointers 指的什么,但是看起来如果你有一个大的,指针作为 value 的 map 时,gc 的 scanobject 耗时就不会少。
处理
所以我们项目里面自己弄了一个名为 slice_map 的东西来专门优化内存中巨大的 map。这个 map 的实现机制是基于一下几个观察到的现象:
-
map[int]*objgc 极慢 -
map[int]intgc非常快 -
[]*objgc 也很快
于是我们使用一个 []interface 来存放数据,map[int]int 做一个 key -> slice 来映射 key 到存放数据的 slice 的下标的索引。
最初的版本,删除 key 之后,留下的 slice 的空间资源,使用了一个 freelist 来维护管理,但这个方案的问题在于:一旦系统中爆发大量突发性的插入将 slice 撑大,后面就再也没有机会回收内存了。
所以后面的版本使用了 挪动代替删除 的操作,将腾出的空间移动到末尾(一个 O(1) 的操作),再在合适的时机回收 slice 后面没有使用的空间(Shrink操作),可以防止内存的浪费。
这样,既得到了 便宜 的 gc,又获得了 map 的便利性。
这个项目放到了 github 上: legougames/slice_map
在自带的性能测试中,额外收获了几点:
- 插入效率比原生 map 快了一倍。
- 如果使用
FastIter,遍历的速度快1个数量级(而且还是稳定的)。 - 如果使用普通的
Iter,那么可以在遍历的过程中删除 key。