`<algorithm>`: `minmax_element()` crashes for NaNs

[ThomasFWise]

Describe the bug

std::minmax_element hits an AV when nan is included in the vector. Probably not legal to include nan, but an error other than an AV would be preferred.

Command-line test case

C:\Temp>type repro.cpp
#include <algorithm>
#include <cmath>
#include <vector>

int main()
{
    std::vector<double> v = {};
    v.push_back(std::nan(""));
    v.push_back(20.0);
    v.push_back(std::nan(""));
    
    const auto [mn, mx] = std::minmax_element(begin(v), end(v));

    return 0;
}

C:\Temp>cl /EHsc /W4 /WX /std:c++latest .\repro.cpp
Microsoft (R) C/C++ Optimizing Compiler Version 19.36.32522 for x64
Copyright (C) Microsoft Corporation.  All rights reserved.

/std:c++latest is provided as a preview of language features from the latest C++
working draft, and we're eager to hear about bugs and suggestions for improvements.
However, note that these features are provided as-is without support, and subject
to changes or removal as the working draft evolves. See
https://go.microsoft.com/fwlink/?linkid=2045807 for details.

repro.cpp
Microsoft (R) Incremental Linker Version 14.36.32522.0
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:repro.exe
repro.obj

C:\Temp>.\repro.exe
test failure

Expected behavior

Not an AV exception

STL version

Microsoft Visual Studio Community 2022
Version 17.10 Preview 7

Additional context

DevCom-10658748

[StephanTLavavej]

This is by design - NaNs are unordered, so they violate minmax_element()'s precondition of having a strict weak ordering.

NaNs disrupt other algorithms in ways that are difficult for debug checks to detect - for example, sort()ing a range that includes NaNs is also undefined behavior, but inspecting pairs of elements via the comparator doesn't reveal any problem. Adding even more debug-check complexity to detect NaN inputs doesn't seem worth it to me. Admittedly, we do have a (permitted by the Standard) behavioral change here, so if we receive a high volume of reports, we may want to consider adding NaN detection before invoking the vectorized algorithms (I would strongly prefer for it to be a debug precondition check, not a "we'll tolerate NaNs in release mode like before" check - we had such things in deque::pop_back and they were bad and we got rid of them).

Thanks for the report!

[matthiasstraka]

What does the C++ standard say about this? As far as I understand it, the behaviour of minmax_element without a Compare comp parameter should behave as if by using operator< (until C++20). This is no longer the case with MSVC 17.10 when NaNs are involved. A comparison with NaN should always return false and thus is defined behavior.
See https://en.cppreference.com/w/cpp/algorithm/minmax_element

[glaure]

@StephanTLavavej

This is also reported here:
https://developercommunity.visualstudio.com/t/std::min_element-and-std::max_element-cr/10683473?sort=newest

Our case:
This change forced us to rollback to an older Visual Studio 2022 Version. Out software handles measured data that can have holes that are filled with NANs. We do an automated MIN/MAX calculation over these sample vectors.

Please consider to fallback to the previous behaviour.

Best regards,
Gunther

[StephanTLavavej]

@matthiasstraka

A comparison with NaN should always return false and thus is defined behavior.

In isolation that is a correct statement, but the larger context is undefined behavior - it's a precondition violation for the sorting family of algorithms.

STL algorithms require "strict weak orderings". (For clarity, I'll refer to the comparison as "less than", but other functions can be used as long as they satisfy the requirements, like "greater than", but not "less than or equal".) Two elements A and B are considered equivalent if A isn't less than B and B isn't less than A. One requirement of a strict weak ordering is that an element A has to be equivalent to itself: A isn't less than A. (This is what forbids less_equal, for example, because it would report true for a self-comparison.)

Another requirement for a strict weak ordering is that equivalence must be transitive: if A is equivalent to B, and B is equivalent to C, then A must be equivalent to C. NaNs break this. Because A < NaN and NaN < A are both false, A and NaN appear to be equivalent. But that means that 3.14 is equivalent to NaN, and NaN is equivalent to 17.29, but 3.14 is not equivalent to 17.29.

This is why giving a range of NaNs and non-NaNs to STL sorting (and sort-like) functions is a forbidden precondition violation. (There's some ambiguity about whether it should be permitted to pass all NaNs, or all NaNs except for exactly one ordinary value, but those aren't really useful corner cases.)

@glaure if you want to ignore NaNs, you should write your code in two steps - one step to filter out NaNs, and then another step to get the min/max. Alternatively, you could write a custom comparison that would project NaNs to some ordinary value (e.g. negative infinity or positive infinity) before comparing them. Our new behavior is a behavioral change but not a Standard conformance bug, and we aren't planning to revert it. There's an escape hatch for code that can't be easily fixed.

[simmse]

Hello @StephanTLavavej @glaure @matthiasstraka @ThomasFWise @mtodd ,

What is the escape hatch referred to above in the August 1, 2024 post? The _USE_STD_VECTOR_ALGORITHMS macro looks to be detecting and used for vectorization. Should the macro be set to zero immediately before any/all call sites and back to one after the call of affected methods like std::minmax_element?

[StephanTLavavej]

What is the escape hatch referred to above in the August 1, 2024 post?

Define _USE_STD_VECTOR_ALGORITHMS to 0.

Should the macro be set to zero immediately before any/all call sites and back to one after the call of affected methods like std::minmax_element?

No. You cannot "push/pop" this. You must define it to 0 project-wide, including in any statically linked OBJ/LIB files, otherwise you might drag in the vectorized algorithms.

Ideally, you should define this on the command line (i.e. in your build system). You should not define this in any source file or header file, because then you run the risk of defining it "too late" after an STL header has been dragged in.

[AlexGuteniev]

There's also _USE_STD_VECTOR_FLOATING_ALGORITHMS which controls floating point vectorization, so currently it is only minmax family. Still, if set, it should be set to the same everywhere

[simmse]

Reviewing the comments in the area where the _USE_STD_VECTOR_FLOATING_ALGORITHMS is set to one or zero, why do the comments indicate that fast math is enabled (e.g. see code below)? Does the floating point compiler option continue to determine whether fast math is enabled?

#ifndef _USE_STD_VECTOR_FLOATING_ALGORITHMS
#if _USE_STD_VECTOR_ALGORITHMS && !defined(_M_FP_EXCEPT)
#define _USE_STD_VECTOR_FLOATING_ALGORITHMS 1
#else // ^^^ use vector algorithms and fast math / not use vector algorithms or not use fast math vvv
#define _USE_STD_VECTOR_FLOATING_ALGORITHMS 0
#endif // ^^^ not use vector algorithms or not use fast math ^^^
#else // ^^^ !defined(_USE_STD_VECTOR_FLOATING_ALGORITHMS) / defined(_USE_STD_VECTOR_FLOATING_ALGORITHMS) vvv
#if _USE_STD_VECTOR_FLOATING_ALGORITHMS && !_USE_STD_VECTOR_ALGORITHMS
#error _USE_STD_VECTOR_FLOATING_ALGORITHMS must imply _USE_STD_VECTOR_ALGORITHMS.
#endif // _USE_STD_VECTOR_FLOATING_ALGORITHMS && !_USE_STD_VECTOR_ALGORITHMS
#endif // ^^^ defined(_USE_STD_VECTOR_FLOATING_ALGORITHMS) ^^^

[AlexGuteniev]

why do the comments indicate that fast math is enabled

An oversight. Initially floating vector algorithms were meant for fast math only, but now they are enabled for the default mode as well.

[simmse]

@StephanTLavavej Okay. When it is expected to have strict or precise floating point operations, and the compiler option is set appropriately, the expected floating point behavior continues, correct?

[StephanTLavavej]

The STL attempts to avoid interfering with your choice of /fp options.

By default, we activate the vectorized algorithms for floating-point minmax, except when /fp:except is active. Again, NaNs trigger undefined behavior, so we are justified in using the vectorized algorithms even under /fp:strict.