sync: add a Map to replace RWLock+map usage

[bcmills]

Per #17973, RWMutex has some scaling issues. One option is to fix RWMutex, but for maps with high read:write ratios we can often do better with a carefully-managed atomic.Value anyway. The standard library contains many such maps, especially in the reflect package.

The actual details of such a map are a bit subtle to implement correctly and efficiently. We should provide a Map implementation in the standard library. Since the implementation may need to use both sync and sync/atomic and the former depends on the latter, it should either go in sync or in a new, separate sync subpackage.

(Presumably this should be targeted to 1.9 due to the 1.8 freeze, but I'd like to add a draft API to x/sync in the meantime.)

[bradfitz]

The standard answer (https://golang.org/doc/faq#x_in_std) is always to prototype it elsewhere first.

So x/sync sounds good to start.

[rsc]

Yes, having such a thing would be nice. There are no details here but I think everyone agrees this comes up repeatedly and would be well served by a library in a standard place. When your code is ready please send a CL.

[josharian]

https://go-review.googlesource.com/c/33912/ has a prototype implementation and API discussion.

Here are some concrete use cases I know of, for use in API discussion:

• reflect's FieldByName: https://go-review.googlesource.com/c/24503/
• reflect's ptrMap: https://go-review.googlesource.com/c/33411/
• mime: https://go-review.googlesource.com/c/2641/

[gopherbot]

CL https://golang.org/cl/33912 mentions this issue.

[gopherbot]

CL https://golang.org/cl/36717 mentions this issue.

[gopherbot]

CL https://golang.org/cl/36719 mentions this issue.

[gopherbot]

CL https://golang.org/cl/36722 mentions this issue.

[gopherbot]

CL https://golang.org/cl/36723 mentions this issue.

[gopherbot]

CL https://golang.org/cl/36724 mentions this issue.

[gopherbot]

CL https://golang.org/cl/36810 mentions this issue.

[gopherbot]

CL https://golang.org/cl/36831 mentions this issue.

[gopherbot]

CL https://golang.org/cl/36959 mentions this issue.

[gopherbot]

CL https://golang.org/cl/36964 mentions this issue.

[gopherbot]

CL https://golang.org/cl/36617 mentions this issue.

[gopherbot]

CL https://golang.org/cl/41991 mentions this issue.

[gopherbot]

CL https://golang.org/cl/42110 mentions this issue.

[gopherbot]

CL https://golang.org/cl/42112 mentions this issue.

[gopherbot]

CL https://golang.org/cl/42113 mentions this issue.

[bradfitz]

This happened. Closing.

CLs can continue to reference this, but no reason to keep this open.

[tmm1]

Very happy to see this land in stdlib.

I wonder though if Delete() should return the deleted value from the Map? Am I missing some simpler way to atomically pull an entry out of the map to operate on it?

[bcmills]

There is currently no way to atomically remove and return a value from the map. There wasn't a use-case for it in the standard library, and it would make the synchronization a bit trickier. If you have a concrete use for it, though, we should by all means consider it.

(Also note that the delete operation for built-in maps doesn't return the deleted element: when possible, I was aiming for consistency with the built-in map API.)

[tmm1]

If you have a concrete use for it, though, we should by all means consider it.

In my case I need to cleanup some resources associated with the object in the map. Currently I have the following, but to make it atomic I would need to add a lock or sync.Once inside my Cleanup() method:

v, ok := streams.Load(key)
if ok {
  v.(*Stream).Cleanup()
  streams.Delete(key)
}

Something like this would be preferable:

v, ok := streams.Delete(key)
if ok {
  v.(*Stream).Cleanup()
}

[bcmills]

I've seen that use-case before.

On the other hand, having Delete return the value would potentially constrain future optimization of sync.Map. The current implementation is reasonably scalable, but it's also very simple. I do not pretend to claim that it is optimal.

I suspect we would want to address this use-case with a separate method. In particular, I think a CompareAndDelete would allow you to do your cleanup without a separate lock:

v, ok := streams.Load(key)
if ok && streams.CompareAndDelete(key, v) {
  v.(*Stream).Cleanup()
}

Since we're after the Go 1.9 feature freeze, let's consider that as a possible API extension for 1.10.

[tmm1]

I like the CompareAndDelete proposal. The additional method would prevent any backwards compat issues.

I'm still on go 1.8, but I imported x/sync/syncmap and it's made my application code significantly cleaner and simpler. Thanks again for this great new type.

I'm also using your lazyLoad technique above to create entries in my map, and I have to say it's quite an elegant implementation. I would echo @akrylysov's sentiment for an API like this in stdlib, as there is quite a lot of boilerplate required at the moment. Maybe a new wrapper type like sync.LazyMap?

[seh]

@bcmills, it looks like Load followed by the hypothetical CompareAndDelete still requires two lookup operations into the map. I understood @tmm1's original request to imply seeking the key's position in the map once, and taking action once there in right place.

Is the problem that you can't atomically remove an entry from that position and capture the value corresponding to the key?

[bcmills]

it looks like Load followed by the hypothetical CompareAndDelete still requires two lookup operations into the map.

Indeed, although a Sufficiently Clever Compiler† could convert them to a single lookup as long as there are no other reads that could introduce a happens-before relationship with some other atomic store.

I understood @tmm1's original request to imply seeking the key's position in the map once, and taking action once there in right place.

The main point of sync.Map is to reduce cross-CPU contention, and it only really needs to be in the standard library at all so that we can use it to reduce contention elsewhere in the standard library. Reducing the number of atomic operations is only a secondary goal. Even with the two atomic operations, CompareAndDelete would avoid contention for @tmm1's use-case.

That said, if you're deleting from the map at all, your use-case is a bit different from the ones in the standard library and you'll likely get better performance from a different data structure, which does not necessarily need to live in the Go standard library.

That's not to say that we can't consider other possible optimizations to the API, of course. A Remove that combines the sequence of Load and CompareAndDelete into a single operation would be worth adding to sync.Map if the use-case turns out to be common. (It's probably worth filing a separate issue to track that use-case, since the immediate goal of this issue, "replace sync.RWMutex usage in the standard library", has been addressed.)

---

† Constructing a Sufficiently Clever Compiler for this usage is left as an exercise for the reader.

[liaoliaopro]

no equivalent method of len(map)?

[tarcieri]

Is this going to ship without any type safety? interface{} everywhere?

It seems like that will make it very hard to add type safety retroactively. What's the plan if Go ever does get generics? Add a new type that uses them and deprecate this?

[bcmills]

Is this going to ship without any type safety? interface{} everywhere?

Run-time type safety, but not compile-time.

It seems like that will make it very hard to add type safety retroactively. What's the plan if Go ever does get generics? Add a new type that uses them and deprecate this?

Presumably, yes.
(See also https://blog.golang.org/toward-go2.)

[pciet]

I brought up having this implementation as a built-in type in the generics discussion for Go 2 due to lack of compile-time type safety: #15292