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 でパフォーマンスが一番だったのが意外だったりした