internal/persistent: no-op deletion from map does not allocate
We can use a property that split does a dfs search for the key before
doing an actual work. This allows us to do a low-cost early return if
there is no key to delete.
Change-Id: I6ed8068945f9f2dacc356d72b18afce04ec89a3c
Reviewed-on: https://go-review.googlesource.com/c/tools/+/413659
gopls-CI: kokoro <noreply+kokoro@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Run-TryBot: Robert Findley <rfindley@google.com>
Reviewed-by: Alan Donovan <adonovan@google.com>
Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
diff --git a/internal/persistent/map.go b/internal/persistent/map.go
index 9c17ad0..19b5048 100644
--- a/internal/persistent/map.go
+++ b/internal/persistent/map.go
@@ -185,7 +185,7 @@
second, first, overwrite = first, second, !overwrite
}
- left, mid, right := split(second, first.key, less)
+ left, mid, right := split(second, first.key, less, false)
var result *mapNode
if overwrite && mid != nil {
result = mid.shallowCloneWithRef()
@@ -205,23 +205,31 @@
// Return three new trees: left with all nodes with smaller than key, mid with
// the node matching the key, right with all nodes larger than key.
// If there are no nodes in one of trees, return nil instead of it.
+// If requireMid is set (such as during deletion), then all return arguments
+// are nil if mid is not found.
//
// split(n:-0) (left:+1, mid:+1, right:+1)
// Split borrows n without affecting its refcount, and returns three
// new references that that caller is expected to call decref.
-func split(n *mapNode, key interface{}, less func(a, b interface{}) bool) (left, mid, right *mapNode) {
+func split(n *mapNode, key interface{}, less func(a, b interface{}) bool, requireMid bool) (left, mid, right *mapNode) {
if n == nil {
return nil, nil, nil
}
if less(n.key, key) {
- left, mid, right := split(n.right, key, less)
+ left, mid, right := split(n.right, key, less, requireMid)
+ if requireMid && mid == nil {
+ return nil, nil, nil
+ }
newN := n.shallowCloneWithRef()
newN.left = n.left.incref()
newN.right = left
return newN, mid, right
} else if less(key, n.key) {
- left, mid, right := split(n.left, key, less)
+ left, mid, right := split(n.left, key, less, requireMid)
+ if requireMid && mid == nil {
+ return nil, nil, nil
+ }
newN := n.shallowCloneWithRef()
newN.left = right
newN.right = n.right.incref()
@@ -234,7 +242,10 @@
// Delete deletes the value for a key.
func (pm *Map) Delete(key interface{}) {
root := pm.root
- left, mid, right := split(root, key, pm.less)
+ left, mid, right := split(root, key, pm.less, true)
+ if mid == nil {
+ return
+ }
pm.root = merge(left, right)
left.decref()
mid.decref()
diff --git a/internal/persistent/map_test.go b/internal/persistent/map_test.go
index 059f0da..bd2cbfa 100644
--- a/internal/persistent/map_test.go
+++ b/internal/persistent/map_test.go
@@ -71,6 +71,15 @@
m1.remove(t, 1)
validateRef(t, m1, m2)
+ gotAllocs := int(testing.AllocsPerRun(10, func() {
+ m1.impl.Delete(100)
+ m1.impl.Delete(1)
+ }))
+ wantAllocs := 0
+ if gotAllocs != wantAllocs {
+ t.Errorf("wanted %d allocs, got %d", wantAllocs, gotAllocs)
+ }
+
for i := 10; i < 14; i++ {
m1.set(t, i, i)
validateRef(t, m1, m2)
@@ -298,19 +307,3 @@
t.Fatalf("different maps:\n%v\nvs\n%v", map1, map2)
}
}
-
-func isSameMap(map1, map2 reflect.Value) bool {
- if map1.Len() != map2.Len() {
- return false
- }
- iter := map1.MapRange()
- for iter.Next() {
- key := iter.Key()
- value1 := iter.Value()
- value2 := map2.MapIndex(key)
- if value2.IsZero() || !reflect.DeepEqual(value1.Interface(), value2.Interface()) {
- return false
- }
- }
- return true
-}
