Hello, CodeForces!
I have just solved 1 problem and I made quite a lot new observations for me. Could anybody explain me, please, the reason behind the behaviors that I will explain here? Thanks a lot!
That is the problem — nothing outstanding, simple implementation 1575J - Jeopardy of Dropped Balls. However to be able to help me out, you will need to get into this problem to see what I will state below :)
A bit of story: while doing CP I was often wondering about the engines behind the code, how and what executes, what takes care of what etc. Hence, I decided to make some experiments on this problem.
First code: 160046810 — [1980ms]. In a while loop I access an element with parameter 2 at the else statement. This parameter just increases x and moves forward, while 2 first statements increase / decrease y + change an element in a matrix. Container for a data is 0-indexed.
Second code: 160047806 — [483ms]. Here in a while loop I access an element with parameter 2 at the first if statement and other statements where I need to change matrix elements follow after. Array is still 0-indexed.
Third code: 160047849 — [280ms]. Everything is similar to the second code, but array is 1-indexed.
I am mostly interested in a reason of difference between 1st and 2nd code, but if you could point out the same between 2nd and 3rd — that will be amazing!
Something very strange is happening. If you send the same solution but replace this:
on this:
The solution becomes almost 2 times slower:
160051880 — [467 ms]
160051866 — [779 ms]
Yep, I have also tried it a while ago with another code
I don't think that such change would make a real difference in generated assembly, so it seems that running time of the program is unstable. It's weird, though, that this instability makes ~67% difference.
The key difference between the first and the second codes is the order of
if's: while the slower solution checks for $$$3$$$, $$$1$$$ and $$$3$$$, the faster one checks for $$$2$$$, $$$1$$$ and $$$3$$$.The optimizer doesn't do much magic here, and the resulting code just checks these
if's in the same order as they were written:https://godbolt.org/z/847onrzb8
https://godbolt.org/z/bxjEjGMG5
However, the most frequent branch here is the branch with $$$2$$$'s: after many balls fall, almost all the field will consist of $$$2$$$'s. In the faster code, this branch is the first, so in the most cases we will just go there without performing all the additional checks. We will also do less jumps during the execution, so the code is faster.
Yep, true. Any idea of the reason behind that significant change while changing the indexing of a container?