diff options
Diffstat (limited to 'src/runtime')
| -rw-r--r-- | src/runtime/map.go | 122 | ||||
| -rw-r--r-- | src/runtime/map_benchmark_test.go | 29 |
2 files changed, 123 insertions, 28 deletions
diff --git a/src/runtime/map.go b/src/runtime/map.go index 1926123458..cc1358a977 100644 --- a/src/runtime/map.go +++ b/src/runtime/map.go @@ -318,7 +318,7 @@ func makemap(t *maptype, hint int, h *hmap) *hmap { // 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) + h.buckets, nextOverflow = makeBucketArray(t, h.B, nil) if nextOverflow != nil { h.extra = new(mapextra) h.extra.nextOverflow = nextOverflow @@ -328,6 +328,57 @@ func makemap(t *maptype, hint int, h *hmap) *hmap { return h } +// makeBucketArray initializes a backing array for map buckets. +// 1<<b is the minimum number of buckets to allocate. +// dirtyalloc should either be nil or a bucket array previously +// allocated by makeBucketArray with the same t and b parameters. +// If dirtyalloc is nil a new backing array will be alloced and +// otherwise dirtyalloc will be cleared and reused as backing array. +func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (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 + } + } + + if dirtyalloc == nil { + buckets = newarray(t.bucket, int(nbuckets)) + } else { + // dirtyalloc was previously generated by + // the above newarray(t.bucket, int(nbuckets)) + // but may not be empty. + buckets = dirtyalloc + size := t.bucket.size * nbuckets + if t.bucket.kind&kindNoPointers == 0 { + memclrHasPointers(buckets, size) + } else { + memclrNoHeapPointers(buckets, size) + } + } + + 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 +} + // 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. @@ -855,34 +906,49 @@ next: 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 - } +// mapclear deletes all keys from a map. +func mapclear(t *maptype, h *hmap) { + if raceenabled && h != nil { + callerpc := getcallerpc() + pc := funcPC(mapclear) + racewritepc(unsafe.Pointer(h), callerpc, pc) } - 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)) + + if h == nil || h.count == 0 { + return } - return buckets, nextOverflow + + if h.flags&hashWriting != 0 { + throw("concurrent map writes") + } + + h.flags |= hashWriting + + h.flags &^= sameSizeGrow + h.oldbuckets = nil + h.nevacuate = 0 + h.noverflow = 0 + h.count = 0 + + // Keep the mapextra allocation but clear any extra information. + if h.extra != nil { + *h.extra = mapextra{} + } + + // makeBucketArray clears the memory pointed to by h.buckets + // and recovers any overflow buckets by generating them + // as if h.buckets was newly alloced. + _, nextOverflow := makeBucketArray(t, h.B, h.buckets) + if nextOverflow != nil { + // If overflow buckets are created then h.extra + // will have been allocated during initial bucket creation. + h.extra.nextOverflow = nextOverflow + } + + if h.flags&hashWriting == 0 { + throw("concurrent map writes") + } + h.flags &^= hashWriting } func hashGrow(t *maptype, h *hmap) { @@ -895,7 +961,7 @@ func hashGrow(t *maptype, h *hmap) { h.flags |= sameSizeGrow } oldbuckets := h.buckets - newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger) + newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil) flags := h.flags &^ (iterator | oldIterator) if h.flags&iterator != 0 { diff --git a/src/runtime/map_benchmark_test.go b/src/runtime/map_benchmark_test.go index aec0c51f3f..025c0398d3 100644 --- a/src/runtime/map_benchmark_test.go +++ b/src/runtime/map_benchmark_test.go @@ -341,3 +341,32 @@ func BenchmarkComplexAlgMap(b *testing.B) { _ = m[k] } } + +func BenchmarkGoMapClear(b *testing.B) { + b.Run("Reflexive", func(b *testing.B) { + for size := 1; size < 100000; size *= 10 { + b.Run(strconv.Itoa(size), func(b *testing.B) { + m := make(map[int]int, size) + for i := 0; i < b.N; i++ { + m[0] = size // Add one element so len(m) != 0 avoiding fast paths. + for k := range m { + delete(m, k) + } + } + }) + } + }) + b.Run("NonReflexive", func(b *testing.B) { + for size := 1; size < 100000; size *= 10 { + b.Run(strconv.Itoa(size), func(b *testing.B) { + m := make(map[float64]int, size) + for i := 0; i < b.N; i++ { + m[1.0] = size // Add one element so len(m) != 0 avoiding fast paths. + for k := range m { + delete(m, k) + } + } + }) + } + }) +} |