Faster float format

[newnon]

Have you seen this project? They have fast float to string conversions
https://code.google.com/p/stringencoders/

[vitaut]

Thanks for the link, @newnon. I haven't seen this before but I have plans to implement faster floating-point formatting, so it might be worth looking at the methods used in stringencoders too.

[vitaut]

There is also relevant discussion here: #116

[vitaut]

A custom implementation of floating-point formatting will also allow locale-independent formatting as in Python.

[NotImplemented]

@vitaut, what will be the fastest way to ramp-up and contribute?

[vitaut]

@NotImplemented Awesome that you interested in contributing! I think for this particular issue we need an implementation of one of the Grisu algorithms described in Printing Floating-Point Numbers Quickly and Accurately with Integers to be used instead of printf for floating-point formatting in https://github.com/cppformat/cppformat/blob/96d518f2f88c0c594e29f1603b89049694b3b6b0/format.cc#L549-L575. This might be a lot of work though. A somewhat simpler thing would be to implement a custom stream buffer (#92).

[NotImplemented]

@newnon, conversion in stringencoders is not correct. Have you seen lines in modp_dtoa()?

    if (prec < 0) {
        prec = 0;
    } else if (prec > 9) {
        /* precision of >= 10 can lead to overflow errors */
        prec = 9;
    }

Here is benchmark of several conversion algorithms I have done:

Algorithm	Speed
fmt::sprintf("%17g")	17.326
sprintf("%17g")	14.321
grisu2	2.145
grisu	8.872

[newnon]

@NotImplemented No i haven't look inside may be you are right and grisu2 is the fastest algorithm. Unfortunately i'm not to strong in math. Look on https://github.com/miloyip/dtoa-benchmark may be it possible to take some code from there

[manylegged]

FWIW googles double-conversion library is the fastest according to milo's benchmarks (the "milo" implementation he references is pretty much double-conversion with some special cases removed) and the interface looks like it would ammenable to formatting requirements. https://github.com/google/double-conversion

[NotImplemented]

We can try to facilitate it. The easiest is to start with %F and %f format specifiers.

[vitaut]

In addition to performance this will allow providing locale-independent formatting (#597).

[Kronuz]

This has a fmt::FormatDouble using Grisu2, it could be a start:
https://github.com/Kronuz/Xapiand/blob/master/src/milo.h

[Boddlnagg]

There is also https://github.com/ulfjack/ryu now

[lgritz]

It seems that floating point formatting is not yet locale-independent. Is that true? Is there any ETA on this being addressed? Or if not, is there a recommended workaround?

[vitaut]

Grisu2 implementation is almost complete, but I'm currently busy with preparing for the ISO C++ meeting in Kona, so no specific ETA. One possible workaround is setting the locale to "C".

[lgritz]

I'm concerned with a library, where the app or user may set it behind my back. Is there anyplace in the fmt code where I can doctor it to force "C" locale? I'm a little new to your code and I'm having trouble pinpointing the exact spot where it's retrieving or relying on the global locale.

[vitaut]

You can force locale for FP formatting just before snprintf is called here:

fmt/include/fmt/format-inl.h

Line 245 in e37d6a9

return precision < 0 ?

I'll be happy to accept a PR that does this (conditionally-compiled).

[vitaut]

More requests for locale-independent floating point formatting: https://twitter.com/lefticus/status/1075515381626753024

[vitaut]

As noticed by Stephan a while ago, Milo's implementation of Grisu2 has rounding issues: https://www.reddit.com/r/cpp/comments/9fiko6/fmt_version_52_released_with_up_to_5x_speedups/e5xmve6/, particularly on 1.9156918820264798e-56.

[vitaut]

{fmt} now uses Grisu for the default {} floating-point formatting. Enabling it for non-default formatting will be explored in #1032.

[Kronuz]

@vitaut, what about when you use printf ("%f") formatting? what does it use there?

[lgritz]

So just to confirm -- default "{}" formatting is now locale-independent, but non-default formatting (e.g. anything that tries to control the number of digits) is still locale-dependent?

[vitaut]

what about when you use printf ("%f") formatting? what does it use there?

Right now snprintf because it requires fixed precision, but I plan to adapt Grisu for %f as part of #1032.

default "{}" formatting is now locale-independent, but non-default formatting (e.g. anything that tries to control the number of digits) is still locale-dependent?

Yes, for platforms with IEEE floating point (pretty much all modern platforms).

[vitaut]

Added {fmt} to dtoa_benchmark and here are some results: http://fmtlib.net/unknown_mac64_clang10.0.html. TL;DR: {fmt} is ~13x faster than iostreams, ~10x faster than sprintf and roughly as fast as double_conversion (unsurprisingly because both implement the same algorithm). The implementation is not particularly optimized yet, so might be able to squeeze 20-30% more.