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.

Sign up for GitHub

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

Jump to bottom

math/big: fast path for Cmp if same #30856

Closed
TuomLarsen opened this issue Mar 14, 2019 · 5 comments
Closed

math/big: fast path for Cmp if same #30856

TuomLarsen opened this issue Mar 14, 2019 · 5 comments
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. Performance
Milestone
Go1.14

Comments

@TuomLarsen
Copy link

I noticed that math/big.Int Cmp method does not have a fast path for the case if x and y are the same. Wouldn't it be beneficial to have there something along the lines:

if x == y {
    r = 0
    return
}

Mul seems to do similar.

Same applies for big.Rat and big.Float.
@ALTree ALTree added this to the Go1.13 milestone Mar 15, 2019
@ALTree ALTree added Performance NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. labels Mar 15, 2019
@ALTree
Copy link
Member

ALTree commented Mar 15, 2019 •
edited

Note that Mul has that check because if the two numbers are the same you can do squaring, which is faster than a fully general multiplication. This is a fast-path that cannot be easily implemented by the caller since a fast squaring routine in not trivial to write. On the other hand, it's easy to avoid an Int.Cmp call when the pointers are the same, and you can do that in user code.

@josharian
Copy link
Contributor

Seems reasonable, if it fires. You might try putting it in, adding some logging when it does/doesn’t fire, and then running make.bash. If it fires a non-trivial percentage of times it definitely seems worthwhile.

@rsc
Copy link
Contributor

rsc commented May 1, 2019

Spoke to @griesemer; go ahead, for Go 1.14.

@rsc rsc added the NeedsFix The path to resolution is known, but the work has not been done. label May 1, 2019
@rsc rsc modified the milestones: Go1.13, Go1.14 May 1, 2019
@gopherbot gopherbot removed the NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. label May 1, 2019
@IllyaYalovyy
Copy link
Contributor

Is anyone working on it? I'm looking to start contributing, and need an easy task for a warmup.

@gopherbot
Copy link

Change https://golang.org/cl/178957 mentions this issue: math/big: fast path for Cmp if same

tomocy pushed a commit to tomocy/go that referenced this issue Sep 1, 2019
@IllyaYalovyy @tomocy
math/big: fast path for Cmp if same
9e4b463 
math/big.Int Cmp method does not have a fast path for the case if x and y are the same.

Fixes golang#30856

Change-Id: Ia9a5b5f72db9d73af1b13ed6ac39ecff87d10393
Reviewed-on: https://go-review.googlesource.com/c/go/+/178957
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
t4n6a1ka pushed a commit to t4n6a1ka/go that referenced this issue Sep 5, 2019
@IllyaYalovyy @t4n6a1ka
math/big: fast path for Cmp if same
0a31615 
math/big.Int Cmp method does not have a fast path for the case if x and y are the same.

Fixes golang#30856

Change-Id: Ia9a5b5f72db9d73af1b13ed6ac39ecff87d10393
Reviewed-on: https://go-review.googlesource.com/c/go/+/178957
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
@golang golang locked and limited conversation to collaborators Aug 27, 2020
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. Performance
Projects
None yet
Milestone
Go1.14
Development

No branches or pull requests
6 participants
@josharian @rsc @IllyaYalovyy @TuomLarsen @ALTree @gopherbot