sync: add new Map method LoadAndDelete

This CL implements a LoadAndDelete method in sync.Map. Benchmark:

name                                              time/op
LoadAndDeleteBalanced/*sync_test.RWMutexMap-12    98.8ns ± 1%
LoadAndDeleteBalanced/*sync.Map-12                10.3ns ±11%
LoadAndDeleteUnique/*sync_test.RWMutexMap-12      99.2ns ± 2%
LoadAndDeleteUnique/*sync.Map-12                  6.63ns ±10%
LoadAndDeleteCollision/*sync_test.DeepCopyMap-12   140ns ± 0%
LoadAndDeleteCollision/*sync_test.RWMutexMap-12   75.2ns ± 2%
LoadAndDeleteCollision/*sync.Map-12               5.21ns ± 5%

In addition, Delete is bounded and more efficient if many collisions:

DeleteCollision/*sync_test.DeepCopyMap-12   120ns ± 2%   125ns ± 1%   +3.80%  (p=0.000 n=10+9)
DeleteCollision/*sync_test.RWMutexMap-12   73.5ns ± 3%  79.5ns ± 1%   +8.03%  (p=0.000 n=10+9)
DeleteCollision/*sync.Map-12               97.8ns ± 3%   5.9ns ± 4%  -94.00%  (p=0.000 n=10+10)

Fixes #33762

Change-Id: Ic8469a7861d27ab0edeface0078aad8af9b26c2f
Reviewed-on: https://go-review.googlesource.com/c/go/+/205899
Reviewed-by: Bryan C. Mills <bcmills@google.com>
Run-TryBot: Bryan C. Mills <bcmills@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>

1 files changed, 18 insertions, 7 deletions

diff --git a/src/sync/map.go b/src/sync/map.go
index c6aa308856..a61e2ebdd6 100644
--- a/src/sync/map.go
+++ b/src/sync/map.go
@@ -263,8 +263,9 @@ func (e *entry) tryLoadOrStore(i interface{}) (actual interface{}, loaded, ok bo
 	}
 }
 
-// Delete deletes the value for a key.
-func (m *Map) Delete(key interface{}) {
+// LoadAndDelete deletes the value for a key, returning the previous value if any.
+// The loaded result reports whether the key was present.
+func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
 	read, _ := m.read.Load().(readOnly)
 	e, ok := read.m[key]
 	if !ok && read.amended {
@@ -272,23 +273,33 @@ func (m *Map) Delete(key interface{}) {
 		read, _ = m.read.Load().(readOnly)
 		e, ok = read.m[key]
 		if !ok && read.amended {
-			delete(m.dirty, key)
+			e, ok = m.dirty[key]
+			// Regardless of whether the entry was present, record a miss: this key
+			// will take the slow path until the dirty map is promoted to the read
+			// map.
+			m.missLocked()
 		}
 		m.mu.Unlock()
 	}
 	if ok {
-		e.delete()
+		return e.delete()
 	}
+	return nil, false
 }
 
-func (e *entry) delete() (hadValue bool) {
+// Delete deletes the value for a key.
+func (m *Map) Delete(key interface{}) {
+	m.LoadAndDelete(key)
+}
+
+func (e *entry) delete() (value interface{}, ok bool) {
 	for {
 		p := atomic.LoadPointer(&e.p)
 		if p == nil || p == expunged {
-			return false
+			return nil, false
 		}
 		if atomic.CompareAndSwapPointer(&e.p, p, nil) {
-			return true
+			return *(*interface{})(p), true
 		}
 	}
 }