P1023R0 constexpr For std::array Comparisons

[StephanTLavavej]

P1023R0 constexpr For std::array Comparisons

This needs part of #6 "constexpr For <algorithm> And exchange()", which needs #156 is_constant_evaluated().

Feature-test macro according to SD-FeatureTest:
#define __cpp_lib_array_constexpr 201806L

[NathanSWard]

This sounds like a good first issue to tackle! Anything in particular to keep in mind before proceeding?

[StephanTLavavej]

This one has a surprising bit of complexity - array comparisons eventually call equal() or lexicographical_compare(), which contain fancy metaprogramming to detect types where calling memcmp() could be faster. (memcmp() is typically written in assembly, offering speed beyond anything that can be written in the Core Language.) Unfortunately, memcmp() isn't constexpr, so we'd have to sacrifice runtime performance in order to gain constexprness.

Fortunately, there are two ways out of this problem. The first is to request dedicated compiler support, as we did for constexpr char_traits. The second is to use C++20's is_constant_evaluated(), which allows an implementation to detect whether it's being called in a constexpr context (in which case a plain old loop will be constexpr-friendly) or whether it's being called at runtime (in which case we can use the existing metaprogramming to potentially call memcmp()).

MSVC's compiler front-end C1XX doesn't yet support is_constant_evaluated() (despite looking like a library function, it's really just a wrapper around compiler magic). The good news is that Clang 9 does! (See https://clang.llvm.org/cxx_status.html .) We consider Clang/LLVM on Windows to be a first-class citizen and are willing to implement library features that are active for Clang before they're active for C1XX, which we've done in the past.

Our library currently requires Clang 8.0.1 at a minimum (newer versions are OK), and we're going to increase this requirement to 9.0.0 very soon (just waiting on the IDE to upgrade its bundled copy). So, working on a feature that requires Clang 9 is fine.

Let us know if you need more info!

[viccpp]

Doesn't MSVC++ compiler recognize comparison of arrays in loops and use cmps instructions like memcmp() does? AFAIK VC++6 was able to do that (as opposed to Borland C++ 5.0).

[NathanSWard]

Thanks for the advice @StephanTLavavej :) However, after viewing more issues, wouldn't this be better addressed by first tackling (#6)? Specifically constexpr bool equal() and constexpr bool lexicographical_compare(). In other words, would it be better to implement these two constexpr algorithms using std::is_constant_evaluated() then implementing constexpr For std::array comparisons?

[StephanTLavavej]

@2underscores-vic - I recall that we looked into this a while ago, and MSVC's optimizer didn't recognize all of the scenarios that our library metaprogramming recognizes. But the real blocker is that the optimizer doesn't run in (non-optimized) debug mode, while the library metaprogramming is always active. So relying on the optimizer would degrade debug scenarios.

@NathanSWard - yep, implementing #6 first would be better, then this issue (#49) becomes trivial. I filed #156 for is_constant_evaluated() just now, thanks for reminding me.

[StephanTLavavej]

is_constant_evaluated() is now available for Clang, and will be available for VS 2019 16.5 Preview 2 in the future, so work on this feature is unblocked (if properly guarded with __cpp_lib_is_constant_evaluated).

[StephanTLavavej]

#6 has been implemented.