5

Whenever I try to compare the execution time of two competing algorithms (using C++), I use std::chrono as formerly suggested for example in this question: Measuring execution time of a function in C++

However, I always notice that the order of execution of the algorithms being compared significantly impacts on the execution times. It often even alters which of the competing algorithms is to be considered the fastest. For instance, suppose I have two algorithms algo1 and algo2.

What I mean is that the code below:

std::chrono::high_resolution_clock::time_point start0, start1;
std::chrono::high_resolution_clock::time_point end0, end1;

start1 = std::chrono::high_resolution_clock::now();
algo1();
end1 = std::chrono::high_resolution_clock::now();

start2 = std::chrono::high_resolution_clock::now();
algo2();
end2 = std::chrono::high_resolution_clock::now();

auto time_elapsed1 = std::chrono::duration_cast<std::chrono::nanoseconds>(end1 - start1).count();
auto time_elapsed2 = std::chrono::duration_cast<std::chrono::nanoseconds>(end2 - start2).count();

Gives different results from the code below:

std::chrono::high_resolution_clock::time_point start0, start1;
std::chrono::high_resolution_clock::time_point end0, end1;

start2 = std::chrono::high_resolution_clock::now();
algo2();
end2 = std::chrono::high_resolution_clock::now();

start1 = std::chrono::high_resolution_clock::now();
algo1();
end1 = std::chrono::high_resolution_clock::now();

auto time_elapsed1 = std::chrono::duration_cast<std::chrono::nanoseconds>(end1 - start1).count();
auto time_elapsed2 = std::chrono::duration_cast<std::chrono::nanoseconds>(end2 - start2).count();

And that for almost any algorithms 1 and 2 that I might want to compare.

So, my question is two-folded: 1) why is that the case, i.e. why does the order matter? 2) Is there a better way of comparing two algorithms in what regards their execution time, i.e. how should one proceed for better and more accurate comparisons?

PS: of course, I always test with all compilers' optimizations on.

Community
  • 1
  • 1
Kim Shutter
  • 187
  • 1
  • 7
  • 4
    You need to run the algo multiple times and get an average. Things can be loaded into cache that will affect subsequent runs. – NathanOliver Aug 15 '16 at 19:19
  • You have to make sure the algorithms run long enough to get a meaningful time lapse. Given that, the thing to watch out for is caching of data. Try running each algo() twice consecutively and time the second runs. – doug Aug 15 '16 at 19:21
  • 2
    I assume that your functions have observable side effects. As otherwise they may be simply optimized away completely. Also, what @NathanOliver said, run each algorithm a couple thousand/million times and get a mean/average. Benchmarking is surprisingly hard ;) – Jesper Juhl Aug 15 '16 at 19:23
  • @JesperJuhl could be why a good benchmark produces hard numbers. – user4581301 Aug 15 '16 at 19:32

1 Answers1

1

This is most likely to be due to caching.

You can easily verify the effect of caching by running the SAME algorithm multiple times. You will likely notice that the time taken of the very first execution takes significantly longer than subsequent executions.

When I had to compare two algorithms for my PhD thesis I ended up executing each algorithm 10 times in a row, discarded the very first result, then averaged the remaining 9 results, and those 9 results were very consistent.

It is arguable whether the first result that was discarded is important or not, but for me it wasn't, because I was more interested in comparing the relative performances of the two algorithms (thus was looking for consistent run times of each algorithm) rather than measuring the impact of caching or the absolute performances of each algorithm under different circumstances.

wookie919
  • 3,054
  • 24
  • 32
  • What did the trick for me was exactly your suggestion: not only running the algorithm multiple times, but discarding the initial values. Much more accurate - which can be verified against any analytical problem whose real solution is known in advance. Thanks! – Kim Shutter Sep 05 '16 at 00:41