If another sync.Map is added, I expect users will demand a generic version. Can this be made to work with the generics proposal? If so, maybe it could go into the proposed generics maps package as maps.Sync or some other name.

I would prefer to improve (replace the implementation of) the existing sync.Map and/or add a generic Map type than to add a second (non-generic) sync.Map type parallel to the first.

If the proposed implementation satisfies all of the existing (documented) invariants of the sync.Map API, then I think it would be fine to swap out the implementation. I do think it's important to preserve the existing behavior for the nil key, though.

We also need to be careful that Store operations concurrent with Range calls continue to work; see #46399.

I assume that this would also address #21035 and #21032?

Can you clarify what it means to say that nil values are not supported? I can think of a couple of possibilities. For example, perhaps you could show a small piece of code that works with the current sync.Map but would stop working under this proposal. Thanks.

Trying to answer all questions raised so far. Please let me know if something is still unclear. Say, I could go into more details on how atomic snapshots in readers work.

If another sync.Map is added, I expect users will demand a generic version. Can this be made to work with the generics proposal? If so, maybe it could go into the proposed generics maps package as maps.Sync or some other name.

I believe it's possible to swap current sync.Map with the new implementation without breaking the API. I left some ideas on how to approach this in the "Compatibility aspects" section above. Moreover, it would be possible to relax some things described as hints to users, like the list of use cases or the O(N) comment for Range method.

So, yes, a replacement for sync.Map seems to be the best option to me.

As for generics, I'm not familiar with the design, so can't tell if xsync.Map is a good match for them. But even if it's not, it doesn't mean that another algorithm (say, similar to CHM in Java) won't be a good fit.

We also need to be careful that Store operations concurrent with Range calls continue to work; see #46399.

Yes, both nested and concurrent Stores in Range should work fine.

I assume that this would also address #21035 and #21032?

It would certainly address #21035 since writers won't block any reader (at least in a general sense - with a lock/mutex; atomic snapshot code in readers may need to do some spins until it succeeds) and also writers that want to modify another hash table bucket.

As for #21032, I'd say that it should be also resolved since readers don't need to acquire any mutex (and, in general, do any loads into shared memory). Due to this, readers should scale linearly with the number of cores.

Can you clarify what it means to say that nil values are not supported? I can think of a couple of possibilities. For example, perhaps you could show a small piece of code that works with the current sync.Map but would stop working under this proposal. Thanks.

I just mean that in my library I raise a panic when a nil value is provided. So m.Store("foo", nil) would panic if you use xsync.Map which is not the case with sync.Map.

But as I mentioned above it's possible to work around that restriction and support nil values. This would mean an allocation of intermediate interface{} struct, but I don't think it can't be considered as something impacting users. Other than that, the number of allocations in xsync.Map's main operations is the same as in sync.Map, but with a lower allocation rate.

One more thing to mention. I didn't verify it yet, but there is a way to make scans more efficient than they are now. ATM they do an equality check for each key in scanned buckets, but that could be improved. By storing MSBs of key's hash code in tagged pointers to key/value, it would possible to skip entries known to have a different hash code. See puzpuzpuz/xsync#2

If there is a consensus to update sync.Map internals with the proposed implementation, I'm happy to open a PR and start working on an integration with the runtime (the first step would be hash code and equality calculation for interface{} keys). I'll be having some questions, so it would be nice to have someone who could answer the questions.

In the meanwhile, I'm going to resolve both nil values and grow-only resize limitations in my library.

In the meanwhile, I'm going to resolve both nil values and grow-only resize limitations in my library.

Update. Both limitations were resolved. See puzpuzpuz/xsync#6 and puzpuzpuz/xsync#11

Closing this due to lack of activity.

Those who need a generic concurrent map with extra methods such as Compute, Clear or Size, should consider using xsync library as an immediate option.