code review 5502079: strconv: faster FormatFloat(x, *, -1, 64) using Grisu3 ...

strconv: faster FormatFloat(x, *, -1, 64) using Grisu3 algorithm.

The implementation is similar to the one from the double-conversion
library used in the Chrome V8 engine.

                            old ns/op   new ns/op  speedup
BenchmarkAppendFloatDecimal      591         480      1.2x
BenchmarkAppendFloat            2956         486      6.1x
BenchmarkAppendFloatExp        10622         503     21.1x
BenchmarkAppendFloatNegExp     40343         483     83.5x
BenchmarkAppendFloatBig         2798         664      4.2x

See F. Loitsch, ``Printing Floating-Point Numbers Quickly and
Accurately with Integers'', Proceedings of the ACM, 2010.

[remyoudompheng, 2011-12-28 01:14:56]

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/

[remyoudompheng, 2011-12-28 01:18:40]

Please note that the ftoa random tests will fail for the moment due to differing
specifications for "Shortest representation". We need to resolve issue 2625
before going on.

Rémy.

[remyoudompheng, 2011-12-30 07:44:04]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com,
remy@archlinux.org),

Please take another look.

[rsc, 2012-01-12 03:02:47]

This is great.  Thanks very much.
Please update and re-hg mail
once I've submitted the strconv fix.

http://codereview.appspot.com/5502079/diff/6/src/pkg/strconv/extfloat.go
File src/pkg/strconv/extfloat.go (right):

http://codereview.appspot.com/5502079/diff/6/src/pkg/strconv/extfloat.go#newc...
src/pkg/strconv/extfloat.go:351: panic("invalid exponent range")
Just in case it happens, "strconv: invalid exponent range" will help us find it.

http://codereview.appspot.com/5502079/diff/6/src/pkg/strconv/extfloat.go#newc...
src/pkg/strconv/extfloat.go:357: lookupexp:
We usually give these upper case names.

Lookupexp:

or even just Loop: is fine here.

http://codereview.appspot.com/5502079/diff/6/src/pkg/strconv/extfloat.go#newc...
src/pkg/strconv/extfloat.go:359: exponent := f.exp + powersOfTen[i].exp + 64
s/exponent/exp/ to match the surrounding code
(nothing else spells it out)

http://codereview.appspot.com/5502079/diff/6/src/pkg/strconv/extfloat.go#newc...
src/pkg/strconv/extfloat.go:376: // frexp10Many applies a common shift by a
power of Ten to a, b, c.
s/Ten/ten/?

http://codereview.appspot.com/5502079/diff/6/src/pkg/strconv/extfloat.go#newc...
src/pkg/strconv/extfloat.go:379: i := (-exp10 - firstPowerOfTen) /
stepPowerOfTen
You could instead make frexp10 return both exp10 and i.

exp10, i := c.frexp10...
a.Multiply(powersOfTen[i])
b.Multiply(powersOfTen[i])

Seems less error-prone (and we have multiple return values,
unlike in C).

http://codereview.appspot.com/5502079/diff/6/src/pkg/strconv/extfloat.go#newc...
src/pkg/strconv/extfloat.go:385: // ToShortestDecimal produces the shortest
decimal representation of f
s/To//
s/produces/stores in d/

http://codereview.appspot.com/5502079/diff/6/src/pkg/strconv/extfloat.go#newc...
src/pkg/strconv/extfloat.go:389: func (f *extFloat) ToShortestDecimal(a
*decimal, lower, upper *extFloat) bool {
s/a/d/ just so that referring to the variable
doesn't look like using the English word 'a'.

http://codereview.appspot.com/5502079/diff/6/src/pkg/strconv/ftoa.go
File src/pkg/strconv/ftoa.go (right):

http://codereview.appspot.com/5502079/diff/6/src/pkg/strconv/ftoa.go#newcode140
src/pkg/strconv/ftoa.go:140: // Precision for shortest representation mode.
This can move up into the if shortest, no?
It doesn't seem to apply to the else case, so it
doesn't have to be down here.

[remyoudompheng, 2012-01-13 07:26:44]

Also updated the benchmark comparison, since "AppendDecimal" was greatly
improved by "strconv: implement fast path for rounding already short numbers"
change.

http://codereview.appspot.com/5502079/diff/6/src/pkg/strconv/extfloat.go
File src/pkg/strconv/extfloat.go (right):

http://codereview.appspot.com/5502079/diff/6/src/pkg/strconv/extfloat.go#newc...
src/pkg/strconv/extfloat.go:351: panic("invalid exponent range")
On 2012/01/12 03:02:47, rsc wrote:
> Just in case it happens, "strconv: invalid exponent range" will help us find
it.

Done.

http://codereview.appspot.com/5502079/diff/6/src/pkg/strconv/extfloat.go#newc...
src/pkg/strconv/extfloat.go:357: lookupexp:
On 2012/01/12 03:02:47, rsc wrote:
> We usually give these upper case names.
> 
> Lookupexp:
> 
> or even just Loop: is fine here.

Done.

http://codereview.appspot.com/5502079/diff/6/src/pkg/strconv/extfloat.go#newc...
src/pkg/strconv/extfloat.go:359: exponent := f.exp + powersOfTen[i].exp + 64
On 2012/01/12 03:02:47, rsc wrote:
> s/exponent/exp/ to match the surrounding code
> (nothing else spells it out)

Done.

http://codereview.appspot.com/5502079/diff/6/src/pkg/strconv/extfloat.go#newc...
src/pkg/strconv/extfloat.go:376: // frexp10Many applies a common shift by a
power of Ten to a, b, c.
On 2012/01/12 03:02:47, rsc wrote:
> s/Ten/ten/?

Done.

http://codereview.appspot.com/5502079/diff/6/src/pkg/strconv/extfloat.go#newc...
src/pkg/strconv/extfloat.go:379: i := (-exp10 - firstPowerOfTen) /
stepPowerOfTen
On 2012/01/12 03:02:47, rsc wrote:
> You could instead make frexp10 return both exp10 and i.
> 
> exp10, i := c.frexp10...
> a.Multiply(powersOfTen[i])
> b.Multiply(powersOfTen[i])
> 
> Seems less error-prone (and we have multiple return values,
> unlike in C).

Done.

http://codereview.appspot.com/5502079/diff/6/src/pkg/strconv/extfloat.go#newc...
src/pkg/strconv/extfloat.go:385: // ToShortestDecimal produces the shortest
decimal representation of f
On 2012/01/12 03:02:47, rsc wrote:
> s/To//
> s/produces/stores in d/

Done.

http://codereview.appspot.com/5502079/diff/6/src/pkg/strconv/extfloat.go#newc...
src/pkg/strconv/extfloat.go:389: func (f *extFloat) ToShortestDecimal(a
*decimal, lower, upper *extFloat) bool {
On 2012/01/12 03:02:47, rsc wrote:
> s/a/d/ just so that referring to the variable
> doesn't look like using the English word 'a'.

Done.

http://codereview.appspot.com/5502079/diff/6/src/pkg/strconv/ftoa.go
File src/pkg/strconv/ftoa.go (right):

http://codereview.appspot.com/5502079/diff/6/src/pkg/strconv/ftoa.go#newcode140
src/pkg/strconv/ftoa.go:140: // Precision for shortest representation mode.
On 2012/01/12 03:02:47, rsc wrote:
> This can move up into the if shortest, no?
> It doesn't seem to apply to the else case, so it
> doesn't have to be down here.

Done.

[remyoudompheng, 2012-01-13 07:28:00]

Hello rsc@golang.org (cc: golang-dev@googlegroups.com, remy@archlinux.org),

Please take another look.

[rsc, 2012-01-13 22:00:35]

LGTM

Will leave for you to submit.
Please run all.bash first.

[remyoudompheng, 2012-01-13 22:24:37]

*** Submitted as http://code.google.com/p/go/source/detail?r=0ebf155c8d5a ***

strconv: faster FormatFloat(x, *, -1, 64) using Grisu3 algorithm.

The implementation is similar to the one from the double-conversion
library used in the Chrome V8 engine.

                            old ns/op   new ns/op  speedup
BenchmarkAppendFloatDecimal      591         480      1.2x
BenchmarkAppendFloat            2956         486      6.1x
BenchmarkAppendFloatExp        10622         503     21.1x
BenchmarkAppendFloatNegExp     40343         483     83.5x
BenchmarkAppendFloatBig         2798         664      4.2x

See F. Loitsch, ``Printing Floating-Point Numbers Quickly and
Accurately with Integers'', Proceedings of the ACM, 2010.

R=rsc
CC=golang-dev, remy
http://codereview.appspot.com/5502079