search

golang / go

The Go programming language
https://go.dev
BSD 3-Clause "New" or "Revised" License
122.26k stars 17.46k forks source link

math/big: improve threshold calibration #25580

Open alexd765 opened 6 years ago

alexd765 commented 6 years ago

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 commented 6 years ago

This should get label Performance and milestone Unplanned.

gopherbot commented 6 years ago

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