Измерение временных интервалов в программах на языке Си

Для замера времени в программах на языке Си существуют несколько специальных библиотечных функций, таких как gettimeofday(), times(), clock(), : Некоторые из них являются специфичными для конкретных операционных систем, а некоторые относительно переносимы.

С измерением времени работы программы в многозадачной операционной системе, какими является Linux и Windows, связаны определенные трудности. Они обусловлены тем, что процессор всегда выполняет несколько процессов (программ) <одновременно>. Таким образом, если мы просто замерим время работы нашей программы, то в этот интервал попадут и какие-то другие процессы. Схематично это можно представить следующим образом:

Пусть на однопроцессорном компьютере активно выполняются 5 процессов (программ). Процессор в некотором порядке выполняет все эти программы - по одной в каждый интервал времени. Наша программа (процесс 2) запомнила значение времени до замеряемого участка кода, а потом после него, и вычислила временной интервал. На рисунке видно, что в этот интервал также попали и другие процессы, время исполнения которых нам совершенно не нужно измерять. Необходимо различать следующие времена, которые можно получить с помощью различных функций:

• Системное время - время, одинаковое для всех программ, работающих на данном компьютере. Функции gettimeofday(), например, возвращает значение относительно системного времени, поэтому оно содержит <лишнее> время работы посторонних процессов. Минимизировать это <лишнее> время можно, если во время замера убрать все другие программы, <съедающие> процессорное время.
• Время процесса - время, которое было потрачено на выполнение конкретного процесса (программы). По сути, именно его желательно получить. Для определения времени процесса в многозадачных операционных системах существуют различные библиотечные функции, специфичные для данной конкретной операционной системы.

Рассмотрим несколько способов измерения интервалов времени.

1. Использование функции gettimeofday()

Функция gettimeofday() позволяет получить текущее значение системного времени. Достоинством этого способа измерения является относительно большая точность измерения.

Пример реализации в ОС Linux:

#include <sys/time.h>

struct timeval tv1,tv2,dtv;

struct timezone tz;

void time_start() { gettimeofday(&tv1, &tz); }

long time_stop()

{ gettimeofday(&tv2, &tz);

dtv.tv_sec= tv2.tv_sec -tv1.tv_sec;

dtv.tv_usec=tv2.tv_usec-tv1.tv_usec;

if(dtv.tv_usec<0) { dtv.tv_sec--; dtv.tv_usec+=1000000; }

return dtv.tv_sec*1000+dtv.tv_usec/1000;

}

Функция time_stop() возвращает время, прошедшее с запуска time_start(), в миллисекундах. Пример использования:

main()

{

. . .

time_start();

/* какие-то действия */

printf("Time: %ld\n", time_stop());

. . .

}

2. Использование функции times()

Функция times() позволяет получить текущее время процесса. Получаемое время зависит от интервала времени прерываний по таймеру, которые использует планировщик задач, например в IA-32/Linux - 10ms, Alpha/Linux - 1ms. Следовательно, недостатком этой функции является низкая точность на малых интервалах времени.

Пример реализации в ОС Linux:

#include <sys/times.h>

#include <time.h>

struct tms tmsBegin,tmsEnd;

void time_start() { times(&tmsBegin); }

long time_stop()

{ times(&tmsEnd);

return ((tmsEnd.tms_utime-tmsBegin.tms_utime)+

(tmsEnd.tms_stime-tmsBegin.tms_stime))*1000/CLK_TCK;

}

Функция time_stop() возвращает время, прошедшее с запуска time_start, в миллисекундах. Пример использования совпадает с приведенным выше.

3. Использование счетчика тактов процессора.

Практически каждый процессор имеет специальный встроенный регистр - счетчик тактов, значение которого можно получить специальной командой процессора. Команда процессора RDTSC (Read Time Stamp Counter) возвращает в регистрах EDX и EAX 64-разрядное беззнаковое целое, равное число тактов с момента запуска процессора. Вызвав эту команду до и после участка программы, для которого требуется вычислить время исполнения, можно вычислить разность показаний счетчика. Это равно числу тактов, затраченных на исполнение замеряемого участка. Для перехода от числа тактов к времени требуется умножить число тактов на время одного такта (величина, обратная тактовой частоте процессора). Для процессора с тактовой частотой 1ГГц время такта - 1 нс.

Достоинством этого способа является максимально возможная точность измерения времени.

Недостатки: команда получения числа тактов зависит от .архитектуры процессора.

Пример реализации в ОС Linux:

long long TimeValue=0;

unsigned long long time_RDTSC()

{ union ticks

{ unsigned long long tx;

struct dblword { long tl,th; } dw; // little endian

} t;

asm("rdtsc\n": "=a"(t.dw.tl),"=d"(t.dw.th));

return t.tx;

} // for x86 only!

void time_start() { TimeValue=time_RDTSC(); }

long long time_stop() { return time_RDTSC()-TimeValue; }

Функция time_stop возвращает число тактов процессора, прошедших с запуска time_start. Пример использования совпадает с приведенным выше.

4. Уменьшения влияния прочих факторов, искажающих измерения

В идеале следует замерять только саму исследуемую процедуру. Код инициализации (например, выделение памяти, заполнение массивов), деинициализации, файлового и консольного ввода и вывода должен обязательно быть вне замеряемого участка.

Прочие процессы в системе

Все современные ОС - многозадачные. Готовые задачи конкурируют за процессор. Кроме этого, они используют виртуальную и основную память и загружают кэш. Необходимо минимизировать число исполняемых процессов на машине в момент профилирования программы. Других счетных процессов и процессов, выделяющих много памяти, не должно быть в системе. Некоторые системные фоновые процессы устранить нельзя, они вносят искажения в измерения.

Кэш записи

В современных ОС существует механизм отложенной записи на диск. Рекомендуется очистить буфер записи перед запуском исследуемой программы для уменьшения влияния предыстории. В ОС Linux для этого используется команда sync. Ее также можно выполнить прямо в программе на Си:

system("sync");