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

cmd/compile: optimizing multiple accesses to same key in map #17133

Open
rasky opened this issue Sep 16, 2016 · 12 comments
Open

cmd/compile: optimizing multiple accesses to same key in map #17133

rasky opened this issue Sep 16, 2016 · 12 comments
Assignees
Milestone

Comments

@rasky
Copy link
Member

@rasky rasky commented Sep 16, 2016

I was reviewing some code for performance issues, and the profile pointed me to a function that was accessing the same map element multiple times like this:

data[key].Foo = 1
data[key].Bar.Baz += 4
[...]

The profile showed many calls to runtime.mapaccess1_fast32. I was wondering if it would be legal for the compiler to optimize this straight code to do only one map access, and then of course if it's worth doing it or not.

@randall77
Copy link
Contributor

@randall77 randall77 commented Sep 16, 2016

Yes, this would be awesome. I've been pondering it. I think we just want to recognize redundant calls and use the same return value from mapaccess* (the pointer to the value) again.

We probably need a mapaccess variant, "lookup key, plus allocate key->0 if not found" method.

Also good for m[x] += 5.

See #5147.

@dgryski
Copy link
Contributor

@dgryski dgryski commented Sep 16, 2016

It would be nice if this could optimize the one place I've been able to beat the built-in map with a custom implementation: lookup-and-insert-if-not-present. With strings especially as this can require hashing twice.

@bradfitz
Copy link
Contributor

@bradfitz bradfitz commented Sep 16, 2016

Damian, I think I have an existing bug open for that.

@cespare
Copy link
Contributor

@cespare cespare commented Sep 16, 2016

It's #5147 that @randall77 linked above.

@dgryski
Copy link
Contributor

@dgryski dgryski commented Sep 16, 2016

Oops, thanks. Sorry for the noise. Subscribed to the original.

@quentinmit quentinmit added this to the Go1.8Maybe milestone Oct 3, 2016
@quentinmit quentinmit added the NeedsFix label Oct 3, 2016
@quentinmit quentinmit changed the title Optimizing multiple accesses to same key in map cmd/compile: optimizing multiple accesses to same key in map Oct 3, 2016
@gopherbot
Copy link

@gopherbot gopherbot commented Oct 12, 2016

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

gopherbot pushed a commit that referenced this issue Oct 12, 2016
To compile:
  m[k] = v
instead of:
  mapassign(maptype, m, &k, &v), do
do:
  *mapassign(maptype, m, &k) = v

mapassign returns a pointer to the value slot in the map.  It is just
like mapaccess except that it will allocate a new slot if k is not
already present in the map.

This makes map accesses faster but potentially larger (codewise).

It is faster because the write into the map is done when the compiler
knows the concrete type, so it can be done with a few store
instructions instead of calling typedmemmove.  We also potentially
avoid stack temporaries to hold v.

The code can be larger when the map has pointers in its value type,
since there is a write barrier call in addition to the mapassign call.
That makes the code at the callsite a bit bigger (go binary is 0.3%
bigger).

This CL is in preparation for doing operations like m[k] += v with
only a single runtime call.  That will roughly double the speed of
such operations.

Update #17133
Update #5147

Change-Id: Ia435f032090a2ed905dac9234e693972fe8c2dc5
Reviewed-on: https://go-review.googlesource.com/30815
Run-TryBot: Keith Randall <khr@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
@rsc
Copy link
Contributor

@rsc rsc commented Oct 20, 2016

@randall77, is the second half of this going to land in Go 1.8, or should we move this issue to Go 1.9?

@randall77
Copy link
Contributor

@randall77 randall77 commented Oct 20, 2016

Not sure yet. Magic 8 ball says "looking iffy". Leave it here for now.

@rasky
Copy link
Member Author

@rasky rasky commented Aug 22, 2017

/cc @josharian as he's doing map performance things right now

@griesemer
Copy link
Contributor

@griesemer griesemer commented Nov 29, 2017

Too late for 1.10.

@griesemer griesemer modified the milestones: Go1.10, Go1.11 Nov 29, 2017
@mdempsky
Copy link
Member

@mdempsky mdempsky commented Nov 29, 2017

We probably need a mapaccess variant, "lookup key, plus allocate key->0 if not found" method.

This is what mapassign already does. I believe there's nothing blocking us from compiling m[k] += 5 into *mapassign(m, k) += 5 rather than *mapassign(m, k) = *mapaccess1(m, k) + 5.

As for recognizing repeated map lookups, could that be handled by CSE if we mapped OMAPINDEX to a high-level SSA Op and later lowered it into a runtime call?

@randall77
Copy link
Contributor

@randall77 randall77 commented Nov 27, 2018

Note: this has been implemented for the m[k] op= v form.
Punting for the generic form.

@randall77 randall77 modified the milestones: Go1.12, Go1.13 Nov 27, 2018
@randall77 randall77 modified the milestones: Go1.13, Go1.14 May 6, 2019
@rsc rsc modified the milestones: Go1.14, Backlog Oct 9, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
10 participants
You can’t perform that action at this time.