Ryū: Fast Float-To-String Conversion | Hacker News Reader

Ryū: Fast Float-To-String Conversion

pldi18.sigplan.org

148 pointsngaut42 comments

4:27 > "Every binary floating point number has an exact decimal equivalent, but not every decimal number has an exact binary equivalent. And the reason for that, you know, is that powers of two and powers of ten are only compatible in one direction, not in the other."

This is because 1/2 is representable as a fraction with 10 in the denominator: 5/10. All fractional digits after the binary point are just powers of 1/2, thus powers of 5/10. Division by ten in decimal doesn't produce any repeating digits.

Here is where the above is slightly misleading, though. The number of decimal digits to capture that exact decimal value of a binary floating point with an n-bit mantissa may be far in excess of the actual decimal precision that is contained in an n-bit mantissa.

In the case of the IEEE 64 bit double we need 17 decimal digits to capture a printed decimal representation which will reproduce the original double. That representation isn't the exact decimal number; much more than 17 digits may be required to get the exact decimal value. The exact decimal value is, I think, rarely of interest. In an ordinary application of floating point numbers, we don't print double values to, say, 30 digits of precision; anything after 17 is "junk".

In the other direction, only 15 decimal digits of precision are guaranteed to be preserved by the representation, so in a 17 digit print, digits 16 and 17 are also "dodgy"; they serve only to record the object exactly.

You're right, but I don't think it qualifies as misleading since the whole algorithm is exactly about finding the minimal expansion for a specific number.

The author even goes through an explicit example.

The paper is open-access at ACM:

https://dl.acm.org/citation.cfm?id=3192369

That's really appreciated; thanks.

You're welcome.

The code is here: https://github.com/ulfjack/ryu

Jacob Quinn has a translation to Julia here: https://github.com/quinnj/Ryu.jl

I really enjoy seeing Julia devs so invested and up-to-date with projects and experiments like this, because isn't this the bread and butter of technical computing? The nitty gritty of making all these bits and bytes do work! So cool.

Is Ryu.jl significantly faster than what's in Base? Is there already an open issue somewhere?

Yes, I think preliminary tests showed that it was faster than Grisu (which is what we're using in Base currently). It also seems significantly simpler (Grisu is generally fairly simple but has a custom BigInt implementation to handle some corner cases, which makes things complicated). Not a good time right now to swap the float print algorithm, but a good project for post-1.0.

I don't see an issue about it at the moment. I guess we just expect Jacob to PR it at some point. IIRC he also wrote the Grisu implementation that's in Base.

To hijack this thread a different direction for a moment, is this type of change one that would be allowed to occur in 1.x? How is it determined what changes are suitable for 1.x and what will wait for 2.0, once 1.0 is released?

I'm very interested in how detailed and coordinated the Julia team has become regarding the longer term future of Julia. Admirable effort all around.

I'd say probably yes. Changes are suitable for 1.x if they are not generally breaking for user code. This change probably wouldn't be considered breaking, but we'd have to look at it at the time.

FYI: Grisu2 and Ryu should produce bit-identical outputs in all cases.

(De-)Serialization being such a common task both in Servers and clients nowadays I wonder if special instructions would make sense in CPUs

At that point just base-64 for your IEEE floats.... Because anywhere where you need that speed you can better handle it without using strings...

But that's not necessarily interoperable. E.g., some JSON parsers might produce IEEE754 doubles, but others might use arbitrary precision representations -- what then? One answer is to make JSON support only IEEE754 doubles, but it's a bit late for that, so at most one can recommend that implementors stick to IEEE754.

If you are starting from scratch, and want to support only platforms that support IEEE754 in hardware, and so on, then yes, just serialize the raw bits.

You've just given me the idea that interop should be done with "hexponential" notation: 0x123ABC*0x10^0xDEF can be an exact representation of a floating point number.

That’s basically hexadecimal floating point strings, which are in C since C99 via the %a format specifier (they use a base-two exponent written in decimal instead of a base-16 exponent in hex, but that doesn’t really change the complexity of parsing or formatting.)

Then support this as a fallback, and negotiate for IEEE754 binary support on the next higher level.

https://stackoverflow.com/questions/50966676/why-do-arm-chip...

(not quite the same thing but heading in that direction)

This is in a track called "PLDI Research Papers - Floats and Maps". Is that because they had one paper on maps and two on floats, and decided to put them together, or is there some deep connection between the two?

As far as I could tell, there wasn't any deep connection between the talks.

Other than printing out the numbers, what are the practical applications?

Javascript was mentioned in the talk; because of its weak typing and plenty of APIs that take strings, floating point printing is pretty common.

That's really sad.

Why? Did you forget to read the implied "just like any other language that's being used in a graphical context, where live numbers need to be shown"?

Often, numbers in JS happen to be just integers. Would the implementation optimize for that case?

Javascript JITs specialize for integers already. I don't know if Ryū does specifically though.

It doesn't optimize for ints right now. I thought about that, but haven't tried it yet.

Printing them out quickly?

Real-time displays often need to show floating point numbers as they change. As a simple example, the time remaining display of a music player ticks down as the music plays. Now in this case, it is easy to fake it by using integers and then placing the decimal point, but if you were controlling something complex in real time you might not be able to do this as easily.

> it is easy to fake it by using integers and then placing the decimal point

That's not "faking it", that using fixed point numbers [1]. They are a great alternative if the numbers stay in roughly the same magnitude, and are much saner when dealing with e.g. money.

1: https://en.wikipedia.org/wiki/Fixed-point_arithmetic

Good point, and thanks. But if you are doing a real-time display (like an industrial controller, for example), you may not be able to choose a fixed point number as your source. I chose the music time example first because it is a common use of a number that needs to change in (almost) real time.

Cross platform serialization.

I mean, that's a huge practical application!

Web apis. Eg: json, xml

To save some time: https://github.com/ulfjack/ryu

Does anyone know of a good decimal float to string converter, preferably in c?

sprintf

Then main drawbacks of sprintf are that it doesn't allow to find the shortest decimal representation and that its output depends on the current locale, so you often need something like sprintf_l which isn't portable.

Why is it not portable?

Because only very few libc's support it. There should also be a locale independent _sprintf_c somewhen.

C code for Ryu is available under the Apache2 and Boost licenses: https://github.com/ulfjack/ryu/tree/master/ryu

Also have a look at Grisu3, Dragon4, dtoa, and the printf implementations of glibc and musl.

The two fastest options that I'm currently aware of, by a pretty wide margin, are Ryu and Swift's implementation (single C file, it's only in a C++ file to satisfy a build system quirk in Swift on linux: https://github.com/apple/swift/blob/master/stdlib/public/run..., Apache2 + run time exception).

Ryu is somewhat faster for doubles, though SwiftDtoa has support for 80-bit and float out of the box, which is nice, and we have some further perf improvements planned. Both are considerably faster than any of the alternatives (some perf data in the original Swift PR: https://github.com/apple/swift/pull/15474), and both pass our fairly intensive test suite.

musl's implementation is also interesting for reasons of simplicity.

Reply on news.ycombinator.com