Go: 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.

[thwd]

A humble request from a bystander: could you kindly document the abstract and internal workings of syncmap somewhere, perhaps in the package's documentation? I read the comment blocks inside the Map struct definition and get the bare mechanics of it. But now I'd love to understand the fast-path vs slow-path and/or clean/dirty rationales.

[bcmills]

@thwd The workings are still in flux. The next version will have fewer slow paths to understand. :)

[gopherbot]

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

[gopherbot]

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

[bcmills]

I have pending changes for several standard-library packages.

There are a few additional uses of RWMutex which could potentially be
replaced but would involve subtle or invasive changes:

syscall/fd_nacl.go uses an RWMutex to guard a map of reference-counted
files. Use of sync.Map would require care to avoid races with
refcount updates.

syscal/env_unix.go uses an RWMutex to guard a map[string]int which
indexes into a []string. sync.Map could potentially be used to reduce
contention in Getenv, but it would require either a parallel map
dedicated to that purpose or a significant change to the existing data
structures.

net/interface.go uses an RWMutex to guard a bidirectional map with
frequent writes. It appears to acquire a read-lock along every path,
so it isn't obvious to me why it's using RWMutex in the first place.

text/template/template.go uses an RWMutex to guard a pair of maps
which are passed to parse.Parse. Changing the underlying data
structure (without introducing needless copying on every Parse) would
require changes to the parse package API.

go/token/position.go uses an RWMutex to guard three variables with
fairly subtle invariants among them. It is plausible that the RWMutex
could be replaced with a sync.Map and one or more atomic variables, but the
changes to do so are not readily apparent.

[rsc]

Let's only replace the ones for which sync.Map makes the code clearer or that show up in profiles and are fixed by use of sync.Map. None of these seem worth doing.

[akrylysov]

Please consider adding a LoadOrStoreLazy(key, factory func() interface{}) (actual interface{}, loaded bool) function:

LoadOrStoreLazy("foo", func() interface{} {
    return heavystuff.New("foo")  
})

This is critical for cases when it's expensive to create a new value.

[bcmills]

@akrylysov What would the semantics of LoadOrStoreLazy be?

If it reserves the slot for the first caller, that's easy enough to do on the caller side with a little extra indirection:

func lazyLoad(m *sync.Map, key interface{}, f func() interface{}) interface{} {
  if g, ok := m.Load(key); ok {
    return g.(func() interface{})()
  }

  var (
    once sync.Once
    x interface{}
  )
  g, _ := m.LoadOrStore(key, func() interface{} {
    once.Do(func() {
      x = f()
      m.Store(key, func() interface{} { return x })
    })
    return x
  })
  return g.(func() interface{})()
})

If it does not reserve the slot, then you just need an extra Load:

x, ok := m.Load(key)
if ok {
  return x
}
x, _ = m.LoadOrStore(key, heavystuff.New(key))
return x

[akrylysov]

@bcmills it should reserve the slot. My idea is that the factory function (the second argument of LoadOrStoreLazy) should be called only when map is missing the key. So basically m.dirty[key] = f() instead of m.dirty[key] = value in https://github.com/golang/sync/blob/master/syncmap/map.go#L119.

[bcmills]

That seems worse than the caller-side lazyLoad function I sketched above. It cuts out a little bit of indirection for clean Load calls, but at the cost of locking the map for all of the other keys that miss while the callback executes.

[bcmills]

I have a couple more use-cases which, unlike the examples I've found in the standard library so far, are not "append-only" with respect to the set of keys in the map.

They fall into the general category of "handles":

1. Maps from integer handle to Go pointer, so that the handles can be passed to C functions or C callers and stored without violating the cgo pointer-passing rules.
2. Maps from session-ID or user-ID to per-session or per-user data in long-lived servers without long-lived connections.

[gopherbot]

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

[josharian]

Is the plan to try to move this to the standard library for 1.9, or wait for 1.10 (or beyond)?

[bcmills]

I'm still planning to try to get it in for 1.9. (I need to address some code review comments — got bogged down with internal work.)

[gopherbot]

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

[gopherbot]

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

[gopherbot]

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

[gopherbot]

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

[gopherbot]

CL https://golang.org/cl/41990 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: https://github.com/golang/go/issues/15292