Измерить время выполнения алгоритма?

Question

[Igor Petrov]

Всем привет!

Подскажите, плиз, как замерить время выполнения алгоритма на Си под Linux?

На текущий момент, использую библиотеку time.h

clock_t startClock, endClock;<br/>
startClock = clock();<br/>
//Код<br/>
endClock = clock();<br/>
diff = difftime(endClock, startClock);<br/>

Но если операций слишком мало, всегда на выходе получаю 0.

Хотелось бы что-нибудь поточнее, как например, в Java System.nanoTime().

Answer 1

[leventov]

Просто поточнее —

typedef unsigned long long ull;

inline ull rdtsc() {
	unsigned int lo, hi;
	asm volatile ( "rdtsc\n" : "=a" (lo), "=d" (hi) );
	return ((ull)hi << 32) | lo;
}

Вместо clock.
Могу написать статью, как мерить небольшие куски си-кода без всякой погрешности.

Comments

[Igor Petrov]

Лично я бы с удовольствием посмотрел.

[Gluttton]

Т.е. сценарий замера такой:
1. Снимаем показание счетчика.
2. Выполняем алгоритм.
3. Снимаем показание счетчика.
4. Из второго значения счетчика вычитаем первое значение — время выполнения алгоритма измеренное в процессорных тактах.
Правильно?

Если да, тогда вопрос, а как мы можем узнать «не отвлекался» ли процессор на выполнение задач отличных от выполнения измеряемого алгоритма?

И вообще:
> Могу написать статью, как мерить небольшие куски си-кода без всякой погрешности.
Было бы здорово!

[1x1]

> Если да, тогда вопрос, а как мы можем узнать «не отвлекался» ли процессор на выполнение задач отличных от выполнения измеряемого алгоритма?
Не узнаем. Для этого и нужно выполнять множество замеров.
Кроме того, rdtsc также нужно применять осмотрительно: кэш, многоядерность и out-of-order execution могут исказить результат.

[Vadikus]

Тоже бы с удовольствием почитал бы Вашу статью.
И ещё, для изучения «сферических коней, вприсанных в кубический метр в вакуме», можно поднять приоритер задаче nice'ом.

Answer 2

[BrainHacker]

Если вы хотите просто знать, сколько времени выполняется алгоритм, то существует стандартная схема:
1. Запустить таймер.
2. Выполнить алгоритм N раз.
3. Остановить таймер и замерить время.

Тогда время выполнения алгоритма один раз будет равно <замеренное_время> / N. Чем больше N, тем точнее значение.

Comments

[Igor Petrov]

Спасибо. Есть такой метод, но его немного неудобно использовать при сортировках, в моем случае.

Answer 3

[huankun]

man gettimeofday
измерение времени с точностью до микросекунд (под Linux)