After writing a solution to an easy warm-up “Best time to buy and sell stock” Leetcode problem I still had some time before the competition starts and started to wonder if there is some other way to improve an already linear solution
The idea is straightforward - we want to buy and sell as often as possible as long as it’s profitable. In such cases it’s common in competitive programming to use the max
function to ignore negative profits (losses). Then I thought to myself - well it certainly looks nice but doesn’t it mean that we now perform unconditional writes to the profit
variable? Memory is slow, so I wondered if switching to a less idiomatic if
else
would make a difference
The thinking was that branching is present in both versions but the second one has only a single clause, which should certainly be cheaper… Shouldn’t it? Well, let’s check.
To make things more interesting, I wrote tests that include tests for best and worst cases of both algorithms - increasing and decreasing sequences. In case of an increasing sequence, we’ll be adding profits on every iteration, so both algorihtms should perform a write, but in case of a decreasing sequence, we don’t expect any profits, so explicit if statement should avoid all writes and be significantly faster. At least that’s how I thought. But
Turns out that all benchmarks took about the same amount of time. How come?
Compiler explorer to the rescue!
Compilers are very smart and instead of blindly translating my inefficiencies into assembly, they kindly vectorized my code and used conditional moves (CMOVcc
) instructions in both cases.
This served me as a good reminder that every time I consider sacrificing readability for performance I should consider if it’s worth it and if so, whether it’s really an optimization.
Bonus. Just for fun, I also decided to check out the assembly generated by my Rust version
To my disappointment Rust compiler didn’t bother vectorizing but still used conditional move so I might as well have saved a few lines and wrote