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: recognize rand.Intn() is bounded for BCE #28314

Open
marigonzes opened this Issue Oct 22, 2018 · 3 comments

Comments

Projects
None yet
3 participants
@marigonzes

marigonzes commented Oct 22, 2018

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

go version go1.11.1 windows/amd64

What did you do?

I implemented an array-shuffling function, using the math/rand.Intn() function.
https://play.golang.org/p/tlTHcU4StTF (reduced example)

What did you expect to see?

I expected the compiler to not generate bounds checking code.

What did you see instead?

Instead, said code was generated.

Note: Even if I change the code to https://play.golang.org/p/-65t27s9OD-, the bounds checking code is still generated (maybe a different issue?).

@randall77

This comment has been minimized.

Contributor

randall77 commented Oct 22, 2018

That's not an easy thing to do. It's not obvious from the code that Intn's return value is bounded. We could hard code the bounded result range for Intn in the compiler, I guess, but it seems like a lot of mechanism to avoid a bounds check.

There are a lot of functions in the stdlib which have bounded results that we could annotate. Which ones are worth it?

Your latter example doesn't work because the compiler doesn't know that Intn will never return a negative value. If Intn returned a negative value (and not 0 mod 10) the bounds check must fail.

@marigonzes

This comment has been minimized.

marigonzes commented Oct 22, 2018

For my case in specific, it doesn't really make a difference, because I'm not working with performance sensitive code. But I guess there are other developers that would take advantage of this extra optimization. This was the reason I opened this issue in the first place. And I believe that if this was to be done to this function in specific, other similar functions could make use of the same optimization.

Regarding my latter example, you are indeed right. My confusion came from the fact that in Python (don't know if there are other languages that work this way) a negative number mod a positive one is always a positive number, so I assumed it was the same in Go (should have tested first man_facepalming).

@randall77 randall77 added this to the Unplanned milestone Oct 22, 2018

@josharian

This comment has been minimized.

Contributor

josharian commented Oct 23, 2018

Related: #25862, #25999

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment