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

Comments

Projects
None yet
5 participants
@alexd765
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

This comment has been minimized.

Contributor

alexd765 commented May 26, 2018

This should get label Performance and milestone Unplanned.

@gopherbot

This comment has been minimized.

gopherbot commented Jul 12, 2018

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment