Menu
▾
▴
#604 Look into integration of grisu fp rendering
[10:04] <yukonbob> http://www.serpentine.com/blog/2011/06/29/here-be-dragons-advances-in-problems-you-didnt-even-know-you-had/
[10:04] <yukonbob> ^--- floating point rendering
<excerpt from the middle>
[...] But how solved was the problem? Dragon4 and its derivatives are complicated and tricky, and they have a hefty performance cost, since they rely on arbitrary-precision integer arithmetic to compute their results. There might be a significant performance improvement to be gained if someone could figure out how to use native machine integers instead.
In 2010, Florian Loitsch published a wonderful paper in PLDI, "Printing floating-point numbers quickly and accurately with integers" [1], which represents the biggest step in this field in 20 years: he mostly figured out how to use machine integers to perform accurate rendering! Why do I say "mostly"? Because although Loitsch's "Grisu3" algorithm is very fast, it gives up on about 0.5% of numbers, in which case you have to fall back to Dragon4 or a derivative.
If you're a language runtime author, the Grisu algorithms are a big deal: Grisu3 is about 5 times faster than the algorithm used by printf in GNU libc, for instance [...]
</excerpt>
[1] http://florian.loitsch.com/publications/dtoa-pldi2010.pdf?attredirects=0
code: http://code.google.com/p/double-conversion
[12:08] kbk aku, yukonbob - Thanks for the Grisu paper. Our fp conversion has a *different* set of improvements over Steele-White, Gay, and Burger-Dybvig. Essentially, our code runs Burger-Dybvig but with optimizations to (1) replace the bignum arithmetic with int64 arithmetic if the number to format is in the range [1.0e-3,1.0e+24), (2) replace mp divisions by powers of 2 with digit shifts.
[12:09] kbk I suspect Grisu would be a Big Win for formatting numbers larger than 1.0e+24, and only a smaller win for numbers in the range where the int64 trick works. No time to chase it at the moment, but open an RFE.
