From 36f30ba289e31df033d100b2adb4eaf557f05a34 Mon Sep 17 00:00:00 2001 From: Keith Randall Date: Tue, 6 Aug 2019 15:22:51 -0700 Subject: cmd/compile,runtime: generate hash functions only for types which are map keys MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Right now we generate hash functions for all types, just in case they are used as map keys. That's a lot of wasted effort and binary size for types which will never be used as a map key. Instead, generate hash functions only for types that we know are map keys. Just doing that is a bit too simple, since maps with an interface type as a key might have to hash any concrete key type that implements that interface. So for that case, implement hashing of such types at runtime (instead of with generated code). It will be slower, but only for maps with interface types as keys, and maybe only a bit slower as the aeshash time probably dominates the dispatch time. Reorg where we keep the equals and hash functions. Move the hash function from the key type to the map type, saving a field in every non-map type. That leaves only one function in the alg structure, so get rid of that and just keep the equal function in the type descriptor itself. cmd/go now has 10 generated hash functions, instead of 504. Makes cmd/go 1.0% smaller. Update #6853. Speed on non-interface keys is unchanged. Speed on interface keys is ~20% slower: name old time/op new time/op delta MapInterfaceString-8 23.0ns ±21% 27.6ns ±14% +20.01% (p=0.002 n=10+10) MapInterfacePtr-8 19.4ns ±16% 23.7ns ± 7% +22.48% (p=0.000 n=10+8) Change-Id: I7c2e42292a46b5d4e288aaec4029bdbb01089263 Reviewed-on: https://go-review.googlesource.com/c/go/+/191198 Run-TryBot: Keith Randall TryBot-Result: Gobot Gobot Reviewed-by: Martin Möhrmann --- src/runtime/alg.go | 121 ++++++++++++++++++++++++-------------- src/runtime/chan.go | 2 +- src/runtime/map.go | 57 +++++++----------- src/runtime/map_benchmark_test.go | 30 ++++++++++ src/runtime/map_fast32.go | 18 +++--- src/runtime/map_fast64.go | 18 +++--- src/runtime/map_faststr.go | 14 ++--- src/runtime/map_test.go | 71 ++++++++++++++++++++-- src/runtime/type.go | 31 +++++++--- 9 files changed, 244 insertions(+), 118 deletions(-) (limited to 'src/runtime') diff --git a/src/runtime/alg.go b/src/runtime/alg.go index 57306f81d9..935d45d503 100644 --- a/src/runtime/alg.go +++ b/src/runtime/alg.go @@ -34,17 +34,6 @@ const ( alg_max ) -// typeAlg is also copied/used in reflect/type.go. -// keep them in sync. -type typeAlg struct { - // function for hashing objects of this type - // (ptr to object, seed) -> hash - hash func(unsafe.Pointer, uintptr) uintptr - // function for comparing objects of this type - // (ptr to object A, ptr to object B) -> ==? - equal func(unsafe.Pointer, unsafe.Pointer) bool -} - func memhash0(p unsafe.Pointer, h uintptr) uintptr { return h } @@ -68,23 +57,9 @@ func memhash_varlen(p unsafe.Pointer, h uintptr) uintptr { return memhash(p, h, size) } -var algarray = [alg_max]typeAlg{ - alg_NOEQ: {nil, nil}, - alg_MEM0: {memhash0, memequal0}, - alg_MEM8: {memhash8, memequal8}, - alg_MEM16: {memhash16, memequal16}, - alg_MEM32: {memhash32, memequal32}, - alg_MEM64: {memhash64, memequal64}, - alg_MEM128: {memhash128, memequal128}, - alg_STRING: {strhash, strequal}, - alg_INTER: {interhash, interequal}, - alg_NILINTER: {nilinterhash, nilinterequal}, - alg_FLOAT32: {f32hash, f32equal}, - alg_FLOAT64: {f64hash, f64equal}, - alg_CPLX64: {c64hash, c64equal}, - alg_CPLX128: {c128hash, c128equal}, -} - +// runtime variable to check if the processor we're running on +// actually supports the instructions used by the AES-based +// hash implementation. var useAeshash bool // in asm_*.s @@ -144,14 +119,17 @@ func interhash(p unsafe.Pointer, h uintptr) uintptr { return h } t := tab._type - fn := t.alg.hash - if fn == nil { + if t.equal == nil { + // Check hashability here. We could do this check inside + // typehash, but we want to report the topmost type in + // the error text (e.g. in a struct with a field of slice type + // we want to report the struct, not the slice). panic(errorString("hash of unhashable type " + t.string())) } if isDirectIface(t) { - return c1 * fn(unsafe.Pointer(&a.data), h^c0) + return c1 * typehash(t, unsafe.Pointer(&a.data), h^c0) } else { - return c1 * fn(a.data, h^c0) + return c1 * typehash(t, a.data, h^c0) } } @@ -161,15 +139,72 @@ func nilinterhash(p unsafe.Pointer, h uintptr) uintptr { if t == nil { return h } - fn := t.alg.hash - if fn == nil { + if t.equal == nil { + // See comment in interhash above. panic(errorString("hash of unhashable type " + t.string())) } if isDirectIface(t) { - return c1 * fn(unsafe.Pointer(&a.data), h^c0) + return c1 * typehash(t, unsafe.Pointer(&a.data), h^c0) } else { - return c1 * fn(a.data, h^c0) + return c1 * typehash(t, a.data, h^c0) + } +} + +// typehash computes the hash of the object of type t at address p. +// h is the seed. +// This function is seldom used. Most maps use for hashing either +// fixed functions (e.g. f32hash) or compiler-generated functions +// (e.g. for a type like struct { x, y string }). This implementation +// is slower but more general and is used for hashing interface types +// (called from interhash or nilinterhash, above) or for hashing in +// maps generated by reflect.MapOf (reflect_typehash, below). +func typehash(t *_type, p unsafe.Pointer, h uintptr) uintptr { + if t.tflag&tflagRegularMemory != 0 { + return memhash(p, h, t.size) } + switch t.kind & kindMask { + case kindFloat32: + return f32hash(p, h) + case kindFloat64: + return f64hash(p, h) + case kindComplex64: + return c64hash(p, h) + case kindComplex128: + return c128hash(p, h) + case kindString: + return strhash(p, h) + case kindInterface: + i := (*interfacetype)(unsafe.Pointer(t)) + if len(i.mhdr) == 0 { + return nilinterhash(p, h) + } + return interhash(p, h) + case kindArray: + a := (*arraytype)(unsafe.Pointer(t)) + for i := uintptr(0); i < a.len; i++ { + h = typehash(a.elem, add(p, i*a.elem.size), h) + } + return h + case kindStruct: + s := (*structtype)(unsafe.Pointer(t)) + for _, f := range s.fields { + // TODO: maybe we could hash several contiguous fields all at once. + if f.name.isBlank() { + continue + } + h = typehash(f.typ, add(p, f.offset()), h) + } + return h + default: + // Should never happen, as typehash should only be called + // with comparable types. + panic(errorString("hash of unhashable type " + t.string())) + } +} + +//go:linkname reflect_typehash reflect.typehash +func reflect_typehash(t *_type, p unsafe.Pointer, h uintptr) uintptr { + return typehash(t, p, h) } func memequal0(p, q unsafe.Pointer) bool { @@ -219,7 +254,7 @@ func efaceeq(t *_type, x, y unsafe.Pointer) bool { if t == nil { return true } - eq := t.alg.equal + eq := t.equal if eq == nil { panic(errorString("comparing uncomparable type " + t.string())) } @@ -236,7 +271,7 @@ func ifaceeq(tab *itab, x, y unsafe.Pointer) bool { return true } t := tab._type - eq := t.alg.equal + eq := t.equal if eq == nil { panic(errorString("comparing uncomparable type " + t.string())) } @@ -249,7 +284,7 @@ func ifaceeq(tab *itab, x, y unsafe.Pointer) bool { // Testing adapters for hash quality tests (see hash_test.go) func stringHash(s string, seed uintptr) uintptr { - return algarray[alg_STRING].hash(noescape(unsafe.Pointer(&s)), seed) + return strhash(noescape(unsafe.Pointer(&s)), seed) } func bytesHash(b []byte, seed uintptr) uintptr { @@ -258,21 +293,21 @@ func bytesHash(b []byte, seed uintptr) uintptr { } func int32Hash(i uint32, seed uintptr) uintptr { - return algarray[alg_MEM32].hash(noescape(unsafe.Pointer(&i)), seed) + return memhash32(noescape(unsafe.Pointer(&i)), seed) } func int64Hash(i uint64, seed uintptr) uintptr { - return algarray[alg_MEM64].hash(noescape(unsafe.Pointer(&i)), seed) + return memhash64(noescape(unsafe.Pointer(&i)), seed) } func efaceHash(i interface{}, seed uintptr) uintptr { - return algarray[alg_NILINTER].hash(noescape(unsafe.Pointer(&i)), seed) + return nilinterhash(noescape(unsafe.Pointer(&i)), seed) } func ifaceHash(i interface { F() }, seed uintptr) uintptr { - return algarray[alg_INTER].hash(noescape(unsafe.Pointer(&i)), seed) + return interhash(noescape(unsafe.Pointer(&i)), seed) } const hashRandomBytes = sys.PtrSize / 4 * 64 diff --git a/src/runtime/chan.go b/src/runtime/chan.go index 8334c1ebba..2162c34a12 100644 --- a/src/runtime/chan.go +++ b/src/runtime/chan.go @@ -111,7 +111,7 @@ func makechan(t *chantype, size int) *hchan { c.dataqsiz = uint(size) if debugChan { - print("makechan: chan=", c, "; elemsize=", elem.size, "; elemalg=", elem.alg, "; dataqsiz=", size, "\n") + print("makechan: chan=", c, "; elemsize=", elem.size, "; dataqsiz=", size, "\n") } return c } diff --git a/src/runtime/map.go b/src/runtime/map.go index 4861cf08db..e456c32556 100644 --- a/src/runtime/map.go +++ b/src/runtime/map.go @@ -403,15 +403,14 @@ func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { } if h == nil || h.count == 0 { if t.hashMightPanic() { - t.key.alg.hash(key, 0) // see issue 23734 + t.hasher(key, 0) // see issue 23734 } return unsafe.Pointer(&zeroVal[0]) } if h.flags&hashWriting != 0 { throw("concurrent map read and map write") } - alg := t.key.alg - hash := alg.hash(key, uintptr(h.hash0)) + hash := t.hasher(key, uintptr(h.hash0)) m := bucketMask(h.B) b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))) if c := h.oldbuckets; c != nil { @@ -438,7 +437,7 @@ bucketloop: if t.indirectkey() { k = *((*unsafe.Pointer)(k)) } - if alg.equal(key, k) { + if t.key.equal(key, k) { e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) if t.indirectelem() { e = *((*unsafe.Pointer)(e)) @@ -462,15 +461,14 @@ func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) } if h == nil || h.count == 0 { if t.hashMightPanic() { - t.key.alg.hash(key, 0) // see issue 23734 + t.hasher(key, 0) // see issue 23734 } return unsafe.Pointer(&zeroVal[0]), false } if h.flags&hashWriting != 0 { throw("concurrent map read and map write") } - alg := t.key.alg - hash := alg.hash(key, uintptr(h.hash0)) + hash := t.hasher(key, uintptr(h.hash0)) m := bucketMask(h.B) b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize))) if c := h.oldbuckets; c != nil { @@ -497,7 +495,7 @@ bucketloop: if t.indirectkey() { k = *((*unsafe.Pointer)(k)) } - if alg.equal(key, k) { + if t.key.equal(key, k) { e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) if t.indirectelem() { e = *((*unsafe.Pointer)(e)) @@ -514,8 +512,7 @@ func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe if h == nil || h.count == 0 { return nil, nil } - alg := t.key.alg - hash := alg.hash(key, uintptr(h.hash0)) + hash := t.hasher(key, uintptr(h.hash0)) m := bucketMask(h.B) b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize))) if c := h.oldbuckets; c != nil { @@ -542,7 +539,7 @@ bucketloop: if t.indirectkey() { k = *((*unsafe.Pointer)(k)) } - if alg.equal(key, k) { + if t.key.equal(key, k) { e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) if t.indirectelem() { e = *((*unsafe.Pointer)(e)) @@ -587,10 +584,9 @@ func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { if h.flags&hashWriting != 0 { throw("concurrent map writes") } - alg := t.key.alg - hash := alg.hash(key, uintptr(h.hash0)) + hash := t.hasher(key, uintptr(h.hash0)) - // Set hashWriting after calling alg.hash, since alg.hash may panic, + // Set hashWriting after calling t.hasher, since t.hasher may panic, // in which case we have not actually done a write. h.flags ^= hashWriting @@ -627,7 +623,7 @@ bucketloop: if t.indirectkey() { k = *((*unsafe.Pointer)(k)) } - if !alg.equal(key, k) { + if !t.key.equal(key, k) { continue } // already have a mapping for key. Update it. @@ -698,7 +694,7 @@ func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { } if h == nil || h.count == 0 { if t.hashMightPanic() { - t.key.alg.hash(key, 0) // see issue 23734 + t.hasher(key, 0) // see issue 23734 } return } @@ -706,10 +702,9 @@ func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { throw("concurrent map writes") } - alg := t.key.alg - hash := alg.hash(key, uintptr(h.hash0)) + hash := t.hasher(key, uintptr(h.hash0)) - // Set hashWriting after calling alg.hash, since alg.hash may panic, + // Set hashWriting after calling t.hasher, since t.hasher may panic, // in which case we have not actually done a write (delete). h.flags ^= hashWriting @@ -734,7 +729,7 @@ search: if t.indirectkey() { k2 = *((*unsafe.Pointer)(k2)) } - if !alg.equal(key, k2) { + if !t.key.equal(key, k2) { continue } // Only clear key if there are pointers in it. @@ -862,7 +857,6 @@ func mapiternext(it *hiter) { b := it.bptr i := it.i checkBucket := it.checkBucket - alg := t.key.alg next: if b == nil { @@ -916,10 +910,10 @@ next: // through the oldbucket, skipping any keys that will go // to the other new bucket (each oldbucket expands to two // buckets during a grow). - if t.reflexivekey() || alg.equal(k, k) { + if t.reflexivekey() || t.key.equal(k, k) { // If the item in the oldbucket is not destined for // the current new bucket in the iteration, skip it. - hash := alg.hash(k, uintptr(h.hash0)) + hash := t.hasher(k, uintptr(h.hash0)) if hash&bucketMask(it.B) != checkBucket { continue } @@ -937,7 +931,7 @@ next: } } if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) || - !(t.reflexivekey() || alg.equal(k, k)) { + !(t.reflexivekey() || t.key.equal(k, k)) { // This is the golden data, we can return it. // OR // key!=key, so the entry can't be deleted or updated, so we can just return it. @@ -1174,8 +1168,8 @@ func evacuate(t *maptype, h *hmap, oldbucket uintptr) { if !h.sameSizeGrow() { // Compute hash to make our evacuation decision (whether we need // to send this key/elem to bucket x or bucket y). - hash := t.key.alg.hash(k2, uintptr(h.hash0)) - if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.alg.equal(k2, k2) { + hash := t.hasher(k2, uintptr(h.hash0)) + if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) { // If key != key (NaNs), then the hash could be (and probably // will be) entirely different from the old hash. Moreover, // it isn't reproducible. Reproducibility is required in the @@ -1269,16 +1263,12 @@ func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) { } } -func ismapkey(t *_type) bool { - return t.alg.hash != nil -} - // Reflect stubs. Called from ../reflect/asm_*.s //go:linkname reflect_makemap reflect.makemap func reflect_makemap(t *maptype, cap int) *hmap { // Check invariants and reflects math. - if !ismapkey(t.key) { + if t.key.equal == nil { throw("runtime.reflect_makemap: unsupported map key type") } if t.key.size > maxKeySize && (!t.indirectkey() || t.keysize != uint8(sys.PtrSize)) || @@ -1381,10 +1371,5 @@ func reflectlite_maplen(h *hmap) int { return h.count } -//go:linkname reflect_ismapkey reflect.ismapkey -func reflect_ismapkey(t *_type) bool { - return ismapkey(t) -} - const maxZero = 1024 // must match value in cmd/compile/internal/gc/walk.go:zeroValSize var zeroVal [maxZero]byte diff --git a/src/runtime/map_benchmark_test.go b/src/runtime/map_benchmark_test.go index d37dadcb56..cf04ead115 100644 --- a/src/runtime/map_benchmark_test.go +++ b/src/runtime/map_benchmark_test.go @@ -483,3 +483,33 @@ func BenchmarkMapStringConversion(b *testing.B) { }) } } + +var BoolSink bool + +func BenchmarkMapInterfaceString(b *testing.B) { + m := map[interface{}]bool{} + + for i := 0; i < 100; i++ { + m[fmt.Sprintf("%d", i)] = true + } + + key := (interface{})("A") + b.ResetTimer() + for i := 0; i < b.N; i++ { + BoolSink = m[key] + } +} +func BenchmarkMapInterfacePtr(b *testing.B) { + m := map[interface{}]bool{} + + for i := 0; i < 100; i++ { + i := i + m[&i] = true + } + + key := new(int) + b.ResetTimer() + for i := 0; i < b.N; i++ { + BoolSink = m[key] + } +} diff --git a/src/runtime/map_fast32.go b/src/runtime/map_fast32.go index 0ab75cad34..534454f3ad 100644 --- a/src/runtime/map_fast32.go +++ b/src/runtime/map_fast32.go @@ -25,7 +25,7 @@ func mapaccess1_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer { // One-bucket table. No need to hash. b = (*bmap)(h.buckets) } else { - hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) + hash := t.hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) m := bucketMask(h.B) b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))) if c := h.oldbuckets; c != nil { @@ -65,7 +65,7 @@ func mapaccess2_fast32(t *maptype, h *hmap, key uint32) (unsafe.Pointer, bool) { // One-bucket table. No need to hash. b = (*bmap)(h.buckets) } else { - hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) + hash := t.hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) m := bucketMask(h.B) b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))) if c := h.oldbuckets; c != nil { @@ -100,9 +100,9 @@ func mapassign_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer { if h.flags&hashWriting != 0 { throw("concurrent map writes") } - hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) + hash := t.hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - // Set hashWriting after calling alg.hash for consistency with mapassign. + // Set hashWriting after calling t.hasher for consistency with mapassign. h.flags ^= hashWriting if h.buckets == nil { @@ -190,9 +190,9 @@ func mapassign_fast32ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer if h.flags&hashWriting != 0 { throw("concurrent map writes") } - hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) + hash := t.hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - // Set hashWriting after calling alg.hash for consistency with mapassign. + // Set hashWriting after calling t.hasher for consistency with mapassign. h.flags ^= hashWriting if h.buckets == nil { @@ -281,9 +281,9 @@ func mapdelete_fast32(t *maptype, h *hmap, key uint32) { throw("concurrent map writes") } - hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) + hash := t.hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - // Set hashWriting after calling alg.hash for consistency with mapdelete + // Set hashWriting after calling t.hasher for consistency with mapdelete h.flags ^= hashWriting bucket := hash & bucketMask(h.B) @@ -400,7 +400,7 @@ func evacuate_fast32(t *maptype, h *hmap, oldbucket uintptr) { if !h.sameSizeGrow() { // Compute hash to make our evacuation decision (whether we need // to send this key/elem to bucket x or bucket y). - hash := t.key.alg.hash(k, uintptr(h.hash0)) + hash := t.hasher(k, uintptr(h.hash0)) if hash&newbit != 0 { useY = 1 } diff --git a/src/runtime/map_fast64.go b/src/runtime/map_fast64.go index 4d420e7477..1669c7cfe9 100644 --- a/src/runtime/map_fast64.go +++ b/src/runtime/map_fast64.go @@ -25,7 +25,7 @@ func mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer { // One-bucket table. No need to hash. b = (*bmap)(h.buckets) } else { - hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) + hash := t.hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) m := bucketMask(h.B) b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))) if c := h.oldbuckets; c != nil { @@ -65,7 +65,7 @@ func mapaccess2_fast64(t *maptype, h *hmap, key uint64) (unsafe.Pointer, bool) { // One-bucket table. No need to hash. b = (*bmap)(h.buckets) } else { - hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) + hash := t.hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) m := bucketMask(h.B) b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))) if c := h.oldbuckets; c != nil { @@ -100,9 +100,9 @@ func mapassign_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer { if h.flags&hashWriting != 0 { throw("concurrent map writes") } - hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) + hash := t.hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - // Set hashWriting after calling alg.hash for consistency with mapassign. + // Set hashWriting after calling t.hasher for consistency with mapassign. h.flags ^= hashWriting if h.buckets == nil { @@ -190,9 +190,9 @@ func mapassign_fast64ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer if h.flags&hashWriting != 0 { throw("concurrent map writes") } - hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) + hash := t.hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - // Set hashWriting after calling alg.hash for consistency with mapassign. + // Set hashWriting after calling t.hasher for consistency with mapassign. h.flags ^= hashWriting if h.buckets == nil { @@ -281,9 +281,9 @@ func mapdelete_fast64(t *maptype, h *hmap, key uint64) { throw("concurrent map writes") } - hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) + hash := t.hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - // Set hashWriting after calling alg.hash for consistency with mapdelete + // Set hashWriting after calling t.hasher for consistency with mapdelete h.flags ^= hashWriting bucket := hash & bucketMask(h.B) @@ -400,7 +400,7 @@ func evacuate_fast64(t *maptype, h *hmap, oldbucket uintptr) { if !h.sameSizeGrow() { // Compute hash to make our evacuation decision (whether we need // to send this key/elem to bucket x or bucket y). - hash := t.key.alg.hash(k, uintptr(h.hash0)) + hash := t.hasher(k, uintptr(h.hash0)) if hash&newbit != 0 { useY = 1 } diff --git a/src/runtime/map_faststr.go b/src/runtime/map_faststr.go index 069994f1b7..069cda6554 100644 --- a/src/runtime/map_faststr.go +++ b/src/runtime/map_faststr.go @@ -76,7 +76,7 @@ func mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer { return unsafe.Pointer(&zeroVal[0]) } dohash: - hash := t.key.alg.hash(noescape(unsafe.Pointer(&ky)), uintptr(h.hash0)) + hash := t.hasher(noescape(unsafe.Pointer(&ky)), uintptr(h.hash0)) m := bucketMask(h.B) b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))) if c := h.oldbuckets; c != nil { @@ -171,7 +171,7 @@ func mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool) { return unsafe.Pointer(&zeroVal[0]), false } dohash: - hash := t.key.alg.hash(noescape(unsafe.Pointer(&ky)), uintptr(h.hash0)) + hash := t.hasher(noescape(unsafe.Pointer(&ky)), uintptr(h.hash0)) m := bucketMask(h.B) b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))) if c := h.oldbuckets; c != nil { @@ -211,9 +211,9 @@ func mapassign_faststr(t *maptype, h *hmap, s string) unsafe.Pointer { throw("concurrent map writes") } key := stringStructOf(&s) - hash := t.key.alg.hash(noescape(unsafe.Pointer(&s)), uintptr(h.hash0)) + hash := t.hasher(noescape(unsafe.Pointer(&s)), uintptr(h.hash0)) - // Set hashWriting after calling alg.hash for consistency with mapassign. + // Set hashWriting after calling t.hasher for consistency with mapassign. h.flags ^= hashWriting if h.buckets == nil { @@ -307,9 +307,9 @@ func mapdelete_faststr(t *maptype, h *hmap, ky string) { } key := stringStructOf(&ky) - hash := t.key.alg.hash(noescape(unsafe.Pointer(&ky)), uintptr(h.hash0)) + hash := t.hasher(noescape(unsafe.Pointer(&ky)), uintptr(h.hash0)) - // Set hashWriting after calling alg.hash for consistency with mapdelete + // Set hashWriting after calling t.hasher for consistency with mapdelete h.flags ^= hashWriting bucket := hash & bucketMask(h.B) @@ -429,7 +429,7 @@ func evacuate_faststr(t *maptype, h *hmap, oldbucket uintptr) { if !h.sameSizeGrow() { // Compute hash to make our evacuation decision (whether we need // to send this key/elem to bucket x or bucket y). - hash := t.key.alg.hash(k, uintptr(h.hash0)) + hash := t.hasher(k, uintptr(h.hash0)) if hash&newbit != 0 { useY = 1 } diff --git a/src/runtime/map_test.go b/src/runtime/map_test.go index ee9468dd0e..593e32267d 100644 --- a/src/runtime/map_test.go +++ b/src/runtime/map_test.go @@ -435,11 +435,11 @@ func TestEmptyKeyAndValue(t *testing.T) { // ("quick keys") as well as long keys. func TestSingleBucketMapStringKeys_DupLen(t *testing.T) { testMapLookups(t, map[string]string{ - "x": "x1val", - "xx": "x2val", - "foo": "fooval", - "bar": "barval", // same key length as "foo" - "xxxx": "x4val", + "x": "x1val", + "xx": "x2val", + "foo": "fooval", + "bar": "barval", // same key length as "foo" + "xxxx": "x4val", strings.Repeat("x", 128): "longval1", strings.Repeat("y", 128): "longval2", }) @@ -1156,3 +1156,64 @@ func TestMapTombstones(t *testing.T) { } runtime.MapTombstoneCheck(m) } + +type canString int + +func (c canString) String() string { + return fmt.Sprintf("%d", int(c)) +} + +func TestMapInterfaceKey(t *testing.T) { + // Test all the special cases in runtime.typehash. + type GrabBag struct { + f32 float32 + f64 float64 + c64 complex64 + c128 complex128 + s string + i0 interface{} + i1 interface { + String() string + } + a [4]string + } + + m := map[interface{}]bool{} + // Put a bunch of data in m, so that a bad hash is likely to + // lead to a bad bucket, which will lead to a missed lookup. + for i := 0; i < 1000; i++ { + m[i] = true + } + m[GrabBag{f32: 1.0}] = true + if !m[GrabBag{f32: 1.0}] { + panic("f32 not found") + } + m[GrabBag{f64: 1.0}] = true + if !m[GrabBag{f64: 1.0}] { + panic("f64 not found") + } + m[GrabBag{c64: 1.0i}] = true + if !m[GrabBag{c64: 1.0i}] { + panic("c64 not found") + } + m[GrabBag{c128: 1.0i}] = true + if !m[GrabBag{c128: 1.0i}] { + panic("c128 not found") + } + m[GrabBag{s: "foo"}] = true + if !m[GrabBag{s: "foo"}] { + panic("string not found") + } + m[GrabBag{i0: "foo"}] = true + if !m[GrabBag{i0: "foo"}] { + panic("interface{} not found") + } + m[GrabBag{i1: canString(5)}] = true + if !m[GrabBag{i1: canString(5)}] { + panic("interface{String() string} not found") + } + m[GrabBag{a: [4]string{"foo", "bar", "baz", "bop"}}] = true + if !m[GrabBag{a: [4]string{"foo", "bar", "baz", "bop"}}] { + panic("array not found") + } +} diff --git a/src/runtime/type.go b/src/runtime/type.go index 660b45ef39..b5e37b9886 100644 --- a/src/runtime/type.go +++ b/src/runtime/type.go @@ -17,9 +17,10 @@ import "unsafe" type tflag uint8 const ( - tflagUncommon tflag = 1 << 0 - tflagExtraStar tflag = 1 << 1 - tflagNamed tflag = 1 << 2 + tflagUncommon tflag = 1 << 0 + tflagExtraStar tflag = 1 << 1 + tflagNamed tflag = 1 << 2 + tflagRegularMemory tflag = 1 << 3 // equal and hash can treat values of this type as a single region of t.size bytes ) // Needs to be in sync with ../cmd/link/internal/ld/decodesym.go:/^func.commonsize, @@ -33,7 +34,9 @@ type _type struct { align uint8 fieldalign uint8 kind uint8 - alg *typeAlg + // function for comparing objects of this type + // (ptr to object A, ptr to object B) -> ==? + equal func(unsafe.Pointer, unsafe.Pointer) bool // gcdata stores the GC type data for the garbage collector. // If the KindGCProg bit is set in kind, gcdata is a GC program. // Otherwise it is a ptrmask bitmap. See mbitmap.go for details. @@ -358,10 +361,12 @@ type interfacetype struct { } type maptype struct { - typ _type - key *_type - elem *_type - bucket *_type // internal type representing a hash bucket + typ _type + key *_type + elem *_type + bucket *_type // internal type representing a hash bucket + // function for hashing keys (ptr to key, seed) -> hash + hasher func(unsafe.Pointer, uintptr) uintptr keysize uint8 // size of key slot elemsize uint8 // size of elem slot bucketsize uint16 // size of bucket @@ -497,6 +502,16 @@ func (n name) pkgPath() string { return pkgPathName.name() } +func (n name) isBlank() bool { + if n.bytes == nil { + return false + } + if n.nameLen() != 1 { + return false + } + return *n.data(3) == '_' +} + // typelinksinit scans the types from extra modules and builds the // moduledata typemap used to de-duplicate type pointers. func typelinksinit() { -- cgit v1.3