Problems while measuring performance

While browsing around StackOverflow I found a page about Square root function implementation. One of the answer points to an article containing different implementations of square root.

One of the things I like to do is pointing out obvious errors in benchmarks. It's not that I don't have an intimate understanding of these things, but if I can point out the error, is has to be obvious. One of the obvious errors in time measurement can be shown using a short pseudo code example.

Begin = Time();
For (I = N; I > 0; I--) {
     F();
}
End = Time();

AvgTime = (End - Begin) / N

This program starts by retrieving the time at the start. Then the function F is called N times. At the end we set End to the current time. The absolute difference between Begin and End is the time it took to call the function F, N times. We divide by N to find the time it took to call the function once.

A benchmark should be structured like this. It reduces the error of your measurement. Benchmarks that are nog structured like this are wrong.

Now back to the code in the article. On the surface the code looks a lot like my pseudo code. I will show why it isn't the same.

for (int j = 0; j  < AVG; j++) {   
    dur.Start();
    for (int i = 1; i < M; i++) {
        RefTotalPrecision+=sqrt((float) i);
    }
    dur.Stop();
    Temp+=dur.GetDuration();
}
RefTotalPrecision/=AVG;
Temp/=AVG;
RefSpeed=(float)(Temp)/CLOCKS_PER_SEC; 

In this code the variable AVG is set to 10 and M is set to 10.000. After running the variable RefTotalPrecision will contain the average precision of M sqrt calls. The variable RefSpeed should contain the average speed of M sqrt calls. It – however – doesn't.

The M loop makes it look like we average over many calls. We don't because the value we average with is AVG, which is used in the outer loop. To show what happens we remove the code that is measured. I also removed the averaging code at the end.

for (int j = 0; j < AVG; j++) {   
    dur.Start();
    // insert code to be measured
    dur.Stop();
    Temp+=dur.GetDuration();
}

The code measures the time 2 * AVG times, while it should only be measured twice, once at the start, and once at the end. To fix this, we need to move two lines and remove one character.

dur.Start();
for (int j = 0; j < AVG; j++)  
{   
    // insert code to be measured
}
dur.Stop();
Temp = dur.GetDuration();

We move the Start and Stop calls outside the loop. The error introduced by the measuring functions will now be divided by AVG, which is AVG times smaller. I also removed the +, it wasn't needed anymore.

Welcome

My name is Peter Stuifzand. You're reading my personal website.

Profiles