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 <mknyszek@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: David Chase <drchase@google.com>

1 files changed, 3 insertions, 3 deletions

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)
 	}
 }