bearzx's blog

Werid results about O2 optimization
By bearzx, 12 years ago, In English

Yesterday when I was attending the CodeForces#100, I met a werid problem.


It was Problem A, I wrote my code, submitted, and passed the pretest, as usual. After the system test, I found that my code failed at test 9, it is:

Input: 2 1000 500
Output: NO
Answer: YES
status no. : 1011828

However, when I tested the data on my PC, I noticed that I' ve passed the test. My classmates told me that it might be the reason of O2 optimization of g++, because I don' t add that option on my PC, while CodeForces do. And Later on I submitted again with the MS Visual C++, this time my code was accepted(see status no. : 1010135), interesting, huh?

And something more interesting, if I add some "cout" before a statement(for debugging), I' ll pass the test in custom test:

See the status no. : 1011863
In this situation, I just add an cout << "" before I make my desicion.

And if I remove the cout << "":

I think this kind of results might have something with the O2 optimization, as the optimization may reduce the orders when it is compiling the source code.
  • Vote: I like it
  • +15
  • Vote: I do not like it

»
12 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

EDIT: It appears that the problem probably actually has something to do with floating point precision: did you try adding an eps of 1e-8 when you compare doubles?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    I think the problem is due to the O2 optimization, the accepted and wrong answer codes are the 99.9% same except ONE line contaning  ' cout << ""  '. At the same time , if you submit the wrong answer code in MS C++, it can get Accepted. Although different compilers have something different, floating numbers should also follow ISO standard.
    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Well, to avoid such problems regardless of what system you're on, you should add an epsilon to your floating point comparisons. You shouldn't assume anything about the compiler's optimizations: there's no way to control what is optimized away.
      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it
        However, output a empty string can affect floating point variables value ?
        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it
          It might be because, without the printing, the compiler can optimize away the local variable, thus changing the floating point rounding.
          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it
            But you cannot predict what O2 optimation will do, so you cannot avoid this kind of problem before you see the results
            → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Therefore, the problem is still caused by O2 optimization.

            O2 optimization has pros and cons. It can make your code run faster, at the same time  it also don't run as your willing sometimes. That is why so many online-judges and ACM/ICPC onsite contests disable the O2 optimization.
            → Reply
»
12 years ago, # |
  Vote: I like it +11 Vote: I do not like it
e-maxx, come!
→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 4   Vote: I like it +20 Vote: I do not like it

    Unfortunately, IMO there's nothing to report :)

    One should never compare precise double values, because there's no guarantee that compiler produced exactly the code we wrote.

    Another instructive example is the following. You wrote DP (which computed, for example, maximum of some double function) and want to restore, at which value did the maximum achieved.

    for (int i=0; i<x; ++i)
   dp = max (dp, value (i));
for (int i=0; i<x; ++i)
   if (dp == value (i))
      sel = i;

    That's totally wrong! Due to some complex optimizations and, as a result, changing of double values, assignment "sel = i" could occur  never.

    That's not a bug because compilers are given freedom with operating with floating-point expressions, and it usually a very bad idea to compare doubles without epsilon.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      So whenever I want to compare doubles I have to use epsilon ?
      Is that a rule?
      → Reply
»
12 years ago, # |
  Vote: I like it -22 Vote: I do not like it
MikeMirzayanov, Come!
→ Reply