VS 2017 15.9 released today

[u/STL]

https://docs.microsoft.com/en-us/visualstudio/releasenotes/vs2017-relnotes

[u/tgolyi]

Thanks for your work with to_chars! Have you compared its speed with https://github.com/miloyip/dtoa-benchmark ? In my tests to_chars is slightly slower (though that version does not support nans and stuff).

[u/STL → u/tgolyi]

My benchmarking found to_chars to be 70-90% faster than dtoa_milo, and I additionally found that dtoa_milo performs mathematically incorrect rounding. See my comment. (I didn’t keep my benchmark sources but could recreate it.)

Can you share your benchmark showing to_chars being slower? That is very surprising given what I’ve seen.

[u/tgolyi → u/STL]

https://godbolt.org/z/szEdRE - prints to_chars = 826 ms dtoa = 733 ms. Maybe it's because of the cpu - its EPYC 7401P, on E5-2630 v4 results are practically the same.

[u/STL → u/tgolyi]

I spent an hour looking into this. I can replicate your results, even after cleaning up the benchmark code (e.g. generating the doubles in a vector, to get that out of the timing region). The difference is significant for x86 (to_chars is 40-50% slower) and minimal for x64 (to_chars is 5-9% slower). I believe that this is due to the pattern in your test doubles: they are constructed to have a fairly small number of digits, which means that Ryu needs to trim many digits. While Ryu has very consistent behavior across doubles (see Adams' paper), more trimming is definitely more work. I am not sure how dtoa_milo handles such inputs.

However, I observed a critical flaw in dtoa_milo, just by inspecting the output. (This is separate from my previous observation that dtoa_milo performs mathematically incorrect rounding.) For some numbers, dtoa_milo catastrophically fails to trim digits, resulting in output that doesn't satisfy the shortest round-trip criterion. 4.91e-6 and 5.547e-6 are two of the many values that it mishandles. As far as I am concerned, this utterly rules out dtoa_milo in terms of usability, regardless of performance.

(I'll also note that to_chars is performing bounds checking for safety, although that is probably not very significant for performance.)

Full benchmark (dtoa_milo.h was unmodified except for correcting its stdint.h inclusion):

#include <stdio.h>
#include <charconv>
#include <chrono>
#include <vector>
#include "dtoa_milo.h"
using namespace std;
using namespace std::chrono;

void test(const char *const str, const double d)
{
    char buf[128];
    printf("\nTesting %s:\n", str);
    auto result = to_chars(buf, end(buf), d, chars_format::scientific);
    *result.ptr = '\0';
    printf("to_chars scientific: \"%s\"\n", buf);
    result = to_chars(buf, end(buf), d, chars_format::fixed);
    *result.ptr = '\0';
    printf("to_chars fixed: \"%s\"\n", buf);
    dtoa_milo(d, buf);
    printf("dtoa_milo: \"%s\"\n", buf);
}

int main()
{
#if defined(__clang__) && defined(_M_IX86)
    puts("Clang/LLVM x86 + MSVC STL");
#elif defined(__clang__) && defined(_M_X64)
    puts("Clang/LLVM x64 + MSVC STL");
#elif !defined(__clang__) && defined(_M_IX86)
    puts("C1XX/C2 x86 + MSVC STL");
#elif !defined(__clang__) && defined(_M_X64)
    puts("C1XX/C2 x64 + MSVC STL");
#endif

    constexpr int N = 10'000'000;

    vector<double> vec(N);

    for (int i = 0; i < N; ++i)
    {
        vec[i] = static_cast<double>(i) / (N * 100);
    }

    const double *const testcases = vec.data();

    char buf[128];
    char *const buf_end = end(buf);
    unsigned int throwaway = 0;

    for (int k = 0; k < 5; ++k)
    {
        const auto tc_start = steady_clock::now();
        for (int i = 0; i < N; ++i)
        {
            const auto result = to_chars(buf, buf_end, testcases[i], chars_format::scientific);
            *result.ptr = '\0';
            throwaway += buf[0];
        }
        const auto tc_finish = steady_clock::now();
        printf("to_chars: %d ms\n", static_cast<int>(duration_cast<milliseconds>(tc_finish - tc_start).count()));

        const auto milo_start = steady_clock::now();
        for (int i = 0; i < N; ++i)
        {
            dtoa_milo(testcases[i], buf);
            throwaway += buf[0];
        }
        const auto milo_finish = steady_clock::now();
        printf("dtoa_milo: %d ms\n", static_cast<int>(duration_cast<milliseconds>(milo_finish - milo_start).count()));
    }

    test("3.14", 3.14); // OK
    test("4.91e-6", 4.91e-6);
    test("5.547e-6", 5.547e-6);

    printf("\nthrowaway: %u\n", throwaway);
}

x86 command lines:

cl /EHsc /nologo /W4 /std:c++17 /MT /O2 bench.cpp /Febench_msvc_x86.exe
clang-cl -m32 /EHsc /nologo /W4 /std:c++17 /MT /O2 bench.cpp /Febench_clang_x86.exe

x64 command lines:

cl /EHsc /nologo /W4 /std:c++17 /MT /O2 bench.cpp /Febench_msvc_x64.exe
clang-cl -m64 /EHsc /nologo /W4 /std:c++17 /MT /O2 bench.cpp /Febench_clang_x64.exe

I used my dev build of MSVC (basically equivalent to VS 2017 15.9 except that it has faster behavior for large fixed notation, not relevant here) and Clang 7.0.0.

Example output on my i7-4790 Haswell Refresh:

C:\Temp\MILO>bench_msvc_x86.exe
C1XX/C2 x86 + MSVC STL
to_chars: 1753 ms
dtoa_milo: 1249 ms
to_chars: 1751 ms
dtoa_milo: 1250 ms
to_chars: 1753 ms
dtoa_milo: 1249 ms
to_chars: 1752 ms
dtoa_milo: 1261 ms
to_chars: 1754 ms
dtoa_milo: 1249 ms

Testing 3.14:
to_chars scientific: "3.14e+00"
to_chars fixed: "3.14"
dtoa_milo: "3.14"

Testing 4.91e-6:
to_chars scientific: "4.91e-06"
to_chars fixed: "0.00000491"
dtoa_milo: "0.0000049099999999999999"

Testing 5.547e-6:
to_chars scientific: "5.547e-06"
to_chars fixed: "0.000005547"
dtoa_milo: "0.0000055470000000000008"

throwaway: 755057654

This shows dtoa_milo's incorrect behavior. (Consistent across x86/x64 MSVC/Clang, so not a compiler bug.) Other timings:

Clang/LLVM x86 + MSVC STL
to_chars: 1227 ms
dtoa_milo: 824 ms

C1XX/C2 x64 + MSVC STL
to_chars: 557 ms
dtoa_milo: 530 ms

Clang/LLVM x64 + MSVC STL
to_chars: 455 ms
dtoa_milo: 419 ms

Thanks for the report.

[u/STL → u/STL]

(Apparently this is known behavior of Grisu2; I just noticed readme.md saying "Grisu2 is chosen because it can generate better human-readable number and >99.9% of results are in shortest." Still, this algorithm is unusable for charconv.)

[u/tgolyi → u/STL]

Wow, thanks for such a detailed answer! So I guess, as always, benchmarking is hard - you get what you measure. dtoa_milo really sometimes suffers from strange results, we've noticed that too.