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 · 8 comments
Open
Assignees
Milestone

Comments

@dgryski
Copy link
Contributor

@dgryski 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 rasky commented Apr 15, 2018

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

@gopherbot
Copy link

@gopherbot gopherbot commented Apr 15, 2018

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

@dgryski
Copy link
Contributor Author

@dgryski 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.

@mvdan mvdan added the Performance label Apr 16, 2018
@bradfitz bradfitz added the NeedsFix label Apr 16, 2018
@ianlancetaylor ianlancetaylor added this to the Unplanned milestone Apr 18, 2018
@rasky
Copy link
Member

@rasky 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

@gopherbot gopherbot commented Aug 17, 2019

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

@gopherbot
Copy link

@gopherbot gopherbot commented Sep 6, 2019

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

@gopherbot
Copy link

@gopherbot gopherbot commented Sep 7, 2019

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

@zdjones
Copy link
Contributor

@zdjones 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.

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
7 participants
You can’t perform that action at this time.