aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--api/next.txt1
-rw-r--r--doc/go1.15.html14
-rw-r--r--src/sync/map.go25
-rw-r--r--src/sync/map_bench_test.go74
-rw-r--r--src/sync/map_reference_test.go23
-rw-r--r--src/sync/map_test.go13
6 files changed, 138 insertions, 12 deletions
diff --git a/api/next.txt b/api/next.txt
index cab86a9904..442c29a416 100644
--- a/api/next.txt
+++ b/api/next.txt
@@ -1,2 +1,3 @@
pkg testing, method (*T) Deadline() (time.Time, bool)
pkg time, method (*Ticker) Reset(Duration)
+pkg sync, method (*Map) LoadAndDelete(interface{}) (interface{}, bool)
diff --git a/doc/go1.15.html b/doc/go1.15.html
index ed240d85cc..5b0459e67a 100644
--- a/doc/go1.15.html
+++ b/doc/go1.15.html
@@ -81,6 +81,20 @@ TODO
TODO
</p>
+<dl id="sync"><dt><a href="/pkg/sync/">sync</a></dt>
+ <dd>
+ <p><!-- golang.org/issue/33762 -->
+ The new method
+ <a href="/pkg/sync#Map.LoadAndDelete"><code>Map.LoadAndDelete</code></a>
+ atomically deletes a key and returns the previous value if present.
+ </p>
+ <p><!-- CL 205899 -->
+ The method
+ <a href="/pkg/sync#Map.Delete"><code>Map.Delete</code></a>
+ is more efficient.
+ </p>
+</dl><!-- sync -->
+
<dl id="time"><dt><a href="/pkg/time/">time</a></dt>
<dd>
<p><!-- golang.org/issue/33184 -->
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
}
}
}
diff --git a/src/sync/map_bench_test.go b/src/sync/map_bench_test.go
index e6a8badddb..cf0a3d7fde 100644
--- a/src/sync/map_bench_test.go
+++ b/src/sync/map_bench_test.go
@@ -144,6 +144,66 @@ func BenchmarkLoadOrStoreCollision(b *testing.B) {
})
}
+func BenchmarkLoadAndDeleteBalanced(b *testing.B) {
+ const hits, misses = 128, 128
+
+ benchMap(b, bench{
+ setup: func(b *testing.B, m mapInterface) {
+ if _, ok := m.(*DeepCopyMap); ok {
+ b.Skip("DeepCopyMap has quadratic running time.")
+ }
+ for i := 0; i < hits; i++ {
+ m.LoadOrStore(i, i)
+ }
+ // Prime the map to get it into a steady state.
+ for i := 0; i < hits*2; i++ {
+ m.Load(i % hits)
+ }
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ j := i % (hits + misses)
+ if j < hits {
+ m.LoadAndDelete(j)
+ } else {
+ m.LoadAndDelete(i)
+ }
+ }
+ },
+ })
+}
+
+func BenchmarkLoadAndDeleteUnique(b *testing.B) {
+ benchMap(b, bench{
+ setup: func(b *testing.B, m mapInterface) {
+ if _, ok := m.(*DeepCopyMap); ok {
+ b.Skip("DeepCopyMap has quadratic running time.")
+ }
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ m.LoadAndDelete(i)
+ }
+ },
+ })
+}
+
+func BenchmarkLoadAndDeleteCollision(b *testing.B) {
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ m.LoadOrStore(0, 0)
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ m.LoadAndDelete(0)
+ }
+ },
+ })
+}
+
func BenchmarkRange(b *testing.B) {
const mapSize = 1 << 10
@@ -213,3 +273,17 @@ func BenchmarkAdversarialDelete(b *testing.B) {
},
})
}
+
+func BenchmarkDeleteCollision(b *testing.B) {
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ m.LoadOrStore(0, 0)
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ m.Delete(0)
+ }
+ },
+ })
+}
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()
diff --git a/src/sync/map_test.go b/src/sync/map_test.go
index b60a1c7bed..4ae989a6d5 100644
--- a/src/sync/map_test.go
+++ b/src/sync/map_test.go
@@ -16,13 +16,14 @@ import (
type mapOp string
const (
- opLoad = mapOp("Load")
- opStore = mapOp("Store")
- opLoadOrStore = mapOp("LoadOrStore")
- opDelete = mapOp("Delete")
+ opLoad = mapOp("Load")
+ opStore = mapOp("Store")
+ opLoadOrStore = mapOp("LoadOrStore")
+ opLoadAndDelete = mapOp("LoadAndDelete")
+ opDelete = mapOp("Delete")
)
-var mapOps = [...]mapOp{opLoad, opStore, opLoadOrStore, opDelete}
+var mapOps = [...]mapOp{opLoad, opStore, opLoadOrStore, opLoadAndDelete, opDelete}
// mapCall is a quick.Generator for calls on mapInterface.
type mapCall struct {
@@ -39,6 +40,8 @@ func (c mapCall) apply(m mapInterface) (interface{}, bool) {
return nil, false
case opLoadOrStore:
return m.LoadOrStore(c.k, c.v)
+ case opLoadAndDelete:
+ return m.LoadAndDelete(c.k)
case opDelete:
m.Delete(c.k)
return nil, false
7apu2bq3rhoylwmucxizk54afw5jyda7pho4j5zdcqpwkufke7zdzwad.onion