sync: reduce (*Map).Load penalty for Stores with new keys

[bcmills]

In the Go 1.9 implementation of sync.Map, storing any new key in the map causes Load calls on all new keys to acquire a mutex until enough misses have occurred to promote the read-write map again.

That's probably fine for append-only maps (such as the sync.Map uses in the standard library), because it goes away in the steady state. However, it's problematic for use in caches, where there may be frequent Load and Store calls for keys that miss the cache.

I suspect we could substantially reduce the Load penalty by using a Bloom or HyperLogLog filter instead of a simple boolean to store the set of new keys: a Load that misses in the read-only map would still have more cache misses due to writes to the filter, but it would no longer block Store calls or contend with other Loads.

[bcmills]

(@odeke-em and @RLH both made suggestions along these lines.)

[thepudds]

For anyone following this issue, Go 1.24 has a new implementation of sync.Map (originally merged in CL 573956 as an internal HashTrieMap, with a more recent stack of CLs here).

That older CL 573956 includes the comment:

The map scales perfectly up to 24 cores for Loads, which is the maximum available parallelism on my machine.

which can be contrasted with this (from the opening comment of this issue here):

In the Go 1.9 implementation of sync.Map, storing any new key in the map causes Load calls on all new keys to acquire a mutex until enough misses have occurred to promote the read-write map again.

If people are curious about performance improvements, it could be helpful to test it out via benchmarks for their use cases, which is relatively easy via gotip:

$ go install golang.org/dl/gotip@latest
$ gotip download
$ gotip test -bench=.                    # use gotip as your go command

Some additional comments by @mknyszek in #21035 (comment) and #21035 (comment).