This is an archive of the discontinued LLVM Phabricator instance.

[libc++] [P1614] Implement the first half of [cmp.alg]: strong_order, weak_order, partial_order.
ClosedPublic

Authored by Quuxplusone on Sep 29 2021, 10:36 AM.

Details

Summary

Re the behavior of std::strong_order for floating-point types, see
https://stackoverflow.com/questions/59348310/how-to-implement-the-totalorder-predicate-for-floating-point-values
https://stackoverflow.com/questions/69068075/what-is-the-purpose-of-if-x-and-y-represent-the-same-floating-point-datum-i
https://quuxplusone.github.io/blog/2021/09/05/float-format/

There's still an open question of what it should do for long double; I'm proposing to just leave it unimplemented in hopes that someone who cares about it will provide an implementation.

This PR does not implement std::strong_order_fallback et al. That will be a second PR. (It is now D111514.)

Diff Detail

Event Timeline

Quuxplusone requested review of this revision.Sep 29 2021, 10:36 AM
Herald added 1 blocking reviewer(s): Restricted Project. · View Herald TranscriptSep 29 2021, 10:36 AM
libcxx/include/__utility/priority_tag.h
22–23

It probably makes sense to rename this from _PriorityTag to __priority_tag, especially in light of the _EnableIf renaming. @ldionne, opinion?

Mordante resigned from this revision.Oct 2 2021, 6:28 AM

For long double would it be possible to use an __int128_t when available? (Obviously this can't be bit_cast-ed.)
I've not looked at the tests in detail, but didn't see any obvious issues.

I'm not familiar enough with the exact details of floating point values, so I haven't validated whether this is correct. Other than that the implementation seems good to me.

libcxx/include/__compare/partial_order.h
39

I like this manually formatting a lot! Would it make sense to guard this code against clang-format, just in case we want to enable it for the entire libc++ in the future?

libcxx/include/__compare/strong_order.h
97

I'm not familiar with this floating point code. But wouldn't this assert trigger on system where sizeof(int) == 8 && sizeof(float) == 4. Isn't it possible to test with int32_t and int64_t?

Quuxplusone marked 2 inline comments as done.Oct 2 2021, 7:40 AM
Quuxplusone added inline comments.
libcxx/include/__compare/partial_order.h
39

This is our standard formatting now for "you must write it three times" functions; see D108144. (Which came out of discussion on some other review.)
We guard it against clang-format in the same way as we guard the entire rest of libc++: don't run clang-format on these files, and if someone accidentally (or just naively) does, then we hope to catch it in code review.
(We could start wrapping whole files in clang-format off comments, but: That's an O(n) solution to an O(1) problem. And, it works only because clang-format is a monoculture. If anyone ever writes a second C++ formatter, we'd have to guard against that one, too. To really ensure that nobody can mess with our aesthetics, we'd put in some sort of technological "do-not-sed" and "do-not-awk" protection... I'm having flashbacks to DeCSS here... ;))

libcxx/include/__compare/strong_order.h
97

This assert would trigger on such systems, if any such systems exist.
On the one hand, I can't think of any reason for int to be 64-bit, unless char is also 64-bit, in which case float must also be at least 64-bit. So it makes more sense to wait and see if any such systems use libc++, and then if they do, they can submit a patch to use (i.e. conditional_t against) their particular type that works.
On the other hand, I actually did use int32_t and int64_t on lines 52–58, so why do I switch back to the built-in types here? I forget. It's particularly weird that I'm testing three types when in practice they'll only have two different sizes (32 and 64). So probably I should just change this to test only int32_t and int64_t.
I dunno; anyone else want to be the tiebreaker?

libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp
449

@Mordante writes:

For long double would it be possible to use an __int128_t when available? (Obviously this can't be bit_cast-ed.)

Yeah, long double on x86-64 has 80 value bits and 48 padding bits, so it can't be bit-casted straight to 128-bit __int128_t. We can bit-cast it to an array of char and then inspect the bytes individually; but then we have to be really confident about how they're arranged in memory (endianness? which side does the padding wind up on?) and I haven't done that homework.
Orthogonally, on non-IEC559 (non-IEEE754) platforms like I believe PPC64, long double is actually represented in memory as a pair of IEEE754 double values with different exponents, and then to find the long double's value, you add them together. In which case I haven't even bothered to think about what the correct strong_order algorithm would look like. (It might be exactly what I've got for the non-IEEE754 codepath, and then still tiebroken by "bit_cast and memcmp." But I haven't thought about it.)
So I would prefer to leave long double unimplemented in this PR; and then either we solicit an implementation from someone who claims to know what they're doing, or else eventually I get bored and submit something (and then we wait for bugfixes from someone who knows what they're doing). :)

Mordante added inline comments.Oct 4 2021, 11:45 AM
libcxx/include/__compare/partial_order.h
39

Fair point. I recall some of these discussions and the nice link you posted about a lightning talk regarding this issue.

libcxx/include/__compare/strong_order.h
97

I prefer the int32_t and int64_t especially since you used that earlier in the code.

libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp
449

So I would prefer to leave long double unimplemented in this PR; and then either we solicit an implementation from someone who claims to know what they're doing, or else eventually I get bored and submit something (and then we wait for bugfixes from someone who knows what they're doing). :)

Sounds fine to me to not do long double in this PR. That sounds like the SO method, do it wrong and wait for people pointing out why it's wrong ;-)

Quuxplusone marked 3 inline comments as done.

Rename _PriorityTag to __priority_tag.
In partial_order.pass.cpp, work around GCC's inability to compare NaN against non-NaN at compile time.
I bet this still needs a bunch of UNSUPPORTED: libcpp-no-concepts etc. for Apple; I'll let buildkite tell me.

Quuxplusone added inline comments.Oct 9 2021, 3:10 PM
libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp
354

This fails for float on the 32-bit x86 buildkite:
https://reviews.llvm.org/harbormaster/unit/view/1389305/
(And maybe other cases would fail after this one, but buildkite won't tell us.)
Anyone got any leads on why this might be? When I try it on Godbolt, it seems OK: https://godbolt.org/z/7eEcnWev7

Quuxplusone edited the summary of this revision. (Show Details)

Skip signaling-NaN tests on x86-32 (x87 floating point).

libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp
354

Now I can reproduce it: https://godbolt.org/z/f17a5GzM9
The problem is that when -m32, the bit-pattern of numeric_limits<float>::signaling_NaN() depends on optimization level. At -O1 the bit-pattern is 0x7fa00000. At -O0 it is 0x7fe00000, which is actually not a signaling NaN at all!
This seems to be a problem with __builtin_nansf("") on -m32: https://godbolt.org/z/cTjqxeG1T
And googling that turns up: https://stackoverflow.com/questions/22816095/signalling-nan-was-corrupted-when-returning-from-x86-function-flds-fstps-of-x87

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57484#c12

This issue is unfortunately unfixable. x87 and x86-32 ABI are just not designed to handle all details of IEEE 754 standard.

So it looks like the appropriate workaround here is just to ifdef out the offending NaN tests on x86-32 targets.

strong_order depends on compare_three_way depends on three_way_comparable_with depends on Concepts, so UNSUPPORTED: libcpp-no-concepts and guard the header too.

mumbleskates added inline comments.
libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp
449

I could gin up some asserts for confirming the standard layout of an intel long double. Not 100% sure how to do that constexpr but I think it's doable.

long double on my ARM device(s) is a true iec559 quad precision type, and should be implementable in the same way as the others by bit_casting to __int128_t in this layout.

I find that layout for PPC long double hilarious, but thankfully the standard specifies that strong_order is not required at all for non-iec559 numeric types, so we can simply leave it out and don't have to worry about ever implementing those types unless it is added to the standard draft as a mandate in the future.

All this to say I'm happy to help pushing on this todo for our supported platforms, and I agree that we probably shouldn't get it in with this diff.

mumbleskates added inline comments.Oct 11 2021, 2:14 PM
libcxx/include/__compare/strong_order.h
97

Would it also be sensible for us to static_assert that quiet_NaN() and signaling_NaN() are ordered correctly by strong_order, or even perhaps SFINAE via a wrapper function that participates only when the behavior is as expected?

libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp
349–352

Now that we have bit_cast, is it not possible for us to flip the sign by round tripping it it through an integer and xor'ing it with the bits for -0.0 at compile time? (I am pretty sure that -0.0 has, in all iec559 encodings binary and decimal, only the sign bit set and all others zeroed out, which can also be checked via has_single_bit).

Quuxplusone marked an inline comment as done.Oct 11 2021, 3:14 PM
Quuxplusone added inline comments.
libcxx/include/__compare/strong_order.h
97

Would it also be sensible for us to static_assert that quiet_NaN() and signaling_NaN() are ordered correctly by strong_order

Isn't that covered in the tests below? (I'll comment on the exact line.)

libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp
349–352

It appears that we can! https://godbolt.org/z/z163Ges6G
However, this requires a bit of metaprogramming to determine an integral type with the same width as F, and that's a bit more complicated than I really want to put into this test file. It would basically be repeating the conditional_t chain from lines 91–94 of strong_order.h.

auto copysign = [](F f, int sign) {
    using I = std::conditional_t<sizeof(F) == sizeof(int32_t), int32_t,
        std::conditional_t<sizeof(F) == sizeof(int64_t), int64_t, void>>;
    I mask = std::bit_cast<I>(F(-0.0));
    if (sign < 0) {
        return std::bit_cast<F>(std::bit_cast<I>(to) | mask);
    } else {
        return std::bit_cast<F>(std::bit_cast<I>(to) & ~mask);
    }
};
387

@mumbleskates: This is the exact line that compares quiet_NaN() against signaling_NaN() (and see line 395 too).
Notice that we're testing "positive quiet NaN" (which might not be literally quiet_NaN()) against "positive signaling NaN" (which might not be literally signaling_NaN()), and lines 361 and 370 are testing "negative quiet" against "negative signaling"; we never literally test the numeric_limits values directly. The Standard doesn't mandate (AFAIK) whether numeric_limits<F>::quiet_NaN() should have a positive or negative sign bit.

mumbleskates added inline comments.Oct 11 2021, 6:22 PM
libcxx/include/__compare/strong_order.h
97

I was thinking about in the library itself, such that the assertion runs at compile time for the user rather than only in our test suite's platform coverage. If that isn't part of our mandate of rigor and our CI tests are adequate for deploying the code everywhere then I suppose that would answer my question.

libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp
349–352

Okay, that's pretty cool! and could be helpful, depending on your thoughts on my other comments here.

387

Yeah, this all makes sense. I was mostly thinking in terms of getting this to also run statically, or check at our strong_ordering header's compile time whether these basic assumptions about the natural ordering of float payloads hold. Again not sure whether that's within our mandate, but recall that the iec559 standard recommends, but does not require, that the signaling bit be set to 1 for quiet and 0 for signaling; it may be reversed.

So yes, this also depends on how paranoid we are being. The only arch I have read about doing this for sure is PA-RISC, whose most recently released CPU came out in 2005, and any support for that platform is "out-of-tree" for LLVM.

Quuxplusone marked 4 inline comments as done.Oct 12 2021, 8:13 AM
Quuxplusone added inline comments.
libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp
387

I think that adding static_assert to our actual libcxx/include/ headers would be a bad idea. Our libcxx/test/ tests will certainly catch such an issue, on any supported platform; and I would hope that anyone trying to use libc++ on a non-supported platform would at least think to run the tests first, just out of curiosity.

I did notice on Godbolt that apparently MSVC-on-Windows uses 0x7fc00000 for quiet-NaN (as usual) but 0x7fc00001 for signaling-NaN (which is not a signaling NaN on the platforms I'm familiar with).
https://godbolt.org/z/oh6ch1dGa

mumbleskates added inline comments.Oct 12 2021, 10:21 AM
libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp
387

Okay that makes sense. If there are really that many buggy underlying implementations of quiet_NaN and signaling_NaN we're an order of magnitude more likely to see those just be outright wrong in this way than we are to find platforms with different-looking NaNs then it isn't really very helpful for us to guard against it this way. Sounds good

ldionne requested changes to this revision.Oct 14 2021, 5:53 AM
ldionne added inline comments.
libcxx/include/__compare/partial_order.h
35

That speaks a bit more than go (even though I'm pretty sure I'm guilty of this name at some point too, I have a faint memory).

39

As a side note, usually we do this:

noexcept(noexcept(EXPRESSION))
-> decltype(      EXPRESSION)
{ return          EXPRESSION; }
67

Do you want to ADL-protect those?

libcxx/include/__compare/strong_order.h
41

Throughout: I've found it a bit surprising that the parameters are called e and f. I would've found a and b easier to follow and closer to what everyone does. Any reason?

59

So for long double, we're supposed to implement it using the ISO/IEC/IEEE 60559 algorithm but currently we fall back to the common operator< & friends. Are those equivalent, but the ISO/IEC/IEEE 60559 is simply more efficient? If that's the case, I think it's reasonable not to implement it immediately. However, if the current implementation isn't correct on long double, then we either can't ship it or we should error out explicitly if someone uses long double.

libcxx/include/__compare/weak_order.h
47

What am I missing here? We're never checking for is_iec559?

libcxx/include/__utility/priority_tag.h
22–23

Yeah, I agree.

libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp
112

General comment for all the floating point comparisons in this patch: is there an existing set of inputs with known comparison outputs we could use and feed as test data? IOW, if we had a list of floating points and how they compare to each other, we could use that to validate our implementation -- as long as we satisfy that almost exhaustive set of inputs, we'd know our algorithm is most likely implemented correctly.

This revision now requires changes to proceed.Oct 14 2021, 5:53 AM
Quuxplusone marked 6 inline comments as done.Oct 14 2021, 7:11 AM

@ldionne ping — some responses to your comments; no planned changes yet.

libcxx/include/__compare/partial_order.h
35

FWIW, I wanted to stay away from "overloading" names that already have a different meaning in the STL. What we're doing here is very much not apply'ing anything (in the std::apply sense); we just need a name that is both a reasonable substitute for operator(), and reasonably Ctrl+F'able (so I also didn't want __f). I also have a faint memory of __go somewhere in libc++, but git grep says it's not there now.

Still, I think it would be nice for us to standardize on __go, for "overload sets like this that take __priority_tag"!

67

You mean __go? No, it's a member, so it needn't (and can't) be qualified.

libcxx/include/__compare/strong_order.h
41

The Standard calls them E and F, so I just went with that.
https://eel.is/c++draft/cmp.alg#1
I suspect the original etymology is just "Expression". :)
I'm not super strongly attached, but if we were to change them, I think I'd want _Tp __t, _Up __u over either _Tp __a, _Up __b (inconsistent) or _Ap __a, _Bp __b (unfamiliar).

59

"Are those equivalent[?]" — No; non-IEC559 types can't guarantee to order sNAN before qNAN, because we don't know anything about the bit layout of the type. However, what actually happens in this case is that we go to codegen the long else if ladder, and we get down to the bit_cast on line 101, and it blows up at compile-time because we're trying to bit_cast to void (line 93).
So, if sizeof(long double) == sizeof(double), then I think we do the right thing; and if sizeof(long double) > sizeof(double) (as on common platforms), regardless of whether it's IEC559 or not, then we already error out at compile time rather than do the wrong thing.

If you like, I could add a more explicit assertion, like

} else if constexpr (!(sizeof(_Dp) == sizeof(int32_t) || sizeof(_Dp) == sizeof(int64_t))) {
    static_assert(sizeof(_Dp) == 0, "Only 32-bit and 64-bit floating-point types are supported right now");
libcxx/include/__compare/weak_order.h
47

The weak_order algorithm doesn't benefit from knowing it's IEC559.
https://eel.is/c++draft/cmp.alg#2
We can't just compare the bits int-wise, the way we can for strong_order, because we need to arrange it so that std::weak_order(qNAN, sNAN) == std::weak_ordering::equivalent even when their bits are different. That motivates lines 55–66. And then the rest of the algorithm ends up being exactly the same no matter whether the type is IEC559 or not (because it's just the ordinary meaning of <=>, including the ordinary meaning of equivalence for positive+negative zeroes).

libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp
112

I don't know of an existing "test vector" for floating-point; but I claim that my lines 123–134 are pretty good if I do say so myself. ;) I'm covering INF, the whole range of normals, and positive and negative zero. The one hole, I guess, is that I'm not doing anything with subnormals (numbers whose magnitude is less than numeric_limits<F>::min()). I don't know how to generate such numbers, except through bit_cast. (But that is my own ignorance; there probably is a way I just don't know.)

Quuxplusone marked 4 inline comments as done.

Mark https://wg21.link/LWG3324 as "Complete".

ldionne added inline comments.Nov 8 2021, 2:25 PM
libcxx/include/__compare/partial_order.h
35

Alright, I still prefer __apply but won't bikeshed here since it's mostly about personal preference. Let's agree on not having any standardized name for this for now :-).

39

Ping on this - please format consistently with the other places where we do this. It helps for grepping.

67

Reviewed my ADL 101 and you're right.

Note that you can, however, qualify it. Like this->__go or __fn::__go. No action needed.

libcxx/include/__compare/strong_order.h
41

Non-binding, but I'd like to use __t and __u if we can agree on that. We don't use __e very often, and we are pretty consistent about using __f to denote some sort of callable, which I find misleading here.

59

I'd be happy with the assertion.

Address review comments. Rename E/F to T/U. Add a .verify.cpp test for the error message on std::strong_order(ld, ld).

Also, drive-by mark some spaceship issues as "Completed." (This will be committed as a separate git commit.)

Quuxplusone marked 4 inline comments as done.Nov 8 2021, 5:06 PM
Quuxplusone added inline comments.
libcxx/include/__compare/partial_order.h
39

The difference was just the extra spaces I put around noexcept(noexcept( E )) and decltype( E ), right? Is this the way you want it now?

libcxx/include/__compare/strong_order.h
41

Done. (But it's easy to revert if anyone objects.)

59

Added a "temporary, TODO FIXME" .verify.cpp test to verify the current behavior.

Quuxplusone marked 3 inline comments as done.Nov 15 2021, 2:50 PM
Quuxplusone added inline comments.
libcxx/test/std/language.support/cmp/cmp.alg/strong_order_long_double.verify.cpp
17–19

This test fails on arm7 (32-bit?) and Win32, where long double is 64 bits just like double.
It also fails on arm8 (64-bit?) for some reason I can't reproduce on Godbolt.
It also fails on AIX.
@ldionne: Any idea what XFAIL lines I should add here? Or shall I just eliminate this test again?

ldionne accepted this revision.Nov 16 2021, 7:21 AM

LGTM with requested changes and CI passing. I think you had updates to the Status pages you wanted to do separately from this commit -- please don't forget to land those (I don't mind them being landed in the same commit FWIW).

libcxx/docs/Status/Cxx20Issues.csv
253

Do you mean 14.0 or 13.0 here?

libcxx/docs/Status/SpaceshipPapers.csv
5 ↗(On Diff #385660)

Same question, 14.0 or 13.0?

libcxx/include/__compare/partial_order.h
27

_LIBCPP_HAS_NO_SPACESHIP_OPERATOR can be removed now.

39

Sorry, should have made it clearer, but the difference is the positioning of braces. This seems like a nitpick, but I've mass-modified these expressions in the past and having consistent formatting really helps.

libcxx/test/std/language.support/cmp/cmp.alg/strong_order_long_double.verify.cpp
17–19

What I did to figure this out is go to the various CI jobs that were failing and look for the following line in the Lit output: add Lit feature target=x86_64-pc-windows-msvc' as a result of parameter 'target_triple=x86_64-pc-windows-msvc' (and similarly for all failing platforms). I think what you want is:

// The following platforms have sizeof(long double) == sizeof(double), so this test doesn't apply to them.
// UNSUPPORTED: target={{arm64|armv8|armv7|powerpc|powerpc64}}-{{.+}}
// UNSUPPORTED: target=x86_64-pc-windows-{{.+}}
25–29
This revision is now accepted and ready to land.Nov 16 2021, 7:21 AM
Quuxplusone marked 7 inline comments as done.

Address @ldionne's review comments. Let's see if CI likes this now.

libcxx/docs/Status/Cxx20Issues.csv
253

I believe I mean 13. This was D99309.

libcxx/include/__compare/partial_order.h
39

Aha. I didn't notice the braces. Fixed now, AFAICT.

Stop static_assert'ing is_iec559 — it turns out that that's false for long double on AIX, but I bet the test still passes either way, so let's just verify that with buildkite.

ldionne accepted this revision.Nov 22 2021, 10:09 AM