go のmap がconccurnet じゃないのはけっこう悩ましい。
1.9からsync.Map というconcurrent なmap が追加されていたのでみてみると コメントで
// The Map type is optimized for two common use cases: (1) when the entry for a given
// key is only ever written once but read many times, as in caches that only grow,
// or (2) when multiple goroutines read, write, and overwrite entries for disjoint
// sets of keys. In these two cases, use of a Map may significantly reduce lock
// contention compared to a Go map paired with a separate Mutex or RWMutex.
なんて書かれてる
まぁread heavy 用ってことですね。ざっとみると
type Map struct {
mu Mutex
read atomic.Value // readOnly
dirty map[interface{}]*entry
misses int
}
こんな感じだ go の標準のmap は map のエントリが追加されていなければ concurrent なので
read/update/delete 用に Map.read が用意されてる。 m.read 自体がatomic.Value でCasなんだけど dirty をread に書き出すためにそうしてる感じ 全部ソースはると複雑なので説明だけで。
Map.read の先は
type readOnly struct {
m map[interface{}]*entry
amended bool // true if the dirty map contains some key not in m.
}
type entry struct {
p unsafe.Pointer
}
こんな感じだ、update のときは
func (m *Map) Store(key, value interface{}) {
read, _ := m.read.Load().(readOnly)
if e, ok := read.m[key]; ok && e.tryStore(&value) {
return
}
// 以下read にヒットしないlock してく
}
tryStore でcas で書き込みしていく
func (e *entry) tryStore(i *interface{}) bool {
for {
p := atomic.LoadPointer(&e.p)
if p == expunged {
return false
}
if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
return true
}
}
}
map の検索時は read をみてなければ dirty をみて返すという実装で、cache miss がdirty より多くなると dirty をread に昇格するという作りだ
write heavy だとつらくなるということでいくつかのアプローチで試してみた
- ふつうにlock していく(WithLock)
- 型を固定して sync.Map を再実装してみる
- map 自体はconcurrent じゃないのでkey でsharding してmap を分割してみる(shard)
- dirty がlock されるのが問題なので dirty をlock-free(non blockking) doubly linked list にしてみる(RMap)
やってみた結果は 以下のようになった
MapString は map のkey をstring に固定してみたやつ。(きっと一番はやいとおもっていた)
Benchmark_Map/WithLock_____________0-32 16719547 73.34 ns/op 15 B/op 1 allocs/op
Benchmark_Map/Map__________________0-32 28676020 39.15 ns/op 31 B/op 2 allocs/op
Benchmark_Map/MapString____________0-32 33192778 36.80 ns/op 31 B/op 2 allocs/op
Benchmark_Map/RMap_________________0-32 35345018 36.52 ns/op 31 B/op 2 allocs/op
Benchmark_Map/sync.Map_____________0-32 27676826 44.20 ns/op 63 B/op 2 allocs/op
Benchmark_Map/WithLock____________10-32 10637793 118.8 ns/op 15 B/op 1 allocs/op
Benchmark_Map/Map_________________10-32 31788711 36.98 ns/op 33 B/op 3 allocs/op
Benchmark_Map/MapString___________10-32 32384090 34.62 ns/op 32 B/op 2 allocs/op
Benchmark_Map/RMap________________10-32 34530396 35.95 ns/op 35 B/op 2 allocs/op
Benchmark_Map/sync.Map____________10-32 23822056 45.10 ns/op 71 B/op 3 allocs/op
Benchmark_Map/WithLock____________50-32 5387150 214.0 ns/op 15 B/op 1 allocs/op
Benchmark_Map/Map_________________50-32 23859121 42.73 ns/op 48 B/op 3 allocs/op
Benchmark_Map/MapString___________50-32 27855962 37.38 ns/op 38 B/op 3 allocs/op
Benchmark_Map/RMap________________50-32 23870059 49.94 ns/op 62 B/op 3 allocs/op
Benchmark_Map/sync.Map____________50-32 16388367 68.01 ns/op 128 B/op 4 allocs/op
Benchmark_Map/shard_Map___________50-32 26889336 43.88 ns/op 48 B/op 3 allocs/op
Benchmark_Map/shard_sync.Map______50-32 15578756 71.13 ns/op 132 B/op 4 allocs/op
Benchmark_Map/shard_MapString_____50-32 26286573 41.83 ns/op 37 B/op 3 allocs/op
shard はほとんど効果がない。もっと細工がいるのかも。書き込みが多いと lock したほうがいいという記述だけど。それでもやはりsync.Map でも良さそうにみえる。 ふつうにread した場合にも Lock すると Rlock が必要なのでそこはやはりコストがでかそう
RMap が結構かんばっている dirty を read に書き出すときだけ lock になっているのはそれなりに効果がありそう。 RMap だとdirty を探査するのが当然線形探索になるのでそれがきついかなとおもったけどread only でパフォーマンスが一番だったのが意外だったりした