proposal: spec: extend comma-ok expressions to + - * / arithmetic

This is a proposal for a (backward-compatible) language extension.

The notion of comma-ok expressions can be extended in a natural way to the 4 basic
arithmetic operations (+, -, *, /) such that a 2nd result value (traditionally the
"ok" value) provides the carry, borrow, overflow, and remainder value,
respectively.

Specifically (spec wording):

-----

A binary expression with one the four basic arithmetic operators may be used in an
assignment of initialization of the special form:

   z, c = x op y
   z, c := x op y
   var z, c = x op y
   var z, c T = x op y

The operator op must be one of +, -, *, or /. The value and type of z is the same as in
the single-result form. In the special form, the type of c is the same as the type of z,
and the value of c is defined as follows:

For +, -, and /, the value of c is (x op y) >> s with the operation carried out in
twice the precision of the types of the operands, and with s = operand type size in
bits. For /, the value of c is the remainder x%y.

In other words:

   for +, c is the "carry" value (0 or 1)
   for -, c is the "borrow" value (0 or -1)
   for *, c is the "overflow" value 
   for /, c is the remainder

-----

The implementation is straight-forward since these c values tend to be computed anyway:
For +, and -, the value of c corresponds to the "carry/borrow bit" usually
computed always for these operations. The carry bit simply needs to be converted and
stored (between 1 to 3 machine instructions, depending on architecture, storage
location). Division operations usually leave the remainder in a register. Only
multiplication requires double-width arithmetic, and only if c is required.

Applications:

- Code that needs to check for integer overflow can be simplified. For unsigned ints,
the c value is the desired bit.
- Numeric conversions (from integer to decimal) require both / and % on the same
operands. Providing q, r := x/y is likely to run twice as fast w/o the need for the
compiler to detect that a % operation following a / is using the same operands.
- Some of the core routines required for arbitrary precision arithmetic can be written
in a straight-forward manner in Go and should achieve similar performance as
corresponding assembly code, without the need for fancy compiler optimizations.

Concrete example: If x, y, z represent fixed-size high precision unsigned integers (n*64
bits), + could be written as follows:

   const n = 100
   var x, y, z [n]uint64

   // compute z = x + y
   var c uint64
   for i, x := range x {
            z[i], c = x + y[i] + c
   }

Without the special z, c = x + y form, analogous code written in c will be prohibitively
expensive compared to the respective assembly.

Comment 1:

Amendments:
1) This extension should only apply for integer operands.
2) If general extension (to all 4 operations) is considered too extensive, one might
consider simply permitting the special form for / .

Comment 2:

Labels changed: added go1.3maybe.

Comment 3:

Labels changed: added release-none, removed go1.3maybe.

Comment 4:

Labels changed: added repo-main.

Comment 5 by mdempsky@chromium.org:

I like the idea of an extra value to easily check for overflow conditions, but the
proposed wording seems to have at least a couple issues when extended to signed integer
arithmetic:
If x and y are both int32(-1), then (int64(-1) + int64(-1)) >> 32 evaluates to -1.  This
isn't consistent with the "for +, c is the 'carry' value (0 or 1)" text, as the value is
neither 0 nor 1.
Additionally, if x and y are both math.MaxInt32 (or both math.MinInt32), then (int64(x)
+ int64(y)) >> 32 will evaluate to 0 (or -1, respectively).  In this case, (x + y) will
wrap around, but c won't give any useful indication of that (at least when inspected in
isolation).

@dr2chase

Numeric conversions (from integer to decimal) require both / and % on the same operands. Providing q, r := x/y is likely to run twice as fast w/o the need for the compiler to detect that a % operation following a / is using the same operands.

I know that the suggestion here was to spare the compiler some work. However, I think that it would now be quite easy to write an SSA pass that recognizes code like

q := x / y
r := x % y

and substitutes a specialized op for it, and then add faster arch-specific implementations for that op. Something similar probably holds for carry, borrow, and overflow, if we pick a standard idiomatic way to express them (a la the memclear range expression).

cc the usual numeric/SSA crowd: @dr2chase @brtzsnr @randall77 @tzneal

@griesemer

@griesemer to clarify do you mean that you're marking the proposal for the language change to Go2 (in favor) but that a separate proposal for a math/checked library would be considered?

@jimmyfrasche

@jimmyfrasche I'm less and less in favor of this language change no matter Go 1 or Go 2. There's no way this is going in Go 1, so I leave it open for Go 2, to be considered as a proper proposal (others may feel differently). We have accepted the math/bits library and we are still considering extending it with some of these operations, which would be an an alternative approach.

@praetergeek

In an out-of-band discussion, @praetergeek pointed out that the typical use of a carry value from an addition is to combine it with some later (three-operand) addition: x = y + z + carry.

And it's worth noting that you can do around 2^31 additions before the carry bits overflow an int32.

So if we were to pursue this proposal further, perhaps we would want to allow strings of multiple addition or subtraction operations, with the second value representing the sum of the carries rather than a single bit. That would also help cut down on boilerplate when the feature is used: applications that are sensitive to overflow in aggregate but don't care about temporary excursions could simply string together multiple operations and check whether the carry is nonzero.

It isn't obvious to me whether that approach can be applied to expressions that mix addition or subtraction with multiplication or division.

I think we should also provide "comma, ok" or carry forms for lossy conversions. For example:

x := math.MaxInt64
y, c := int16(x)

would result in y = int16(math.MaxInt16) and c = int64(math.MaxInt64 - math.MaxInt16).

I've been thinking about this some more. Putting the carry in the second value has a nice mathematical purity to it, but in practice it seems more useful to be able to detect overflow for an expression containing multiple arithmetic operators (including multiple multiplication operators).

So I'm now in favor of using booleans instead (as described in #19624).

On 26 March 2017 at 06:02, Bryan C. Mills ***@***.***> wrote: And it's worth noting that you can do around 2^31 additions before the carry bits overflow an int32.

The alternative of using counting carry will still perform *worse* than the single-bit carry version, even -- or especially -- when amortized over a large number of operations. Addition with with a *single-bit* carry-in and carry-out has zero additional cost over a regular addition, because it's a single CPU instruction. Whereas implementing the "counting carry-out" that you're suggesting would be at least twice as expensive. The intended use-case is operand-major iteration, rather than word-within-operand-major. Multi-precision addition would look like this: a := operands[0] // or make a copy, if you might need to re-use the first operand for b := range operands[1:] { c := false for i, _ := range b { a[i], c := a[i] + b[i] + c // carry-in/carry-out, a single CPU instruction } } rather than a := operands[0] c := 0 for i, _ := range a { a[i], c = a[i] + c c = 0 for b := range operands[1:] { a[i], c += b[i] // counting carry, at least 2 CPU instructions } } In the ideal case "operands" is declared as "[][8]uint64" in which case the inner loop could be unrolled in the first version.

FWIW, given both Robert's Mar 20 comment above and the fact that now we have math/bits for similar compiler trickery, it seems like a language change is overkill for this, since these are only rarely needed. It would be much simpler to add appropriate functions to math/bits than to complicate the core language.

Based on above comments, withdrawing this proposal.

Navigation Menu

Repository navigation

proposal: spec: extend comma-ok expressions to + - * / arithmetic #6815

22 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

proposal: spec: extend comma-ok expressions to + - * / arithmetic #6815

Description

Activity

griesemer commented on Nov 21, 2013

rsc commented on Nov 27, 2013

rsc commented on Dec 4, 2013

rsc commented on Dec 4, 2013

gopherbot commented on Jun 10, 2014

josharian commented on Mar 7, 2016

22 remaining items

jimmyfrasche commented on Mar 20, 2017

griesemer commented on Mar 20, 2017

bcmills commented on Mar 25, 2017

bcmills commented on Mar 27, 2017

bcmills commented on Mar 28, 2017

praetergeek commented on Mar 28, 2017

rsc commented on Jun 17, 2017

ianlancetaylor commented on Dec 6, 2017

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions