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: BCE optimizes less for string than slice #27585

Open
go101 opened this issue Sep 9, 2018 · 3 comments
Open

cmd/compile: BCE optimizes less for string than slice #27585

go101 opened this issue Sep 9, 2018 · 3 comments
Assignees
@rasky
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

@go101
Copy link

go101 commented Sep 9, 2018

Please answer these questions before submitting your issue. Thanks!

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

go version go1.11 linux/amd64

Does this issue reproduce with the latest release?

yes

What did you do?

package main

type T = string
// type T = []int

func NumSameBytes_1(x, y T) int {
	if len(x) > len(y) {
		x, y = y, x
	}
	for i := 0; i < len(x); i++ {
		if x[i] != y[i] { // y[i] needs bound check
			return i
		}
	}
	return len(x)
}

func NumSameBytes_2(x, y T) int {
	if len(x) > len(y) {
		x, y = y, x
	}
	
	y = y[:len(x)] // this line doesn't work
	for i := 0; i < len(x); i++ {
		if x[i] != y[i] { // y[i] still needs bound check (line 25)
			return i
		}
	}
	return len(x)
}

func NumSameBytes_3(x, y T) int {
	if len(x) > len(y) {
		x, y = y, x
	}
	if len(x) <= len(y) { // this line works
		for i := 0; i < len(x); i++ {
			if x[i] != y[i] { // bound check elimated for y[i]
				return i
			}
		}
	}
	return len(x)
}

func main() {}

What did you expect to see?

For T is either string or []int, the bounds check for y[i] at line 25 should be eliminated.
But this is only true for T is []int.

What did you see instead?

When T is string, the bounds check for y[i] at line 25 is still needed.

$ go build -gcflags="-d=ssa/check_bce/debug=1" main.go
# command-line-arguments
./main.go:11:15: Found IsInBounds
./main.go:23:7: Found IsSliceInBounds
./main.go:25:15: Found IsInBounds
@go101 go101 changed the title cmd/go: BCE doesn't optimize less for string than slice cmd/go: BCE optimizes less for string than slice Sep 9, 2018
@josharian josharian changed the title cmd/go: BCE optimizes less for string than slice cmd/compile: BCE optimizes less for string than slice Sep 10, 2018
@josharian
Copy link
Contributor

cc @rasky

@josharian josharian added Performance NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Sep 10, 2018
@josharian josharian added this to the Unplanned milestone Sep 10, 2018
@rasky rasky self-assigned this Sep 10, 2018
@rasky
Copy link
Member

rasky commented Sep 10, 2018

I’ll have a look

@go101
Copy link
Author

go101 commented Aug 4, 2021

New finding:

package main

type T = []int

func NumSameBytes_1(x, y T) int {
	if len(x) > len(y) {
		x, y = y, x
	}
	for i := 0; i < len(x); i++ {
		if x[i] != 
			y[i] { // Found IsInBounds
			return i
		}
	}
	return len(x)
}

func NumSameBytes_2(x, y T) int {
	if len(x) > len(y) {
		x, y = y, x
	}
	
	// a hint, works for T is either slice or string
	if len(x) > len(y) {
		panic("unreachable")
	}
	
	for i := 0; i < len(x); i++ {
		if x[i] != y[i] { // BCEed
			return i
		}
	}
	return len(x)
}

func NumSameBytes_3(x, y T) int {
	if len(x) > len(y) {
		x, y = y, x
	}
	
	y = y[:len(x)] // a hint, only works if T is slice
	for i := 0; i < len(x); i++ {
		if x[i] != y[i] {
			return i
		}
	}
	return len(x)
}

func NumSameBytes_4(x, y T) int {
	if len(x) > len(y) {
		x, y = y, x
	}
	
	_ = y[:len(x)] // a hint, only works if T is string
	for i := 0; i < len(x); i++ {
		if x[i] != y[i] {
			return i
		}
	}
	return len(x)
}

func main() {}

@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

@rasky rasky

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
4 participants
@josharian @rasky @gopherbot @go101