Porównanie czasu wykonywania algorytmów: dlaczego kolejność wykonywania ma znaczenie?

Question

Ilekroć próbuję porównać czas realizacji dwóch konkurujących ze sobą algorytmów (z wykorzystaniem C++), używam std::chrono jak dawniej zaproponował na przykład w tej kwestii: Measuring execution time of a function in C++

Jednak zawsze zauważyć, że kolejność wykonywania algorytmów bycia w porównaniu znacząco wpłynęły na czasy realizacji. Często nawet zmienia to, który z konkurencyjnych algorytmów należy uznać za najszybszy. Załóżmy na przykład, że mam dwa algorytmy: algo1 i algo2.

Chodzi mi o to, że poniższy kod:

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

daje różne wyniki z poniższym kodzie:

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

i że dla prawie wszystkich algorytmów 1 i 2, które mogą chcę porównać .

Moje pytanie jest zatem złożone: 1) dlaczego tak jest, tzn. Dlaczego zamówienie ma znaczenie? 2) Czy istnieje lepszy sposób porównania dwóch algorytmów pod względem czasu ich wykonania, tj. Jak należy postępować w celu uzyskania lepszych i dokładniejszych porównań?

PS: Oczywiście, zawsze testuję przy włączonych optymalizacjach wszystkich kompilatorów.

Answer 1

Jest to najprawdopodobniej spowodowane buforowaniem.

Możesz łatwo zweryfikować efekt buforowania, uruchamiając algorytm SAME wiele razy. Najprawdopodobniej zauważysz, że czas wykonania pierwszej realizacji trwa znacznie dłużej niż kolejne egzekucje.

Kiedy musiałem porównać dwa algorytmy do mojej pracy doktorskiej, zakończyłem wykonywanie każdego algorytmu 10 razy z rzędu, odrzuciłem pierwszy wynik, a następnie uśredniono pozostałe 9 wyników, a te 9 wyników było bardzo spójne.

Można argumentować, czy pierwszy wynik, który został odrzucony, jest ważny czy nie, ale dla mnie tak nie było, ponieważ bardziej interesowałem się porównywaniem względnych osiągów dwóch algorytmów (w ten sposób szukałem spójnych czasów uruchamiania każdy algorytm) zamiast mierzyć wpływ buforowania lub bezwzględnych wydajności każdego algorytmu w różnych okolicznościach.