Werid results about O2 optimization

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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.

Комментарии (13)

Написать комментарий?

random.johnnyh

13 лет назад, # |

← Rev. 2 →

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?

→ Ответить

luyi0619

13 лет назад, # ^ |

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.

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.

However, output a empty string can affect floating point variables value ?

It might be because, without the printing, the compiler can optimize away the local variable, thus changing the floating point rounding.

bearzx

But you cannot predict what O2 optimation will do, so you cannot avoid this kind of problem before you see the results

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.

daftcoder

+11

e-maxx, come!

e-maxx

← Rev. 4 →

+20

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.

So whenever I want to compare doubles I have to use epsilon ?

Is that a rule?

-7

Yes

mkagenius

But notice, which side of the operator (</>) you would use it.

icek

-22

MikeMirzayanov, Come!

Блог пользователя bearzx