-
Notifications
You must be signed in to change notification settings - Fork 18k
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: recognize append loop #14325
Comments
In the specific case of s := make([]T, 0, len(x)) // or just var s []T, to avoid the possibly-premature optimization
for _, v := range x {
s = append(s, v)
} IMO it's better style anyway to write s := make([]T, len(x))
for i, v := range x {
s[i] = v
} because it's about the same complexity (make is needed, but append is not) and because it's more obviously performant without the need for compiler optimizations. I think that this style preference is borne out by stdlib code as well. But I suppose your proposal still helps in cases where s was previously initialized with some other elements. By the way, I find your last code snippet confusing (why are the variable names different from the preceding snippets, and why are we appending slice indexes?) Should it instead read var s []T
for _, v := range x {
s = append(s, v)
} |
@cespare I agree, this is a most logical way to proceed if you define a fixed size array s := make([]T, len(x))
for i, v := range x {
s[i] = v
} |
There are some subtleties to when this is a safe transformation. E.g., in
the first two calls to Instead of up front calling a hypothetical runtime.ensurecapacity function, we could instead be smarter about calculating the desired length argument for runtime.growslice. Currently, for However, the Go spec makes no guarantees about how large the newly allocated slice will be. That gives us freedom to try to predict the target size better and let that influence what size slice to allocate. |
I am skeptical. What's missing from this report is any kind of motivation from performance of a real program. Even Francesc's post points out that this kind of microbenchmark is likely misleading. Any real loop is going to have possible calculations that can cause it to panic, aborting the loop early. You don't want to be left with an enormous piece of unnecessary garbage in that case. And to the extent that you might underallocate during an append loop, you shoot yourself in the foot by breaking the guarantees of append, for example when that loop is enclosed in another loop. I suspect we should not change anything here, certainly not until there are real programs to worry about instead of toys. |
Whenever I'm coding in languages like Python or Javascript, I'm much less concerned about memory allocation. With Go, I somehow switch into C-mode and see mallocs everywhere. And because I know how the append() works, it's really hard to not add that make() before every for-range -loop. I'm sure I'm not the only one having this struggle so I hope the compiler is fixed to do it automatically. Also the lint tools should be aligned with it. A recent example of litter here: 77e68ea |
The algorithm involves three nested slices of small dimensions. Some duplicated values appeared for larger numbers with no reason. The end size of any slice is not known and can't be calculated within the range of reality w/o writing more code to evaluate the size than for the algorithm itself. After reading this issue, the solution is to duplicate the variable of the range only when it must be updated.
It seems to me that the make/append/update could somehow have an easier solution as identifying such an issue is time consuming. |
Loops with appends are common in Go. And often the loops have a fixed iteration count.
cmd/compile could recognize something of the form:
And compile it as:
Likewise with
for i := 0; i < n; i++
.That would remove the need for the (often premature) optimization of:
And let people just write instead:
This would also help eliminating garbage when the number of iterations is very large. (e.g. @campoy's https://news.ycombinator.com/item?id=11098802)
/cc @randall77 @dr2chase @rsc
The text was updated successfully, but these errors were encountered: