CODEWITHSUNDEEP
c++gcc
Pibben
Pibben

Reputation: 2025

FMA instructions in compare function breaks strict weak ordering property

The C++ named requirement Compare require that the compare functions follow the strict weak ordering property. This is used for many standard library functions, for example std::sort.

Many modern-day CPUs support Fused-Multiply-Add operations that computes a + b * c efficiently and without rounding the result of the multiplication. This implies that there are situations where the result from an FMA operation is different from separate multiply and add operations. FMA code generations for GCC is controlled by the -ffp-contract flag and is enabled by default.

When the compiler generates FMA instructions in the compare function, there can arise a situation where the strict weak ordering property is (silently) no longer holding. This can cause std::sort and other functions to fail and crash on runtime.

Consider the following example:

struct S {
    double a;
    double b;
};

bool compare(const volatile S& s1, const volatile S& s2) {  // Volatile to prevent compile-time computations
    return s1.a * s1.b - s2.a * s2.b < 0.0;
}

int main() {
    const double a = 1 + 0x1.0p-52;
    const double b = 1 - 0x1.0p-52;

    volatile S s1{a, b};  // Volatile to prevent compile-time computations
    volatile S s2{1.0, 1.0};

    std::cout << compare(s1, s2) << '\n';
    std::cout << compare(s2, s1) << '\n';
}

The expected output would be

1
0

However, on platforms supporting FMA (and when enabled, which again is default on GCC) the result is

0
0

(GCC 11.2, -O3 -march=haswell)

Clearly showing that the weak ordering property is not enforced does no longer hold.

Why is this, potentially dangerous, feature enabled by default? What can be done to avoid this situation, besides disabling FMA code geneneration?

Upvotes: 0

Views: 77

Answers (1)

MSalters
MSalters

Reputation: 179991

The responsibility for ensuring a strict weak order lies with you, not the compiler. If you simply return true ignoring the arguments, it's obviously not a strict weak order. There's nothing a compiler can do to "enforce" the weak ordering.

Your code is of course not nearly as bad. It just contains a hidden assumption, namely that s1.a * s1.b - s2.a * s2.b < 0.0; if and only if s1.a * s1.b < s2.a * s2.b;. That holds for rational numbers, not for doubles. The reason is that operator- rounds to a double value. And only your version has an operator-

Again, when the implementation of the comparison is wrong, there is nothing a compiler can do to "enforce" the weak ordering.

Note that if you pass the option -ffast-math, then the compiler may turn s1.a * s1.b - s2.a * s2.b < 0.0; into s1.a * s1.b < s2.a * s2.b; or the other way around. It is an unsafe optimization, so the compiler won't do it until given permission. But without -ffast-math, the compiler will use exactly what you wrote, even if you should have used the other form.

Upvotes: 4

Related Questions