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/big: improve threshold calibration #25580

Open
alexd765 opened this issue May 26, 2018 · 2 comments
Open

math/big: improve threshold calibration #25580

alexd765 opened this issue May 26, 2018 · 2 comments
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone

Comments

@alexd765
Copy link
Contributor

alexd765 commented May 26, 2018

For multiplication and squaring we use different algorithms depending on the input length. We currently have 3 threshold constants to decide which algorithm to use. These are calibrated with TestCalibrate.

This calibration takes multiple minutes to run and the outcome doesn't seem to be that reliable. Last noticed in cl 105075.

Quote @griesemer :

On my machine, the threshold is much lower (less than 200). At some point we need to find a better way to determine these values.

I see three issues:

  1. Reliable result on a single machine: this worked on my machine, but didn't for @ALTree.
  2. Similar results on different machines: for calibrating karatsubaSqrThreshold we got differences of more than 100% between our 3 machines
  3. Slowness. This might be less important, but if this wouldn't take multiple minutes where you shouldn't run other programs it might be easier to ask more people to run the calibration.
@alexd765
Copy link
Contributor Author

This should get label Performance and milestone Unplanned.

@agnivade agnivade added Performance NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels May 26, 2018
@agnivade agnivade added this to the Unplanned milestone May 26, 2018
@gopherbot
Copy link

Change https://golang.org/cl/123497 mentions this issue: math/big: improve threshold calibration for karatsuba

@bradfitz bradfitz modified the milestones: Unplanned, Go1.12 Jul 12, 2018
@griesemer griesemer modified the milestones: Go1.12, Go1.13 Dec 11, 2018
@griesemer griesemer modified the milestones: Go1.13, Go1.14 May 6, 2019
@rsc rsc modified the milestones: Go1.14, Backlog Oct 9, 2019
@smasher164 smasher164 modified the milestones: Backlog, Go1.14 Oct 11, 2019
@griesemer griesemer modified the milestones: Go1.14, Backlog Nov 12, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Projects
None yet
Development

No branches or pull requests

7 participants