2. comp
  3. Измерение времени выполнения блока кода на C/С++

Измерение времени выполнения блока кода на C/С++

Date Редакция Категория comp Теги C / linux / windows

Распространенный совет, который дают новичкам: подключить библиотеку time.h и, с помощью функции получения времени clock(), определить время перед выполнением блока кода и после него. Время выполнения блока будет разницей полученных времен. То есть, что-то вроде

#include <stdio.h>
#include <time.h>       /* clock_t, clock(), CLOCKS_PER_SEC */

int main ()
{
  clock_t t;

  t = clock();

  /* Блок кода */

  t = clock() - t;

  printf ("It took me %d clicks (%f seconds).\n", 
          (int)t, ((double)t)/CLOCKS_PER_SEC);
  return 0;
}

Здесь clock_t — арифметический тип для представления времени; clock() возвращает время, фиксируемое процессором от начала выполнения программы, или -1, если оно не известно. Для выражения этого времени в секундах применяется формула clock()/CLOCKS_PER_SEC.

Однако такой способ плохо подходит для измерения коротких интервалов времени. Рассмотрим следующий код

#include <stdio.h>
#include <time.h>       /* clock_t, clock, CLOCKS_PER_SEC */
#include <math.h>       /* sqrt */

int frequency_of_primes (int n) {
  int i,j;
  int freq = n-1;
  for (i=2; i<=n; ++i) for (j=sqrt(i);j>1;--j) if (i%j==0) {--freq; break;}
  return freq;
}

int main ()
{
  clock_t t;
  const int maxnum = 100000;
  int f;
  printf ("Calculating...\n");
  t = clock();
  f = frequency_of_primes(maxnum);
  t = clock() - t;
  printf ("The number of primes lower than %d is: %d\n",maxnum,f);
  printf ("It took me %d clicks (%f seconds).\n",
          (int)t,((double)t)/CLOCKS_PER_SEC);
  return 0;
}

Он (взят отсюда) составлен по приведенной выше схеме и подсчитывает количество простых чисел на интервале от 0 до maxnum. Сущность вычислений сейчас не важна -- они просто занимают некоторое время, которое мы пытаемся подсчитать. Выполнив, получим

 Calculating...
 The number of primes lower than 100000 is: 9592
 It took me 140000 clicks (0.140000 seconds).

Теперь уменьшим maxnum в 10 раз

 Calculating...
 The number of primes lower than 10000 is: 1229
 It took me 0 clicks (0.000000 seconds).

Количество простых чисел сократилось даже менее, чем в 10 раз. Казалось бы, мы вправе ожидать ненулевого результата, но... Недаром пишут в руководстве по clock():

 The clock() function returns an approximation of processor time used by the program.

Видимо, все дело в этом "approximation".

Обращает на себя внимание то, что следующая за выводом программы строка

 Process returned 0 (0x0)   execution time : 0.007 s

показывала ненулевое время. То есть системные средства считают все, что нужно, и пора ими воспользоваться.

Сначала приведем решения для Linux, хотя они работают и в Windows при использовании компилятора MinGW. Итак, альтернативами clock() являются gettimeofday() и clock_gettime().

Функция gettimeofday

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

позволяет получить время в виде структуры timeval (вторая структура -- timezone считается устаревшей и при вызове заменяется NULL'ом):

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

которая содержит число секунд и микросекунд, прошедших с 1-го января 1970 г. 00:00:00 Всемирного времени. Имеется в виду, что с начального момента прошло tv_sec секунд и еще tv_usec микросекунд.

Микросекунды представляются мне слишком кратким интервалом. Напишем функцию, возвращающую число миллисекунд с начального момента времени

#include <sys/time.h>   /* gettimeofday, timeval */

long mtime()
{
  struct timeval t;

  gettimeofday(&t, NULL);
  long mt = (long)t.tv_sec * 1000 + t.tv_usec / 1000;
  return mt;
}

Тестовую программу переделаем следующим образом:

#include <stdio.h>
#include <sys/time.h>   /* gettimeofday, timeval */
#include <math.h>       /* sqrt */

int frequency_of_primes (int n) {...}
long mtime() {...}

int main ()
{
  long t;
  const int maxnum = 100000;
  int f;
  printf ("Calculating...\n");
  t = mtime();
  f = frequency_of_primes(maxnum);
  t = mtime() - t;
  printf ("The number of primes lower than %d is: %d\n",maxnum,f);
  printf ("It took me %ld milliseconds.\n",t);
  return 0;
}

В результате получим

Calculating... The number of primes lower than 100000 is: 9592 It took me 144 milliseconds.

и

Calculating... The number of primes lower than 10000 is: 1229 It took me 7 milliseconds.

соответственно.

Конечно, по хорошему, нужно было бы испытать код несколько раз и выдать среднее значение. Мы этого не делаем, поскольку нас интересует не столько конкретная цифра, сколько сама возможность подсчитать время выполнения.

Функция clock_gettime() из time.h обеспечивает доступ к нескольким видам системных таймеров и имеет наносекундное разрешение. Прототип функции имеет вид:

int clock_gettime(clockid_t clk_id, struct timespect *tp);

clk_id позволяет выбрать вид таймера, например (приведу фрагмент из руководства, там есть и другие таймеры):

  • CLOCK_REALTIME, a system-wide realtime clock.
  • CLOCK_PROCESS_CPUTIME_ID, high-resolution timer provided by the CPU for each process.
  • CLOCK_THREAD_CPUTIME_ID, high-resolution timer provided by the CPU for each of the threads.

Время сохраняется в структуре timespec

struct timespec {
    time_t tv_sec; /* seconds */
    long tv_nsec; /* nanoseconds */
};

по тому же принципу, что и в timeval: с начального момента прошло tv_sec секунд и еще tv_nsec наносекунд.

Запишем функцию, возвращающую время в миллисекундах, основываясь на clock_gettime()

#include <time.h>       /* clock_gettime, timespec */

long mtime()
{
  struct timespec t;

  clock_gettime(CLOCK_REALTIME, &t);
  long mt = (long)t.tv_sec * 1000 + t.tv_nsec / 1000000;
  return mt;
}

Теперь -- Windows-решение, работающее в Visual Studio. Это функция GetTickCount(), возвращающая время в миллисекундах с момента старта операционной системы и в течение 49.7 дней:

DWORD WINAPI GetTickCount(void);

Поскольку GetTickCount() возвращает DWORD, счетчик времени сбрасывается в ноль через 49.7 дней. Эта проблема решается использованием GetTickCount64()

ULONGLONG WINAPI GetTickCount64(void);

переполнение в которой вряд ли возможно.

Тестовая программа с использованием GetTickCount():

#include <stdio.h>
#include <Windows.h>    /* GetTickCount */
#include <math.h>       /* sqrt */

int frequency_of_primes (int n) {
  int i,j;
  int freq = n-1;
  for (i=2; i<=n; ++i) for (j=(int)sqrt((double)i);j>1;--j) if (i%j==0) {--freq; break;}
  return freq;
}

int main ()
{
  long t;
  const int maxnum = 100000;
  int f;
  printf ("Calculating...\n");
  t = GetTickCount();
  f = frequency_of_primes(maxnum);
  t = GetTickCount() - t;
  printf ("The number of primes lower than %d is: %d\n",maxnum,f);
  printf ("It took me %ld milliseconds.\n",t);
  return 0;
}

Комментарии

comments powered by Disqus