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, 23 insertions, 0 deletions

diff --git a/src/sync/map_reference_test.go b/src/sync/map_reference_test.go
index 9f27b07c32..d105a24e92 100644
--- a/src/sync/map_reference_test.go
+++ b/src/sync/map_reference_test.go
@@ -16,6 +16,7 @@ type mapInterface interface {
 	Load(interface{}) (interface{}, bool)
 	Store(key, value interface{})
 	LoadOrStore(key, value interface{}) (actual interface{}, loaded bool)
+	LoadAndDelete(key interface{}) (value interface{}, loaded bool)
 	Delete(interface{})
 	Range(func(key, value interface{}) (shouldContinue bool))
 }
@@ -56,6 +57,18 @@ func (m *RWMutexMap) LoadOrStore(key, value interface{}) (actual interface{}, lo
 	return actual, loaded
 }
 
+func (m *RWMutexMap) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
+	m.mu.Lock()
+	value, loaded = m.dirty[key]
+	if !loaded {
+		m.mu.Unlock()
+		return nil, false
+	}
+	delete(m.dirty, key)
+	m.mu.Unlock()
+	return value, loaded
+}
+
 func (m *RWMutexMap) Delete(key interface{}) {
 	m.mu.Lock()
 	delete(m.dirty, key)
@@ -124,6 +137,16 @@ func (m *DeepCopyMap) LoadOrStore(key, value interface{}) (actual interface{}, l
 	return actual, loaded
 }
 
+func (m *DeepCopyMap) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
+	m.mu.Lock()
+	dirty := m.dirty()
+	value, loaded = dirty[key]
+	delete(dirty, key)
+	m.clean.Store(dirty)
+	m.mu.Unlock()
+	return
+}
+
 func (m *DeepCopyMap) Delete(key interface{}) {
 	m.mu.Lock()
 	dirty := m.dirty()