Saturday, December 07, 2013

Better algorithms v/s micro-optimization

As a kid, I participated in a game that involved bouncing a tennis ball on the ground using your hands. The winner was the one who was able to bounce the ball the most number of times in 60 second.

All the little ones (including me) went first (since the game was primarily meant to keep us busy). I was top scoring with a little over 70 bounces in 60 second. What I did to get there was try and go as fast as I possibly could without losing control of the ball, and focusing heavily on where the ball was at all times.

Then the grown-ups started and for a while no one was able to beat that score. Then one smart dude knelt down when the signal to start was given. Everyone else had already started bouncing there balls and were in to their second bounce, and this guy was taking his own time getting settled in his squatting position. When he was ready, he started bouncing the ball, and boy did he go fast! He had just out-smarted everyone else with a better algorithm for getting more bounces in the same time duration.

Better algorithms are like bicycles for the mind.

Before we had sorting algorithms that ran efficiently [O(n log n)], we had micro-optimizations applied to every known O(n2) sorting algorithm in an attempt to make it perform fewer comparisons, or exit early, and hence run faster. Fixing the algorithm, however, was the real game changer.