Algorithm runtime comparison: why does execution order matter?

Question

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

However, I always notice that the execution order of the compared algorithms significantly affects the execution time. It often even changes which of the competing algorithms should be considered the fastest. For example, suppose I have two algorithms algo1 and algo2 .

I mean 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(); 

Gets 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 for almost any algorithms 1 and 2 that I can compare.

So, my question is twofold: 1) why is this so, that is why the question is order? 2) Is there a better way to compare the two algorithms in terms of their execution time, i.e. How to proceed for more accurate and accurate comparisons?

PS: of course, I always check all compiler optimizers on.

Answer 1

This is most likely due to caching.

You can easily check the effect of caching by running the SAME algorithm several times. You will probably notice that the time spent on the very first performance takes much longer than subsequent executions.

When I had to compare two algorithms for my Ph.D. thesis, I completed each algorithm 10 times in a row, discarded the first result, then averaged the remaining 9 results, and these 9 results were very consistent.

Is it possible that the first result that was discarded is important or not, but for me it is not, because I was more interested in comparing the relative characteristics of these two algorithms (thus, they looked for sequential execution times of each algorithm) rather than measuring the effect caching or the absolute characteristics of each algorithm under different circumstances.