When I published Grisu (Google double-conversion), it was multiple times faster than the existing algorithms. I knew that there was still room for improvement, but I was at most expecting a factor 2 or so. Six times faster is really impressive.
I wonder how Teju Jaguá compares. I don't see it in the C++ benchmark repo you linked and whose graph you included.
I have contributed an implementation in Rust :) https://crates.io/crates/teju it includes benchmarks which compare it vs Ryu and vs Rust's stdlib, and the readme shows a graph with some test cases. It's quite easy to run if you're interested!
I am not sure how it compares but I did use one idea from Cassio's talk on Teju:
> A more interesting improvement comes from a talk by Cassio Neri Fast Conversion From Floating Point Numbers. In Schubfach, we look at four candidate numbers. The first two, of which at most one is in the rounding interval, correspond to a larger decimal exponent. The other two, of which at least one is in the rounding interval, correspond to the smaller exponent. Cassio’s insight is that we can directly construct a single candidate from the upper bound in the first case.
Indeed! I saw that you linked to Neri's work, so you were aware of Teju Jaguá. Might make a pull request to add it to the benchmark repo when I have some time :)
Another nice thing about your post is mentioning the "shell" of the algorithm, that is, actually translating the decimal significant and exponent to a string (as opposed to the "core", turning f * 2^e into f' * 10^e'). A decent chunk of the overall time is spent there, so it's worth optimising it as well.
The bottleneck are the 3 conditionals:
- positive or negative
- positive or negative exponent, x > 10.0
- correction for 1.xxxxx * 2^Y => fract(log10(2^Y)) 1.xxxxxxxx > 10.0
When I published Grisu (Google double-conversion), it was multiple times faster than the existing algorithms. I knew that there was still room for improvement, but I was at most expecting a factor 2 or so. Six times faster is really impressive.
I wonder how Teju Jaguá compares. I don't see it in the C++ benchmark repo you linked and whose graph you included.
I have contributed an implementation in Rust :) https://crates.io/crates/teju it includes benchmarks which compare it vs Ryu and vs Rust's stdlib, and the readme shows a graph with some test cases. It's quite easy to run if you're interested!
> A more interesting improvement comes from a talk by Cassio Neri Fast Conversion From Floating Point Numbers. In Schubfach, we look at four candidate numbers. The first two, of which at most one is in the rounding interval, correspond to a larger decimal exponent. The other two, of which at least one is in the rounding interval, correspond to the smaller exponent. Cassio’s insight is that we can directly construct a single candidate from the upper bound in the first case.
Another nice thing about your post is mentioning the "shell" of the algorithm, that is, actually translating the decimal significant and exponent to a string (as opposed to the "core", turning f * 2^e into f' * 10^e'). A decent chunk of the overall time is spent there, so it's worth optimising it as well.
The bottleneck are the 3 conditionals: - positive or negative - positive or negative exponent, x > 10.0 - correction for 1.xxxxx * 2^Y => fract(log10(2^Y)) 1.xxxxxxxx > 10.0