Page MenuHomePhabricator

[WIP] [libc++] [P1614] Various unimplemented parts of <compare>. [WIP]
Needs ReviewPublic

Authored by Quuxplusone on Jul 28 2021, 10:38 PM.

Details

Reviewers
ldionne
cjdb
Group Reviewers
Restricted Project
Summary

I have this locally as five commits, and plan to upload several PRs when it's actually ready to land.

Duplicates/supersedes the following similar PRs by others:

  • D80899 compare_three_way, blocked by lack of three_way_comparable

But does not supersede this one:

  • D80902 lexicographical_compare_three_way, blocked by lack of compare_three_way

Diff Detail

Unit TestsFailed

TimeTest
700 mslibcxx CI GCC 11 / C++latest > libc++.std/language_support/cmp/cmp_alg::strong_order.pass.cpp
Script: -- : 'COMPILED WITH'; /usr/bin/g++-11 /home/libcxx-builder/.buildkite-agent/builds/cd3de43f241a-1/llvm-project/libcxx-ci/libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp -v -include /home/libcxx-builder/.buildkite-agent/builds/cd3de43f241a-1/llvm-project/libcxx-ci/libcxx/test/support/nasty_macros.h -nostdinc++ -I/home/libcxx-builder/.buildkite-agent/builds/cd3de43f241a-1/llvm-project/libcxx-ci/build/generic-gcc/include/c++/v1 -I/home/libcxx-builder/.buildkite-agent/builds/cd3de43f241a-1/llvm-project/libcxx-ci/build/generic-gcc/projects/libcxx/include/c++build -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -D__STDC_CONSTANT_MACROS -I/home/libcxx-builder/.buildkite-agent/builds/cd3de43f241a-1/llvm-project/libcxx-ci/libcxx/test/support -std=c++2b -Werror -Wall -Wextra -Wshadow -Wundef -Wno-unused-command-line-argument -Wno-attributes -Wno-pessimizing-move -Wno-c++11-extensions -Wno-user-defined-literals -Wno-noexcept-type -Wno-aligned-allocation-unavailable -Wno-atomic-alignment -Wno-sized-deallocation -Wsign-compare -Wunused-variable -Wunused-parameter -Wunreachable-code -Wno-unused-local-typedef -D_LIBCPP_DISABLE_AVAILABILITY -Wno-macro-redefined -D_LIBCPP_HAS_THREAD_API_PTHREAD -Wno-macro-redefined -D_LIBCPP_ABI_VERSION=1 -lc++experimental -L/home/libcxx-builder/.buildkite-agent/builds/cd3de43f241a-1/llvm-project/libcxx-ci/build/generic-gcc/./lib -Wl,-rpath,/home/libcxx-builder/.buildkite-agent/builds/cd3de43f241a-1/llvm-project/libcxx-ci/build/generic-gcc/./lib -L/home/libcxx-builder/.buildkite-agent/builds/cd3de43f241a-1/llvm-project/libcxx-ci/build/generic-gcc/./lib -Wl,-rpath,/home/libcxx-builder/.buildkite-agent/builds/cd3de43f241a-1/llvm-project/libcxx-ci/build/generic-gcc/./lib -nodefaultlibs -lc++ -lm -lgcc_s -lgcc -lpthread -lc -lgcc_s -lgcc -latomic -o /home/libcxx-builder/.buildkite-agent/builds/cd3de43f241a-1/llvm-project/libcxx-ci/build/generic-gcc/projects/libcxx/test/std/language.support/cmp/cmp.alg/Output/strong_order.pass.cpp.dir/t.tmp.exe

Event Timeline

Quuxplusone created this revision.Jul 28 2021, 10:38 PM
Quuxplusone requested review of this revision.Jul 28 2021, 10:38 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptJul 28 2021, 10:38 PM
Quuxplusone planned changes to this revision.Jul 28 2021, 10:38 PM

Has tests now.
std::strong_order still doesn't compare NaNs correctly; we may need a domain expert for this.
Everything up to strong_order is probably ready to upload separately for review:

  • [libc++][modularisation] Split up <concepts> into granular headers.
  • [libc++] [p1614] Implement std::compare_three_way_result.
  • [libc++] [p1614] Implement std::three_way_comparable.
  • [libc++] [p1614] Implement std::compare_three_way.

@ldionne: Do you want the above as four PRs, one PR, or something in between?

Quuxplusone edited the summary of this revision. (Show Details)Jul 30 2021, 11:13 AM

Rebase (expecting CI to pass this time)

Wmbat added a subscriber: Wmbat.Jul 31 2021, 8:33 AM
cjdb requested changes to this revision.Aug 1 2021, 5:14 PM
cjdb added a subscriber: cjdb.

Has tests now.
std::strong_order still doesn't compare NaNs correctly; we may need a domain expert for this.
Everything up to strong_order is probably ready to upload separately for review:

  • [libc++][modularisation] Split up <concepts> into granular headers.
  • [libc++] [p1614] Implement std::compare_three_way_result.
  • [libc++] [p1614] Implement std::three_way_comparable.
  • [libc++] [p1614] Implement std::compare_three_way.

@ldionne: Do you want the above as four PRs, one PR, or something in between?

I'd appreciate it if you could make these dependent PRs to make it easier to review.

libcxx/include/__concepts/__boolean_testable.h
1 ↗(On Diff #363160)

Please rename this file to boolean_testable.h. We decided a while back to not prefix detail headers with underscores.

libcxx/include/concepts
155–159 ↗(On Diff #363160)

If you're going to split up <concepts>, please entirely split it up. Having some content in <concepts> and other stuff in __concepts is going to be difficult to track.

libcxx/test/std/language.support/cmp/cmp.concept/three_way_comparable.compile.pass.cpp
1 ↗(On Diff #363160)

There are a lot of missing tests for this file. Please reintroduce them.

libcxx/test/std/language.support/cmp/cmp.concept/three_way_comparable_with.compile.pass.cpp
1 ↗(On Diff #363160)

There are a lot of missing tests for this file. Please reintroduce them.

This revision now requires changes to proceed.Aug 1 2021, 5:14 PM
cjdb added a comment.Aug 9 2021, 11:27 AM

In addition to my feedback above, please drop the <concepts> changes from this patch (no longer necessary), as well as the changes in common with D80899 and D80902 (I'll return to these once three_way_comparable lands).

Please also ensure that what's left properly credits the original patch authors in the commit, preferably by making them the person that's named in git blame.

mumbleskates added inline comments.
libcxx/include/__compare/cmp_alg.h
66 ↗(On Diff #363160)

I would hope that we can order them by union view of the data in memory if such a thing is allowed (or memcpy, if that's better) once we know that the sign and signaling bits are the same, because the specifics of the payload ordering are unspecified by totalOrder. Any way that we can look at the raw data in memory without UB should be sufficient.

mumbleskates added inline comments.Aug 16 2021, 5:57 PM
libcxx/include/__compare/cmp_alg.h
66 ↗(On Diff #363160)

Ah I see, there are literally no standard implementation for the isSignaling predicate for iec559 types in C++. However, it does look like ISO C has an issignaling macro as part of the Floating-point extensions part 1, which I gather was accepted into the C23 standard in 2019 (ISO/IEC TS 60559-1, of interest section 7.12.3.7). Complete implementation of C++ strong_order for iec559 floating point types might be considered to be blocked on the implementation of this part of the standard as that seems like the best place to get it.

Implementing this just for strong_order is messy, very complex, and generally inadvisable. (Even for binary floating point values, ignoring the existence of decimal floating point types, some platforms -- notably PA-RISC -- use the opposite interpretation for the signaling bit in IEC559 floating point types, even though it's in the same location.) Unless we can strongly declare that we don't support any platforms other than say ARM and x86 this seems like a no-go, and it just seems better to take the platform support directly from the llvm C standard implementation.

Quuxplusone added inline comments.Aug 17 2021, 8:23 PM
libcxx/include/__compare/cmp_alg.h
66 ↗(On Diff #363160)

@mumbleskates: I doubt I understand your two comments. In case it's not already obvious: the IEEE 754 "total order" predicate is well-defined and we must implement std::strong_order consistently with it, on IEEE 754 platforms, because the Standard says so. (On other platforms, C++ doesn't care so much, because those platforms are dumb. :)) std::strong_order(x,y) is the way that C++20 exposes the "total order" predicate to end-users; there is no isolable floating-point-total-order library function for us to delegate to (because WG21 doesn't do software engineering).

Is there an isolable "llvm C standard implementation" we could be exploiting here — some kind of __builtin_totalorder we could use when it's available? That would be really cool.
I do think that this will eventually need to use either constexpr-friendly __builtin_memcpy, or else std::bit_cast; I just haven't gotten around to revisiting it.

A bit of googling turned up this solution which maybe just needs to be tweaked a tiny bit: https://stackoverflow.com/a/20154751/1424877

mumbleskates added inline comments.Aug 17 2021, 9:36 PM
libcxx/include/__compare/cmp_alg.h
66 ↗(On Diff #363160)

That general solution in the stackoverflow link works, but may only be correct for x86/ARM binary representation floating point types. (I don't know enough about the decimal types to know if they would also sort this way, but they are unsupported by by x86/ARM silicon.)

What it boils down to is that the *only* predicate we are missing, for any given iec559 type, is isSignaling: detecting whether a NaN is signaling or not. If we have that we can use it to complete the implementation here. Such a predicate does exist in standard C, but I believe it is not yet implemented in llvm's libc.

I know exactly how to do this on x86 and ARM with bit twiddling for pretty much any floating point type in the standard, but there are platforms with iec559 implementations where the signaling bit has the opposite meaning, and I think there might exist platforms where it is in a different place. Because signaling/non-signaling NaN implementation details are a property of the platform this immediately becomes a question of platform support; it's probably best to centralize this implementation knowledge as much as possible, but I don't know much about our approach to that in the llvm project.

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

Rebased on main, to show what's left to do.
Tried a new bit-twiddling version of IEC559 totalOrder. Unfortunately I still don't know how to test it or how to make it constexpr. Fortunately, C++20 requires that it not be constexpr, AFAICT? See https://eel.is/c++draft/cmp#alg-1 which doesn't mention constexpr either positively or negatively.

mumbleskates added inline comments.Sun, Aug 29, 3:11 AM
libcxx/include/__compare/cmp_alg.h
49 ↗(On Diff #367673)

Fun cursed fact here, intel 80bit long doubles are also iec559. At least on my skylakex system they have sizeof() 16, have 6 bytes of padding at the end, and otherwise work mostly the same (sign bit at the top, 15 bits of exponent, 63 bits of mantissa in a 64 bit field wherein the MSB is always 1 except when it's sub-normal, and the next highest bit is used for 0=signaling/1=quiet NaN, as the highest bit of the real mantissa). Not completely sure what to do about that!

jloser added a subscriber: jloser.Sun, Aug 29, 4:03 PM
jloser added inline comments.
libcxx/include/__compare/cmp_alg.h
45 ↗(On Diff #367673)

Should we use std::same_as and std::floating_point concepts instead? Same applies to other uses ofG type traits that are concepts now as well.

libcxx/test/std/utilities/function.objects/comparisons/compare_three_way.pass.cpp
26

Any reason to prefer this over just return true;? Similarly for the fallback overload (except return false; in that case).

libcxx/test/std/utilities/function.objects/comparisons/transparent.pass.cpp
60

We can drop the empty string second argument if you care.

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

Rebase on std::bit_cast (D75960), and use std::bit_cast in the implementation of std::strong_order.
Rebase on D103478 (which has been merged now).

Rebase; incorporate D109331 and further bugfixes to D75960.