From f4bb25c937cffb277e5ba87708d286ea7fd1b6ed Mon Sep 17 00:00:00 2001 From: Martin Möhrmann Date: Sat, 27 Jan 2018 12:48:15 +0100 Subject: runtime: rename map implementation and test files to use a common prefix MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Rename all map implementation and test files to use "map" as a file name prefix instead of "hashmap" for the implementation and "map" for the test file names. Change-Id: I7b317c1f7a660b95c6d1f1a185866f2839e69446 Reviewed-on: https://go-review.googlesource.com/90336 Run-TryBot: Martin Möhrmann TryBot-Result: Gobot Gobot Reviewed-by: Keith Randall --- src/runtime/hashmap.go | 1249 ------------------------------------- src/runtime/hashmap_fast.go | 1239 ------------------------------------ src/runtime/map.go | 1249 +++++++++++++++++++++++++++++++++++++ src/runtime/map_benchmark_test.go | 343 ++++++++++ src/runtime/map_fast.go | 1239 ++++++++++++++++++++++++++++++++++++ src/runtime/map_test.go | 2 +- src/runtime/mapspeed_test.go | 343 ---------- 7 files changed, 2832 insertions(+), 2832 deletions(-) delete mode 100644 src/runtime/hashmap.go delete mode 100644 src/runtime/hashmap_fast.go create mode 100644 src/runtime/map.go create mode 100644 src/runtime/map_benchmark_test.go create mode 100644 src/runtime/map_fast.go delete mode 100644 src/runtime/mapspeed_test.go (limited to 'src/runtime') diff --git a/src/runtime/hashmap.go b/src/runtime/hashmap.go deleted file mode 100644 index eddb045622..0000000000 --- a/src/runtime/hashmap.go +++ /dev/null @@ -1,1249 +0,0 @@ -// Copyright 2014 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -package runtime - -// This file contains the implementation of Go's map type. -// -// A map is just a hash table. The data is arranged -// into an array of buckets. Each bucket contains up to -// 8 key/value pairs. The low-order bits of the hash are -// used to select a bucket. Each bucket contains a few -// high-order bits of each hash to distinguish the entries -// within a single bucket. -// -// If more than 8 keys hash to a bucket, we chain on -// extra buckets. -// -// When the hashtable grows, we allocate a new array -// of buckets twice as big. Buckets are incrementally -// copied from the old bucket array to the new bucket array. -// -// Map iterators walk through the array of buckets and -// return the keys in walk order (bucket #, then overflow -// chain order, then bucket index). To maintain iteration -// semantics, we never move keys within their bucket (if -// we did, keys might be returned 0 or 2 times). When -// growing the table, iterators remain iterating through the -// old table and must check the new table if the bucket -// they are iterating through has been moved ("evacuated") -// to the new table. - -// Picking loadFactor: too large and we have lots of overflow -// buckets, too small and we waste a lot of space. I wrote -// a simple program to check some stats for different loads: -// (64-bit, 8 byte keys and values) -// 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 -// -// %overflow = percentage of buckets which have an overflow bucket -// bytes/entry = overhead bytes used per key/value pair -// hitprobe = # of entries to check when looking up a present key -// missprobe = # of entries to check when looking up an absent key -// -// Keep in mind this data is for maximally loaded tables, i.e. just -// before the table grows. Typical tables will be somewhat less loaded. - -import ( - "runtime/internal/atomic" - "runtime/internal/sys" - "unsafe" -) - -const ( - // Maximum number of key/value pairs a bucket can hold. - bucketCntBits = 3 - bucketCnt = 1 << bucketCntBits - - // Maximum average load of a bucket that triggers growth is 6.5. - // Represent as loadFactorNum/loadFactDen, to allow integer math. - loadFactorNum = 13 - loadFactorDen = 2 - - // Maximum key or value size to keep inline (instead of mallocing per element). - // Must fit in a uint8. - // Fast versions cannot handle big values - the cutoff size for - // fast versions in ../../cmd/internal/gc/walk.go must be at most this value. - maxKeySize = 128 - maxValueSize = 128 - - // data offset should be the size of the bmap struct, but needs to be - // aligned correctly. For amd64p32 this means 64-bit alignment - // even though pointers are 32 bit. - dataOffset = unsafe.Offsetof(struct { - b bmap - v int64 - }{}.v) - - // Possible tophash values. We reserve a few possibilities for special marks. - // Each bucket (including its overflow buckets, if any) will have either all or none of its - // entries in the evacuated* states (except during the evacuate() method, which only happens - // during map writes and thus no one else can observe the map during that time). - empty = 0 // cell is empty - evacuatedEmpty = 1 // cell is empty, bucket is evacuated. - evacuatedX = 2 // key/value is valid. Entry has been evacuated to first half of larger table. - evacuatedY = 3 // same as above, but evacuated to second half of larger table. - minTopHash = 4 // minimum tophash for a normal filled cell. - - // flags - iterator = 1 // there may be an iterator using buckets - oldIterator = 2 // there may be an iterator using oldbuckets - hashWriting = 4 // a goroutine is writing to the map - sameSizeGrow = 8 // the current map growth is to a new map of the same size - - // sentinel bucket ID for iterator checks - noCheck = 1<<(8*sys.PtrSize) - 1 -) - -// A header for a Go map. -type hmap struct { - // Note: the format of the Hmap is encoded in ../../cmd/internal/gc/reflect.go and - // ../reflect/type.go. Don't change this structure without also changing that code! - count int // # live cells == size of map. Must be first (used by len() builtin) - flags uint8 - B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items) - noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details - hash0 uint32 // hash seed - - buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0. - oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing - nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated) - - extra *mapextra // optional fields -} - -// mapextra holds fields that are not present on all maps. -type mapextra struct { - // If both key and value do not contain pointers and are inline, then we mark bucket - // type as containing no pointers. This avoids scanning such maps. - // However, bmap.overflow is a pointer. In order to keep overflow buckets - // alive, we store pointers to all overflow buckets in hmap.overflow and h.map.oldoverflow. - // overflow and oldoverflow are only used if key and value do not contain pointers. - // overflow contains overflow buckets for hmap.buckets. - // oldoverflow contains overflow buckets for hmap.oldbuckets. - // The indirection allows to store a pointer to the slice in hiter. - overflow *[]*bmap - oldoverflow *[]*bmap - - // nextOverflow holds a pointer to a free overflow bucket. - nextOverflow *bmap -} - -// A bucket for a Go map. -type bmap struct { - // tophash generally contains the top byte of the hash value - // for each key in this bucket. If tophash[0] < minTopHash, - // tophash[0] is a bucket evacuation state instead. - tophash [bucketCnt]uint8 - // Followed by bucketCnt keys and then bucketCnt values. - // NOTE: packing all the keys together and then all the values together makes the - // code a bit more complicated than alternating key/value/key/value/... but it allows - // us to eliminate padding which would be needed for, e.g., map[int64]int8. - // Followed by an overflow pointer. -} - -// A hash iteration structure. -// If you modify hiter, also change cmd/internal/gc/reflect.go to indicate -// the layout of this structure. -type hiter struct { - key unsafe.Pointer // Must be in first position. Write nil to indicate iteration end (see cmd/internal/gc/range.go). - value unsafe.Pointer // Must be in second position (see cmd/internal/gc/range.go). - t *maptype - h *hmap - buckets unsafe.Pointer // bucket ptr at hash_iter initialization time - bptr *bmap // current bucket - overflow *[]*bmap // keeps overflow buckets of hmap.buckets alive - oldoverflow *[]*bmap // keeps overflow buckets of hmap.oldbuckets alive - startBucket uintptr // bucket iteration started at - offset uint8 // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1) - wrapped bool // already wrapped around from end of bucket array to beginning - B uint8 - i uint8 - bucket uintptr - checkBucket uintptr -} - -// bucketShift returns 1<> (sys.PtrSize*8 - 8)) - if top < minTopHash { - top += minTopHash - } - return top -} - -func evacuated(b *bmap) bool { - h := b.tophash[0] - return h > empty && h < minTopHash -} - -func (b *bmap) overflow(t *maptype) *bmap { - return *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize)) -} - -func (b *bmap) setoverflow(t *maptype, ovf *bmap) { - *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize)) = ovf -} - -func (b *bmap) keys() unsafe.Pointer { - return add(unsafe.Pointer(b), dataOffset) -} - -// incrnoverflow increments h.noverflow. -// noverflow counts the number of overflow buckets. -// This is used to trigger same-size map growth. -// See also tooManyOverflowBuckets. -// To keep hmap small, noverflow is a uint16. -// When there are few buckets, noverflow is an exact count. -// When there are many buckets, noverflow is an approximate count. -func (h *hmap) incrnoverflow() { - // We trigger same-size map growth if there are - // as many overflow buckets as buckets. - // We need to be able to count to 1< int(maxSliceCap(t.bucket.size)) { - hint = 0 - } - - // initialize Hmap - if h == nil { - h = new(hmap) - } - h.hash0 = fastrand() - - // find size parameter which will hold the requested # of elements - B := uint8(0) - for overLoadFactor(hint, B) { - B++ - } - h.B = B - - // allocate initial hash table - // if B == 0, the buckets field is allocated lazily later (in mapassign) - // If hint is large zeroing this memory could take a while. - if h.B != 0 { - var nextOverflow *bmap - h.buckets, nextOverflow = makeBucketArray(t, h.B) - if nextOverflow != nil { - h.extra = new(mapextra) - h.extra.nextOverflow = nextOverflow - } - } - - return h -} - -// mapaccess1 returns a pointer to h[key]. Never returns nil, instead -// it will return a reference to the zero object for the value type if -// the key is not in the map. -// NOTE: The returned pointer may keep the whole map live, so don't -// hold onto it for very long. -func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { - if raceenabled && h != nil { - callerpc := getcallerpc() - pc := funcPC(mapaccess1) - racereadpc(unsafe.Pointer(h), callerpc, pc) - raceReadObjectPC(t.key, key, callerpc, pc) - } - if msanenabled && h != nil { - msanread(key, t.key.size) - } - if h == nil || h.count == 0 { - 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)) - m := bucketMask(h.B) - b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))) - if c := h.oldbuckets; c != nil { - if !h.sameSizeGrow() { - // There used to be half as many buckets; mask down one more power of two. - m >>= 1 - } - oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) - if !evacuated(oldb) { - b = oldb - } - } - top := tophash(hash) - for ; b != nil; b = b.overflow(t) { - for i := uintptr(0); i < bucketCnt; i++ { - if b.tophash[i] != top { - continue - } - k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) - if t.indirectkey { - k = *((*unsafe.Pointer)(k)) - } - if alg.equal(key, k) { - v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) - if t.indirectvalue { - v = *((*unsafe.Pointer)(v)) - } - return v - } - } - } - return unsafe.Pointer(&zeroVal[0]) -} - -func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) { - if raceenabled && h != nil { - callerpc := getcallerpc() - pc := funcPC(mapaccess2) - racereadpc(unsafe.Pointer(h), callerpc, pc) - raceReadObjectPC(t.key, key, callerpc, pc) - } - if msanenabled && h != nil { - msanread(key, t.key.size) - } - if h == nil || h.count == 0 { - 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)) - m := bucketMask(h.B) - b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize))) - if c := h.oldbuckets; c != nil { - if !h.sameSizeGrow() { - // There used to be half as many buckets; mask down one more power of two. - m >>= 1 - } - oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize))) - if !evacuated(oldb) { - b = oldb - } - } - top := tophash(hash) - for ; b != nil; b = b.overflow(t) { - for i := uintptr(0); i < bucketCnt; i++ { - if b.tophash[i] != top { - continue - } - k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) - if t.indirectkey { - k = *((*unsafe.Pointer)(k)) - } - if alg.equal(key, k) { - v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) - if t.indirectvalue { - v = *((*unsafe.Pointer)(v)) - } - return v, true - } - } - } - return unsafe.Pointer(&zeroVal[0]), false -} - -// returns both key and value. Used by map iterator -func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer) { - if h == nil || h.count == 0 { - return nil, nil - } - alg := t.key.alg - hash := alg.hash(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 { - if !h.sameSizeGrow() { - // There used to be half as many buckets; mask down one more power of two. - m >>= 1 - } - oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize))) - if !evacuated(oldb) { - b = oldb - } - } - top := tophash(hash) - for ; b != nil; b = b.overflow(t) { - for i := uintptr(0); i < bucketCnt; i++ { - if b.tophash[i] != top { - continue - } - k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) - if t.indirectkey { - k = *((*unsafe.Pointer)(k)) - } - if alg.equal(key, k) { - v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) - if t.indirectvalue { - v = *((*unsafe.Pointer)(v)) - } - return k, v - } - } - } - return nil, nil -} - -func mapaccess1_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) unsafe.Pointer { - v := mapaccess1(t, h, key) - if v == unsafe.Pointer(&zeroVal[0]) { - return zero - } - return v -} - -func mapaccess2_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) (unsafe.Pointer, bool) { - v := mapaccess1(t, h, key) - if v == unsafe.Pointer(&zeroVal[0]) { - return zero, false - } - return v, true -} - -// Like mapaccess, but allocates a slot for the key if it is not present in the map. -func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { - if h == nil { - panic(plainError("assignment to entry in nil map")) - } - if raceenabled { - callerpc := getcallerpc() - pc := funcPC(mapassign) - racewritepc(unsafe.Pointer(h), callerpc, pc) - raceReadObjectPC(t.key, key, callerpc, pc) - } - if msanenabled { - msanread(key, t.key.size) - } - if h.flags&hashWriting != 0 { - throw("concurrent map writes") - } - alg := t.key.alg - hash := alg.hash(key, uintptr(h.hash0)) - - // Set hashWriting after calling alg.hash, since alg.hash may panic, - // in which case we have not actually done a write. - h.flags |= hashWriting - - if h.buckets == nil { - h.buckets = newobject(t.bucket) // newarray(t.bucket, 1) - } - -again: - bucket := hash & bucketMask(h.B) - if h.growing() { - growWork(t, h, bucket) - } - b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize))) - top := tophash(hash) - - var inserti *uint8 - var insertk unsafe.Pointer - var val unsafe.Pointer - for { - for i := uintptr(0); i < bucketCnt; i++ { - if b.tophash[i] != top { - if b.tophash[i] == empty && inserti == nil { - inserti = &b.tophash[i] - insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) - val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) - } - continue - } - k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) - if t.indirectkey { - k = *((*unsafe.Pointer)(k)) - } - if !alg.equal(key, k) { - continue - } - // already have a mapping for key. Update it. - if t.needkeyupdate { - typedmemmove(t.key, k, key) - } - val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) - goto done - } - ovf := b.overflow(t) - if ovf == nil { - break - } - b = ovf - } - - // Did not find mapping for key. Allocate new cell & add entry. - - // If we hit the max load factor or we have too many overflow buckets, - // and we're not already in the middle of growing, start growing. - if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { - hashGrow(t, h) - goto again // Growing the table invalidates everything, so try again - } - - if inserti == nil { - // all current buckets are full, allocate a new one. - newb := h.newoverflow(t, b) - inserti = &newb.tophash[0] - insertk = add(unsafe.Pointer(newb), dataOffset) - val = add(insertk, bucketCnt*uintptr(t.keysize)) - } - - // store new key/value at insert position - if t.indirectkey { - kmem := newobject(t.key) - *(*unsafe.Pointer)(insertk) = kmem - insertk = kmem - } - if t.indirectvalue { - vmem := newobject(t.elem) - *(*unsafe.Pointer)(val) = vmem - } - typedmemmove(t.key, insertk, key) - *inserti = top - h.count++ - -done: - if h.flags&hashWriting == 0 { - throw("concurrent map writes") - } - h.flags &^= hashWriting - if t.indirectvalue { - val = *((*unsafe.Pointer)(val)) - } - return val -} - -func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { - if raceenabled && h != nil { - callerpc := getcallerpc() - pc := funcPC(mapdelete) - racewritepc(unsafe.Pointer(h), callerpc, pc) - raceReadObjectPC(t.key, key, callerpc, pc) - } - if msanenabled && h != nil { - msanread(key, t.key.size) - } - if h == nil || h.count == 0 { - return - } - if h.flags&hashWriting != 0 { - throw("concurrent map writes") - } - - alg := t.key.alg - hash := alg.hash(key, uintptr(h.hash0)) - - // Set hashWriting after calling alg.hash, since alg.hash may panic, - // in which case we have not actually done a write (delete). - h.flags |= hashWriting - - bucket := hash & bucketMask(h.B) - if h.growing() { - growWork(t, h, bucket) - } - b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) - top := tophash(hash) -search: - for ; b != nil; b = b.overflow(t) { - for i := uintptr(0); i < bucketCnt; i++ { - if b.tophash[i] != top { - continue - } - k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) - k2 := k - if t.indirectkey { - k2 = *((*unsafe.Pointer)(k2)) - } - if !alg.equal(key, k2) { - continue - } - // Only clear key if there are pointers in it. - if t.indirectkey { - *(*unsafe.Pointer)(k) = nil - } else if t.key.kind&kindNoPointers == 0 { - memclrHasPointers(k, t.key.size) - } - // Only clear value if there are pointers in it. - if t.indirectvalue || t.elem.kind&kindNoPointers == 0 { - v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) - if t.indirectvalue { - *(*unsafe.Pointer)(v) = nil - } else { - memclrHasPointers(v, t.elem.size) - } - } - b.tophash[i] = empty - h.count-- - break search - } - } - - if h.flags&hashWriting == 0 { - throw("concurrent map writes") - } - h.flags &^= hashWriting -} - -// mapiterinit initializes the hiter struct used for ranging over maps. -// The hiter struct pointed to by 'it' is allocated on the stack -// by the compilers order pass or on the heap by reflect_mapiterinit. -// Both need to have zeroed hiter since the struct contains pointers. -func mapiterinit(t *maptype, h *hmap, it *hiter) { - if raceenabled && h != nil { - callerpc := getcallerpc() - racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiterinit)) - } - - if h == nil || h.count == 0 { - return - } - - if unsafe.Sizeof(hiter{})/sys.PtrSize != 12 { - throw("hash_iter size incorrect") // see ../../cmd/internal/gc/reflect.go - } - it.t = t - it.h = h - - // grab snapshot of bucket state - it.B = h.B - it.buckets = h.buckets - if t.bucket.kind&kindNoPointers != 0 { - // Allocate the current slice and remember pointers to both current and old. - // This preserves all relevant overflow buckets alive even if - // the table grows and/or overflow buckets are added to the table - // while we are iterating. - h.createOverflow() - it.overflow = h.extra.overflow - it.oldoverflow = h.extra.oldoverflow - } - - // decide where to start - r := uintptr(fastrand()) - if h.B > 31-bucketCntBits { - r += uintptr(fastrand()) << 31 - } - it.startBucket = r & bucketMask(h.B) - it.offset = uint8(r >> h.B & (bucketCnt - 1)) - - // iterator state - it.bucket = it.startBucket - - // Remember we have an iterator. - // Can run concurrently with another mapiterinit(). - if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator { - atomic.Or8(&h.flags, iterator|oldIterator) - } - - mapiternext(it) -} - -func mapiternext(it *hiter) { - h := it.h - if raceenabled { - callerpc := getcallerpc() - racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiternext)) - } - if h.flags&hashWriting != 0 { - throw("concurrent map iteration and map write") - } - t := it.t - bucket := it.bucket - b := it.bptr - i := it.i - checkBucket := it.checkBucket - alg := t.key.alg - -next: - if b == nil { - if bucket == it.startBucket && it.wrapped { - // end of iteration - it.key = nil - it.value = nil - return - } - if h.growing() && it.B == h.B { - // Iterator was started in the middle of a grow, and the grow isn't done yet. - // If the bucket we're looking at hasn't been filled in yet (i.e. the old - // bucket hasn't been evacuated) then we need to iterate through the old - // bucket and only return the ones that will be migrated to this bucket. - oldbucket := bucket & it.h.oldbucketmask() - b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) - if !evacuated(b) { - checkBucket = bucket - } else { - b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize))) - checkBucket = noCheck - } - } else { - b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize))) - checkBucket = noCheck - } - bucket++ - if bucket == bucketShift(it.B) { - bucket = 0 - it.wrapped = true - } - i = 0 - } - for ; i < bucketCnt; i++ { - offi := (i + it.offset) & (bucketCnt - 1) - if b.tophash[offi] == empty || b.tophash[offi] == evacuatedEmpty { - continue - } - k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize)) - if t.indirectkey { - k = *((*unsafe.Pointer)(k)) - } - v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.valuesize)) - if checkBucket != noCheck && !h.sameSizeGrow() { - // Special case: iterator was started during a grow to a larger size - // and the grow is not done yet. We're working on a bucket whose - // oldbucket has not been evacuated yet. Or at least, it wasn't - // evacuated when we started the bucket. So we're iterating - // 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 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)) - if hash&bucketMask(it.B) != checkBucket { - continue - } - } else { - // Hash isn't repeatable if k != k (NaNs). We need a - // repeatable and randomish choice of which direction - // to send NaNs during evacuation. We'll use the low - // bit of tophash to decide which way NaNs go. - // NOTE: this case is why we need two evacuate tophash - // values, evacuatedX and evacuatedY, that differ in - // their low bit. - if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) { - continue - } - } - } - if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) || - !(t.reflexivekey || alg.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. - // That's lucky for us because when key!=key we can't look it up successfully. - it.key = k - if t.indirectvalue { - v = *((*unsafe.Pointer)(v)) - } - it.value = v - } else { - // The hash table has grown since the iterator was started. - // The golden data for this key is now somewhere else. - // Check the current hash table for the data. - // This code handles the case where the key - // has been deleted, updated, or deleted and reinserted. - // NOTE: we need to regrab the key as it has potentially been - // updated to an equal() but not identical key (e.g. +0.0 vs -0.0). - rk, rv := mapaccessK(t, h, k) - if rk == nil { - continue // key has been deleted - } - it.key = rk - it.value = rv - } - it.bucket = bucket - if it.bptr != b { // avoid unnecessary write barrier; see issue 14921 - it.bptr = b - } - it.i = i + 1 - it.checkBucket = checkBucket - return - } - b = b.overflow(t) - i = 0 - goto next -} - -func makeBucketArray(t *maptype, b uint8) (buckets unsafe.Pointer, nextOverflow *bmap) { - base := bucketShift(b) - nbuckets := base - // For small b, overflow buckets are unlikely. - // Avoid the overhead of the calculation. - if b >= 4 { - // Add on the estimated number of overflow buckets - // required to insert the median number of elements - // used with this value of b. - nbuckets += bucketShift(b - 4) - sz := t.bucket.size * nbuckets - up := roundupsize(sz) - if up != sz { - nbuckets = up / t.bucket.size - } - } - buckets = newarray(t.bucket, int(nbuckets)) - if base != nbuckets { - // We preallocated some overflow buckets. - // To keep the overhead of tracking these overflow buckets to a minimum, - // we use the convention that if a preallocated overflow bucket's overflow - // pointer is nil, then there are more available by bumping the pointer. - // We need a safe non-nil pointer for the last overflow bucket; just use buckets. - nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize))) - last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize))) - last.setoverflow(t, (*bmap)(buckets)) - } - return buckets, nextOverflow -} - -func hashGrow(t *maptype, h *hmap) { - // If we've hit the load factor, get bigger. - // Otherwise, there are too many overflow buckets, - // so keep the same number of buckets and "grow" laterally. - bigger := uint8(1) - if !overLoadFactor(h.count+1, h.B) { - bigger = 0 - h.flags |= sameSizeGrow - } - oldbuckets := h.buckets - newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger) - - flags := h.flags &^ (iterator | oldIterator) - if h.flags&iterator != 0 { - flags |= oldIterator - } - // commit the grow (atomic wrt gc) - h.B += bigger - h.flags = flags - h.oldbuckets = oldbuckets - h.buckets = newbuckets - h.nevacuate = 0 - h.noverflow = 0 - - if h.extra != nil && h.extra.overflow != nil { - // Promote current overflow buckets to the old generation. - if h.extra.oldoverflow != nil { - throw("oldoverflow is not nil") - } - h.extra.oldoverflow = h.extra.overflow - h.extra.overflow = nil - } - if nextOverflow != nil { - if h.extra == nil { - h.extra = new(mapextra) - } - h.extra.nextOverflow = nextOverflow - } - - // the actual copying of the hash table data is done incrementally - // by growWork() and evacuate(). -} - -// overLoadFactor reports whether count items placed in 1< bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen) -} - -// tooManyOverflowBuckets reports whether noverflow buckets is too many for a map with 1< 15 { - B = 15 - } - // The compiler doesn't see here that B < 16; mask B to generate shorter shift code. - return noverflow >= uint16(1)<<(B&15) -} - -// growing reports whether h is growing. The growth may be to the same size or bigger. -func (h *hmap) growing() bool { - return h.oldbuckets != nil -} - -// sameSizeGrow reports whether the current growth is to a map of the same size. -func (h *hmap) sameSizeGrow() bool { - return h.flags&sameSizeGrow != 0 -} - -// noldbuckets calculates the number of buckets prior to the current map growth. -func (h *hmap) noldbuckets() uintptr { - oldB := h.B - if !h.sameSizeGrow() { - oldB-- - } - return bucketShift(oldB) -} - -// oldbucketmask provides a mask that can be applied to calculate n % noldbuckets(). -func (h *hmap) oldbucketmask() uintptr { - return h.noldbuckets() - 1 -} - -func growWork(t *maptype, h *hmap, bucket uintptr) { - // make sure we evacuate the oldbucket corresponding - // to the bucket we're about to use - evacuate(t, h, bucket&h.oldbucketmask()) - - // evacuate one more oldbucket to make progress on growing - if h.growing() { - evacuate(t, h, h.nevacuate) - } -} - -func bucketEvacuated(t *maptype, h *hmap, bucket uintptr) bool { - b := (*bmap)(add(h.oldbuckets, bucket*uintptr(t.bucketsize))) - return evacuated(b) -} - -// evacDst is an evacuation destination. -type evacDst struct { - b *bmap // current destination bucket - i int // key/val index into b - k unsafe.Pointer // pointer to current key storage - v unsafe.Pointer // pointer to current value storage -} - -func evacuate(t *maptype, h *hmap, oldbucket uintptr) { - b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) - newbit := h.noldbuckets() - if !evacuated(b) { - // TODO: reuse overflow buckets instead of using new ones, if there - // is no iterator using the old buckets. (If !oldIterator.) - - // xy contains the x and y (low and high) evacuation destinations. - var xy [2]evacDst - x := &xy[0] - x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize))) - x.k = add(unsafe.Pointer(x.b), dataOffset) - x.v = add(x.k, bucketCnt*uintptr(t.keysize)) - - if !h.sameSizeGrow() { - // Only calculate y pointers if we're growing bigger. - // Otherwise GC can see bad pointers. - y := &xy[1] - y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize))) - y.k = add(unsafe.Pointer(y.b), dataOffset) - y.v = add(y.k, bucketCnt*uintptr(t.keysize)) - } - - for ; b != nil; b = b.overflow(t) { - k := add(unsafe.Pointer(b), dataOffset) - v := add(k, bucketCnt*uintptr(t.keysize)) - for i := 0; i < bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) { - top := b.tophash[i] - if top == empty { - b.tophash[i] = evacuatedEmpty - continue - } - if top < minTopHash { - throw("bad map state") - } - k2 := k - if t.indirectkey { - k2 = *((*unsafe.Pointer)(k2)) - } - var useY uint8 - if !h.sameSizeGrow() { - // Compute hash to make our evacuation decision (whether we need - // to send this key/value 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) { - // 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 - // presence of iterators, as our evacuation decision must - // match whatever decision the iterator made. - // Fortunately, we have the freedom to send these keys either - // way. Also, tophash is meaningless for these kinds of keys. - // We let the low bit of tophash drive the evacuation decision. - // We recompute a new random tophash for the next level so - // these keys will get evenly distributed across all buckets - // after multiple grows. - useY = top & 1 - top = tophash(hash) - } else { - if hash&newbit != 0 { - useY = 1 - } - } - } - - if evacuatedX+1 != evacuatedY { - throw("bad evacuatedN") - } - - b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY - dst := &xy[useY] // evacuation destination - - if dst.i == bucketCnt { - dst.b = h.newoverflow(t, dst.b) - dst.i = 0 - dst.k = add(unsafe.Pointer(dst.b), dataOffset) - dst.v = add(dst.k, bucketCnt*uintptr(t.keysize)) - } - dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check - if t.indirectkey { - *(*unsafe.Pointer)(dst.k) = k2 // copy pointer - } else { - typedmemmove(t.key, dst.k, k) // copy value - } - if t.indirectvalue { - *(*unsafe.Pointer)(dst.v) = *(*unsafe.Pointer)(v) - } else { - typedmemmove(t.elem, dst.v, v) - } - dst.i++ - // These updates might push these pointers past the end of the - // key or value arrays. That's ok, as we have the overflow pointer - // at the end of the bucket to protect against pointing past the - // end of the bucket. - dst.k = add(dst.k, uintptr(t.keysize)) - dst.v = add(dst.v, uintptr(t.valuesize)) - } - } - // Unlink the overflow buckets & clear key/value to help GC. - if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 { - b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)) - // Preserve b.tophash because the evacuation - // state is maintained there. - ptr := add(b, dataOffset) - n := uintptr(t.bucketsize) - dataOffset - memclrHasPointers(ptr, n) - } - } - - if oldbucket == h.nevacuate { - advanceEvacuationMark(h, t, newbit) - } -} - -func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) { - h.nevacuate++ - // Experiments suggest that 1024 is overkill by at least an order of magnitude. - // Put it in there as a safeguard anyway, to ensure O(1) behavior. - stop := h.nevacuate + 1024 - if stop > newbit { - stop = newbit - } - for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) { - h.nevacuate++ - } - if h.nevacuate == newbit { // newbit == # of oldbuckets - // Growing is all done. Free old main bucket array. - h.oldbuckets = nil - // Can discard old overflow buckets as well. - // If they are still referenced by an iterator, - // then the iterator holds a pointers to the slice. - if h.extra != nil { - h.extra.oldoverflow = nil - } - h.flags &^= sameSizeGrow - } -} - -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 sz := unsafe.Sizeof(hmap{}); sz != t.hmap.size { - println("runtime: sizeof(hmap) =", sz, ", t.hmap.size =", t.hmap.size) - throw("bad hmap size") - } - if !ismapkey(t.key) { - throw("runtime.reflect_makemap: unsupported map key type") - } - if t.key.size > maxKeySize && (!t.indirectkey || t.keysize != uint8(sys.PtrSize)) || - t.key.size <= maxKeySize && (t.indirectkey || t.keysize != uint8(t.key.size)) { - throw("key size wrong") - } - if t.elem.size > maxValueSize && (!t.indirectvalue || t.valuesize != uint8(sys.PtrSize)) || - t.elem.size <= maxValueSize && (t.indirectvalue || t.valuesize != uint8(t.elem.size)) { - throw("value size wrong") - } - if t.key.align > bucketCnt { - throw("key align too big") - } - if t.elem.align > bucketCnt { - throw("value align too big") - } - if t.key.size%uintptr(t.key.align) != 0 { - throw("key size not a multiple of key align") - } - if t.elem.size%uintptr(t.elem.align) != 0 { - throw("value size not a multiple of value align") - } - if bucketCnt < 8 { - throw("bucketsize too small for proper alignment") - } - if dataOffset%uintptr(t.key.align) != 0 { - throw("need padding in bucket (key)") - } - if dataOffset%uintptr(t.elem.align) != 0 { - throw("need padding in bucket (value)") - } - - return makemap(t, cap, nil) -} - -//go:linkname reflect_mapaccess reflect.mapaccess -func reflect_mapaccess(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { - val, ok := mapaccess2(t, h, key) - if !ok { - // reflect wants nil for a missing element - val = nil - } - return val -} - -//go:linkname reflect_mapassign reflect.mapassign -func reflect_mapassign(t *maptype, h *hmap, key unsafe.Pointer, val unsafe.Pointer) { - p := mapassign(t, h, key) - typedmemmove(t.elem, p, val) -} - -//go:linkname reflect_mapdelete reflect.mapdelete -func reflect_mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { - mapdelete(t, h, key) -} - -//go:linkname reflect_mapiterinit reflect.mapiterinit -func reflect_mapiterinit(t *maptype, h *hmap) *hiter { - it := new(hiter) - mapiterinit(t, h, it) - return it -} - -//go:linkname reflect_mapiternext reflect.mapiternext -func reflect_mapiternext(it *hiter) { - mapiternext(it) -} - -//go:linkname reflect_mapiterkey reflect.mapiterkey -func reflect_mapiterkey(it *hiter) unsafe.Pointer { - return it.key -} - -//go:linkname reflect_maplen reflect.maplen -func reflect_maplen(h *hmap) int { - if h == nil { - return 0 - } - if raceenabled { - callerpc := getcallerpc() - racereadpc(unsafe.Pointer(h), callerpc, funcPC(reflect_maplen)) - } - 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 -var zeroVal [maxZero]byte diff --git a/src/runtime/hashmap_fast.go b/src/runtime/hashmap_fast.go deleted file mode 100644 index f978d1be7b..0000000000 --- a/src/runtime/hashmap_fast.go +++ /dev/null @@ -1,1239 +0,0 @@ -// Copyright 2014 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -package runtime - -import ( - "runtime/internal/sys" - "unsafe" -) - -func mapaccess1_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer { - if raceenabled && h != nil { - callerpc := getcallerpc() - racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess1_fast32)) - } - if h == nil || h.count == 0 { - return unsafe.Pointer(&zeroVal[0]) - } - if h.flags&hashWriting != 0 { - throw("concurrent map read and map write") - } - var b *bmap - if h.B == 0 { - // One-bucket table. No need to hash. - b = (*bmap)(h.buckets) - } else { - hash := t.key.alg.hash(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 { - if !h.sameSizeGrow() { - // There used to be half as many buckets; mask down one more power of two. - m >>= 1 - } - oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) - if !evacuated(oldb) { - b = oldb - } - } - } - for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 4) { - if *(*uint32)(k) == key && b.tophash[i] != empty { - return add(unsafe.Pointer(b), dataOffset+bucketCnt*4+i*uintptr(t.valuesize)) - } - } - } - return unsafe.Pointer(&zeroVal[0]) -} - -func mapaccess2_fast32(t *maptype, h *hmap, key uint32) (unsafe.Pointer, bool) { - if raceenabled && h != nil { - callerpc := getcallerpc() - racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess2_fast32)) - } - if h == nil || h.count == 0 { - return unsafe.Pointer(&zeroVal[0]), false - } - if h.flags&hashWriting != 0 { - throw("concurrent map read and map write") - } - var b *bmap - if h.B == 0 { - // One-bucket table. No need to hash. - b = (*bmap)(h.buckets) - } else { - hash := t.key.alg.hash(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 { - if !h.sameSizeGrow() { - // There used to be half as many buckets; mask down one more power of two. - m >>= 1 - } - oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) - if !evacuated(oldb) { - b = oldb - } - } - } - for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 4) { - if *(*uint32)(k) == key && b.tophash[i] != empty { - return add(unsafe.Pointer(b), dataOffset+bucketCnt*4+i*uintptr(t.valuesize)), true - } - } - } - return unsafe.Pointer(&zeroVal[0]), false -} - -func mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer { - if raceenabled && h != nil { - callerpc := getcallerpc() - racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess1_fast64)) - } - if h == nil || h.count == 0 { - return unsafe.Pointer(&zeroVal[0]) - } - if h.flags&hashWriting != 0 { - throw("concurrent map read and map write") - } - var b *bmap - if h.B == 0 { - // One-bucket table. No need to hash. - b = (*bmap)(h.buckets) - } else { - hash := t.key.alg.hash(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 { - if !h.sameSizeGrow() { - // There used to be half as many buckets; mask down one more power of two. - m >>= 1 - } - oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) - if !evacuated(oldb) { - b = oldb - } - } - } - for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 8) { - if *(*uint64)(k) == key && b.tophash[i] != empty { - return add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.valuesize)) - } - } - } - return unsafe.Pointer(&zeroVal[0]) -} - -func mapaccess2_fast64(t *maptype, h *hmap, key uint64) (unsafe.Pointer, bool) { - if raceenabled && h != nil { - callerpc := getcallerpc() - racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess2_fast64)) - } - if h == nil || h.count == 0 { - return unsafe.Pointer(&zeroVal[0]), false - } - if h.flags&hashWriting != 0 { - throw("concurrent map read and map write") - } - var b *bmap - if h.B == 0 { - // One-bucket table. No need to hash. - b = (*bmap)(h.buckets) - } else { - hash := t.key.alg.hash(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 { - if !h.sameSizeGrow() { - // There used to be half as many buckets; mask down one more power of two. - m >>= 1 - } - oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) - if !evacuated(oldb) { - b = oldb - } - } - } - for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 8) { - if *(*uint64)(k) == key && b.tophash[i] != empty { - return add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.valuesize)), true - } - } - } - return unsafe.Pointer(&zeroVal[0]), false -} - -func mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer { - if raceenabled && h != nil { - callerpc := getcallerpc() - racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess1_faststr)) - } - if h == nil || h.count == 0 { - return unsafe.Pointer(&zeroVal[0]) - } - if h.flags&hashWriting != 0 { - throw("concurrent map read and map write") - } - key := stringStructOf(&ky) - if h.B == 0 { - // One-bucket table. - b := (*bmap)(h.buckets) - if key.len < 32 { - // short key, doing lots of comparisons is ok - for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) { - k := (*stringStruct)(kptr) - if k.len != key.len || b.tophash[i] == empty { - continue - } - if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize)) - } - } - return unsafe.Pointer(&zeroVal[0]) - } - // long key, try not to do more comparisons than necessary - keymaybe := uintptr(bucketCnt) - for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) { - k := (*stringStruct)(kptr) - if k.len != key.len || b.tophash[i] == empty { - continue - } - if k.str == key.str { - return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize)) - } - // check first 4 bytes - if *((*[4]byte)(key.str)) != *((*[4]byte)(k.str)) { - continue - } - // check last 4 bytes - if *((*[4]byte)(add(key.str, uintptr(key.len)-4))) != *((*[4]byte)(add(k.str, uintptr(key.len)-4))) { - continue - } - if keymaybe != bucketCnt { - // Two keys are potential matches. Use hash to distinguish them. - goto dohash - } - keymaybe = i - } - if keymaybe != bucketCnt { - k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+keymaybe*2*sys.PtrSize)) - if memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+keymaybe*uintptr(t.valuesize)) - } - } - return unsafe.Pointer(&zeroVal[0]) - } -dohash: - hash := t.key.alg.hash(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 { - if !h.sameSizeGrow() { - // There used to be half as many buckets; mask down one more power of two. - m >>= 1 - } - oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) - if !evacuated(oldb) { - b = oldb - } - } - top := tophash(hash) - for ; b != nil; b = b.overflow(t) { - for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) { - k := (*stringStruct)(kptr) - if k.len != key.len || b.tophash[i] != top { - continue - } - if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize)) - } - } - } - return unsafe.Pointer(&zeroVal[0]) -} - -func mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool) { - if raceenabled && h != nil { - callerpc := getcallerpc() - racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess2_faststr)) - } - if h == nil || h.count == 0 { - return unsafe.Pointer(&zeroVal[0]), false - } - if h.flags&hashWriting != 0 { - throw("concurrent map read and map write") - } - key := stringStructOf(&ky) - if h.B == 0 { - // One-bucket table. - b := (*bmap)(h.buckets) - if key.len < 32 { - // short key, doing lots of comparisons is ok - for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) { - k := (*stringStruct)(kptr) - if k.len != key.len || b.tophash[i] == empty { - continue - } - if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize)), true - } - } - return unsafe.Pointer(&zeroVal[0]), false - } - // long key, try not to do more comparisons than necessary - keymaybe := uintptr(bucketCnt) - for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) { - k := (*stringStruct)(kptr) - if k.len != key.len || b.tophash[i] == empty { - continue - } - if k.str == key.str { - return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize)), true - } - // check first 4 bytes - if *((*[4]byte)(key.str)) != *((*[4]byte)(k.str)) { - continue - } - // check last 4 bytes - if *((*[4]byte)(add(key.str, uintptr(key.len)-4))) != *((*[4]byte)(add(k.str, uintptr(key.len)-4))) { - continue - } - if keymaybe != bucketCnt { - // Two keys are potential matches. Use hash to distinguish them. - goto dohash - } - keymaybe = i - } - if keymaybe != bucketCnt { - k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+keymaybe*2*sys.PtrSize)) - if memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+keymaybe*uintptr(t.valuesize)), true - } - } - return unsafe.Pointer(&zeroVal[0]), false - } -dohash: - hash := t.key.alg.hash(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 { - if !h.sameSizeGrow() { - // There used to be half as many buckets; mask down one more power of two. - m >>= 1 - } - oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) - if !evacuated(oldb) { - b = oldb - } - } - top := tophash(hash) - for ; b != nil; b = b.overflow(t) { - for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) { - k := (*stringStruct)(kptr) - if k.len != key.len || b.tophash[i] != top { - continue - } - if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize)), true - } - } - } - return unsafe.Pointer(&zeroVal[0]), false -} - -func mapassign_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer { - if h == nil { - panic(plainError("assignment to entry in nil map")) - } - if raceenabled { - callerpc := getcallerpc() - racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapassign_fast32)) - } - if h.flags&hashWriting != 0 { - throw("concurrent map writes") - } - hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - - // Set hashWriting after calling alg.hash for consistency with mapassign. - h.flags |= hashWriting - - if h.buckets == nil { - h.buckets = newobject(t.bucket) // newarray(t.bucket, 1) - } - -again: - bucket := hash & bucketMask(h.B) - if h.growing() { - growWork_fast32(t, h, bucket) - } - b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize))) - - var insertb *bmap - var inserti uintptr - var insertk unsafe.Pointer - - for { - for i := uintptr(0); i < bucketCnt; i++ { - if b.tophash[i] == empty { - if insertb == nil { - inserti = i - insertb = b - } - continue - } - k := *((*uint32)(add(unsafe.Pointer(b), dataOffset+i*4))) - if k != key { - continue - } - inserti = i - insertb = b - goto done - } - ovf := b.overflow(t) - if ovf == nil { - break - } - b = ovf - } - - // Did not find mapping for key. Allocate new cell & add entry. - - // If we hit the max load factor or we have too many overflow buckets, - // and we're not already in the middle of growing, start growing. - if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { - hashGrow(t, h) - goto again // Growing the table invalidates everything, so try again - } - - if insertb == nil { - // all current buckets are full, allocate a new one. - insertb = h.newoverflow(t, b) - inserti = 0 // not necessary, but avoids needlessly spilling inserti - } - insertb.tophash[inserti&(bucketCnt-1)] = tophash(hash) // mask inserti to avoid bounds checks - - insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*4) - // store new key at insert position - *(*uint32)(insertk) = key - - h.count++ - -done: - val := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*4+inserti*uintptr(t.valuesize)) - if h.flags&hashWriting == 0 { - throw("concurrent map writes") - } - h.flags &^= hashWriting - return val -} - -func mapassign_fast32ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { - if h == nil { - panic(plainError("assignment to entry in nil map")) - } - if raceenabled { - callerpc := getcallerpc() - racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapassign_fast32)) - } - if h.flags&hashWriting != 0 { - throw("concurrent map writes") - } - hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - - // Set hashWriting after calling alg.hash for consistency with mapassign. - h.flags |= hashWriting - - if h.buckets == nil { - h.buckets = newobject(t.bucket) // newarray(t.bucket, 1) - } - -again: - bucket := hash & bucketMask(h.B) - if h.growing() { - growWork_fast32(t, h, bucket) - } - b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize))) - - var insertb *bmap - var inserti uintptr - var insertk unsafe.Pointer - - for { - for i := uintptr(0); i < bucketCnt; i++ { - if b.tophash[i] == empty { - if insertb == nil { - inserti = i - insertb = b - } - continue - } - k := *((*unsafe.Pointer)(add(unsafe.Pointer(b), dataOffset+i*4))) - if k != key { - continue - } - inserti = i - insertb = b - goto done - } - ovf := b.overflow(t) - if ovf == nil { - break - } - b = ovf - } - - // Did not find mapping for key. Allocate new cell & add entry. - - // If we hit the max load factor or we have too many overflow buckets, - // and we're not already in the middle of growing, start growing. - if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { - hashGrow(t, h) - goto again // Growing the table invalidates everything, so try again - } - - if insertb == nil { - // all current buckets are full, allocate a new one. - insertb = h.newoverflow(t, b) - inserti = 0 // not necessary, but avoids needlessly spilling inserti - } - insertb.tophash[inserti&(bucketCnt-1)] = tophash(hash) // mask inserti to avoid bounds checks - - insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*4) - // store new key at insert position - *(*unsafe.Pointer)(insertk) = key - - h.count++ - -done: - val := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*4+inserti*uintptr(t.valuesize)) - if h.flags&hashWriting == 0 { - throw("concurrent map writes") - } - h.flags &^= hashWriting - return val -} - -func mapassign_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer { - if h == nil { - panic(plainError("assignment to entry in nil map")) - } - if raceenabled { - callerpc := getcallerpc() - racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapassign_fast64)) - } - if h.flags&hashWriting != 0 { - throw("concurrent map writes") - } - hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - - // Set hashWriting after calling alg.hash for consistency with mapassign. - h.flags |= hashWriting - - if h.buckets == nil { - h.buckets = newobject(t.bucket) // newarray(t.bucket, 1) - } - -again: - bucket := hash & bucketMask(h.B) - if h.growing() { - growWork_fast64(t, h, bucket) - } - b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize))) - - var insertb *bmap - var inserti uintptr - var insertk unsafe.Pointer - - for { - for i := uintptr(0); i < bucketCnt; i++ { - if b.tophash[i] == empty { - if insertb == nil { - insertb = b - inserti = i - } - continue - } - k := *((*uint64)(add(unsafe.Pointer(b), dataOffset+i*8))) - if k != key { - continue - } - insertb = b - inserti = i - goto done - } - ovf := b.overflow(t) - if ovf == nil { - break - } - b = ovf - } - - // Did not find mapping for key. Allocate new cell & add entry. - - // If we hit the max load factor or we have too many overflow buckets, - // and we're not already in the middle of growing, start growing. - if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { - hashGrow(t, h) - goto again // Growing the table invalidates everything, so try again - } - - if insertb == nil { - // all current buckets are full, allocate a new one. - insertb = h.newoverflow(t, b) - inserti = 0 // not necessary, but avoids needlessly spilling inserti - } - insertb.tophash[inserti&(bucketCnt-1)] = tophash(hash) // mask inserti to avoid bounds checks - - insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*8) - // store new key at insert position - *(*uint64)(insertk) = key - - h.count++ - -done: - val := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*8+inserti*uintptr(t.valuesize)) - if h.flags&hashWriting == 0 { - throw("concurrent map writes") - } - h.flags &^= hashWriting - return val -} - -func mapassign_fast64ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { - if h == nil { - panic(plainError("assignment to entry in nil map")) - } - if raceenabled { - callerpc := getcallerpc() - racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapassign_fast64)) - } - if h.flags&hashWriting != 0 { - throw("concurrent map writes") - } - hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - - // Set hashWriting after calling alg.hash for consistency with mapassign. - h.flags |= hashWriting - - if h.buckets == nil { - h.buckets = newobject(t.bucket) // newarray(t.bucket, 1) - } - -again: - bucket := hash & bucketMask(h.B) - if h.growing() { - growWork_fast64(t, h, bucket) - } - b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize))) - - var insertb *bmap - var inserti uintptr - var insertk unsafe.Pointer - - for { - for i := uintptr(0); i < bucketCnt; i++ { - if b.tophash[i] == empty { - if insertb == nil { - insertb = b - inserti = i - } - continue - } - k := *((*unsafe.Pointer)(add(unsafe.Pointer(b), dataOffset+i*8))) - if k != key { - continue - } - insertb = b - inserti = i - goto done - } - ovf := b.overflow(t) - if ovf == nil { - break - } - b = ovf - } - - // Did not find mapping for key. Allocate new cell & add entry. - - // If we hit the max load factor or we have too many overflow buckets, - // and we're not already in the middle of growing, start growing. - if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { - hashGrow(t, h) - goto again // Growing the table invalidates everything, so try again - } - - if insertb == nil { - // all current buckets are full, allocate a new one. - insertb = h.newoverflow(t, b) - inserti = 0 // not necessary, but avoids needlessly spilling inserti - } - insertb.tophash[inserti&(bucketCnt-1)] = tophash(hash) // mask inserti to avoid bounds checks - - insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*8) - // store new key at insert position - *(*unsafe.Pointer)(insertk) = key - - h.count++ - -done: - val := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*8+inserti*uintptr(t.valuesize)) - if h.flags&hashWriting == 0 { - throw("concurrent map writes") - } - h.flags &^= hashWriting - return val -} - -func mapassign_faststr(t *maptype, h *hmap, s string) unsafe.Pointer { - if h == nil { - panic(plainError("assignment to entry in nil map")) - } - if raceenabled { - callerpc := getcallerpc() - racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapassign_faststr)) - } - if h.flags&hashWriting != 0 { - throw("concurrent map writes") - } - key := stringStructOf(&s) - hash := t.key.alg.hash(noescape(unsafe.Pointer(&s)), uintptr(h.hash0)) - - // Set hashWriting after calling alg.hash for consistency with mapassign. - h.flags |= hashWriting - - if h.buckets == nil { - h.buckets = newobject(t.bucket) // newarray(t.bucket, 1) - } - -again: - bucket := hash & bucketMask(h.B) - if h.growing() { - growWork_faststr(t, h, bucket) - } - b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize))) - top := tophash(hash) - - var insertb *bmap - var inserti uintptr - var insertk unsafe.Pointer - - for { - for i := uintptr(0); i < bucketCnt; i++ { - if b.tophash[i] != top { - if b.tophash[i] == empty && insertb == nil { - insertb = b - inserti = i - } - continue - } - k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+i*2*sys.PtrSize)) - if k.len != key.len { - continue - } - if k.str != key.str && !memequal(k.str, key.str, uintptr(key.len)) { - continue - } - // already have a mapping for key. Update it. - inserti = i - insertb = b - goto done - } - ovf := b.overflow(t) - if ovf == nil { - break - } - b = ovf - } - - // Did not find mapping for key. Allocate new cell & add entry. - - // If we hit the max load factor or we have too many overflow buckets, - // and we're not already in the middle of growing, start growing. - if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { - hashGrow(t, h) - goto again // Growing the table invalidates everything, so try again - } - - if insertb == nil { - // all current buckets are full, allocate a new one. - insertb = h.newoverflow(t, b) - inserti = 0 // not necessary, but avoids needlessly spilling inserti - } - insertb.tophash[inserti&(bucketCnt-1)] = top // mask inserti to avoid bounds checks - - insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*2*sys.PtrSize) - // store new key at insert position - *((*stringStruct)(insertk)) = *key - h.count++ - -done: - val := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*2*sys.PtrSize+inserti*uintptr(t.valuesize)) - if h.flags&hashWriting == 0 { - throw("concurrent map writes") - } - h.flags &^= hashWriting - return val -} - -func mapdelete_fast32(t *maptype, h *hmap, key uint32) { - if raceenabled && h != nil { - callerpc := getcallerpc() - racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapdelete_fast32)) - } - if h == nil || h.count == 0 { - return - } - if h.flags&hashWriting != 0 { - throw("concurrent map writes") - } - - hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - - // Set hashWriting after calling alg.hash for consistency with mapdelete - h.flags |= hashWriting - - bucket := hash & bucketMask(h.B) - if h.growing() { - growWork_fast32(t, h, bucket) - } - b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) -search: - for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 4) { - if key != *(*uint32)(k) || b.tophash[i] == empty { - continue - } - // Only clear key if there are pointers in it. - if t.key.kind&kindNoPointers == 0 { - memclrHasPointers(k, t.key.size) - } - // Only clear value if there are pointers in it. - if t.elem.kind&kindNoPointers == 0 { - v := add(unsafe.Pointer(b), dataOffset+bucketCnt*4+i*uintptr(t.valuesize)) - memclrHasPointers(v, t.elem.size) - } - b.tophash[i] = empty - h.count-- - break search - } - } - - if h.flags&hashWriting == 0 { - throw("concurrent map writes") - } - h.flags &^= hashWriting -} - -func mapdelete_fast64(t *maptype, h *hmap, key uint64) { - if raceenabled && h != nil { - callerpc := getcallerpc() - racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapdelete_fast64)) - } - if h == nil || h.count == 0 { - return - } - if h.flags&hashWriting != 0 { - throw("concurrent map writes") - } - - hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) - - // Set hashWriting after calling alg.hash for consistency with mapdelete - h.flags |= hashWriting - - bucket := hash & bucketMask(h.B) - if h.growing() { - growWork_fast64(t, h, bucket) - } - b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) -search: - for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 8) { - if key != *(*uint64)(k) || b.tophash[i] == empty { - continue - } - // Only clear key if there are pointers in it. - if t.key.kind&kindNoPointers == 0 { - memclrHasPointers(k, t.key.size) - } - // Only clear value if there are pointers in it. - if t.elem.kind&kindNoPointers == 0 { - v := add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.valuesize)) - memclrHasPointers(v, t.elem.size) - } - b.tophash[i] = empty - h.count-- - break search - } - } - - if h.flags&hashWriting == 0 { - throw("concurrent map writes") - } - h.flags &^= hashWriting -} - -func mapdelete_faststr(t *maptype, h *hmap, ky string) { - if raceenabled && h != nil { - callerpc := getcallerpc() - racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapdelete_faststr)) - } - if h == nil || h.count == 0 { - return - } - if h.flags&hashWriting != 0 { - throw("concurrent map writes") - } - - key := stringStructOf(&ky) - hash := t.key.alg.hash(noescape(unsafe.Pointer(&ky)), uintptr(h.hash0)) - - // Set hashWriting after calling alg.hash for consistency with mapdelete - h.flags |= hashWriting - - bucket := hash & bucketMask(h.B) - if h.growing() { - growWork_faststr(t, h, bucket) - } - b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) - top := tophash(hash) -search: - for ; b != nil; b = b.overflow(t) { - for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) { - k := (*stringStruct)(kptr) - if k.len != key.len || b.tophash[i] != top { - continue - } - if k.str != key.str && !memequal(k.str, key.str, uintptr(key.len)) { - continue - } - // Clear key's pointer. - k.str = nil - // Only clear value if there are pointers in it. - if t.elem.kind&kindNoPointers == 0 { - v := add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize)) - memclrHasPointers(v, t.elem.size) - } - b.tophash[i] = empty - h.count-- - break search - } - } - - if h.flags&hashWriting == 0 { - throw("concurrent map writes") - } - h.flags &^= hashWriting -} - -func growWork_fast32(t *maptype, h *hmap, bucket uintptr) { - // make sure we evacuate the oldbucket corresponding - // to the bucket we're about to use - evacuate_fast32(t, h, bucket&h.oldbucketmask()) - - // evacuate one more oldbucket to make progress on growing - if h.growing() { - evacuate_fast32(t, h, h.nevacuate) - } -} - -func evacuate_fast32(t *maptype, h *hmap, oldbucket uintptr) { - b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) - newbit := h.noldbuckets() - if !evacuated(b) { - // TODO: reuse overflow buckets instead of using new ones, if there - // is no iterator using the old buckets. (If !oldIterator.) - - // xy contains the x and y (low and high) evacuation destinations. - var xy [2]evacDst - x := &xy[0] - x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize))) - x.k = add(unsafe.Pointer(x.b), dataOffset) - x.v = add(x.k, bucketCnt*4) - - if !h.sameSizeGrow() { - // Only calculate y pointers if we're growing bigger. - // Otherwise GC can see bad pointers. - y := &xy[1] - y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize))) - y.k = add(unsafe.Pointer(y.b), dataOffset) - y.v = add(y.k, bucketCnt*4) - } - - for ; b != nil; b = b.overflow(t) { - k := add(unsafe.Pointer(b), dataOffset) - v := add(k, bucketCnt*4) - for i := 0; i < bucketCnt; i, k, v = i+1, add(k, 4), add(v, uintptr(t.valuesize)) { - top := b.tophash[i] - if top == empty { - b.tophash[i] = evacuatedEmpty - continue - } - if top < minTopHash { - throw("bad map state") - } - var useY uint8 - if !h.sameSizeGrow() { - // Compute hash to make our evacuation decision (whether we need - // to send this key/value to bucket x or bucket y). - hash := t.key.alg.hash(k, uintptr(h.hash0)) - if hash&newbit != 0 { - useY = 1 - } - } - - b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap - dst := &xy[useY] // evacuation destination - - if dst.i == bucketCnt { - dst.b = h.newoverflow(t, dst.b) - dst.i = 0 - dst.k = add(unsafe.Pointer(dst.b), dataOffset) - dst.v = add(dst.k, bucketCnt*4) - } - dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check - - // Copy key. - if sys.PtrSize == 4 && t.key.kind&kindNoPointers == 0 && writeBarrier.enabled { - // Write with a write barrier. - *(*unsafe.Pointer)(dst.k) = *(*unsafe.Pointer)(k) - } else { - *(*uint32)(dst.k) = *(*uint32)(k) - } - - typedmemmove(t.elem, dst.v, v) - dst.i++ - // These updates might push these pointers past the end of the - // key or value arrays. That's ok, as we have the overflow pointer - // at the end of the bucket to protect against pointing past the - // end of the bucket. - dst.k = add(dst.k, 4) - dst.v = add(dst.v, uintptr(t.valuesize)) - } - } - // Unlink the overflow buckets & clear key/value to help GC. - if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 { - b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)) - // Preserve b.tophash because the evacuation - // state is maintained there. - ptr := add(b, dataOffset) - n := uintptr(t.bucketsize) - dataOffset - memclrHasPointers(ptr, n) - } - } - - if oldbucket == h.nevacuate { - advanceEvacuationMark(h, t, newbit) - } -} - -func growWork_fast64(t *maptype, h *hmap, bucket uintptr) { - // make sure we evacuate the oldbucket corresponding - // to the bucket we're about to use - evacuate_fast64(t, h, bucket&h.oldbucketmask()) - - // evacuate one more oldbucket to make progress on growing - if h.growing() { - evacuate_fast64(t, h, h.nevacuate) - } -} - -func evacuate_fast64(t *maptype, h *hmap, oldbucket uintptr) { - b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) - newbit := h.noldbuckets() - if !evacuated(b) { - // TODO: reuse overflow buckets instead of using new ones, if there - // is no iterator using the old buckets. (If !oldIterator.) - - // xy contains the x and y (low and high) evacuation destinations. - var xy [2]evacDst - x := &xy[0] - x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize))) - x.k = add(unsafe.Pointer(x.b), dataOffset) - x.v = add(x.k, bucketCnt*8) - - if !h.sameSizeGrow() { - // Only calculate y pointers if we're growing bigger. - // Otherwise GC can see bad pointers. - y := &xy[1] - y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize))) - y.k = add(unsafe.Pointer(y.b), dataOffset) - y.v = add(y.k, bucketCnt*8) - } - - for ; b != nil; b = b.overflow(t) { - k := add(unsafe.Pointer(b), dataOffset) - v := add(k, bucketCnt*8) - for i := 0; i < bucketCnt; i, k, v = i+1, add(k, 8), add(v, uintptr(t.valuesize)) { - top := b.tophash[i] - if top == empty { - b.tophash[i] = evacuatedEmpty - continue - } - if top < minTopHash { - throw("bad map state") - } - var useY uint8 - if !h.sameSizeGrow() { - // Compute hash to make our evacuation decision (whether we need - // to send this key/value to bucket x or bucket y). - hash := t.key.alg.hash(k, uintptr(h.hash0)) - if hash&newbit != 0 { - useY = 1 - } - } - - b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap - dst := &xy[useY] // evacuation destination - - if dst.i == bucketCnt { - dst.b = h.newoverflow(t, dst.b) - dst.i = 0 - dst.k = add(unsafe.Pointer(dst.b), dataOffset) - dst.v = add(dst.k, bucketCnt*8) - } - dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check - - // Copy key. - if t.key.kind&kindNoPointers == 0 && writeBarrier.enabled { - if sys.PtrSize == 8 { - // Write with a write barrier. - *(*unsafe.Pointer)(dst.k) = *(*unsafe.Pointer)(k) - } else { - // There are three ways to squeeze at least one 32 bit pointer into 64 bits. - // Give up and call typedmemmove. - typedmemmove(t.key, dst.k, k) - } - } else { - *(*uint64)(dst.k) = *(*uint64)(k) - } - - typedmemmove(t.elem, dst.v, v) - dst.i++ - // These updates might push these pointers past the end of the - // key or value arrays. That's ok, as we have the overflow pointer - // at the end of the bucket to protect against pointing past the - // end of the bucket. - dst.k = add(dst.k, 8) - dst.v = add(dst.v, uintptr(t.valuesize)) - } - } - // Unlink the overflow buckets & clear key/value to help GC. - if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 { - b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)) - // Preserve b.tophash because the evacuation - // state is maintained there. - ptr := add(b, dataOffset) - n := uintptr(t.bucketsize) - dataOffset - memclrHasPointers(ptr, n) - } - } - - if oldbucket == h.nevacuate { - advanceEvacuationMark(h, t, newbit) - } -} - -func growWork_faststr(t *maptype, h *hmap, bucket uintptr) { - // make sure we evacuate the oldbucket corresponding - // to the bucket we're about to use - evacuate_faststr(t, h, bucket&h.oldbucketmask()) - - // evacuate one more oldbucket to make progress on growing - if h.growing() { - evacuate_faststr(t, h, h.nevacuate) - } -} - -func evacuate_faststr(t *maptype, h *hmap, oldbucket uintptr) { - b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) - newbit := h.noldbuckets() - if !evacuated(b) { - // TODO: reuse overflow buckets instead of using new ones, if there - // is no iterator using the old buckets. (If !oldIterator.) - - // xy contains the x and y (low and high) evacuation destinations. - var xy [2]evacDst - x := &xy[0] - x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize))) - x.k = add(unsafe.Pointer(x.b), dataOffset) - x.v = add(x.k, bucketCnt*2*sys.PtrSize) - - if !h.sameSizeGrow() { - // Only calculate y pointers if we're growing bigger. - // Otherwise GC can see bad pointers. - y := &xy[1] - y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize))) - y.k = add(unsafe.Pointer(y.b), dataOffset) - y.v = add(y.k, bucketCnt*2*sys.PtrSize) - } - - for ; b != nil; b = b.overflow(t) { - k := add(unsafe.Pointer(b), dataOffset) - v := add(k, bucketCnt*2*sys.PtrSize) - for i := 0; i < bucketCnt; i, k, v = i+1, add(k, 2*sys.PtrSize), add(v, uintptr(t.valuesize)) { - top := b.tophash[i] - if top == empty { - b.tophash[i] = evacuatedEmpty - continue - } - if top < minTopHash { - throw("bad map state") - } - var useY uint8 - if !h.sameSizeGrow() { - // Compute hash to make our evacuation decision (whether we need - // to send this key/value to bucket x or bucket y). - hash := t.key.alg.hash(k, uintptr(h.hash0)) - if hash&newbit != 0 { - useY = 1 - } - } - - b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap - dst := &xy[useY] // evacuation destination - - if dst.i == bucketCnt { - dst.b = h.newoverflow(t, dst.b) - dst.i = 0 - dst.k = add(unsafe.Pointer(dst.b), dataOffset) - dst.v = add(dst.k, bucketCnt*2*sys.PtrSize) - } - dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check - - // Copy key. - *(*string)(dst.k) = *(*string)(k) - - typedmemmove(t.elem, dst.v, v) - dst.i++ - // These updates might push these pointers past the end of the - // key or value arrays. That's ok, as we have the overflow pointer - // at the end of the bucket to protect against pointing past the - // end of the bucket. - dst.k = add(dst.k, 2*sys.PtrSize) - dst.v = add(dst.v, uintptr(t.valuesize)) - } - } - // Unlink the overflow buckets & clear key/value to help GC. - // Unlink the overflow buckets & clear key/value to help GC. - if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 { - b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)) - // Preserve b.tophash because the evacuation - // state is maintained there. - ptr := add(b, dataOffset) - n := uintptr(t.bucketsize) - dataOffset - memclrHasPointers(ptr, n) - } - } - - if oldbucket == h.nevacuate { - advanceEvacuationMark(h, t, newbit) - } -} diff --git a/src/runtime/map.go b/src/runtime/map.go new file mode 100644 index 0000000000..eddb045622 --- /dev/null +++ b/src/runtime/map.go @@ -0,0 +1,1249 @@ +// Copyright 2014 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package runtime + +// This file contains the implementation of Go's map type. +// +// A map is just a hash table. The data is arranged +// into an array of buckets. Each bucket contains up to +// 8 key/value pairs. The low-order bits of the hash are +// used to select a bucket. Each bucket contains a few +// high-order bits of each hash to distinguish the entries +// within a single bucket. +// +// If more than 8 keys hash to a bucket, we chain on +// extra buckets. +// +// When the hashtable grows, we allocate a new array +// of buckets twice as big. Buckets are incrementally +// copied from the old bucket array to the new bucket array. +// +// Map iterators walk through the array of buckets and +// return the keys in walk order (bucket #, then overflow +// chain order, then bucket index). To maintain iteration +// semantics, we never move keys within their bucket (if +// we did, keys might be returned 0 or 2 times). When +// growing the table, iterators remain iterating through the +// old table and must check the new table if the bucket +// they are iterating through has been moved ("evacuated") +// to the new table. + +// Picking loadFactor: too large and we have lots of overflow +// buckets, too small and we waste a lot of space. I wrote +// a simple program to check some stats for different loads: +// (64-bit, 8 byte keys and values) +// 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 +// +// %overflow = percentage of buckets which have an overflow bucket +// bytes/entry = overhead bytes used per key/value pair +// hitprobe = # of entries to check when looking up a present key +// missprobe = # of entries to check when looking up an absent key +// +// Keep in mind this data is for maximally loaded tables, i.e. just +// before the table grows. Typical tables will be somewhat less loaded. + +import ( + "runtime/internal/atomic" + "runtime/internal/sys" + "unsafe" +) + +const ( + // Maximum number of key/value pairs a bucket can hold. + bucketCntBits = 3 + bucketCnt = 1 << bucketCntBits + + // Maximum average load of a bucket that triggers growth is 6.5. + // Represent as loadFactorNum/loadFactDen, to allow integer math. + loadFactorNum = 13 + loadFactorDen = 2 + + // Maximum key or value size to keep inline (instead of mallocing per element). + // Must fit in a uint8. + // Fast versions cannot handle big values - the cutoff size for + // fast versions in ../../cmd/internal/gc/walk.go must be at most this value. + maxKeySize = 128 + maxValueSize = 128 + + // data offset should be the size of the bmap struct, but needs to be + // aligned correctly. For amd64p32 this means 64-bit alignment + // even though pointers are 32 bit. + dataOffset = unsafe.Offsetof(struct { + b bmap + v int64 + }{}.v) + + // Possible tophash values. We reserve a few possibilities for special marks. + // Each bucket (including its overflow buckets, if any) will have either all or none of its + // entries in the evacuated* states (except during the evacuate() method, which only happens + // during map writes and thus no one else can observe the map during that time). + empty = 0 // cell is empty + evacuatedEmpty = 1 // cell is empty, bucket is evacuated. + evacuatedX = 2 // key/value is valid. Entry has been evacuated to first half of larger table. + evacuatedY = 3 // same as above, but evacuated to second half of larger table. + minTopHash = 4 // minimum tophash for a normal filled cell. + + // flags + iterator = 1 // there may be an iterator using buckets + oldIterator = 2 // there may be an iterator using oldbuckets + hashWriting = 4 // a goroutine is writing to the map + sameSizeGrow = 8 // the current map growth is to a new map of the same size + + // sentinel bucket ID for iterator checks + noCheck = 1<<(8*sys.PtrSize) - 1 +) + +// A header for a Go map. +type hmap struct { + // Note: the format of the Hmap is encoded in ../../cmd/internal/gc/reflect.go and + // ../reflect/type.go. Don't change this structure without also changing that code! + count int // # live cells == size of map. Must be first (used by len() builtin) + flags uint8 + B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items) + noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details + hash0 uint32 // hash seed + + buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0. + oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing + nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated) + + extra *mapextra // optional fields +} + +// mapextra holds fields that are not present on all maps. +type mapextra struct { + // If both key and value do not contain pointers and are inline, then we mark bucket + // type as containing no pointers. This avoids scanning such maps. + // However, bmap.overflow is a pointer. In order to keep overflow buckets + // alive, we store pointers to all overflow buckets in hmap.overflow and h.map.oldoverflow. + // overflow and oldoverflow are only used if key and value do not contain pointers. + // overflow contains overflow buckets for hmap.buckets. + // oldoverflow contains overflow buckets for hmap.oldbuckets. + // The indirection allows to store a pointer to the slice in hiter. + overflow *[]*bmap + oldoverflow *[]*bmap + + // nextOverflow holds a pointer to a free overflow bucket. + nextOverflow *bmap +} + +// A bucket for a Go map. +type bmap struct { + // tophash generally contains the top byte of the hash value + // for each key in this bucket. If tophash[0] < minTopHash, + // tophash[0] is a bucket evacuation state instead. + tophash [bucketCnt]uint8 + // Followed by bucketCnt keys and then bucketCnt values. + // NOTE: packing all the keys together and then all the values together makes the + // code a bit more complicated than alternating key/value/key/value/... but it allows + // us to eliminate padding which would be needed for, e.g., map[int64]int8. + // Followed by an overflow pointer. +} + +// A hash iteration structure. +// If you modify hiter, also change cmd/internal/gc/reflect.go to indicate +// the layout of this structure. +type hiter struct { + key unsafe.Pointer // Must be in first position. Write nil to indicate iteration end (see cmd/internal/gc/range.go). + value unsafe.Pointer // Must be in second position (see cmd/internal/gc/range.go). + t *maptype + h *hmap + buckets unsafe.Pointer // bucket ptr at hash_iter initialization time + bptr *bmap // current bucket + overflow *[]*bmap // keeps overflow buckets of hmap.buckets alive + oldoverflow *[]*bmap // keeps overflow buckets of hmap.oldbuckets alive + startBucket uintptr // bucket iteration started at + offset uint8 // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1) + wrapped bool // already wrapped around from end of bucket array to beginning + B uint8 + i uint8 + bucket uintptr + checkBucket uintptr +} + +// bucketShift returns 1<> (sys.PtrSize*8 - 8)) + if top < minTopHash { + top += minTopHash + } + return top +} + +func evacuated(b *bmap) bool { + h := b.tophash[0] + return h > empty && h < minTopHash +} + +func (b *bmap) overflow(t *maptype) *bmap { + return *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize)) +} + +func (b *bmap) setoverflow(t *maptype, ovf *bmap) { + *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize)) = ovf +} + +func (b *bmap) keys() unsafe.Pointer { + return add(unsafe.Pointer(b), dataOffset) +} + +// incrnoverflow increments h.noverflow. +// noverflow counts the number of overflow buckets. +// This is used to trigger same-size map growth. +// See also tooManyOverflowBuckets. +// To keep hmap small, noverflow is a uint16. +// When there are few buckets, noverflow is an exact count. +// When there are many buckets, noverflow is an approximate count. +func (h *hmap) incrnoverflow() { + // We trigger same-size map growth if there are + // as many overflow buckets as buckets. + // We need to be able to count to 1< int(maxSliceCap(t.bucket.size)) { + hint = 0 + } + + // initialize Hmap + if h == nil { + h = new(hmap) + } + h.hash0 = fastrand() + + // find size parameter which will hold the requested # of elements + B := uint8(0) + for overLoadFactor(hint, B) { + B++ + } + h.B = B + + // allocate initial hash table + // if B == 0, the buckets field is allocated lazily later (in mapassign) + // If hint is large zeroing this memory could take a while. + if h.B != 0 { + var nextOverflow *bmap + h.buckets, nextOverflow = makeBucketArray(t, h.B) + if nextOverflow != nil { + h.extra = new(mapextra) + h.extra.nextOverflow = nextOverflow + } + } + + return h +} + +// mapaccess1 returns a pointer to h[key]. Never returns nil, instead +// it will return a reference to the zero object for the value type if +// the key is not in the map. +// NOTE: The returned pointer may keep the whole map live, so don't +// hold onto it for very long. +func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { + if raceenabled && h != nil { + callerpc := getcallerpc() + pc := funcPC(mapaccess1) + racereadpc(unsafe.Pointer(h), callerpc, pc) + raceReadObjectPC(t.key, key, callerpc, pc) + } + if msanenabled && h != nil { + msanread(key, t.key.size) + } + if h == nil || h.count == 0 { + 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)) + m := bucketMask(h.B) + b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))) + if c := h.oldbuckets; c != nil { + if !h.sameSizeGrow() { + // There used to be half as many buckets; mask down one more power of two. + m >>= 1 + } + oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) + if !evacuated(oldb) { + b = oldb + } + } + top := tophash(hash) + for ; b != nil; b = b.overflow(t) { + for i := uintptr(0); i < bucketCnt; i++ { + if b.tophash[i] != top { + continue + } + k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) + if t.indirectkey { + k = *((*unsafe.Pointer)(k)) + } + if alg.equal(key, k) { + v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) + if t.indirectvalue { + v = *((*unsafe.Pointer)(v)) + } + return v + } + } + } + return unsafe.Pointer(&zeroVal[0]) +} + +func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) { + if raceenabled && h != nil { + callerpc := getcallerpc() + pc := funcPC(mapaccess2) + racereadpc(unsafe.Pointer(h), callerpc, pc) + raceReadObjectPC(t.key, key, callerpc, pc) + } + if msanenabled && h != nil { + msanread(key, t.key.size) + } + if h == nil || h.count == 0 { + 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)) + m := bucketMask(h.B) + b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize))) + if c := h.oldbuckets; c != nil { + if !h.sameSizeGrow() { + // There used to be half as many buckets; mask down one more power of two. + m >>= 1 + } + oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize))) + if !evacuated(oldb) { + b = oldb + } + } + top := tophash(hash) + for ; b != nil; b = b.overflow(t) { + for i := uintptr(0); i < bucketCnt; i++ { + if b.tophash[i] != top { + continue + } + k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) + if t.indirectkey { + k = *((*unsafe.Pointer)(k)) + } + if alg.equal(key, k) { + v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) + if t.indirectvalue { + v = *((*unsafe.Pointer)(v)) + } + return v, true + } + } + } + return unsafe.Pointer(&zeroVal[0]), false +} + +// returns both key and value. Used by map iterator +func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer) { + if h == nil || h.count == 0 { + return nil, nil + } + alg := t.key.alg + hash := alg.hash(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 { + if !h.sameSizeGrow() { + // There used to be half as many buckets; mask down one more power of two. + m >>= 1 + } + oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize))) + if !evacuated(oldb) { + b = oldb + } + } + top := tophash(hash) + for ; b != nil; b = b.overflow(t) { + for i := uintptr(0); i < bucketCnt; i++ { + if b.tophash[i] != top { + continue + } + k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) + if t.indirectkey { + k = *((*unsafe.Pointer)(k)) + } + if alg.equal(key, k) { + v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) + if t.indirectvalue { + v = *((*unsafe.Pointer)(v)) + } + return k, v + } + } + } + return nil, nil +} + +func mapaccess1_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) unsafe.Pointer { + v := mapaccess1(t, h, key) + if v == unsafe.Pointer(&zeroVal[0]) { + return zero + } + return v +} + +func mapaccess2_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) (unsafe.Pointer, bool) { + v := mapaccess1(t, h, key) + if v == unsafe.Pointer(&zeroVal[0]) { + return zero, false + } + return v, true +} + +// Like mapaccess, but allocates a slot for the key if it is not present in the map. +func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { + if h == nil { + panic(plainError("assignment to entry in nil map")) + } + if raceenabled { + callerpc := getcallerpc() + pc := funcPC(mapassign) + racewritepc(unsafe.Pointer(h), callerpc, pc) + raceReadObjectPC(t.key, key, callerpc, pc) + } + if msanenabled { + msanread(key, t.key.size) + } + if h.flags&hashWriting != 0 { + throw("concurrent map writes") + } + alg := t.key.alg + hash := alg.hash(key, uintptr(h.hash0)) + + // Set hashWriting after calling alg.hash, since alg.hash may panic, + // in which case we have not actually done a write. + h.flags |= hashWriting + + if h.buckets == nil { + h.buckets = newobject(t.bucket) // newarray(t.bucket, 1) + } + +again: + bucket := hash & bucketMask(h.B) + if h.growing() { + growWork(t, h, bucket) + } + b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize))) + top := tophash(hash) + + var inserti *uint8 + var insertk unsafe.Pointer + var val unsafe.Pointer + for { + for i := uintptr(0); i < bucketCnt; i++ { + if b.tophash[i] != top { + if b.tophash[i] == empty && inserti == nil { + inserti = &b.tophash[i] + insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) + val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) + } + continue + } + k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) + if t.indirectkey { + k = *((*unsafe.Pointer)(k)) + } + if !alg.equal(key, k) { + continue + } + // already have a mapping for key. Update it. + if t.needkeyupdate { + typedmemmove(t.key, k, key) + } + val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) + goto done + } + ovf := b.overflow(t) + if ovf == nil { + break + } + b = ovf + } + + // Did not find mapping for key. Allocate new cell & add entry. + + // If we hit the max load factor or we have too many overflow buckets, + // and we're not already in the middle of growing, start growing. + if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { + hashGrow(t, h) + goto again // Growing the table invalidates everything, so try again + } + + if inserti == nil { + // all current buckets are full, allocate a new one. + newb := h.newoverflow(t, b) + inserti = &newb.tophash[0] + insertk = add(unsafe.Pointer(newb), dataOffset) + val = add(insertk, bucketCnt*uintptr(t.keysize)) + } + + // store new key/value at insert position + if t.indirectkey { + kmem := newobject(t.key) + *(*unsafe.Pointer)(insertk) = kmem + insertk = kmem + } + if t.indirectvalue { + vmem := newobject(t.elem) + *(*unsafe.Pointer)(val) = vmem + } + typedmemmove(t.key, insertk, key) + *inserti = top + h.count++ + +done: + if h.flags&hashWriting == 0 { + throw("concurrent map writes") + } + h.flags &^= hashWriting + if t.indirectvalue { + val = *((*unsafe.Pointer)(val)) + } + return val +} + +func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { + if raceenabled && h != nil { + callerpc := getcallerpc() + pc := funcPC(mapdelete) + racewritepc(unsafe.Pointer(h), callerpc, pc) + raceReadObjectPC(t.key, key, callerpc, pc) + } + if msanenabled && h != nil { + msanread(key, t.key.size) + } + if h == nil || h.count == 0 { + return + } + if h.flags&hashWriting != 0 { + throw("concurrent map writes") + } + + alg := t.key.alg + hash := alg.hash(key, uintptr(h.hash0)) + + // Set hashWriting after calling alg.hash, since alg.hash may panic, + // in which case we have not actually done a write (delete). + h.flags |= hashWriting + + bucket := hash & bucketMask(h.B) + if h.growing() { + growWork(t, h, bucket) + } + b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) + top := tophash(hash) +search: + for ; b != nil; b = b.overflow(t) { + for i := uintptr(0); i < bucketCnt; i++ { + if b.tophash[i] != top { + continue + } + k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) + k2 := k + if t.indirectkey { + k2 = *((*unsafe.Pointer)(k2)) + } + if !alg.equal(key, k2) { + continue + } + // Only clear key if there are pointers in it. + if t.indirectkey { + *(*unsafe.Pointer)(k) = nil + } else if t.key.kind&kindNoPointers == 0 { + memclrHasPointers(k, t.key.size) + } + // Only clear value if there are pointers in it. + if t.indirectvalue || t.elem.kind&kindNoPointers == 0 { + v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) + if t.indirectvalue { + *(*unsafe.Pointer)(v) = nil + } else { + memclrHasPointers(v, t.elem.size) + } + } + b.tophash[i] = empty + h.count-- + break search + } + } + + if h.flags&hashWriting == 0 { + throw("concurrent map writes") + } + h.flags &^= hashWriting +} + +// mapiterinit initializes the hiter struct used for ranging over maps. +// The hiter struct pointed to by 'it' is allocated on the stack +// by the compilers order pass or on the heap by reflect_mapiterinit. +// Both need to have zeroed hiter since the struct contains pointers. +func mapiterinit(t *maptype, h *hmap, it *hiter) { + if raceenabled && h != nil { + callerpc := getcallerpc() + racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiterinit)) + } + + if h == nil || h.count == 0 { + return + } + + if unsafe.Sizeof(hiter{})/sys.PtrSize != 12 { + throw("hash_iter size incorrect") // see ../../cmd/internal/gc/reflect.go + } + it.t = t + it.h = h + + // grab snapshot of bucket state + it.B = h.B + it.buckets = h.buckets + if t.bucket.kind&kindNoPointers != 0 { + // Allocate the current slice and remember pointers to both current and old. + // This preserves all relevant overflow buckets alive even if + // the table grows and/or overflow buckets are added to the table + // while we are iterating. + h.createOverflow() + it.overflow = h.extra.overflow + it.oldoverflow = h.extra.oldoverflow + } + + // decide where to start + r := uintptr(fastrand()) + if h.B > 31-bucketCntBits { + r += uintptr(fastrand()) << 31 + } + it.startBucket = r & bucketMask(h.B) + it.offset = uint8(r >> h.B & (bucketCnt - 1)) + + // iterator state + it.bucket = it.startBucket + + // Remember we have an iterator. + // Can run concurrently with another mapiterinit(). + if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator { + atomic.Or8(&h.flags, iterator|oldIterator) + } + + mapiternext(it) +} + +func mapiternext(it *hiter) { + h := it.h + if raceenabled { + callerpc := getcallerpc() + racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiternext)) + } + if h.flags&hashWriting != 0 { + throw("concurrent map iteration and map write") + } + t := it.t + bucket := it.bucket + b := it.bptr + i := it.i + checkBucket := it.checkBucket + alg := t.key.alg + +next: + if b == nil { + if bucket == it.startBucket && it.wrapped { + // end of iteration + it.key = nil + it.value = nil + return + } + if h.growing() && it.B == h.B { + // Iterator was started in the middle of a grow, and the grow isn't done yet. + // If the bucket we're looking at hasn't been filled in yet (i.e. the old + // bucket hasn't been evacuated) then we need to iterate through the old + // bucket and only return the ones that will be migrated to this bucket. + oldbucket := bucket & it.h.oldbucketmask() + b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) + if !evacuated(b) { + checkBucket = bucket + } else { + b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize))) + checkBucket = noCheck + } + } else { + b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize))) + checkBucket = noCheck + } + bucket++ + if bucket == bucketShift(it.B) { + bucket = 0 + it.wrapped = true + } + i = 0 + } + for ; i < bucketCnt; i++ { + offi := (i + it.offset) & (bucketCnt - 1) + if b.tophash[offi] == empty || b.tophash[offi] == evacuatedEmpty { + continue + } + k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize)) + if t.indirectkey { + k = *((*unsafe.Pointer)(k)) + } + v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.valuesize)) + if checkBucket != noCheck && !h.sameSizeGrow() { + // Special case: iterator was started during a grow to a larger size + // and the grow is not done yet. We're working on a bucket whose + // oldbucket has not been evacuated yet. Or at least, it wasn't + // evacuated when we started the bucket. So we're iterating + // 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 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)) + if hash&bucketMask(it.B) != checkBucket { + continue + } + } else { + // Hash isn't repeatable if k != k (NaNs). We need a + // repeatable and randomish choice of which direction + // to send NaNs during evacuation. We'll use the low + // bit of tophash to decide which way NaNs go. + // NOTE: this case is why we need two evacuate tophash + // values, evacuatedX and evacuatedY, that differ in + // their low bit. + if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) { + continue + } + } + } + if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) || + !(t.reflexivekey || alg.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. + // That's lucky for us because when key!=key we can't look it up successfully. + it.key = k + if t.indirectvalue { + v = *((*unsafe.Pointer)(v)) + } + it.value = v + } else { + // The hash table has grown since the iterator was started. + // The golden data for this key is now somewhere else. + // Check the current hash table for the data. + // This code handles the case where the key + // has been deleted, updated, or deleted and reinserted. + // NOTE: we need to regrab the key as it has potentially been + // updated to an equal() but not identical key (e.g. +0.0 vs -0.0). + rk, rv := mapaccessK(t, h, k) + if rk == nil { + continue // key has been deleted + } + it.key = rk + it.value = rv + } + it.bucket = bucket + if it.bptr != b { // avoid unnecessary write barrier; see issue 14921 + it.bptr = b + } + it.i = i + 1 + it.checkBucket = checkBucket + return + } + b = b.overflow(t) + i = 0 + goto next +} + +func makeBucketArray(t *maptype, b uint8) (buckets unsafe.Pointer, nextOverflow *bmap) { + base := bucketShift(b) + nbuckets := base + // For small b, overflow buckets are unlikely. + // Avoid the overhead of the calculation. + if b >= 4 { + // Add on the estimated number of overflow buckets + // required to insert the median number of elements + // used with this value of b. + nbuckets += bucketShift(b - 4) + sz := t.bucket.size * nbuckets + up := roundupsize(sz) + if up != sz { + nbuckets = up / t.bucket.size + } + } + buckets = newarray(t.bucket, int(nbuckets)) + if base != nbuckets { + // We preallocated some overflow buckets. + // To keep the overhead of tracking these overflow buckets to a minimum, + // we use the convention that if a preallocated overflow bucket's overflow + // pointer is nil, then there are more available by bumping the pointer. + // We need a safe non-nil pointer for the last overflow bucket; just use buckets. + nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize))) + last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize))) + last.setoverflow(t, (*bmap)(buckets)) + } + return buckets, nextOverflow +} + +func hashGrow(t *maptype, h *hmap) { + // If we've hit the load factor, get bigger. + // Otherwise, there are too many overflow buckets, + // so keep the same number of buckets and "grow" laterally. + bigger := uint8(1) + if !overLoadFactor(h.count+1, h.B) { + bigger = 0 + h.flags |= sameSizeGrow + } + oldbuckets := h.buckets + newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger) + + flags := h.flags &^ (iterator | oldIterator) + if h.flags&iterator != 0 { + flags |= oldIterator + } + // commit the grow (atomic wrt gc) + h.B += bigger + h.flags = flags + h.oldbuckets = oldbuckets + h.buckets = newbuckets + h.nevacuate = 0 + h.noverflow = 0 + + if h.extra != nil && h.extra.overflow != nil { + // Promote current overflow buckets to the old generation. + if h.extra.oldoverflow != nil { + throw("oldoverflow is not nil") + } + h.extra.oldoverflow = h.extra.overflow + h.extra.overflow = nil + } + if nextOverflow != nil { + if h.extra == nil { + h.extra = new(mapextra) + } + h.extra.nextOverflow = nextOverflow + } + + // the actual copying of the hash table data is done incrementally + // by growWork() and evacuate(). +} + +// overLoadFactor reports whether count items placed in 1< bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen) +} + +// tooManyOverflowBuckets reports whether noverflow buckets is too many for a map with 1< 15 { + B = 15 + } + // The compiler doesn't see here that B < 16; mask B to generate shorter shift code. + return noverflow >= uint16(1)<<(B&15) +} + +// growing reports whether h is growing. The growth may be to the same size or bigger. +func (h *hmap) growing() bool { + return h.oldbuckets != nil +} + +// sameSizeGrow reports whether the current growth is to a map of the same size. +func (h *hmap) sameSizeGrow() bool { + return h.flags&sameSizeGrow != 0 +} + +// noldbuckets calculates the number of buckets prior to the current map growth. +func (h *hmap) noldbuckets() uintptr { + oldB := h.B + if !h.sameSizeGrow() { + oldB-- + } + return bucketShift(oldB) +} + +// oldbucketmask provides a mask that can be applied to calculate n % noldbuckets(). +func (h *hmap) oldbucketmask() uintptr { + return h.noldbuckets() - 1 +} + +func growWork(t *maptype, h *hmap, bucket uintptr) { + // make sure we evacuate the oldbucket corresponding + // to the bucket we're about to use + evacuate(t, h, bucket&h.oldbucketmask()) + + // evacuate one more oldbucket to make progress on growing + if h.growing() { + evacuate(t, h, h.nevacuate) + } +} + +func bucketEvacuated(t *maptype, h *hmap, bucket uintptr) bool { + b := (*bmap)(add(h.oldbuckets, bucket*uintptr(t.bucketsize))) + return evacuated(b) +} + +// evacDst is an evacuation destination. +type evacDst struct { + b *bmap // current destination bucket + i int // key/val index into b + k unsafe.Pointer // pointer to current key storage + v unsafe.Pointer // pointer to current value storage +} + +func evacuate(t *maptype, h *hmap, oldbucket uintptr) { + b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) + newbit := h.noldbuckets() + if !evacuated(b) { + // TODO: reuse overflow buckets instead of using new ones, if there + // is no iterator using the old buckets. (If !oldIterator.) + + // xy contains the x and y (low and high) evacuation destinations. + var xy [2]evacDst + x := &xy[0] + x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize))) + x.k = add(unsafe.Pointer(x.b), dataOffset) + x.v = add(x.k, bucketCnt*uintptr(t.keysize)) + + if !h.sameSizeGrow() { + // Only calculate y pointers if we're growing bigger. + // Otherwise GC can see bad pointers. + y := &xy[1] + y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize))) + y.k = add(unsafe.Pointer(y.b), dataOffset) + y.v = add(y.k, bucketCnt*uintptr(t.keysize)) + } + + for ; b != nil; b = b.overflow(t) { + k := add(unsafe.Pointer(b), dataOffset) + v := add(k, bucketCnt*uintptr(t.keysize)) + for i := 0; i < bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) { + top := b.tophash[i] + if top == empty { + b.tophash[i] = evacuatedEmpty + continue + } + if top < minTopHash { + throw("bad map state") + } + k2 := k + if t.indirectkey { + k2 = *((*unsafe.Pointer)(k2)) + } + var useY uint8 + if !h.sameSizeGrow() { + // Compute hash to make our evacuation decision (whether we need + // to send this key/value 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) { + // 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 + // presence of iterators, as our evacuation decision must + // match whatever decision the iterator made. + // Fortunately, we have the freedom to send these keys either + // way. Also, tophash is meaningless for these kinds of keys. + // We let the low bit of tophash drive the evacuation decision. + // We recompute a new random tophash for the next level so + // these keys will get evenly distributed across all buckets + // after multiple grows. + useY = top & 1 + top = tophash(hash) + } else { + if hash&newbit != 0 { + useY = 1 + } + } + } + + if evacuatedX+1 != evacuatedY { + throw("bad evacuatedN") + } + + b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY + dst := &xy[useY] // evacuation destination + + if dst.i == bucketCnt { + dst.b = h.newoverflow(t, dst.b) + dst.i = 0 + dst.k = add(unsafe.Pointer(dst.b), dataOffset) + dst.v = add(dst.k, bucketCnt*uintptr(t.keysize)) + } + dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check + if t.indirectkey { + *(*unsafe.Pointer)(dst.k) = k2 // copy pointer + } else { + typedmemmove(t.key, dst.k, k) // copy value + } + if t.indirectvalue { + *(*unsafe.Pointer)(dst.v) = *(*unsafe.Pointer)(v) + } else { + typedmemmove(t.elem, dst.v, v) + } + dst.i++ + // These updates might push these pointers past the end of the + // key or value arrays. That's ok, as we have the overflow pointer + // at the end of the bucket to protect against pointing past the + // end of the bucket. + dst.k = add(dst.k, uintptr(t.keysize)) + dst.v = add(dst.v, uintptr(t.valuesize)) + } + } + // Unlink the overflow buckets & clear key/value to help GC. + if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 { + b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)) + // Preserve b.tophash because the evacuation + // state is maintained there. + ptr := add(b, dataOffset) + n := uintptr(t.bucketsize) - dataOffset + memclrHasPointers(ptr, n) + } + } + + if oldbucket == h.nevacuate { + advanceEvacuationMark(h, t, newbit) + } +} + +func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) { + h.nevacuate++ + // Experiments suggest that 1024 is overkill by at least an order of magnitude. + // Put it in there as a safeguard anyway, to ensure O(1) behavior. + stop := h.nevacuate + 1024 + if stop > newbit { + stop = newbit + } + for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) { + h.nevacuate++ + } + if h.nevacuate == newbit { // newbit == # of oldbuckets + // Growing is all done. Free old main bucket array. + h.oldbuckets = nil + // Can discard old overflow buckets as well. + // If they are still referenced by an iterator, + // then the iterator holds a pointers to the slice. + if h.extra != nil { + h.extra.oldoverflow = nil + } + h.flags &^= sameSizeGrow + } +} + +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 sz := unsafe.Sizeof(hmap{}); sz != t.hmap.size { + println("runtime: sizeof(hmap) =", sz, ", t.hmap.size =", t.hmap.size) + throw("bad hmap size") + } + if !ismapkey(t.key) { + throw("runtime.reflect_makemap: unsupported map key type") + } + if t.key.size > maxKeySize && (!t.indirectkey || t.keysize != uint8(sys.PtrSize)) || + t.key.size <= maxKeySize && (t.indirectkey || t.keysize != uint8(t.key.size)) { + throw("key size wrong") + } + if t.elem.size > maxValueSize && (!t.indirectvalue || t.valuesize != uint8(sys.PtrSize)) || + t.elem.size <= maxValueSize && (t.indirectvalue || t.valuesize != uint8(t.elem.size)) { + throw("value size wrong") + } + if t.key.align > bucketCnt { + throw("key align too big") + } + if t.elem.align > bucketCnt { + throw("value align too big") + } + if t.key.size%uintptr(t.key.align) != 0 { + throw("key size not a multiple of key align") + } + if t.elem.size%uintptr(t.elem.align) != 0 { + throw("value size not a multiple of value align") + } + if bucketCnt < 8 { + throw("bucketsize too small for proper alignment") + } + if dataOffset%uintptr(t.key.align) != 0 { + throw("need padding in bucket (key)") + } + if dataOffset%uintptr(t.elem.align) != 0 { + throw("need padding in bucket (value)") + } + + return makemap(t, cap, nil) +} + +//go:linkname reflect_mapaccess reflect.mapaccess +func reflect_mapaccess(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { + val, ok := mapaccess2(t, h, key) + if !ok { + // reflect wants nil for a missing element + val = nil + } + return val +} + +//go:linkname reflect_mapassign reflect.mapassign +func reflect_mapassign(t *maptype, h *hmap, key unsafe.Pointer, val unsafe.Pointer) { + p := mapassign(t, h, key) + typedmemmove(t.elem, p, val) +} + +//go:linkname reflect_mapdelete reflect.mapdelete +func reflect_mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { + mapdelete(t, h, key) +} + +//go:linkname reflect_mapiterinit reflect.mapiterinit +func reflect_mapiterinit(t *maptype, h *hmap) *hiter { + it := new(hiter) + mapiterinit(t, h, it) + return it +} + +//go:linkname reflect_mapiternext reflect.mapiternext +func reflect_mapiternext(it *hiter) { + mapiternext(it) +} + +//go:linkname reflect_mapiterkey reflect.mapiterkey +func reflect_mapiterkey(it *hiter) unsafe.Pointer { + return it.key +} + +//go:linkname reflect_maplen reflect.maplen +func reflect_maplen(h *hmap) int { + if h == nil { + return 0 + } + if raceenabled { + callerpc := getcallerpc() + racereadpc(unsafe.Pointer(h), callerpc, funcPC(reflect_maplen)) + } + 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 +var zeroVal [maxZero]byte diff --git a/src/runtime/map_benchmark_test.go b/src/runtime/map_benchmark_test.go new file mode 100644 index 0000000000..aec0c51f3f --- /dev/null +++ b/src/runtime/map_benchmark_test.go @@ -0,0 +1,343 @@ +// Copyright 2013 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. +package runtime_test + +import ( + "fmt" + "strconv" + "strings" + "testing" +) + +const size = 10 + +func BenchmarkHashStringSpeed(b *testing.B) { + strings := make([]string, size) + for i := 0; i < size; i++ { + strings[i] = fmt.Sprintf("string#%d", i) + } + sum := 0 + m := make(map[string]int, size) + for i := 0; i < size; i++ { + m[strings[i]] = 0 + } + idx := 0 + b.ResetTimer() + for i := 0; i < b.N; i++ { + sum += m[strings[idx]] + idx++ + if idx == size { + idx = 0 + } + } +} + +type chunk [17]byte + +func BenchmarkHashBytesSpeed(b *testing.B) { + // a bunch of chunks, each with a different alignment mod 16 + var chunks [size]chunk + // initialize each to a different value + for i := 0; i < size; i++ { + chunks[i][0] = byte(i) + } + // put into a map + m := make(map[chunk]int, size) + for i, c := range chunks { + m[c] = i + } + idx := 0 + b.ResetTimer() + for i := 0; i < b.N; i++ { + if m[chunks[idx]] != idx { + b.Error("bad map entry for chunk") + } + 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 + } + } +} +func BenchmarkHashStringArraySpeed(b *testing.B) { + stringpairs := make([][2]string, size) + for i := 0; i < size; i++ { + for j := 0; j < 2; j++ { + stringpairs[i][j] = fmt.Sprintf("string#%d/%d", i, j) + } + } + sum := 0 + m := make(map[[2]string]int, size) + for i := 0; i < size; i++ { + m[stringpairs[i]] = 0 + } + idx := 0 + b.ResetTimer() + for i := 0; i < b.N; i++ { + sum += m[stringpairs[idx]] + idx++ + if idx == size { + idx = 0 + } + } +} + +func BenchmarkMegMap(b *testing.B) { + m := make(map[string]bool) + for suffix := 'A'; suffix <= 'G'; suffix++ { + m[strings.Repeat("X", 1<<20-1)+fmt.Sprint(suffix)] = true + } + key := strings.Repeat("X", 1<<20-1) + "k" + b.ResetTimer() + for i := 0; i < b.N; i++ { + _, _ = m[key] + } +} + +func BenchmarkMegOneMap(b *testing.B) { + m := make(map[string]bool) + m[strings.Repeat("X", 1<<20)] = true + key := strings.Repeat("Y", 1<<20) + b.ResetTimer() + for i := 0; i < b.N; i++ { + _, _ = m[key] + } +} + +func BenchmarkMegEqMap(b *testing.B) { + m := make(map[string]bool) + key1 := strings.Repeat("X", 1<<20) + key2 := strings.Repeat("X", 1<<20) // equal but different instance + m[key1] = true + b.ResetTimer() + for i := 0; i < b.N; i++ { + _, _ = m[key2] + } +} + +func BenchmarkMegEmptyMap(b *testing.B) { + m := make(map[string]bool) + key := strings.Repeat("X", 1<<20) + b.ResetTimer() + for i := 0; i < b.N; i++ { + _, _ = m[key] + } +} + +func BenchmarkSmallStrMap(b *testing.B) { + m := make(map[string]bool) + for suffix := 'A'; suffix <= 'G'; suffix++ { + m[fmt.Sprint(suffix)] = true + } + key := "k" + b.ResetTimer() + for i := 0; i < b.N; i++ { + _, _ = m[key] + } +} + +func BenchmarkMapStringKeysEight_16(b *testing.B) { benchmarkMapStringKeysEight(b, 16) } +func BenchmarkMapStringKeysEight_32(b *testing.B) { benchmarkMapStringKeysEight(b, 32) } +func BenchmarkMapStringKeysEight_64(b *testing.B) { benchmarkMapStringKeysEight(b, 64) } +func BenchmarkMapStringKeysEight_1M(b *testing.B) { benchmarkMapStringKeysEight(b, 1<<20) } + +func benchmarkMapStringKeysEight(b *testing.B, keySize int) { + m := make(map[string]bool) + for i := 0; i < 8; i++ { + m[strings.Repeat("K", i+1)] = true + } + key := strings.Repeat("K", keySize) + b.ResetTimer() + for i := 0; i < b.N; i++ { + _ = m[key] + } +} + +func BenchmarkIntMap(b *testing.B) { + m := make(map[int]bool) + for i := 0; i < 8; i++ { + m[i] = true + } + b.ResetTimer() + for i := 0; i < b.N; i++ { + _, _ = m[7] + } +} + +// Accessing the same keys in a row. +func benchmarkRepeatedLookup(b *testing.B, lookupKeySize int) { + m := make(map[string]bool) + // At least bigger than a single bucket: + for i := 0; i < 64; i++ { + m[fmt.Sprintf("some key %d", i)] = true + } + base := strings.Repeat("x", lookupKeySize-1) + key1 := base + "1" + key2 := base + "2" + b.ResetTimer() + for i := 0; i < b.N/4; i++ { + _ = m[key1] + _ = m[key1] + _ = m[key2] + _ = m[key2] + } +} + +func BenchmarkRepeatedLookupStrMapKey32(b *testing.B) { benchmarkRepeatedLookup(b, 32) } +func BenchmarkRepeatedLookupStrMapKey1M(b *testing.B) { benchmarkRepeatedLookup(b, 1<<20) } + +func BenchmarkNewEmptyMap(b *testing.B) { + b.ReportAllocs() + for i := 0; i < b.N; i++ { + _ = make(map[int]int) + } +} + +func BenchmarkNewSmallMap(b *testing.B) { + b.ReportAllocs() + for i := 0; i < b.N; i++ { + m := make(map[int]int) + m[0] = 0 + m[1] = 1 + } +} + +func BenchmarkMapIter(b *testing.B) { + m := make(map[int]bool) + for i := 0; i < 8; i++ { + m[i] = true + } + b.ResetTimer() + for i := 0; i < b.N; i++ { + for range m { + } + } +} + +func BenchmarkMapIterEmpty(b *testing.B) { + m := make(map[int]bool) + b.ResetTimer() + for i := 0; i < b.N; i++ { + for range m { + } + } +} + +func BenchmarkSameLengthMap(b *testing.B) { + // long strings, same length, differ in first few + // and last few bytes. + m := make(map[string]bool) + s1 := "foo" + strings.Repeat("-", 100) + "bar" + s2 := "goo" + strings.Repeat("-", 100) + "ber" + m[s1] = true + m[s2] = true + b.ResetTimer() + for i := 0; i < b.N; i++ { + _ = m[s1] + } +} + +type BigKey [3]int64 + +func BenchmarkBigKeyMap(b *testing.B) { + m := make(map[BigKey]bool) + k := BigKey{3, 4, 5} + m[k] = true + for i := 0; i < b.N; i++ { + _ = m[k] + } +} + +type BigVal [3]int64 + +func BenchmarkBigValMap(b *testing.B) { + m := make(map[BigKey]BigVal) + k := BigKey{3, 4, 5} + m[k] = BigVal{6, 7, 8} + for i := 0; i < b.N; i++ { + _ = m[k] + } +} + +func BenchmarkSmallKeyMap(b *testing.B) { + m := make(map[int16]bool) + m[5] = true + for i := 0; i < b.N; i++ { + _ = m[5] + } +} + +func BenchmarkMapPopulate(b *testing.B) { + for size := 1; size < 1000000; size *= 10 { + b.Run(strconv.Itoa(size), func(b *testing.B) { + b.ReportAllocs() + for i := 0; i < b.N; i++ { + m := make(map[int]bool) + for j := 0; j < size; j++ { + m[j] = true + } + } + }) + } +} + +type ComplexAlgKey struct { + a, b, c int64 + _ int + d int32 + _ int + e string + _ int + f, g, h int64 +} + +func BenchmarkComplexAlgMap(b *testing.B) { + m := make(map[ComplexAlgKey]bool) + var k ComplexAlgKey + m[k] = true + for i := 0; i < b.N; i++ { + _ = m[k] + } +} diff --git a/src/runtime/map_fast.go b/src/runtime/map_fast.go new file mode 100644 index 0000000000..f978d1be7b --- /dev/null +++ b/src/runtime/map_fast.go @@ -0,0 +1,1239 @@ +// Copyright 2014 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package runtime + +import ( + "runtime/internal/sys" + "unsafe" +) + +func mapaccess1_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer { + if raceenabled && h != nil { + callerpc := getcallerpc() + racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess1_fast32)) + } + if h == nil || h.count == 0 { + return unsafe.Pointer(&zeroVal[0]) + } + if h.flags&hashWriting != 0 { + throw("concurrent map read and map write") + } + var b *bmap + if h.B == 0 { + // One-bucket table. No need to hash. + b = (*bmap)(h.buckets) + } else { + hash := t.key.alg.hash(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 { + if !h.sameSizeGrow() { + // There used to be half as many buckets; mask down one more power of two. + m >>= 1 + } + oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) + if !evacuated(oldb) { + b = oldb + } + } + } + for ; b != nil; b = b.overflow(t) { + for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 4) { + if *(*uint32)(k) == key && b.tophash[i] != empty { + return add(unsafe.Pointer(b), dataOffset+bucketCnt*4+i*uintptr(t.valuesize)) + } + } + } + return unsafe.Pointer(&zeroVal[0]) +} + +func mapaccess2_fast32(t *maptype, h *hmap, key uint32) (unsafe.Pointer, bool) { + if raceenabled && h != nil { + callerpc := getcallerpc() + racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess2_fast32)) + } + if h == nil || h.count == 0 { + return unsafe.Pointer(&zeroVal[0]), false + } + if h.flags&hashWriting != 0 { + throw("concurrent map read and map write") + } + var b *bmap + if h.B == 0 { + // One-bucket table. No need to hash. + b = (*bmap)(h.buckets) + } else { + hash := t.key.alg.hash(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 { + if !h.sameSizeGrow() { + // There used to be half as many buckets; mask down one more power of two. + m >>= 1 + } + oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) + if !evacuated(oldb) { + b = oldb + } + } + } + for ; b != nil; b = b.overflow(t) { + for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 4) { + if *(*uint32)(k) == key && b.tophash[i] != empty { + return add(unsafe.Pointer(b), dataOffset+bucketCnt*4+i*uintptr(t.valuesize)), true + } + } + } + return unsafe.Pointer(&zeroVal[0]), false +} + +func mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer { + if raceenabled && h != nil { + callerpc := getcallerpc() + racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess1_fast64)) + } + if h == nil || h.count == 0 { + return unsafe.Pointer(&zeroVal[0]) + } + if h.flags&hashWriting != 0 { + throw("concurrent map read and map write") + } + var b *bmap + if h.B == 0 { + // One-bucket table. No need to hash. + b = (*bmap)(h.buckets) + } else { + hash := t.key.alg.hash(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 { + if !h.sameSizeGrow() { + // There used to be half as many buckets; mask down one more power of two. + m >>= 1 + } + oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) + if !evacuated(oldb) { + b = oldb + } + } + } + for ; b != nil; b = b.overflow(t) { + for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 8) { + if *(*uint64)(k) == key && b.tophash[i] != empty { + return add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.valuesize)) + } + } + } + return unsafe.Pointer(&zeroVal[0]) +} + +func mapaccess2_fast64(t *maptype, h *hmap, key uint64) (unsafe.Pointer, bool) { + if raceenabled && h != nil { + callerpc := getcallerpc() + racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess2_fast64)) + } + if h == nil || h.count == 0 { + return unsafe.Pointer(&zeroVal[0]), false + } + if h.flags&hashWriting != 0 { + throw("concurrent map read and map write") + } + var b *bmap + if h.B == 0 { + // One-bucket table. No need to hash. + b = (*bmap)(h.buckets) + } else { + hash := t.key.alg.hash(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 { + if !h.sameSizeGrow() { + // There used to be half as many buckets; mask down one more power of two. + m >>= 1 + } + oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) + if !evacuated(oldb) { + b = oldb + } + } + } + for ; b != nil; b = b.overflow(t) { + for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 8) { + if *(*uint64)(k) == key && b.tophash[i] != empty { + return add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.valuesize)), true + } + } + } + return unsafe.Pointer(&zeroVal[0]), false +} + +func mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer { + if raceenabled && h != nil { + callerpc := getcallerpc() + racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess1_faststr)) + } + if h == nil || h.count == 0 { + return unsafe.Pointer(&zeroVal[0]) + } + if h.flags&hashWriting != 0 { + throw("concurrent map read and map write") + } + key := stringStructOf(&ky) + if h.B == 0 { + // One-bucket table. + b := (*bmap)(h.buckets) + if key.len < 32 { + // short key, doing lots of comparisons is ok + for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) { + k := (*stringStruct)(kptr) + if k.len != key.len || b.tophash[i] == empty { + continue + } + if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { + return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize)) + } + } + return unsafe.Pointer(&zeroVal[0]) + } + // long key, try not to do more comparisons than necessary + keymaybe := uintptr(bucketCnt) + for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) { + k := (*stringStruct)(kptr) + if k.len != key.len || b.tophash[i] == empty { + continue + } + if k.str == key.str { + return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize)) + } + // check first 4 bytes + if *((*[4]byte)(key.str)) != *((*[4]byte)(k.str)) { + continue + } + // check last 4 bytes + if *((*[4]byte)(add(key.str, uintptr(key.len)-4))) != *((*[4]byte)(add(k.str, uintptr(key.len)-4))) { + continue + } + if keymaybe != bucketCnt { + // Two keys are potential matches. Use hash to distinguish them. + goto dohash + } + keymaybe = i + } + if keymaybe != bucketCnt { + k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+keymaybe*2*sys.PtrSize)) + if memequal(k.str, key.str, uintptr(key.len)) { + return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+keymaybe*uintptr(t.valuesize)) + } + } + return unsafe.Pointer(&zeroVal[0]) + } +dohash: + hash := t.key.alg.hash(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 { + if !h.sameSizeGrow() { + // There used to be half as many buckets; mask down one more power of two. + m >>= 1 + } + oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) + if !evacuated(oldb) { + b = oldb + } + } + top := tophash(hash) + for ; b != nil; b = b.overflow(t) { + for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) { + k := (*stringStruct)(kptr) + if k.len != key.len || b.tophash[i] != top { + continue + } + if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { + return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize)) + } + } + } + return unsafe.Pointer(&zeroVal[0]) +} + +func mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool) { + if raceenabled && h != nil { + callerpc := getcallerpc() + racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess2_faststr)) + } + if h == nil || h.count == 0 { + return unsafe.Pointer(&zeroVal[0]), false + } + if h.flags&hashWriting != 0 { + throw("concurrent map read and map write") + } + key := stringStructOf(&ky) + if h.B == 0 { + // One-bucket table. + b := (*bmap)(h.buckets) + if key.len < 32 { + // short key, doing lots of comparisons is ok + for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) { + k := (*stringStruct)(kptr) + if k.len != key.len || b.tophash[i] == empty { + continue + } + if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { + return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize)), true + } + } + return unsafe.Pointer(&zeroVal[0]), false + } + // long key, try not to do more comparisons than necessary + keymaybe := uintptr(bucketCnt) + for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) { + k := (*stringStruct)(kptr) + if k.len != key.len || b.tophash[i] == empty { + continue + } + if k.str == key.str { + return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize)), true + } + // check first 4 bytes + if *((*[4]byte)(key.str)) != *((*[4]byte)(k.str)) { + continue + } + // check last 4 bytes + if *((*[4]byte)(add(key.str, uintptr(key.len)-4))) != *((*[4]byte)(add(k.str, uintptr(key.len)-4))) { + continue + } + if keymaybe != bucketCnt { + // Two keys are potential matches. Use hash to distinguish them. + goto dohash + } + keymaybe = i + } + if keymaybe != bucketCnt { + k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+keymaybe*2*sys.PtrSize)) + if memequal(k.str, key.str, uintptr(key.len)) { + return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+keymaybe*uintptr(t.valuesize)), true + } + } + return unsafe.Pointer(&zeroVal[0]), false + } +dohash: + hash := t.key.alg.hash(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 { + if !h.sameSizeGrow() { + // There used to be half as many buckets; mask down one more power of two. + m >>= 1 + } + oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) + if !evacuated(oldb) { + b = oldb + } + } + top := tophash(hash) + for ; b != nil; b = b.overflow(t) { + for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) { + k := (*stringStruct)(kptr) + if k.len != key.len || b.tophash[i] != top { + continue + } + if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { + return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize)), true + } + } + } + return unsafe.Pointer(&zeroVal[0]), false +} + +func mapassign_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer { + if h == nil { + panic(plainError("assignment to entry in nil map")) + } + if raceenabled { + callerpc := getcallerpc() + racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapassign_fast32)) + } + if h.flags&hashWriting != 0 { + throw("concurrent map writes") + } + hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) + + // Set hashWriting after calling alg.hash for consistency with mapassign. + h.flags |= hashWriting + + if h.buckets == nil { + h.buckets = newobject(t.bucket) // newarray(t.bucket, 1) + } + +again: + bucket := hash & bucketMask(h.B) + if h.growing() { + growWork_fast32(t, h, bucket) + } + b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize))) + + var insertb *bmap + var inserti uintptr + var insertk unsafe.Pointer + + for { + for i := uintptr(0); i < bucketCnt; i++ { + if b.tophash[i] == empty { + if insertb == nil { + inserti = i + insertb = b + } + continue + } + k := *((*uint32)(add(unsafe.Pointer(b), dataOffset+i*4))) + if k != key { + continue + } + inserti = i + insertb = b + goto done + } + ovf := b.overflow(t) + if ovf == nil { + break + } + b = ovf + } + + // Did not find mapping for key. Allocate new cell & add entry. + + // If we hit the max load factor or we have too many overflow buckets, + // and we're not already in the middle of growing, start growing. + if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { + hashGrow(t, h) + goto again // Growing the table invalidates everything, so try again + } + + if insertb == nil { + // all current buckets are full, allocate a new one. + insertb = h.newoverflow(t, b) + inserti = 0 // not necessary, but avoids needlessly spilling inserti + } + insertb.tophash[inserti&(bucketCnt-1)] = tophash(hash) // mask inserti to avoid bounds checks + + insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*4) + // store new key at insert position + *(*uint32)(insertk) = key + + h.count++ + +done: + val := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*4+inserti*uintptr(t.valuesize)) + if h.flags&hashWriting == 0 { + throw("concurrent map writes") + } + h.flags &^= hashWriting + return val +} + +func mapassign_fast32ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { + if h == nil { + panic(plainError("assignment to entry in nil map")) + } + if raceenabled { + callerpc := getcallerpc() + racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapassign_fast32)) + } + if h.flags&hashWriting != 0 { + throw("concurrent map writes") + } + hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) + + // Set hashWriting after calling alg.hash for consistency with mapassign. + h.flags |= hashWriting + + if h.buckets == nil { + h.buckets = newobject(t.bucket) // newarray(t.bucket, 1) + } + +again: + bucket := hash & bucketMask(h.B) + if h.growing() { + growWork_fast32(t, h, bucket) + } + b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize))) + + var insertb *bmap + var inserti uintptr + var insertk unsafe.Pointer + + for { + for i := uintptr(0); i < bucketCnt; i++ { + if b.tophash[i] == empty { + if insertb == nil { + inserti = i + insertb = b + } + continue + } + k := *((*unsafe.Pointer)(add(unsafe.Pointer(b), dataOffset+i*4))) + if k != key { + continue + } + inserti = i + insertb = b + goto done + } + ovf := b.overflow(t) + if ovf == nil { + break + } + b = ovf + } + + // Did not find mapping for key. Allocate new cell & add entry. + + // If we hit the max load factor or we have too many overflow buckets, + // and we're not already in the middle of growing, start growing. + if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { + hashGrow(t, h) + goto again // Growing the table invalidates everything, so try again + } + + if insertb == nil { + // all current buckets are full, allocate a new one. + insertb = h.newoverflow(t, b) + inserti = 0 // not necessary, but avoids needlessly spilling inserti + } + insertb.tophash[inserti&(bucketCnt-1)] = tophash(hash) // mask inserti to avoid bounds checks + + insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*4) + // store new key at insert position + *(*unsafe.Pointer)(insertk) = key + + h.count++ + +done: + val := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*4+inserti*uintptr(t.valuesize)) + if h.flags&hashWriting == 0 { + throw("concurrent map writes") + } + h.flags &^= hashWriting + return val +} + +func mapassign_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer { + if h == nil { + panic(plainError("assignment to entry in nil map")) + } + if raceenabled { + callerpc := getcallerpc() + racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapassign_fast64)) + } + if h.flags&hashWriting != 0 { + throw("concurrent map writes") + } + hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) + + // Set hashWriting after calling alg.hash for consistency with mapassign. + h.flags |= hashWriting + + if h.buckets == nil { + h.buckets = newobject(t.bucket) // newarray(t.bucket, 1) + } + +again: + bucket := hash & bucketMask(h.B) + if h.growing() { + growWork_fast64(t, h, bucket) + } + b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize))) + + var insertb *bmap + var inserti uintptr + var insertk unsafe.Pointer + + for { + for i := uintptr(0); i < bucketCnt; i++ { + if b.tophash[i] == empty { + if insertb == nil { + insertb = b + inserti = i + } + continue + } + k := *((*uint64)(add(unsafe.Pointer(b), dataOffset+i*8))) + if k != key { + continue + } + insertb = b + inserti = i + goto done + } + ovf := b.overflow(t) + if ovf == nil { + break + } + b = ovf + } + + // Did not find mapping for key. Allocate new cell & add entry. + + // If we hit the max load factor or we have too many overflow buckets, + // and we're not already in the middle of growing, start growing. + if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { + hashGrow(t, h) + goto again // Growing the table invalidates everything, so try again + } + + if insertb == nil { + // all current buckets are full, allocate a new one. + insertb = h.newoverflow(t, b) + inserti = 0 // not necessary, but avoids needlessly spilling inserti + } + insertb.tophash[inserti&(bucketCnt-1)] = tophash(hash) // mask inserti to avoid bounds checks + + insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*8) + // store new key at insert position + *(*uint64)(insertk) = key + + h.count++ + +done: + val := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*8+inserti*uintptr(t.valuesize)) + if h.flags&hashWriting == 0 { + throw("concurrent map writes") + } + h.flags &^= hashWriting + return val +} + +func mapassign_fast64ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { + if h == nil { + panic(plainError("assignment to entry in nil map")) + } + if raceenabled { + callerpc := getcallerpc() + racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapassign_fast64)) + } + if h.flags&hashWriting != 0 { + throw("concurrent map writes") + } + hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) + + // Set hashWriting after calling alg.hash for consistency with mapassign. + h.flags |= hashWriting + + if h.buckets == nil { + h.buckets = newobject(t.bucket) // newarray(t.bucket, 1) + } + +again: + bucket := hash & bucketMask(h.B) + if h.growing() { + growWork_fast64(t, h, bucket) + } + b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize))) + + var insertb *bmap + var inserti uintptr + var insertk unsafe.Pointer + + for { + for i := uintptr(0); i < bucketCnt; i++ { + if b.tophash[i] == empty { + if insertb == nil { + insertb = b + inserti = i + } + continue + } + k := *((*unsafe.Pointer)(add(unsafe.Pointer(b), dataOffset+i*8))) + if k != key { + continue + } + insertb = b + inserti = i + goto done + } + ovf := b.overflow(t) + if ovf == nil { + break + } + b = ovf + } + + // Did not find mapping for key. Allocate new cell & add entry. + + // If we hit the max load factor or we have too many overflow buckets, + // and we're not already in the middle of growing, start growing. + if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { + hashGrow(t, h) + goto again // Growing the table invalidates everything, so try again + } + + if insertb == nil { + // all current buckets are full, allocate a new one. + insertb = h.newoverflow(t, b) + inserti = 0 // not necessary, but avoids needlessly spilling inserti + } + insertb.tophash[inserti&(bucketCnt-1)] = tophash(hash) // mask inserti to avoid bounds checks + + insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*8) + // store new key at insert position + *(*unsafe.Pointer)(insertk) = key + + h.count++ + +done: + val := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*8+inserti*uintptr(t.valuesize)) + if h.flags&hashWriting == 0 { + throw("concurrent map writes") + } + h.flags &^= hashWriting + return val +} + +func mapassign_faststr(t *maptype, h *hmap, s string) unsafe.Pointer { + if h == nil { + panic(plainError("assignment to entry in nil map")) + } + if raceenabled { + callerpc := getcallerpc() + racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapassign_faststr)) + } + if h.flags&hashWriting != 0 { + throw("concurrent map writes") + } + key := stringStructOf(&s) + hash := t.key.alg.hash(noescape(unsafe.Pointer(&s)), uintptr(h.hash0)) + + // Set hashWriting after calling alg.hash for consistency with mapassign. + h.flags |= hashWriting + + if h.buckets == nil { + h.buckets = newobject(t.bucket) // newarray(t.bucket, 1) + } + +again: + bucket := hash & bucketMask(h.B) + if h.growing() { + growWork_faststr(t, h, bucket) + } + b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize))) + top := tophash(hash) + + var insertb *bmap + var inserti uintptr + var insertk unsafe.Pointer + + for { + for i := uintptr(0); i < bucketCnt; i++ { + if b.tophash[i] != top { + if b.tophash[i] == empty && insertb == nil { + insertb = b + inserti = i + } + continue + } + k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+i*2*sys.PtrSize)) + if k.len != key.len { + continue + } + if k.str != key.str && !memequal(k.str, key.str, uintptr(key.len)) { + continue + } + // already have a mapping for key. Update it. + inserti = i + insertb = b + goto done + } + ovf := b.overflow(t) + if ovf == nil { + break + } + b = ovf + } + + // Did not find mapping for key. Allocate new cell & add entry. + + // If we hit the max load factor or we have too many overflow buckets, + // and we're not already in the middle of growing, start growing. + if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { + hashGrow(t, h) + goto again // Growing the table invalidates everything, so try again + } + + if insertb == nil { + // all current buckets are full, allocate a new one. + insertb = h.newoverflow(t, b) + inserti = 0 // not necessary, but avoids needlessly spilling inserti + } + insertb.tophash[inserti&(bucketCnt-1)] = top // mask inserti to avoid bounds checks + + insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*2*sys.PtrSize) + // store new key at insert position + *((*stringStruct)(insertk)) = *key + h.count++ + +done: + val := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*2*sys.PtrSize+inserti*uintptr(t.valuesize)) + if h.flags&hashWriting == 0 { + throw("concurrent map writes") + } + h.flags &^= hashWriting + return val +} + +func mapdelete_fast32(t *maptype, h *hmap, key uint32) { + if raceenabled && h != nil { + callerpc := getcallerpc() + racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapdelete_fast32)) + } + if h == nil || h.count == 0 { + return + } + if h.flags&hashWriting != 0 { + throw("concurrent map writes") + } + + hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) + + // Set hashWriting after calling alg.hash for consistency with mapdelete + h.flags |= hashWriting + + bucket := hash & bucketMask(h.B) + if h.growing() { + growWork_fast32(t, h, bucket) + } + b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) +search: + for ; b != nil; b = b.overflow(t) { + for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 4) { + if key != *(*uint32)(k) || b.tophash[i] == empty { + continue + } + // Only clear key if there are pointers in it. + if t.key.kind&kindNoPointers == 0 { + memclrHasPointers(k, t.key.size) + } + // Only clear value if there are pointers in it. + if t.elem.kind&kindNoPointers == 0 { + v := add(unsafe.Pointer(b), dataOffset+bucketCnt*4+i*uintptr(t.valuesize)) + memclrHasPointers(v, t.elem.size) + } + b.tophash[i] = empty + h.count-- + break search + } + } + + if h.flags&hashWriting == 0 { + throw("concurrent map writes") + } + h.flags &^= hashWriting +} + +func mapdelete_fast64(t *maptype, h *hmap, key uint64) { + if raceenabled && h != nil { + callerpc := getcallerpc() + racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapdelete_fast64)) + } + if h == nil || h.count == 0 { + return + } + if h.flags&hashWriting != 0 { + throw("concurrent map writes") + } + + hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0)) + + // Set hashWriting after calling alg.hash for consistency with mapdelete + h.flags |= hashWriting + + bucket := hash & bucketMask(h.B) + if h.growing() { + growWork_fast64(t, h, bucket) + } + b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) +search: + for ; b != nil; b = b.overflow(t) { + for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 8) { + if key != *(*uint64)(k) || b.tophash[i] == empty { + continue + } + // Only clear key if there are pointers in it. + if t.key.kind&kindNoPointers == 0 { + memclrHasPointers(k, t.key.size) + } + // Only clear value if there are pointers in it. + if t.elem.kind&kindNoPointers == 0 { + v := add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.valuesize)) + memclrHasPointers(v, t.elem.size) + } + b.tophash[i] = empty + h.count-- + break search + } + } + + if h.flags&hashWriting == 0 { + throw("concurrent map writes") + } + h.flags &^= hashWriting +} + +func mapdelete_faststr(t *maptype, h *hmap, ky string) { + if raceenabled && h != nil { + callerpc := getcallerpc() + racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapdelete_faststr)) + } + if h == nil || h.count == 0 { + return + } + if h.flags&hashWriting != 0 { + throw("concurrent map writes") + } + + key := stringStructOf(&ky) + hash := t.key.alg.hash(noescape(unsafe.Pointer(&ky)), uintptr(h.hash0)) + + // Set hashWriting after calling alg.hash for consistency with mapdelete + h.flags |= hashWriting + + bucket := hash & bucketMask(h.B) + if h.growing() { + growWork_faststr(t, h, bucket) + } + b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) + top := tophash(hash) +search: + for ; b != nil; b = b.overflow(t) { + for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) { + k := (*stringStruct)(kptr) + if k.len != key.len || b.tophash[i] != top { + continue + } + if k.str != key.str && !memequal(k.str, key.str, uintptr(key.len)) { + continue + } + // Clear key's pointer. + k.str = nil + // Only clear value if there are pointers in it. + if t.elem.kind&kindNoPointers == 0 { + v := add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize)) + memclrHasPointers(v, t.elem.size) + } + b.tophash[i] = empty + h.count-- + break search + } + } + + if h.flags&hashWriting == 0 { + throw("concurrent map writes") + } + h.flags &^= hashWriting +} + +func growWork_fast32(t *maptype, h *hmap, bucket uintptr) { + // make sure we evacuate the oldbucket corresponding + // to the bucket we're about to use + evacuate_fast32(t, h, bucket&h.oldbucketmask()) + + // evacuate one more oldbucket to make progress on growing + if h.growing() { + evacuate_fast32(t, h, h.nevacuate) + } +} + +func evacuate_fast32(t *maptype, h *hmap, oldbucket uintptr) { + b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) + newbit := h.noldbuckets() + if !evacuated(b) { + // TODO: reuse overflow buckets instead of using new ones, if there + // is no iterator using the old buckets. (If !oldIterator.) + + // xy contains the x and y (low and high) evacuation destinations. + var xy [2]evacDst + x := &xy[0] + x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize))) + x.k = add(unsafe.Pointer(x.b), dataOffset) + x.v = add(x.k, bucketCnt*4) + + if !h.sameSizeGrow() { + // Only calculate y pointers if we're growing bigger. + // Otherwise GC can see bad pointers. + y := &xy[1] + y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize))) + y.k = add(unsafe.Pointer(y.b), dataOffset) + y.v = add(y.k, bucketCnt*4) + } + + for ; b != nil; b = b.overflow(t) { + k := add(unsafe.Pointer(b), dataOffset) + v := add(k, bucketCnt*4) + for i := 0; i < bucketCnt; i, k, v = i+1, add(k, 4), add(v, uintptr(t.valuesize)) { + top := b.tophash[i] + if top == empty { + b.tophash[i] = evacuatedEmpty + continue + } + if top < minTopHash { + throw("bad map state") + } + var useY uint8 + if !h.sameSizeGrow() { + // Compute hash to make our evacuation decision (whether we need + // to send this key/value to bucket x or bucket y). + hash := t.key.alg.hash(k, uintptr(h.hash0)) + if hash&newbit != 0 { + useY = 1 + } + } + + b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap + dst := &xy[useY] // evacuation destination + + if dst.i == bucketCnt { + dst.b = h.newoverflow(t, dst.b) + dst.i = 0 + dst.k = add(unsafe.Pointer(dst.b), dataOffset) + dst.v = add(dst.k, bucketCnt*4) + } + dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check + + // Copy key. + if sys.PtrSize == 4 && t.key.kind&kindNoPointers == 0 && writeBarrier.enabled { + // Write with a write barrier. + *(*unsafe.Pointer)(dst.k) = *(*unsafe.Pointer)(k) + } else { + *(*uint32)(dst.k) = *(*uint32)(k) + } + + typedmemmove(t.elem, dst.v, v) + dst.i++ + // These updates might push these pointers past the end of the + // key or value arrays. That's ok, as we have the overflow pointer + // at the end of the bucket to protect against pointing past the + // end of the bucket. + dst.k = add(dst.k, 4) + dst.v = add(dst.v, uintptr(t.valuesize)) + } + } + // Unlink the overflow buckets & clear key/value to help GC. + if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 { + b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)) + // Preserve b.tophash because the evacuation + // state is maintained there. + ptr := add(b, dataOffset) + n := uintptr(t.bucketsize) - dataOffset + memclrHasPointers(ptr, n) + } + } + + if oldbucket == h.nevacuate { + advanceEvacuationMark(h, t, newbit) + } +} + +func growWork_fast64(t *maptype, h *hmap, bucket uintptr) { + // make sure we evacuate the oldbucket corresponding + // to the bucket we're about to use + evacuate_fast64(t, h, bucket&h.oldbucketmask()) + + // evacuate one more oldbucket to make progress on growing + if h.growing() { + evacuate_fast64(t, h, h.nevacuate) + } +} + +func evacuate_fast64(t *maptype, h *hmap, oldbucket uintptr) { + b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) + newbit := h.noldbuckets() + if !evacuated(b) { + // TODO: reuse overflow buckets instead of using new ones, if there + // is no iterator using the old buckets. (If !oldIterator.) + + // xy contains the x and y (low and high) evacuation destinations. + var xy [2]evacDst + x := &xy[0] + x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize))) + x.k = add(unsafe.Pointer(x.b), dataOffset) + x.v = add(x.k, bucketCnt*8) + + if !h.sameSizeGrow() { + // Only calculate y pointers if we're growing bigger. + // Otherwise GC can see bad pointers. + y := &xy[1] + y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize))) + y.k = add(unsafe.Pointer(y.b), dataOffset) + y.v = add(y.k, bucketCnt*8) + } + + for ; b != nil; b = b.overflow(t) { + k := add(unsafe.Pointer(b), dataOffset) + v := add(k, bucketCnt*8) + for i := 0; i < bucketCnt; i, k, v = i+1, add(k, 8), add(v, uintptr(t.valuesize)) { + top := b.tophash[i] + if top == empty { + b.tophash[i] = evacuatedEmpty + continue + } + if top < minTopHash { + throw("bad map state") + } + var useY uint8 + if !h.sameSizeGrow() { + // Compute hash to make our evacuation decision (whether we need + // to send this key/value to bucket x or bucket y). + hash := t.key.alg.hash(k, uintptr(h.hash0)) + if hash&newbit != 0 { + useY = 1 + } + } + + b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap + dst := &xy[useY] // evacuation destination + + if dst.i == bucketCnt { + dst.b = h.newoverflow(t, dst.b) + dst.i = 0 + dst.k = add(unsafe.Pointer(dst.b), dataOffset) + dst.v = add(dst.k, bucketCnt*8) + } + dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check + + // Copy key. + if t.key.kind&kindNoPointers == 0 && writeBarrier.enabled { + if sys.PtrSize == 8 { + // Write with a write barrier. + *(*unsafe.Pointer)(dst.k) = *(*unsafe.Pointer)(k) + } else { + // There are three ways to squeeze at least one 32 bit pointer into 64 bits. + // Give up and call typedmemmove. + typedmemmove(t.key, dst.k, k) + } + } else { + *(*uint64)(dst.k) = *(*uint64)(k) + } + + typedmemmove(t.elem, dst.v, v) + dst.i++ + // These updates might push these pointers past the end of the + // key or value arrays. That's ok, as we have the overflow pointer + // at the end of the bucket to protect against pointing past the + // end of the bucket. + dst.k = add(dst.k, 8) + dst.v = add(dst.v, uintptr(t.valuesize)) + } + } + // Unlink the overflow buckets & clear key/value to help GC. + if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 { + b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)) + // Preserve b.tophash because the evacuation + // state is maintained there. + ptr := add(b, dataOffset) + n := uintptr(t.bucketsize) - dataOffset + memclrHasPointers(ptr, n) + } + } + + if oldbucket == h.nevacuate { + advanceEvacuationMark(h, t, newbit) + } +} + +func growWork_faststr(t *maptype, h *hmap, bucket uintptr) { + // make sure we evacuate the oldbucket corresponding + // to the bucket we're about to use + evacuate_faststr(t, h, bucket&h.oldbucketmask()) + + // evacuate one more oldbucket to make progress on growing + if h.growing() { + evacuate_faststr(t, h, h.nevacuate) + } +} + +func evacuate_faststr(t *maptype, h *hmap, oldbucket uintptr) { + b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) + newbit := h.noldbuckets() + if !evacuated(b) { + // TODO: reuse overflow buckets instead of using new ones, if there + // is no iterator using the old buckets. (If !oldIterator.) + + // xy contains the x and y (low and high) evacuation destinations. + var xy [2]evacDst + x := &xy[0] + x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize))) + x.k = add(unsafe.Pointer(x.b), dataOffset) + x.v = add(x.k, bucketCnt*2*sys.PtrSize) + + if !h.sameSizeGrow() { + // Only calculate y pointers if we're growing bigger. + // Otherwise GC can see bad pointers. + y := &xy[1] + y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize))) + y.k = add(unsafe.Pointer(y.b), dataOffset) + y.v = add(y.k, bucketCnt*2*sys.PtrSize) + } + + for ; b != nil; b = b.overflow(t) { + k := add(unsafe.Pointer(b), dataOffset) + v := add(k, bucketCnt*2*sys.PtrSize) + for i := 0; i < bucketCnt; i, k, v = i+1, add(k, 2*sys.PtrSize), add(v, uintptr(t.valuesize)) { + top := b.tophash[i] + if top == empty { + b.tophash[i] = evacuatedEmpty + continue + } + if top < minTopHash { + throw("bad map state") + } + var useY uint8 + if !h.sameSizeGrow() { + // Compute hash to make our evacuation decision (whether we need + // to send this key/value to bucket x or bucket y). + hash := t.key.alg.hash(k, uintptr(h.hash0)) + if hash&newbit != 0 { + useY = 1 + } + } + + b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap + dst := &xy[useY] // evacuation destination + + if dst.i == bucketCnt { + dst.b = h.newoverflow(t, dst.b) + dst.i = 0 + dst.k = add(unsafe.Pointer(dst.b), dataOffset) + dst.v = add(dst.k, bucketCnt*2*sys.PtrSize) + } + dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check + + // Copy key. + *(*string)(dst.k) = *(*string)(k) + + typedmemmove(t.elem, dst.v, v) + dst.i++ + // These updates might push these pointers past the end of the + // key or value arrays. That's ok, as we have the overflow pointer + // at the end of the bucket to protect against pointing past the + // end of the bucket. + dst.k = add(dst.k, 2*sys.PtrSize) + dst.v = add(dst.v, uintptr(t.valuesize)) + } + } + // Unlink the overflow buckets & clear key/value to help GC. + // Unlink the overflow buckets & clear key/value to help GC. + if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 { + b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)) + // Preserve b.tophash because the evacuation + // state is maintained there. + ptr := add(b, dataOffset) + n := uintptr(t.bucketsize) - dataOffset + memclrHasPointers(ptr, n) + } + } + + if oldbucket == h.nevacuate { + advanceEvacuationMark(h, t, newbit) + } +} diff --git a/src/runtime/map_test.go b/src/runtime/map_test.go index 6ed655de0a..b12b09eeb6 100644 --- a/src/runtime/map_test.go +++ b/src/runtime/map_test.go @@ -620,7 +620,7 @@ func TestMapBuckets(t *testing.T) { // have a nil bucket pointer due to starting with preallocated buckets // on the stack. Escaping maps start with a non-nil bucket pointer if // hint size is above bucketCnt and thereby have more than one bucket. - // These tests depend on bucketCnt and loadFactor* in hashmap.go. + // These tests depend on bucketCnt and loadFactor* in map.go. t.Run("mapliteral", func(t *testing.T) { for _, tt := range mapBucketTests { localMap := map[int]int{} diff --git a/src/runtime/mapspeed_test.go b/src/runtime/mapspeed_test.go deleted file mode 100644 index aec0c51f3f..0000000000 --- a/src/runtime/mapspeed_test.go +++ /dev/null @@ -1,343 +0,0 @@ -// Copyright 2013 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. -package runtime_test - -import ( - "fmt" - "strconv" - "strings" - "testing" -) - -const size = 10 - -func BenchmarkHashStringSpeed(b *testing.B) { - strings := make([]string, size) - for i := 0; i < size; i++ { - strings[i] = fmt.Sprintf("string#%d", i) - } - sum := 0 - m := make(map[string]int, size) - for i := 0; i < size; i++ { - m[strings[i]] = 0 - } - idx := 0 - b.ResetTimer() - for i := 0; i < b.N; i++ { - sum += m[strings[idx]] - idx++ - if idx == size { - idx = 0 - } - } -} - -type chunk [17]byte - -func BenchmarkHashBytesSpeed(b *testing.B) { - // a bunch of chunks, each with a different alignment mod 16 - var chunks [size]chunk - // initialize each to a different value - for i := 0; i < size; i++ { - chunks[i][0] = byte(i) - } - // put into a map - m := make(map[chunk]int, size) - for i, c := range chunks { - m[c] = i - } - idx := 0 - b.ResetTimer() - for i := 0; i < b.N; i++ { - if m[chunks[idx]] != idx { - b.Error("bad map entry for chunk") - } - 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 - } - } -} -func BenchmarkHashStringArraySpeed(b *testing.B) { - stringpairs := make([][2]string, size) - for i := 0; i < size; i++ { - for j := 0; j < 2; j++ { - stringpairs[i][j] = fmt.Sprintf("string#%d/%d", i, j) - } - } - sum := 0 - m := make(map[[2]string]int, size) - for i := 0; i < size; i++ { - m[stringpairs[i]] = 0 - } - idx := 0 - b.ResetTimer() - for i := 0; i < b.N; i++ { - sum += m[stringpairs[idx]] - idx++ - if idx == size { - idx = 0 - } - } -} - -func BenchmarkMegMap(b *testing.B) { - m := make(map[string]bool) - for suffix := 'A'; suffix <= 'G'; suffix++ { - m[strings.Repeat("X", 1<<20-1)+fmt.Sprint(suffix)] = true - } - key := strings.Repeat("X", 1<<20-1) + "k" - b.ResetTimer() - for i := 0; i < b.N; i++ { - _, _ = m[key] - } -} - -func BenchmarkMegOneMap(b *testing.B) { - m := make(map[string]bool) - m[strings.Repeat("X", 1<<20)] = true - key := strings.Repeat("Y", 1<<20) - b.ResetTimer() - for i := 0; i < b.N; i++ { - _, _ = m[key] - } -} - -func BenchmarkMegEqMap(b *testing.B) { - m := make(map[string]bool) - key1 := strings.Repeat("X", 1<<20) - key2 := strings.Repeat("X", 1<<20) // equal but different instance - m[key1] = true - b.ResetTimer() - for i := 0; i < b.N; i++ { - _, _ = m[key2] - } -} - -func BenchmarkMegEmptyMap(b *testing.B) { - m := make(map[string]bool) - key := strings.Repeat("X", 1<<20) - b.ResetTimer() - for i := 0; i < b.N; i++ { - _, _ = m[key] - } -} - -func BenchmarkSmallStrMap(b *testing.B) { - m := make(map[string]bool) - for suffix := 'A'; suffix <= 'G'; suffix++ { - m[fmt.Sprint(suffix)] = true - } - key := "k" - b.ResetTimer() - for i := 0; i < b.N; i++ { - _, _ = m[key] - } -} - -func BenchmarkMapStringKeysEight_16(b *testing.B) { benchmarkMapStringKeysEight(b, 16) } -func BenchmarkMapStringKeysEight_32(b *testing.B) { benchmarkMapStringKeysEight(b, 32) } -func BenchmarkMapStringKeysEight_64(b *testing.B) { benchmarkMapStringKeysEight(b, 64) } -func BenchmarkMapStringKeysEight_1M(b *testing.B) { benchmarkMapStringKeysEight(b, 1<<20) } - -func benchmarkMapStringKeysEight(b *testing.B, keySize int) { - m := make(map[string]bool) - for i := 0; i < 8; i++ { - m[strings.Repeat("K", i+1)] = true - } - key := strings.Repeat("K", keySize) - b.ResetTimer() - for i := 0; i < b.N; i++ { - _ = m[key] - } -} - -func BenchmarkIntMap(b *testing.B) { - m := make(map[int]bool) - for i := 0; i < 8; i++ { - m[i] = true - } - b.ResetTimer() - for i := 0; i < b.N; i++ { - _, _ = m[7] - } -} - -// Accessing the same keys in a row. -func benchmarkRepeatedLookup(b *testing.B, lookupKeySize int) { - m := make(map[string]bool) - // At least bigger than a single bucket: - for i := 0; i < 64; i++ { - m[fmt.Sprintf("some key %d", i)] = true - } - base := strings.Repeat("x", lookupKeySize-1) - key1 := base + "1" - key2 := base + "2" - b.ResetTimer() - for i := 0; i < b.N/4; i++ { - _ = m[key1] - _ = m[key1] - _ = m[key2] - _ = m[key2] - } -} - -func BenchmarkRepeatedLookupStrMapKey32(b *testing.B) { benchmarkRepeatedLookup(b, 32) } -func BenchmarkRepeatedLookupStrMapKey1M(b *testing.B) { benchmarkRepeatedLookup(b, 1<<20) } - -func BenchmarkNewEmptyMap(b *testing.B) { - b.ReportAllocs() - for i := 0; i < b.N; i++ { - _ = make(map[int]int) - } -} - -func BenchmarkNewSmallMap(b *testing.B) { - b.ReportAllocs() - for i := 0; i < b.N; i++ { - m := make(map[int]int) - m[0] = 0 - m[1] = 1 - } -} - -func BenchmarkMapIter(b *testing.B) { - m := make(map[int]bool) - for i := 0; i < 8; i++ { - m[i] = true - } - b.ResetTimer() - for i := 0; i < b.N; i++ { - for range m { - } - } -} - -func BenchmarkMapIterEmpty(b *testing.B) { - m := make(map[int]bool) - b.ResetTimer() - for i := 0; i < b.N; i++ { - for range m { - } - } -} - -func BenchmarkSameLengthMap(b *testing.B) { - // long strings, same length, differ in first few - // and last few bytes. - m := make(map[string]bool) - s1 := "foo" + strings.Repeat("-", 100) + "bar" - s2 := "goo" + strings.Repeat("-", 100) + "ber" - m[s1] = true - m[s2] = true - b.ResetTimer() - for i := 0; i < b.N; i++ { - _ = m[s1] - } -} - -type BigKey [3]int64 - -func BenchmarkBigKeyMap(b *testing.B) { - m := make(map[BigKey]bool) - k := BigKey{3, 4, 5} - m[k] = true - for i := 0; i < b.N; i++ { - _ = m[k] - } -} - -type BigVal [3]int64 - -func BenchmarkBigValMap(b *testing.B) { - m := make(map[BigKey]BigVal) - k := BigKey{3, 4, 5} - m[k] = BigVal{6, 7, 8} - for i := 0; i < b.N; i++ { - _ = m[k] - } -} - -func BenchmarkSmallKeyMap(b *testing.B) { - m := make(map[int16]bool) - m[5] = true - for i := 0; i < b.N; i++ { - _ = m[5] - } -} - -func BenchmarkMapPopulate(b *testing.B) { - for size := 1; size < 1000000; size *= 10 { - b.Run(strconv.Itoa(size), func(b *testing.B) { - b.ReportAllocs() - for i := 0; i < b.N; i++ { - m := make(map[int]bool) - for j := 0; j < size; j++ { - m[j] = true - } - } - }) - } -} - -type ComplexAlgKey struct { - a, b, c int64 - _ int - d int32 - _ int - e string - _ int - f, g, h int64 -} - -func BenchmarkComplexAlgMap(b *testing.B) { - m := make(map[ComplexAlgKey]bool) - var k ComplexAlgKey - m[k] = true - for i := 0; i < b.N; i++ { - _ = m[k] - } -} -- cgit v1.3