[go] runtime: on map update, don't overwrite key if we don't need to.

[Keith Randall (Gerrit)]

Reviewers: Russ Cox

Keith Randall uploaded a change:
https://go-review.googlesource.com/10843

runtime: on map update, don't overwrite key if we don't need to.

Keep track of which types of keys need an update and which don't.

Strings need an update because the new key might pin a smaller backing
store.
Floats need an update because it might be +0/-0.
Interfaces need an update because they may contain strings or floats.

Fixes #11088

Change-Id: I9ade53c1dfb3c1a2870d68d07201bc8128e9f217
---
M src/cmd/compile/internal/gc/reflect.go
M src/reflect/type.go
M src/runtime/hashmap.go
M src/runtime/type.go
4 files changed, 83 insertions(+), 3 deletions(-)



diff --git a/src/cmd/compile/internal/gc/reflect.go
b/src/cmd/compile/internal/gc/reflect.go
index 6c0962f..f687cf8 100644
--- a/src/cmd/compile/internal/gc/reflect.go
+++ b/src/cmd/compile/internal/gc/reflect.go
@@ -930,7 +930,7 @@
}

/*
- * Returns 1 if t has a reflexive equality operator.
+ * Returns true if t has a reflexive equality operator.
* That is, if x==x for all x of type t.
*/
func isreflexive(t *Type) bool {
@@ -973,12 +973,62 @@
return false
}
}
-
return true

default:
Fatal("bad type for map key: %v", t)
return false
+ }
+}
+
+/*
+ * Returns true if map updates with t as a key need the key to be updated.
+ */
+func needkeyupdate(t *Type) bool {
+ switch t.Etype {
+ case TBOOL,
+ TINT,
+ TUINT,
+ TINT8,
+ TUINT8,
+ TINT16,
+ TUINT16,
+ TINT32,
+ TUINT32,
+ TINT64,
+ TUINT64,
+ TUINTPTR,
+ TPTR32,
+ TPTR64,
+ TUNSAFEPTR,
+ TCHAN:
+ return false
+
+ case TFLOAT32, // floats can be +0/-0
+ TFLOAT64,
+ TCOMPLEX64,
+ TCOMPLEX128,
+ TINTER,
+ TSTRING: // strings might have smaller backing stores
+ return true
+
+ case TARRAY:
+ if Isslice(t) {
+ Fatal("slice can't be a map key: %v", t)
+ }
+ return needkeyupdate(t.Type)
+
+ case TSTRUCT:
+ for t1 := t.Type; t1 != nil; t1 = t1.Down {
+ if needkeyupdate(t1.Type) {
+ return true
+ }
+ }
+ return false
+
+ default:
+ Fatal("bad type for map key: %v", t)
+ return true
}
}

@@ -1162,6 +1212,7 @@

ot = duint16(s, ot, uint16(mapbucket(t).Width))
ot = duint8(s, ot, uint8(obj.Bool2int(isreflexive(t.Down))))
+ ot = duint8(s, ot, uint8(obj.Bool2int(needkeyupdate(t.Down))))

case TPTR32, TPTR64:
if t.Type.Etype == TANY {
diff --git a/src/reflect/type.go b/src/reflect/type.go
index e55a0d1..5c19149 100644
--- a/src/reflect/type.go
+++ b/src/reflect/type.go
@@ -348,6 +348,7 @@
indirectvalue uint8 // store ptr to value instead of value itself
bucketsize uint16 // size of bucket
reflexivekey bool // true if k==k for all keys
+ needkeyupdate bool // true if we need to update key on an overwrite
}

// ptrType represents a pointer type.
@@ -1526,6 +1527,7 @@
}
mt.bucketsize = uint16(mt.bucket.size)
mt.reflexivekey = isReflexive(ktyp)
+ mt.needkeyupdate = needKeyUpdate(ktyp)
mt.uncommonType = nil
mt.ptrToThis = nil

@@ -1670,6 +1672,30 @@
}
}

+// needKeyUpdate reports whether map overwrites require the key to be
copied.
+func needKeyUpdate(t *rtype) bool {
+ switch t.Kind() {
+ case Bool, Int, Int8, Int16, Int32, Int64, Uint, Uint8, Uint16, Uint32,
Uint64, Uintptr, Chan, Ptr, UnsafePointer:
+ return true
+ case Float32, Float64, Complex64, Complex128, Interface, String:
+ return false
+ case Array:
+ tt := (*arrayType)(unsafe.Pointer(t))
+ return needKeyUpdate(tt.elem)
+ case Struct:
+ tt := (*structType)(unsafe.Pointer(t))
+ for _, f := range tt.fields {
+ if needKeyUpdate(f.typ) {
+ return true
+ }
+ }
+ return false
+ default:
+ // Func, Map, Slice, Invalid
+ panic("needKeyUpdate called on non-key type " + t.String())
+ }
+}
+
// Make sure these routines stay in sync with ../../runtime/hashmap.go!
// These types exist only for GC, so we only fill out GC relevant info.
// Currently, that's just size and the GC program. We also fill in string
diff --git a/src/runtime/hashmap.go b/src/runtime/hashmap.go
index b199330..e5bdbbb 100644
--- a/src/runtime/hashmap.go
+++ b/src/runtime/hashmap.go
@@ -460,7 +460,9 @@
continue
}
// already have a mapping for key. Update it.
- typedmemmove(t.key, k2, key)
+ if t.needkeyupdate {
+ typedmemmove(t.key, k2, key)
+ }
v := add(unsafe.Pointer(b),
dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
v2 := v
if t.indirectvalue {
diff --git a/src/runtime/type.go b/src/runtime/type.go
index 45bdac8..98446f6 100644
--- a/src/runtime/type.go
+++ b/src/runtime/type.go
@@ -68,6 +68,7 @@
indirectvalue bool // store ptr to value instead of value itself
bucketsize uint16 // size of bucket
reflexivekey bool // true if k==k for all keys
+ needkeyupdate bool // true if we need to update key on an overwrite
}

type chantype struct {

--
https://go-review.googlesource.com/10843
Gerrit-Reviewer: Russ Cox <r...@golang.org>

[Russ Cox (Gerrit)]

Russ Cox has posted comments on this change.

runtime: on map update, don't overwrite key if we don't need to.

Patch Set 1:

The case I was worried about is not keeping the original string pointer. If
we're not going to keep the original string pointer, I don't see much
problem with just overwriting the key always like we used to. I'm not sure
we need to do anything at all here.

It would be fine to do this if you think it's important, but unless we know
of a compelling reason we should probably wait until Go 1.6.

--
https://go-review.googlesource.com/10843
Gerrit-Reviewer: Russ Cox <r...@golang.org>

Gerrit-HasComments: No

[Keith Randall (Gerrit)]

Keith Randall has posted comments on this change.

runtime: on map update, don't overwrite key if we don't need to.

Patch Set 1:

I'm happy to wait.

--
https://go-review.googlesource.com/10843
Gerrit-Reviewer: Keith Randall <k...@golang.org>

[Russ Cox (Gerrit)]

Russ Cox has posted comments on this change.

runtime: on map update, don't overwrite key if we don't need to.

Patch Set 1:

R=close
(reply after Go 1.5 to un-close)

[Russ Cox (Gerrit)]

Russ Cox has posted comments on this change.

runtime: on map update, don't overwrite key if we don't need to.

Patch Set 1:

actually, reupload

[Keith Randall (Gerrit)]

Keith Randall has posted comments on this change.

runtime: on map update, don't overwrite key if we don't need to.

Patch Set 1:

(2 comments)

https://go-review.googlesource.com/#/c/10843/1/src/reflect/type.go
File src/reflect/type.go:

PS1, Line 1679: true
return false


PS1, Line 1681: false
return true

--
https://go-review.googlesource.com/10843
Gerrit-Reviewer: Keith Randall <k...@golang.org>
Gerrit-Reviewer: Russ Cox <r...@golang.org>

Gerrit-HasComments: Yes

[Keith Randall (Gerrit)]

Reviewers: Russ Cox

Keith Randall uploaded a new patch set:

https://go-review.googlesource.com/10843

runtime: on map update, don't overwrite key if we don't need to.

Keep track of which types of keys need an update and which don't.

Strings need an update because the new key might pin a smaller backing
store.
Floats need an update because it might be +0/-0.
Interfaces need an update because they may contain strings or floats.

Fixes #11088

Change-Id: I9ade53c1dfb3c1a2870d68d07201bc8128e9f217
---
M src/cmd/compile/internal/gc/reflect.go
M src/reflect/type.go
M src/runtime/hashmap.go
M src/runtime/type.go
4 files changed, 83 insertions(+), 3 deletions(-)

[Brad Fitzpatrick (Gerrit)]

Brad Fitzpatrick has posted comments on this change.

runtime: on map update, don't overwrite key if we don't need to.

Patch Set 2: Code-Review+2

(4 comments)

https://go-review.googlesource.com/#/c/10843/2/src/cmd/compile/internal/gc/reflect.go
File src/cmd/compile/internal/gc/reflect.go:

Line 947: * Returns true if t has a reflexive equality operator.
isreflexive reports whether t has a ....


Line 998: /*
//

... and be more go like? /* is pretty rare.


Line 999: * Returns true if map updates with t as a key need the key to be
updated.
reports whether

Actually--- this is the classic case that Rob normally complained about
regarding this wording difference. His argument was "Returns trues if"
meant "So, in some cases it doesn't return?". And indeed, in this function
sometimes it returns true, sometimes it returns false, and sometimes it
doesn't return at all. (well, I guess Fatalf doesn't actually terminate
the goroutine?)


https://go-review.googlesource.com/#/c/10843/2/src/reflect/type.go
File src/reflect/type.go:

Line 1679: case Float32, Float64, Complex64, Complex128, Interface, String:
this could use a comment after this line to rationalize why.


--
https://go-review.googlesource.com/10843
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

Gerrit-Reviewer: Keith Randall <k...@golang.org>
Gerrit-Reviewer: Russ Cox <r...@golang.org>

Gerrit-HasComments: Yes

[Keith Randall (Gerrit)]

Reviewers: Brad Fitzpatrick

Keith Randall uploaded a new patch set:

https://go-review.googlesource.com/10843

runtime: on map update, don't overwrite key if we don't need to.

Keep track of which types of keys need an update and which don't.

Strings need an update because the new key might pin a smaller backing
store.
Floats need an update because it might be +0/-0.
Interfaces need an update because they may contain strings or floats.

Fixes #11088

Change-Id: I9ade53c1dfb3c1a2870d68d07201bc8128e9f217
---
M src/cmd/compile/internal/gc/reflect.go
M src/reflect/type.go
M src/runtime/hashmap.go
M src/runtime/type.go

4 files changed, 86 insertions(+), 6 deletions(-)

[Keith Randall (Gerrit)]

Keith Randall has submitted this change and it was merged.

runtime: on map update, don't overwrite key if we don't need to.

Keep track of which types of keys need an update and which don't.

Strings need an update because the new key might pin a smaller backing
store.
Floats need an update because it might be +0/-0.
Interfaces need an update because they may contain strings or floats.

Fixes #11088

Change-Id: I9ade53c1dfb3c1a2870d68d07201bc8128e9f217

Reviewed-on: https://go-review.googlesource.com/10843
Reviewed-by: Brad Fitzpatrick <brad...@golang.org>

---
M src/cmd/compile/internal/gc/reflect.go
M src/reflect/type.go
M src/runtime/hashmap.go
M src/runtime/type.go

4 files changed, 86 insertions(+), 6 deletions(-)

Approvals:
Brad Fitzpatrick: Looks good to me, approved