3 ms·
This needs a 2011 on it, which will explain why it is missing the very recent Ryū algorithm, which I believe is the fastest algorithm at this point: https://dl
by jcranmer 6y ago
This needs a 2011 on it, which will explain why it is missing the very recent Ryū algorithm, which I believe is the fastest algorithm at this point:
https://dl.acm.org/doi/10.1145/3192366.3192369 https://dl.acm.org/doi/10.1145/3192366.3192369 (PLDI 2018 paper)
https://github.com/ulfjack/ryu https://github.com/ulfjack/ryu (C source code)
- est31 6y agoApparently Ryu is slower on shorter numbers than the Rust standard library's implementation which uses Grisu/Dragon. It might be only due to the implementation though. https://www.reddit.com/r/rust/comments/93d045/fast_floattostring_conversion_ryu_for_rust/e3d24f4/ https://www.reddit.com/r/rust/comments/93d045/fast_floattost... Also it seems that Ryu prints some numbers in weird ways even though "nicer" representations exist: https://github.com/rust-lang/rust/issues/52811#issuecomment-408644826 https://github.com/rust-lang/rust/issues/52811#issuecomment-...
- StephanTLavavej 6y agoThat “weirdness” is just scientific notation, which the Ryu implementation always emits. It is “superficial” in the sense that it’s separate from the core algorithm. When I adapted it for C++17 charconv in MSVC, I implemented fixed, general, and “plain shortest” notation, which will print 0.3 there. (General notation follows C printf %g’s rules for switching between fixed and scientific; “plain shortest” notation selects the one that’s fewer characters, tiebreaking to prefer fixed).
- zX41ZdbW 6y agoIn ClickHouse* we patched Ryu to provide nicer representations and to have better performance for floats that appear to be integers. * https://github.com/ClickHouse/ClickHouse/pull/8542 https://github.com/ClickHouse/ClickHouse/pull/8542
- zX41ZdbW 6y agoThe change to Ryu is here: https://github.com/ClickHouse-Extras/ryu/pull/1 https://github.com/ClickHouse-Extras/ryu/pull/1
- ygra 6y agoStephan T Lavavej also had a surprisingly fun and approachable talk on that problem, talking about how charconv got implemented and improved in Microsoft's C++ standard library: https://youtu.be/4P_kbF0EbZM https://youtu.be/4P_kbF0EbZM
- MaxBarraclough 6y agoWhat do you make of this algorithm which claims to be faster than the Ryu algorithm [0]? I think this is the implementation in C++ [1]. The author also worked on an algorithm for half-precision conversions. [2] [0] http://www.fox-toolkit.org/ http://www.fox-toolkit.org/ New, faster, and often more accurate floating point to string conversion. No, this is not based on Ryu paper. New method reliably generates 16 digits, and does much better rounding. [1] https://github.com/gogglesguy/fox/blob/77396c6/lib/fxprintf.cpp#L381 https://github.com/gogglesguy/fox/blob/77396c6/lib/fxprintf.... [2] [PDF] http://www.fox-toolkit.org/ftp/fasthalffloatconversion.pdf http://www.fox-toolkit.org/ftp/fasthalffloatconversion.pdf
- SloopJon 6y agoIf I understand correctly, it's a printf-style function for which the %g format code outputs the shortest decimal string that round trips. This implies that it would output no more than seventeen significant figures, regardless of the requested precision. The first thing I notice is this comment in a later changelog: > I believe we have a very fast numerical conversion that appears to be reliably generating about 15 to 16 digits out output [last digit may be off by 1 or 2 in typical case]. If the last digit of a fifteen- to sixteen-digit output is off by one or two, are we sure it round trips? Second, the test coverage for this feature in tests/format.cpp looks pretty sparse, and it's not obvious to me how the output is verified. Interesting find. I may play around with this later. Edit: I tried the test cases from here: https://www.exploringbinary.com/the-shortest-decimal-string-that-round-trips-examples/ https://www.exploringbinary.com/the-shortest-decimal-string-... Here's the result: format="%.30g" output="0.1" format="%.30g" output="50388143.06823721984" format="%.30g" output="54167628.18" format="%.30g" output="9161196241250.051072" The first and third cases output the correct string. The second case outputs nineteen digits, instead of seventeen, and does not round trip (i.e., it rounded incorrectly). The last case outputs nineteen digits instead of fifteen, but does round trip.
- MaxBarraclough 6y agoNice work, thanks for looking into it.
- 6y ago
- screwreg 6y agoActually, there's been another advance since Ryu: Schubfach by Raffaello Giulietti and its optimized derivative Dragonbox by Junekey Jeon. Here's a cool page with implementations and a benchmark: https://github.com/abolz/Drachennest/ https://github.com/abolz/Drachennest/
- ptspts 6y agoThis page has a benchmark graph, but without labels on the axes, thus it doesn't even say which algorithm was faster. My guess is that smaller y values indicate proportionally faster executions.