Jak zmierzyć czas obliczeń?

Wyobraźmy sobie, że chcielibyśmy zmierzyć czas wykonania jakiegoś fragmentu programu. Na laboratorium, ćwiczeniach lub tylko na listach zadań poznaliśmy funkcję time():

#include <time.h>
...
time_t czas;
czas = time( NULL )

Funkcja time zwraca (gdy nie było błędu) aktualny czas jako liczbę sekund od początku „Epoki"¹. Kiedyś (i być może w dalszym ciągu na niektórych starych systemach) czas był przechowywany w zmiennej 32-bitowej (co powodowało, że ten system liczenia czasu przestanie działać w 2038 roku). Dziś przechowywany jest w zmiennej typu time_t, który jest zdefinowany w sposób pozwalający efektywnie przechowywać czas (może to być zmienna typu long int).

Funkcja ta może być więc wykorzystana do pomiaru odcinków czasu w następujący sposób:

time_t Start, Stop;
...

Start = time(NULL);
// Tu coś robimy, co zajmuje trochę czasu
Stop = time(NULL);

Wartość różnicy Stop - Start zawiera czas obliczeń. Niestety, rozdzielczość pomiaru czasu wynosi tylko jedną sekundę. Zatem nie zawsze można z tego skorzystać. Na przykład

    Start = time(NULL);
    for(i=0; i < N; i++)
    sin(0.333333);
    Stop = time(NULL);

Dla N równego 10000000 (dziesięć milionów) czas obliczeń jest równy 0. Dla N równego 100 milionów — 1 sekunda.

Zatem potrzebny jest dokładniejszy zegar…

Funkcja gettimeofday podaje czas od początku Epoki w mikrosekundach. Jej definicja jest następująca:

#include <sys/time.h>

int gettimeofday(struct timeval *tv, struct timezone *tz);

Pierwszy argument funkcji (wskaźnik do struktury timeval)

struct timeval {
    time_t      tv_sec;     /* seconds */
    suseconds_t tv_usec;    /* microseconds */
};

Zwraca czas (od początku Epoki) jako pełną liczbę sekund (składowa tv_sec) i liczbę mikrosekund w rozpoczętej sekundzie (składowa tv_usec). I teraz

struct timeval start, stop;
unsigned long long Start, Stop;
// ......
gettimeofday(&start, NULL);
Start = ((unsigned long long) start.tv_sec * 1000000) 
        + start.tv_usec;
for (i = 0; i < N  ; i++) 
{
    sin(0.33333);
}
gettimeofday(&stop, NULL);
Stop = ((unsigned long long) stop.tv_sec * 1000000) 
       + stop.tv_usec;
printf("Czas: %ld\n", Stop - Start);

Pozwala wyznaczyć czas operacji nawet dla N = 100000 (na moim laptopie czas ten wynosi około 500 mikrosekund). Ciągle oblczenie czasu pojedynczej operacji wyliczenia nie jest możliwe, ale…

Minus jeden do potęgi n

W jednym z zadań na kolokwium pojawił się problem wyliczenia wyrażenia: $$(-1)^n$$ Większość studentów zaproponowała, żeby wyliczyć wartość tego wyrażenia używając funkcji pow: pow(-1, n). Sprawdźmy zatem ile trwa wykonanie funkcji pow:

gettimeofday(&start, NULL);
Start = ((unsigned long long) start.tv_sec * 1000000) 
        + start.tv_usec;
k = -1
for (i = 0; i < N  ; i++) 
{
    pow(k, i);
}
gettimeofday(&stop, NULL);
Stop = ((unsigned long long) stop.tv_sec * 1000000) 
       + stop.tv_usec;
printf("Czas: %ld\n", Stop - Start);

Czas obliczeń dla N = 1000000 (milion) wynosi około 120–130 tysięcy mikrosekund. Obliczenia można jednak uprościć. Zamiast używać pow(k, i) można użyć k=k*(-1) i wówczas czas obliczeń spada do około 5500 mikrosekund (czyli przyśpieszenie około 22 razy)!

Tak na marginesie zamina k=k*(-1) na k = -k nie przynosi już żadnego istotnego przyśpieszenia.

Możemy poprosić kompilator, żeby w trakcie kompilacji dokonał optymalizacji kodu. W tym przypadku czas spadnie do ciut mniej niż 100 tysięcy mikrosekund w pierwszym przypadku (pow) i 1200 mikrosekund w drugim, więc przyśpieszenie będzie około 80 razy!