proposal: add a math/checked package for checked arithmetic

[jimmyfrasche]

Adding checked arithmetic has been discussed much in the past across many issues (#18616 #21588 #19624 #6815).

I propose a math/checked package.

It would consist of the 30 functions {Add,Sub,Mul}{,U}{,8,16,32,64}.

These would take two values of the specified type and return a third and an appropriate carry/overflow value (a bool for Add/Sub and a fourth value for Mul with the result of the overflow). For example

func Add(a, b int) (result int, carry bool) { // ...
func MulU32(a, b uint32) (result, overflow uint32) { // ...

Div is left out since the only case to consider is when the denominator is 0, which is easy enough to handle without a library.

[ericlagergren]

Like math/bits, goal of these is for them to be intrinsified, right?

[jimmyfrasche]

Not so much a goal as it is a benefit, but, yes, they could easily be compile intrinsics and most likely would be.

[mundaym]

How about the following API style for Add/Sub:

func Add(a, b, carryin int) (result int, carryout int) { // ...

That would mean you could also use the library for wide arithmetic more cleanly (without if statements everywhere), and overflow can be detected with a zero equality check. The carry could still be a bool, but that would make it slightly less flexible.

[jimmyfrasche]

@mundaym carryin can just be two calls to Add/Sub. That's more code if you're implementing multiword arithmetic but that only has to be done once and hopefully one of #24813 or #9455 is accepted as well to cover that.

carryout is more interesting.

For the unsigned versions, it's always 0 or 1 so bool makes as much sense since the most common case is just checking "did this cause wrap around" and it's not hard to convert bool to {0,1} if needed.

For the signed versions, on most processors (afaik) if it's supported in the ALU it's going to be a single bit flag set on overflow but there's an extra implicit bit as the sign of the result (or either operand) that determines the sign of the carry.

Maybe it would be better to return {-1, 0, 1} and let anyone who's only concerned with whether there was an overflow test carry != 0. That does mean testing the sign of the result to compute the sign of the carry—can that be optimized out when it's clear that the sign isn't used?

Even if it can't, it may be worth the additional cost to avoid incorrect code because it can be easy to mess up the edge cases here and the purpose of this library is to make it easy to detect and handle the edge cases. On the other hand, are there many uses for knowing that aside from implementing multiword arithmetic?

cc @bcmills who has thought about all of this more than I have.

[bcmills]

My advice is to take a look at some concrete call sites and see what happens.

Based on my research for #19624, I suspect that a two-result form will be too awkward in practice. I'll pull an arbitrary example (from #19624 (comment)). Under the current draft of this proposal, it would read:

low, high := checked.Mul(2, cap(b.buf))
s, carry := checked.Add(low, n)
if high > 0 || carry {
  panic(ErrTooLarge)
}
newBuf = makeSlice(s)

Instead, if the target use-case really is checked arithmetic (rather than multi-precision arithmetic), I would recommend something with a receiver and an Ok() method, so that the same overflow check can be used across multiple calls:

var c checked.Int
s := c.Add(c.Mul(2, cap(b.buf)), n)
if !c.Ok() {
  panic(ErrTooLarge)
}
newBuf = makeSlice(s)

I would argue that that's still not as readable as the version in #19624 (comment), but perhaps it's still clearer than what we have to write without a checked package today.

[bcmills]

Div is left out since the only case to consider is when the denominator is 0, which is easy enough to handle without a library.

Don't forget -1. (https://play.golang.org/p/q_2Ilgid_Dt)

[jimmyfrasche]

I've been looking at other language/libraries approaches. It seems they all return bool (or equivalent), even for Mul. That makes more sense the more I think about it. If you need wide/big arithmetic, use something that does that; use this if you need to detect overflow in regular arithmetic.

@bcmills

Having them be methods simplifies the naming of the operations. Presumably that would make it harder to make them intrinsics, though. While not the primary goal, it would be a shame to lose that property/possibility. Also, if they're not to be intrinsics, there isn't as large a gain from putting this in the stdlib.

The first example you provided is more awkward than with operators but the example with methods isn't that much less awkward and these will tend to be used for rather short sequences of operations so I'm not especially worried.

That's a good point about div. It seems like there would need to be operations for that as well. If it only detects overflow and not division by 0 (causing the usual panic) it's unneeded for the unsigned variants.

[bcmills]

Having them be methods simplifies the naming of the operations. Presumably that would make it harder to make them intrinsics, though.

Methods vs. functions shouldn't have any impact on whether the operations can be intrinsics. (If it does, I'd argue that's a significant defect in the compiler. A method on a concrete type is just a function with one of its arguments moved to a distinguished location.)

And as @griesemer said (in #19624 (comment)), “We need to look at language changes not from a compiler writer's point of view, but from a programmer's productivity point of view.”

[jimmyfrasche]

If they're methods and they all only report whether there was overflow, the underlying type for each T can simply be a bool (that only ever transitions from false to true,) then your example would be

var overflow checked.Int
s := overflow.Add(overflow.Mul(2, cap(b.buf)), n)
if overflow {
  panic(ErrTooLarge)
}
newBuf = makeSlice(s)

[rsc]

To be a bit pedantic, this is not checked arithmetic. This is access to extended arithmetic results, which can then be used for any number of applications, including checking for overflow and the like.

#6815 proposed access to these extended results in the language. We closed it saying that instead of a language change, it would be much simpler to add them to math/bits. I still think that's right: they should be in math/bits, not in a second magic package.

That said, I think we're missing a clear statement of use cases, which makes it difficult to evaluate what the right API actually is. An obvious use case is to replace some assembly in math/big, but once you start looking more closely I think you'd find that the assembly is necessary for more than just access to extended results. What other use cases do you have in mind? What problem are you actually trying to solve?

[rsc]

This has a lot of overlap with potential Go 2 evolution so this is on hold for Go 2 work.

[jimmyfrasche]

@rsc As I said in #24813 (comment) I disagree that it belongs in math/bits: that's turning it into a util package.

That issue reminded me of the various proposals for handling overflow which seemed to have petered off so after rereading those I filed this one for tracking it and to flush out the specifics of the API. Most of the languages/libraries I looked at all just return true on overflow (or raise an exception) and tend to call it "checked". This would likely be insignificant for math/big.

Personally, my use cases have all revolved around int and buffers and wanting an easy way to bail with a nice error message if there's an overflow rather than panicing later when the cause of the panic isn't obvious from the stack trace or worse silently causing corruption by writing to the wrong portion of the buffer. It's possible to detect this in the language now—but it's fiddly to write, not at all clear what's going on when you read the code, and CPUs often have a flag for this and accessing that directly should be faster. (The first two points are much more important to me than the last, but an intrinsic would be nice).

[ianlancetaylor]

I think the essential points here are covered by #24813. Everything else can easily be in a third party package. Let's start there before considering it for the standard library.