Go6 Advent Calendar 2019の11日目の記事になります。

はじめに

この間のGoConferenceで、mapをmakeする時に第二引数を指定できることを知ったので、これを機にGoの組み込み関数を読んでみることにしました。また、このmake関数の利用方法についても検討してみます。

make関数

まずは、make関数をおさらいしておきましょう。
buildinパッケージ配下の関数で、slice, map, chanのみがこの関数を用いてアロケート、初期化を行うことができます。実装はruntime/map.goにあります。

https://golang.org/pkg/builtin/#make

makeの第二引数

makeの実装を読んでみると、第二引数を指定しなかった場合、64bit環境では48byte, 32bit環境では28byteが確保されます。

第二引数に数値count(>8)を指定した場合¹、以下の式を満たす最小のBをバケット数のlogとして設定します。

count \leq 6.5 * 2^B

つまり、バケット数は$2^B$となります。

この6.5というのはLoadFactorと言って、実験的に分かっている数値のようです。
この数値に関する実験結果がソースコードに載っていました²。

loadFactor    %overflow  bytes/entry     hitprobe    missprobe
      4.00         2.13        20.77         3.00         4.00
      4.50         4.05        17.30         3.25         4.50
      5.00         6.85        14.77         3.50         5.00
      5.50        10.55        12.94         3.75         5.50
      6.00        15.27        11.67         4.00         6.00
      6.50        20.90        10.79         4.25         6.50
      7.00        27.14        10.15         4.50         7.00
      7.50        34.03         9.73         4.75         7.50
      8.00        41.10         9.40         5.00         8.00

ベンチマーク

込み入った実装の話はともかく、測ってみましょう。PCのスペックは以下の通りです。

OS	Mac OS X 10.15.1
Memory	16 GB
Architecture	x86_64
CPU	Dual-Core Intel Core i5
Processor Speed	3.1GHz

べき乗

func BenchmarkMakeInt64Cap(b *testing.B) {
	for i := 1; i < (1 << 16); i *= 2 {
		b.ResetTimer()
		b.Run(fmt.Sprintf("bench_%d", i), func(b *testing.B) {
			for j := 0; j < b.N; j++ {
				Int64X = make(map[int64]struct{}, i)
			}
		})
	}
}

BenchmarkMakeInt64Cap/bench_1-4         	28402369	        41.6 ns/op	      48 B/op	       1 allocs/op
BenchmarkMakeInt64Cap/bench_2-4         	29772153	        43.1 ns/op	      48 B/op	       1 allocs/op
BenchmarkMakeInt64Cap/bench_4-4         	27501942	        56.4 ns/op	      48 B/op	       1 allocs/op
BenchmarkMakeInt64Cap/bench_8-4         	29967360	        52.7 ns/op	      48 B/op	       1 allocs/op
BenchmarkMakeInt64Cap/bench_16-4        	 8653381	       157 ns/op	     368 B/op	       2 allocs/op
BenchmarkMakeInt64Cap/bench_32-4        	 7163944	       208 ns/op	     688 B/op	       2 allocs/op
BenchmarkMakeInt64Cap/bench_64-4        	 3039774	       376 ns/op	    1488 B/op	       3 allocs/op
BenchmarkMakeInt64Cap/bench_128-4       	 2910937	       417 ns/op	    3152 B/op	       3 allocs/op
BenchmarkMakeInt64Cap/bench_256-4       	 1599004	       893 ns/op	    6224 B/op	       3 allocs/op
BenchmarkMakeInt64Cap/bench_512-4       	 1000000	      1202 ns/op	   10960 B/op	       3 allocs/op
BenchmarkMakeInt64Cap/bench_1024-4      	  480177	      2138 ns/op	   21840 B/op	       3 allocs/op
BenchmarkMakeInt64Cap/bench_2048-4      	  230806	      5414 ns/op	   49232 B/op	       3 allocs/op
BenchmarkMakeInt64Cap/bench_4096-4      	  144682	      9290 ns/op	   90192 B/op	       3 allocs/op
BenchmarkMakeInt64Cap/bench_8192-4      	   77228	     17512 ns/op	  180304 B/op	       3 allocs/op
BenchmarkMakeInt64Cap/bench_16384-4     	   34556	     42192 ns/op	  352336 B/op	       3 allocs/op
BenchmarkMakeInt64Cap/bench_32768-4     	   13330	     77874 ns/op	  696402 B/op	       3 allocs/op

等差

8-16を抜き出してみました。

BenchmarkMakeInt64Cap/bench_8-4         	29940098	        40.5 ns/op	      48 B/op	       1 allocs/op
BenchmarkMakeInt64Cap/bench_9-4         	13250494	        87.9 ns/op	     208 B/op	       2 allocs/op
BenchmarkMakeInt64Cap/bench_10-4        	14729614	        83.2 ns/op	     208 B/op	       2 allocs/op
BenchmarkMakeInt64Cap/bench_11-4        	13443326	        84.9 ns/op	     208 B/op	       2 allocs/op
BenchmarkMakeInt64Cap/bench_12-4        	14355352	        85.5 ns/op	     208 B/op	       2 allocs/op
BenchmarkMakeInt64Cap/bench_13-4        	13879141	       103 ns/op	     208 B/op	       2 allocs/op
BenchmarkMakeInt64Cap/bench_14-4        	10961332	       117 ns/op	     368 B/op	       2 allocs/op
BenchmarkMakeInt64Cap/bench_15-4        	 9795126	       179 ns/op	     368 B/op	       2 allocs/op
BenchmarkMakeInt64Cap/bench_16-4        	 8644429	       197 ns/op	     368 B/op	       2 allocs/op

やはりバケット数が切り替わる時に時間がかかっています。
第二引数の値が8と9, 12と13の間を見ても顕著です。

指定なし

BenchmarkMakeInt64CapNormal-4           32085063                41.8 ns/op            48 B/op          1 allocs/op

key-valueを入れていく場合

次は第二引数を指定して作成したmapに対して、Key/Valueを突っ込んでいった場合を計測してみます。

べき乗

func BenchmarkInt64_Use(b *testing.B) {
	for cap := 0; cap < 20; cap++ {
		Int64X = make(map[int64]struct{}, 1<<cap)
		b.ResetTimer()
		b.Run(fmt.Sprintf("bench_cap%d", 1<<cap), func(b *testing.B) {
			for i := 0; i < b.N; i++ {
				Int64X[int64(i)] = struct{}{}
			}
		})
	}
}

goos: darwin
goarch: amd64
pkg: exp
BenchmarkInt64_Use/bench_cap1-4         	 8799891	       296 ns/op	      39 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap2-4         	 8789410	       201 ns/op	      40 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap4-4         	11362676	       188 ns/op	      17 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap8-4         	11531607	       163 ns/op	      16 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap16-4        	 6192375	       204 ns/op	      26 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap32-4        	 6534572	       155 ns/op	      25 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap64-4        	 9086074	       234 ns/op	      38 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap128-4       	 9732811	       144 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap256-4       	 6139575	       200 ns/op	      26 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap512-4       	 8514468	       219 ns/op	      41 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap1024-4      	 7699090	       320 ns/op	      45 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap2048-4      	 6927254	       168 ns/op	      50 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap4096-4      	 8979837	       245 ns/op	      39 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap8192-4      	 7255461	       154 ns/op	      26 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap16384-4     	 7960039	       211 ns/op	      44 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap32768-4     	10175954	       123 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap65536-4     	 7713075	       196 ns/op	      45 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap131072-4    	 8026257	       235 ns/op	      43 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap262144-4    	 3203480	       381 ns/op	      18 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap524288-4    	10070474	       157 ns/op	      18 B/op	       0 allocs/op
PASS
ok  	exp	49.156s

等差

8-16だけ抜き出します。

BenchmarkInt64_Use/bench_cap8-4         	 4403760	       247 ns/op	      21 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap9-4         	 5703932	       247 ns/op	      27 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap10-4        	 9316352	       211 ns/op	      37 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap11-4        	 7860754	       261 ns/op	      44 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap12-4        	 5210029	       504 ns/op	       0 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap13-4        	 5197764	       236 ns/op	      29 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap14-4        	 5198084	       193 ns/op	      29 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap15-4        	 6422066	       254 ns/op	      25 B/op	       0 allocs/op
BenchmarkInt64_Use/bench_cap16-4        	 5074384	       220 ns/op	      29 B/op	       0 allocs/op

時々、実行あたりのメモリ割当が0Bのところがあります。
これはバケット数がオバーフローしそうになったためであると考えられます³。

指定なし

結構ブレが大きかったので、これは参考までに。

BenchmarkInt64_Use_Normal-4      6892214               175 ns/op              57 B/op          0 allocs/op

まとめ

makeでmapを作成する時のコストの方が目に着きます。
makeによる初期化については、

特段、初期化時にでかいマップを作成しなくて良いならば、make関数の第二引数を指定しなくていい
使うにしても、作成されるバケット数を意識する

ようにしましょう。

データ数がある程度予測可能であるならば、それに応じて第二引数を調整するとよいのではないかと思います。
（初期化のオーバーヘッドとの相談にはなりますが。）
単純にデータ数を第二引数に指定してmakeすると、実はバケット数が増えていなかったり、ちょうどバケットが増えるような値を指定したりすることで、思わぬパフォーマンス低下に繋がる可能性があるので、使う時には注意が必要です。

最後に

Goのマップの実装は結構長く、また難しい部分（例えば、LoadFactorやhashGrow）もあるので、今回は飛ばし飛ばし読んでいきました。
機会があれば詳細な実装・ロジックについても記事を出したいと思います。

また、間違い・ご指摘等ありましたら、コメントいただけると幸いです。

参考

https://github.com/golang/go/blob/master/src/runtime/map.go

第二引数が設定されなかったり、デフォルト値より小さい値が設定された場合はmake_mapが呼ばれます ↩
おそらくマップのオーバーヘッドを最小化しつつ、かつヒットするまでのチェック回数とミスするまでのチェック回数を最小化しようとすると、6.5ぐらいになるのだと思われます ↩
https://github.com/golang/go/blob/daaab44f3124aff61937fa7e118f02d4ff82166c/src/runtime/map.go#L304 ↩