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

So your computer doesn't work or crawls

This is sometimes the most common complaint of someone who shelled out a good amount of money for a computer. The problem lies in the fact that configuring a computer is as much a science as an art, and even experienced computer scientists may (and mostly :D ) get it wrong, or not the best possible one for the amount of money you've paid. One of the big reasons I want to write this post is the deluge of poorly configured and doomed-to-fail configurations I see being sold in India.

Now the interesting part, computers aren't that compilcated, it's just that the people who design and develop things like to show they're doing something, and some are mathematicians (shock,horror). Now I have nothing against mathematicians, but most of them have this obsession for things called "correctness" and "completeness", which is what causes a lot of your problems. This tends to create complicated terms for simple things, which in well, obfuscated english, is called obfuscation, or simply unnecessary complication. Want examples? try googling some of the common acronyms your hear. But it's not like computer scientists are mad to complicate things, some of these definitions carry extra meaning than what their english meanings imply.

So lets get back to what I meant in the title. The most common problem is computers running slow. And I don't mean running slow later in its life, I mean slow to start with. I'm writing this on a computer with a 1.6Ghz processor with 256MB of ~200Mhz RAM, which (to anyone who knows anything about hardware) is a joke. The bigger joke is that the computer is an IBM Thinkpad. Now the standard Windows XP installation after bootup requires around 380MB of memory. So why are global corporations selling computers which will run excruciatingly slowly? If you haven't realised by now, the excess 120MB or so will be swapped in and out of disk, which is about a 100 times slower than memory. And, the even more wonderous, Windows Vista uses about 750MB at the first boot onwards. So how big does that leave your 1GB (or 1024MB) of RAM? not too big eh? Add to this, even your run-of-the-mill internet browser uses around 20MB of memory. To do what you might ask, well only the programmers know. But even this is after endless rounds of optimization, so it's not as bad.

I was introduced to computers on a 8086 which ran at something around 1Mhz, and the first computer I owned was a 386 (at a lightning fast 20MHz), with 4MB RAM and 80MB of disk. I've seen Windows grow from it's very first avataars to the behemoth it is today. I concede, it is still the easiest to use even today, amidst the onslaught of Linux, even I prefer it to Linux. It's again become pretty stable (Windows 3.1 never crashed in my lifetime :D) but it's still too big. So the best you can do, is get sufficient amounts of RAM(memory). Processors have become fast enough that lower megahertz don't hurt as much as lower MB of memory. Keep an eye out for 1 biggest number that's never advertised, cache. Most current processors have 2MB (of L2 cache, I might add for purists sake, ignore if you're a layman), and Celeron's have less of it. Even 1 MB less of this hits, and hits hard. Why? Your processor is like this guzzler, and memory and cache are the carts that get stuff to it from your disk, that larger they are, the more chunks you get to the processor, as simple as that. The guzzler has grown faster than the carts, and only very few people in the world can write programs for very few problems that keep the guzzler occupied at all times. In your usual computer, your processor does useful work for very little time, i.e. uses a small percentage of its thinking power, like we use our heads, only about 10% (it's true).

And if computers scare you, don't be, they've been designed by idiots like me and you, and just confidently use your common sense. In all the time I've experimented, I've never lost any data of worth, which you won't if you do your homework, and don't delete or format things mindlessly. So the next time you see a cryptic error, try googling it rather than call tech support, don't understand the terms? google them as well. You'll find that the answers you find will be better than what techsupp will give you. Any normal person can fix most of their problems if they just pay a little attention and devote a little time, and think what they would do if they designed something like this.