expvar: replace RWMutex usage with sync.Map and atomics

Int and Float already used atomics.

When many goroutines on many CPUs concurrently update a StringSet or a
Map with different keys per goroutine, this change results in dramatic
steady-state speedups.

This change does add some overhead for single-CPU and ephemeral maps.
I believe that is mostly due to an increase in allocations per call
(to pack the map keys and values into interface{} values that may
escape into the heap). With better inlining and/or escape analysis,
the single-CPU penalty may decline somewhat.

There are still two RWMutexes in the package: one for the keys in the
global "vars" map, and one for the keys in individual Map variables.

Those RWMutexes could also be eliminated, but avoiding excessive
allocations when adding new keys would require care. The remaining
RWMutexes are only acquired in Do functions, which I believe are not
typically on the fast path.

updates #17973
updates #18177

name             old time/op    new time/op    delta
StringSet          65.9ns ± 8%    55.7ns ± 1%   -15.46%  (p=0.000 n=8+7)
StringSet-6         416ns ±22%     127ns ±19%   -69.37%  (p=0.000 n=8+8)
StringSet-48        309ns ± 8%      94ns ± 3%   -69.43%  (p=0.001 n=7+7)

name             old alloc/op   new alloc/op   delta
StringSet           0.00B         16.00B ± 0%     +Inf%  (p=0.000 n=8+8)
StringSet-6         0.00B         16.00B ± 0%     +Inf%  (p=0.000 n=8+8)
StringSet-48        0.00B         16.00B ± 0%     +Inf%  (p=0.000 n=8+8)

name             old allocs/op  new allocs/op  delta
StringSet            0.00           1.00 ± 0%     +Inf%  (p=0.000 n=8+8)
StringSet-6          0.00           1.00 ± 0%     +Inf%  (p=0.000 n=8+8)
StringSet-48         0.00           1.00 ± 0%     +Inf%  (p=0.000 n=8+8)

https://perf.golang.org/search?q=upload:20170427.3

name                           old time/op    new time/op    delta
IntAdd                           5.64ns ± 3%    5.58ns ± 1%      ~     (p=0.185 n=8+8)
IntAdd-6                         18.6ns ±32%    21.4ns ±21%      ~     (p=0.078 n=8+8)
IntAdd-48                        19.6ns ±13%    20.6ns ±19%      ~     (p=0.702 n=8+8)
IntSet                           5.50ns ± 1%    5.48ns ± 0%      ~     (p=0.222 n=7+8)
IntSet-6                         18.5ns ±16%    20.4ns ±30%      ~     (p=0.314 n=8+8)
IntSet-48                        19.7ns ±12%    20.4ns ±16%      ~     (p=0.522 n=8+8)
FloatAdd                         14.5ns ± 1%    14.6ns ± 2%      ~     (p=0.237 n=7+8)
FloatAdd-6                       69.9ns ±13%    68.4ns ± 7%      ~     (p=0.557 n=7+7)
FloatAdd-48                       110ns ± 9%     109ns ± 6%      ~     (p=0.667 n=8+8)
FloatSet                         7.62ns ± 3%    7.64ns ± 5%      ~     (p=0.939 n=8+8)
FloatSet-6                       20.7ns ±22%    21.0ns ±23%      ~     (p=0.959 n=8+8)
FloatSet-48                      20.4ns ±24%    20.8ns ±19%      ~     (p=0.899 n=8+8)
MapSet                           88.1ns ±15%   200.9ns ± 7%  +128.11%  (p=0.000 n=8+8)
MapSet-6                          453ns ±12%     202ns ± 8%   -55.43%  (p=0.000 n=8+8)
MapSet-48                         432ns ±12%     240ns ±15%   -44.49%  (p=0.000 n=8+8)
MapSetDifferent                   349ns ± 1%     876ns ± 2%  +151.08%  (p=0.001 n=6+7)
MapSetDifferent-6                1.74µs ±32%    0.25µs ±17%   -85.71%  (p=0.000 n=8+8)
MapSetDifferent-48               1.77µs ±10%    0.14µs ± 2%   -91.84%  (p=0.000 n=8+8)
MapSetString                     88.1ns ± 7%   205.3ns ± 5%  +132.98%  (p=0.001 n=7+7)
MapSetString-6                    438ns ±30%     205ns ± 9%   -53.15%  (p=0.000 n=8+8)
MapSetString-48                   419ns ±14%     241ns ±15%   -42.39%  (p=0.000 n=8+8)
MapAddSame                        686ns ± 9%    1010ns ± 5%   +47.41%  (p=0.000 n=8+8)
MapAddSame-6                      238ns ±10%     300ns ±11%   +26.22%  (p=0.000 n=8+8)
MapAddSame-48                     366ns ± 4%     483ns ± 3%   +32.06%  (p=0.000 n=8+8)
MapAddDifferent                  1.96µs ± 4%    3.24µs ± 6%   +65.58%  (p=0.000 n=8+8)
MapAddDifferent-6                 553ns ± 3%     948ns ± 8%   +71.43%  (p=0.000 n=7+8)
MapAddDifferent-48                548ns ± 4%    1242ns ±10%  +126.81%  (p=0.000 n=8+8)
MapAddSameSteadyState            31.5ns ± 7%    41.7ns ± 6%   +32.61%  (p=0.000 n=8+8)
MapAddSameSteadyState-6           239ns ± 7%     101ns ±30%   -57.53%  (p=0.000 n=7+8)
MapAddSameSteadyState-48          152ns ± 4%      85ns ±13%   -43.84%  (p=0.000 n=8+7)
MapAddDifferentSteadyState        151ns ± 5%     177ns ± 1%   +17.32%  (p=0.001 n=8+6)
MapAddDifferentSteadyState-6      861ns ±15%      62ns ±23%   -92.85%  (p=0.000 n=8+8)
MapAddDifferentSteadyState-48     617ns ± 2%      20ns ±14%   -96.75%  (p=0.000 n=8+8)
RealworldExpvarUsage             4.33µs ± 4%    4.48µs ± 6%      ~     (p=0.336 n=8+7)
RealworldExpvarUsage-6           2.12µs ±20%    2.28µs ±10%      ~     (p=0.228 n=8+6)
RealworldExpvarUsage-48          1.23µs ±19%    1.36µs ±16%      ~     (p=0.152 n=7+8)

name                           old alloc/op   new alloc/op   delta
IntAdd                            0.00B          0.00B           ~     (all equal)
IntAdd-6                          0.00B          0.00B           ~     (all equal)
IntAdd-48                         0.00B          0.00B           ~     (all equal)
IntSet                            0.00B          0.00B           ~     (all equal)
IntSet-6                          0.00B          0.00B           ~     (all equal)
IntSet-48                         0.00B          0.00B           ~     (all equal)
FloatAdd                          0.00B          0.00B           ~     (all equal)
FloatAdd-6                        0.00B          0.00B           ~     (all equal)
FloatAdd-48                       0.00B          0.00B           ~     (all equal)
FloatSet                          0.00B          0.00B           ~     (all equal)
FloatSet-6                        0.00B          0.00B           ~     (all equal)
FloatSet-48                       0.00B          0.00B           ~     (all equal)
MapSet                            0.00B         48.00B ± 0%     +Inf%  (p=0.000 n=8+8)
MapSet-6                          0.00B         48.00B ± 0%     +Inf%  (p=0.000 n=8+8)
MapSet-48                         0.00B         48.00B ± 0%     +Inf%  (p=0.000 n=8+8)
MapSetDifferent                   0.00B        192.00B ± 0%     +Inf%  (p=0.000 n=8+8)
MapSetDifferent-6                 0.00B        192.00B ± 0%     +Inf%  (p=0.000 n=8+8)
MapSetDifferent-48                0.00B        192.00B ± 0%     +Inf%  (p=0.000 n=8+8)
MapSetString                      0.00B         48.00B ± 0%     +Inf%  (p=0.000 n=8+8)
MapSetString-6                    0.00B         48.00B ± 0%     +Inf%  (p=0.000 n=8+8)
MapSetString-48                   0.00B         48.00B ± 0%     +Inf%  (p=0.000 n=8+8)
MapAddSame                         456B ± 0%      480B ± 0%    +5.26%  (p=0.000 n=8+8)
MapAddSame-6                       456B ± 0%      480B ± 0%    +5.26%  (p=0.000 n=8+8)
MapAddSame-48                      456B ± 0%      480B ± 0%    +5.26%  (p=0.000 n=8+8)
MapAddDifferent                    672B ± 0%     1088B ± 0%   +61.90%  (p=0.000 n=8+8)
MapAddDifferent-6                  672B ± 0%     1088B ± 0%   +61.90%  (p=0.000 n=8+8)
MapAddDifferent-48                 672B ± 0%     1088B ± 0%   +61.90%  (p=0.000 n=8+8)
MapAddSameSteadyState             0.00B          0.00B           ~     (all equal)
MapAddSameSteadyState-6           0.00B          0.00B           ~     (all equal)
MapAddSameSteadyState-48          0.00B          0.00B           ~     (all equal)
MapAddDifferentSteadyState        0.00B          0.00B           ~     (all equal)
MapAddDifferentSteadyState-6      0.00B          0.00B           ~     (all equal)
MapAddDifferentSteadyState-48     0.00B          0.00B           ~     (all equal)
RealworldExpvarUsage              0.00B          0.00B           ~     (all equal)
RealworldExpvarUsage-6            0.00B          0.00B           ~     (all equal)
RealworldExpvarUsage-48           0.00B          0.00B           ~     (all equal)

name                           old allocs/op  new allocs/op  delta
IntAdd                             0.00           0.00           ~     (all equal)
IntAdd-6                           0.00           0.00           ~     (all equal)
IntAdd-48                          0.00           0.00           ~     (all equal)
IntSet                             0.00           0.00           ~     (all equal)
IntSet-6                           0.00           0.00           ~     (all equal)
IntSet-48                          0.00           0.00           ~     (all equal)
FloatAdd                           0.00           0.00           ~     (all equal)
FloatAdd-6                         0.00           0.00           ~     (all equal)
FloatAdd-48                        0.00           0.00           ~     (all equal)
FloatSet                           0.00           0.00           ~     (all equal)
FloatSet-6                         0.00           0.00           ~     (all equal)
FloatSet-48                        0.00           0.00           ~     (all equal)
MapSet                             0.00           3.00 ± 0%     +Inf%  (p=0.000 n=8+8)
MapSet-6                           0.00           3.00 ± 0%     +Inf%  (p=0.000 n=8+8)
MapSet-48                          0.00           3.00 ± 0%     +Inf%  (p=0.000 n=8+8)
MapSetDifferent                    0.00          12.00 ± 0%     +Inf%  (p=0.000 n=8+8)
MapSetDifferent-6                  0.00          12.00 ± 0%     +Inf%  (p=0.000 n=8+8)
MapSetDifferent-48                 0.00          12.00 ± 0%     +Inf%  (p=0.000 n=8+8)
MapSetString                       0.00           3.00 ± 0%     +Inf%  (p=0.000 n=8+8)
MapSetString-6                     0.00           3.00 ± 0%     +Inf%  (p=0.000 n=8+8)
MapSetString-48                    0.00           3.00 ± 0%     +Inf%  (p=0.000 n=8+8)
MapAddSame                         6.00 ± 0%     11.00 ± 0%   +83.33%  (p=0.000 n=8+8)
MapAddSame-6                       6.00 ± 0%     11.00 ± 0%   +83.33%  (p=0.000 n=8+8)
MapAddSame-48                      6.00 ± 0%     11.00 ± 0%   +83.33%  (p=0.000 n=8+8)
MapAddDifferent                    14.0 ± 0%      31.0 ± 0%  +121.43%  (p=0.000 n=8+8)
MapAddDifferent-6                  14.0 ± 0%      31.0 ± 0%  +121.43%  (p=0.000 n=8+8)
MapAddDifferent-48                 14.0 ± 0%      31.0 ± 0%  +121.43%  (p=0.000 n=8+8)
MapAddSameSteadyState              0.00           0.00           ~     (all equal)
MapAddSameSteadyState-6            0.00           0.00           ~     (all equal)
MapAddSameSteadyState-48           0.00           0.00           ~     (all equal)
MapAddDifferentSteadyState         0.00           0.00           ~     (all equal)
MapAddDifferentSteadyState-6       0.00           0.00           ~     (all equal)
MapAddDifferentSteadyState-48      0.00           0.00           ~     (all equal)
RealworldExpvarUsage               0.00           0.00           ~     (all equal)
RealworldExpvarUsage-6             0.00           0.00           ~     (all equal)
RealworldExpvarUsage-48            0.00           0.00           ~     (all equal)

https://perf.golang.org/search?q=upload:20170427.1

Change-Id: I388b2e8a3cadb84fc1418af8acfc27338f799273
Reviewed-on: https://go-review.googlesource.com/41930
Run-TryBot: Bryan Mills <bcmills@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>

2 files changed, 63 insertions, 93 deletions

diff --git a/src/expvar/expvar.go b/src/expvar/expvar.go
index 7339fa00b7..8a777e45d8 100644
--- a/src/expvar/expvar.go
+++ b/src/expvar/expvar.go
@@ -99,9 +99,9 @@ func (v *Float) Set(value float64) {
 
 // Map is a string-to-Var map variable that satisfies the Var interface.
 type Map struct {
-	mu   sync.RWMutex
-	m    map[string]Var
-	keys []string // sorted
+	m      sync.Map // map[string]Var
+	keysMu sync.RWMutex
+	keys   []string // sorted
 }
 
 // KeyValue represents a single entry in a Map.
@@ -111,12 +111,10 @@ type KeyValue struct {
 }
 
 func (v *Map) String() string {
-	v.mu.RLock()
-	defer v.mu.RUnlock()
 	var b bytes.Buffer
 	fmt.Fprintf(&b, "{")
 	first := true
-	v.doLocked(func(kv KeyValue) {
+	v.Do(func(kv KeyValue) {
 		if !first {
 			fmt.Fprintf(&b, ", ")
 		}
@@ -127,79 +125,60 @@ func (v *Map) String() string {
 	return b.String()
 }
 
-func (v *Map) Init() *Map {
-	v.m = make(map[string]Var)
-	return v
-}
+func (v *Map) Init() *Map { return v }
 
 // updateKeys updates the sorted list of keys in v.keys.
-// must be called with v.mu held.
-func (v *Map) updateKeys() {
-	if len(v.m) == len(v.keys) {
-		// No new key.
-		return
-	}
-	v.keys = v.keys[:0]
-	for k := range v.m {
-		v.keys = append(v.keys, k)
-	}
+func (v *Map) addKey(key string) {
+	v.keysMu.Lock()
+	defer v.keysMu.Unlock()
+	v.keys = append(v.keys, key)
 	sort.Strings(v.keys)
 }
 
 func (v *Map) Get(key string) Var {
-	v.mu.RLock()
-	defer v.mu.RUnlock()
-	return v.m[key]
+	i, _ := v.m.Load(key)
+	av, _ := i.(Var)
+	return av
 }
 
 func (v *Map) Set(key string, av Var) {
-	v.mu.Lock()
-	defer v.mu.Unlock()
-	v.m[key] = av
-	v.updateKeys()
+	if _, dup := v.m.LoadOrStore(key, av); dup {
+		v.m.Store(key, av)
+	} else {
+		v.addKey(key)
+	}
 }
 
+// Add adds delta to the *Int value stored under the given map key.
 func (v *Map) Add(key string, delta int64) {
-	v.mu.RLock()
-	av, ok := v.m[key]
-	v.mu.RUnlock()
+	i, ok := v.m.Load(key)
 	if !ok {
-		// check again under the write lock
-		v.mu.Lock()
-		av, ok = v.m[key]
-		if !ok {
-			av = new(Int)
-			v.m[key] = av
-			v.updateKeys()
+		var dup bool
+		i, dup = v.m.LoadOrStore(key, new(Int))
+		if !dup {
+			v.addKey(key)
 		}
-		v.mu.Unlock()
 	}
 
 	// Add to Int; ignore otherwise.
-	if iv, ok := av.(*Int); ok {
+	if iv, ok := i.(*Int); ok {
 		iv.Add(delta)
 	}
 }
 
 // AddFloat adds delta to the *Float value stored under the given map key.
 func (v *Map) AddFloat(key string, delta float64) {
-	v.mu.RLock()
-	av, ok := v.m[key]
-	v.mu.RUnlock()
+	i, ok := v.m.Load(key)
 	if !ok {
-		// check again under the write lock
-		v.mu.Lock()
-		av, ok = v.m[key]
-		if !ok {
-			av = new(Float)
-			v.m[key] = av
-			v.updateKeys()
+		var dup bool
+		i, dup = v.m.LoadOrStore(key, new(Float))
+		if !dup {
+			v.addKey(key)
 		}
-		v.mu.Unlock()
 	}
 
 	// Add to Float; ignore otherwise.
-	if iv, ok := av.(*Float); ok {
+	if iv, ok := i.(*Float); ok {
 		iv.Add(delta)
 	}
 }
@@ -208,45 +187,34 @@ func (v *Map) AddFloat(key string, delta float64) {
 // The map is locked during the iteration,
 // but existing entries may be concurrently updated.
 func (v *Map) Do(f func(KeyValue)) {
-	v.mu.RLock()
-	defer v.mu.RUnlock()
-	v.doLocked(f)
-}
-
-// doLocked calls f for each entry in the map.
-// v.mu must be held for reads.
-func (v *Map) doLocked(f func(KeyValue)) {
+	v.keysMu.RLock()
+	defer v.keysMu.RUnlock()
 	for _, k := range v.keys {
-		f(KeyValue{k, v.m[k]})
+		i, _ := v.m.Load(k)
+		f(KeyValue{k, i.(Var)})
 	}
 }
 
 // String is a string variable, and satisfies the Var interface.
 type String struct {
-	mu sync.RWMutex
-	s  string
+	s atomic.Value // string
 }
 
 func (v *String) Value() string {
-	v.mu.RLock()
-	defer v.mu.RUnlock()
-	return v.s
+	p, _ := v.s.Load().(string)
+	return p
 }
 
 // String implements the Val interface. To get the unquoted string
 // use Value.
 func (v *String) String() string {
-	v.mu.RLock()
-	s := v.s
-	v.mu.RUnlock()
+	s := v.Value()
 	b, _ := json.Marshal(s)
 	return string(b)
 }
 
 func (v *String) Set(value string) {
-	v.mu.Lock()
-	defer v.mu.Unlock()
-	v.s = value
+	v.s.Store(value)
 }
 
 // Func implements Var by calling the function
@@ -264,21 +232,20 @@ func (f Func) String() string {
 
 // All published variables.
 var (
-	mutex   sync.RWMutex
-	vars    = make(map[string]Var)
-	varKeys []string // sorted
+	vars      sync.Map // map[string]Var
+	varKeysMu sync.RWMutex
+	varKeys   []string // sorted
 )
 
 // Publish declares a named exported variable. This should be called from a
 // package's init function when it creates its Vars. If the name is already
 // registered then this will log.Panic.
 func Publish(name string, v Var) {
-	mutex.Lock()
-	defer mutex.Unlock()
-	if _, existing := vars[name]; existing {
+	if _, dup := vars.LoadOrStore(name, v); dup {
 		log.Panicln("Reuse of exported var name:", name)
 	}
-	vars[name] = v
+	varKeysMu.Lock()
+	defer varKeysMu.Unlock()
 	varKeys = append(varKeys, name)
 	sort.Strings(varKeys)
 }
@@ -286,9 +253,9 @@ func Publish(name string, v Var) {
 // Get retrieves a named exported variable. It returns nil if the name has
 // not been registered.
 func Get(name string) Var {
-	mutex.RLock()
-	defer mutex.RUnlock()
-	return vars[name]
+	i, _ := vars.Load(name)
+	v, _ := i.(Var)
+	return v
 }
 
 // Convenience functions for creating new exported variables.
@@ -321,10 +288,11 @@ func NewString(name string) *String {
 // The global variable map is locked during the iteration,
 // but existing entries may be concurrently updated.
 func Do(f func(KeyValue)) {
-	mutex.RLock()
-	defer mutex.RUnlock()
+	varKeysMu.RLock()
+	defer varKeysMu.RUnlock()
 	for _, k := range varKeys {
-		f(KeyValue{k, vars[k]})
+		val, _ := vars.Load(k)
+		f(KeyValue{k, val.(Var)})
 	}
 }
 
diff --git a/src/expvar/expvar_test.go b/src/expvar/expvar_test.go
index 7ee66845cd..7014063d4f 100644
--- a/src/expvar/expvar_test.go
+++ b/src/expvar/expvar_test.go
@@ -21,9 +21,11 @@ import (
 // RemoveAll removes all exported variables.
 // This is for tests only.
 func RemoveAll() {
-	mutex.Lock()
-	defer mutex.Unlock()
-	vars = make(map[string]Var)
+	varKeysMu.Lock()
+	defer varKeysMu.Unlock()
+	for _, k := range varKeys {
+		vars.Delete(k)
+	}
 	varKeys = nil
 }
 
@@ -130,22 +132,22 @@ func BenchmarkFloatSet(b *testing.B) {
 func TestString(t *testing.T) {
 	RemoveAll()
 	name := NewString("my-name")
-	if name.Value() != "" {
-		t.Errorf("name.Value() = %q, want \"\"", name.s)
+	if s := name.Value(); s != "" {
+		t.Errorf(`NewString("my-name").Value() = %q, want ""`, s)
 	}
 
 	name.Set("Mike")
 	if s, want := name.String(), `"Mike"`; s != want {
-		t.Errorf("from %q, name.String() = %q, want %q", name.s, s, want)
+		t.Errorf(`after name.Set("Mike"), name.String() = %q, want %q`, s, want)
 	}
 	if s, want := name.Value(), "Mike"; s != want {
-		t.Errorf("from %q, name.Value() = %q, want %q", name.s, s, want)
+		t.Errorf(`after name.Set("Mike"), name.Value() = %q, want %q`, s, want)
 	}
 
 	// Make sure we produce safe JSON output.
-	name.Set(`<`)
+	name.Set("<")
 	if s, want := name.String(), "\"\\u003c\""; s != want {
-		t.Errorf("from %q, name.String() = %q, want %q", name.s, s, want)
+		t.Errorf(`after name.Set("<"), name.String() = %q, want %q`, s, want)
 	}
 }