mapをmakeする時の第二引数

[Go6 Advent Calendar 2019](https://qiita.com/advent-calendar/2019/go6)の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)`を指定した場合[^1]、以下の式を満たす最小の`B`をバケット数のlogとして設定します。

[^1]: 第二引数が設定されなかったり、デフォルト値より小さい値が設定された場合は`make_map`が呼ばれます

```math
count \leq 6.5 * 2^B
```

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

この6.5というのは`LoadFactor`と言って、実験的に分かっている数値のようです。
この数値に関する実験結果が[ソースコード](https://github.com/golang/go/blob/daaab44f3124aff61937fa7e118f02d4ff82166c/src/runtime/map.go#L37)に載っていました[^2]。

[^2]: おそらくマップのオーバーヘッドを最小化しつつ、かつヒットするまでのチェック回数とミスするまでのチェック回数を最小化しようとすると、6.5ぐらいになるのだと思われます

```
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                  |

### べき乗

```go
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を突っ込んでいった場合を計測してみます。

### べき乗
```go
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`のところがあります。
これはバケット数がオバーフローしそうになったためであると考えられます[^3]。

[^3]: https://github.com/golang/go/blob/daaab44f3124aff61937fa7e118f02d4ff82166c/src/runtime/map.go#L304

### 指定なし

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

```
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