Golang 中使用 Slice + 索引 Map 替代 Map 获得性能提升

秦川 · · 1902 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

起因

在我们的多个线上游戏项目中,很多模块和服务为了提高响应速度,都在内存中存放了大量的(缓存)数据以便获得最快的访问速度。

通常情况下,为了使用方便,使用了 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]*obj gc 极慢
  • map[int]int gc非常快
  • []*obj gc 也很快

于是我们使用一个 []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。

有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:秦川

查看原文:Golang 中使用 Slice + 索引 Map 替代 Map 获得性能提升

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

1902 次点击  ∙  3 赞  
加入收藏 微博
1 回复  |  直到 2019-09-10 08:58:43
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传