sync: add a Map to replace RWLock+map usage

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.)

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.

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.

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/

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

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

expvar: parallelize BenchmarkMapAdd{Same,Different}

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

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?

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.)

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()
}

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.

@akrylysov

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?

@bcmills

@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?

@tmm1

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.

no equivalent method of len(map)?

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?

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.)

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

Navigation Menu

Repository navigation

sync: add a Map to replace RWLock+map usage #18177

57 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

sync: add a Map to replace RWLock+map usage #18177

Description

Activity

bradfitz commented on Dec 3, 2016

rsc commented on Dec 5, 2016

josharian commented on Dec 5, 2016

gopherbot commented on Dec 5, 2016

gopherbot commented on Feb 10, 2017

gopherbot commented on Feb 10, 2017

57 remaining items

tmm1 commented on May 3, 2017

bcmills commented on May 4, 2017

tmm1 commented on May 4, 2017

bcmills commented on May 4, 2017

tmm1 commented on May 4, 2017

seh commented on May 5, 2017

bcmills commented on May 9, 2017

liaoliaopro commented on Jul 9, 2017

tarcieri commented on Jul 20, 2017

bcmills commented on Jul 20, 2017

pciet commented on Dec 9, 2017

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions