Hello there, while I was solving some hackerrank problems and I came across a couple of failed test cases due to timeout. After researching in a little bit deeper, I finally solved the issue, It was a pipeline problem! I was so happy to realize and apply the things I learned in school to practical life./p>
The Problem and The Solution
Keep in mind that solution is in C++, other programing languages or compilers might apply optimizations, however for this case it was an issue.In the picture, the code on left works faster than the code on right, therefore it does not fail the test case due to timeout. Main issue is at line 27 and 38 in the code in right side. Since value of "data[(*it)]" changes there, accessing to same data right below causes slowdowns. However if we save the data first to another variable, just like at lines 26 and 36 in the code on left side, issue is solved and our program works much more faster.
Why changing data slows it down?
Because of something called pipelining. In modern computers processors uses already processed data in the next line of the code while executing the code. This is called asynchronous code execution. In this case, when we change data in "data[(*it)]", previously saved data becomes invalid. Therefore already executed steps have to be discarded in order to get correct results and maintain data integrity. And discarded steps have to be performed again, which causes a slowdown. It is also called "wasting cycles" because it costs us process cycles to calculate same steps again.