Page MenuHomePhabricator

Microsoft's floating-point to_chars powered by Ryu and Ryu Printf
ClosedPublic

Authored by Mordante on Nov 22 2019, 8:21 PM.

Details

Summary

Microsoft would like to contribute its implementation of floating-point to_chars to libc++. This uses the impossibly fast Ryu and Ryu Printf algorithms invented by Ulf Adams at Google. Upstream repos: https://github.com/microsoft/STL and https://github.com/ulfjack/ryu .

Licensing notes: MSVC's STL is available under the Apache License v2.0 with LLVM Exception, intentionally chosen to match libc++. We've used Ryu under the Boost Software License.

This patch contains minor changes from Jorg Brown at Google, to adapt the code to libc++. He verified that it works in Google's Linux-based environment, but then I applied more changes on top of his, so any compiler errors are my fault. (I haven't tried to build and test libc++ yet.) Please tell me if we need to do anything else in order to follow https://llvm.org/docs/DeveloperPolicy.html#attribution-of-changes .

Notes:

  • libc++'s integer charconv is unchanged (except for a small refactoring). MSVC's integer charconv hasn't been tuned for performance yet, so you're not missing anything.
  • Floating-point from_chars isn't part of this patch because Jorg found that MSVC's implementation (derived from our CRT's strtod) was slower than Abseil's. If you're unable to use Abseil or another implementation due to licensing or technical considerations, Microsoft would be delighted if you used MSVC's from_chars (and you can just take it, or ask us to provide a patch like this). Ulf is also working on a novel algorithm for from_chars.
  • This assumes that float is IEEE 32-bit, double is IEEE 64-bit, and long double is also IEEE 64-bit.
  • I have added MSVC's charconv tests (the whole thing: integer/floating from_chars/to_chars), but haven't adapted them to libcxx's harness at all. (These tests will be available in the microsoft/STL repo soon.)
  • Jorg added int128 codepaths. These were originally present in upstream Ryu, and I removed them from microsoft/STL purely for performance reasons (MSVC doesn't support int128; Clang on Windows does, but I found that x64 intrinsics were slightly faster).
  • The implementation is split into 3 headers. In MSVC's STL, charconv contains only Microsoft-written code. xcharconv_ryu.h contains code derived from Ryu (with significant modifications and additions). xcharconv_ryu_tables.h contains Ryu's large lookup tables (they were sufficiently large to make editing inconvenient, hence the separate file). The xmeow.h convention is MSVC's for internal headers; you may wish to rename them.
  • You should consider separately compiling the lookup tables (see https://github.com/microsoft/STL/issues/172 ) for compiler throughput and reduced object file size.
  • See https://github.com/StephanTLavavej/llvm-project/commits/charconv for fine-grained history. (If necessary, I can perform some rebase surgery to show you what Jorg changed relative to the microsoft/STL repo; currently that's all fused into the first commit.)

Questions:

  1. MSVC's STL conventionally uses _Single_uppercase_ugly identifiers, but xcharconv_ryu.h (and tables) also use __double_lowercase_ugly in Ryu-derived code, for ease of search-and-replacing (and comparing) with upstream Ryu. (That file still uses _Single_uppercase_ugly for additions; it looks weird but helped me keep track of what surgery I was performing.) I've compared these files against MSVC's and the diffs are very readable, so I'd like to keep the identifiers following the same convention so our codebases don't diverge too much. Does libc++ want to use __double_lowercase_ugly identifiers? (But apparently you use _Single_uppercase_ugly for template parameters?) If so, I can change the identifiers in this patch, and in microsoft/STL charconv upstream.
  2. I have included Microsoft's Apache+LLVM and Ulf's Boost banners, as they have appeared in the microsoft/STL repo. Would you like something different?

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes

Disable test on AIX for now.

Mordante planned changes to this revision.Nov 17 2021, 8:59 AM
Mordante added inline comments.
libcxx/src/include/ryu/d2fixed.h
54

@ldionne Do you have an idea what's wrong here. I declare this function here and define it in src/ryu/d2fixed.cpp. Do you see anything wrong with this? Am I missing some visibility macro's?

The reason I ask is since this cause causes a ICE in Clang when building with -DCMAKE_BUILD_TYPE=RelWithDebInfo -DLLVM_ENABLE_ASSERTIONS=ON. This combination is used on our CI's bootstrap build.

ldionne added inline comments.Nov 17 2021, 12:18 PM
libcxx/src/include/ryu/d2fixed.h
54

Is this supposed to be exported from the dylib? If so, it needs _LIBCPP_FUNC_VIS IIRC. Otherwise, no visibility macro should be fine (it will automatically be hidden since we build the dylib with -fvisibility=hidden, which you should be able to confirm by looking at the build log).

I think the best course of action here would be to reduce the Clang ICE, since an ICE is always a bug.

Mordante added inline comments.Nov 17 2021, 1:22 PM
libcxx/src/include/ryu/d2fixed.h
54

It's supposed to be hidden in the dylib. This is part of the functions that we want to hide to allow us to change the implementation of the floating point algorithm without introducing ABI breaks. The dylib is indeed build with -fvisibility=hidden.

I agree and ICE is a bug and I want to report it after reducing it. For now I wanted to make sure I didn't overlook anything obvious. Thanks for your input.

Mordante marked 7 inline comments as done.Nov 23 2021, 11:43 AM
Mordante added inline comments.
libcxx/include/charconv
117

Since std::to_chars and std::to_string are both in the dylib this isn't an issue anymore.

libcxx/src/include/ryu/d2fixed.h
54

Is this supposed to be exported from the dylib? If so, it needs _LIBCPP_FUNC_VIS IIRC. Otherwise, no visibility macro should be fine (it will automatically be hidden since we build the dylib with -fvisibility=hidden, which you should be able to confirm by looking at the build log).

I think the best course of action here would be to reduce the Clang ICE, since an ICE is always a bug.

Reduced and reported as https://bugs.llvm.org/show_bug.cgi?id=52584

libcxx/test/std/utilities/charconv/charconv.msvc/double_scientific_precision_to_chars_test_cases_1.hpp
40

@STL_MSFT If you're willing to update the headers in Microsoft's that would be great. Then I can sync them.

Mordante updated this revision to Diff 389275.Nov 23 2021, 11:45 AM
Mordante marked an inline comment as done.

Rebased.
Partial update of the tests with MSVC STL, other changes need more effort.
Polishing and addressing review comments.

ldionne accepted this revision.Nov 23 2021, 12:23 PM

LGTM with comments, assuming CI passes. Also, please add a release note.

I want to thank everybody who got involved in shipping this, I'm glad we finally finished this up!

I know there's been some progress on algorithms to implement this in the recent years -- it should always be possible to swap the implementation under the hood since everything is implemented in the dylib, and the ABI boundary is not going to change.

libcxx/CREDITS.TXT
29

@Mordante You might want to credit yourself for the part of the work you did on landing this.

libcxx/include/charconv
611

Since those are libc++'s own declarations, we should use libc++ style and use __first instead of _First. Similarly, let's put _LIBCPP_AVAILABILITY_TO_CHARS_FLOATING_POINT _LIBCPP_FUNC_VIS on its own line.

Finally, I think we can remove the bit of the license here as long as we retain the one in the source file?

libcxx/lib/abi/CHANGELOG.TXT
49
libcxx/test/std/utilities/charconv/charconv.msvc/test.pass.cpp
12–14

This is technically inaccurate since it hasn't landed yet period, let's change it to my suggestion.

I'll fix it up once it lands in one of our OSes.

22

Do you know why it's failing on AIX? Just curious.

Mordante updated this revision to Diff 389518.Nov 24 2021, 9:13 AM

Attempt to fix the CI.

Mordante updated this revision to Diff 389543.Nov 24 2021, 10:31 AM

Attempt to fix the MinGW build.

Mordante updated this revision to Diff 389549.Nov 24 2021, 10:38 AM

Fix a typo.

Mordante updated this revision to Diff 389585.Nov 24 2021, 12:01 PM

Attempt to fix the failed test on MinGW.

mstorsjo added inline comments.Nov 24 2021, 2:47 PM
libcxx/src/include/ryu/d2s_intrinsics.h
50

I think you could loosen this into #if defined(_M_X64) && defined(_MSC_VER); _LIBCPP_COMPILER_MSVC is only defined when building with the actual MSVC, not clang-cl impersonating MSVC. (And the real MSVC isn't supported for building libcxx in practice.)

Or did this codepath give errors when built with clang-cl before?

72

Isn't this condition kinda opposite to what you suggest in the comment? I.e. the comment writes (and we discussed) that mingw does support int128, but then you check defined(_M_X64) && !defined(__MINGW32__) - I believe this codepath isn't used here as intended.

Actually, I would suggest simplifying this whole condition into this:

#elif defined(__SIZEOF_INT128__) && ( \
    (defined(__clang__) && !defined(_MSC_VER)) || \
    (defined(__GNUC__) && !defined(__clang__) && !defined(__CUDACC__)))

Thus, if we have __SIZEOF_INT128__ defined (this should exclude all 32 bit targets, so we don't need to check for any 64 bit architecture specifically). This check in itself is almost enough as such. But then as a extra requirement, we'd only try this if we also have specifically clang or gcc. And for clang, we'd exclude building in MSVC mode, where we might not have all the runtime functions available. (If it turns out that the code below doesn't actually generate any calls to runtime helpers, we wouldn't need the check for _MSC_VER at all.)

Or it could even be as simple as this:

#elif !defined(_LIBCPP_HAS_NO_INT128) && !defined(_MSC_VER)

We already have _LIBCPP_HAS_NO_INT128 in libcxx, and it might be good to honor it. However that define is only based on compiler support - in MSVC mode, it doesn't know that we actually don't have all the necessary runtime functions.

We have __uint128 support in clang or gcc or MinGW 64

Those three aren't really three comparable things - when building for mingw, you'd be using either clang or gcc. Maybe "We have __uint128 support in gcc and clang, except when in MSVC mode" (or clang-cl instead of MSVC)?

Mordante marked 6 inline comments as done.Nov 30 2021, 11:46 AM

LGTM with comments, assuming CI passes. Also, please add a release note.

Good point!

libcxx/CREDITS.TXT
29

Good point. I even discovered I never added myself to the credits.

libcxx/src/include/ryu/d2s_intrinsics.h
50

I only had an issue when the guard was #ifdef _M_X64. I'll apply your suggestion and let the CI be the judge.

72

I've changed it to your first suggestion, that matches the original code better. I could use _LIBCPP_HAS_NO_INT128 but that's defined in terms of __SIZEOF_INT128__. I prefer to keep this as much to the original code submitted by Microsoft to keep the size of the diff with their code-base as small as possible.

libcxx/test/std/utilities/charconv/charconv.msvc/test.pass.cpp
12–14

Good to know, I wasn't sure what the process was to make sure it's enabled in the next Apple product.

Mordante marked 4 inline comments as done.Nov 30 2021, 11:48 AM
Mordante updated this revision to Diff 390774.Nov 30 2021, 11:48 AM

Rebased and addresses review comments.
I really like to test the dylib changes in the CI.

This revision was not accepted when it landed; it landed in state Needs Review.Dec 5 2021, 4:25 AM
This revision was automatically updated to reflect the committed changes.
phosek added a subscriber: phosek.Dec 6 2021, 12:09 PM

This broke all our builders that use the bootstrapping build due to PR52584. I saw you disabled the use of debugging information for libc++ ci in 15495be014032339600cda7770d7bf45dfb10d54, but there are other projects that build LLVM from source at HEAD which will be affected by that issue. I'd prefer if this change was reverted until PR52584 is addressed or we find some other workaround.

phosek added a comment.Dec 6 2021, 6:43 PM

This broke all our builders that use the bootstrapping build due to PR52584. I saw you disabled the use of debugging information for libc++ ci in 15495be014032339600cda7770d7bf45dfb10d54, but there are other projects that build LLVM from source at HEAD which will be affected by that issue. I'd prefer if this change was reverted until PR52584 is addressed or we find some other workaround.

@ldionne Would it be fine with you if I revert this change? I haven't heard back from @Mordante and libc++ build is still failing all our builders because of Clang ICE that hasn't yet been addressed. We cannot disable the use of debug info because we use it for symbolization, and we don't want to disable assertions because we might then miss other issues.

This broke all our builders that use the bootstrapping build due to PR52584. I saw you disabled the use of debugging information for libc++ ci in 15495be014032339600cda7770d7bf45dfb10d54, but there are other projects that build LLVM from source at HEAD which will be affected by that issue. I'd prefer if this change was reverted until PR52584 is addressed or we find some other workaround.

@ldionne Would it be fine with you if I revert this change? I haven't heard back from @Mordante and libc++ build is still failing all our builders because of Clang ICE that hasn't yet been addressed. We cannot disable the use of debug info because we use it for symbolization, and we don't want to disable assertions because we might then miss other issues.

Yes, please revert the change. We will investigate tomorrow. I think @Mordante is in a different time zone.

Mordante reopened this revision.Dec 7 2021, 8:37 AM

@phosek Thanks for reverting the patch. I'm in a different timezone and just read your message.

dblaikie added inline comments.
libcxx/src/include/to_chars_floating_point.h
120

This bit_cast means the to_chars functionality (intended to be available in C++17 or above) fails when used in a C++17 context, since bit_cast is only available in C++20 onwards - at least in an internal Google build this seems to be the case (possible there's something esoteric there).

Does that seem plausible/a problem that needs fixing upstream here?

dblaikie added inline comments.Dec 7 2021, 4:49 PM
libcxx/src/include/to_chars_floating_point.h
120

Looking back at some of the review discussion, it looks like this was deemed OK because bit_cast would be available in the dylib even when compiling in an earlier language mode? But the declaration of the function is still gated on C++20 or above here: https://github.com/llvm/llvm-project/blob/572d1ecccc473ba4ddb46dd04759dc2e336f0e1c/libcxx/include/__bit/bit_cast.h#L22 so this usage fails to compile before ever worrying about whether it links correctly.

STL_MSFT added inline comments.Dec 7 2021, 5:32 PM
libcxx/src/include/to_chars_floating_point.h
120

Good question about upstream - it's unaffected as we used an internal helper _Bit_cast precisely so that we could have access to it in C++17 mode. This is https://github.com/microsoft/STL/blob/3c2fd04d441d46ec9d914d9cbb621a3bac96c3a5/stl/inc/charconv#L2081 and https://github.com/microsoft/STL/blob/3c2fd04d441d46ec9d914d9cbb621a3bac96c3a5/stl/inc/xutility#L62-L74 .

dblaikie added inline comments.Dec 7 2021, 6:08 PM
libcxx/src/include/to_chars_floating_point.h
120

The code that was committed doesn't appear to use that _Bit_cast internal helper.
The helper and its use seemed to have been removed in this iteration of the proposed patch: https://reviews.llvm.org/D70631?vs=380156&id=380203#toc
The final commited code ( https://reviews.llvm.org/rGa8025e06fc0f2fe1bbee9e1a6f15c336bfbdcb05 ) have no mention of _Bit_cast and use _VSTD::bit_cast in several places, including this one (line 119 here that I'm commenting on).

Am I misunderstanding something?

floam added inline comments.Dec 7 2021, 6:55 PM
libcxx/src/include/to_chars_floating_point.h
120

@dblaikie They are saying that is how Microsoft solved that quandary in their product.

STL_MSFT added inline comments.Dec 7 2021, 7:49 PM
libcxx/src/include/to_chars_floating_point.h
120

I think you're completely correct - I was merely clarifying that there is no issue that needs to be fixed upstream here, it was introduced during the later changes here.

dblaikie added inline comments.Dec 7 2021, 10:36 PM
libcxx/src/include/to_chars_floating_point.h
120

Ah, sorry, I meant "upstream" as in "LLVM" here (as contrasted to "Downstream" being "inside google" - ie: something we need to fix on our end internally).

Sounds like we're on the same page here. Sorry for the confusion.

Mordante marked 7 inline comments as done.Dec 8 2021, 9:36 AM
Mordante added inline comments.
libcxx/src/include/to_chars_floating_point.h
120

This header is part of the dylib and not part of a libc++ header shipped to customers.
Since the dylib is always build with C++20 it's safe to use bit_cast here.

The public std::to_chars for floating-point is available in C++17 and newer.
There are lit tests ensuring the function works correctly in C++17, C++20, and C++2b.

This revision was not accepted when it landed; it landed in state Needs Review.Dec 12 2021, 7:39 AM
This revision was automatically updated to reflect the committed changes.

Relanded since the bug blocking it has been resolved.

dblaikie added inline comments.Dec 12 2021, 10:07 AM
libcxx/src/include/to_chars_floating_point.h
120

Ah, sure, thanks. Yeah, looks like we might be building even the library with std=gnu++17 internally & probably need to fix that. Will look into it on our side.

Let's not forget to restore Debug information in the bootstrapping build.

Mordante marked an inline comment as done.Dec 13 2021, 9:28 AM

Let's not forget to restore Debug information in the bootstrapping build.

I already did that after it was clear the bug needed to be resolved before this patch could land.
https://reviews.llvm.org/rGade336dee4762572bbd03085d96ce72bdbbb123b

libcxx/src/include/to_chars_floating_point.h
120

Thanks. I'm surprised this works since the CMake file should force C++20. I expected the format.cpp to require C++20, but it seems that is guarded. (That code was added while we didn't require C++20 yet, but these guards should be removed.)

dblaikie added inline comments.Dec 13 2021, 10:18 AM
libcxx/src/include/to_chars_floating_point.h
120

The issue is that we don't use CMake internally, but Bazel instead - apparently we've been "getting away" with building in C++17 mode until this change. But that's just a bug on our side to get fixed. Sorry for the noise in the review & thanks for walking me through the issue/pointing out the distinctions here.

bcain added a subscriber: bcain.Feb 22 2022, 7:34 AM

This test libcxx/test/std/utilities/charconv/charconv.msvc/test.cpp fails downstream for us w/Hexagon SDK. It's a subtle nit from the compiler regarding format specifiers.

I can post a patch to change the test to use the inttypes.h PRI___ specifiers instead. But it occurs to me: since this is a lit test, are the printouts only used for debugging? Should/could we purge them or hide them behind a debug guard? Does this test come from a third party repository that we want to stay in sync with? The commit regards printf implementation -- are any of the calls to printf part of the intended scope of the test? If not, could/should the test be redesigned to use C++ streams instead?

Apologies for the lack-of-context questions.

Here's the downstream failures btw (both unsigned long and unsigned int are 32-bits on this target):

.../tools/llvm-top/libcxx/test/std/utilities/charconv/charconv.msvc/test.cpp:94:23: error: format specifies type 'unsigned int' but the argument has type 'unsigned long' [-Werror,-Wformat]
        printf("%u ", elem);
                ~~    ^~~~
                %lu
.../tools/llvm-top/libcxx/test/std/utilities/charconv/charconv.msvc/test.cpp:569:56: error: format specifies type 'unsigned int' but the argument has type 'uint32_t' (aka 'unsigned long') [-Werror,-Wformat]
        fprintf(stderr, "%s failed for 0x%08X\n", msg, bits);
                                         ~~~~          ^~~~
                                         %08lX
.../tools/llvm-top/libcxx/test/std/utilities/charconv/charconv.msvc/test.cpp:1096:43: error: format specifies type 'unsigned int' but the argument has type 'unsigned long' [-Werror,-Wformat]
    printf("Randomized test cases: %u\n", PrefixesToTest * Fractions);
                                   ~~     ^~~~~~~~~~~~~~~~~~~~~~~~~~
                                   %lu

This test libcxx/test/std/utilities/charconv/charconv.msvc/test.cpp fails downstream for us w/Hexagon SDK. It's a subtle nit from the compiler regarding format specifiers.

This was my fault, sorry about that - I forgot that uint32_t is slightly platform-dependent.

I can post a patch to change the test to use the inttypes.h PRI___ specifiers instead.

I think that'd be the least invasive fix, yeah.

But it occurs to me: since this is a lit test, are the printouts only used for debugging?

In general, they're needed to understand test failures - particularly the ones that say "this value failed, it's a randomized test, so report this to the maintainers and don't just rerun it".

Does this test come from a third party repository that we want to stay in sync with?

Yes, https://github.com/microsoft/STL . We'd be happy to review and merge a PR there to keep it in sync with libcxx.

The commit regards printf implementation -- are any of the calls to printf part of the intended scope of the test? If not, could/should the test be redesigned to use C++ streams instead?

printf/fprintf isn't essential, we could also use iostreams, but iostreams manipulators (for the equivalent of %016llX) are a pain to remember (even for a Standard Library maintainer, heh) so I used printf for convenience.

(There are sprintf_s calls in the MSVC implementation that verify that to_chars prints floating-point values in the same way - those are essential since we don't want to compare against the iostreams implementation)

I can post a patch to change the test to use the inttypes.h PRI___ specifiers instead.

I think that'd be the least invasive fix, yeah.

FWIW, I would vastly rather see printf("%zu whatever", size_t(x)) instead of printf("%" PRIu32 " whatever", x). Keeps the message's string literal all in one piece, doesn't suffer UDL-related lexer issues, and doesn't require intimate knowledge of <stdint.h> or whatever.

Mordante marked an inline comment as done.Feb 23 2022, 9:53 AM

Yes please provide a patch, can you supply one to libc++ and one to MSVC STL? Thanks.

Yes please provide a patch, can you supply one to libc++ and one to MSVC STL? Thanks.

I will provide a patch.

It is considerably easier for me to supply it to libc++ because our contributions are permitted there already. I don't think it will be quite so easy to get MSVC STL repo added. But the license is the same, so maybe.