Disclaimer 1: This post was influenced heavily by my good friend, co-worker, and Haskell hacker Evan.

Disclaimer 2: Unless otherwise noted, I am completely making up terms in this article. I pulled them right out of the ether. Don’t expect to find industry conventions that agree with me.

Bob is a fictitious developer on my software team, who suggested that we could speed up some of our Qt/C++ code. The code under scrutiny is this:

for(int i=0; i<somelist .count(); i++)
{
    SomeClass *ptr = someList&#91;i&#93;;
    // Do something with "ptr" here
}
&#91;/cpp&#93;

Bob suggested that we do this instead:

&#91;cpp&#93;
SomeClass *ptr;
for(int i=0; i<someList.count(); i++)
{
    ptr = someList&#91;i&#93;;
    // Do something with "ptr" here
}
&#91;/cpp&#93;

Notice how we moved the <strong>ptr declaration outside the loop? That way, Bob surmised, the program doesn't allocate memory for <strong>ptr</strong> once per iteration of the loop. That should speed things up, right? Right?

This is an example of what I call <strong>Intuition-based Optimization</strong>, or <strong>IBO</strong> for short. IBO is a method of speeding up your code where the only tool you use is the raw power of your brain. It's where you apply human intuition to optimize your code, and no other tools, like profilers or measurements of any kind.

When you use IBO to speed up your code (or <strong>attempt</strong> to speed up your code), you should always remember the first and only rule of IBO:

<h2>st[i];
    // Do something with "ptr" here
}

Bob suggested that we do this instead:

SomeClass *ptr;
for(int i=0; iptr declaration outside the loop? That way, Bob surmised, the program doesn’t allocate memory for ptr once per iteration of the loop. That should speed things up, right? Right?

This is an example of what I call Intuition-based Optimization, or IBO for short. IBO is a method of speeding up your code where the only tool you use is the raw power of your brain. It’s where you apply human intuition to optimize your code, and no other tools, like profilers or measurements of any kind.

When you use IBO to speed up your code (or attempt to speed up your code), you should always remember the first and only rule of IBO:

The First and Only Rule of IBO: You are wrong.

There’s only one rule. You are wrong. If your computer program has a performance problem, and all you’ve done is think about what might be causing it and try to fix it, even if you use the almighty power of your human brain, which in its own right is a pretty advanced computer, you are wrong. You just are. Even if you aren’t wrong (hint: you are wrong), and the only tool you use for optimizing your code is IBO, then you don’t have a way to measure the effect of your code changes on your program’s actual speed.

All but the most obvious performance problems require tools to measure the effect of your code changes, and the most heinous problems require tools to identify where the bottle-necks are even happening.

I’ve lost track of the number of times I’ve used IBO to try to speed up some code, and failed. For example, it should be faster to use a hash-based lookup, like QHash, instead of a BST-based lookup, like QMap, in theory. In practice, though, there are other considerations. How many elements are in your data structure? How fast are the elements%2The First and Only Rule of IBO: You are wrong.

There’s only one rule. You are wrong. If your computer program has a performance problem, and all you’ve done is think about what might be causing it and try to fix it, even if you use the almighty power of your human brain, which in its own right is a pretty advanced computer, you are wrong. You just are. Even if you aren’t wrong (hint: you are wrong), and the only tool you use for optimizing your code is IBO, then you don’t have a way to measure the effect of your code changes on your program’s actual speed.

All but the most obvious performance problems require tools to measure the effect of your code changes, and the most heinous problems require tools to identify where the bottle-necks are even happening.

I’ve lost track of the number of times I’ve used IBO to try to speed up some code, and failed. For example, it should be faster to use a hash-based lookup, like QHash, instead of a BST-based lookup, like QMap, in theory. In practice, though, there are other considerations. How many elements are in your data structure? How fast are the elements’ hash-code functions vs. their comparison operators? Just because an algorithm is O(1) doesn’t mean it’s faster than an O(n) algorithm. There are just too many other variables besides order of complexity (not to mention, big “O” notation really only applies to theoretically very large datasets anyway).

So, if Intuition-based Optimization is so crappy at actually making code faster, then what is the right way?

Evidence-based Optimization

Or EBO, for short. This is where you use actual evidence to diagnose performance problems and measure the speed impact of your code changes. There are several techniques for doing this. Let’s look at a few.

Technique 1: The time command

In the simplest of situations, all you want to know is how long it takes your (command line) program to run. If you’re using a Unix-ish operating system like Linux or Mac OS X, you can use the time command to do this. Here’s an example:

$ time some-program

real    0m2.235s
user    0m0.155s
sys     0m0.077 hash-code functions vs. their comparison operators? Just because an algorithm is O(1) doesn't mean it's faster than an O(n) algorithm. There are just too many other variables besides order of complexity (not to mention, big "O" notation really only applies to theoretically very large datasets anyway).

So, if Intuition-based Optimization is so crappy at actually making code faster, then what is the right way?

<h2>Evidence-based Optimization</h2>

Or <b>EBO</b>, for short. This is where you use actual <b>evidence</b> to diagnose performance problems and measure the speed impact of your code changes. There are several techniques for doing this. Let's look at a few.

<h3>Technique 1: The time command</h3>

In the simplest of situations, all you want to know is how long it takes your (command line) program to run. If you're using a Unix-ish operating system like Linux or Mac OS X, you can use the <b>time</b> command to do this. Here's an example:

[bash]
$ time some-program

real    0m2.235s
user    0m0.155s
sys     0m0.075s

In a nutshell, the time command will tell you how long your program took to run. Look at the “real” time to get this info. The other two times listed tell you a little about where your program spent its time, and you can read a lot of cryptic details about these numbers from the time man page. For most simple applications, the “real” time is adequate.

Technique 2: Measuring time in your program

A more common case is that a subset of your application is running slowly, but you don’t know exactly where. Maybe you have an educated guess where the code is getting bogged down, but you want to use actual evidence to identify the code that is causing the problem (congratulations on wanting to use evidence instead of intuition by the way).

If you’re using Qt and C++ (which by the way is the only non-insane way to write C++ code), you can use the QTime class to do this. If you are using version 4.7 or newer5s
[/bash]

In a nutshell, the time command will tell you how long your program took to run. Look at the “real” time to get this info. The other two times listed tell you a little about where your program spent its time, and you can read a lot of cryptic details about these numbers from the time man page. For most simple applications, the “real” time is adequate.

Technique 2: Measuring time in your program

A more common case is that a subset of your application is running slowly, but you don’t know exactly where. Maybe you have an educated guess where the code is getting bogged down, but you want to use actual evidence to identify the code that is causing the problem (congratulations on wanting to use evidence instead of intuition by the way).

If you’re using Qt and C++ (which by the way is the only non-insane way to write C++ code), you can use the QTime class to do this. If you are using version 4.7 or newer, you can use the QElapsedTimer class for a little bit more precision, but I have not needed that much more precision.

Here’s how you use QTime:

QTime time;
time.start()

// Code to measure goes here

qDebug() < < "Took:" << time.elapsed() << "ms"; [/cpp] It's fairly simple. There are caveats to be aware of, though. If you are measuring code that executes in less than a few milliseconds, QTime will not give meaningful results. There are a few ways to work around this problem. You can simply increase the number of iterations, using a naive approach like this: [cpp] QTime time; time.start() for(int i=0; i<10000; i++) { // Code to measure goes here } qDebug() << "Took:" << ((float)time.elapsed() / 10000) << "ms per iteration"; [/cpp] You can also get more clever about where to put your calls to QTime::start()., you can use the QElapsedTimer class for a little bit more precision, but I have not needed that much more precision.

valgrind --tool=callgrind /path/to/your/application

kcachegrind callgrind.out

valgrind --tool=callgrind /path/to/your/application

kcachegrind callgrind.out