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: escape analysis reports that make() is using a non-constant size after inlining with a constant size #47524

Open
renthraysk opened this issue Aug 3, 2021 · 5 comments
Open

cmd/compile: escape analysis reports that make() is using a non-constant size after inlining with a constant size #47524

renthraysk opened this issue Aug 3, 2021 · 5 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
Unplanned

Comments

@renthraysk
Copy link

What version of Go are you using (go version)?

$ go version
go version go1.16.6 linux/amd64

Does this issue reproduce with the latest release?

What operating system and processor architecture are you using (go env)?

go env Output
$ go env

What did you do?

package main

// translate translates any byte in s between (lower, upper) to (newLower, newLower + upper - lower)
func translate(s string, cap int, lower, upper, newLower byte) string {
	// code removed
	b := append(make([]byte, 0, cap), s...)
	// code removed
	return string(b)
}

// toLower returns s with all upper case characters replaced with their lower case counterparts.
func toLower(s string, cap int) string {
	return translate(s, cap, 'A', 'Z', 'a')
}

// lookup ASCII case insensitive map lookup.
func lookup(m map[string]string, key string) (string, bool) {
	if len(key) > 32 {
		return "", false
	}
	r, ok := m[toLower(key, 32)]
	return r, ok
}

What did you expect to see?

translate() inlines into toLower() and resulting toLower() will also inline into it's caller. So in lookup() when toLower() is inlined would expect the capacity of slice created in translate() to be constant and therefore able to be reserved on the stack.

What did you see instead?

make([]byte, 0, cap) escapes to heap (non-constant size), when it is inlined into lookup().
If use a fixed capacity like make([]byte, 0, 32) in translate() the slice is always reserved on the stack.
@randall77
Copy link
Contributor

I think this is just a limitation of the constant propagation in escape analysis. Inlining introduces temporaries and we don't propagate through those temporaries.

@randall77 randall77 added this to the Unplanned milestone Aug 3, 2021
@zpavlinovic
Copy link
Contributor

Just out of curiosity, why is propagation of constants not happening in such cases?

@randall77
Copy link
Contributor

No one has implemented it.
It's a bit tricky in that phase of the compiler because you have to prove that a variable never changes value. That involves looking for other assignments to that variable, including through pointers.

@zpavlinovic
Copy link
Contributor

zpavlinovic commented Aug 4, 2021 •
edited

My understanding might be a bit off, but the constant propagation should take care of this. That is, it should not touch pointers or anything like that. It should do its job in propagating 32 to cap after inlining. Of course, if all of the temporaries are implemented as pointers, then I can see the issue.

@renthraysk
Copy link
Author

renthraysk commented Aug 5, 2021 •
edited

In a perfect implementation, the cap parameter wouldn't be required.

As after len() check in lookup() the compiler should know the possible range of len(key) is (0, 32). Then rather than need to use an explicit fixed capacity, could use make([]byte, 0, len(s)) and compiler determines that the upper limit is small enough to always be stack allocated.

Using bounds checking elimination to move smaller non escaping allocations to the stack.

@dmitshur dmitshur added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Aug 9, 2021
@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
None yet
Milestone
Unplanned
Development

No branches or pull requests
5 participants
@zpavlinovic @dmitshur @randall77 @gopherbot @renthraysk