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: avoid unnecessary allocations for consecutive appends #44628

Open
rogpeppe opened this issue Feb 26, 2021 · 3 comments
Open

cmd/compile: avoid unnecessary allocations for consecutive appends #44628

rogpeppe opened this issue Feb 26, 2021 · 3 comments

Comments

@rogpeppe
Copy link
Contributor

@rogpeppe rogpeppe commented Feb 26, 2021

go1.16

The following function will often incur two allocations, one for each append call.
However the compiler could potentially know the length of the extra data in advance
(len(f) + 4) and hence allocate at most once.

func appendFoo(x []byte, f string) []byte {
	x = append(x, "aggf"...)
	x = append(x, f...)
	return x
}

Working around this is awkward because to do that properly requires duplication of the append capacity-growing algorithm so that the slice will grow by a multiplicative rather than a constant factor. When generics arrive, I'd love to see a function like this in the standard library (that would be useful for #14325 amongst others), but the above optimization would still be useful to avoid using that.

// Grow returns ts with its capacity grown enough to accommodate n more items.
func Grow[T any](ts []T, n int) []T

Related issues:

  • #14325 - this kind of optimization but with loops
  • #25828 - when several append calls can be fused into one (not the case here)
  • #37694 - relates specifically to arrays
@pierrec
Copy link

@pierrec pierrec commented Feb 26, 2021

I may be mistaken, but doesnt the following allow growing the capacity accordingly and is optimized to not allocate the make?

s = append(s, make([]T, n)...)

@tmthrgd
Copy link
Contributor

@tmthrgd tmthrgd commented Feb 26, 2021

I don’t think the compiler will ever be able to optimise this because each append has effects that are observable outside the function. Compare the following:

https://play.golang.org/p/WvBXW8u1SWk

https://play.golang.org/p/nfqTnI8SrnV

https://play.golang.org/p/N2dtswu2dLC

@randall77
Copy link
Contributor

@randall77 randall77 commented Feb 26, 2021

It is still possible, but tricky. What @rogpeppe is worried about is when both appends cause a grow. In that case, the intermediate growth is not observable and can be skipped. But yes, you do have to write all the appends you can to the original slice.

Nevertheless, @pierrec 's workaround should handle this. I'm not sure if specialized code in the compiler would be worth it.

@dmitshur dmitshur added this to the Backlog milestone Mar 5, 2021
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
6 participants