[go] sync: add new Map method Swap
Changkun Ou (Gerrit)
Set Ready For Review
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills.
Patch set 3:Run-TryBot +1
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills, Changkun Ou.
Changkun Ou uploaded patch set #4 to this change.
sync: add new Map method Swap
SwapCollision/*sync_test.DeepCopyMap-16 252ns ± 1%
SwapCollision/*sync_test.RWMutexMap-16 102ns ± 1%
SwapCollision/*sync.Map-16 133ns ± 2%
SwapMostlyHits/*sync_test.DeepCopyMap-16 54.9µs ± 1%
SwapMostlyHits/*sync_test.RWMutexMap-16 161ns ± 1%
SwapMostlyHits/*sync.Map-16 15.7ns ± 3%
SwapMostlyMisses/*sync_test.DeepCopyMap-16 53.5µs ± 2%
SwapMostlyMisses/*sync_test.RWMutexMap-16 161ns ± 0%
SwapMostlyMisses/*sync.Map-16 172ns ± 1%
DO NOT SUBMIT until #51972 is accepted.
Fixes #51972
Change-Id: I469e71033592997832c3e8ebdad1b8950a70c99c
---
A api/next/51972.txt
M doc/go1.19.html
M src/sync/map.go
M src/sync/map_bench_test.go
M src/sync/map_reference_test.go
M src/sync/map_test.go
6 files changed, 185 insertions(+), 39 deletions(-)
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills, Changkun Ou.
Changkun Ou uploaded patch set #5 to this change.
sync: add new Map method Swap
SwapCollision/*sync_test.DeepCopyMap-16 252ns ± 1%
SwapCollision/*sync_test.RWMutexMap-16 102ns ± 1%
SwapCollision/*sync.Map-16 133ns ± 2%
SwapMostlyHits/*sync_test.DeepCopyMap-16 54.9µs ± 1%
SwapMostlyHits/*sync_test.RWMutexMap-16 161ns ± 1%
SwapMostlyHits/*sync.Map-16 15.7ns ± 3%
SwapMostlyMisses/*sync_test.DeepCopyMap-16 53.5µs ± 2%
SwapMostlyMisses/*sync_test.RWMutexMap-16 161ns ± 0%
SwapMostlyMisses/*sync.Map-16 172ns ± 1%
DO NOT SUBMIT
until #51972 is accepted.
Fixes #51972
Change-Id: I469e71033592997832c3e8ebdad1b8950a70c99c
---
A api/next/51972.txt
M doc/go1.19.html
M src/sync/map.go
M src/sync/map_bench_test.go
M src/sync/map_reference_test.go
M src/sync/map_test.go
6 files changed, 187 insertions(+), 39 deletions(-)
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills.
Patch set 5:Code-Review +1
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills.
Patch set 5:Run-TryBot +1-Code-Review
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills, Changkun Ou.
Changkun Ou uploaded patch set #6 to this change.
sync: add new Map method Swap, CompareAndSwap, CompareAndDelete
DO NOT SUBMIT
SwapCollision/*sync_test.DeepCopyMap-16 248ns ± 2%
SwapCollision/*sync_test.RWMutexMap-16 101ns ± 3%
SwapCollision/*sync.Map-16 139ns ± 1%
SwapMostlyHits/*sync_test.DeepCopyMap-16 55.0µs ± 1%
SwapMostlyHits/*sync_test.RWMutexMap-16 158ns ± 1%
SwapMostlyHits/*sync.Map-16 14.6ns ± 4%
SwapMostlyMisses/*sync_test.DeepCopyMap-16 53.6µs ± 3%
SwapMostlyMisses/*sync_test.RWMutexMap-16 158ns ± 1%
SwapMostlyMisses/*sync.Map-16 176ns ± 2%
CompareAndSwapCollision/*sync_test.DeepCopyMap-16 287ns ± 1%
CompareAndSwapCollision/*sync_test.RWMutexMap-16 109ns ± 3%
CompareAndSwapCollision/*sync.Map-16 136ns ± 1%
CompareAndSwapMostlyHits/*sync_test.DeepCopyMap-16 55.4µs ± 1%
CompareAndSwapMostlyHits/*sync_test.RWMutexMap-16 153ns ± 1%
CompareAndSwapMostlyHits/*sync.Map-16 159ns ± 5%
CompareAndSwapMostlyMisses/*sync_test.DeepCopyMap-16 259ns ± 1%
CompareAndSwapMostlyMisses/*sync_test.RWMutexMap-16 107ns ± 2%
CompareAndSwapMostlyMisses/*sync.Map-16 128ns ± 4%
CompareAndDeleteCollision/*sync_test.DeepCopyMap-16 86.4ns ± 0%
CompareAndDeleteCollision/*sync_test.RWMutexMap-16 69.4ns ± 1%
CompareAndDeleteCollision/*sync.Map-16 57.4ns ± 4%
CompareAndDeleteMostlyHits/*sync_test.DeepCopyMap-16 307ns ±24%
CompareAndDeleteMostlyHits/*sync_test.RWMutexMap-16 100ns ± 1%
CompareAndDeleteMostlyHits/*sync.Map-16 92.6ns ± 4%
CompareAndDeleteMostlyMisses/*sync_test.DeepCopyMap-16 124ns ± 1%
CompareAndDeleteMostlyMisses/*sync_test.RWMutexMap-16 100ns ± 1%
CompareAndDeleteMostlyMisses/*sync.Map-16 92.7ns ± 4%
Fixes #51972
Change-Id: I469e71033592997832c3e8ebdad1b8950a70c99c
---
A api/next/51972.txt
M doc/go1.19.html
M src/sync/map.go
M src/sync/map_bench_test.go
M src/sync/map_reference_test.go
M src/sync/map_test.go
6 files changed, 521 insertions(+), 43 deletions(-)
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills, Changkun Ou.
Changkun Ou uploaded patch set #7 to this change.
sync: add new Map method Swap, CompareAndSwap, CompareAndDelete
DO NOT SUBMIT
name time/op
SwapCollision/*sync_test.DeepCopyMap-8 263ns ± 6%
SwapCollision/*sync_test.RWMutexMap-8 180ns ± 1%
SwapCollision/*sync.Map-8 173ns ± 1%
SwapMostlyHits/*sync_test.DeepCopyMap-8 45.5µs ± 3%
SwapMostlyHits/*sync_test.RWMutexMap-8 217ns ± 3%
SwapMostlyHits/*sync.Map-8 23.8ns ± 6%
SwapMostlyMisses/*sync_test.DeepCopyMap-8 46.2µs ± 1%
SwapMostlyMisses/*sync_test.RWMutexMap-8 229ns ± 2%
SwapMostlyMisses/*sync.Map-8 205ns ± 2%
CompareAndSwapCollision/*sync_test.DeepCopyMap-8 316ns ± 5%
CompareAndSwapCollision/*sync_test.RWMutexMap-8 227ns ± 1%
CompareAndSwapCollision/*sync.Map-8 180ns ± 1%
CompareAndSwapMostlyHits/*sync_test.DeepCopyMap-8 48.0µs ± 2%
CompareAndSwapMostlyHits/*sync_test.RWMutexMap-8 200ns ± 2%
CompareAndSwapMostlyHits/*sync.Map-8 221ns ± 3%
CompareAndSwapMostlyMisses/*sync_test.DeepCopyMap-8 333ns ± 3%
CompareAndSwapMostlyMisses/*sync_test.RWMutexMap-8 158ns ± 1%
CompareAndSwapMostlyMisses/*sync.Map-8 137ns ± 3%
CompareAndDeleteCollision/*sync_test.DeepCopyMap-8 143ns ± 3%
CompareAndDeleteCollision/*sync_test.RWMutexMap-8 127ns ± 2%
CompareAndDeleteCollision/*sync.Map-8 96.6ns ± 2%
CompareAndDeleteMostlyHits/*sync_test.DeepCopyMap-8 208ns ± 6%
CompareAndDeleteMostlyHits/*sync_test.RWMutexMap-8 144ns ± 7%
CompareAndDeleteMostlyHits/*sync.Map-8 202ns ± 4%
CompareAndDeleteMostlyMisses/*sync_test.DeepCopyMap-8 171ns ± 2%
CompareAndDeleteMostlyMisses/*sync_test.RWMutexMap-8 142ns ± 0%
CompareAndDeleteMostlyMisses/*sync.Map-8 135ns ± 4%
Fixes #51972
Change-Id: I469e71033592997832c3e8ebdad1b8950a70c99c
---
A api/next/51972.txt
M doc/go1.19.html
M src/sync/map.go
M src/sync/map_bench_test.go
M src/sync/map_reference_test.go
M src/sync/map_test.go
6 files changed, 543 insertions(+), 43 deletions(-)
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills, Changkun Ou.
Changkun Ou uploaded patch set #8 to this change.
sync: add new Map method Swap, CompareAndSwap, CompareAndDelete
6 files changed, 541 insertions(+), 43 deletions(-)
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills.
Patch set 8:Run-TryBot +1
Bryan Mills (Gerrit)
Attention is currently required from: Changkun Ou.
18 comments:
Patchset:
Thanks! I added a lot of comments, but this is actually a really good first cut at the implementation. 👍
(`sync.Map` is pretty gnarly to begin with!)
File src/sync/map.go:
Patch Set #8, Line 163:
func (e *entry) tryCompareAndSwap(old, new *any) bool {We use some interface-copying tricks in `tryLoadOrStore` to avoid a heap-allocation on the “load” path. Should we use a similar technique in `tryCompareAndSwap` to avoid heap-allocating if the comparison fails on the first try?
I think that would imply passing `old` and `new` as type `any` (instead of `*any`) here, and making a copy before the loop:
```
p := atomic.LoadPointer(&e.p)
if p == nil || p == expunged || *(*any)(p) != old {
return false
}// Copy the interface after the first load to make this method more amenable
// to escape analysis: if the comparison fails from the start, we shouldn't
// bother heap-allocating an interface value to store.
nc := new
for {
if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(&nc)) {
return true
}
p = atomic.LoadPointer(&e.p)
if p == nil || p == expunged || *(*any)(p) != old {
return false
}
}
```Patch Set #8, Line 166:
p == nilIn https://go.dev/issue/51972#issuecomment-1090718989, I suggested that if `*old == nil` then we should allow swapping with “no existing value”, but reading your implementation here has caused me to reconsider. (I added a comment to the proposal in https://go.dev/issue/51972#issuecomment-1126408637.)
So I think what you've got here is good, but we need to update the doc comment for `CompareAndSwap` to match what is implemented here.
I think it would also be a good idea to lock that in with a test, demonstrating that `CompareAndSwap(k, nil, v)` returns `false` (and does not swap) if there was no existing value.
Patch Set #8, Line 180:
// compareAndSwapLocked unconditionally compares the old value with theDo we actually need this variant of the method?
I think it's basically equivalent to `tryCompareAndSwap` except that it uses a non-atomic load and always returns on the first iteration, but with branch prediction and cache locality I wonder if those differences are worth the extra code — especially given the heap-allocation optimization described above (which probably also ought to be replicated here).
Patch Set #8, Line 191:
_ = atomic.SwapPointer(&e.p, unsafe.Pointer(new))A comment here would be helpful — why do we need an atomic swap here when we can use a non-atomic load above?
(Or, conversely, why is it ok to use a non-atomic load above if we need an atomic swap here?)
Patch Set #8, Line 191:
_ = atomic.SwapPointer(&e.p, unsafe.Pointer(new))I think that discarding the return value makes this call equivalent to `atomic.StorePointer(&e.p, unsafe.Pointer(new))`..?
if v != nil {
previous = *v
loaded = true
}
return(nit) I'm not a fan of bare returns. I think this would be clearer as:
```
if v == nil {
return nil, false
}
return *v, true
```Patch Set #8, Line 363:
return(nit) `return previous, loaded`
Patch Set #8, Line 376:
if e.tryCompareAndSwap(&old, &new) {Something looks off here to me — I would expect that if `tryCompareAndSwap` fails, then `CompareAndSwap` overall should also fail, not fall back to locking the map and so on.
(Or is this what causes the special-case `nil` behavior?)
swapped = true
return(nit) `return true`
if e.unexpungeLocked() {
// The entry was previously expunged, which implies that there is a
// non-nil dirty map and this entry is not in it.
m.dirty[key] = e
}With the revised `nil` / no-entry behavior in https://go.dev/issue/51972#issuecomment-1126408637, I think we can drop the call to `unexpungeLocked` here — if the entry exists and is expunged, then the comparison fails.
(The lack of an `else` branch here is what got me thinking about revising the `nil` special-case.)
Patch Set #8, Line 395:
return(nit) `return swapped`
Patch Set #8, Line 406:
if e.tryCompareAndSwap(&old, nil) {Ah, now I see why `tryCompareAndSwap` takes a pointer-to-interface. Hmm... I think the escape-analysis trick still applies, but it might require an extra conditional somewhere. 🤔
Patch Set #8, Line 406:
if e.tryCompareAndSwap(&old, nil) {(I think this is the same as in `CompareAndSwap` — we should be able to return immediately if the key exists in the read-only map and the comparison fails.)
if e.unexpungeLocked() {
// The entry was previously expunged, which implies that there is a
// non-nil dirty map and this entry is not in it.
m.dirty[key] = e
}We definitely shouldn't be unexpunging on the `Delete` path. 😅
(“Unexpunging” restores a previously-deleted key, but we're about to delete that key all over again.)Can we replace this with an atomic load of some sort, or just let `compareAndSwapLocked` fail due to the `expunged` value?
Patch Set #8, Line 421:
delete(read.m, key)Can't delete from `read.m` — other goroutines might be reading from it concurrently, which would be a data race.
Instead, we need to mark it with `expunged` (instead of `nil`).
else if !read.amended {
// We're adding the first new key to the dirty map.
// Make sure it is allocated and mark the read-only map as incomplete.
m.dirtyLocked()
m.read.Store(readOnly{m: read.m, amended: true})
}This `else` branch should probably go away — we don't need to allocate a new `dirty` map if we're not going to put anything into it.
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Changkun Ou.
Changkun Ou uploaded patch set #9 to this change.
The following approvals got outdated and were removed: Run-TryBot+1 by Changkun Ou, TryBot-Result+1 by Gopher Robot
sync: add new Map method Swap, CompareAndSwap, CompareAndDelete
SwapCollision/*sync_test.DeepCopyMap-8 231ns ± 3%
SwapCollision/*sync_test.RWMutexMap-8 156ns ± 1%
SwapCollision/*sync.Map-8 152ns ± 1%
SwapMostlyHits/*sync_test.DeepCopyMap-8 40.8µs ± 1%
SwapMostlyHits/*sync_test.RWMutexMap-8 181ns ± 1%
SwapMostlyHits/*sync.Map-8 19.9ns ±12%
SwapMostlyMisses/*sync_test.DeepCopyMap-8 40.1µs ± 1%
SwapMostlyMisses/*sync_test.RWMutexMap-8 189ns ± 2%
SwapMostlyMisses/*sync.Map-8 162ns ± 3%
CompareAndSwapCollision/*sync_test.DeepCopyMap-8 245ns ± 2%
CompareAndSwapCollision/*sync_test.RWMutexMap-8 186ns ± 3%
CompareAndSwapCollision/*sync.Map-8 154ns ± 1%
CompareAndSwapMostlyHits/*sync_test.DeepCopyMap-8 40.9µs ± 0%
CompareAndSwapMostlyHits/*sync_test.RWMutexMap-8 165ns ± 3%
CompareAndSwapMostlyHits/*sync.Map-8 114ns ± 3%
CompareAndSwapMostlyMisses/*sync_test.DeepCopyMap-8 271ns ± 2%
CompareAndSwapMostlyMisses/*sync_test.RWMutexMap-8 143ns ± 1%
CompareAndSwapMostlyMisses/*sync.Map-8 108ns ± 1%
CompareAndDeleteCollision/*sync_test.DeepCopyMap-8 137ns ± 2%
CompareAndDeleteCollision/*sync_test.RWMutexMap-8 123ns ± 1%
CompareAndDeleteCollision/*sync.Map-8 89.0ns ± 1%
CompareAndDeleteMostlyHits/*sync_test.DeepCopyMap-8 167ns ±10%
CompareAndDeleteMostlyHits/*sync_test.RWMutexMap-8 132ns ± 2%
CompareAndDeleteMostlyHits/*sync.Map-8 108ns ± 3%
CompareAndDeleteMostlyMisses/*sync_test.DeepCopyMap-8 157ns ± 1%
CompareAndDeleteMostlyMisses/*sync_test.RWMutexMap-8 137ns ± 2%
CompareAndDeleteMostlyMisses/*sync.Map-8 105ns ± 2%
Fixes #51972
Change-Id: I469e71033592997832c3e8ebdad1b8950a70c99c
---
A api/next/51972.txt
M doc/go1.19.html
M src/sync/map.go
M src/sync/map_bench_test.go
M src/sync/map_reference_test.go
M src/sync/map_test.go
6 files changed, 530 insertions(+), 44 deletions(-)
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills.
Patch set 9:Run-TryBot +1
15 comments:
File src/sync/map.go:
Patch Set #8, Line 163:
func (e *entry) tryCompareAndSwap(old, new *any) bool {
We use some interface-copying tricks in `tryLoadOrStore` to avoid a heap-allocation on the “load” pa […]
Done. Ah, nice trick (didn't notice the existing `tryLoadOrStore`), thanks!
Patch Set #8, Line 166:
p == nil
In https://go. […]
I added test `TestCompareAndSwap_NonExistingKey`.
Patch Set #8, Line 180:
// compareAndSwapLocked unconditionally compares the old value with theDo we actually need this variant of the method? […]
I benchmarked the existing cases:
```
CompareAndDeleteCollision/*sync.Map-8 89.7ns ± 1% 88.9ns ± 1% -0.83% (p=0.000 n=9+10)
CompareAndDeleteMostlyHits/*sync.Map-8 161ns ± 2% 175ns ± 2% +9.10% (p=0.000 n=10+10)
CompareAndDeleteMostlyMisses/*sync.Map-8 95.6ns ± 2% 114.4ns ± 1% +19.73% (p=0.000 n=10+9)
```Although it is just a single atomic operation, but it should have better performance
for the mostly misses case.If we decided to remove this variant, we may also remove `swapLocked`. Should we do that too?
Patch Set #8, Line 191:
_ = atomic.SwapPointer(&e.p, unsafe.Pointer(new))
A comment here would be helpful — why do we need an atomic swap here when we can use a non-atomic lo […]
Hmm. I don't fully remember why I was using atomic swap here. But currently I think you are right: we don't need atomic here.
Patch Set #8, Line 191:
_ = atomic.SwapPointer(&e.p, unsafe.Pointer(new))
I think that discarding the return value makes this call equivalent to `atomic.StorePointer(&e. […]
Done
if v != nil {
previous = *v
loaded = true
}
return
(nit) I'm not a fan of bare returns. I think this would be clearer as: […]
Done
Patch Set #8, Line 363:
return(nit) `return previous, loaded`
Done
Patch Set #8, Line 376:
if e.tryCompareAndSwap(&old, &new) {
(Or is this what causes the special-case `nil` behavior?)
Hmm.. If we fail this fast path, then it get different result compare to RWMutex and DeepCopy results.
I don't know if my understanding to the `Map` implementation is sound: for an entry, it under the loop points to the same actual value cross read and dirty map. The current path is roughly matching the idea as `Swap`'s fast path. So if we swap success, then here should be fine regardless of promoting?
swapped = true
return(nit) `return true`
Done
if e.unexpungeLocked() {
// The entry was previously expunged, which implies that there is a
// non-nil dirty map and this entry is not in it.
m.dirty[key] = e
}
With the revised `nil` / no-entry behavior in https://go. […]
Done
Patch Set #8, Line 395:
return(nit) `return swapped`
Done
Patch Set #8, Line 406:
if e.tryCompareAndSwap(&old, nil) {
(I think this is the same as in `CompareAndSwap` — we should be able to return immediately if the ke […]
See above comments in `CompareAndSwap`.
if e.unexpungeLocked() {
// The entry was previously expunged, which implies that there is a
// non-nil dirty map and this entry is not in it.
m.dirty[key] = e
}
We definitely shouldn't be unexpunging on the `Delete` path. 😅 […]
Hmm. Another place I don't remember why I did that.. I think we could just remove that as `CompareAndSwap` and `CompareAndDelete` align to each other similarly anyway?
Patch Set #8, Line 421:
delete(read.m, key)
Can't delete from `read. […]
Done
else if !read.amended {
// We're adding the first new key to the dirty map.
// Make sure it is allocated and mark the read-only map as incomplete.
m.dirtyLocked()
m.read.Store(readOnly{m: read.m, amended: true})
}
This `else` branch should probably go away — we don't need to allocate a new `dirty` map if we're no […]
Done
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills, Changkun Ou.
Changkun Ou uploaded patch set #10 to this change.
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills.
Patch set 10:Run-TryBot +1
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills, Russ Cox.
1 comment:
Patchset:
Sorry, but I think we've probably missed the cutoff at this point for adding new API for Go 1.19. […]
Hm. But the CL was sent in April initially before the cutoff...
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills, Changkun Ou.
Changkun Ou uploaded patch set #11 to this change.
M src/sync/map.go
M src/sync/map_bench_test.go
M src/sync/map_reference_test.go
M src/sync/map_test.go
5 files changed, 520 insertions(+), 44 deletions(-)
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills.
Patch set 11:Run-TryBot +1
Bryan Mills (Gerrit)
Attention is currently required from: Bryan Mills, Russ Cox.
Bryan Mills removed a vote from this change.
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Bryan Mills (Gerrit)
Attention is currently required from: Changkun Ou, Russ Cox.
5 comments:
File src/sync/map.go:
Patch Set #8, Line 180:
// compareAndSwapLocked unconditionally compares the old value with theI benchmarked the existing cases: […]
I'm curious as to why there is a performance difference for the `MostlyMisses` case — the timing looks like an extra cache miss, which could be due to an extra allocation.
(I wonder if that indicates that the deferred-allocation trick in `tryCompareAndSwap` isn't working?)
Patch Set #8, Line 376:
if e.tryCompareAndSwap(&old, &new) {(Or is this what causes the special-case `nil` behavior?)
Hmm.. If we fail this fast path, then it get different result compare to RWMutex and DeepCopy results.
Different in what way?
I don't know if my understanding to the `Map` implementation is sound: for an entry, it under the loop points to the same actual value cross read and dirty map.
Correct: if an entry exists in the `read` map, then either it isn't present in the `dirty` map at all (and its entry points to `expunged`, and `CompareAndSwap` should fail because the current value is not equal to `old`), or the entry in the `dirty` map is the same as the one in the `read` map.
The current path is roughly matching the idea as `Swap`'s fast path. So if we swap success, then here should be fine regardless of promoting?
I don't think I follow what you mean? 😅
File src/sync/map.go:
Patch Set #11, Line 179:
nc := newDoes this actually prevent `new` from escaping? (What do the allocs in the benchmarks indicate?)
I think that in order to prevent the allocation the `new` argument (and perhaps `old` as well) needs to be passed as a non-pointer (`any` instead of `*any`). Then `nc := new` allocates a new two-word interface value on the heap, preventing the function argument itself from needing to be heap-allocated.
Or, maybe we need an extra dereference here somewhere?
```
var nc *any
if new != nil {
nc = new(any)
*nc = *new
}
```Patch Set #11, Line 181:
unsafe.Pointer(nc)Now that we have `atomic.Pointer[T]`, would it make sense to change `e.p` to `atomic.Pointer[any]` (perhaps in a separate CL before this one)?
I think that could clean up a lot of these swaps and loads, and would also reduce the risk of `unsafe.Pointer` bugs.
if e, ok := read.m[key]; ok {
if e.compareAndSwapLocked(&old, nil) {
delete(m.dirty, key)
e.delete()
deleted = true
}
} else if e, ok := m.dirty[key]; ok {
if e.compareAndSwapLocked(&old, nil) {
delete(m.dirty, key)
e.delete()
deleted = true
}
}Something seems off here — the two branches of this conditional now have the same body.
Looking at `LoadAndDelete` for comparison, I think what's missing is recording cache misses. (If not for that, we wouldn't need to recheck the `read` map at all: either way we're only deleting from `m.dirty`.)
So, I think what we need here may be something very much like `LoadAndDelete` but without the actual `delete` part:
```
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
if !ok {
m.mu.Lock()
e, ok = read.m[key]
if !ok && read.amended {
e, ok = m.dirty[key]
// Don't delete key from m.dirty: we still need to do the “compare” part
// of the operation. The entry will eventually be expunged when the
// dirty map is promoted to the read map.
//
// 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 {
return e.tryCompareAndSwap(&old, nil)
}
return false
```
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Changkun Ou, Russ Cox.
Changkun Ou uploaded patch set #12 to this change.
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Changkun Ou, Russ Cox.
Changkun Ou uploaded patch set #13 to this change.
sync: add new Map method Swap, CompareAndSwap, CompareAndDelete
5 files changed, 521 insertions(+), 44 deletions(-)
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Changkun Ou, Russ Cox.
Changkun Ou uploaded patch set #14 to this change.
sync: add new Map method Swap, CompareAndSwap, CompareAndDelete
goos: darwin
goarch: arm64
pkg: sync
BenchmarkSwapCollision/*sync_test.DeepCopyMap-8 4885048 225.7 ns/op 336 B/op 2 allocs/op
BenchmarkSwapCollision/*sync_test.RWMutexMap-8 8152669 146.8 ns/op 0 B/op 0 allocs/op
BenchmarkSwapCollision/*sync.Map-8 8820404 158.9 ns/op 16 B/op 1 allocs/op
BenchmarkSwapMostlyHits/*sync_test.DeepCopyMap-8 29109 41170 ns/op 82010 B/op 4 allocs/op
BenchmarkSwapMostlyHits/*sync_test.RWMutexMap-8 6383384 204.8 ns/op 14 B/op 1 allocs/op
BenchmarkSwapMostlyHits/*sync.Map-8 47021022 28.46 ns/op 30 B/op 2 allocs/op
BenchmarkSwapMostlyMisses/*sync_test.DeepCopyMap-8 28825 40364 ns/op 79157 B/op 4 allocs/op
BenchmarkSwapMostlyMisses/*sync_test.RWMutexMap-8 6169014 207.1 ns/op 14 B/op 1 allocs/op
BenchmarkSwapMostlyMisses/*sync.Map-8 6216919 206.7 ns/op 30 B/op 2 allocs/op
BenchmarkCompareAndSwapCollision/*sync_test.DeepCopyMap-8 4753238 247.6 ns/op 336 B/op 2 allocs/op
BenchmarkCompareAndSwapCollision/*sync_test.RWMutexMap-8 7877620 168.0 ns/op 0 B/op 0 allocs/op
BenchmarkCompareAndSwapCollision/*sync.Map-8 7768374 154.4 ns/op 16 B/op 1 allocs/op
BenchmarkCompareAndSwapMostlyHits/*sync_test.DeepCopyMap-8 28162 41870 ns/op 82011 B/op 4 allocs/op
BenchmarkCompareAndSwapMostlyHits/*sync_test.RWMutexMap-8 7161682 160.7 ns/op 14 B/op 1 allocs/op
BenchmarkCompareAndSwapMostlyHits/*sync.Map-8 7724161 157.3 ns/op 30 B/op 2 allocs/op
BenchmarkCompareAndSwapMostlyMisses/*sync_test.DeepCopyMap-8 4298024 269.6 ns/op 350 B/op 3 allocs/op
BenchmarkCompareAndSwapMostlyMisses/*sync_test.RWMutexMap-8 9888058 132.5 ns/op 14 B/op 1 allocs/op
BenchmarkCompareAndSwapMostlyMisses/*sync.Map-8 8733549 137.4 ns/op 30 B/op 2 allocs/op
BenchmarkCompareAndDeleteCollision/*sync_test.DeepCopyMap-8 9433279 136.9 ns/op 48 B/op 1 allocs/op
BenchmarkCompareAndDeleteCollision/*sync_test.RWMutexMap-8 10080013 120.4 ns/op 0 B/op 0 allocs/op
BenchmarkCompareAndDeleteCollision/*sync.Map-8 326674948 3.777 ns/op 0 B/op 0 allocs/op
BenchmarkCompareAndDeleteMostlyHits/*sync_test.DeepCopyMap-8 6796590 184.7 ns/op 124 B/op 2 allocs/op
BenchmarkCompareAndDeleteMostlyHits/*sync_test.RWMutexMap-8 9660237 130.8 ns/op 13 B/op 1 allocs/op
BenchmarkCompareAndDeleteMostlyHits/*sync.Map-8 100000000 11.51 ns/op 14 B/op 1 allocs/op
BenchmarkCompareAndDeleteMostlyMisses/*sync_test.DeepCopyMap-8 8014750 149.3 ns/op 62 B/op 2 allocs/op
BenchmarkCompareAndDeleteMostlyMisses/*sync_test.RWMutexMap-8 9533977 129.6 ns/op 14 B/op 1 allocs/op
BenchmarkCompareAndDeleteMostlyMisses/*sync.Map-8
9546687 124.7 ns/op 13 B/op 1
allocs/op
Fixes #51972
Change-Id: I469e71033592997832c3e8ebdad1b8950a70c99c
---
A api/next/51972.txt
M src/sync/map.go
M src/sync/map_bench_test.go
M src/sync/map_reference_test.go
M src/sync/map_test.go
5 files changed, 511 insertions(+), 43 deletions(-)
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills, Russ Cox.
10 comments:
Patchset:
Thanks for the feedback! It would be great if you could take a quick look on the current unresolved comments.
File src/sync/map.go:
Patch Set #8, Line 180:
// compareAndSwapLocked unconditionally compares the old value with the
I'm curious as to why there is a performance difference for the `MostlyMisses` case — the timing loo […]
I benchmarked this again, and there is no difference between using `tryCompareAndSwap` and `compareAndSwapLocked` anymore.
I think the use of `atomic.Pointer` in the entry struct might influence this, but I could not find enough evidence to explain why there was a difference quite a long time ago. Hence I removed `compareAndSwapLocked` in the latest patch.
Patch Set #8, Line 191:
_ = atomic.SwapPointer(&e.p, unsafe.Pointer(new))
Hmm. I don't fully remember why I was using atomic swap here. […]
Done
Patch Set #8, Line 376:
if e.tryCompareAndSwap(&old, &new) {
> > (Or is this what causes the special-case `nil` behavior?) […]
😅 I also could not follow the reasoning here now, could we somehow re-clarify what was the problem here?
Patch Set #8, Line 406:
if e.tryCompareAndSwap(&old, nil) {
Ah, now I see why `tryCompareAndSwap` takes a pointer-to-interface. Hmm... […]
Done
Patch Set #8, Line 406:
if e.tryCompareAndSwap(&old, nil) {
See above comments in `CompareAndSwap`.
Done
if e.unexpungeLocked() {
// The entry was previously expunged, which implies that there is a
// non-nil dirty map and this entry is not in it.
m.dirty[key] = e
}
Hmm. Another place I don't remember why I did that.. […]
I cannot recall what's happening here... Mark is as resolved.
File src/sync/map.go:
Patch Set #11, Line 179:
nc := new
Does this actually prevent `new` from escaping? (What do the allocs in the benchmarks indicate?) […]
Benchmark does not suggest any difference in terms of
```
nc := new
```or the extra dereference approach:
```
name old time/op new time/op delta
SwapCollision/*sync_test.DeepCopyMap-8 227ns ± 0% 231ns ± 0% ~ (p=1.000 n=1+1)
SwapCollision/*sync_test.RWMutexMap-8 153ns ± 0% 141ns ± 0% ~ (p=1.000 n=1+1)
SwapCollision/*sync.Map-8 157ns ± 0% 154ns ± 0% ~ (p=1.000 n=1+1)
SwapMostlyHits/*sync_test.DeepCopyMap-8 41.9µs ± 0% 41.4µs ± 0% ~ (p=1.000 n=1+1)
SwapMostlyHits/*sync_test.RWMutexMap-8 214ns ± 0% 201ns ± 0% ~ (p=1.000 n=1+1)
SwapMostlyHits/*sync.Map-8 25.2ns ± 0% 28.7ns ± 0% ~ (p=1.000 n=1+1)
SwapMostlyMisses/*sync_test.DeepCopyMap-8 41.1µs ± 0% 40.4µs ± 0% ~ (p=1.000 n=1+1)
SwapMostlyMisses/*sync_test.RWMutexMap-8 213ns ± 0% 207ns ± 0% ~ (p=1.000 n=1+1)
SwapMostlyMisses/*sync.Map-8 204ns ± 0% 195ns ± 0% ~ (p=1.000 n=1+1)
CompareAndSwapCollision/*sync_test.DeepCopyMap-8 246ns ± 0% 251ns ± 0% ~ (p=1.000 n=1+1)
CompareAndSwapCollision/*sync_test.RWMutexMap-8 166ns ± 0% 170ns ± 0% ~ (p=1.000 n=1+1)
CompareAndSwapCollision/*sync.Map-8 152ns ± 0% 152ns ± 0% ~ (p=1.000 n=1+1)
CompareAndSwapMostlyHits/*sync_test.DeepCopyMap-8 41.8µs ± 0% 41.9µs ± 0% ~ (p=1.000 n=1+1)
CompareAndSwapMostlyHits/*sync_test.RWMutexMap-8 162ns ± 0% 161ns ± 0% ~ (p=1.000 n=1+1)
CompareAndSwapMostlyHits/*sync.Map-8 155ns ± 0% 157ns ± 0% ~ (p=1.000 n=1+1)
CompareAndSwapMostlyMisses/*sync_test.DeepCopyMap-8 272ns ± 0% 276ns ± 0% ~ (p=1.000 n=1+1)
CompareAndSwapMostlyMisses/*sync_test.RWMutexMap-8 134ns ± 0% 132ns ± 0% ~ (p=1.000 n=1+1)
CompareAndSwapMostlyMisses/*sync.Map-8 140ns ± 0% 150ns ± 0% ~ (p=1.000 n=1+1)
CompareAndDeleteCollision/*sync_test.DeepCopyMap-8 136ns ± 0% 143ns ± 0% ~ (p=1.000 n=1+1)
CompareAndDeleteCollision/*sync_test.RWMutexMap-8 121ns ± 0% 121ns ± 0% ~ (all equal)
CompareAndDeleteCollision/*sync.Map-8 3.59ns ± 0% 3.68ns ± 0% ~ (p=1.000 n=1+1)
CompareAndDeleteMostlyHits/*sync_test.DeepCopyMap-8 150ns ± 0% 206ns ± 0% ~ (p=1.000 n=1+1)
CompareAndDeleteMostlyHits/*sync_test.RWMutexMap-8 133ns ± 0% 131ns ± 0% ~ (p=1.000 n=1+1)
CompareAndDeleteMostlyHits/*sync.Map-8 10.9ns ± 0% 11.2ns ± 0% ~ (p=1.000 n=1+1)
CompareAndDeleteMostlyMisses/*sync_test.DeepCopyMap-8 143ns ± 0% 151ns ± 0% ~ (p=1.000 n=1+1)
CompareAndDeleteMostlyMisses/*sync_test.RWMutexMap-8 128ns ± 0% 138ns ± 0% ~ (p=1.000 n=1+1)
CompareAndDeleteMostlyMisses/*sync.Map-8 121ns ± 0% 120ns ± 0% ~ (p=1.000 n=1+1)name old alloc/op new alloc/op delta
SwapCollision/*sync_test.DeepCopyMap-8 336B ± 0% 336B ± 0% ~ (all equal)
SwapCollision/*sync_test.RWMutexMap-8 0.00B 0.00B ~ (all equal)
SwapCollision/*sync.Map-8 16.0B ± 0% 16.0B ± 0% ~ (all equal)
SwapMostlyHits/*sync_test.DeepCopyMap-8 82.0kB ± 0% 82.0kB ± 0% ~ (all equal)
SwapMostlyHits/*sync_test.RWMutexMap-8 14.0B ± 0% 13.0B ± 0% ~ (p=1.000 n=1+1)
SwapMostlyHits/*sync.Map-8 30.0B ± 0% 30.0B ± 0% ~ (all equal)
SwapMostlyMisses/*sync_test.DeepCopyMap-8 80.3kB ± 0% 79.6kB ± 0% ~ (p=1.000 n=1+1)
SwapMostlyMisses/*sync_test.RWMutexMap-8 14.0B ± 0% 14.0B ± 0% ~ (all equal)
SwapMostlyMisses/*sync.Map-8 30.0B ± 0% 30.0B ± 0% ~ (all equal)
CompareAndSwapCollision/*sync_test.DeepCopyMap-8 336B ± 0% 336B ± 0% ~ (all equal)
CompareAndSwapCollision/*sync_test.RWMutexMap-8 0.00B 0.00B ~ (all equal)
CompareAndSwapCollision/*sync.Map-8 16.0B ± 0% 16.0B ± 0% ~ (all equal)
CompareAndSwapMostlyHits/*sync_test.DeepCopyMap-8 82.0kB ± 0% 82.0kB ± 0% ~ (p=1.000 n=1+1)
CompareAndSwapMostlyHits/*sync_test.RWMutexMap-8 14.0B ± 0% 14.0B ± 0% ~ (all equal)
CompareAndSwapMostlyHits/*sync.Map-8 30.0B ± 0% 30.0B ± 0% ~ (all equal)
CompareAndSwapMostlyMisses/*sync_test.DeepCopyMap-8 350B ± 0% 350B ± 0% ~ (all equal)
CompareAndSwapMostlyMisses/*sync_test.RWMutexMap-8 14.0B ± 0% 14.0B ± 0% ~ (all equal)
CompareAndSwapMostlyMisses/*sync.Map-8 30.0B ± 0% 30.0B ± 0% ~ (all equal)
CompareAndDeleteCollision/*sync_test.DeepCopyMap-8 48.0B ± 0% 48.0B ± 0% ~ (all equal)
CompareAndDeleteCollision/*sync_test.RWMutexMap-8 0.00B 0.00B ~ (all equal)
CompareAndDeleteCollision/*sync.Map-8 0.00B 0.00B ~ (all equal)
CompareAndDeleteMostlyHits/*sync_test.DeepCopyMap-8 72.0B ± 0% 143.0B ± 0% ~ (p=1.000 n=1+1)
CompareAndDeleteMostlyHits/*sync_test.RWMutexMap-8 14.0B ± 0% 13.0B ± 0% ~ (p=1.000 n=1+1)
CompareAndDeleteMostlyHits/*sync.Map-8 14.0B ± 0% 14.0B ± 0% ~ (all equal)
CompareAndDeleteMostlyMisses/*sync_test.DeepCopyMap-8 62.0B ± 0% 62.0B ± 0% ~ (all equal)
CompareAndDeleteMostlyMisses/*sync_test.RWMutexMap-8 13.0B ± 0% 14.0B ± 0% ~ (p=1.000 n=1+1)
CompareAndDeleteMostlyMisses/*sync.Map-8 14.0B ± 0% 13.0B ± 0% ~ (p=1.000 n=1+1)name old allocs/op new allocs/op delta
SwapCollision/*sync_test.DeepCopyMap-8 2.00 ± 0% 2.00 ± 0% ~ (all equal)
SwapCollision/*sync_test.RWMutexMap-8 0.00 0.00 ~ (all equal)
SwapCollision/*sync.Map-8 1.00 ± 0% 1.00 ± 0% ~ (all equal)
SwapMostlyHits/*sync_test.DeepCopyMap-8 4.00 ± 0% 4.00 ± 0% ~ (all equal)
SwapMostlyHits/*sync_test.RWMutexMap-8 1.00 ± 0% 1.00 ± 0% ~ (all equal)
SwapMostlyHits/*sync.Map-8 2.00 ± 0% 2.00 ± 0% ~ (all equal)
SwapMostlyMisses/*sync_test.DeepCopyMap-8 4.00 ± 0% 4.00 ± 0% ~ (all equal)
SwapMostlyMisses/*sync_test.RWMutexMap-8 1.00 ± 0% 1.00 ± 0% ~ (all equal)
SwapMostlyMisses/*sync.Map-8 2.00 ± 0% 2.00 ± 0% ~ (all equal)
CompareAndSwapCollision/*sync_test.DeepCopyMap-8 2.00 ± 0% 2.00 ± 0% ~ (all equal)
CompareAndSwapCollision/*sync_test.RWMutexMap-8 0.00 0.00 ~ (all equal)
CompareAndSwapCollision/*sync.Map-8 1.00 ± 0% 1.00 ± 0% ~ (all equal)
CompareAndSwapMostlyHits/*sync_test.DeepCopyMap-8 4.00 ± 0% 4.00 ± 0% ~ (all equal)
CompareAndSwapMostlyHits/*sync_test.RWMutexMap-8 1.00 ± 0% 1.00 ± 0% ~ (all equal)
CompareAndSwapMostlyHits/*sync.Map-8 2.00 ± 0% 2.00 ± 0% ~ (all equal)
CompareAndSwapMostlyMisses/*sync_test.DeepCopyMap-8 3.00 ± 0% 3.00 ± 0% ~ (all equal)
CompareAndSwapMostlyMisses/*sync_test.RWMutexMap-8 1.00 ± 0% 1.00 ± 0% ~ (all equal)
CompareAndSwapMostlyMisses/*sync.Map-8 2.00 ± 0% 2.00 ± 0% ~ (all equal)
CompareAndDeleteCollision/*sync_test.DeepCopyMap-8 1.00 ± 0% 1.00 ± 0% ~ (all equal)
CompareAndDeleteCollision/*sync_test.RWMutexMap-8 0.00 0.00 ~ (all equal)
CompareAndDeleteCollision/*sync.Map-8 0.00 0.00 ~ (all equal)
CompareAndDeleteMostlyHits/*sync_test.DeepCopyMap-8 2.00 ± 0% 2.00 ± 0% ~ (all equal)
CompareAndDeleteMostlyHits/*sync_test.RWMutexMap-8 1.00 ± 0% 1.00 ± 0% ~ (all equal)
CompareAndDeleteMostlyHits/*sync.Map-8 1.00 ± 0% 1.00 ± 0% ~ (all equal)
CompareAndDeleteMostlyMisses/*sync_test.DeepCopyMap-8 2.00 ± 0% 2.00 ± 0% ~ (all equal)
CompareAndDeleteMostlyMisses/*sync_test.RWMutexMap-8 1.00 ± 0% 1.00 ± 0% ~ (all equal)
CompareAndDeleteMostlyMisses/*sync.Map-8 1.00 ± 0% 1.00 ± 0% ~ (all equal)
```We need to pass a pointer here as the `e.p.CompareAndSwap` needs to compare pointers. Otherwise, `new any` results in a copied pointer.
Patch Set #11, Line 181:
unsafe.Pointer(nc)
Now that we have `atomic.Pointer[T]`, would it make sense to change `e.p` to `atomic. […]
Done
if e, ok := read.m[key]; ok {
if e.compareAndSwapLocked(&old, nil) {
delete(m.dirty, key)
e.delete()
deleted = true
}
} else if e, ok := m.dirty[key]; ok {
if e.compareAndSwapLocked(&old, nil) {
delete(m.dirty, key)
e.delete()
deleted = true
}
}
Something seems off here — the two branches of this conditional now have the same body. […]
Done
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills, Russ Cox.
Patch set 14:Run-TryBot +1
Bryan Mills (Gerrit)
Attention is currently required from: Changkun Ou, Russ Cox.
9 comments:
File src/sync/map_bench_test.go:
Patch Set #14, Line 321:
m.Swap(i%(hits+misses), i)Will this ever miss in the steady state? (Won't the first `Swap` that misses result in all subsequent `Swap` calls for that key being hits?)
Patch Set #14, Line 343:
m.Swap(i%(hits+misses), i)Same here — won't this start to hit after the first pass?
Patch Set #14, Line 383:
if i%2 == 0 {This closely correlates with `i%(hits+misses)`, right?
(Will there be any actual swapping after the first `hits+misses` iterations?)
Patch Set #14, Line 419:
CollisionWhen this reaches a steady state, I think it will not be colliding at all. (The first `CompareAndDelete` will succeed, and after some number of misses the `readOnly` map will get promoted, and then every `CompareAndDelete` after that will be on a completely empty map.)
Patch Set #14, Line 449:
m.CompareAndDelete(i%(hits+misses), i)Same here: since the first `CompareAndDelete` for each key succeeds, later calls will end up operating on an empty map.
File src/sync/map_reference_test.go:
Patch Set #14, Line 108:
reflect.DeepEqual(value, old)I would expect the `CompareAnd` variants to use `==`, not `reflect.DeepEqual` (throughout this file).
File src/sync/map_test.go:
Patch Set #14, Line 65:
m.Store(c.k, 42)The `Store` and `Delete` calls in these ops seem off to me — they're substantially reducing the state space. (They make the `CompareAnd…` operations always operate on keys that are already present in the map, and make it so that the next operation after a `CompareAnd` for any given key is always a `Delete`.)
That said, now that we have proper coverage-guided fuzzing at some point we should switch this test over to a proper fuzz test! 😅
Patch Set #14, Line 103:
index += 1Please use a field on the `mapCall` instead of a package variable here. 😅
Patch Set #14, Line 286:
42, nilI think these arguments are swapped. The case we're considering in the linked comment is `old == nil`, but here we're passing `nil` for the `new` parameter.
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Bryan Mills (Gerrit)
Attention is currently required from: Changkun Ou, Russ Cox.
2 comments:
File src/sync/map.go:
Patch Set #11, Line 179:
nc := new
CompareAndSwapCollision/*sync.Map-8 1.00 ± 0% 1.00 ± 0% ~ (all equal)
File src/sync/map_bench_test.go:
Patch Set #14, Line 349:
func BenchmarkCompareAndSwapCollision(b *testing.B) {The main `CompareAndSwap` benchmark I'd like to see is one where the “old” value never matches, analogous to `BenchmarkLoadOrStoreCollision` which never stores and manages to benchmark at 0 allocs/op.
(If the “old” value does not match, then ideally a call to `CompareAndSwap` should not cause any additional allocations.)
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Bryan Mills (Gerrit)
Attention is currently required from: Changkun Ou, Russ Cox.
1 comment:
File src/sync/map.go:
Patch Set #11, Line 179:
nc := new
> CompareAndSwapCollision/*sync.Map-8 1.00 ± 0% 1. […]
(Ah, that benchmark is not analogous to `BenchmarkLoadOrStoreCollision` because it actually does perform the swap sometimes.)
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Changkun Ou.
Changkun Ou uploaded patch set #15 to this change.
The following approvals got outdated and were removed: Run-TryBot+1 by Changkun Ou, TryBot-Result+1 by Gopher Robot
sync: add new Map method Swap, CompareAndSwap, CompareAndDelete
name time/op
SwapCollision/*sync_test.DeepCopyMap-8 225ns ± 0%
SwapCollision/*sync_test.RWMutexMap-8 142ns ± 0%
SwapCollision/*sync.Map-8 133ns ± 0%
SwapMostlyHits/*sync_test.DeepCopyMap-8 44.6µs ± 0%
SwapMostlyHits/*sync_test.RWMutexMap-8 163ns ± 0%
SwapMostlyHits/*sync.Map-8 22.3ns ± 0%
SwapMostlyMisses/*sync_test.DeepCopyMap-8 234µs ± 0%
SwapMostlyMisses/*sync_test.RWMutexMap-8 373ns ± 0%
SwapMostlyMisses/*sync.Map-8 454ns ± 0%
CompareAndSwapCollision/*sync_test.DeepCopyMap-8 274ns ± 0%
CompareAndSwapCollision/*sync_test.RWMutexMap-8 159ns ± 0%
CompareAndSwapCollision/*sync.Map-8 122ns ± 0%
CompareAndSwapMostlyHits/*sync_test.DeepCopyMap-8 44.9µs ± 0%
CompareAndSwapMostlyHits/*sync_test.RWMutexMap-8 172ns ± 0%
CompareAndSwapMostlyHits/*sync.Map-8 19.7ns ± 0%
CompareAndSwapMostlyMisses/*sync_test.DeepCopyMap-8 260ns ± 0%
CompareAndSwapMostlyMisses/*sync_test.RWMutexMap-8 120ns ± 0%
CompareAndSwapMostlyMisses/*sync.Map-8 96.8ns ± 0%
CompareAndDeleteCollision/*sync_test.DeepCopyMap-8 186ns ± 0%
CompareAndDeleteCollision/*sync_test.RWMutexMap-8 139ns ± 0%
CompareAndDeleteCollision/*sync.Map-8 12.8ns ± 0%
CompareAndDeleteMostlyHits/*sync_test.DeepCopyMap-8 89.2µs ± 0%
CompareAndDeleteMostlyHits/*sync_test.RWMutexMap-8 318ns ± 0%
CompareAndDeleteMostlyHits/*sync.Map-8 25.8ns ± 0%
CompareAndDeleteMostlyMisses/*sync_test.DeepCopyMap-8 251ns ± 0%
CompareAndDeleteMostlyMisses/*sync_test.RWMutexMap-8 120ns ± 0%
CompareAndDeleteMostlyMisses/*sync.Map-8 92.2ns ± 0%
name alloc/op
SwapCollision/*sync_test.DeepCopyMap-8 336B ± 0%
SwapCollision/*sync_test.RWMutexMap-8 0.00B
SwapCollision/*sync.Map-8 16.0B ± 0%
SwapMostlyHits/*sync_test.DeepCopyMap-8 82.0kB ± 0%
SwapMostlyHits/*sync_test.RWMutexMap-8 12.0B ± 0%
SwapMostlyHits/*sync.Map-8 28.0B ± 0%
SwapMostlyMisses/*sync_test.DeepCopyMap-8 337kB ± 0%
SwapMostlyMisses/*sync_test.RWMutexMap-8 121B ± 0%
SwapMostlyMisses/*sync.Map-8 153B ± 0%
CompareAndSwapCollision/*sync_test.DeepCopyMap-8 382B ± 0%
CompareAndSwapCollision/*sync_test.RWMutexMap-8 0.00B
CompareAndSwapCollision/*sync.Map-8 17.0B ± 0%
CompareAndSwapMostlyHits/*sync_test.DeepCopyMap-8 82.0kB ± 0%
CompareAndSwapMostlyHits/*sync_test.RWMutexMap-8 18.0B ± 0%
CompareAndSwapMostlyHits/*sync.Map-8 34.0B ± 0%
CompareAndSwapMostlyMisses/*sync_test.DeepCopyMap-8 359B ± 0%
CompareAndSwapMostlyMisses/*sync_test.RWMutexMap-8 23.0B ± 0%
CompareAndSwapMostlyMisses/*sync.Map-8 39.0B ± 0%
CompareAndDeleteCollision/*sync_test.DeepCopyMap-8 151B ± 0%
CompareAndDeleteCollision/*sync_test.RWMutexMap-8 0.00B
CompareAndDeleteCollision/*sync.Map-8 0.00B
CompareAndDeleteMostlyHits/*sync_test.DeepCopyMap-8 164kB ± 0%
CompareAndDeleteMostlyHits/*sync_test.RWMutexMap-8 23.0B ± 0%
CompareAndDeleteMostlyHits/*sync.Map-8 39.0B ± 0%
CompareAndDeleteMostlyMisses/*sync_test.DeepCopyMap-8 350B ± 0%
CompareAndDeleteMostlyMisses/*sync_test.RWMutexMap-8 15.0B ± 0%
CompareAndDeleteMostlyMisses/*sync.Map-8 15.0B ± 0%
name allocs/op
SwapCollision/*sync_test.DeepCopyMap-8 2.00 ± 0%
SwapCollision/*sync_test.RWMutexMap-8 0.00
SwapCollision/*sync.Map-8 1.00 ± 0%
SwapMostlyHits/*sync_test.DeepCopyMap-8 4.00 ± 0%
SwapMostlyHits/*sync_test.RWMutexMap-8 1.00 ± 0%
SwapMostlyHits/*sync.Map-8 2.00 ± 0%
SwapMostlyMisses/*sync_test.DeepCopyMap-8 9.00 ± 0%
SwapMostlyMisses/*sync_test.RWMutexMap-8 2.00 ± 0%
SwapMostlyMisses/*sync.Map-8 5.00 ± 0%
CompareAndSwapCollision/*sync_test.DeepCopyMap-8 2.00 ± 0%
CompareAndSwapCollision/*sync_test.RWMutexMap-8 0.00
CompareAndSwapCollision/*sync.Map-8 1.00 ± 0%
CompareAndSwapMostlyHits/*sync_test.DeepCopyMap-8 5.00 ± 0%
CompareAndSwapMostlyHits/*sync_test.RWMutexMap-8 2.00 ± 0%
CompareAndSwapMostlyHits/*sync.Map-8 3.00 ± 0%
CompareAndSwapMostlyMisses/*sync_test.DeepCopyMap-8 4.00 ± 0%
CompareAndSwapMostlyMisses/*sync_test.RWMutexMap-8 2.00 ± 0%
CompareAndSwapMostlyMisses/*sync.Map-8 3.00 ± 0%
CompareAndDeleteCollision/*sync_test.DeepCopyMap-8 1.00 ± 0%
CompareAndDeleteCollision/*sync_test.RWMutexMap-8 0.00
CompareAndDeleteCollision/*sync.Map-8 0.00
CompareAndDeleteMostlyHits/*sync_test.DeepCopyMap-8 9.00 ± 0%
CompareAndDeleteMostlyHits/*sync_test.RWMutexMap-8 2.00 ± 0%
CompareAndDeleteMostlyHits/*sync.Map-8 3.00 ± 0%
CompareAndDeleteMostlyMisses/*sync_test.DeepCopyMap-8 3.00 ± 0%
CompareAndDeleteMostlyMisses/*sync_test.RWMutexMap-8 1.00 ± 0%
CompareAndDeleteMostlyMisses/*sync.Map-8 1.00 ± 0%
Fixes #51972
Change-Id: I469e71033592997832c3e8ebdad1b8950a70c99c
---
A api/next/51972.txt
M src/sync/map.go
M src/sync/map_bench_test.go
M src/sync/map_reference_test.go
M src/sync/map_test.go
5 files changed, 579 insertions(+), 40 deletions(-)
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
10 comments:
File src/sync/map_bench_test.go:
Patch Set #14, Line 321:
m.Swap(i%(hits+misses), i)Will this ever miss in the steady state? (Won't the first `Swap` that misses result in all subsequen […]
Reworked the benchmark
Patch Set #14, Line 343:
m.Swap(i%(hits+misses), i)Same here — won't this start to hit after the first pass?
Reworked the benchmark
Patch Set #14, Line 349:
func BenchmarkCompareAndSwapCollision(b *testing.B) {
The main `CompareAndSwap` benchmark I'd like to see is one where the “old” value never matches, anal […]
Updated the benchmark.
Patch Set #14, Line 383:
if i%2 == 0 {
This closely correlates with `i%(hits+misses)`, right? […]
Reworked the benchmark
Patch Set #14, Line 419:
Collision
When this reaches a steady state, I think it will not be colliding at all. […]
Reworked the benchmark
Patch Set #14, Line 449:
m.CompareAndDelete(i%(hits+misses), i)
Same here: since the first `CompareAndDelete` for each key succeeds, later calls will end up operati […]
Reworked the benchmark
File src/sync/map_reference_test.go:
Patch Set #14, Line 108:
reflect.DeepEqual(value, old)
I would expect the `CompareAnd` variants to use `==`, not `reflect. […]
Done
File src/sync/map_test.go:
Patch Set #14, Line 65:
m.Store(c.k, 42)
The `Store` and `Delete` calls in these ops seem off to me — they're substantially reducing the stat […]
Should we do the fuzz test in this CL? or we go for the current feature first?
Patch Set #14, Line 103:
index += 1
Please use a field on the `mapCall` instead of a package variable here. […]
It was added for easier debugging of the outputs. Note that it could not be easily done to use a mapCall field because the mapCall is generated in testing/quick package using reflect; the original index is always a zero value. To not complicate things, removed.
Patch Set #14, Line 286:
42, nil
I think these arguments are swapped. […]
Done
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills.
Patch set 15:Run-TryBot +1
1 comment:
File src/sync/map.go:
Patch Set #11, Line 179:
nc := new
(Ah, that benchmark is not analogous to `BenchmarkLoadOrStoreCollision` because it actually does per […]
Is this still in consideration according to the latest benchmark results?
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills.
Patch set 16:Run-TryBot +1
1 comment:
Patchset:
Rebased to tip
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Bryan Mills (Gerrit)
Attention is currently required from: Changkun Ou.
4 comments:
File src/sync/map_bench_test.go:
Patch Set #16, Line 323:
v := iI think this will result in the map continuously growing as the benchmark runs..?
(Perhaps in the “miss” case we should use `Swap(i, i)` followed by `Delete(i)`?)
Patch Set #16, Line 349:
v := iSame here — unbounded growth?
if m.CompareAndSwap(0, 0, 42) {
m.CompareAndSwap(0, 42, 0)
}I think we also still need (separately) a benchmark where the `CompareAndSwap` always follows the “no existing entry for key” branch, and one where the `CompareAndSwap` always follows the “existing entry for key, but value is not equal” branch.
Both of those benchmarks should report 0 allocs/op for at least the `sync.Map` implementation.
File src/sync/map_test.go:
Patch Set #14, Line 65:
m.Store(c.k, 42)
Should we do the fuzz test in this CL? or we go for the current feature first?
I would do the fuzz test conversion in a separate CL, either before or after this one.
(For this CL, I think it would be fine to either convert to a proper fuzz test in a precursor CL, or implement more realistic `Swap` and `CompareAndSwap` ops in this `quick`-based test.)
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Bryan Mills (Gerrit)
Attention is currently required from: Changkun Ou.
1 comment:
File src/sync/map.go:
Patch Set #8, Line 376:
if e.tryCompareAndSwap(&old, &new) {😅 I also could not follow the reasoning here now, could we somehow re-clarify what was the problem […]
`ok == true` here implies that `read.m` contains an entry for the key.
`!e.tryCompareAndSwap(&old, &new)` implies that that entry does not contain a value equal to `old`.
The interesting case to consider here is when the entry contains `expunged`. In that case, we know that at that moment the `readOnly` map contained an entry for the key but the dirty map did not. (If an entry was re-added in the dirty map, it would have reused the same entry and unexpunged it.)
So we know that either there is no value associated with the key (the entry exists and is either empty or marked as expunged), or there is a value associated with the key but it is not equal to `old`.
In both of those cases, it is valid for `CompareAndSwap` to return `false` immediately, without doing additional work to check the read/write map.
That is: we only need to check the read/write map if it might contain an *equal* value, which would imply no entry at all in `read.m`.
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Changkun Ou.
Changkun Ou uploaded patch set #17 to this change.
The following approvals got outdated and were removed: Run-TryBot+1 by Changkun Ou, TryBot-Result+1 by Gopher Robot
sync: add new Map method Swap, CompareAndSwap, CompareAndDelete
name time/op
SwapCollision/*sync_test.DeepCopyMap-8 239ns ± 0%
SwapCollision/*sync_test.RWMutexMap-8 141ns ± 0%
SwapCollision/*sync.Map-8 149ns ± 0%
SwapMostlyHits/*sync_test.DeepCopyMap-8 42.0µs ± 0%
SwapMostlyHits/*sync_test.RWMutexMap-8 215ns ± 0%
SwapMostlyHits/*sync.Map-8 25.3ns ± 0%
SwapMostlyMisses/*sync_test.DeepCopyMap-8 700ns ± 0%
SwapMostlyMisses/*sync_test.RWMutexMap-8 327ns ± 0%
SwapMostlyMisses/*sync.Map-8 530ns ± 0%
CompareAndSwapCollision/*sync_test.DeepCopyMap-8 314ns ± 0%
CompareAndSwapCollision/*sync_test.RWMutexMap-8 147ns ± 0%
CompareAndSwapCollision/*sync.Map-8 160ns ± 0%
CompareAndSwapNoExistingKey/*sync_test.DeepCopyMap-8 153ns ± 0%
CompareAndSwapNoExistingKey/*sync_test.RWMutexMap-8 122ns ± 0%
CompareAndSwapNoExistingKey/*sync.Map-8 126ns ± 0%
CompareAndSwapValueNotEqual/*sync_test.DeepCopyMap-8 47.2µs ± 0%
CompareAndSwapValueNotEqual/*sync_test.RWMutexMap-8 143ns ± 0%
CompareAndSwapValueNotEqual/*sync.Map-8 166ns ± 0%
CompareAndSwapMostlyHits/*sync_test.DeepCopyMap-8 43.1µs ± 0%
CompareAndSwapMostlyHits/*sync_test.RWMutexMap-8 222ns ± 0%
CompareAndSwapMostlyHits/*sync.Map-8 27.4ns ± 0%
CompareAndSwapMostlyMisses/*sync_test.DeepCopyMap-8 318ns ± 0%
CompareAndSwapMostlyMisses/*sync_test.RWMutexMap-8 141ns ± 0%
CompareAndSwapMostlyMisses/*sync.Map-8 141ns ± 0%
CompareAndDeleteCollision/*sync_test.DeepCopyMap-8 200ns ± 0%
CompareAndDeleteCollision/*sync_test.RWMutexMap-8 132ns ± 0%
CompareAndDeleteCollision/*sync.Map-8 15.5ns ± 0%
CompareAndDeleteMostlyHits/*sync_test.DeepCopyMap-8 85.6µs ± 0%
CompareAndDeleteMostlyHits/*sync_test.RWMutexMap-8 404ns ± 0%
CompareAndDeleteMostlyHits/*sync.Map-8 34.1ns ± 0%
CompareAndDeleteMostlyMisses/*sync_test.DeepCopyMap-8 288ns ± 0%
CompareAndDeleteMostlyMisses/*sync_test.RWMutexMap-8 135ns ± 0%
CompareAndDeleteMostlyMisses/*sync.Map-8 138ns ± 0%
name alloc/op
SwapCollision/*sync_test.DeepCopyMap-8 336B ± 0%
SwapCollision/*sync_test.RWMutexMap-8 0.00B
SwapCollision/*sync.Map-8 16.0B ± 0%
SwapMostlyHits/*sync_test.DeepCopyMap-8 82.1kB ± 0%
SwapMostlyHits/*sync_test.RWMutexMap-8 12.0B ± 0%
SwapMostlyHits/*sync.Map-8 28.0B ± 0%
SwapMostlyMisses/*sync_test.DeepCopyMap-8 713B ± 0%
SwapMostlyMisses/*sync_test.RWMutexMap-8 23.0B ± 0%
SwapMostlyMisses/*sync.Map-8 133B ± 0%
CompareAndSwapCollision/*sync_test.DeepCopyMap-8 381B ± 0%
CompareAndSwapCollision/*sync_test.RWMutexMap-8 0.00B
CompareAndSwapCollision/*sync.Map-8 4.00B ± 0%
CompareAndSwapNoExistingKey/*sync_test.DeepCopyMap-8 56.0B ± 0%
CompareAndSwapNoExistingKey/*sync_test.RWMutexMap-8 7.00B ± 0%
CompareAndSwapNoExistingKey/*sync.Map-8 7.00B ± 0%
CompareAndSwapValueNotEqual/*sync_test.DeepCopyMap-8 82.0kB ± 0%
CompareAndSwapValueNotEqual/*sync_test.RWMutexMap-8 12.0B ± 0%
CompareAndSwapValueNotEqual/*sync.Map-8 12.0B ± 0%
CompareAndSwapMostlyHits/*sync_test.DeepCopyMap-8 82.0kB ± 0%
CompareAndSwapMostlyHits/*sync_test.RWMutexMap-8 18.0B ± 0%
CompareAndSwapMostlyHits/*sync.Map-8 33.0B ± 0%
CompareAndSwapMostlyMisses/*sync_test.DeepCopyMap-8 359B ± 0%
CompareAndSwapMostlyMisses/*sync_test.RWMutexMap-8 23.0B ± 0%
CompareAndSwapMostlyMisses/*sync.Map-8 23.0B ± 0%
CompareAndDeleteCollision/*sync_test.DeepCopyMap-8 142B ± 0%
CompareAndDeleteCollision/*sync_test.RWMutexMap-8 0.00B
CompareAndDeleteCollision/*sync.Map-8 0.00B
CompareAndDeleteMostlyHits/*sync_test.DeepCopyMap-8 164kB ± 0%
CompareAndDeleteMostlyHits/*sync_test.RWMutexMap-8 23.0B ± 0%
CompareAndDeleteMostlyHits/*sync.Map-8 39.0B ± 0%
CompareAndDeleteMostlyMisses/*sync_test.DeepCopyMap-8 351B ± 0%
CompareAndDeleteMostlyMisses/*sync_test.RWMutexMap-8 15.0B ± 0%
CompareAndDeleteMostlyMisses/*sync.Map-8 15.0B ± 0%
name allocs/op
SwapCollision/*sync_test.DeepCopyMap-8 2.00 ± 0%
SwapCollision/*sync_test.RWMutexMap-8 0.00
SwapCollision/*sync.Map-8 1.00 ± 0%
SwapMostlyHits/*sync_test.DeepCopyMap-8 4.00 ± 0%
SwapMostlyHits/*sync_test.RWMutexMap-8 1.00 ± 0%
SwapMostlyHits/*sync.Map-8 2.00 ± 0%
SwapMostlyMisses/*sync_test.DeepCopyMap-8 6.00 ± 0%
SwapMostlyMisses/*sync_test.RWMutexMap-8 2.00 ± 0%
SwapMostlyMisses/*sync.Map-8 6.00 ± 0%
CompareAndSwapCollision/*sync_test.DeepCopyMap-8 2.00 ± 0%
CompareAndSwapCollision/*sync_test.RWMutexMap-8 0.00
CompareAndSwapCollision/*sync.Map-8 0.00
CompareAndSwapNoExistingKey/*sync_test.DeepCopyMap-8 1.00 ± 0%
CompareAndSwapNoExistingKey/*sync_test.RWMutexMap-8 0.00
CompareAndSwapNoExistingKey/*sync.Map-8 0.00
CompareAndSwapValueNotEqual/*sync_test.DeepCopyMap-8 4.00 ± 0%
CompareAndSwapValueNotEqual/*sync_test.RWMutexMap-8 1.00 ± 0%
CompareAndSwapValueNotEqual/*sync.Map-8 1.00 ± 0%
CompareAndSwapMostlyHits/*sync_test.DeepCopyMap-8 5.00 ± 0%
CompareAndSwapMostlyHits/*sync_test.RWMutexMap-8 2.00 ± 0%
CompareAndSwapMostlyHits/*sync.Map-8 3.00 ± 0%
CompareAndSwapMostlyMisses/*sync_test.DeepCopyMap-8 4.00 ± 0%
CompareAndSwapMostlyMisses/*sync_test.RWMutexMap-8 2.00 ± 0%
CompareAndSwapMostlyMisses/*sync.Map-8 2.00 ± 0%
CompareAndDeleteCollision/*sync_test.DeepCopyMap-8 1.00 ± 0%
CompareAndDeleteCollision/*sync_test.RWMutexMap-8 0.00
CompareAndDeleteCollision/*sync.Map-8 0.00
CompareAndDeleteMostlyHits/*sync_test.DeepCopyMap-8 9.00 ± 0%
CompareAndDeleteMostlyHits/*sync_test.RWMutexMap-8 2.00 ± 0%
CompareAndDeleteMostlyHits/*sync.Map-8 3.00 ± 0%
CompareAndDeleteMostlyMisses/*sync_test.DeepCopyMap-8 3.00 ± 0%
CompareAndDeleteMostlyMisses/*sync_test.RWMutexMap-8 1.00 ± 0%
CompareAndDeleteMostlyMisses/*sync.Map-8 1.00 ± 0%
Fixes #51972
Change-Id: I469e71033592997832c3e8ebdad1b8950a70c99c
---
A api/next/51972.txt
M src/sync/map.go
M src/sync/map_bench_test.go
M src/sync/map_reference_test.go
M src/sync/map_test.go
5 files changed, 631 insertions(+), 40 deletions(-)
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills.
Patch set 17:Run-TryBot +1
6 comments:
Patchset:
I added more benchmarks, but it seems as long as we enter tryCompareAndSwap, there will always be an allocation and the trick
nc := new
not working.
name allocs/op
CompareAndSwapValueNotEqual/*sync.Map-8 1.00 ± 0%
File src/sync/map.go:
Patch Set #8, Line 376:
if e.tryCompareAndSwap(&old, &new) {
`ok == true` here implies that `read.m` contains an entry for the key. […]
Thanks for the elaborative answer. I hope the new change should be able to resolve your concern here.
File src/sync/map_bench_test.go:
Patch Set #16, Line 323:
v := i
I think this will result in the map continuously growing as the benchmark runs..? […]
Ah, that's a nice catch. Didn't aware of this issue. But the unbounded growth will only be inside this benchmark, and should it be problematic at all?
Patch Set #16, Line 349:
v := iSame here — unbounded growth?
Done
if m.CompareAndSwap(0, 0, 42) {
m.CompareAndSwap(0, 42, 0)
}
I think we also still need (separately) a benchmark where the `CompareAndSwap` always follows the “n […]
Added BenchmarkCompareAndSwapNoExistingKey and BenchmarkCompareAndSwapValueNotEqual
File src/sync/map_test.go:
Patch Set #14, Line 65:
m.Store(c.k, 42)
I would do the fuzz test conversion in a separate CL, either before or after this one. […]
Convert to a proper fuzz test seems to require a few more adjustments to the mapCall. Hence I revised the CompareAndSwap and CompareAndDelete cases first. A fuzz CL will be appended later.
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills.
1 comment:
File src/sync/map.go:
Patch Set #11, Line 179:
nc := newIs this still in consideration according to the latest benchmark results?
I added more benchmarks, but it seems as long as we enter tryCompareAndSwap, there will always be an allocation and the trick
nc := new
not working:
```
name allocs/op
CompareAndSwapValueNotEqual/*sync.Map-8 1.00 ± 0%
```
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills.
Patch set 18:Run-TryBot +1
1 comment:
Patchset:
sync to tip
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills, Changkun Ou.
Changkun Ou uploaded patch set #19 to this change.
The following approvals got outdated and were removed: Run-TryBot+1 by Changkun Ou, TryBot-Result-1 by Gopher Robot
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills.
Patch set 19:Run-TryBot +1
1 comment:
Patchset:
add new line to api/next/51972.txt
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Bryan Mills (Gerrit)
Attention is currently required from: Changkun Ou.
15 comments:
File src/sync/map.go:
Patch Set #11, Line 179:
nc := new
I added more benchmarks, but it seems as long as we enter tryCompareAndSwap, there will always be an […]
Compiling with `-gcflags=-m`, it appears that this optimization is working:
```
sync/map.go:178:7: leaking param: e
sync/map.go:178:35: old does not escape
sync/map.go:178:40: leaking param: new
sync/map.go:187:2: moved to heap: nc
```That `moved to heap` means that line 187 causes a heap allocation for `any` interface value to be stored (which we expect, and which is fine because at that point we are very likely to successfully swap the map entry).
File src/sync/map.go:
// If old is the nil interface value, the swap will occur if either there
// is no existing value for the key or the existing value is also the
// nil interface.Per https://github.com/golang/go/issues/51972#issuecomment-1126408637, drop this sentence from the doc comment.
(We not longer swap in `new` for a nil `old` if there is no existing value in the map.)
```
} else if !read.amended {
return false // No existing value for key.
}
```Patch Set #20, Line 382:
m.mu.Lock()Looking at the benchmark results, I don't see any performance difference between `sync.Map` and `RWMutexMap` for the compare-and-swap unequal case — they both take ~318 ns/op on my machine.
That suggests that we are acquiring the Mutex on every iteration here. I think we're missing a call to `m.missLocked()` on this path. 🙃
(Specifically a call to `CompareAndSwap` or `CompareAndDelete` with a key that is not equal should count as a “load” for the purpose of counting misses.)
Indeed, adding a call to `missLocked` drops the benchmark down to 8 ns/op:
```
m.mu.Lock()
defer m.mu.Unlock()
read = m.loadReadOnly()
swapped := false
if e, ok := read.m[key]; ok {
swapped = e.tryCompareAndSwap(old, new)
} else if e, ok := m.dirty[key]; ok {
swapped = e.tryCompareAndSwap(old, new)
if !swapped {
// We needed to lock mu in order to compare the value for key, but we didn't end up storing anything.
// Count it as a missed load.
m.missLocked()
}
}
return swapped
```Patch Set #20, Line 401:
if !ok {Move the fast path for `!read.amended` so that it happens before we lock `mu`:
```
e, ok = read.m[key]
if !ok {
if !read.amended {
return false // No existing value for key.
}
m.mu.Lock()
…
}
```That way we don't contend on the mutex at all if `CompareAndDelete` is doomed to fail.
(And maybe add a `BenchmarkCompareAndDeleteNoExistingKey` to cover that case?)
e, ok = read.m[key]
if !ok && read.amended {We need to reload `read` before checking it here. The race is:
0. Start from a state in which `m.dirty` contains an entry for `key` with a value equal to `old`, and `m.read` has no value for `key` but `amended = true`.
1. Goroutine A loads the `read` map and notices that it is amended.
2. Concurrently, goroutine B promotes `m.dirty` to `m.read` and sets `m.dirty` to `nil`.
3. Goroutine A acquires `m.mu`.Now goroutine A will not find the entry in `m.dirty` (because `m.dirty` is nil), but also will not find the entry in `read` (because it was loaded before goroutine B promoted the old `dirty` map).
So this becomes:
```
m.mu.Lock()
read = m.loadReadOnly()
e, ok = read.m[key]
if !ok && read.amended {
e, ok = m.dirty[key]
// …
m.missLocked()
}
m.mu.Unlock()
```
File src/sync/map_bench_test.go:
Patch Set #20, Line 402:
m.CompareAndSwap(i%n, i%n, 0)To really capture the allocation behavior we're interested in, we also need to drive the allocs/op for the reference `RWMutexMap` down to 0 as well.
(Notably, the existing `BenchmarkLoadOrStoreCollision` drives the allocations down to zero per op in part by using the constant `0` for the key.)
If I change this benchmark to use:
```
setup: func(_ *testing.B, m mapInterface) {
m.Store(0, 0)
},perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
for ; pb.Next(); i++ {
m.CompareAndSwap(0, 1, 2)
}
},
```then I find that it indeed has 0 allos/op with both the `RWMutexMap` and `sync.Map`, as expected.
Patch Set #20, Line 412:
setup: func(_ *testing.B, m mapInterface) {Also skip on `DeepCopyMap` due to quadratic running time?
Patch Set #20, Line 480:
setup: func(_ *testing.B, m mapInterface) {Also skip on `DeepCopyMap` due to quadratic running time?
File src/sync/map_reference_test.go:
Patch Set #20, Line 103:
m.dirty = make(map[any]any)Drop this allocation (no need for it, since the comparison fails).
Patch Set #20, Line 119:
m.dirty = make(map[any]any)Drop this allocation.
Patch Set #20, Line 221:
func (m *DeepCopyMap) CompareAndSwap(key, old, new any) (swapped bool) {For a fair comparison, the `CompareAnd` methods for `DeepCopyMap` should first perform the comparison without dirtying the map:
```
clean, _ := m.clean.Load().(map[any]any)
if previous, ok := clean[key]; !ok || previous != old {
return false
}
```That should bring `CompareAndSwapValueNotEqual` down to a very low cost (~4ns/op) in the `DeepCopyMap` case.
Patch Set #20, Line 227:
reflect.DeepEqual(value, old)`value == old`
Patch Set #20, Line 236:
m.mu.Lock()Same here — try the comparison first without dirtying the map.
Patch Set #20, Line 241:
reflect.DeepEqual(value, old)`value == old`
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Changkun Ou.
Changkun Ou uploaded patch set #21 to this change.
The following approvals got outdated and were removed: Run-TryBot+1 by Changkun Ou, TryBot-Result+1 by Gopher Robot
sync: add new Map method Swap, CompareAndSwap, CompareAndDelete
name time/op
SwapCollision/*sync_test.DeepCopyMap-8 246ns ± 0%
SwapCollision/*sync_test.RWMutexMap-8 147ns ± 0%
SwapCollision/*sync.Map-8 146ns ± 0%
SwapMostlyHits/*sync_test.DeepCopyMap-8 42.8µs ± 0%
SwapMostlyHits/*sync_test.RWMutexMap-8 217ns ± 0%
SwapMostlyHits/*sync.Map-8 27.2ns ± 0%
SwapMostlyMisses/*sync_test.DeepCopyMap-8 702ns ± 0%
SwapMostlyMisses/*sync_test.RWMutexMap-8 326ns ± 0%
SwapMostlyMisses/*sync.Map-8 572ns ± 0%
CompareAndSwapCollision/*sync_test.DeepCopyMap-8 3.69ns ± 0%
CompareAndSwapCollision/*sync_test.RWMutexMap-8 144ns ± 0%
CompareAndSwapCollision/*sync.Map-8 20.1ns ± 0%
CompareAndSwapNoExistingKey/*sync_test.DeepCopyMap-8 4.74ns ± 0%
CompareAndSwapNoExistingKey/*sync_test.RWMutexMap-8 125ns ± 0%
CompareAndSwapNoExistingKey/*sync.Map-8 6.36ns ± 0%
CompareAndSwapValueNotEqual/*sync_test.DeepCopyMap-8 2.31ns ± 0%
CompareAndSwapValueNotEqual/*sync_test.RWMutexMap-8 129ns ± 0%
CompareAndSwapValueNotEqual/*sync.Map-8 4.84ns ± 0%
CompareAndSwapMostlyHits/*sync_test.RWMutexMap-8 235ns ± 0%
CompareAndSwapMostlyHits/*sync.Map-8 27.1ns ± 0%
CompareAndSwapMostlyMisses/*sync_test.DeepCopyMap-8 14.0ns ± 0%
CompareAndSwapMostlyMisses/*sync_test.RWMutexMap-8 142ns ± 0%
CompareAndSwapMostlyMisses/*sync.Map-8 14.6ns ± 0%
CompareAndDeleteCollision/*sync_test.DeepCopyMap-8 2.37ns ± 0%
CompareAndDeleteCollision/*sync_test.RWMutexMap-8 131ns ± 0%
CompareAndDeleteCollision/*sync.Map-8 18.0ns ± 0%
CompareAndDeleteMostlyHits/*sync_test.RWMutexMap-8 376ns ± 0%
CompareAndDeleteMostlyHits/*sync.Map-8 32.9ns ± 0%
CompareAndDeleteMostlyMisses/*sync_test.DeepCopyMap-8 8.98ns ± 0%
CompareAndDeleteMostlyMisses/*sync_test.RWMutexMap-8 134ns ± 0%
CompareAndDeleteMostlyMisses/*sync.Map-8 10.9ns ± 0%
name alloc/op
SwapCollision/*sync_test.DeepCopyMap-8 336B ± 0%
SwapCollision/*sync_test.RWMutexMap-8 0.00B
SwapCollision/*sync.Map-8 16.0B ± 0%
SwapMostlyHits/*sync_test.DeepCopyMap-8 82.1kB ± 0%
SwapMostlyHits/*sync_test.RWMutexMap-8 12.0B ± 0%
SwapMostlyHits/*sync.Map-8 28.0B ± 0%
SwapMostlyMisses/*sync_test.DeepCopyMap-8 713B ± 0%
SwapMostlyMisses/*sync_test.RWMutexMap-8 23.0B ± 0%
SwapMostlyMisses/*sync.Map-8 134B ± 0%
CompareAndSwapCollision/*sync_test.DeepCopyMap-8 0.00B
CompareAndSwapCollision/*sync_test.RWMutexMap-8 0.00B
CompareAndSwapCollision/*sync.Map-8 3.00B ± 0%
CompareAndSwapNoExistingKey/*sync_test.DeepCopyMap-8 8.00B ± 0%
CompareAndSwapNoExistingKey/*sync_test.RWMutexMap-8 8.00B ± 0%
CompareAndSwapNoExistingKey/*sync.Map-8 8.00B ± 0%
CompareAndSwapValueNotEqual/*sync_test.DeepCopyMap-8 0.00B
CompareAndSwapValueNotEqual/*sync_test.RWMutexMap-8 0.00B
CompareAndSwapValueNotEqual/*sync.Map-8 0.00B
CompareAndSwapMostlyHits/*sync_test.RWMutexMap-8 18.0B ± 0%
CompareAndSwapMostlyHits/*sync.Map-8 33.0B ± 0%
CompareAndSwapMostlyMisses/*sync_test.DeepCopyMap-8 24.0B ± 0%
CompareAndSwapMostlyMisses/*sync_test.RWMutexMap-8 23.0B ± 0%
CompareAndSwapMostlyMisses/*sync.Map-8 23.0B ± 0%
CompareAndDeleteCollision/*sync_test.DeepCopyMap-8 0.00B
CompareAndDeleteCollision/*sync_test.RWMutexMap-8 0.00B
CompareAndDeleteCollision/*sync.Map-8 0.00B
CompareAndDeleteMostlyHits/*sync_test.RWMutexMap-8 23.0B ± 0%
CompareAndDeleteMostlyHits/*sync.Map-8 39.0B ± 0%
CompareAndDeleteMostlyMisses/*sync_test.DeepCopyMap-8 16.0B ± 0%
CompareAndDeleteMostlyMisses/*sync_test.RWMutexMap-8 15.0B ± 0%
CompareAndDeleteMostlyMisses/*sync.Map-8 16.0B ± 0%
name allocs/op
SwapCollision/*sync_test.DeepCopyMap-8 2.00 ± 0%
SwapCollision/*sync_test.RWMutexMap-8 0.00
SwapCollision/*sync.Map-8 1.00 ± 0%
SwapMostlyHits/*sync_test.DeepCopyMap-8 4.00 ± 0%
SwapMostlyHits/*sync_test.RWMutexMap-8 1.00 ± 0%
SwapMostlyHits/*sync.Map-8 2.00 ± 0%
SwapMostlyMisses/*sync_test.DeepCopyMap-8 6.00 ± 0%
SwapMostlyMisses/*sync_test.RWMutexMap-8 2.00 ± 0%
SwapMostlyMisses/*sync.Map-8 6.00 ± 0%
CompareAndSwapCollision/*sync_test.DeepCopyMap-8 0.00
CompareAndSwapCollision/*sync_test.RWMutexMap-8 0.00
CompareAndSwapCollision/*sync.Map-8 0.00
CompareAndSwapNoExistingKey/*sync_test.DeepCopyMap-8 1.00 ± 0%
CompareAndSwapNoExistingKey/*sync_test.RWMutexMap-8 0.00
CompareAndSwapNoExistingKey/*sync.Map-8 1.00 ± 0%
CompareAndSwapValueNotEqual/*sync_test.DeepCopyMap-8 0.00
CompareAndSwapValueNotEqual/*sync_test.RWMutexMap-8 0.00
CompareAndSwapValueNotEqual/*sync.Map-8 0.00
CompareAndSwapMostlyHits/*sync_test.RWMutexMap-8 2.00 ± 0%
CompareAndSwapMostlyHits/*sync.Map-8 3.00 ± 0%
CompareAndSwapMostlyMisses/*sync_test.DeepCopyMap-8 2.00 ± 0%
CompareAndSwapMostlyMisses/*sync_test.RWMutexMap-8 2.00 ± 0%
CompareAndSwapMostlyMisses/*sync.Map-8 2.00 ± 0%
CompareAndDeleteCollision/*sync_test.DeepCopyMap-8 0.00
CompareAndDeleteCollision/*sync_test.RWMutexMap-8 0.00
CompareAndDeleteCollision/*sync.Map-8 0.00
CompareAndDeleteMostlyHits/*sync_test.RWMutexMap-8 2.00 ± 0%
CompareAndDeleteMostlyHits/*sync.Map-8 3.00 ± 0%
CompareAndDeleteMostlyMisses/*sync_test.DeepCopyMap-8 2.00 ± 0%
CompareAndDeleteMostlyMisses/*sync_test.RWMutexMap-8 1.00 ± 0%
CompareAndDeleteMostlyMisses/*sync.Map-8 1.00 ± 0%
Fixes #51972
Change-Id: I469e71033592997832c3e8ebdad1b8950a70c99c
---
A api/next/51972.txt
M src/sync/map.go
M src/sync/map_bench_test.go
M src/sync/map_reference_test.go
M src/sync/map_test.go
5 files changed, 645 insertions(+), 40 deletions(-)
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills.
Patch set 21:Run-TryBot +1
14 comments:
File src/sync/map.go:
// If old is the nil interface value, the swap will occur if either there
// is no existing value for the key or the existing value is also the
// nil interface.
Per https://github. […]
Done
``` […]
Done
Patch Set #20, Line 382:
m.mu.Lock()
Looking at the benchmark results, I don't see any performance difference between `sync. […]
I am quite surprised by this decision process.
Patch Set #20, Line 401:
if !ok {
Move the fast path for `!read.amended` so that it happens before we lock `mu`: […]
Done
e, ok = read.m[key]
if !ok && read.amended {
We need to reload `read` before checking it here. The race is: […]
Emmm.. Looks like it was uncarefully missed.
File src/sync/map_bench_test.go:
Patch Set #20, Line 402:
m.CompareAndSwap(i%n, i%n, 0)
To really capture the allocation behavior we're interested in, we also need to drive the allocs/op f […]
I just keep failing to understand everything that is happening in this CL regarding what is really the expected result. My previous understanding was that the map stores a bunch of data, and every swap hits the key but is not swapped due to inconsistently stored values.
And now in this changed benchmark, all concurrent CompareAndSwap are hitting the same key 0.
What makes a difference here?
Patch Set #20, Line 412:
setup: func(_ *testing.B, m mapInterface) {Also skip on `DeepCopyMap` due to quadratic running time?
Done
Patch Set #20, Line 480:
setup: func(_ *testing.B, m mapInterface) {Also skip on `DeepCopyMap` due to quadratic running time?
Done
File src/sync/map_reference_test.go:
Patch Set #20, Line 103:
m.dirty = make(map[any]any)Drop this allocation (no need for it, since the comparison fails).
Done
Patch Set #20, Line 119:
m.dirty = make(map[any]any)Drop this allocation.
Done
Patch Set #20, Line 221:
func (m *DeepCopyMap) CompareAndSwap(key, old, new any) (swapped bool) {
For a fair comparison, the `CompareAnd` methods for `DeepCopyMap` should first perform the compariso […]
Done
Patch Set #20, Line 227:
reflect.DeepEqual(value, old)`value == old`
Done
Patch Set #20, Line 236:
m.mu.Lock()Same here — try the comparison first without dirtying the map.
Done
Patch Set #20, Line 241:
reflect.DeepEqual(value, old)`value == old`
Done
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Bryan Mills (Gerrit)
File src/sync/map_bench_test.go:
Patch Set #20, Line 402:
m.CompareAndSwap(i%n, i%n, 0)
I just keep failing to understand everything that is happening in this CL regarding what is really t […]
With a large enough `n`, simply putting the key `i%n` into an interface value allocates.
(In https://go.dev/doc/go1.15#runtime, “[c]onverting a small integer value into an interface value no longer causes allocation.” “small” in that case is “in the range 0–255” — see https://cs.opensource.google/go/go/+/master:src/runtime/iface.go;l=493;drc=2580d0e08d5e9f979b943758d3c49877fb2324cb.)
Since the purpose of the benchmark is to eliminate unnecessary allocations, we want to start out with interface values that don't otherwise force an allocation. (In a real world program, that might be because the key and/or value is some object that is already heap-allocated and long-lived, such as a `reflect.Type`, a small integer, or a named type with underlying type `struct{}`.)
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills.
1 comment:
File src/sync/map_bench_test.go:
Patch Set #20, Line 402:
m.CompareAndSwap(i%n, i%n, 0)
With a large enough `n`, simply putting the key `i%n` into an interface value allocates. […]
That's really in-depth learning from here. Thanks for the explanation 👍
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Bryan Mills (Gerrit)
Attention is currently required from: Changkun Ou.
6 comments:
Patchset:
Thanks again for bearing with me. I just took another read through to double-check my earlier reviews — this code is _really_ subtle so I want to be sure I haven't missed anything! 😅
I have a few minor comments this round, but I think we're converging on something we can merge for Go 1.20. 😁
File src/sync/map.go:
// trySwap swaps a value if the entry has not been expunged.
//
// If the entry is expunged, trySwap returns false and leaves the entry
// unchanged.
func (e *entry) trySwap(i *any) (*any, bool) {
for {
p := e.p.Load()
if p == expunged {
return nil, false
}
if e.p.CompareAndSwap(p, i) {
return p, true
}
}
}(nit) It appears that `trySwap` is only called once, in `Swap`, so please move it down near that function. (In the baseline commit, `tryStore` was located near `Store`, but the call site from `Store` has been moved into `Swap`.)
Patch Set #21, Line 193:
*(*any)(p)(nit) `*p != old`
(since `p` already has type `*any`)
Patch Set #21, Line 388:
if !swapped {I know I suggested this conditional, but thinking about it some more I think the call to `missLocked` should probably be unconditional.
Here's my thinking: if some goroutine were to call `CompareAndSwap` on the same key between two values over and over again, it would hit the lock every single time and never increment the miss-count. On the other hand, if it increments the miss count every time, it will eventually promote the `dirty` map to `read`, and then we'll be able to swap the value as often as we want without acquiring the mutex.
That may be important for cases similar to `expvar.Map`, where a handful of goroutines make a lot of updates to a very stable set of (disjoint) keys.
So probably we should drop the `!swapped` condition, and perhaps the comment should say something like:
```
// We needed to lock mu in order to load the entry for key,
// and the operation didn't change the set of keys in the map
// (so it would be made more efficient by promoting the dirty
// map to read-only).
// Count it as a miss so that we will eventually switch to the
// more efficient steady state.
m.missLocked()
```
if !ok {
if !read.amended {
return false // No existing value for key.
}
(nit) Re-reading this in comparison with `LoadAndDelete`, let's fold the `read.amended` check into the condition and let it fall through otherwise, just like the `if &ok && read.amended {` condition in `LoadAndDelete`.
That helps to emphasize the similarity between `LoadAndDelete` and `CompareAndDelete`, and may also help future readers (like me! 🙃) understand the relationship between the two functions.
```
if !ok && read.amended {
m.mu.Lock()
…
m.mu.Unlock()
}
if ok {
p := e.p.Load()
…
}
return false
```Patch Set #21, Line 425:
if ok {Thinking about the edge-cases here some more, this should probably be a loop rather than a once-through condition.
Suppose that we have one goroutine spinning in a loop on `Store`:
```
n := 0
for m.Store(k, v) {
time.Sleep(nextBackoff(n))
n++
}
```and another racing a `CompareAndDelete`:
```
m.Store(k, v)
…
if m.CompareAndDelete(k, v) {
… // Hit!
}
```Since the value for key `k` is always equal to `v`, the call to `CompareAndDelete` should always return `true`. However, it may currently return `false` instead: the `Store(k, v)` may replace the existing `e.p` pointer with a pointer to another copy of exactly the same value, in which case `e.p.CompareAndSwap(p, nil)` will return false.
To avoid that situation, we can make this loop spin, exactly like the one in `tryCompareAndSwap` but storing `nil` instead of `nc`:
```
for ok {
p := e.p.Load()
if p == nil || p == expunged || *p != old {
return false
}
if e.p.CompareAndSwap(p, nil) {
return true
}
}
```
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Changkun Ou.
Changkun Ou uploaded patch set #22 to this change.
The following approvals got outdated and were removed: Run-TryBot+1 by Changkun Ou, TryBot-Result+1 by Gopher Robot
sync: add new Map method Swap, CompareAndSwap, CompareAndDelete
name time/op
SwapCollision/*sync_test.DeepCopyMap-8 235ns ± 0%
SwapCollision/*sync_test.RWMutexMap-8 145ns ± 0%
SwapCollision/*sync.Map-8 153ns ± 0%
SwapMostlyHits/*sync_test.DeepCopyMap-8 48.2µs ± 0%
SwapMostlyHits/*sync_test.RWMutexMap-8 190ns ± 0%
SwapMostlyHits/*sync.Map-8 28.3ns ± 0%
SwapMostlyMisses/*sync_test.DeepCopyMap-8 681ns ± 0%
SwapMostlyMisses/*sync_test.RWMutexMap-8 336ns ± 0%
SwapMostlyMisses/*sync.Map-8 523ns ± 0%
CompareAndSwapCollision/*sync_test.DeepCopyMap-8 3.99ns ± 0%
CompareAndSwapCollision/*sync_test.RWMutexMap-8 151ns ± 0%
CompareAndSwapCollision/*sync.Map-8 21.6ns ± 0%
CompareAndSwapNoExistingKey/*sync_test.DeepCopyMap-8 3.95ns ± 0%
CompareAndSwapNoExistingKey/*sync_test.RWMutexMap-8 126ns ± 0%
CompareAndSwapNoExistingKey/*sync.Map-8 6.11ns ± 0%
CompareAndSwapValueNotEqual/*sync_test.DeepCopyMap-8 2.15ns ± 0%
CompareAndSwapValueNotEqual/*sync_test.RWMutexMap-8 132ns ± 0%
CompareAndSwapValueNotEqual/*sync.Map-8 5.32ns ± 0%
CompareAndSwapMostlyHits/*sync_test.RWMutexMap-8 219ns ± 0%
CompareAndSwapMostlyHits/*sync.Map-8 27.1ns ± 0%
CompareAndSwapMostlyMisses/*sync_test.DeepCopyMap-8 13.0ns ± 0%
CompareAndSwapMostlyMisses/*sync_test.RWMutexMap-8 147ns ± 0%
CompareAndSwapMostlyMisses/*sync.Map-8 19.6ns ± 0%
CompareAndDeleteCollision/*sync_test.DeepCopyMap-8 2.23ns ± 0%
CompareAndDeleteCollision/*sync_test.RWMutexMap-8 131ns ± 0%
CompareAndDeleteCollision/*sync.Map-8 16.2ns ± 0%
CompareAndDeleteMostlyHits/*sync_test.RWMutexMap-8 367ns ± 0%
CompareAndDeleteMostlyHits/*sync.Map-8 33.1ns ± 0%
CompareAndDeleteMostlyMisses/*sync_test.DeepCopyMap-8 8.75ns ± 0%
CompareAndDeleteMostlyMisses/*sync_test.RWMutexMap-8 134ns ± 0%
CompareAndDeleteMostlyMisses/*sync.Map-8 10.9ns ± 0%
name alloc/op
SwapCollision/*sync_test.DeepCopyMap-8 336B ± 0%
SwapCollision/*sync_test.RWMutexMap-8 0.00B
SwapCollision/*sync.Map-8 16.0B ± 0%
SwapMostlyHits/*sync_test.DeepCopyMap-8 82.1kB ± 0%
SwapMostlyHits/*sync_test.RWMutexMap-8 12.0B ± 0%
SwapMostlyHits/*sync.Map-8 28.0B ± 0%
SwapMostlyMisses/*sync_test.DeepCopyMap-8 713B ± 0%
SwapMostlyMisses/*sync_test.RWMutexMap-8 23.0B ± 0%
SwapMostlyMisses/*sync.Map-8 129B ± 0%
CompareAndSwapCollision/*sync_test.DeepCopyMap-8 0.00B
CompareAndSwapCollision/*sync_test.RWMutexMap-8 0.00B
CompareAndSwapCollision/*sync.Map-8 3.00B ± 0%
CompareAndSwapNoExistingKey/*sync_test.DeepCopyMap-8 8.00B ± 0%
CompareAndSwapNoExistingKey/*sync_test.RWMutexMap-8 8.00B ± 0%
CompareAndSwapNoExistingKey/*sync.Map-8 8.00B ± 0%
CompareAndSwapValueNotEqual/*sync_test.DeepCopyMap-8 0.00B
CompareAndSwapValueNotEqual/*sync_test.RWMutexMap-8 0.00B
CompareAndSwapValueNotEqual/*sync.Map-8 0.00B
CompareAndSwapMostlyHits/*sync_test.RWMutexMap-8 18.0B ± 0%
CompareAndSwapMostlyHits/*sync.Map-8 33.0B ± 0%
CompareAndSwapMostlyMisses/*sync_test.DeepCopyMap-8 24.0B ± 0%
CompareAndSwapMostlyMisses/*sync_test.RWMutexMap-8 23.0B ± 0%
CompareAndSwapMostlyMisses/*sync.Map-8 23.0B ± 0%
CompareAndDeleteCollision/*sync_test.DeepCopyMap-8 0.00B
CompareAndDeleteCollision/*sync_test.RWMutexMap-8 0.00B
CompareAndDeleteCollision/*sync.Map-8 0.00B
CompareAndDeleteMostlyHits/*sync_test.RWMutexMap-8 23.0B ± 0%
CompareAndDeleteMostlyHits/*sync.Map-8 39.0B ± 0%
CompareAndDeleteMostlyMisses/*sync_test.DeepCopyMap-8 16.0B ± 0%
CompareAndDeleteMostlyMisses/*sync_test.RWMutexMap-8 15.0B ± 0%
CompareAndDeleteMostlyMisses/*sync.Map-8 15.0B ± 0%
5 files changed, 649 insertions(+), 45 deletions(-)
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
Attention is currently required from: Bryan Mills.
Patch set 22:Run-TryBot +1
5 comments:
File src/sync/map.go:
// trySwap swaps a value if the entry has not been expunged.
//
// If the entry is expunged, trySwap returns false and leaves the entry
// unchanged.
func (e *entry) trySwap(i *any) (*any, bool) {
for {
p := e.p.Load()
if p == expunged {
return nil, false
}
if e.p.CompareAndSwap(p, i) {
return p, true
}
}
}
(nit) It appears that `trySwap` is only called once, in `Swap`, so please move it down near that fun […]
Done
Patch Set #21, Line 193:
*(*any)(p)
(nit) `*p != old` […]
Done
Patch Set #21, Line 388:
if !swapped {
I know I suggested this conditional, but thinking about it some more I think the call to `missLocked […]
This makes sense to me too.
if !ok {
if !read.amended {
return false // No existing value for key.
}
(nit) Re-reading this in comparison with `LoadAndDelete`, let's fold the `read. […]
Done
Patch Set #21, Line 425:
if ok {
Thinking about the edge-cases here some more, this should probably be a loop rather than a once-thro […]
Done
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Bryan Mills (Gerrit)
Attention is currently required from: Changkun Ou.
Patch set 22:Auto-Submit +1Code-Review +2
Joedian Reid (Gerrit)
Attention is currently required from: Changkun Ou.
Patch set 22:Code-Review +1
Gopher Robot (Gerrit)
Gopher Robot submitted this change.
Reviewed-on: https://go-review.googlesource.com/c/go/+/399094
Run-TryBot: Changkun Ou <ma...@changkun.de>
Reviewed-by: Joedian Reid <joe...@golang.org>
Auto-Submit: Bryan Mills <bcm...@google.com>
TryBot-Result: Gopher Robot <go...@golang.org>
Reviewed-by: Bryan Mills <bcm...@google.com>
---
A api/next/51972.txt
M src/sync/map.go
M src/sync/map_bench_test.go
M src/sync/map_reference_test.go
M src/sync/map_test.go
5 files changed, 655 insertions(+), 45 deletions(-)
diff --git a/api/next/51972.txt b/api/next/51972.txt
new file mode 100644
index 0000000..cab7b3a
--- /dev/null
+++ b/api/next/51972.txt
@@ -0,0 +1,3 @@
+pkg sync, method (*Map) Swap(interface{}, interface{}) (interface{}, bool) #51972
+pkg sync, method (*Map) CompareAndSwap(interface{}, interface{}, interface{}) bool #51972
+pkg sync, method (*Map) CompareAndDelete(interface{}, interface{}) bool #51972
diff --git a/src/sync/map.go b/src/sync/map.go
index fa1cf7c..658cef6 100644
--- a/src/sync/map.go
+++ b/src/sync/map.go
@@ -150,47 +150,33 @@
// Store sets the value for a key.
func (m *Map) Store(key, value any) {
- read := m.loadReadOnly()
- if e, ok := read.m[key]; ok && e.tryStore(&value) {
- return
- }
-
- m.mu.Lock()
- read = m.loadReadOnly()
- if e, ok := read.m[key]; ok {
- if e.unexpungeLocked() {
- // The entry was previously expunged, which implies that there is a
- // non-nil dirty map and this entry is not in it.
- m.dirty[key] = e
- }
- e.storeLocked(&value)
- } else if e, ok := m.dirty[key]; ok {
- e.storeLocked(&value)
- } else {
- if !read.amended {
- // We're adding the first new key to the dirty map.
- // Make sure it is allocated and mark the read-only map as incomplete.
- m.dirtyLocked()
- m.read.Store(&readOnly{m: read.m, amended: true})
- }
- m.dirty[key] = newEntry(value)
- }
- m.mu.Unlock()
+ _, _ = m.Swap(key, value)
}
-// tryStore stores a value if the entry has not been expunged.
+// tryCompareAndSwap compare the entry with the given old value and swaps
+// it with a new value if the entry is equal to the old value, and the entry
+// has not been expunged.
//
-// If the entry is expunged, tryStore returns false and leaves the entry
-// unchanged.
-func (e *entry) tryStore(i *any) bool {
+// If the entry is expunged, tryCompareAndSwap returns false and leaves
+// the entry unchanged.
+func (e *entry) tryCompareAndSwap(old, new any) bool {
+ p := e.p.Load()
+ if p == nil || p == expunged || *p != old {
+ return false
+ }
+
+ // Copy the interface after the first load to make this method more amenable
+ // to escape analysis: if the comparison fails from the start, we shouldn't
+ // bother heap-allocating an interface value to store.
+ nc := new
for {
- p := e.p.Load()
- if p == expunged {
- return false
- }
- if e.p.CompareAndSwap(p, i) {
+ if e.p.CompareAndSwap(p, &nc) {
return true
}
+ p = e.p.Load()
+ if p == nil || p == expunged || *p != old {
+ return false
+ }
}
}
@@ -202,11 +188,11 @@
return e.p.CompareAndSwap(expunged, nil)
}
-// storeLocked unconditionally stores a value to the entry.
+// swapLocked unconditionally swaps a value into the entry.
//
// The entry must be known not to be expunged.
-func (e *entry) storeLocked(i *any) {
- e.p.Store(i)
+func (e *entry) swapLocked(i *any) *any {
+ return e.p.Swap(i)
}
// LoadOrStore returns the existing value for the key if present.
@@ -321,6 +307,132 @@
}
}
+// trySwap swaps a value if the entry has not been expunged.
+//
+// If the entry is expunged, trySwap returns false and leaves the entry
+// unchanged.
+func (e *entry) trySwap(i *any) (*any, bool) {
+ for {
+ p := e.p.Load()
+ if p == expunged {
+ return nil, false
+ }
+ if e.p.CompareAndSwap(p, i) {
+ return p, true
+ }
+ }
+}
+
+// Swap swaps the value for a key and returns the previous value if any.
+// The loaded result reports whether the key was present.
+func (m *Map) Swap(key, value any) (previous any, loaded bool) {
+ read := m.loadReadOnly()
+ if e, ok := read.m[key]; ok {
+ if v, ok := e.trySwap(&value); ok {
+ if v == nil {
+ return nil, false
+ }
+ return *v, true
+ }
+ }
+
+ m.mu.Lock()
+ read = m.loadReadOnly()
+ if e, ok := read.m[key]; ok {
+ if e.unexpungeLocked() {
+ // The entry was previously expunged, which implies that there is a
+ // non-nil dirty map and this entry is not in it.
+ m.dirty[key] = e
+ }
+ if v := e.swapLocked(&value); v != nil {
+ loaded = true
+ previous = *v
+ }
+ } else if e, ok := m.dirty[key]; ok {
+ if v := e.swapLocked(&value); v != nil {
+ loaded = true
+ previous = *v
+ }
+ } else {
+ if !read.amended {
+ // We're adding the first new key to the dirty map.
+ // Make sure it is allocated and mark the read-only map as incomplete.
+ m.dirtyLocked()
+ m.read.Store(&readOnly{m: read.m, amended: true})
+ }
+ m.dirty[key] = newEntry(value)
+ }
+ m.mu.Unlock()
+ return previous, loaded
+}
+
+// CompareAndSwap swaps the old and new values for key
+// if the value stored in the map is equal to old.
+// The old value must be of a comparable type.
+func (m *Map) CompareAndSwap(key, old, new any) bool {
+ read := m.loadReadOnly()
+ if e, ok := read.m[key]; ok {
+ return e.tryCompareAndSwap(old, new)
+ } else if !read.amended {
+ return false // No existing value for key.
+ }
+
+ m.mu.Lock()
+ defer m.mu.Unlock()
+ read = m.loadReadOnly()
+ swapped := false
+ if e, ok := read.m[key]; ok {
+ swapped = e.tryCompareAndSwap(old, new)
+ } else if e, ok := m.dirty[key]; ok {
+ swapped = e.tryCompareAndSwap(old, new)
+ // We needed to lock mu in order to load the entry for key,
+ // and the operation didn't change the set of keys in the map
+ // (so it would be made more efficient by promoting the dirty
+ // map to read-only).
+ // Count it as a miss so that we will eventually switch to the
+ // more efficient steady state.
+ m.missLocked()
+ }
+ return swapped
+}
+
+// CompareAndDelete deletes the entry for key if its value is equal to old.
+// The old value must be of a comparable type.
+//
+// If there is no current value for key in the map, CompareAndDelete
+// returns false (even if the old value is the nil interface value).
+func (m *Map) CompareAndDelete(key, old any) (deleted bool) {
+ read := m.loadReadOnly()
+ e, ok := read.m[key]
+ if !ok && read.amended {
+ m.mu.Lock()
+ read = m.loadReadOnly()
+ e, ok = read.m[key]
+ if !ok && read.amended {
+ e, ok = m.dirty[key]
+ // Don't delete key from m.dirty: we still need to do the “compare” part
+ // of the operation. The entry will eventually be expunged when the
+ // dirty map is promoted to the read map.
+ //
+ // 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()
+ }
+ for ok {
+ p := e.p.Load()
+ if p == nil || p == expunged || *p != old {
+ return false
+ }
+ if e.p.CompareAndSwap(p, nil) {
+ return true
+ }
+ }
+ return false
+}
+
// Range calls f sequentially for each key and value present in the map.
// If f returns false, range stops the iteration.
//
diff --git a/src/sync/map_bench_test.go b/src/sync/map_bench_test.go
index e7b0e60..4815f57 100644
--- a/src/sync/map_bench_test.go
+++ b/src/sync/map_bench_test.go
@@ -198,7 +198,9 @@
perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
for ; pb.Next(); i++ {
- m.LoadAndDelete(0)
+ if _, loaded := m.LoadAndDelete(0); loaded {
+ m.Store(0, 0)
+ }
}
},
})
@@ -287,3 +289,248 @@
},
})
}
+
+func BenchmarkSwapCollision(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.Swap(0, 0)
+ }
+ },
+ })
+}
+
+func BenchmarkSwapMostlyHits(b *testing.B) {
+ const hits, misses = 1023, 1
+
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ 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++ {
+ if i%(hits+misses) < hits {
+ v := i % (hits + misses)
+ m.Swap(v, v)
+ } else {
+ m.Swap(i, i)
+ m.Delete(i)
+ }
+ }
+ },
+ })
+}
+
+func BenchmarkSwapMostlyMisses(b *testing.B) {
+ const hits, misses = 1, 1023
+
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ 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++ {
+ if i%(hits+misses) < hits {
+ v := i % (hits + misses)
+ m.Swap(v, v)
+ } else {
+ m.Swap(i, i)
+ m.Delete(i)
+ }
+ }
+ },
+ })
+}
+
+func BenchmarkCompareAndSwapCollision(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() {
+ if m.CompareAndSwap(0, 0, 42) {
+ m.CompareAndSwap(0, 42, 0)
+ }
+ }
+ },
+ })
+}
+
+func BenchmarkCompareAndSwapNoExistingKey(b *testing.B) {
+ benchMap(b, bench{
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ if m.CompareAndSwap(i, 0, 0) {
+ m.Delete(i)
+ }
+ }
+ },
+ })
+}
+
+func BenchmarkCompareAndSwapValueNotEqual(b *testing.B) {
+ const n = 1 << 10
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ m.Store(0, 0)
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ m.CompareAndSwap(0, 1, 2)
+ }
+ },
+ })
+}
+
+func BenchmarkCompareAndSwapMostlyHits(b *testing.B) {
+ const hits, misses = 1023, 1
+
+ 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++ {
+ v := i
+ if i%(hits+misses) < hits {
+ v = i % (hits + misses)
+ }
+ m.CompareAndSwap(v, v, v)
+ }
+ },
+ })
+}
+
+func BenchmarkCompareAndSwapMostlyMisses(b *testing.B) {
+ const hits, misses = 1, 1023
+
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ 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++ {
+ v := i
+ if i%(hits+misses) < hits {
+ v = i % (hits + misses)
+ }
+ m.CompareAndSwap(v, v, v)
+ }
+ },
+ })
+}
+
+func BenchmarkCompareAndDeleteCollision(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++ {
+ if m.CompareAndDelete(0, 0) {
+ m.Store(0, 0)
+ }
+ }
+ },
+ })
+}
+
+func BenchmarkCompareAndDeleteMostlyHits(b *testing.B) {
+ const hits, misses = 1023, 1
+
+ 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++ {
+ v := i
+ if i%(hits+misses) < hits {
+ v = i % (hits + misses)
+ }
+ if m.CompareAndDelete(v, v) {
+ m.Store(v, v)
+ }
+ }
+ },
+ })
+}
+
+func BenchmarkCompareAndDeleteMostlyMisses(b *testing.B) {
+ const hits, misses = 1, 1023
+
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ 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++ {
+ v := i
+ if i%(hits+misses) < hits {
+ v = i % (hits + misses)
+ }
+ if m.CompareAndDelete(v, v) {
+ m.Store(v, v)
+ }
+ }
+ },
+ })
+}
diff --git a/src/sync/map_reference_test.go b/src/sync/map_reference_test.go
index 1122b40..aa5ebf3 100644
--- a/src/sync/map_reference_test.go
+++ b/src/sync/map_reference_test.go
@@ -18,9 +18,17 @@
LoadOrStore(key, value any) (actual any, loaded bool)
LoadAndDelete(key any) (value any, loaded bool)
Delete(any)
+ Swap(key, value any) (previous any, loaded bool)
+ CompareAndSwap(key, old, new any) (swapped bool)
+ CompareAndDelete(key, old any) (deleted bool)
Range(func(key, value any) (shouldContinue bool))
}
+var (
+ _ mapInterface = &RWMutexMap{}
+ _ mapInterface = &DeepCopyMap{}
+)
+
// RWMutexMap is an implementation of mapInterface using a sync.RWMutex.
type RWMutexMap struct {
mu sync.RWMutex
@@ -57,6 +65,18 @@
return actual, loaded
}
+func (m *RWMutexMap) Swap(key, value any) (previous any, loaded bool) {
+ m.mu.Lock()
+ if m.dirty == nil {
+ m.dirty = make(map[any]any)
+ }
+
+ previous, loaded = m.dirty[key]
+ m.dirty[key] = value
+ m.mu.Unlock()
+ return
+}
+
func (m *RWMutexMap) LoadAndDelete(key any) (value any, loaded bool) {
m.mu.Lock()
value, loaded = m.dirty[key]
@@ -75,6 +95,36 @@
m.mu.Unlock()
}
+func (m *RWMutexMap) CompareAndSwap(key, old, new any) (swapped bool) {
+ m.mu.Lock()
+ defer m.mu.Unlock()
+ if m.dirty == nil {
+ return false
+ }
+
+ value, loaded := m.dirty[key]
+ if loaded && value == old {
+ m.dirty[key] = new
+ return true
+ }
+ return false
+}
+
+func (m *RWMutexMap) CompareAndDelete(key, old any) (deleted bool) {
+ m.mu.Lock()
+ defer m.mu.Unlock()
+ if m.dirty == nil {
+ return false
+ }
+
+ value, loaded := m.dirty[key]
+ if loaded && value == old {
+ delete(m.dirty, key)
+ return true
+ }
+ return false
+}
+
func (m *RWMutexMap) Range(f func(key, value any) (shouldContinue bool)) {
m.mu.RLock()
keys := make([]any, 0, len(m.dirty))
@@ -137,6 +187,16 @@
return actual, loaded
}
+func (m *DeepCopyMap) Swap(key, value any) (previous any, loaded bool) {
+ m.mu.Lock()
+ dirty := m.dirty()
+ previous, loaded = dirty[key]
+ dirty[key] = value
+ m.clean.Store(dirty)
+ m.mu.Unlock()
+ return
+}
+
func (m *DeepCopyMap) LoadAndDelete(key any) (value any, loaded bool) {
m.mu.Lock()
dirty := m.dirty()
@@ -155,6 +215,43 @@
m.mu.Unlock()
}
+func (m *DeepCopyMap) CompareAndSwap(key, old, new any) (swapped bool) {
+ clean, _ := m.clean.Load().(map[any]any)
+ if previous, ok := clean[key]; !ok || previous != old {
+ return false
+ }
+
+ m.mu.Lock()
+ defer m.mu.Unlock()
+ dirty := m.dirty()
+ value, loaded := dirty[key]
+ if loaded && value == old {
+ dirty[key] = new
+ m.clean.Store(dirty)
+ return true
+ }
+ return false
+}
+
+func (m *DeepCopyMap) CompareAndDelete(key, old any) (deleted bool) {
+ clean, _ := m.clean.Load().(map[any]any)
+ if previous, ok := clean[key]; !ok || previous != old {
+ return false
+ }
+
+ m.mu.Lock()
+ defer m.mu.Unlock()
+
+ dirty := m.dirty()
+ value, loaded := dirty[key]
+ if loaded && value == old {
+ delete(dirty, key)
+ m.clean.Store(dirty)
+ return true
+ }
+ return false
+}
+
func (m *DeepCopyMap) Range(f func(key, value any) (shouldContinue bool)) {
clean, _ := m.clean.Load().(map[any]any)
for k, v := range clean {
diff --git a/src/sync/map_test.go b/src/sync/map_test.go
index 8352471..1eb3fc6 100644
--- a/src/sync/map_test.go
+++ b/src/sync/map_test.go
@@ -17,14 +17,26 @@
type mapOp string
const (
- opLoad = mapOp("Load")
- opStore = mapOp("Store")
- opLoadOrStore = mapOp("LoadOrStore")
- opLoadAndDelete = mapOp("LoadAndDelete")
- opDelete = mapOp("Delete")
+ opLoad = mapOp("Load")
+ opStore = mapOp("Store")
+ opLoadOrStore = mapOp("LoadOrStore")
+ opLoadAndDelete = mapOp("LoadAndDelete")
+ opDelete = mapOp("Delete")
+ opSwap = mapOp("Swap")
+ opCompareAndSwap = mapOp("CompareAndSwap")
+ opCompareAndDelete = mapOp("CompareAndDelete")
)
-var mapOps = [...]mapOp{opLoad, opStore, opLoadOrStore, opLoadAndDelete, opDelete}
+var mapOps = [...]mapOp{
+ opLoad,
+ opStore,
+ opLoadOrStore,
+ opLoadAndDelete,
+ opDelete,
+ opSwap,
+ opCompareAndSwap,
+ opCompareAndDelete,
+}
// mapCall is a quick.Generator for calls on mapInterface.
type mapCall struct {
@@ -46,6 +58,21 @@
case opDelete:
m.Delete(c.k)
return nil, false
+ case opSwap:
+ return m.Swap(c.k, c.v)
+ case opCompareAndSwap:
+ if m.CompareAndSwap(c.k, c.v, rand.Int()) {
+ m.Delete(c.k)
+ return c.v, true
+ }
+ return nil, false
+ case opCompareAndDelete:
+ if m.CompareAndDelete(c.k, c.v) {
+ if _, ok := m.Load(c.k); !ok {
+ return nil, true
+ }
+ }
+ return nil, false
default:
panic("invalid mapOp")
}
@@ -245,3 +272,11 @@
t.Fatalf("Unexpected sync.Map size, got %v want %v", length, 0)
}
}
+
+func TestCompareAndSwap_NonExistingKey(t *testing.T) {
+ m := &sync.Map{}
+ if m.CompareAndSwap(m, nil, 42) {
+ // See https://go.dev/issue/51972#issuecomment-1126408637.
+ t.Fatalf("CompareAndSwap on an non-existing key succeeded")
+ }
+}
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Dominik Honnef (Gerrit)
Attention is currently required from: Changkun Ou.
1 comment:
File src/sync/map_bench_test.go:
This constant is unused
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.
Changkun Ou (Gerrit)
1 comment:
File src/sync/map_bench_test.go:
This constant is unused
To view, visit change 399094. To unsubscribe, or for help writing mail filters, visit settings.