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

runtime: do map growth work on reads #19094

Open
josharian opened this Issue Feb 14, 2017 · 8 comments

Comments

Projects
None yet
6 participants
@josharian
Contributor

josharian commented Feb 14, 2017

CLs 37011 and 37012 suggest that finishing map growth can be important. If an author knows that a particular map is done growing and will henceforth be read-only, and they can spend some cycles optimizing it, it would be useful for them to be able to ask the runtime to finish any ongoing map growth.

This is kinda sort possible now:

for k, v := range m {
  m[k] = v
}

However, this is really slow, particularly for a large map. It does way more work than is necessary, and it does it very inefficiently.

The compiler could recognize this idiom and convert it into a runtime call.

Another option is to add API surface: runtime.OptimizeMap(m interface{}) or some such, which would be documented to be a slow, expensive, blocking call that makes subsequent reads more efficient.

Another idiomatic option, if copy worked on maps :) would be copy(m, m).

Other suggestions welcomed. I don't particularly like any of these, but it'd be nice to find something.

@josharian josharian added this to the Proposal milestone Feb 14, 2017

@randall77

This comment has been minimized.

Contributor

randall77 commented Feb 14, 2017

I'd rather implement do-grow-work-on-read. It's tricky, as you have to use atomic operations and whatnot, but I think it is possible and it doesn't expose any new API.

@josharian

This comment has been minimized.

Contributor

josharian commented Feb 14, 2017

That sounds great.

@josharian josharian changed the title from proposal: runtime: add a way for code to signal that maps are stable to runtime: do map growth work on reads Feb 14, 2017

@josharian

This comment has been minimized.

Contributor

josharian commented Feb 14, 2017

Changed from proposal to regular bug and retitled.

@cznic

This comment has been minimized.

Contributor

cznic commented Feb 15, 2017

I'd rather implement do-grow-work-on-read. It's tricky, as you have to use atomic operations and whatnot, ...

I falsely assumed years ago that this is the case. Since then, IIRC, in several places people were assured concurrent read operations on maps are safe. That may imply the expectation of no map mutations in such scenarios and that means no atomics/no lock with the good performance implications. If that's actually the status quo then I am slightly worried about losing this property, regardless of it had never been documented or guaranteed to such level of implementation details.

@ianlancetaylor

This comment has been minimized.

Contributor

ianlancetaylor commented Feb 15, 2017

Concurrent read operations on maps do have to work. But that doesn't mean that we can't modify the map on read. It just means that we have to do it in ways that programs can not detect. Hence the reference to atomic operations and whatnot.

For example, we wouldn't do this because of the performance implications, but it would be perfectly fine to add a mutex to a map, acquire the mutex on every read, modify the map, and release the mutex when the read was complete. That would work for all existing programs except for the changes in performance.

@cznic

This comment has been minimized.

Contributor

cznic commented Feb 15, 2017

@ianlancetaylor I'm sorry that I was apparently not able to communicate clearly, but I'm now confused because what you wrote is precisely what I was trying to say, with emphasizes on "except for the changes in performance".

@ianlancetaylor

This comment has been minimized.

Contributor

ianlancetaylor commented Feb 15, 2017

My apologies for misunderstanding. When you said "I am slightly worried about losing this property" I am not sure what property you are worried about losing.

@randall77

This comment has been minimized.

Contributor

randall77 commented Feb 15, 2017

I'm pretty sure we can get the common case for grow-on-read down to a single additional atomic load (which on x86 at least is just a regular load).
Because grow-on-read can be best-effort, even that atomic load may not be necessary. That might make the race detector unhappy, though.

@bradfitz bradfitz modified the milestones: Go1.10, Go1.9 May 24, 2017

@rsc rsc modified the milestones: Go1.10, Go1.11 Nov 22, 2017

@bradfitz bradfitz modified the milestones: Go1.11, Unplanned May 18, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment