cmd/compile: optimizing multiple accesses to same key in map #17133
Comments
|
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 See #5147. |
|
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. |
|
Damian, I think I have an existing bug open for that. |
|
It's #5147 that @randall77 linked above. |
|
Oops, thanks. Sorry for the noise. Subscribed to the original. |
quentinmit
added
the
NeedsFix
quentinmit
changed the title
|
CL https://golang.org/cl/30815 mentions this issue. |
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>
|
@randall77, is the second half of this going to land in Go 1.8, or should we move this issue to Go 1.9? |
|
Not sure yet. Magic 8 ball says "looking iffy". Leave it here for now. |
|
/cc @josharian as he's doing map performance things right now |
|
Too late for 1.10. |
This is what mapassign already does. I believe there's nothing blocking us from compiling 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? |
|
Note: this has been implemented for the |
gopherbot
added
the
compiler/runtime
|
This would help the flag package, since |
This idea reminds me of "Representing Data Collections in an SSA Form", which explores (to great effect) representing container operations in a compiler SSA backend, which enables all sorts of things like detecting that two map lookups for the same key has the same result, even if there is another map insert of a different key in between. |
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:
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.The text was updated successfully, but these errors were encountered: