diff options
| author | Michael Pratt <mpratt@google.com> | 2024-10-04 15:20:48 -0400 |
|---|---|---|
| committer | Gopher Robot <gobot@golang.org> | 2024-10-28 20:34:48 +0000 |
| commit | efa43c57b109582d602eeb9b5fb690d38e4cf9aa (patch) | |
| tree | 22f4fda23d6334c119d565b7382d0acb2c284eed /src/internal/runtime/maps/map.go | |
| parent | 7de87ebd59f7667f6b27d635a380ea0d9d3dabf5 (diff) | |
| download | go-efa43c57b109582d602eeb9b5fb690d38e4cf9aa.tar.xz | |
internal/runtime/maps: reuse deleted slots on insert
While walking the probe sequence, Put keeps track of the first deleted
slot it encountered. If it reaches the end of the probe sequence without
finding a match, then it will prefer to use the deleted slot rather than
a new empty slot.
For #54766.
Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap
Change-Id: I19356ef6780176506f57b42990ac15dc426f1b14
Reviewed-on: https://go-review.googlesource.com/c/go/+/618016
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Keith Randall <khr@google.com>
Auto-Submit: Michael Pratt <mpratt@google.com>
Reviewed-by: Keith Randall <khr@golang.org>
Diffstat (limited to 'src/internal/runtime/maps/map.go')
| -rw-r--r-- | src/internal/runtime/maps/map.go | 7 |
1 files changed, 4 insertions, 3 deletions
diff --git a/src/internal/runtime/maps/map.go b/src/internal/runtime/maps/map.go index 3594deb285..a26b3cd130 100644 --- a/src/internal/runtime/maps/map.go +++ b/src/internal/runtime/maps/map.go @@ -77,9 +77,10 @@ import ( // slot as empty, as there could be more slots used later in a probe sequence // and this deletion would cause probing to stop too early. Instead, we mark // such slots as "deleted" with a tombstone. If the group still has an empty -// slot, we don't need a tombstone and directly mark the slot empty. Currently, -// tombstone are only cleared during grow, as an in-place cleanup complicates -// iteration. +// slot, we don't need a tombstone and directly mark the slot empty. Insert +// prioritizes reuse of tombstones over filling an empty slots. Otherwise, +// tombstones are only completely cleared during grow, as an in-place cleanup +// complicates iteration. // // Growth // |