5 ms·

This paper is first-rate. That said, it would have be nice to have links to the C code used for the performance comparisons (reproducable research). Python cu

This paper is first-rate. That said, it would have be nice to have links to the C code used for the performance comparisons (reproducable research). Python currently uses David Gay's algorithm and would likely benefit from Errol3. However there is a concern that arises when switching from integer arithmetic to floating point -- the algorithm becomes susceptible to FP rounding modes and susceptible to C compilers generating code with double rounding when mixing 64-bit doubles with 80-bit extended precision. We encountered both problems when implementing Python's math.fsum() from Shewchuk's "Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates".

lifthrasiir 11y ago
http://goto.ucsd.edu/~andrysco/errol/ http://goto.ucsd.edu/~andrysco/errol/ seems to be the artifact in question. (My friend also noted that there is a Github repo in https://github.com/marcandrysco/Errol https://github.com/marcandrysco/Errol, but I'm not sure if it is intended to be canonical.) > Python currently uses David Gay's algorithm and would likely benefit from Errol3. [...] the algorithm becomes susceptible to FP rounding modes and susceptible to C compilers generating code with double rounding when mixing 64-bit doubles with 80-bit extended precision. That would be really problematic since double-double arithmetic relies on the recovery of errors from prior operations. If you are interested in the integer-only algorithm, Rust's Grisu3 implementation derives from my own public-domain reimplementation of Grisu [1]. [1] https://github.com/lifthrasiir/rust-strconv https://github.com/lifthrasiir/rust-strconv
- marcandrysco 11y ago
  Author here. We intend for the GitHub repo (https://github.com/marcandrysco/Errol https://github.com/marcandrysco/Errol) to be the primary source for Errol. We still want to add a few improvements to the existing implementation: selecting the middle-most shortest number and an implementation for 32-bit floats (and maybe __float128).
  - TazeTSchnitzel 11y ago
    I assume that for 32-bit floats, you could mostly do away with the HP stuff and just use 64-bit floats, right? Though it does make me wonder if that's always faster than two 32-bit floats. I would think so.
    - marcandrysco 11y ago
      It should be faster to replace the HP numbers entirely with 64-bit floats. Regardless, I think it would be a useful for two purposes: 1) it would serve as an implementation for chips with only 32-bit floats (maybe some kinds of embedded systems) and 2) we can exhaustively test and verify that the algorithm works on all 32-bit numbers, providing more confidence in the 64-bit version.
  - bodyfour 11y ago
    I took a quick glance though the code... looks really good. I wonder how hard it would be to tweak it to not require compiler support for __uint128_t by replacing it with manual 64-bit ops... or is support for that type no longer limited to gcc/clang?
    - marcandrysco 11y ago
      Good catch! I mostly used __uint128_t out of haste. Ideally, I would like to remove dependencies on large integer types. For now, this remains future work.
- mraleph 11y ago
  > http://goto.ucsd.edu/~andrysco/errol/ http://goto.ucsd.edu/~andrysco/errol/ seems to be the artifact in question. The artifact reveals that authors of the paper benchmarked Grisu3 in the debug mode (low compiler optimization level, ASSERTions enabled). Changing their scripts to actually build Grisu3 in release mode turns tables: ==== Absolute Results ==== Errol3 1196 cycles Grisu3 802 cycles Dragon4 6176 cycles Grisu3 w/fallback 833 cycles ==== Relative Speedup of Errol ==== Grisu3 0.67x Dragon4 5.16x Grisu3 w/fallback 0.70x (these are results on my machine with both Grisu3 and Errol3 compiled with -O3, original scripts build Errol with -O2 which makes it yet more slower than Grisu3). So ultimately it seems that Grisu3 is still faster. I also wanted to try benchmarking it on ARM - but it actually fails to build due to its dependency on __uint128_t which does not seem to be supported by my cross-compilation tool chain (at least for 32bit ARMs).
TazeTSchnitzel 11y ago
> However there is a concern that arises when switching from integer arithmetic to floating point -- the algorithm becomes susceptible to FP rounding modes and susceptible to C compilers generating code with double rounding when mixing 64-bit doubles with 80-bit extended precision. The solution to this would presumably be to compile Errol with its own set of compiler flags, rather than with your normal ones.
- marcandrysco 11y ago
  This problem is even trickier than that. The core of the algorithm should be robust given different rounding modes, but the values in the lookup table may differ based on the rounding mode. While it may seem odd for the rounding mode to change at run-time, it has happened before: https://blogs.msdn.microsoft.com/oldnewthing/20080703-00/?p=21753 https://blogs.msdn.microsoft.com/oldnewthing/20080703-00/?p=.... I will have to look at this further. It might mean generating lookup table for every rounding mode and using their union. In general, changing the global state of the FPU seems to be a risky proposition.
  - lifthrasiir 11y ago
    Hmm, just out of curiosity, would it be possible to tweak Grisu to use the same error analysis as Errol? While possibly slower in the modern architecture, it might result in the compact, fast enough and hassle-free algorithm that is good for most [1] purposes. [1] I have seen some performance-oriented JSON encoders using Grisu2 instead of Grisu3 in favor of performance. They may be willing to switch to Errol3 in spite of such configuration problems...
    - marcandrysco 11y ago
      That really depends on what you are trying to get out of the algorithm. Using 64-bit integers, I don't think you can turn Grisu2 into an failure-free algorithm. However, you can definitely improve its reliability by handling special casing small integers (as is done in Errol2/Errol3). By my estimates, this should improve Grisu's success rate from ~99.5% to ~99.95% [see math at end]. The remaining 0.05% is far too large to for enumeration and using a lookup. If you are willing to print numbers that are correct but possibly suboptimal, you can also use Errol2 and modify it to remove checking. This will give you the speed of Errol3 without having a lookup table. I might look at making such an implementation and maybe call it Errol2b. [math for calculating approximate error rate] With an input floating-point format with p bits of precision and an intermediate format with q-bits of precision: the "chance" of value failing is close to 1 in 2^(q-p). With 2^p values per exponent, you're going to see about 2^(2p-q) errors per exponent. In the case if Grisu, q is 64 and p is 53, for a total of about 2^42 errors. These numbers only give rough estimates, you'd have to verify them manually.

lifthrasiir 11y ago

http://goto.ucsd.edu/~andrysco/errol/ http://goto.ucsd.edu/~andrysco/errol/ seems to be the artifact in question. (My friend also noted that there is a Github repo in https://github.com/marcandrysco/Errol https://github.com/marcandrysco/Errol, but I'm not sure if it is intended to be canonical.) > Python currently uses David Gay's algorithm and would likely benefit from Errol3. [...] the algorithm becomes susceptible to FP rounding modes and susceptible to C compilers generating code with double rounding when mixing 64-bit doubles with 80-bit extended precision. That would be really problematic since double-double arithmetic relies on the recovery of errors from prior operations. If you are interested in the integer-only algorithm, Rust's Grisu3 implementation derives from my own public-domain reimplementation of Grisu [1]. [1] https://github.com/lifthrasiir/rust-strconv https://github.com/lifthrasiir/rust-strconv

marcandrysco 11y ago
Author here. We intend for the GitHub repo (https://github.com/marcandrysco/Errol https://github.com/marcandrysco/Errol) to be the primary source for Errol. We still want to add a few improvements to the existing implementation: selecting the middle-most shortest number and an implementation for 32-bit floats (and maybe __float128).
- TazeTSchnitzel 11y ago
  I assume that for 32-bit floats, you could mostly do away with the HP stuff and just use 64-bit floats, right? Though it does make me wonder if that's always faster than two 32-bit floats. I would think so.
  - marcandrysco 11y ago
    It should be faster to replace the HP numbers entirely with 64-bit floats. Regardless, I think it would be a useful for two purposes: 1) it would serve as an implementation for chips with only 32-bit floats (maybe some kinds of embedded systems) and 2) we can exhaustively test and verify that the algorithm works on all 32-bit numbers, providing more confidence in the 64-bit version.
- bodyfour 11y ago
  I took a quick glance though the code... looks really good. I wonder how hard it would be to tweak it to not require compiler support for __uint128_t by replacing it with manual 64-bit ops... or is support for that type no longer limited to gcc/clang?
  - marcandrysco 11y ago
    Good catch! I mostly used __uint128_t out of haste. Ideally, I would like to remove dependencies on large integer types. For now, this remains future work.
mraleph 11y ago
> http://goto.ucsd.edu/~andrysco/errol/ http://goto.ucsd.edu/~andrysco/errol/ seems to be the artifact in question. The artifact reveals that authors of the paper benchmarked Grisu3 in the debug mode (low compiler optimization level, ASSERTions enabled). Changing their scripts to actually build Grisu3 in release mode turns tables: ==== Absolute Results ==== Errol3 1196 cycles Grisu3 802 cycles Dragon4 6176 cycles Grisu3 w/fallback 833 cycles ==== Relative Speedup of Errol ==== Grisu3 0.67x Dragon4 5.16x Grisu3 w/fallback 0.70x (these are results on my machine with both Grisu3 and Errol3 compiled with -O3, original scripts build Errol with -O2 which makes it yet more slower than Grisu3). So ultimately it seems that Grisu3 is still faster. I also wanted to try benchmarking it on ARM - but it actually fails to build due to its dependency on __uint128_t which does not seem to be supported by my cross-compilation tool chain (at least for 32bit ARMs).

TazeTSchnitzel 11y ago

> However there is a concern that arises when switching from integer arithmetic to floating point -- the algorithm becomes susceptible to FP rounding modes and susceptible to C compilers generating code with double rounding when mixing 64-bit doubles with 80-bit extended precision. The solution to this would presumably be to compile Errol with its own set of compiler flags, rather than with your normal ones.

marcandrysco 11y ago
This problem is even trickier than that. The core of the algorithm should be robust given different rounding modes, but the values in the lookup table may differ based on the rounding mode. While it may seem odd for the rounding mode to change at run-time, it has happened before: https://blogs.msdn.microsoft.com/oldnewthing/20080703-00/?p=21753 https://blogs.msdn.microsoft.com/oldnewthing/20080703-00/?p=.... I will have to look at this further. It might mean generating lookup table for every rounding mode and using their union. In general, changing the global state of the FPU seems to be a risky proposition.
- lifthrasiir 11y ago
  Hmm, just out of curiosity, would it be possible to tweak Grisu to use the same error analysis as Errol? While possibly slower in the modern architecture, it might result in the compact, fast enough and hassle-free algorithm that is good for most [1] purposes. [1] I have seen some performance-oriented JSON encoders using Grisu2 instead of Grisu3 in favor of performance. They may be willing to switch to Errol3 in spite of such configuration problems...
  - marcandrysco 11y ago
    That really depends on what you are trying to get out of the algorithm. Using 64-bit integers, I don't think you can turn Grisu2 into an failure-free algorithm. However, you can definitely improve its reliability by handling special casing small integers (as is done in Errol2/Errol3). By my estimates, this should improve Grisu's success rate from ~99.5% to ~99.95% [see math at end]. The remaining 0.05% is far too large to for enumeration and using a lookup. If you are willing to print numbers that are correct but possibly suboptimal, you can also use Errol2 and modify it to remove checking. This will give you the speed of Errol3 without having a lookup table. I might look at making such an implementation and maybe call it Errol2b. [math for calculating approximate error rate] With an input floating-point format with p bits of precision and an intermediate format with q-bits of precision: the "chance" of value failing is close to 1 in 2^(q-p). With 2^p values per exponent, you're going to see about 2^(2p-q) errors per exponent. In the case if Grisu, q is 64 and p is 53, for a total of about 2^42 errors. These numbers only give rough estimates, you'd have to verify them manually.