LoginSignup
9
2

More than 3 years have passed since last update.

Go6Advent Calendar 2019Day 11
@donko_(donko)inフューチャー株式会社

mapをmakeする時の第二引数

Last updated at Posted at 2019-12-11

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)を指定した場合1、以下の式を満たす最小のBをバケット数のlogとして設定します。

count \leq 6.5 * 2^B

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

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

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

指定なし

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

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

まとめ

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

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

ようにしましょう。

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

最後に

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

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

参考

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

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

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

9
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
9
2