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

proposal: math/big: add Int.AddInt64, Int.CmpInt64 #29951

Closed
TuomLarsen opened this issue Jan 26, 2019 · 33 comments
Closed

proposal: math/big: add Int.AddInt64, Int.CmpInt64 #29951

TuomLarsen opened this issue Jan 26, 2019 · 33 comments

Comments

@TuomLarsen
Copy link

Please consider adding big.Int methods Inc and Dec which would increase or decrease the given Int by one. It would be similar to the following code, except for the allocation:

x.Add(x, big.NewInt(1))

The motivation is that it is quite common operation and the code using it would be simpler and saving one allocation.

Alternatively, please consider AddInt(64) and SubInt(64), which would still save one allocation when knowing the increment/decrement fits a (64-bit) machine word.

Cursory look at Go source shows that the first alternative could be useful here and here, and the second one here.

Yet another alternative would be to expose intOne from int.go.

@robpike
Copy link
Contributor

robpike commented Jan 26, 2019

You can declare some package variables called one, two, etc. and use them throughout.

x.Add(x, one)

This also lets you do things like

x.Cmp(one)

@odeke-em odeke-em changed the title math/big: Int.Inc, Int.Dec proposal: math/big: add Int.Inc, Int.Dec methods Jan 27, 2019
@gopherbot gopherbot added this to the Proposal milestone Jan 27, 2019
@ericlagergren
Copy link
Contributor

ericlagergren commented Jan 29, 2019

@TuomLarsen
Copy link
Author

TuomLarsen commented Jan 30, 2019

@robpike Yes, package variables are one way of how to approach (although each package would have to possibly allocate the same big.NewInt(1)) this but the proposal is more about avoid allocations and simplifying the notation for arguments which fit machine word. Kind of like GMP _si and ui methods, of which I find that +1/-1 are the most useful.

@rsc
Copy link
Contributor

rsc commented Jan 30, 2019

Int.AddInt64 seems strictly better than Inc/Dec and matches the Int64 and SetInt64 methods. (Probably don't need SubInt64 if we have a general AddInt64. Also probably don't need AddUint64, SubUint64.)

But what else would it require adding? And? AndNot? Cmp? Div? DivMod? Mod? Mul? Or? Quo? QuoRem? Rem? Sub after all? Xor?

Just declaring a few globals with the constants you need seems to be the right answer most of the time. It's not clear that doubling the API surface is a significant enough win.

@TuomLarsen
Copy link
Author

Perhaps And, AndNot, Xor are not really necessary, Cmp can be worked around with Sign, IsInt64, Int64. So if I may summarize this gives 4 options:

  • Add every arithmetic operator (Add, Sub, Mul, QuoRem, Quo, Rem, DivMod, Div, Mod) and maybe Exp, each for Int64 and Uint64. This would be quite complete (akin to GMP) but it seems too specialized for stdlib to compensate for so many new methods.

  • Add only Add and Sub, for both Int64 and Uint64. I would argue Sub is needed even for Int64 case as the main motivation is to simplify code and to manually check whether an argument is negative or not to suitably change the sign so that it works for Add seems way too much work. And big.Int also has Sub even when it is not strictly necessary. Four methods, and really only two of which need a proper implementation as Int64 may be using Uin64 internally. The drawback is that it somehow "promises" there are more machine word methods like this, as shown by your question.

  • And only Inc and Dec. No need to worry about Uint, Int64, it does not suggest other "missing" machine word methods. Albeit more limited that any option above, perhaps it's still better than nothing.

  • Don't add anything. Clearly this is the easiest option but I believe that the above options have the potential to be generally useful.

@rsc
Copy link
Contributor

rsc commented Feb 6, 2019

Talked to @griesemer, who is inclined to start with just AddInt64 and CmpInt64 and wait for more compelling needs for any of the others. Those are clearly the most common.

@rsc rsc changed the title proposal: math/big: add Int.Inc, Int.Dec methods math/big: add Int.AddInt64, Int.CmpInt64 Feb 6, 2019
@rsc rsc modified the milestones: Proposal, Go1.13 Feb 6, 2019
@ianlancetaylor ianlancetaylor added help wanted NeedsFix The path to resolution is known, but the work has not been done. labels Feb 6, 2019
@robpike
Copy link
Contributor

robpike commented Feb 6, 2019

I would start with none of them. If you add one, you'll end up adding them all, or at best dealing with a string of proposals to add them piecemeal. Please hold the line.

@TuomLarsen
Copy link
Author

@rsc If I understood correctly, AddInt64 would need to distinguish positive and negative values as the internal implementation of big.Int uses big.nat, i.e. to add a negative number it subtracts its absolute value. If there would indeed be such mechanism, why not expose it, i.e. to add both AddUint64 and SubUint64? (With or without AddInt64?) It is similar to Int.SetInt64/Int.SetUint64, Rat.SetInt64/Rat.SetUint64, I think unsigned 64-bits are useful.

@bmkessler
Copy link
Contributor

I don't understand the need for adding these methods to the standard library. As @robpike mentioned, package level variables already handle the proposed use case very well and the big.Int API is already very large.

@mazarin1
Copy link

mazarin1 commented Mar 4, 2019

Since AddInt64(x) would need to distinguish the sign and conver x to nat we can’t save much on allocations. And may be even more harmful for memory to do so in case of making increment functions. Only convenience I see is symantics. But I think std libs should follow: KISS.
Makes it easy to test, debug and understand

Solution like

  one := big.NewInt(1)
  counter := big.NewInt(0)
   ...
   counter.Add(counter,one)
   ...

are way better approach to issue.

@odeke-em
Copy link
Member

odeke-em commented Jun 7, 2019

I shall punt to Go1.14 as the jury is still hung on whether to implement it or not, but also there hasn't been movement.

@odeke-em odeke-em modified the milestones: Go1.13, Go1.14 Jun 7, 2019
@lmittmann
Copy link

lmittmann commented Aug 7, 2019

The methods Inc and Dec seem like a nice pendant to ++ and -- for the integer primitive types. Also they would probably have some performance benefits opposed to x.Add(x, one) as less comparisons and allocations are necessary.

@griesemer
Copy link
Contributor

Despite this proposal being accepted we have not moved ahead yet. @robpike is likely correct that this will simply invite piecemeal additions of more little helpers. There may be ways to improve performance of the existing code w/o changing the API.

@rsc rsc modified the milestones: Go1.14, Backlog Oct 9, 2019
@smasher164
Copy link
Member

Since there doesn't appear to be a clear consensus on this addition to math/big, should this be moved back into active discussion, with the Accepted label removed?

@gopherbot
Copy link

Change https://golang.org/cl/334885 mentions this issue: math/big: add Int.AddInt64, Int.SubInt64 Int.CmpInt64

@vpereira01
Copy link

Since there doesn't appear to be a clear consensus on this addition to math/big, should this be moved back into active discussion, with the Accepted label removed?

Can someone clean the "Proposal-Accepted" label as it seems to not really being accepted?


Having crossed paths with z.Add(z, smallNumber) API and performance I have wondered if there was an improvement that could be made but that does not seem to be the case.

  • As bmkessler stated, big.Int API is already big so there's should be a strong case to expand it further.
  • As mazarin1 stated, allocations can not really be saved.
  • A z.AddInt64(oneInt64) breaks the big.Int API pattern of always received two values x,y and storing the result in z.
  • A z.AddInt64(xBigInt, oneInt64) expands/confuses the API and does not reduce allocations or seems to have a performance benefit.

The only improvement I see that could be done is advising in the docs not to do z.Add(x, big.NewInt(1)) but create a local variable of "oneBI" and do z.Add(x, oneBI).


If someone really needs to save allocations and/or improvement performance a fixed-precision package should be used and/or hacks which are just that, hacks. If you really need a hack check https://github.com/vpereira01/biigist/blob/master/bigintinc.go

@rsc rsc moved this from Incoming to Active in Proposals (old) May 25, 2022
@randall77
Copy link
Contributor

big.NewInt is inlined, and so the big.Int it allocates is allocated on the stack.
However, then big.NewInt calls SetInt64, which calls nat.SetUint64, which then does an allocation of a slice to hold the number itself.

Maybe we could allocate space for a single-word number in the big.Int or big.nat structure, and use that space when we can. That might get rid of the allocation.

@griesemer
Copy link
Contributor

Having space for a single-word number in a big.Int seems reasonable (it's a struct). big.nat values are []Word slices.

@randall77
Copy link
Contributor

Looks like that won't quite work, at least currently, because we haven't fixed #7921. Doing

type S struct {
	a []byte
	b [1]byte
}

func f(s *S) {
	s.a = s.b[:]
}

Causes s to escape in f. (Because some later code can read s.a and store the result in a global.)

@rsc
Copy link
Contributor

rsc commented Jun 1, 2022

If NewInt was as simple as:

func NewInt(x int64) *Int {
x := &Int{nat: []Word{Word(x)}}
return x
}

I think that would inline and not escape. So we just have to figure out how to preserve that with setting neg and negating x. Maybe sign shifting tricks are enough.

On 32-bit it might be harder because sometimes you need two words, but maybe we don't care as much if 32-bit can't be made non-allocating.

@randall77
Copy link
Contributor

That doesn't work either, unfortunately. The x.nat field might escape even though x doesn't.

@vpereira01
Copy link

That doesn't work either, unfortunately. The x.nat field might escape even though x doesn't.

I'm probably missing something but can you double check that?

My simple test seems to indicate that z.Add(y, big.NewInt(5)) already does not escape.

user@host$ go version
go version go1.18.1 linux/amd64
user@host$ cat -n bigLeak.go 
     1  package main
     2
     3  import (
     4          "fmt"
     5          "math"
     6          "math/big"
     7  )
     8
     9  func main() {
    10          z, _ := big.NewInt(0).SetString("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 16)
    11          addI64nt(z, math.MaxInt32)
    12          fmt.Printf("result %v\n", z)
    13  }
    14
    15  func addI64nt(z *big.Int, y int64) {
    16          z.Add(z, big.NewInt(y))
    17  }
user@host$ go build -gcflags -m bigLeak.go
# command-line-arguments
./bigLeak.go:16:21: inlining call to big.NewInt
./bigLeak.go:10:20: inlining call to big.NewInt
./bigLeak.go:12:12: inlining call to fmt.Printf
./bigLeak.go:15:15: leaking param content: z
./bigLeak.go:16:21: new(big.Int) does not escape <--------------
./bigLeak.go:10:20: new(big.Int) escapes to heap
./bigLeak.go:12:12: ... argument does not escape

@randall77
Copy link
Contributor

The big.Int struct itself is on the stack just fine. It's the [1]Word that is currently heap-allocated.

@rsc
Copy link
Contributor

rsc commented Jun 8, 2022

Is the [1]Word heap-allocated because of Add?
If we just did _ = big.NewInt(1) I would not expect that to heap allocate the words by itself.
The words must be escaping somewhere.

@rsc rsc changed the title math/big: add Int.AddInt64, Int.CmpInt64 proposal: math/big: add Int.AddInt64, Int.CmpInt64 Jun 8, 2022
@randall77
Copy link
Contributor

Ah yes, that's the problem. Add bottoms out to things like addVV which are in assembly. If I mark all that assembly as //go:noescape, then the [1]Word gets stack allocated.

@gopherbot
Copy link

Change https://go.dev/cl/411254 mentions this issue: math/big: make NewInt inlineable and zero allocation

@rsc
Copy link
Contributor

rsc commented Jun 15, 2022

OK, so it sounds like we don't need any new API here once this change lands.
There may be still be some optimization work to do, but that doesn't affect API and so wouldn't require proposals.
So I will move this along to likely decline.

@rsc
Copy link
Contributor

rsc commented Jun 15, 2022

Thanks @randall77!

@rsc
Copy link
Contributor

rsc commented Jun 15, 2022

Based on the discussion above, this proposal seems like a likely decline.
— rsc for the proposal review group

@rsc rsc moved this from Active to Likely Decline in Proposals (old) Jun 15, 2022
@rsc rsc moved this from Likely Decline to Declined in Proposals (old) Jun 22, 2022
@rsc
Copy link
Contributor

rsc commented Jun 22, 2022

No change in consensus, so declined.
— rsc for the proposal review group

@rsc rsc closed this as completed Jun 22, 2022
gopherbot pushed a commit that referenced this issue Aug 8, 2022
Mark the assembly routines as not escaping their arguments.

Add a special case to NewInt that, when inlined, can do all
of its allocations (a big.Int and a [1]Word) on the stack.

Update #29951

Change-Id: I9bd38c262eb97df98c0ed9874da7daac381243ea
Reviewed-on: https://go-review.googlesource.com/c/go/+/411254
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@google.com>
Run-TryBot: Keith Randall <khr@golang.org>
Reviewed-by: Robert Griesemer <gri@google.com>
@gopherbot
Copy link

Change https://go.dev/cl/422039 mentions this issue: math/big: disable TestNewIntAllocs on noopt builder

gopherbot pushed a commit that referenced this issue Aug 8, 2022
Since when that test requires inlining, which is disabled on noopt
builder.

Updates #29951

Change-Id: I9d7a0a64015a30d3bfb5ad5d806ea0955657fda3
Reviewed-on: https://go-review.googlesource.com/c/go/+/422039
Run-TryBot: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Auto-Submit: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Reviewed-by: Than McIntosh <thanm@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
jproberts pushed a commit to jproberts/go that referenced this issue Aug 10, 2022
Mark the assembly routines as not escaping their arguments.

Add a special case to NewInt that, when inlined, can do all
of its allocations (a big.Int and a [1]Word) on the stack.

Update golang#29951

Change-Id: I9bd38c262eb97df98c0ed9874da7daac381243ea
Reviewed-on: https://go-review.googlesource.com/c/go/+/411254
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@google.com>
Run-TryBot: Keith Randall <khr@golang.org>
Reviewed-by: Robert Griesemer <gri@google.com>
jproberts pushed a commit to jproberts/go that referenced this issue Aug 10, 2022
Since when that test requires inlining, which is disabled on noopt
builder.

Updates golang#29951

Change-Id: I9d7a0a64015a30d3bfb5ad5d806ea0955657fda3
Reviewed-on: https://go-review.googlesource.com/c/go/+/422039
Run-TryBot: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Auto-Submit: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Reviewed-by: Than McIntosh <thanm@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
@golang golang locked and limited conversation to collaborators Aug 8, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
No open projects
Development

No branches or pull requests