Skip to content
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

spec: clarify range over maps will produce every non-deleted entry avaiable when it starts #35239

Open
seebs opened this issue Oct 29, 2019 · 4 comments
Labels
Documentation NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made.
Milestone

Comments

@seebs
Copy link
Contributor

seebs commented Oct 29, 2019

What version of Go are you using (go version)?

N/A, but 1.13

Does this issue reproduce with the latest release?

Sure.

What operating system and processor architecture are you using (go env)?

N/A

What did you do?

https://play.golang.org/p/jX-Bp63JDHX

What did you expect to see?

I have no idea. This is a spec question, really. I'm writing it because I brought this up in a couple of places and ended up with a significant range of intuitions and answers from experienced and competent developers, ranging from "that will work" to "that won't work" to "that might work". I think it should perhaps be clearer whether or not this is "safe" -- could this code produce a race condition or concurrency failure?

If you have a range loop on a map, and unsynchronized writes to the map, that's a clear violation -- you can't read the map while it's being written to.

But let's say, hypothetically, that you want to range over a map slowly -- say, for a low priority background cleanup task. You don't want to run the entire thing with a lock held preventing the map from being updated. You could, of course, lock the map, grab a slice of keys, unlock it, and iterate the keys.

But why would you do something sane like that when you can do something insane?

Enter the example code: Grab a lock, start a range loop, and then inside the body of the loop, release the lock, operate on the k/v pair, and grab the lock again right before resuming at the range statement. Each evaluation of the range statement happens with the lock held. If the same lock controls modifications to the map, that's... maybe... safe?

I can't tell whether it's safe. I think it probably is, not because the spec says so, but because the spec says something that implies it, I think:

The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next. If a map entry that has not yet been reached is removed during iteration, the corresponding iteration value will not be produced. If a map entry is created during iteration, that entry may be produced during the iteration or may be skipped. The choice may vary for each entry created and from one iteration to the next. If the map is nil, the number of iterations is 0.

This suggests that map entries may be removed or created during iteration, which implies that the range statement is expected to function at least somewhat if there's creation or deletion while it's running. It's less obvious whether the creation or deletion will be reliable. Imagine for instance that we have a map with a hundred items, we iterate through 90 of them, and then we add a thousand more items, causing the entire map to get grown and rehashed at least once. Do I reliably expect to see the other 10 items that were in it before I started? I have no idea. It looks to me like the current implementation is at least trying to handle that case carefully, and indeed, I can't make it fail; I always hit every item that was present when the range statement started and hasn't been deleted yet, but don't necessarily hit any new items.

I can't tell whether I'm safe or (un?)lucky.

@randall77
Copy link
Contributor

Iteration with locking like you do is fine. The spec doesn't say anything explicit about this, but the iteration description doesn't have any weasel words about "except when synchronizing" or "deletes must happen in the same goroutine as the iterator" or anything. The iteration behavior meets the spec regardless of what the body of the loop does, or where any inserts/deletes might come from. The only exception is the general language exception "if there is a data race, any behavior is valid".

I guess the spec doesn't say "map iteration returns each key/value pair exactly once, except..." after the first sentence there. I feel like it is kind of implied - how could iteration be at all useful otherwise?

@seebs
Copy link
Contributor Author

seebs commented Oct 29, 2019

#9926 (comment) <-- someone in gopher slack pointed at this, which is possibly relevant.

(I note also in the code, there's specific code to handle the possibility that a key the iterator wants to look at has been removed and since re-added, possibly with a different key value which compares equal, such as +0.0 and -0.0.)

@ianlancetaylor
Copy link
Contributor

I'm not sure there is a bug here. Is there some way that we could make the spec clearer?

Note that in general we don't use the issue tracker for discussion. See https://golang.org/wiki/Questions. Thanks.

@ianlancetaylor ianlancetaylor added the WaitingForInfo Issue is not actionable because of missing required information, which needs to be provided. label Oct 29, 2019
@seebs
Copy link
Contributor Author

seebs commented Oct 29, 2019

Oh, hey, sorry about that, wasn't aware of the Questions thing.

I think the spec could be clearer. For instance, it appears that in fact the iterator really does reliably hit everything that was present when it started (and doesn't get deleted), even if resizes and rehashing have happened, and that's surprising to enough people I asked that it might be worth clarifying that it's guaranteed, if indeed it is. (I'm still not even entirely sure how the iterator can be sure this happens, but I can't break it, so.)

@ALTree ALTree added NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. Documentation and removed WaitingForInfo Issue is not actionable because of missing required information, which needs to be provided. labels Jan 7, 2020
@seankhliao seankhliao changed the title spec: modifying maps during (sort of) a range operation unclear spec: clarify range over maps will produce every non-deleted entry avaiable when it starts Aug 27, 2022
@seankhliao seankhliao added this to the Unplanned milestone Aug 27, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Documentation NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made.
Projects
None yet
Development

No branches or pull requests

5 participants