Goのmapはハッシュテーブルで実装されているらしいのですが、
keyによるアクセス速度が気になったので調べてみました
versionは下記です
go version go1.7.5 darwin/amd64
とりあえず公式にbenchがあったので実行してみた
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