strconv: implement the Ryu algorithm to speed up float64->decimal conversion

[dvyukov]

go version devel +15f2d0e Fri May 13 01:19:05 2016 +0000 linux/amd64

func BenchmarkAppendFloatLarge1(b *testing.B) { benchmarkAppendFloat(b, 622666234635.321e-320, 'e', -1, 64) }
func BenchmarkAppendFloatLarge2(b *testing.B) { benchmarkAppendFloat(b, 622666234635.3213e-320, 'e', -1, 64) }
func BenchmarkAppendFloatLarge3(b *testing.B) { benchmarkAppendFloat(b, 622666234635.322e-320, 'e', -1, 64) }

BenchmarkAppendFloatLarge1-48        5000000           276 ns/op
BenchmarkAppendFloatLarge2-48           2000         89589 ns/op
BenchmarkAppendFloatLarge3-48         500000           278 ns/op

[dvyukov]

320 times slower WAT?1!1
100 microseconds. Does it contact FFS (Float-Formatting Service)?

[griesemer]

This is a corner-case of a corner-case - extremely unlikely to matter in real-world apps. We have large-exponent values (unlikely), and for the BenchmarkAppendFloatLarge2-48 we have a slow-path:

In genericFtoa, we end up calling bigFtoa which uses slow bignum arithmetic. In bigFtoa, the call to roundShortest fails to return quickly, and it proceeds doing the slow (but precise) binary-to-decimal mantissa conversion (ftoa.go:257ff).

Probably not worth spending much time on fixing this.

[dvyukov]

Looks like a nice DoS attack vector on any Go software that ever formats floats.

Also, strconv.AppendFloat(dst[:0], 622666234635.3213e-320, 'f', -1, 64) outputs just zeros, but still takes 100+ microseconds.

[griesemer]

cc: @agl for input re: uses of float formatting for DoS attacks. I suspect this might not be unique to Go, and if so, what do other systems do?

[agl]

It's an interesting algorithmic complexity attack. (There have been similar issues in the past.)

It's a bit of a sharp edge, but some values will probably always take a little longer to format. We could put effort into optimising this, but it probably makes the code complex in an already complex area. Perhaps it's worth a comment, but I'm not sure about more than that.

[nightlyone]

How many of these corner case numbers exist? If their number is small, maybe a static lookup table could work....

[griesemer]

@nightlyone Hard to say without very careful (and difficult!) mathematical analysis.

[ALTree]

Well, the fact that Dmitry found one (in a space of 2**64 elements) by fuzzing (I believe?) suggests that the number of slow values is probably not that small.

[rsc]

Basically all floating point printing algorithms use a fast path for most numbers and fall back to a slow path. Go's fast path is the Grisu3 algorithm, which fails for 0.5% of inputs. The fallback is to some slow decimal code that I wrote a long time ago. In practice this is fine. Grisu3 was basically state of the art when it was added here, I believe by @remyoudompheng .

Very recently a new paper came out that gets the fast path down to "all but 45 float64 values", which you can then handle with a table. See Andrysco, Jhala, and Lerner,
"Printing Floating-Point Numbers: A Faster, Always Correct Method", POPL 2016.

If someone wants to implement that, great, but I don't think it's a particularly high priority.

[cespare]

@rsc it seems that by the authors' own benchmarks, Errol is 2.4x slower than Grisu3. Does that seem like a reasonable tradeoff for strconv? (I ask because I'm thinking of working on this but I anticipate pushback if the change makes the 95.5% case more than twice as slow. Another alternative would be to use Errol as the Grisu3 fallback but that seems like a lot of code for printing floats.)