Crystal: Use Ryu algorithm for floating point to string conversation

[watzon]

It was just brought to my attention by a friend that Crystal uses the Grisu3 algorithm for converting floating point numbers to strings. Apparently switching to the Ryu algorithm could offer a boost in performance. CC: @Zenohate

[vlazar]

Numbers look great
https://github.com/ulfjack/ryu#ryu-printf

Has comparison with grisu2 (no grisu3 though) here among others

So, my preliminary findings are:

• erthink is faster when value could be represented by 12 or less digits (I checked this by changing range of this loop);
• ryu is faster in the all other cases;

https://github.com/ulfjack/ryu/issues/28#issuecomment-497864191

[Zenohate]

I will tackle an implementation based of the C one, It will take time tho and may bear no fruits. I am currently fighting the new overflow safe Int a lot doing all of that.

I am copying the API of the Grisu3 class for now so that it can be easy to replace as well as writing the code in a separate library which it will be possible to merge later.

Best regards

[watzon]

Excited to see what you can come up with @Zenohate

[vlazar]

Oh my... what a rabbit hole. Why did I've started following links for ryu on GitHub 😆

Anyways... There is a discussion about implementing ryu in Go. Lots of interesting stuff.

This comment in particular might help correctness checking https://github.com/golang/go/issues/15672#issuecomment-476012114

[vlazar]

Also as mentioned in the paper

The main disadvantage of Ry ̄u is its reliance on lookuptables. These are quite reasonable for the typical 32-bit and64-bit floating point types but grow exponentially for largertypes. It is up to future work to determine whether it ispossible to reduce their size or even avoid them entirely.

[jhass]

I guess we could always keep Grisu3 around for bigger than 64bit floats then.

[asterite]

There's also no good way to have static lookup tables in Crystal like they do in C, but once there's a Ryu implementation we'll see.

[vlazar]

@asterite There is also a Java version https://github.com/ulfjack/ryu/tree/master/src/main/java/info/adams/ryu but I guess you mean Crystal needs static lookup tables closer to C for such cases? This can allow even more optimizations?

[asterite]

I guess C will dump those static lookup tables to the data segment of the program. In Java it seems they are initialized at runtime. In Crystal it'll probably be have to be the same. Maybe it'll still be fast enough.

[vlazar]

Maybe Crystal can use something similar to Ruby's __END__ + DATA magic for such data?

[rdp]

The readme does mention Grisu3 in some comparisons, FWIW (stated to be significantly faster).