Comparing algorithms' execution time: why does the order of execution matter?

Question

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.

Answer 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.