runtime: map key hashing is slow for compound types (array/struct)

[anton-povarov]

It seems that map[[8]byte]int is much slower than map[uint64]int purely because of the time spent on hashing the key.

consider this benchmark

package main

import (
    "testing"

    //
    "reflect"
    "unsafe"
)

func BenchmarkMap1S(b *testing.B) {
    m := make(map[string]int)

    k_tmp := [12]byte{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1}
    k := string(k_tmp[:])
    m[k] = 1

    b.ResetTimer()

    counter := 0
    for i := 0; i < b.N; i++ {
        counter += m[k]
    }
}

func BenchmarkMap1S3U(b *testing.B) {
    m := make(map[string]int)

    k_tmp := [3]uint32{0, 1, 2}
    h := reflect.StringHeader{Data: uintptr(unsafe.Pointer(&k_tmp[0])), Len: len(k_tmp) * int(unsafe.Sizeof(k_tmp[0]))}
    k := *(*string)(unsafe.Pointer(&h))
    m[k] = 1

    b.ResetTimer()

    counter := 0
    for i := 0; i < b.N; i++ {
        hh := reflect.StringHeader{Data: uintptr(unsafe.Pointer(&k_tmp[0])), Len: 12}
        kk := *(*string)(unsafe.Pointer(&hh))
        counter += m[kk]
    }
}
func BenchmarkMap1Str3U(b *testing.B) {
    m := make(map[string]int)

    k_tmp := [3]uint32{0, 1, 2}
    h := (*[12]byte)(unsafe.Pointer(&k_tmp[0]))
    k := string(h[:])
    m[k] = 1

    b.ResetTimer()

    counter := 0
    for i := 0; i < b.N; i++ {
        hh := (*[12]byte)(unsafe.Pointer(&k_tmp[0]))
        kk := string(hh[:])
        counter += m[kk]
    }
}

func BenchmarkMap12C(b *testing.B) {
    m := make(map[[12]byte]int)

    k := [12]byte{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1}
    m[k] = 1

    b.ResetTimer()

    counter := 0
    for i := 0; i < b.N; i++ {
        counter += m[k]
    }
}

func BenchmarkMap3U(b *testing.B) {
    m := make(map[[3]uint32]int)

    k := [3]uint32{0, 1, 2}
    m[k] = 1

    b.ResetTimer()

    counter := 0
    for i := 0; i < b.N; i++ {
        counter += m[k]
    }
}

func BenchmarkMap2L(b *testing.B) {
    m := make(map[[2]uint64]int)

    k := [2]uint64{1234, 456}
    m[k] = 1

    b.ResetTimer()

    counter := 0
    for i := 0; i < b.N; i++ {
        counter += m[k]
    }
}

func BenchmarkMap1L(b *testing.B) {
    m := make(map[uint64]int)

    k := uint64(1234)
    m[k] = 1

    b.ResetTimer()

    counter := 0
    for i := 0; i < b.N; i++ {
        counter += m[k]
    }
}

func BenchmarkMap1K(b *testing.B) {
    m := make(map[interface{}]int)

    k := &struct {
        k interface{}
    }{k: 1234}

    m[k] = 1

    b.ResetTimer()

    counter := 0
    for i := 0; i < b.N; i++ {
        counter += m[k]
    }
}

type M struct {
    k uint64
}

func BenchmarkMap1M(b *testing.B) {
    m := make(map[M]int)

    k := M{1234}

    m[k] = 1

    b.ResetTimer()

    counter := 0
    for i := 0; i < b.N; i++ {
        counter += m[k]
    }
}

func main() {

}

my results for this benchmark are as follows

BenchmarkMap1S-4        200000000                6.36 ns/op            0 B/op          0 allocs/op
BenchmarkMap1S3U-4      200000000                7.56 ns/op            0 B/op          0 allocs/op
BenchmarkMap1Str3U-4    50000000                27.6 ns/op             0 B/op          0 allocs/op
BenchmarkMap12C-4       50000000                27.0 ns/op             0 B/op          0 allocs/op
BenchmarkMap3U-4        50000000                27.3 ns/op             0 B/op          0 allocs/op
BenchmarkMap2L-4        50000000                26.3 ns/op             0 B/op          0 allocs/op
BenchmarkMap1L-4        300000000                5.26 ns/op            0 B/op          0 allocs/op
BenchmarkMap1K-4        50000000                28.0 ns/op             0 B/op          0 allocs/op
BenchmarkMap1M-4        100000000               16.1 ns/op             0 B/op          0 allocs/op

Would love if compiler would recognize that compound types memory layout is flat and hash them as byte arrays.
We currently use workaround like BenchmarkMap1S3U (with map sets constructing real GC visible strings) which is fugly.

tested on go versions 1.4 and 1.5.1

[anton-povarov]

cpu prof for char array test above for example looks like this

antoxa@antoxa-suse:~/_Dev/go/src/antoxa> go test -cpuprofile=cpu.out -bench=BenchmarkMap12C ./1_test.go
testing: warning: no tests to run
PASS
BenchmarkMap12C-4       50000000                27.0 ns/op
ok      command-line-arguments  1.385s
antoxa@antoxa-suse:~/_Dev/go/src/antoxa> go tool pprof main.test cpu.out
Entering interactive mode (type "help" for commands)
(pprof) top
1.37s of 1.37s total (  100%)
Showing top 10 nodes out of 11 (cum >= 1.37s)
      flat  flat%   sum%        cum   cum%
     0.46s 33.58% 33.58%      0.46s 33.58%  runtime.aeshashbody
     0.46s 33.58% 67.15%      1.29s 94.16%  runtime.mapaccess1
     0.18s 13.14% 80.29%      0.66s 48.18%  runtime.memhash
     0.09s  6.57% 86.86%      0.75s 54.74%  runtime.memhash_varlen
     0.08s  5.84% 92.70%      1.37s   100%  command-line-arguments.BenchmarkMap12C
     0.07s  5.11% 97.81%      0.07s  5.11%  runtime.memeqbody
     0.02s  1.46% 99.27%      0.02s  1.46%  runtime.aeshash
     0.01s  0.73%   100%      0.01s  0.73%  runtime.memequal_varlen
         0     0%   100%      1.37s   100%  runtime.goexit
         0     0%   100%      1.37s   100%  testing.(*B).launch

[ianlancetaylor]

CC @randall77

[randall77]

Would love if compiler would recognize that compound types memory layout is flat and hash them as byte arrays.

It does.

The speed difference you're seeing is because there is a special-case fast path for maps with int32, int64, or string keys. For maps of size 1 like you're benchmarking, we don't hash at all. That is not the case for [12]byte or [3]int32 keys.

We might be able to fix your 1M benchmark. We should still use the fast path if you just wrap an int64 in a struct. I thought we did that already, but maybe not.

[mkevac]

[12]byte and [3]int32 is pretty much string in some sense. It's a byte array with length 12. Is it possible to use fast path in these cases?

[randall77]

Not in general. Every special case bloats the binary with additional code, and we don't want to special case all of [12]byte, [13]byte, [14]byte, ...

[anton-povarov]

is it then possible to generalize the fastpath from string-only to ptr+length ?

[randall77]

No. The fast path is not only about hashing, it also includes fast indexing and copy for the specialized types. A [12]byte and a string with 12 bytes in it do not have the same internal representation.

[tildeleb]

Does the fast path work for []byte too? If not, could it?

[davecheney]

Slices may not be map keys.

On Mon, 7 Dec 2015, 18:19 Lawrence E. Bakst [email protected]
wrote:

Does the fast path work for []byte too? If not, could it?

—
Reply to this email directly or view it on GitHub
#13271 (comment).

[randall77]

I'm not sure what you are asking. []byte cannot be a map key. It would be fine to be a map value, any values <=128 bytes can be used and still take advantage of the fast path.

[tildeleb]

Yep, sorry about that. I didn't remember that slices weren't Key Types. I just came back to delete the comment but it's already too late, you guys are fast.

It's too bad though. I have a bunch of hash values I want to store in a map. I guess for now I will cast []byte to string as it's prototype code. I assume that cast has to copy the bytes of the slice to the string so there is an allocation and a copy?

Is there any optimization for struct{} as a value take no memory? In my case I just need to test if the hash is in the map and don't care about the value. I have lots of hashes to store in the map.

[davecheney]

That's OK, it took me a few minutes to remember that restriction. I'm so
used to things just working (tm)

Wrt. var m map[string]T
x := m[string(key)]

Has an optimisation to avoid the copy for the purposes of hashing. I forget
the exact version it went in, I'm going to guess 1.4, but I'm probably
wrong - check the release notes for 1.3-1.5

Note: the optimisation is very specific

s := string(key)
x := m[s]

Will incur a copy as expected.

Thanks

Dave

On Mon, 7 Dec 2015, 19:06 Lawrence E. Bakst [email protected]
wrote:

Yep, sorry about that. I didn't remember that slices weren't Key Types. I
just came back to delete the comment but it's already too late, you guys
are fast.

It's too bad though. I have a bunch of hash values I want to store in a
map. I guess for now I will cast []byte to string as it's prototype code. I
assume that cast has to copy the bytes of the slice to the string so there
is an allocation and a copy?

Is there any optimization for struct{} as a value take no memory? In my
case I just need to test if the hash is in the map and don't care about the
value. I have lots of hashes to store in the map.

—
Reply to this email directly or view it on GitHub
#13271 (comment).

[gopherbot]

CL https://golang.org/cl/17464 mentions this issue.

[tildeleb]

@davecheney thanks for the info on the string cast optimization.