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

Jump to bottom

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

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

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

rogpeppe opened this issue Feb 26, 2021 · 4 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone
Backlog

Comments

@rogpeppe
Copy link
Contributor

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:
@pierrec
Copy link

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 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 commented Feb 26, 2021 •
edited

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
@dmitshur dmitshur added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Mar 5, 2021
@quasilyte
Copy link
Contributor

quasilyte commented Jan 28, 2022 •
edited

A very similar case is #25828
We can probably move the missing info from one issue into another (any of the two would suffice) and close the other one.
See #25828 (comment) for some insights.

@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Projects
Go Compiler / Runtime
Status: Triage Backlog
Milestone
Backlog
Development

No branches or pull requests
8 participants
@rogpeppe @tmthrgd @pierrec @dmitshur @mvdan @quasilyte @randall77 @gopherbot