ldyllic's blog

By ldyllic, history, 4 months ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it
No less interesting fact
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yep, I have also tried it a while ago with another code

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yep, true. Any idea of the reason behind that significant change while changing the indexing of a container?