Hacker News Reader

Comment by lifthrasiir | Hacker News Reader

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, 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

View on HN

Author here. We intend for the GitHub repo (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).

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.

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.

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?

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.

> 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).

Reply on news.ycombinator.com