Перейти к содержанию
    

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

Алгоритм может отлаживаться как на компе, так и на целевой платформе.

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

 

Покапавшись в интернете:

Из­ме­ре­ние ин­тер­ва­лов вре­ме­ни в 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;
}

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

 

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

Изменено пользователем beaRTS

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

Вот тут немного об этом написано

Смысл в том, что в начало и в конец каждой функции компилятор вставляет вызов функций __cyg_profile_func_enter и __cyg_profile_func_exit соответственно. В них передается арес текущей функции и адрес вызывающей. Есть таймер, который служит источником временнЫх меток. Адреса вызванной, вызывающей функций и временную метку от таймера можно передать на ПК, например, через USART, где потом анализировать.

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

Для МК использется какой-нибудь из доступных

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Для ПК есть такие инструменты - профайлеры называются. В той-же 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 и на работе побаловаться с этим анализом кода... Одно точно - надо бы эту технологию поосваивать.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Гость 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;

 

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

 

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

Изменено пользователем beaRTS

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
К сожалению, ваш контент содержит запрещённые слова. Пожалуйста, отредактируйте контент, чтобы удалить выделенные ниже слова.
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...