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: bounds check elimination for if len(x) > 32 { ...; x = x[8:]; ... } #24876

Open
dgryski opened this issue Apr 15, 2018 · 9 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsFix The path to resolution is known, but the work has not been done. Performance
Milestone

Comments

@dgryski
Copy link
Contributor

dgryski commented Apr 15, 2018

( From #23354 (comment) )

In dgryski/go-metro@1308eab I got a major performance boost by changing the loop to remove the reassignments to ptr which, even though they were still within range, invalidated the bounds checks for that were valid for ptr before the assignment.

The bounds-check elimination prover should handle this common case.

@rasky
Copy link
Member

rasky commented Apr 15, 2018

This is already fixed on master by my prove CLs. I will add a specific testcase.

@gopherbot
Copy link

Change https://golang.org/cl/107355 mentions this issue: cmd/compile: add testcase for #24876

@dgryski
Copy link
Contributor Author

dgryski commented Apr 15, 2018

Sweet! Sorry I didn't check against tip. I forgot about filing this issue and Austin's comments made it sound like it was unlikely to be done anytime soon.

@bradfitz bradfitz added the NeedsFix The path to resolution is known, but the work has not been done. label Apr 16, 2018
@ianlancetaylor ianlancetaylor added this to the Unplanned milestone Apr 18, 2018
@rasky
Copy link
Member

rasky commented Sep 2, 2018

Sorry, forgot to update this issue. The specific case in dgryski/go-metro@1308eab is unfortunately not fixed yet.

IOW, this still has bound checks:

        for len(data) >= 32 {
		x += binary.BigEndian.Uint64(data)
		data = data[8:]
		x += binary.BigEndian.Uint64(data) // ERROR "Found IsInBounds$"
		data = data[8:]
		x += binary.BigEndian.Uint64(data) // ERROR "Found IsInBounds$"
		data = data[8:]
		x += binary.BigEndian.Uint64(data) // ERROR "Found IsInBounds$"
		data = data[8:]
	}

while this doesn't:

        for len(data) >= 32 {
		x += binary.BigEndian.Uint64(data[:8])
		x += binary.BigEndian.Uint64(data[8:16])
		x += binary.BigEndian.Uint64(data[16:24])
		x += binary.BigEndian.Uint64(data[24:32])
		data = data[32:]
	}

I'll notice that, even if you remove bound checks from the first snippet, you still get a lot of overhead compared to the second one because the additional 3 slice updates that require a writebarrier and computation of len/cap which are not optimized away.

gopherbot pushed a commit that referenced this issue Sep 2, 2018
This is still not fixed, the testcase reflects that there are still
a few boundchecks. Let's fix the good alternative with an explicit
test though.

Updates #24876

Change-Id: I4da35eb353e19052bd7b69ea6190a69ced8b9b3d
Reviewed-on: https://go-review.googlesource.com/107355
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
@gopherbot
Copy link

Change https://golang.org/cl/190657 mentions this issue: cmd/compile: introduce recursive, on-demand inference in prove

@gopherbot
Copy link

Change https://golang.org/cl/193839 mentions this issue: cmd/compile: make prove trace OpIsSliceInBounds:

@gopherbot
Copy link

Change https://golang.org/cl/193838 mentions this issue: cmd/compile: make prove trace OpAdd64 and OpMakeSlice:

@zdjones
Copy link
Contributor

zdjones commented Sep 13, 2019

And interesing thing I noticed when looking to fix this. Maybe it was obvious, but not to me. The bounds checks in question are not actually from the slicing operations, they are from the inlined encoding/binary methods. Within prove, the bounds check in the inlined method is actually doing some work in helping to pass information along about the length of the slice. For illustration, despite removing the bounds checks in the example for this issue, my CL above doesnt remove the IsSliceInBounds from this:

for len(data) >= 32 {
	data = data[8:]
	x = data
	data = data[8:]
	x = data
	data = data[8:]
	x = data
	data = data[8:]
	x = data
}

The next CL in the chain will get these though.

@egonelbre
Copy link
Contributor

Related #28941.

@rsc rsc unassigned rasky Jun 23, 2022
@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
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsFix The path to resolution is known, but the work has not been done. Performance
Projects
None yet
Development

No branches or pull requests

8 participants