Werid results about O2 optimization

№	Пользователь	Рейтинг
1	tourist	3757
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

№	Пользователь	Вклад
1	maomao90	171
2	awoo	165
3	adamant	164
4	TheScrasse	159
5	nor	155
5	maroonrk	155
7	-is-this-fft-	152
8	Petr	147
9	orz	146
10	pajenegod	145

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

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

← 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

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

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