Today I solved problem E. A Simple task that was given at last contest,and I find something intersting and new for me, posible and for other users.Why if I declare k,l,st,dr as a global variable I get TLE on test 9 and if I declare as a local variable my code past all tests?
Can someone explain why?
k=x;
for (l=26;l>=1;l--) {
st=lower_bound(g[l].begin(),g[l].end(),x)-g[l].begin();
dr=upper_bound(g[l].begin(),g[l].end(),y)-g[l].begin();
for (;st<dr;st++) {
g[l][st]=k; k++;
}
}
get TLE;
int k=x;
for (int l=26;l>=1;l--) {
int st=lower_bound(g[l].begin(),g[l].end(),x)-g[l].begin();
int dr=upper_bound(g[l].begin(),g[l].end(),y)-g[l].begin();
for (;st<dr;st++) {
g[l][st]=k; k++;
}
}
past all tests.
May be it's some compiler optimization effects...
Between the two submissions you linked, you also changed
cintoscanf.When viewing a submission, you can use the Compare button on the right to check that.
Look at this code no differents, also TLE on test 9.
Indeed, and I get the same behavior locally.
For example, if we take the passing solution (12126668) make the loop variable
lglobal (12126676), the time used raises from ~1.7 seconds to ~4.3 seconds, more than 2x!The effect is the same when using GNU C++11 (local, global) and GNU C++ (local, global). There is no such effect when using Visual Studio (local, global), and the runtime is ~2.9 seconds — something in between.
As to why that happens, my guess is the following.
When variable
lis local, it can not normally be altered by other code, and that allows the compiler to store it implicitly in a register, which speeds up things.On the other hand, when variable
lis global, the compiler can not prove that global state is not affected between executing the inner loop instructions (perhaps trying to be multithread-aware), and so has to store and access it explicitly, recalculating the address ofg[l][st]before every write.The most readable disassembly I've got is with
objdump -Sl <exefile>. Here is what looks as the inner loop at lines 41-43.C++ source:
Local version:
Global version:
Thanks for answer Gassa,now I understand why this small change make my code ran faster,now I will use only locals variables in
forandwhile,because it's really make difference.I've tested so amazing !!!
http://mirror.codeforces.com/contest/558/submission/12119277
i confused things you are right and im wrong :D