Goのmapのkeyによるアクセス速度

Goのmapはハッシュテーブルで実装されているらしいのですが、
keyによるアクセス速度が気になったので調べてみました

versionは下記です
```                                                                                                                                                                        go version go1.7.5 darwin/amd64
```

とりあえず公式にbenchがあったので実行してみた

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

```
BenchmarkHashStringSpeed              100000000           20.1 ns/op         0 B/op          0 allocs/op
BenchmarkHashBytesSpeed                50000000           32.8 ns/op         0 B/op          0 allocs/op
BenchmarkHashInt32Speed               100000000           15.5 ns/op         0 B/op          0 allocs/op
BenchmarkHashInt64Speed               100000000           15.8 ns/op         0 B/op          0 allocs/op
BenchmarkHashStringArraySpeed          30000000           67.5 ns/op         0 B/op          0 allocs/op
BenchmarkMegMap                       100000000           18.7 ns/op         0 B/op          0 allocs/op
BenchmarkMegOneMap                    100000000           11.7 ns/op         0 B/op          0 allocs/op
BenchmarkMegEqMap                         20000          62252 ns/op         0 B/op          0 allocs/op
BenchmarkMegEmptyMap                  500000000           3.49 ns/op         0 B/op          0 allocs/op
BenchmarkSmallStrMap                  100000000           17.9 ns/op         0 B/op          0 allocs/op
BenchmarkMapStringKeysEight_16        100000000           18.0 ns/op         0 B/op          0 allocs/op
BenchmarkMapStringKeysEight_32        100000000           19.0 ns/op         0 B/op          0 allocs/op
BenchmarkMapStringKeysEight_64        100000000           18.9 ns/op         0 B/op          0 allocs/op
BenchmarkMapStringKeysEight_1M        100000000           19.2 ns/op         0 B/op          0 allocs/op
BenchmarkIntMap                       100000000           11.9 ns/op         0 B/op          0 allocs/op
BenchmarkRepeatedLookupStrMapKey32     50000000           26.8 ns/op         0 B/op          0 allocs/op
BenchmarkRepeatedLookupStrMapKey1M        30000          47544 ns/op         0 B/op          0 allocs/op
BenchmarkNewEmptyMap                   30000000           47.5 ns/op         0 B/op          0 allocs/op
BenchmarkNewSmallMap                   10000000            138 ns/op         0 B/op          0 allocs/op
BenchmarkMapIter                       10000000            123 ns/op         0 B/op          0 allocs/op
BenchmarkMapIterEmpty                 100000000           10.7 ns/op         0 B/op          0 allocs/op
BenchmarkSameLengthMap                300000000           6.24 ns/op         0 B/op          0 allocs/op
BenchmarkBigKeyMap                     50000000           33.2 ns/op         0 B/op          0 allocs/op
BenchmarkBigValMap                     30000000           34.4 ns/op         0 B/op          0 allocs/op
BenchmarkSmallKeyMap                   50000000           30.9 ns/op         0 B/op          0 allocs/op
BenchmarkComplexAlgMap                 20000000            100 ns/op         0 B/op          0 allocs/op
```

うーんなるほどint系が早いですね
int8 int16 int を追加してみました

```
func BenchmarkHashInt8Speed(b *testing.B) {
     ints := make([]int8, size)
     for i := 0; i < size; i++ {
          ints[i] = int8(i)
     }
     sum := 0
     m := make(map[int8]int, size)
     for i := 0; i < size; i++ {
          m[ints[i]] = 0
     }
     idx := 0
     b.ResetTimer()
     for i := 0; i < b.N; i++ {
          sum += m[ints[idx]]
          idx++
          if idx == size {
               idx = 0
          }
     }
}

func BenchmarkHashInt16Speed(b *testing.B) {
     ints := make([]int16, size)
     for i := 0; i < size; i++ {
          ints[i] = int16(i)
     }
     sum := 0
     m := make(map[int16]int, size)
     for i := 0; i < size; i++ {
          m[ints[i]] = 0
     }
     idx := 0
     b.ResetTimer()
     for i := 0; i < b.N; i++ {
          sum += m[ints[idx]]
          idx++
          if idx == size {
               idx = 0
          }
     }
}

func BenchmarkHashIntSpeed(b *testing.B) {
     ints := make([]int, size)
     for i := 0; i < size; i++ {
          ints[i] = int(i)
     }
     sum := 0
     m := make(map[int]int, size)
     for i := 0; i < size; i++ {
          m[ints[i]] = 0
     }
     idx := 0
     b.ResetTimer()
     for i := 0; i < b.N; i++ {
          sum += m[ints[idx]]
          idx++
          if idx == size {
               idx = 0
          }
     }
}

func BenchmarkHashInt32Speed(b *testing.B) {
     ints := make([]int32, size)
     for i := 0; i < size; i++ {
          ints[i] = int32(i)
     }
     sum := 0
     m := make(map[int32]int, size)
     for i := 0; i < size; i++ {
          m[ints[i]] = 0
     }
     idx := 0
     b.ResetTimer()
     for i := 0; i < b.N; i++ {
          sum += m[ints[idx]]
          idx++
          if idx == size {
               idx = 0
          }
     }
}

func BenchmarkHashInt64Speed(b *testing.B) {
     ints := make([]int64, size)
     for i := 0; i < size; i++ {
          ints[i] = int64(i)
     }
     sum := 0
     m := make(map[int64]int, size)
     for i := 0; i < size; i++ {
          m[ints[i]] = 0
     }
     idx := 0
     b.ResetTimer()
     for i := 0; i < b.N; i++ {
          sum += m[ints[idx]]
          idx++
          if idx == size {
               idx = 0
          }
     }
}
```

```
BenchmarkHashInt8Speed         50000000                34.4 ns/op            0 B/op          0 allocs/op
BenchmarkHashInt16Speed        50000000                34.5 ns/op            0 B/op          0 allocs/op
BenchmarkHashIntSpeed         200000000                7.49 ns/op            0 B/op          0 allocs/op
BenchmarkHashInt32Speed       200000000                7.22 ns/op            0 B/op          0 allocs/op
BenchmarkHashInt64Speed       200000000                7.24 ns/op            0 B/op          0 allocs/op
```

差が出ました int8 int16 は遅いです

自作structと多次元mapとの比較もしてみました

```
type field2Key struct {
     a, b int
}

func BenchmarkField2StructMap(b *testing.B) {
     m := make(map[field2Key]bool)
     m[field2Key{a: 1, b: 2}] = true

     for i := 0; i < b.N; i++ {
          _ = m[field2Key{a: 1, b: 2}]
     }
}

func BenchmarkDimensional2Map(b *testing.B) {
     m := make(map[int]map[int]bool)
     m[1] = make(map[int]bool)
     m[1][2] = true

     for i := 0; i < b.N; i++ {
          _ = m[1][2]
     }
}
```
 

```
BenchmarkField2StructMap       50000000               32.9 ns/op             0 B/op          0 allocs/op
BenchmarkDimensional2Map      100000000               10.8 ns/op             0 B/op          0 allocs/op
```

多次元mapのほうが早いようです
ただstructをkeyにするほうが扱いやすいですね

ちなみにfieldの型をsliceにしたらどうかなと思ってやってみたらエラーになりました

```
type fieldSlice struct {
     a []int
}

func BenchmarkFieldSliceMap(b *testing.B) {
     m := make(map[fieldSlice]bool)
     m[fieldSlice{a: []int{1, 2}}] = true

     for i := 0; i < b.N; i++ {
          _ = m[fieldSlice{a: []int{1, 2}}]
     }
}
```

```
invalid map key type fieldSlice
```