Issue 5494060: code review 5494060: strconv: implement fast path for rounding already short... (Closed)
|
Created:
13 years, 7 months ago by remyoudompheng Modified:
13 years, 6 months ago Reviewers:
CC:
rsc, golang-dev, remy_archlinux.org Visibility:
Public. |
Descriptionstrconv: implement fast path for rounding already short numbers.
benchmark old ns/op new ns/op delta
BenchmarkFormatFloatDecimal 3765 1386 -63%
Patch Set 1 #Patch Set 2 : diff -r 3036d2362ea5 https://go.googlecode.com/hg/ #Patch Set 3 : diff -r 3036d2362ea5 https://go.googlecode.com/hg/ #
Total comments: 7
Patch Set 4 : diff -r 561eb3ec7eb5 https://go.googlecode.com/hg/ #
Total comments: 2
Patch Set 5 : diff -r 29382b5af719 https://go.googlecode.com/hg/ #MessagesTotal messages: 12
Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com, remy@archlinux.org), I'd like you to review this change to https://go.googlecode.com/hg/
Sign in to reply to this message.
http://codereview.appspot.com/5494060/diff/1002/src/pkg/strconv/ftoa.go File src/pkg/strconv/ftoa.go (right): http://codereview.appspot.com/5494060/diff/1002/src/pkg/strconv/ftoa.go#newco... src/pkg/strconv/ftoa.go:189: // If d is not denormal, then 2^exp < d < 10^dp. first < should be <=, no? http://codereview.appspot.com/5494060/diff/1002/src/pkg/strconv/ftoa.go#newco... src/pkg/strconv/ftoa.go:190: // The distance to the closest shorter number is less than 5 * 10^(dp-nd). s/less than/at most/ http://codereview.appspot.com/5494060/diff/1002/src/pkg/strconv/ftoa.go#newco... src/pkg/strconv/ftoa.go:191: // The distance to the lower/upper bounds is more than 2^(exp-mantbits-1). s/more than/at least/ http://codereview.appspot.com/5494060/diff/1002/src/pkg/strconv/ftoa.go#newco... src/pkg/strconv/ftoa.go:192: // So if 10^(dp-nd+1) > 2^(exp-mantbits) we already have the It would help future programmers to spell out the step here, namely: // So if 5*10^(dp-nd) < 2^(exp-mantbits-1), we already have the shortest number. // That is equivalent to 10^(dp-nd+1) < 2^(exp-mantbits). And then I lost you. I don't see the leap to mantbits/10 > (nd-1)/3. Where did dp and exp go?
Sign in to reply to this message.
http://codereview.appspot.com/5494060/diff/1002/src/pkg/strconv/ftoa.go File src/pkg/strconv/ftoa.go (right): http://codereview.appspot.com/5494060/diff/1002/src/pkg/strconv/ftoa.go#newco... src/pkg/strconv/ftoa.go:189: // If d is not denormal, then 2^exp < d < 10^dp. Sure, the important consequence is that 2^exp < 10^dp. http://codereview.appspot.com/5494060/diff/1002/src/pkg/strconv/ftoa.go#newco... src/pkg/strconv/ftoa.go:190: // The distance to the closest shorter number is less than 5 * 10^(dp-nd). Sorry for that, French language habits. http://codereview.appspot.com/5494060/diff/1002/src/pkg/strconv/ftoa.go#newco... src/pkg/strconv/ftoa.go:192: // So if 10^(dp-nd+1) > 2^(exp-mantbits) we already have the Right, I was a bit greedy on the math details. The reasoning here is that we know that 10^dp > 2^exp. It is thus sufficient to get 10^(-nd+1) > 2^(-mantbits) to obtain the required inequality, which is 5*10^(dp-nd) > 2^(exp-mantbits-1). Taking reciprocals, we want to obtain 10^(nd-1) < 2^mantbits. Now, 10^(nd-1) = 1000^((nd-1)/3) and 2^mantbits = 1024^(mantbits/10), so a sufficient condition for the whole thing is (nd-1) < 3*mantbits/10 (something like nd<=16). If this seems valid to youn I can edit the CL to give more detailed comments.
Sign in to reply to this message.
That reasoning looks good to me. Please put it in a comment. Thanks! Russ
Sign in to reply to this message.
On 2011/12/19 Russ Cox <rsc@golang.org> wrote: > That reasoning looks good to me. > Please put it in a comment. After rewriting it, I realize it's wrong: you are sure to be shortest with 15 digits, but certainly not with 16 digits since 2^-52 is a bit more than 2e-16. I'm correcting the CL, I think the test cases were not strong enough to catch this. Rémy.
Sign in to reply to this message.
Hello rsc@golang.org (cc: golang-dev@googlegroups.com, remy@archlinux.org), Please take another look.
Sign in to reply to this message.
http://codereview.appspot.com/5494060/diff/3004/src/pkg/strconv/ftoa.go File src/pkg/strconv/ftoa.go (right): http://codereview.appspot.com/5494060/diff/3004/src/pkg/strconv/ftoa.go#newco... src/pkg/strconv/ftoa.go:201: // will suffice. For example, 2^-52 is about 2.22e-16, hence 15 decimal Something is not right here. You need 17 digits in general to fully specify a float64. For example, these are distinct: 1.0000000000000002 1.0000000000000004
Sign in to reply to this message.
On 2012/01/10 20:37:01, rsc wrote: > http://codereview.appspot.com/5494060/diff/3004/src/pkg/strconv/ftoa.go > File src/pkg/strconv/ftoa.go (right): > > http://codereview.appspot.com/5494060/diff/3004/src/pkg/strconv/ftoa.go#newco... > src/pkg/strconv/ftoa.go:201: // will suffice. For example, 2^-52 is about > 2.22e-16, hence 15 decimal > Something is not right here. You need 17 digits in general > to fully specify a float64. For example, these are distinct: > > 1.0000000000000002 > 1.0000000000000004 Hum, this looks like a different problem: the question is how many digits ensure the shortest-ness of the number. 17 digits do not ensure the number is shortest, because there might be a 16-digit representation. However, if the number has only a few digits (15, for example), a shorter number is necessarily very far away, so it can't be a better representation. So if the number is *longer* that the limit (15 digits), there is doubt and a long computation must be done. But, as I got myself totally confused here, I am absolutely for a careful review of this. Rémy.
Sign in to reply to this message.
http://codereview.appspot.com/5494060/diff/3004/src/pkg/strconv/ftoa.go File src/pkg/strconv/ftoa.go (right): http://codereview.appspot.com/5494060/diff/3004/src/pkg/strconv/ftoa.go#newco... src/pkg/strconv/ftoa.go:197: // Since already 10^dp > 2^exp, it is enough to arrange for I asked before about the leap here, and you explained it well, but I am still not sure it is the right thing to do. It is definitely correct, but 10^dp / 2^exp can be in the range (1, 10], and the simplification here only takes advantage of the fact that it is >= 1. In particular, if 10^dp / 2^exp >= 2.22 or so, then even a 16-digit representation can be shortest and stop here. 3351200045039316 is such a number. I suggest making this part say: // So the number is already shortest if 10^(dp-nd) > 2^(exp-mantbits), // or equivalently log2(10)*(dp-nd) > exp-mantbits, // or equivalently 332*(dp-nd) > 100*(exp-mantbits). minexp := flt.bias + 1 // minimum possible exponent if exp > minexp && 332*(d.dp-d.nd) >= 100*(exp-int(flt.mantbits)) { // The number is already shortest. return } That's less to explain and triggers in more cases. Just running the current test suite I found that it triggered (where this CL's current code does not) for 412321923223059.5 55136109853548720 169307312997611200 6910451436370337 2459097028550238 51320142329528640 8515811600646302 8532065512384777 3905791496339036 62160630055645.25 3351200045039316 4642390149040519 23737736847187060
Sign in to reply to this message.
Hello rsc@golang.org (cc: golang-dev@googlegroups.com, remy@archlinux.org), Please take another look.
Sign in to reply to this message.
LGTM
Sign in to reply to this message.
*** Submitted as aa208a81cc08 *** strconv: implement fast path for rounding already short numbers. benchmark old ns/op new ns/op delta BenchmarkFormatFloatDecimal 3765 1386 -63% R=rsc CC=golang-dev, remy http://codereview.appspot.com/5494060 Committer: Russ Cox <rsc@golang.org>
Sign in to reply to this message.
|
