maps: implement faster clone

            │     base     │             experiment              │
            │    sec/op    │   sec/op     vs base                │
MapClone-24   66.802m ± 7%   3.348m ± 2%  -94.99% (p=0.000 n=10)

Fixes #70836

Change-Id: I9e192b1ee82e18f5580ff18918307042a337fdcc
Reviewed-on: https://go-review.googlesource.com/c/go/+/660175
Reviewed-by: Michael Pratt <mpratt@google.com>
Auto-Submit: Keith Randall <khr@golang.org>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Keith Randall <khr@google.com>

1 files changed, 37 insertions, 0 deletions

diff --git a/src/internal/runtime/maps/map.go b/src/internal/runtime/maps/map.go
index 62463351c7..b4db522978 100644
--- a/src/internal/runtime/maps/map.go
+++ b/src/internal/runtime/maps/map.go
@@ -770,3 +770,40 @@ func (m *Map) clearSmall(typ *abi.SwissMapType) {
 	m.used = 0
 	m.clearSeq++
 }
+
+func (m *Map) Clone(typ *abi.SwissMapType) *Map {
+	// Note: this should never be called with a nil map.
+	if m.writing != 0 {
+		fatal("concurrent map clone and map write")
+	}
+
+	// Shallow copy the Map structure.
+	m2 := new(Map)
+	*m2 = *m
+	m = m2
+
+	// We need to just deep copy the dirPtr field.
+	if m.dirPtr == nil {
+		// delayed group allocation, nothing to do.
+	} else if m.dirLen == 0 {
+		// Clone one group.
+		oldGroup := groupReference{data: m.dirPtr}
+		newGroup := groupReference{data: newGroups(typ, 1).data}
+		cloneGroup(typ, newGroup, oldGroup)
+		m.dirPtr = newGroup.data
+	} else {
+		// Clone each (different) table.
+		oldDir := unsafe.Slice((**table)(m.dirPtr), m.dirLen)
+		newDir := make([]*table, m.dirLen)
+		for i, t := range oldDir {
+			if i > 0 && t == oldDir[i-1] {
+				newDir[i] = newDir[i-1]
+				continue
+			}
+			newDir[i] = t.clone(typ)
+		}
+		m.dirPtr = unsafe.Pointer(&newDir[0])
+	}
+
+	return m
+}