Closed
Description
The problem
The following code is quite common:
type Set struct {
m map[string]struct{}
}
// Add adds key to s.
//
// False is returned if the key was already registered.
func (s *Set) Add(key string) bool {
m := s.m
if _, ok := m[key]; ok { // step 1
return false
}
m[key] = struct{}{} // step 2
return true
}The problem with this code is that the hash for the key is calculated two times here:
- The first time when reading from
s.mat the step 1. - The second time when writing to
s.mat the step 2.
The step 1 and step 2 are both executed in the common case when the key is missing in s. This means that CPU time is wasted at the step 2 on repeated calculation of the hash for the key.
The solution
It would be great from performance PoV if Go compiler could re-use the already calculated hash for the key at the step 2 above. The performance improvement increases with the size of the key.
Additional details
There is another frequently used pattern, which could benefit from this optimization:
// maxHits is the maximum number of hits, which can be tracked
const maxHits = 42
// AddHitsWithSaturation adds hits for the given key in the m, taken into account maxHits
func AddHitsWithSaturation(m map[string]int, key string, hits int) {
n := m[key]
if n >= maxHits {
return
}
n += hits
if n < maxHits {
n = maxHits
}
m[key] = n
}Another common variation of the previous function:
// AddHits adds hits for the given key in the m and returns the resulting hits
func AddHits(m map[string]int, key string, hits int) int {
m[key] += hits
return m[key]
}It would be great from the performance PoV if the hash for the key is calculated only once inside these functions.