Do Those Optimizations Really Optimize?

How often have you encountered this scenario?

You open a problem, read the problem statements, and realize that it requires a fast algorithm, because of many complexities behind it. And soon you realize again that the algorithm must really fast: the time limit is too strict.

And you learn many optimizations from many resources, and wonder which optimizations really take effect.

You might want to read this tip, then.

Create your own benchmarking programs

Now it’s the time for you whether or not a given optimization really works. You just have to create two small programs. One that is not optimized, and the optimized one.

For example, suppose you are curious if a literal comparison does better than STL’s max() function. It is a classic optimization, and you want to prove it.

It may be fine to directly create two programs that contain only those instructions of interest; comparison and max() function. But then you will encounter difficulties when comparing the time used to execute those two sets of instructions. Those small programs will run in several milliseconds (maybe), so how to compare them accurately? A nice workaround is to place the instructions in a loop.

Overall, your benchmarking programs should look like this.

// benchmark1.cpp:
int main()
{
    int a = 1, b = 2;
    for (int i = 0; i < 100000000; i++)
        if (a > b)
            a;
        else
            b;
}

// benchmark2.cpp:
#include <algorithm>
int main()
{
    int a = 1, b = 2;
    for (int i = 0; i < 100000000; i++)
        std::max(a, b);
}

There’s nothing about the constant 100000000 in the above code. Any big value will do, as long as the program will execute in a reasonable amount of time. And make sure the constant is same between the two versions of code.

Compile the two source codes, so that the programs are named benchmark1 and benchmark2.

Running the programs

After setting up the testing programs, the next step is running them and measuring the time used by each program. Of course not using a manual stopwatch! In Linux terminal, there is a handy built-in program, called time, that measure it accurately.

So, open a terminal, change the current directory to that of the two programs, and execute

time ./benchmark1
time ./benchmark2

Three values will appear after each program finishes executing. They are real, user, and sys. You should consider only the real value. That is the time consumed by each program. Example output:

real    0m0.740s
user    0m0.736s
sys     0m0.004s

Analyzing the results

The two runs of benchmark1 and benchmark2 gives you two values. It is up to you now how to interpret those values! If the conjectured optimized version has a lower running time, then it may be worth using the optimized code.

A good habit in running an experimental test is doing it more than once. So I advise you to execute each program, say, ten times, and take the average time.

Hope this helps you analyzing many types of optimizations!

Enjoyed this article? Subscribe to our RSS feed for free!

Be the first to comment!