From aecb8faa91e2b40e3651ee93c8e70635ed367677 Mon Sep 17 00:00:00 2001 From: Michael Anthony Knyszek Date: Mon, 26 Aug 2024 14:18:26 +0000 Subject: [PATCH] sync: make HashTrieMap[any, any] the default implementation of Map This change adds a GOEXPERIMENT, synchashtriemap, which replaces the internals of a sync.Map with internal/sync.HashTrieMap[any, any]. The main purpose behind this change is improved performance. Across almost every benchmark, HashTrieMap[any, any] performs better than Map. Also, relax TestMapClearNoAllocations to allow for one allocation. Currently, the HashTrieMap allocates a new empty root node and stores it: that's the whole clear operation. At the cost of some complexity, we could allow Clear to have zero allocations by clearing the root node. The complexity comes down to allowing threads to race to install a new root node *or* creating a top-level mutex for installing a root node. But I'm not sure this is worth it. Whether Clear or some other operation takes the hit for allocating a single node almost certainly doesn't matter. And Clear is still much, much faster in the new implementation than the old, so I don't consider this a regression. Change-Id: I939aa70a0edf2e850cedbea239aaf29a11a77b79 Reviewed-on: https://go-review.googlesource.com/c/go/+/608335 Auto-Submit: Michael Knyszek LUCI-TryBot-Result: Go LUCI Reviewed-by: David Chase --- src/internal/buildcfg/exp.go | 1 + .../goexperiment/exp_synchashtriemap_off.go | 8 ++ .../goexperiment/exp_synchashtriemap_on.go | 8 ++ src/internal/goexperiment/flags.go | 3 + src/sync/hashtriemap.go | 116 ++++++++++++++++++ src/sync/map.go | 2 + src/sync/map_test.go | 6 +- 7 files changed, 141 insertions(+), 3 deletions(-) create mode 100644 src/internal/goexperiment/exp_synchashtriemap_off.go create mode 100644 src/internal/goexperiment/exp_synchashtriemap_on.go create mode 100644 src/sync/hashtriemap.go diff --git a/src/internal/buildcfg/exp.go b/src/internal/buildcfg/exp.go index c8ff974767..332c9afa57 100644 --- a/src/internal/buildcfg/exp.go +++ b/src/internal/buildcfg/exp.go @@ -80,6 +80,7 @@ func ParseGOEXPERIMENT(goos, goarch, goexp string) (*ExperimentFlags, error) { AliasTypeParams: true, SwissMap: true, SpinbitMutex: haveXchg8, + SyncHashTrieMap: true, } // Start with the statically enabled set of experiments. diff --git a/src/internal/goexperiment/exp_synchashtriemap_off.go b/src/internal/goexperiment/exp_synchashtriemap_off.go new file mode 100644 index 0000000000..cab23aac1d --- /dev/null +++ b/src/internal/goexperiment/exp_synchashtriemap_off.go @@ -0,0 +1,8 @@ +// Code generated by mkconsts.go. DO NOT EDIT. + +//go:build !goexperiment.synchashtriemap + +package goexperiment + +const SyncHashTrieMap = false +const SyncHashTrieMapInt = 0 diff --git a/src/internal/goexperiment/exp_synchashtriemap_on.go b/src/internal/goexperiment/exp_synchashtriemap_on.go new file mode 100644 index 0000000000..87433ef4de --- /dev/null +++ b/src/internal/goexperiment/exp_synchashtriemap_on.go @@ -0,0 +1,8 @@ +// Code generated by mkconsts.go. DO NOT EDIT. + +//go:build goexperiment.synchashtriemap + +package goexperiment + +const SyncHashTrieMap = true +const SyncHashTrieMapInt = 1 diff --git a/src/internal/goexperiment/flags.go b/src/internal/goexperiment/flags.go index f3c9c17d32..e654471a6a 100644 --- a/src/internal/goexperiment/flags.go +++ b/src/internal/goexperiment/flags.go @@ -122,4 +122,7 @@ type Flags struct { // SpinbitMutex enables the new "spinbit" mutex implementation on supported // platforms. See https://go.dev/issue/68578. SpinbitMutex bool + + // SyncHashTrieMap enables the HashTrieMap sync.Map implementation. + SyncHashTrieMap bool } diff --git a/src/sync/hashtriemap.go b/src/sync/hashtriemap.go new file mode 100644 index 0000000000..8df0e2b567 --- /dev/null +++ b/src/sync/hashtriemap.go @@ -0,0 +1,116 @@ +// Copyright 2024 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +//go:build goexperiment.synchashtriemap + +package sync + +import ( + isync "internal/sync" +) + +// Map is like a Go map[any]any but is safe for concurrent use +// by multiple goroutines without additional locking or coordination. +// Loads, stores, and deletes run in amortized constant time. +// +// The Map type is specialized. Most code should use a plain Go map instead, +// with separate locking or coordination, for better type safety and to make it +// easier to maintain other invariants along with the map content. +// +// The Map type is optimized for two common use cases: (1) when the entry for a given +// key is only ever written once but read many times, as in caches that only grow, +// or (2) when multiple goroutines read, write, and overwrite entries for disjoint +// sets of keys. In these two cases, use of a Map may significantly reduce lock +// contention compared to a Go map paired with a separate [Mutex] or [RWMutex]. +// +// The zero Map is empty and ready for use. A Map must not be copied after first use. +// +// In the terminology of [the Go memory model], Map arranges that a write operation +// “synchronizes before” any read operation that observes the effect of the write, where +// read and write operations are defined as follows. +// [Map.Load], [Map.LoadAndDelete], [Map.LoadOrStore], [Map.Swap], [Map.CompareAndSwap], +// and [Map.CompareAndDelete] are read operations; +// [Map.Delete], [Map.LoadAndDelete], [Map.Store], and [Map.Swap] are write operations; +// [Map.LoadOrStore] is a write operation when it returns loaded set to false; +// [Map.CompareAndSwap] is a write operation when it returns swapped set to true; +// and [Map.CompareAndDelete] is a write operation when it returns deleted set to true. +// +// [the Go memory model]: https://go.dev/ref/mem +type Map struct { + _ noCopy + + m isync.HashTrieMap[any, any] +} + +// Load returns the value stored in the map for a key, or nil if no +// value is present. +// The ok result indicates whether value was found in the map. +func (m *Map) Load(key any) (value any, ok bool) { + return m.m.Load(key) +} + +// Store sets the value for a key. +func (m *Map) Store(key, value any) { + m.m.Store(key, value) +} + +// Clear deletes all the entries, resulting in an empty Map. +func (m *Map) Clear() { + m.m.Clear() +} + +// LoadOrStore returns the existing value for the key if present. +// Otherwise, it stores and returns the given value. +// The loaded result is true if the value was loaded, false if stored. +func (m *Map) LoadOrStore(key, value any) (actual any, loaded bool) { + return m.m.LoadOrStore(key, value) +} + +// LoadAndDelete deletes the value for a key, returning the previous value if any. +// The loaded result reports whether the key was present. +func (m *Map) LoadAndDelete(key any) (value any, loaded bool) { + return m.m.LoadAndDelete(key) +} + +// Delete deletes the value for a key. +func (m *Map) Delete(key any) { + m.m.Delete(key) +} + +// Swap swaps the value for a key and returns the previous value if any. +// The loaded result reports whether the key was present. +func (m *Map) Swap(key, value any) (previous any, loaded bool) { + return m.m.Swap(key, value) +} + +// CompareAndSwap swaps the old and new values for key +// if the value stored in the map is equal to old. +// The old value must be of a comparable type. +func (m *Map) CompareAndSwap(key, old, new any) (swapped bool) { + return m.m.CompareAndSwap(key, old, new) +} + +// CompareAndDelete deletes the entry for key if its value is equal to old. +// The old value must be of a comparable type. +// +// If there is no current value for key in the map, CompareAndDelete +// returns false (even if the old value is the nil interface value). +func (m *Map) CompareAndDelete(key, old any) (deleted bool) { + return m.m.CompareAndDelete(key, old) +} + +// Range calls f sequentially for each key and value present in the map. +// If f returns false, range stops the iteration. +// +// Range does not necessarily correspond to any consistent snapshot of the Map's +// contents: no key will be visited more than once, but if the value for any key +// is stored or deleted concurrently (including by f), Range may reflect any +// mapping for that key from any point during the Range call. Range does not +// block other methods on the receiver; even f itself may call any method on m. +// +// Range may be O(N) with the number of elements in the map even if f returns +// false after a constant number of calls. +func (m *Map) Range(f func(key, value any) bool) { + m.m.Range(f) +} diff --git a/src/sync/map.go b/src/sync/map.go index 4f1395110a..25181e0c78 100644 --- a/src/sync/map.go +++ b/src/sync/map.go @@ -2,6 +2,8 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. +//go:build !goexperiment.synchashtriemap + package sync import ( diff --git a/src/sync/map_test.go b/src/sync/map_test.go index cb820e7be2..f12c43a28f 100644 --- a/src/sync/map_test.go +++ b/src/sync/map_test.go @@ -358,13 +358,13 @@ func TestConcurrentClear(t *testing.T) { }) } -func TestMapClearNoAllocations(t *testing.T) { +func TestMapClearOneAllocation(t *testing.T) { testenv.SkipIfOptimizationOff(t) var m sync.Map allocs := testing.AllocsPerRun(10, func() { m.Clear() }) - if allocs > 0 { - t.Errorf("AllocsPerRun of m.Clear = %v; want 0", allocs) + if allocs > 1 { + t.Errorf("AllocsPerRun of m.Clear = %v; want 1", allocs) } } -- 2.48.1