How far can code be optimized

(written by lawrence krubner, however indented passages are often quotes). You can contact lawrence at: lawrence@krubner.com, or follow me on Twitter.

This is funny and interesting:

When you’re competing with another player, they will probably find a way to beat your score by just a few points. Let’s say my score is 340 and a friend beats me with a score of 335. (lower is better. The score is just the number of executed instructions) What follows is a bunch of head-scratching about how you could possibly get any more cycles out of the algorithm. After an hour of staring and trying different things you find a small improvement, and your new score is 332! Proudly you tell your friend that you beat their score. Soon after your friend will beat your score with 320. Such a big jump seems impossible. But your friend somehow did it. So now you need to think outside of the box. You’re thinking the only way that you could possibly achieve such a big jump is if you could somehow combine these two different parts of the algorithm, so that they can share this one part of the work. It doesn’t seem possible, and it’s not even clear that this will buy this much of a score improvement, but it’s the only thing you can think of. So after another hour of head-scratching about how you could possible achieve this you find a way to do it, and lo and behold it the wins are far bigger than expected, the new score is 310! And the next day your friend comes back with 290…

My friend and I have literally had cases where we went from a score of more than 500, where my friend thought that my score was impossible, down to a score of 202 for me, and 200 for my friend which put us completely off the charts. At that point a new patch hit that changed the level slightly so that our solutions didn’t work any more. (the game is still in early access) But if it hadn’t been for that, I wouldn’t have been surprised if we could have optimized this further. Almost every single time that I thought the limit was reached, we broke through it soon after.

I can now say for a fact that a lot of code out there is far from optimal. Even the code in our standard libraries that’s maintained by some of the best programmers and that’s used by millions is slower than it needs to be. It is simply faster than whatever code they compared it against.

2. You can’t think of a solution until you know it’s possible
On the second puzzle in the game, which serves as a kind of tutorial, the only possible score is 240. Except there were some people over on the left of the histogram. And wondering how to get over there, my friend somehow got to 180, telling me “I think this one is optimal.” The score seemed unreachable. With a few tricks I got it down to 232. After literally days of thinking about this problem I managed to think outside the box and match my friend’s score of 180. It wasn’t until we talked about it that we realized that we had used different solutions. It was crazy to realize that there were in fact two entirely different ways to reach 180. Once I realized that I had used a different solution, I also realized that the solution that my friend picked could not be optimized further, but mine could. It took me hours, but I got the score down to 156, and then very quickly down to 149. My friend then beat me with 148 using my technique, forcing me to find one last cycle.

Post external references

  1. 1
    https://probablydance.com/2016/11/07/lessons-learned-from-shenzhen-io/
Source