Skip to content

runtime: map assignment copies key every time #11088

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
rsc opened this issue Jun 5, 2015 · 9 comments
Closed

runtime: map assignment copies key every time #11088

rsc opened this issue Jun 5, 2015 · 9 comments
Milestone

Comments

@rsc
Copy link
Contributor

rsc commented Jun 5, 2015

While debugging another issue, Austin and I discovered that when m[k] already exists,

m[k] = v

still copies k into the map entry as the new value for key.

There is no semantic problem here, but if k is a string, this means that the
old pointer is evicted and k is recorded in its place.

I believe that some users expect that only the first assignment
using a string map key captures the string. But what happens
is that every assignment captures the string (and releases the
previously captured string).

There is a also a minor expense in memmove and write barriers
but that is not very important compared to the string capture.

This seems suboptimal. Why is it this way?

@rsc rsc added this to the Go1.5 milestone Jun 5, 2015
@randall77
Copy link
Contributor

It is this way because if you do:
m[+0.0] = ...
m[-0.0] = ...

We want the resulting map to have the -0.0 key, not the +0.0 key. We could avoid this situation in most cases by not doing the copy if the key type is "well-behaved" (the type's equality is byte-by-byte equality).

@mdempsky
Copy link
Contributor

mdempsky commented Jun 5, 2015

Is there a rationale for why it's desirable to replace the +0.0 key with -0.0 in that case?

For what it's worth, I just tested C++, Python, and Java, and their standard map types all seem to prefer preserving preexisting key values (including for the -0.0 and +0.0 case, except for Java because its boxed Double type treats -0.0 and +0.0 as unequal).

@randall77
Copy link
Contributor

I don't think it is in the spec, so we could possibly change the behavior. It seemed to be the least surprising behavior at the time. Last assignment wins.

In Russ' example, suppose you had a map from strings to something. Suppose the strings were small but potentially keeping large buffers live. You could do:

for k, v := range m {
    m[string([]byte(k))] = v
}

To allocate only the backing store required for the existing strings. If the behavior was the other way around (first write wins) there's no way to fix the map. You'd have to allocate a new map.

@mdempsky
Copy link
Contributor

mdempsky commented Jun 5, 2015

Hm, I was going to suggest you could do

for k, v := range m {
    k = string([]byte(k))
    delete(m, k)
    m[k] = v
}

but rereading the Go spec's wording about map iteration, that doesn't seem guaranteed to avoid redundant work or even to terminate. :-/

@rsc
Copy link
Contributor Author

rsc commented Jun 8, 2015

Thanks, Keith. I had forgotten about the -0/+0 case. That's definitely the reason.

I thought for a little while about having a bit in the type that says whether it contains any floats, and do the assignment only then, but it seems not worth it, at least not until someone comes up with a non-hypothetical problem.

@rsc rsc closed this as completed Jun 8, 2015
@randall77
Copy link
Contributor

We already have that bit, it is called reflexivekey (in runtime.maptype). It's used to recognize that NaN stuff will never happen, but could also be used to recognize that +0/-0 stuff will never happen. It wouldn't be hard to avoid the copy in that case.

@bradfitz bradfitz modified the milestones: Go1.6, Go1.5 Jun 8, 2015
@bradfitz bradfitz reopened this Jun 8, 2015
@gopherbot
Copy link
Contributor

CL https://golang.org/cl/10843 mentions this issue.

@tilinna
Copy link

tilinna commented Jun 24, 2015

Just wondering if the case Bool, .. should return false and the case Float, .. return true in https://go-review.googlesource.com/#/c/10843/1/src/reflect/type.go 's needKeyUpdate?

@randall77
Copy link
Contributor

You are right, the return values are wrong. I'll fix it.

@golang golang locked and limited conversation to collaborators Sep 8, 2016
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

6 participants