Exhausting efforts of optimization!

Warning: Any non-geeks, avoid this article, u're unlikely to appreciate, let alone understand the article(no offense, but it is the case here).

I write this post after having spent the past 8 hours on trying to optimize my program. My code was originally written in Visual C++ (i.e. Windows) and on finding no tools to let me profile my code, i shifted to gcc (i.e. linux). Why a commercial programming suite lacks a profiling tool is baffling. It would only let me do a profile guided optimization. In my experience, a good programmer with a profiler can do a hell lot better job at optimization than any compiler. In fact, after my efforts, adding any other optimization flag other than the obv -O3 actually slowed down the code!. That is one big reason i like linux and gcc. It's a developer's os, meant expressly for development, which is why its adoption by other people baffles me a bit, they're not using the most powerful features of the os, and giving up quite a bit of user friendliness in the process.

One of my professors once said, that some code written by a novice programmer can be speeded up about 10-20 times by an highly experienced programmer who knows his hardware, even without knowing what the program does. Though this might be a bit of an insult to some, it's true to an extent. I've actually hit the 10 times mark on some of my own code :D , and the code wasn't badly written to begin with. But, something the confuses me is that there is no comprehensive guide to writing fast code. There are some basic tenets which if followed, can give very good performance on any machine. In my opinion, hardware specific optimizations are best left to compilers, unless u're really gud at it. you'll always find the basic stuff like locality of reference, pass by reference etc. Yet no one usually talks about the stuff you can do if you spend some time with the program. Statistical analysis is an amazing tool. The biggest thing that tend to slow down code is branching. Only very experienced people can truly minimize the branch penalty. But you can do some things on your own. See which options are more likely to occur, and try to keep these options higher up in the 'if' condition checks. Simple as this may sound, it's often ignored. Plus, removing unnecessary conditional checks. See if some condition checks can be reduced, e.g. if u're using nested if's see if conditions on the outer loop variable can be confined to the outer loop, it can speed things up by quite a bit.

Adding threads is also a good idea, especially for scientific codes. OpenMP is an amazing tool that you can use if you don't want to get your hands dirty with thread management. Most modern compilers support it, and using it, you can usually speed up your code by about twice (in most cases which can be parallelized) with about 5 minutes of effort. But not always, it actually slowed down my code by twice, even though it's eminently parallelizable. The fact that it was GCC may have something to do with it, their OpenMP implementation is still new. Open source guys, don't scream that i don't know what i'm doing, that's the reason and it's not gcc's fault, I'm decently experienced at code optimization, and i quite put the blame squarely on gcc, cause the same code was speeded up by vc++ when openmp was switched on.

You'll be amazed how some basic thinking can help you write code that can make those crappy looking algos run better than more sophisticated ones. To those who only believe in big-Oh's , try meeting a systems guy with programming experience, you'll be amazed at how O(n2) may be less than O(nlogn) :D