Dardy's blog

GNU G++ bug with global set
By Dardy, history, 5 years ago, In English

Me and MrOkasha found an odd quirk with the GNU G++ compiler, (we tested with G++11, G++14, and G++17, all having the same bug).

This code here:



#include <bits/stdc++.h>
using namespace std;

set<double> st;

int main() {

    double x, y;
    for(int i = 0; i < 3; ++i){
        cin >> x >> y;
        st.insert(y/x);
    }
    cout << st.size() << endl;
}
// input:    5 -2 5 -2 5 -2

should output without any doubt '1', as the set should remove duplicate numbers. The output is 3 for some reason on the GNU compilers. It should be noted that the output is indeed 1 on Clang++17 compiler, Visual C++, and other available versions of GNU G++ compilers found online, for us, it seems the bug only occurs here on codeforces, verified by the Custom Invocation feature.

The weirdest thing about this bug is that, for some bizarre reason, if the declaration of the set set<double> is moved to inside the main function, the code works as intended.

Any thoughts on this weird issue?

  • Vote: I like it
  • +39
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
5 years ago, # |
  Vote: I like it +78 Vote: I do not like it

Welcome to the world of the floating point arithmetic!

The compiler is allowed to do floating point operations sometimes with higher precision than necessary. It is also allowed to do the exact same floating point operations with just the precision that was necessary at other times. Therefore the exact same operation may produce slightly different results, which is what you see here.

So it's not a bug.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm not entirely convinced because of multiple reasons, why specifically does it not work when the set is global not local, and does it produce slightly different results every single time?

    Also, what compiler options/flags do I need to reproduce this on my own machine? Why does this issue only occur on codeforces' machine?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      I guess -mfpmath=387 should be such a flag. And you need x86 machine or 32-bit building mode, -m32 for example.

      The answer on your first question is may be the fact that nowadays most of the floating-point arithmetic is performed by SSE instructions, and not by FPU (math coprocessor). CF servers may be an exception =) And SSE has no such problems.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Isn't -5/2 calculated without precision loss in any floating point type?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      As I know it works in the following way: you have 8 byte variables, but math coprocessor operates with 10 bytes registers, so you get 2 bytes (actually not) from garbage for most of operations performed by math coprocessor (not only /, but < also). Btw, it's -2/5.

      And it still weird that it depends on if the set is global. So I actually can be wrong, and it's really a bug of GCC (not first time for it). If someone isn't lazy and can take a look at the difference of compiler output for x86 mingw, we will know the answer for sure =)

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        My bad. With -5/2 this can never happen, right?

        → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it
What you should use in double comparison

Link to cppref

P.S. You can change epsilon when you will need to calculate many sqrt, sin, cos, tan, atan

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +47 Vote: I do not like it

    This is not a good compare function. It doesn't satisfy the requirement that a function is a strict weak ordering:

    if comp(a,b)==true and comp(b,c)==true then comp(a,c)==true

    For your function, I can find a,b,c such that isEqual(a,b) and isEqual(b,c) but not isEqual(a,c)

    See this code
    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Always use customized rational data type when you have to compare rational numbers!

I lost a gold medal in 2018 ICPC Xi'an Invitation because I believed I could mitigate the percision issue with double and some stupid adjustment.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Never hash floating numbers! Instead you can use this

Spoiler
→ Reply