Как измерять время выполнения алгоритма?, на целевой платформе и PC Опции

[beaRTS]

Алгоритм может отлаживаться как на компе, так и на целевой платформе.
Вопрос: как в обоих случаях вы измеряете время выполнения ? подсчитываете количество тактов, затрачиваемых функцией/алгоритмом ? и однозначные ли результаты получаете?

Покапавшись в интернете:
Из­ме­ре­ние ин­тер­ва­лов вре­ме­ни в Windows
Максимально точное измерение кода Хабр
Оптимизация длинной арифметики на C++
Как можно подсчитать время работы алгоритма (части программы) __ простенько
C/C++. Измерение времени работы кода с точностью до такта.
измеряем время выполнения понял что для Большого Брата сложно измерить однозначно и точно количество тактов (время) выполнения. Так как каждый раз при новом запуске будем получать разное время выполнения из-за многозадачности Оси и многоядерности процессоров.

У меня разница получалась примерно в 2-3 раза. максимум около 1000 тиков, минимум около 400 ( ниже программа для оценки извлечения корня ) Причем я не уверен, что 400 - это минимум времени исполнения алгоритма .
Приведу простенькую прогу. Запускал в Визуал Студии.

Код

#include <iostream>
#include <ctime>
#include <intrin.h> // для  __rdtsc()

#pragma intrinsic(__rdtsc)

int isqrt (unsigned x);

int main() {

    double time;
    int result;
    //константа для задания верхнего предела для цикла for
    const int max = 1000000;
    const clock_t start = clock();

    for(int i = 0; i < max; ++i)
        result = isqrt( 10);
    
    time = static_cast< double >( clock() - start ) / CLOCKS_PER_SEC;

    std::cout<< "sqrt result:  " << result  << "  avarage time is " << time << std::endl;
    std::cout << "CLOCKS_PER_SEC: " << CLOCKS_PER_SEC << std::endl;
    std::cout << " time for one isqrt(): " << time / max <<std::endl;
    
    unsigned __int64 startTick, stopTick, ticks;

    startTick = __rdtsc();
    result = isqrt( 10);
    stopTick = __rdtsc();

    ticks = stopTick - startTick;
    std::cout << " time in Ticks for one isqrt(): " << ticks << std::endl;

    std::cin.get();
    return 0;
}

int isqrt (unsigned x)
{
unsigned m, y, b;
m = 0x40000000;
y = 0;
while (m != 0) { //16 раз
b = y | m;
y = y >> 1;
if (x >= b) {
x = x - b;
y = y | m;
}
m = m >> 2;
}
return y;
}

[eugen_pcad_ru]

Сам не меряю. ИМХО в такой постановке задачи можно вести речь только о средней скорости выполнения. Средняя скорость и есть однозначный результат.
P.S.: Думаю, что если в железе работают асинхронные протоколы, тоже можно измерять только среднюю скорость.

[beaRTS]

Сам не меряю. ИМХО в такой постановке задачи можно вести речь только о средней скорости выполнения.

да просто книги ли читаешь, форум ли этот штудируешь - везде приводятся цифры времени выполнения алгоритма. вот и стало интересно. Да и спортивный интерес сравнить свою реализацию чего-нибудь с библиотечной функцией-аналогом..

или там обычно считают по ассемблерным командам, полученным из Си/С++ кода? т.е. смотрят транслированный файл, видят ассемблерные команды, знают по документации, что он на данном контроллере выполняется за 1/2 такта и подобным образом вычисляют время выполнения алгоритма?? (ну я так делал в универе, еще когда нас на асме учили писать под PIC)

Сообщение отредактировал beaRTS - Dec 18 2012, 08:43

[Serg76]

Для софтового решения вообще не вижу проблем, есть куча способов, например, с помощью все тех же Win API. Но как правильно сказали, это все в среднем по ряду причин, но для оценки сойдет.

[beaRTS]

Для софтового решения вообще не вижу проблем, есть куча способов, например, с помощью все тех же Win API.

А я не вижу проблем в железячном решении=)...

Да во всех этих способах вскрылось много подводных камней. Но без них, видимо, никуда. Поэтому да - только оценивать. Просто казалось, что можно с точностью до такта все замерить и спать спокойно.

[Serg76]

Просто казалось, что можно с точностью до такта все замерить и спать спокойно.

При особом желании можно и до такта, только зачем это при ресурсоемкой задаче? Кроме того, некоторые компиляторы могут оценивать временнЫе затраты самостоятельно.

[beaRTS]

Кроме того, некоторые компиляторы могут оценивать временнЫе затраты самостоятельно.

а это уже интересно. Не знал!!!

[neiver]

Для ПК есть такие инструменты - профайлеры называются. В той-же VisualStudio есть встроенный. Из меню "Analyze" вызывается. Есть еще куча других. Так вот они подробный отчёт предоставляют, какая функция сколько раз вызвана, и сколько времени выполнялась.
В МК можно сделать тест производительности и просто померить время выполнения какой-то функции таймером. А можно пойти дальше и воспользоваться возможностями профилировки кода, предостовляемыми компилятором.
Вот тут немного об этом написано
Смысл в том, что в начало и в конец каждой функции компилятор вставляет вызов функций __cyg_profile_func_enter и __cyg_profile_func_exit соответственно. В них передается арес текущей функции и адрес вызывающей. Есть таймер, который служит источником временнЫх меток. Адреса вызванной, вызывающей функций и временную метку от таймера можно передать на ПК, например, через USART, где потом анализировать.
Конечно такое профилирование искажает время работы программы в целом, но общую картину показывает.

[beaRTS]

Для ПК есть такие инструменты - профайлеры называются. ...

оооОО спасибо огромное за подробный ответ!

[SyncLair]

Основной способ -- использовать аппаратный счётчик и записывать его значения ДО и ПОСЛЕ выполнения функции. В 586 ых компах для его считывания появилась ассемблерная инструкция.
Для МК использется какой-нибудь из доступных

[_Pasha]

В МК можно сделать тест производительности и просто померить время выполнения какой-то функции таймером. А можно пойти дальше и воспользоваться возможностями профилировки кода, предостовляемыми компилятором.

Времена будут максимальными, без учета сокращений при ветвлениях, зависящих от данных.Это лучше, чем ничего, но практически ничего.

[beaRTS]

Для ПК есть такие инструменты - профайлеры называются. В той-же VisualStudio есть встроенный. Из меню "Analyze" вызывается.

Как я понял: "As a developer, you can run code analysis on your project automatically and you can run it manually from Visual Studio Premium or Visual Studio Premium " (с) ссылка (то же самое постулируется и здесь , - нет в Microsoft Visual Studio Express Edition возможности анализами заниматься.

Так что решение очевидно .... =) как добыть Premium/Premium и на работе побаловаться с этим анализом кода... Одно точно - надо бы эту технологию поосваивать.

[Guest_TSerg_*]

Общее правило таково - длительность измерения д.б. значительно больше длительности неопределенности времени измерения Ratio > 100...1000.
Для увеличения длительности измерения измерямый блок гоняют в цикле, замеряя общее время N-циклов и деля на N.
Либо время измерения должно уложиться в slice ОС-платформы, но тоже с учетом Ratio.

Также, для повышения достоверности, повышают приоритет процесса до "не могу больше".

procedure SetRealTime_;
var
ProcessID : DWORD;
ProcessHandle : THandle;
ThreadHandle : THandle;
begin
ProcessID := GetCurrentProcessID;
ProcessHandle := OpenProcess(PROCESS_SET_INFORMATION,
false,ProcessID);
SetPriorityClass(ProcessHandle, REALTIME_PRIORITY_CLASS);
ThreadHandle := GetCurrentThread;
SetThreadPriority(ThreadHandle, THREAD_PRIORITY_TIME_CRITICAL);
end;

[beaRTS]

Также, для повышения достоверности, повышают приоритет процесса до "не могу больше".

ага , спасибо Вам за наставление. слышал, что если проц многопроцессорный (у меня, например core i7), то еще в BIOS'е отключают поддержку многопроцессорности для пущей уверенности.

[beaRTS]

А кто знает сие чудо AMD CodeAnalyst для windows бесплатная ли ? т.е. на рабочий комп то ставить можно?

P.s. опять стоило задать вопрос - так ответ сам ко мне пришел.. В общем , можно.

Сообщение отредактировал beaRTS - Dec 19 2012, 08:34

[beaRTS]

Сам не меряю. ИМХО в такой постановке задачи можно вести речь только о средней скорости выполнения. Средняя скорость и есть однозначный результат.

Мне тоже так казалось в соответствии со статистическими знаниями.. но не тут то было! Покапавшись в инете вот что вскрылось:
"В многозадачной системе Windows, никакая программа не владеет всеми ресурсами системы единолично и вынуждена делить их с остальными задачами. А это значит, что скорость выполнения профилируемой программы не постоянна и находится в тесной зависимости от "окружающей среды". На практике разброс результатов измерений может достигать 10%—15%, а то и больше, особенно, если параллельно с профилировкой исполняются интенсивно нагружающие систему задачи.

Тем не менее, особой проблемы в этом нет, — достаточно лишь в каждом сеансе профилировки делать несколько контрольных прогонов и затем… нет, не усреднять, а выбирать замер с наименьшим временем выполнения. Дело в том, что измерения производительности — это не совсем обычные инструментальные измерения и типовые правила метрологии здесь неуместны. Процессор никогда не ошибается и каждый полученный результат точен. Другое дело, что он в той или иной степени искажен побочными эффектами, но! Никакие побочные эффекты никогда не приводят к тому, что программа начинает исполняться быстрее, нежели она исполняется в действительности, а потому, прогон с минимальным временем исполнения и представляет собой измерение в минимальной степени испорченное побочными эффектами.

Кстати, во многих руководствах утверждается, что перед профилировкой целесообразно выходить из сети ("что бы машина не принимала пакеты"), завершать все-все приложения, кроме самого профилировщика и вообще лучше даже "на всякий случай" перегрузиться. Все это чистейшей воды бред! Автор частенько отлаживал программы параллельно с работой в Word, приемом корреспонденции, загрузкой нескольких файлов из Интернета и при этом точность профилировки всегда оставалась удовлетворительной! Конечно, без особой нужды не стоит так рисковать, и параллельно работающие приложения перед началом профилировки, действительно, лучше завершить, но не следует доводить ситуацию до абсурда, и пытаться обеспечить полную "стерильность" своей машине. "

Сообщение отредактировал beaRTS - Dec 20 2012, 07:13

[Guest_TSerg_*]

> прогон с минимальным временем исполнения и представляет собой измерение в минимальной степени испорченное побочными

Это не всегда так, более того - на современных компах это далеко не так.
Наиболее точным является первое измерение, т.к. производятся различные подготовки. Последующие измерения при одних и тех же входных условиях могут дать значительно меньший результат, т.к. начинает работать кэш и уточняются предсказания.
Однако если данные меняются при каждом тесте, то все начинается с нуля.

[beaRTS]

Это не всегда так

да да . вы правы. я тут дальше накопал примерно такие рекомендации:
"При профилировании многократно выполняющихся функций, результаты первых двух–трех прогонов стоит вообще откинуть, и категорически не следует их арифметически усреднять.

Напротив, при профилировании функций, исполняющихся в реальной программе всего один раз, следует обращать внимание лишь на время первого прогона и отбрасывать все остальные"

[Guest_TSerg_*]

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

[beaRTS]

Ндаа. =) как это все неоднозначно.
Спасибо! подчерпнул для себя что-то новое. Но пока не готов трудо-дни тратить на углубление в профилировании.

Пока на данном этапе развития буду если что в железе ножкой порта дрыгать да смотреть осциллографом.

Сообщение отредактировал beaRTS - Dec 20 2012, 08:05

[Guest_TSerg_*]

Пример трассировки на РС одной вычислительной функции в ticks
Нормальный приоритет:
N: 100
Tmax: 47267
Tmin: 22509
Tmean: 27899
Tstd: 3913

RealTime приоритет:
N: 100
Tmax: 31293
Tmin: 22754
Tmean: 27241
Tstd: 1700

[beaRTS]

Пример трассировки на РС одной вычислительной функции в ticks
<..>

наверно, так и стоит делать, собирая всю статистику целиком. я Вас понял, применю при случае. спс