【介绍一个组件】go: Copy-On-Write map,对读极多和写极少的场景做优化
  ZvAhkxhPQwyp 2024年04月24日 39 0
Go

作者:张富春(ahfuzhang),转载时请注明作者和引用链接,谢谢!


代码请看:https://github.com/ahfuzhang/cowmap

有这样一种场景:数据量不多的map,在使用中读极多写极少。为了在这种场景下做极致的优化,我实现了 copy-on-write 的map:
其实现原理为:所有的读都可以不加锁的并发读取,一旦需要写,则 copy 一份原来的map,在备份上修改,然后通过原子操作把指针切换到新的对象上。

我对比了CowMap(Copy-On-Write Map) 和 sync.Map , 以及普通map + 读写锁三种方式的性能:

Read-write rate Type ns/op
99.99% : 0.01% CowMap 4.649
99.99% : 0.01% map + sync.RWMutex 187.5
99.99% : 0.01% sync.Map 15.06
99.90% : 0.10% CowMap 32.70
99.90% : 0.10% map + sync.RWMutex 159.9
99.90% : 0.10% sync.Map 14.08
99.00% : 1.00% CowMap 303.6
99.00% : 1.00% map + sync.RWMutex 105.7
99.00% : 1.00% sync.Map 14.08

因此,当读的比例超过 99.99%时,CowMapsync.Map 的 3.24 倍。是 map+sync.RWMutex 的 40.33 倍。

不过我认为更好的实现方法,还是应该参考 rust hashbrown 的实现(see: 《Swisstable:C++中比std::unordered_map更快的hash表》),这样有可能实现这样一些优化:

  • 因为hash的结构是平坦的数组,理论上在不扩容和缩容的前提下,读写都能做到无锁
  • 使用simd指令集来搜索位置,能够提供更好的查找速度。

Have Fun. 😃

【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 2024年04月24日 0

暂无评论

推荐阅读
  uGYzDadp0Cs7   2024年04月18日   61   0   0 Go
  hyrB1Ag4eVs8   2024年04月15日   41   0   0 Go
  YFCZjJLTjJgW   25天前   25   0   0 Go
  uGYzDadp0Cs7   2024年04月16日   97   0   0 Go
  YFCZjJLTjJgW   12天前   19   0   0 Go
ZvAhkxhPQwyp