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> // dla funkcji std::chrono
class Timer
{
private:
// Aliasy typów, aby ułatwić dostęp do typu zagnieżdżonego
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;
// Tutaj znajduje się kod do czasu
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> // dla funkcji std::chrono
#include <cstddef> // dla std::size_t
#include <iostream>
#include <numeric> // dla std::iota
const int g_arrayElements { 10000 };
class Timer
{
private:
// Aliasy typów, aby ułatwić dostęp do typu zagnieżdżonego
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)
{
// Przejdź przez każdy element tablicy
// (z wyjątkiem ostatniego, który będzie już posortowany, zanim tam dotrzemy)
for (std::size_t startIndex{ 0 }; startIndex < (g_arrayElements - 1); ++startIndex)
{
// smallestIndex to indeks najmniejszego elementu, jaki napotkaliśmy w tej iteracji
// Zacznij od założenia, że najmniejszy element jest pierwszym elementem tej iteracji
std::size_t smallestIndex{ startIndex };
// Następnie poszukaj mniejszego elementu w pozostałej części tablicy
for (std::size_t currentIndex{ startIndex + 1 }; currentIndex < g_arrayElements; ++currentIndex)
{
// Jeśli znaleźliśmy element mniejszy niż poprzednio znaleziony najmniejszy
if (array[currentIndex] < array[smallestIndex])
{
// następnie ją śledź
smallestIndex = currentIndex;
}
}
// smallestIndex jest teraz najmniejszym elementem pozostałej tablicy
// zamień nasz element początkowy z naszym najmniejszym elementem (to sortuje go do prawidłowego miejsce)
std::swap(array[startIndex], array[smallestIndex]);
}
}
int main()
{
std::array<int, g_arrayElements> array;
std::iota(array.rbegin(), array.rend(), 1); // wypełnij tablicę wartościami 10000 do 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> // dla std::sort
#include <array>
#include <chrono> // dla funkcji std::chrono
#include <cstddef> // dla std::size_t
#include <iostream>
#include <numeric> // dla std::iota
const int g_arrayElements { 10000 };
class Timer
{
private:
// Aliasy typów, aby ułatwić dostęp do typu zagnieżdżonego
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); // wypełnij tablicę wartościami 10000 do 1
Timer t;
std::ranges::sort(array); // Since C++20
// Jeśli twój kompilator nie obsługuje C++ 20
// 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.