Go1.9から追加されたsync.Mapのパフォーマンス

Go Advent Calender 2017(その4)の11日目の記事です。

Golangの並行処理では、共有リソースにアクセスする場合は競合が発生しないようにロックを用意する必要があります。

例えば標準のマップの場合、goroutine safeではないため、Write同士が競合したり、Write中にReadが発生した場合はPanicを起こします。 そのため、従来はマップとsync.RWMutexを併用することでロックを用意し、複数goroutineから安全にアクセスできるようにするのが定石でした。

Go1.9からはsync.Mapが標準パッケージ入りし、自前でsync.RWMutexを書かなくともロック付きのマップを使うことができるようになっています。

使い方

以下コードの通り(Playground)。 簡潔でとても使いやすいです。

package main

import (
	"fmt"
	"sync"
)

func main() {
	// Mapを作成
	m := sync.Map{}

	// 保存
	m.Store("hoge", "fuga")

	// 取得
	// 標準のMap同様、キーが存在しなければok == falseとなる
	if v, ok := m.Load("hoge"); ok {
		fmt.Printf("hoge: %s\n", v) // hoge: fuga
	}

	// 新規キーの場合は登録+取得
	// 既存キーの場合は取得のみ(loaded == trueとなる)
	actual, loaded := m.LoadOrStore("hoge", "piyo")
	fmt.Printf("hoge: %s, loaded=%t\n", actual, loaded) // hoge: fuga, loaded=true

	// マップ中の全要素を参照する
	// 引数で渡している関数がfalseを返すとRangeを終了する
	m.Range(func(k, v interface{}) bool {
		fmt.Printf("key: %s, value: %s\n", k, v) // key: hoge, value: fuga
		return true
	})

	// 削除
	m.Delete("hoge")
}

計測

sync.Mapは従来のsync.RWMutexなマップとは異なり、内部で2種類のマップを使用しています。

readOnly

  • ロックが不要なエントリを格納する(キャッシュの役割を担う)
  • atomicで制御されており、readOnly上のエントリであれば、ロック無しで参照・更新が可能
  • readOnly上に存在しないキーの処理要求を受けた場合、dirtyを参照する

dirty

  • ロックが必要なエントリを格納する
  • mutexで制御されており、ロックが必要な処理はdirty上で行う
  • readOnlyでキャッシュミスが多発すると、dirtyはreadOnly化される

公式のベンチマークでは、sync.Mapだけではなくsync.RWMutexのマップも含まれていて、両者を比較することができます。 また、sync.Mapが必ずしも優位というわけではありませんでした。

sync.MapLoadは高速なものの、Storesync.RWMutexよりも若干低速になります。 特にキーが分散するとdirty側の処理が多くなり、readOnlyのatomicが効かなくなるため、二層構造によるオーバヘッドが発生します。

以下は公式ベンチの結果とメモです。 環境はSierra, 1.1 GHz Intel Core m3, 8 GB。

Load

ヒット率に関わらず、sync.Mapの方が高速。 readonlyをロック無しで取得しているためだと思われます。

  • 1023/1024の確率で値が存在する場合にLoadするケース
BenchmarkLoadMostlyHits/*sync_test.RWMutexMap-4          	20000000	       102 ns/op	       7 B/op	       0 allocs/op
BenchmarkLoadMostlyHits/*sync.Map-4                      	30000000	        47.5 ns/op	       7 B/op	       0 allocs/op
  • 1/1024の確率で値が存在する場合にLoadするケース
BenchmarkLoadMostlyMisses/*sync_test.RWMutexMap-4        	20000000	        90.5 ns/op	       7 B/op	       0 allocs/op
BenchmarkLoadMostlyMisses/*sync.Map-4                    	30000000	        35.7 ns/op	       7 B/op	       0 allocs/op

LoadOrStore

Storeとなる可能性がある場合はsync.RWMutexの方が高速。 既存キーのLoadOrStore(一番下の結果)はsync.Mapの方が高速ですが、これは返す値をreadOnlyからロック無しで取得しているためです。

  • 128/256の確率で値が存在する場合に、LoadOrStoreするケース
BenchmarkLoadOrStoreBalanced/*sync_test.RWMutexMap-4     	 2000000	       833 ns/op	      97 B/op	       2 allocs/op
BenchmarkLoadOrStoreBalanced/*sync.Map-4                 	 2000000	      1110 ns/op	      89 B/op	       3 allocs/op
  • 未定義のキーをLoadOrStore(m.LoadOrStore(i, i))
BenchmarkLoadOrStoreUnique/*sync_test.RWMutexMap-4       	 1000000	      1123 ns/op	     178 B/op	       2 allocs/op
BenchmarkLoadOrStoreUnique/*sync.Map-4                   	 1000000	      1444 ns/op	     163 B/op	       4 allocs/op
  • 既存のキーをLoadOrStore(m.LoadOrStore(0, 0))
BenchmarkLoadOrStoreCollision/*sync_test.RWMutexMap-4    	10000000	       150 ns/op	       0 B/op	       0 allocs/op
BenchmarkLoadOrStoreCollision/*sync.Map-4                	50000000	        25.2 ns/op	       0 B/op	       0 allocs/op

Range

sync.Mapの方が高速。 これまでの結果と同じく、readOnlyを参照しているためです。

ただし、readOnlyとdirtyに差異があった場合、dirtyがreadOnlyに昇格した上でRangeが実行されます(sync/map.go#L315)。 頻繁なStoreによりreadOnlyとdirtyに差が出やすいケースでは、パフォーマンスが劣化する可能性がありそうです。

  • 要素数1024のマップを、Rangeで参照
BenchmarkRange/*sync_test.RWMutexMap-4                   	   20000	     94268 ns/op	   16384 B/op	       1 allocs/op
BenchmarkRange/*sync.Map-4                               	  100000	     15142 ns/op	       0 B/op	       0 allocs/op

まとめ

  • sync.Mapにより、自前でsync.RWMutexを書かなくともロック付きのマップを使うことができます
  • キーが分散するStoreが多いケースでは、sync.Mapより従来のsync.RWMutexの方がパフォーマンスが出る可能性があります
  • Loadについては、ロックが発生しないsync.Mapの方が2〜3倍高速でした