Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmd/compile: optimize map access from multiple concurrent goroutines #19047

Closed
valyala opened this issue Feb 12, 2017 · 5 comments
Closed

cmd/compile: optimize map access from multiple concurrent goroutines #19047

valyala opened this issue Feb 12, 2017 · 5 comments

Comments

@valyala
Copy link
Contributor

valyala commented Feb 12, 2017

The following code is quite common in production systems:

func getValueByKey(k string) Value {
    mu.Lock()
    v, ok := m[k]
    if !ok {
        v = newValue()
        m[k] = v
    }
    mu.Unlock()
    return v
}

The following two optimizations may be applied by the compiler to the code:

  1. Calculate hash for k only once, since k doesn't change
  2. Move hash calculation outside the mu lock. This will improve scalability of the code on multi-CPU machines.

cc @dr2chase , @josharian .

@randall77
Copy link
Contributor

#1 is a dup of #17133. I'm intending to fix this for 1.9.

#2 is more difficult. The hash depends on the state of the map, and outside the lock it is unreliable to look at the state of the map. In addition, whether to hash at all depends on the state of the map - for small maps we don't hash at all. That also depends on the state of the map that we can't reliably detect outside the lock. Doing the hash unconditionally would be a performance regression for small maps.

I'm going to close this for now, I don't think there is anything we can do for #2.

@quentinmit
Copy link
Contributor

If the hash can change based on the state of the map, doesn't that mean this code can't optimize away either of the hash calculations? The newValue() function call might itself mutate the state of the map.

@randall77
Copy link
Contributor

@quentinmit : To be more specific, the hash depends on the initial seed chosen for each map. So in the example given the hash will always be the same before and after newValue. (Whether we need to do the hash at all can change across the call to newValue. We could probably handle that complication, it would just lead to some wasted work.)

The hard part about computing the hash outside the lock is that we can't read that seed out of the map because such a read would be racy.

@valyala
Copy link
Contributor Author

valyala commented Feb 13, 2017

The hash depends on the state of the map, and outside the lock it is unreliable to look at the state of the map. In addition, whether to hash at all depends on the state of the map - for small maps we don't hash at all. That also depends on the state of the map that we can't reliably detect outside the lock. Doing the hash unconditionally would be a performance regression for small maps.

The compiler can do 'optimistic' hash calculation outside the lock - i.e. calculate the hash only if hash seed is already set and the map size is big enough to calculate the hash. Otherwise fall back to in-place hash calculation.

Additionally, it looks like the compiler shouldn't know anything about the lock - it should just insert the 'optimistic' hash calculation to the beginning of basic block where the map is accessed by key.

@valyala
Copy link
Contributor Author

valyala commented Feb 13, 2017

Just realized the 'optimistic' hash calculation won't work if the map may be substituted during program execution:

func cleanMap() {
    mu.Lock()
    // This breaks 'optimistic' hash calculations :(
    m = make(map[string]Value)
    mu.Unlock()
}

Probably the compiler may use optimistic hash calculation only if it could prove that the map variable is never re-assigned after the initial assignment.
Or insert additional checks before each map access whether the map variable re-assigned after the optimistic hash calculation.

@valyala valyala changed the title cmd/compile: optimize map access cmd/compile: optimize map access from multiple concurrent goroutines Mar 3, 2017
@golang golang locked and limited conversation to collaborators Mar 3, 2018
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

4 participants