search

suzuki-shunsuke / issue

MIT License
4 stars 0 forks source link

Go の sync.Map について調べる #53

Closed suzuki-shunsuke closed 4 years ago

suzuki-shunsuke commented 4 years ago

map と sync.RWMutex を使って map[string]string に関して sync.Map 的なものを実装してみた。

https://github.com/suzuki-shunsuke/go-thread-safe

sync.Map のドキュメントにも書いてあるが、 sync.Map だと型が interface{} なため、 個別に自分で実装したほうがいいんじゃないかなと思った。

ベンチーマークを取って sync.Map とパフォーマンスを比較した

その結果、 Get/Set に関しては go-thread-safe のほうが良いが、Range に関しては sync.Map のほうが良かった

$ go test -bench="VersusSyncMap" -benchmem
goos: darwin
goarch: amd64
pkg: github.com/suzuki-shunsuke/go-thread-safe/safe
BenchmarkMapString_VersusSyncMap/MapString.Set-16                   9332            127778 ns/op          166913 B/op         33 allocs/op
BenchmarkMapString_VersusSyncMap/sync.Map.Store-16                  3772            313465 ns/op          194440 B/op       5043 allocs/op
BenchmarkMapString_VersusSyncMap/MapString.GetOk-16                28759             38566 ns/op               0 B/op          0 allocs/op
BenchmarkMapString_VersusSyncMap/sync.Map.Load-16                  22934             51165 ns/op               0 B/op          0 allocs/op
BenchmarkMapString_VersusSyncMap/MapString.RangeB-16               17863             66442 ns/op           81952 B/op          2 allocs/op
BenchmarkMapString_VersusSyncMap/sync.Map.Range-16                 84883             13320 ns/op               0 B/op          0 allocs/op
PASS
ok      github.com/suzuki-shunsuke/go-thread-safe/safe  9.967s

どうも allocation が発生しているらしい。 自分の実装では read lock を取って map[string]string をコピーしたあとに コピーした map を使って loop を回しているが、

https://github.com/suzuki-shunsuke/go-thread-safe/blob/v0.7.0/safe/map_string.go#L159-L172

sync.Map ではパット見そんな実装にはなっていない。 そこでどういうふうに実現しているのか、ちょっと見てみたいと思う。

suzuki-shunsuke commented 4 years ago

sync.Map に関するリファレンス

https://golang.org/pkg/sync/#Map

なぜ sync.Map を実装したか Gophercon で発表された資料が公開されていた。

https://github.com/gophercon/2017-talks/blob/master/lightningtalks/BryanCMills-AnOverviewOfSyncMap/An%20Overview%20of%20sync.Map.pdf

また、 sync.Map のパフォーマンスに関する issue でも作者がコメントしている。

https://github.com/golang/go/issues/28938

Also note that much of the overhead that sync.Map avoids comes from cache contention, which can make individual operations O(N) with the number of physical cores: with N cores executing those operations concurrently, you can get O(N²) behavior.

どうもマルチコアで並列に操作した場合の cache contention を解決するために sync.Map を実装したっぽい。

https://github.com/golang/go/issues/28938#issuecomment-441681208

ただ、 sync.Map に関しては performance issue があるっぽい。

suzuki-shunsuke commented 4 years ago

https://golang.org/pkg/sync/#Map

2 つの common use case に最適化されている

  1. 同じキーに一度しか書き込まれず、何度も読み取られる場合 (cache)
  2. 複数の goroutine がそれぞれ別の key 群を読み書きする場合

この 2 つのユースケースの場合、 sync.Map を使うと sync.(RW)Mutex を使う場合に比べて lock contention (ロックの競合) を大幅に減らせる

suzuki-shunsuke commented 4 years ago

読み取りと書き込みを atomic にやるような API は sync.Map は提供していないので、そういう用途では使えない。 例えば同じキーの int の value を increment するような操作を複数の goroutine でやればそれは thread safe ではない。

これは atomic.Value についても言えること。

そういう場合は、 読み取りから書き込みまで sync.(RW)Mutex でロックしたりする必要がある。

https://github.com/suzuki-shunsuke/go-thread-safe/blob/v0.7.0/safe/map_string.go#L135-L142

suzuki-shunsuke commented 4 years ago

sync.Map には size を取得する API がないっぽい https://golang.org/pkg/sync/#Map

issue もある https://github.com/golang/go/issues/20680

suzuki-shunsuke commented 4 years ago

こんなものもある。 https://github.com/orcaman/concurrent-map

The stdlib sync.Map is designed for append-only scenarios. So if you want to use the map for something more like in-memory db, you might benefit from using our version