aboutsummaryrefslogtreecommitdiff
path: root/src/runtime
diff options
context:
space:
mode:
Diffstat (limited to 'src/runtime')
-rw-r--r--src/runtime/hashmap_fast.go169
-rw-r--r--src/runtime/map_test.go76
2 files changed, 232 insertions, 13 deletions
diff --git a/src/runtime/hashmap_fast.go b/src/runtime/hashmap_fast.go
index f1a5bf3fc3..0a625cca56 100644
--- a/src/runtime/hashmap_fast.go
+++ b/src/runtime/hashmap_fast.go
@@ -692,3 +692,172 @@ done:
h.flags &^= hashWriting
return val
}
+
+func mapdelete_fast32(t *maptype, h *hmap, key uint32) {
+ if raceenabled && h != nil {
+ callerpc := getcallerpc(unsafe.Pointer(&t))
+ 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 & (uintptr(1)<<h.B - 1)
+ if h.growing() {
+ growWork(t, h, bucket)
+ }
+ b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
+ top := uint8(hash >> (sys.PtrSize*8 - 8))
+ if top < minTopHash {
+ top += minTopHash
+ }
+ for {
+ for i := uintptr(0); i < bucketCnt; i++ {
+ if b.tophash[i] != top {
+ continue
+ }
+ k := (*uint32)(add(unsafe.Pointer(b), dataOffset+i*4))
+ if key != *k {
+ continue
+ }
+ *k = 0
+ v := unsafe.Pointer(uintptr(unsafe.Pointer(b)) + dataOffset + bucketCnt*4 + i*uintptr(t.valuesize))
+ typedmemclr(t.elem, v)
+ b.tophash[i] = empty
+ h.count--
+ goto done
+ }
+ b = b.overflow(t)
+ if b == nil {
+ goto done
+ }
+ }
+
+done:
+ 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(unsafe.Pointer(&t))
+ 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 & (uintptr(1)<<h.B - 1)
+ if h.growing() {
+ growWork(t, h, bucket)
+ }
+ b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
+ top := uint8(hash >> (sys.PtrSize*8 - 8))
+ if top < minTopHash {
+ top += minTopHash
+ }
+ for {
+ for i := uintptr(0); i < bucketCnt; i++ {
+ if b.tophash[i] != top {
+ continue
+ }
+ k := (*uint64)(add(unsafe.Pointer(b), dataOffset+i*8))
+ if key != *k {
+ continue
+ }
+ *k = 0
+ v := unsafe.Pointer(uintptr(unsafe.Pointer(b)) + dataOffset + bucketCnt*8 + i*uintptr(t.valuesize))
+ typedmemclr(t.elem, v)
+ b.tophash[i] = empty
+ h.count--
+ goto done
+ }
+ b = b.overflow(t)
+ if b == nil {
+ goto done
+ }
+ }
+
+done:
+ 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(unsafe.Pointer(&t))
+ 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 & (uintptr(1)<<h.B - 1)
+ if h.growing() {
+ growWork(t, h, bucket)
+ }
+ b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
+ top := uint8(hash >> (sys.PtrSize*8 - 8))
+ if top < minTopHash {
+ top += minTopHash
+ }
+ for {
+ for i := uintptr(0); i < bucketCnt; i++ {
+ if b.tophash[i] != top {
+ 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
+ }
+ typedmemclr(t.key, unsafe.Pointer(k))
+ v := unsafe.Pointer(uintptr(unsafe.Pointer(b)) + dataOffset + bucketCnt*2*sys.PtrSize + i*uintptr(t.valuesize))
+ typedmemclr(t.elem, v)
+ b.tophash[i] = empty
+ h.count--
+ goto done
+ }
+ b = b.overflow(t)
+ if b == nil {
+ goto done
+ }
+ }
+
+done:
+ if h.flags&hashWriting == 0 {
+ throw("concurrent map writes")
+ }
+ h.flags &^= hashWriting
+}
diff --git a/src/runtime/map_test.go b/src/runtime/map_test.go
index 8ec67d5ab0..45d14126c2 100644
--- a/src/runtime/map_test.go
+++ b/src/runtime/map_test.go
@@ -619,35 +619,85 @@ func TestNonEscapingMap(t *testing.T) {
}
}
-func benchmarkMapAssignInt32(b *testing.B, pow uint) {
+func benchmarkMapAssignInt32(b *testing.B, n int) {
a := make(map[int32]int)
for i := 0; i < b.N; i++ {
- a[int32(i&((1<<pow)-1))] = i
+ a[int32(i&(n-1))] = i
}
}
-func BenchmarkMapAssignInt32_255(b *testing.B) { benchmarkMapAssignInt32(b, 8) }
-func BenchmarkMapAssignInt32_64k(b *testing.B) { benchmarkMapAssignInt32(b, 16) }
-func benchmarkMapAssignInt64(b *testing.B, pow uint) {
+func benchmarkMapDeleteInt32(b *testing.B, n int) {
+ a := make(map[int32]int)
+ for i := 0; i < n*b.N; i++ {
+ a[int32(i)] = i
+ }
+ b.ResetTimer()
+ for i := 0; i < n*b.N; i = i + n {
+ delete(a, int32(i))
+ }
+}
+
+func benchmarkMapAssignInt64(b *testing.B, n int) {
a := make(map[int64]int)
for i := 0; i < b.N; i++ {
- a[int64(i&((1<<pow)-1))] = i
+ a[int64(i&(n-1))] = i
+ }
+}
+
+func benchmarkMapDeleteInt64(b *testing.B, n int) {
+ a := make(map[int64]int)
+ for i := 0; i < n*b.N; i++ {
+ a[int64(i)] = i
+ }
+ b.ResetTimer()
+ for i := 0; i < n*b.N; i = i + n {
+ delete(a, int64(i))
}
}
-func BenchmarkMapAssignInt64_255(b *testing.B) { benchmarkMapAssignInt64(b, 8) }
-func BenchmarkMapAssignInt64_64k(b *testing.B) { benchmarkMapAssignInt64(b, 16) }
-func benchmarkMapAssignStr(b *testing.B, pow uint) {
- k := make([]string, (1 << pow))
+func benchmarkMapAssignStr(b *testing.B, n int) {
+ k := make([]string, n)
for i := 0; i < len(k); i++ {
k[i] = strconv.Itoa(i)
}
b.ResetTimer()
a := make(map[string]int)
for i := 0; i < b.N; i++ {
- a[k[i&((1<<pow)-1)]] = i
+ a[k[i&(n-1)]] = i
}
}
-func BenchmarkMapAssignStr_255(b *testing.B) { benchmarkMapAssignStr(b, 8) }
-func BenchmarkMapAssignStr_64k(b *testing.B) { benchmarkMapAssignStr(b, 16) }
+func benchmarkMapDeleteStr(b *testing.B, n int) {
+ k := make([]string, n*b.N)
+ for i := 0; i < n*b.N; i++ {
+ k[i] = strconv.Itoa(i)
+ }
+ a := make(map[string]int)
+ for i := 0; i < n*b.N; i++ {
+ a[k[i]] = i
+ }
+ b.ResetTimer()
+ for i := 0; i < n*b.N; i = i + n {
+ delete(a, k[i])
+ }
+}
+
+func runWith(f func(*testing.B, int), v ...int) func(*testing.B) {
+ return func(b *testing.B) {
+ for _, n := range v {
+ b.Run(strconv.Itoa(n), func(b *testing.B) { f(b, n) })
+ }
+ }
+}
+
+func BenchmarkMapAssign(b *testing.B) {
+ b.Run("Int32", runWith(benchmarkMapAssignInt32, 1<<8, 1<<16))
+ b.Run("Int64", runWith(benchmarkMapAssignInt64, 1<<8, 1<<16))
+ b.Run("Str", runWith(benchmarkMapAssignStr, 1<<8, 1<<16))
+}
+
+func BenchmarkMapDelete(b *testing.B) {
+ b.Run("Int32", runWith(benchmarkMapDeleteInt32, 1, 2, 4))
+ b.Run("Int64", runWith(benchmarkMapDeleteInt64, 1, 2, 4))
+ b.Run("Str", runWith(benchmarkMapDeleteStr, 1, 2, 4))
+}
generated by cgit v1.3-5-g9baa (git 2.53.0) at 2026-04-17 10:29:35 +0000