-
Notifications
You must be signed in to change notification settings - Fork 17.9k
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: iterators cannot be composed without incurring extra heap allocations (val + func literals) #69539
Comments
Related Issues and Documentation
(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.) |
I had hoped "cmd/compile: fix wrong esacpe analysis for rangefunc" would fix it, but it appears the composed version has the same cost in both
|
Moving the underlying iterator out of the closure seems to remove the allocations but it is still a lot slower. func (s Collection[T]) Values() iter.Seq[T] {
underlyingIter := s.underlying.All()
return func(yield func(T) bool) {
for _, v := range underlyingIter {
if !yield(v) {
return
}
}
}
}
|
The fix is about wrong analysis of escape analysis, so it won't change the inlining cost. |
Not entirely sure what's gone wrong here -- when compiled "-m", it helpfully reports that it can inline all the things with recent closure-inline-enhancing CLs applied, but it is not faster. Correction -- it is NOT inlining all the things. |
Here's another benchmark -- if nothing else, assigning to "_" in the loop body gets optimized away. I'd also rather write these as go-test benchmarks, which reduces the need to check to see if something non-standard is going on.
|
Change https://go.dev/cl/622415 mentions this issue: |
Updates #69539. Change-Id: I40885e9c23f35772f8ace645044afee0d55b70b2 Reviewed-on: https://go-review.googlesource.com/c/go/+/622415 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Robert Griesemer <gri@google.com>
@dr2chase Sorry for the non-standard benchmark — only did that so it was viewable in |
This is a dupe of #69411 -- same bug, same root cause. The inliner needs to get better at closures. |
Change https://go.dev/cl/629195 mentions this issue: |
This tweaks the inlining cost knob for closures specifically, they receive a doubled budget. The rationale for this is that closures have a lot of "crud" in their IR that will disappear after inlining, so the standard budget penalizes them unnecessarily. This is also the cause of these bugs -- looking at the code involved, these closures "should" be inlineable, therefore tweak the parameters until behavior matches expectations. It's not costly in binary size, because the only-called-from-one-site case is common (especially for rangefunc iterators). I can imagine better fixes and I am going to try to get that done, but this one is small and makes things better. Fixes #69411, #69539. Change-Id: I8a892c40323173a723799e0ddad69dcc2724a8f9 Reviewed-on: https://go-review.googlesource.com/c/go/+/629195 Reviewed-by: Keith Randall <khr@google.com> Reviewed-by: Keith Randall <khr@golang.org> Reviewed-by: Robert Griesemer <gri@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
I don't think the GitHub regex matching for fixes/closes deals with lists like that - I normally do one fixes per line. |
Go version
go 1.23 / go1.24-fc968d4 / go1.24-165bf24
Output of
go env
in your module/workspace:What did you do?
Runnable benchmark: https://go.dev/play/p/1J9H8AL2aGM
Created two types:
This simulates an actual use-case I have: an AVL tree being embedded in a graph data structure. Iterating from a higher-order type should be as performant as iterating from the foundational one.
When moving away from callback-style iteration (
avl.Each(func(key int64, val *Edge) { /* ... */ })
) to idiomatic iterators, I noticed a non-trivial performance regression. Granted, some of this iteration is in a tight-loop so maybe it isn't affecting every program, but after digging I noticed that higher-order iterators' func literals escape to the heap while the lowest-order one's do not.The benchmark link above demonstrates. I'm not sure if this is #66469, #69015, or simply related. But the first issue didn't get any traction which was before the 1.23 release.
What did you see happen?
iter.Seq
style iterator performs 0 allocations.iter.Seq
style iterator on that dispatches to the other incurs allocations — 6 in the go.dev/play example.What did you expect to see?
Equivalent performance of both.
The only current option is to duplicate iteration logic instead of composing iterators.
The text was updated successfully, but these errors were encountered: