Stl: <charconv>: Investigate using Grisu-Exact for to_chars() decimal shortest

[StephanTLavavej]

Repo: https://github.com/jk-jeon/Grisu-Exact

Reddit posts: Aug 2020 and earlier Jan 2020.

It is a variant of Grisu2 a classic float-to-string conversion algorithm developed by Florian Loitsch, and is largely inspired by Ryu, another float-to-string conversion algorithm developed by Ulf Adams. The main strength of Grisu-Exact over Ryu is that it performs better for short numbers.

The algorithm's inventor and implementer, Junekey Jeon, has graciously licensed this code so that it's compatible with microsoft/STL (the bulk of the code is dual Apache 2.0 + LLVM / Boost; fp_to_chars.cpp is Apache 2.0 / Boost as it's derived from Ryu). :heart_eyes_cat:

[jk-jeon]

FYI: there is even faster one (with almost same size of table). Please have a look at the implementation of _Schubfach_ in this repository: https://github.com/abolz/Drachennest

[StephanTLavavej]

Also see https://github.com/jk-jeon/dragonbox .

[jk-jeon]

Just FYI.

After Dragonbox, I'm working on Ryu-printf now. I think the core routine is now working correctly, and it uses about 39KB of static data. Although 39KB is still huge, that's way better than 100KB. (I don't think I really understood what was the precise table compression scheme that Ulf came up with, so I have no idea why he ended up using more than 100KB, because what I did was just to follow the paper pretty straightforwardly.) But I didn't do any performance evaluation against the original implementation yet. It is possible that mine is much slower than the original one, though I honestly think that the performances should be not that different if I didn't do something stupid on the string generation part.

I also think it is possible to further compress the table by using more(!) bits per an entry, but at the cost of speed because then we need things like 192-bit modular operation and/or 320-bit multiplication or something like that. Maybe I can work on that later.

After Ryu-printf, I will work on arbitrary-precision string-to-float conversion, using the core of Ryu-printf. That should be not so difficult I guess.

Please look at the repo if you are interested. (It is not well furnished yet, sorry.) It would be great if you can give me some suggestion or advice or anything, if you have time. I mean, the core routine (binary-to-decimal conversion) is actually pretty simple once the algorithm is understood, but the string generation part with the correct rounding was in fact much more annoying. I think you also have worked on string generation part of the original Ryu-printf implementation, so may know better about it than me.

[StephanTLavavej]

39KB is indeed amazing. Unfortunately I'm very busy at the moment trying to help finish our C++20 implementation before the end of 2020 - but if you haven't already, I recommend using our charconv test data to validate the correctness of your algorithm. See the files in https://github.com/microsoft/STL/tree/master/tests/std/tests/P0067R5_charconv - the files like double_scientific_precision_to_chars_test_cases_1.hpp, double_scientific_precision_to_chars_test_cases_2.hpp, etc. contain an extensive set of test cases, derived from Ulf's, that I developed when testing Ryu Printf (and which found a correctness bug in his early implementation). They're structured as flat tables so it should be very easy to adapt them to your code.

I think you also have worked on string generation part of the original Ryu-printf implementation, so may know better about it than me.

I adapted it to charconv's non-null-terminated, bounds-checked interface but didn't change the core structure of Ulf's code. Looking at your code I don't see anything that could be immediately improved, but I might be able to think of something with sufficient time to explore later.