Podczas pisania kodu czasami napotkasz przypadki, w których nie masz pewności, czy ta czy inna metoda będzie bardziej wydajna. Jak więc to sprawdzić?
Jednym z prostych sposobów jest sprawdzenie czasu działania kodu, aby zobaczyć, ile czasu zajmie jego wykonanie. C++ 11 zawiera pewną funkcjonalność w bibliotece chrono, która właśnie to umożliwia. Jednak korzystanie z biblioteki chrono jest nieco tajemnicze. Dobra wiadomość jest taka, że możemy łatwo zawrzeć całą potrzebną funkcjonalność synchronizacji w klasie, której możemy następnie używać w naszych własnych programach.
Oto klasa:
#include <chrono> // for std::chrono functions
class Timer
{
private:
// Type aliases to make accessing nested type easier
using Clock = std::chrono::steady_clock;
using Second = std::chrono::duration<double, std::ratio<1> >;
std::chrono::time_point<Clock> m_beg { Clock::now() };
public:
void reset()
{
m_beg = Clock::now();
}
double elapsed() const
{
return std::chrono::duration_cast<Second>(Clock::now() - m_beg).count();
}
};To wszystko! Aby z niego skorzystać, tworzymy instancję obiektu Timer na górze naszej głównej funkcji (lub gdziekolwiek, gdzie chcemy rozpocząć odliczanie czasu), a następnie wywołujemy funkcję członkowską elapsed() za każdym razem, gdy chcemy wiedzieć, ile czasu zajęło wykonanie programu do tego punktu.
#include <iostream>
int main()
{
Timer t;
// Code to time goes here
std::cout << "Time elapsed: " << t.elapsed() << " seconds\n";
return 0;
}Wykorzystajmy to teraz w rzeczywistym przykładzie, w którym sortujemy tablicę składającą się z 10000 elementów. Najpierw użyjmy algorytmu sortowania przez wybór, który opracowaliśmy w poprzednim rozdziale:
#include <array>
#include <chrono> // for std::chrono functions
#include <cstddef> // for std::size_t
#include <iostream>
#include <numeric> // for std::iota
const int g_arrayElements { 10000 };
class Timer
{
private:
// Type aliases to make accessing nested type easier
using Clock = std::chrono::steady_clock;
using Second = std::chrono::duration<double, std::ratio<1> >;
std::chrono::time_point<Clock> m_beg{ Clock::now() };
public:
void reset()
{
m_beg = Clock::now();
}
double elapsed() const
{
return std::chrono::duration_cast<Second>(Clock::now() - m_beg).count();
}
};
void sortArray(std::array<int, g_arrayElements>& array)
{
// Step through each element of the array
// (except the last one, which will already be sorted by the time we get there)
for (std::size_t startIndex{ 0 }; startIndex < (g_arrayElements - 1); ++startIndex)
{
// smallestIndex is the index of the smallest element we’ve encountered this iteration
// Start by assuming the smallest element is the first element of this iteration
std::size_t smallestIndex{ startIndex };
// Then look for a smaller element in the rest of the array
for (std::size_t currentIndex{ startIndex + 1 }; currentIndex < g_arrayElements; ++currentIndex)
{
// If we've found an element that is smaller than our previously found smallest
if (array[currentIndex] < array[smallestIndex])
{
// then keep track of it
smallestIndex = currentIndex;
}
}
// smallestIndex is now the smallest element in the remaining array
// swap our start element with our smallest element (this sorts it into the correct place)
std::swap(array[startIndex], array[smallestIndex]);
}
}
int main()
{
std::array<int, g_arrayElements> array;
std::iota(array.rbegin(), array.rend(), 1); // fill the array with values 10000 to 1
Timer t;
sortArray(array);
std::cout << "Time taken: " << t.elapsed() << " seconds\n";
return 0;
}Na maszynie autora trzy serie dały czasy 0,0507, 0,0506 i 0,0498. Możemy więc powiedzieć, że około 0,05 sekundy.
Teraz wykonaj ten sam test, używając std::sort ze standardowej biblioteki.
#include <algorithm> // for std::sort
#include <array>
#include <chrono> // for std::chrono functions
#include <cstddef> // for std::size_t
#include <iostream>
#include <numeric> // for std::iota
const int g_arrayElements { 10000 };
class Timer
{
private:
// Type aliases to make accessing nested type easier
using Clock = std::chrono::steady_clock;
using Second = std::chrono::duration<double, std::ratio<1> >;
std::chrono::time_point<Clock> m_beg{ Clock::now() };
public:
void reset()
{
m_beg = Clock::now();
}
double elapsed() const
{
return std::chrono::duration_cast<Second>(Clock::now() - m_beg).count();
}
};
int main()
{
std::array<int, g_arrayElements> array;
std::iota(array.rbegin(), array.rend(), 1); // fill the array with values 10000 to 1
Timer t;
std::ranges::sort(array); // Since C++20
// If your compiler isn't C++20-capable
// std::sort(array.begin(), array.end());
std::cout << "Time taken: " << t.elapsed() << " seconds\n";
return 0;
}Na komputerze autora dało to wyniki: 0,000693, 0,000692 i 0,000699. Czyli w zasadzie około 0,0007.
Innymi słowy, w tym przypadku std::sort jest 100 razy szybsze niż sortowanie przez wybór, które sami napisaliśmy!
Rzeczy, które mogą mieć wpływ na wydajność twojego programu
Wyznaczenie czasu uruchomienia programu jest dość proste, ale na wyniki może znacząco wpływać wiele rzeczy i ważne jest, aby mieć świadomość, jak prawidłowo mierzyć i jakie czynniki mogą mieć wpływ na czas.
Po pierwsze, upewnij się, że używasz celu kompilacji wydania, a nie celu kompilacji debugowania. Cele kompilacji debugowania zazwyczaj wyłączają optymalizację, a ta optymalizacja może mieć znaczący wpływ na wyniki. Na przykład przy użyciu celu kompilacji debugowania uruchomienie powyższego przykładu std::sort na komputerze autora zajęło 0,0235 sekundy — 33 razy dłużej!
Po drugie, na wyniki synchronizacji mogą mieć wpływ inne rzeczy, które system może robić w tle. Upewnij się, że Twój system nie wykonuje żadnych czynności obciążających procesor, pamięć lub dysk twardy (np. nie grasz w grę, nie szukasz pliku, nie uruchamiasz skanowania antywirusowego lub nie instalujesz aktualizacji w tle). Pozornie niewinne rzeczy, takie jak bezczynne przeglądarki internetowe, mogą tymczasowo zwiększyć wykorzystanie procesora do 100%, gdy aktywna karta obróci się w nowym banerze reklamowym i będzie musiała przeanalizować mnóstwo kodu JavaScript. Im więcej aplikacji możesz wyłączyć przed pomiarem, tym mniej prawdopodobne jest, że rozbieżność w wynikach będzie mniejsza.
Po trzecie, jeśli Twój program korzysta z generatora liczb losowych, konkretna sekwencja wygenerowanych liczb losowych może mieć wpływ na czas. Na przykład, jeśli sortujesz tablicę wypełnioną liczbami losowymi, wyniki prawdopodobnie będą się różnić w zależności od uruchomienia, ponieważ liczba operacji zamiany wymaganych do posortowania tablicy będzie się różnić w zależności od uruchomienia. Aby uzyskać bardziej spójne wyniki w wielu uruchomieniach programu, możesz tymczasowo zaszczepić generator liczb losowych wartością dosłowną (zamiast std::random_device lub zegara systemowego), tak aby generował tę samą sekwencję liczb przy każdym uruchomieniu. Jeśli jednak wydajność Twojego programu w dużym stopniu zależy od konkretnej wygenerowanej losowej sekwencji, może to również prowadzić do ogólnie mylących wyników.
Po czwarte, upewnij się, że nie planujesz czasu oczekiwania na wprowadzenie danych przez użytkownika, ponieważ czas potrzebny użytkownikowi na wprowadzenie czegoś nie powinien być częścią Twoich rozważań dotyczących czasu. Jeśli wymagane jest wprowadzenie danych przez użytkownika, rozważ dodanie sposobu zapewnienia tych danych wejściowych, które nie będą czekać na użytkownika (np. linia poleceń, plik z ścieżką kodu wyznaczającą drogę wokół danych wejściowych).
Pomiar wydajności
Podczas pomiaru wydajności swojego programu zbierz co najmniej 3 wyniki. Jeśli wszystkie wyniki są podobne, prawdopodobnie reprezentują one rzeczywistą wydajność programu na tym komputerze. W przeciwnym razie kontynuuj wykonywanie pomiarów, aż uzyskasz grupę podobnych wyników (i zrozumiesz, które inne wyniki są wartościami odstającymi). Nierzadko zdarza się, że jedna lub więcej wartości odstających występuje, ponieważ system robi coś w tle podczas niektórych z tych uruchomień.
Jeśli wyniki wykazują dużą rozbieżność (i nie są dobrze zgrupowane), na program prawdopodobnie znacząco wpływają inne rzeczy dziejące się w systemie lub skutki randomizacji w aplikacji.
Ponieważ na pomiary wydajności wpływa wiele czynników (szczególnie szybkość sprzętu, ale także system operacyjny, działające aplikacje, itp.), bezwzględne pomiary wydajności (np. „program działa w 10 sekund”) na ogół nie są zbyt przydatne poza zrozumieniem, jak dobrze program działa na konkretnej maszynie, na której Ci zależy. Na innym komputerze ten sam program może działać w ciągu 1 sekundy, 10 sekund lub 1 minuty. Trudno to stwierdzić bez dokonania pomiaru całego spektrum różnych urządzeń.
Jednak w przypadku pojedynczej maszyny przydatne mogą być względne pomiary wydajności. Możemy zebrać wyniki wydajności kilku różnych wariantów programu, aby określić, który wariant jest najskuteczniejszy. Na przykład, jeśli wariant 1 działa w 10 sekund, a wariant 2 w 8 sekund, wariant 2 będzie prawdopodobnie szybszy na wszystkich podobnych maszynach, niezależnie od bezwzględnej prędkości tej maszyny.
Po zmierzeniu drugiego wariantu, dobrym sposobem sprawdzenia poprawności jest ponowne zmierzenie pierwszego wariantu. Jeśli wyniki pierwszego wariantu są zgodne z początkowymi pomiarami dla tego wariantu, wówczas wynik obu wariantów powinien być w miarę porównywalny. Na przykład, jeśli wariant 1 działa w 10 sekund, a wariant 2 w 8 sekund, a następnie ponownie mierzymy wariant 1 i otrzymujemy 10 sekund, to możemy zasadnie stwierdzić, że pomiary dla obu wariantów były rzetelnie zmierzone, a wariant 2 jest szybszy.
Jeśli jednak wyniki pierwszego wariantu nie są już zgodne z początkowymi pomiarami dla tego wariantu, oznacza to, że na maszynie wydarzyło się coś, co teraz wpływa na wydajność i trudno będzie stwierdzić, czy różnice w pomiarach wynikają z wariantu lub z samej maszyny. W takim przypadku najlepiej odrzucić istniejące wyniki i dokonać ponownego pomiaru.