proposal: sync: new type MapHash #76762
Description
proposal: sync: new type MapHash
Background
The sync package's Map type treats keys and values as type any, and requires that the keys are comparable. This both leaves performance on the table by frequently forcing simple value types to be boxed into an any and eschews type-safety, leading to lots of code that simply states the types of the keys and values in a comment, such as this (one of many) example from the standard library:
var listCache sync.Map // map[string]listImports, keyed by contextNameToday we have generics, so we can make uses of sync.Map (which are the common ones) much more type-safe. The current situation is especially silly since the underlying implementation of a Map has actually been type-parameterized since Go 1.23!
One reason we haven't been able to move forward with a type-parameterized sync.Map in the sync package itself is that we had no idea what to call it. Creating a new sync/v2 package was proposed as an alternative, but because only two types (Pool and Map) would actually benefit from generics at this time, we would be forced to incur all the costs of a v2 package for just those types.
Also, @bradfitz has since exported the internal implementation of sync.Map, internal/sync.HashTrieMap.
Proposal
With the standardization of the hash function, there's an opportunity to modernize the Map type and give it a new, clear name: MapHash. The existing Map can be defined in terms of it.
I propose the following API changes for the sync package.
type MapHash[K, V any, H maphash.Hasher[K]] struct{ ... }
func (*MapHash[K, V, H]) All() iter.Seq2[K, V]
func (*MapHash[K, V, H]) Clear()
func (*MapHash[K, V, H]) CompareAndDelete(key K, old V) (deleted bool)
func (*MapHash[K, V, H]) CompareAndSwap(key K, old, new V) (swapped bool)
func (*MapHash[K, V, H]) Delete(key K)
func (*MapHash[K, V, H]) Load(key K) (value V, ok bool)
func (*MapHash[K, V, H]) LoadAndDelete(key K) (value V, loaded bool)
func (*MapHash[K, V, H]) LoadOrStore(key K, value V) (result V, loaded bool)
func (*MapHash[K, V, H]) Range(yield func(key K, value V) bool) // for sync.Map
func (*MapHash[K, V, H]) Store(key K, old V)
func (*MapHash[K, V, H]) Swap(key K, new V) (previous V, loaded bool)
type Map = MapHash[any, any, maphash.ComparableHasher[any]]This API is identical to sync.Map except that it makes use of the type parameters, and adds an idiomatic iterator with an All method that returns an iter.Seq2. This method has the same synchronization guarantees as Range.
NOTE: Do not pay too close attention to the type signature. It will change to follow whatever the broader consensus is on container type signatures. For now, this proposal simply matches #69559. The core part of the proposal is the addition of a new type with a custom maphash.Hasher in the existing sync package as a way to move forward on having at type-safe concurrent map. Changes to this part may affect some of the minor details in this proposal, such as whether we replace Map with a type alias.
Rationale: Why a custom maphash.Hasher?
The use-case for a custom maphash.Hasher is admittedly niche. Most of the time a comparable key type is good enough. The downside of requiring a maphash.Hasher is that it complicates the API.
There are two reasons I propose supporting a custom hash function:
- Consistency across the standard library.
- The underlying implementation trivially supports it.
For (1), this API is intended to exist alongside #69559, which proposes a map implementation with a custom hash function.
For (2), my concern is that eliding support for custom hash functions would just encourage more unnecessary exports of the internal map implementation, precisely because it can trivially support it. This makes the choice of concurrent map even more messy and complicated in the broader ecosystem. A good quality implementation already exists in the standard library.
Alternative: Don't redefine Map
Alternatively, we don't define Map as a type alias, and instead just use the MapHash implementation under the hood. This way we don't need to add the Range method to MapHash.
One benefit of the type alias approach is that it may minimize the visibility of Map in the documentation when users go looking for a concurrent map.
Optional: Shorthand for comparable keys
A downside of MapHash is that common cases are very verbose, requiring the developer to write out maphash.ComparableHasher everywhere the type is referenced. We can make this common case much less verbose with a generic type alias, too:
type MapOf[K comparable, V any] = MapHash[K, V, maphash.ComparableHasher[K]]The MapOf name is not intended to set a precedent or a new pattern that others should follow. It's a compromise that may or may not be a better alternative to creating a new sync/v2 package.
Implementation
We would need to rework the underlying map implementation of internal/sync.HashTrieMap to use the new maphash.Hasher, but this is fairly trivial to do, since the equality and hash functions are already invoked indirectly. Then we would be able to refactor internal/sync.HashTrieMap into the implementation of sync.MapHash in the sync package and remove the internal/sync package, which would be a nice internal cleanup.
Go 1 Compatibility
This proposal only adds a new API, so it's backward compatible. Although sync.Map is redefined, it still exposes an identical API to today, with the sole addition of the All method.
Alternatives
As mentioned earlier, we could choose to pursue a sync/v2 package wholesale instead, for which a proposal already exists.
I don't feel strongly about either, but at this point the sync/v2 proposal has fallen behind a little bit (namely around the addition of maphash.Hasher), though it could be trivially updated to accommodate it.
Acknowledgements
Thank you to Cherry, David, and Russ for your initial feedback on this proposal.