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

math/bits: define Div to panic when hi>=y #28316

Closed
randall77 opened this issue Oct 22, 2018 · 11 comments
Closed

math/bits: define Div to panic when hi>=y #28316

randall77 opened this issue Oct 22, 2018 · 11 comments

Comments

@randall77
Copy link
Contributor

randall77 commented Oct 22, 2018

math/bits.Div currently makes the behavior undefined if hi >= y.

func Div(hi, lo, y uint) (quo, rem uint)

We should instead define it to panic in that case.

The compare-and-branch should be cheap relative to the divide itself.

This came up because the current code returns a (weird?) sentinel value in this case. When intrinsifying the code, the raw amd64 opcode will instead cause an arithmetic fault. Both behaviors fit in the "undefined" category, so they are technically spec conforming, but it's really weird for behavior to change when optimization is turned on. Since we'd need a test anyway to unify the behaviors, might as well make the test result panic.

We should resolve this one way or the other for 1.12, before the API goes public.

See #28273 #24813

@randall77 randall77 added this to the Go1.12 milestone Oct 22, 2018
@randall77
Copy link
Contributor Author

randall77 commented Oct 22, 2018

@bmkessler

@randall77
Copy link
Contributor Author

randall77 commented Oct 22, 2018

I added the proposal label, as this is kind of a mini-proposal.

@gopherbot
Copy link

gopherbot commented Oct 24, 2018

Change https://golang.org/cl/144377 mentions this issue: math/bits: define Div to panic when hi>=y

@bcmills
Copy link
Member

bcmills commented Nov 5, 2018

A panic can be recovered. Would it make sense to throw instead?
(Almost equivalently, do we expect folks using math/bits to fuzz-test their programs?)

Either way, the carry and borrow bits for Add and Sub should probably get a similar treatment.

@bcmills
Copy link
Member

bcmills commented Nov 5, 2018

We should instead define it to panic in that case.

Thinking about this some more, I strongly disagree. If we define it to panic, then we are inviting users to throw whatever garbage they want at the API and use recover to clean up the mess. It seems preferable to keep the definition of the API such that invalid inputs are unambiguously a caller-side bug.

That way, we would remain free to do something reasonable and consistent — including panic! — in the concrete implementation, but we would also remain free to take other reasonable actions — such as rejecting the program at compile-time — in cases where we have more information available.

@bmkessler
Copy link
Contributor

bmkessler commented Nov 5, 2018

For integer division, the language spec states that if the divisor is a constant, it must not be zero, but it handles division by zero at runtime with a runtime panic similar to this change for overflow.https://golang.org/ref/spec#Integer_operators

If the divisor is a constant, it must not be zero. If the divisor is zero at run time, a run-time panic occurs.

Would a preferable wording explicitly label this as a runtime behavior, leaving open the option to validate arguments at compile time as a future possibility? I'm not aware of other functions that currently have compile-time argument validation.

As for Add and Sub, a more foolproof API might actually be to use booleans for the carry since they are just a single bit. That would eliminate any possible mis-use at a cost of a slightly different API.

@bcmills
Copy link
Member

bcmills commented Nov 5, 2018

As for Add and Sub, a more foolproof API might actually be to use booleans for the carry since they are just a single bit. That would eliminate any possible mis-use at a cost of a slightly different API.

I don't think booleans for the Add and Sub carry would be an improvement, since the caller would just end up writing a boilerplate function anyway (and either do the obvious panic that we could do ourselves, or ignore the possibility of invalid inputs in their own function). Moving the misuse to the caller does not eliminate it. 🙂

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Nov 5, 2018

@bcmills Given that the language panics on division by zero, I think it is consistent for math/bits.Div to panic in a similar situation.

On a different point, I think that experience with rejecting constant division by zero at compile time has shown that that was a mistake. We should not be rejecting invalid operations at compile time. That just makes life painful for people who use build tags to control their constants, and who check for a zero divisor before executing the division.

@gopherbot
Copy link

gopherbot commented Nov 14, 2018

Change https://golang.org/cl/149517 mentions this issue: math/bits: define Div to panic when y<=hi

@bcmills
Copy link
Member

bcmills commented Nov 14, 2018

Given that the language panics on division by zero, I think it is consistent for math/bits.Div to panic in a similar situation.

That's a good point. Much as I don't want to specify control-flow behavior for something that ~always indicates a programming error, consistency with the existing control-flow behavior for division by zero is compelling.

@bcmills
Copy link
Member

bcmills commented Nov 14, 2018

On a different point, I think that experience with rejecting constant division by zero at compile time has shown that that was a mistake. We should not be rejecting invalid operations at compile time.

I gave the example of rejecting an error at compile time as an example, but perhaps it's not the best example of a useful alternative behavior.

My broader point is that panic and recover are defined as control-flow constructs, not program errors: if an expression actually does panic at run-time but the panic is recovered (or the program stalls while evaluating deferred calls), dynamic tools (like the race detector) cannot report that expression, even during testing, even though the panic is nearly always a symptom of an error in the program logic.

gopherbot pushed a commit that referenced this issue Nov 27, 2018
Explicitly check for divide-by-zero/overflow and panic with the appropriate
runtime error.  The additional checks have basically no effect on performance
since the branch is easily predicted.

name     old time/op  new time/op  delta
Div-4    53.9ns ± 1%  53.0ns ± 1%  -1.59%  (p=0.016 n=4+5)
Div32-4  17.9ns ± 0%  18.4ns ± 0%  +2.56%  (p=0.008 n=5+5)
Div64-4  53.5ns ± 0%  53.3ns ± 0%    ~     (p=0.095 n=5+5)

Updates #28316

Change-Id: I36297ee9946cbbc57fefb44d1730283b049ecf57
Reviewed-on: https://go-review.googlesource.com/c/144377
Run-TryBot: Keith Randall <khr@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
@golang golang locked and limited conversation to collaborators Nov 27, 2019
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

5 participants