Сроки и Бенчмаркинг

Question

Если я хочу сравнить скорость двух алгоритмов, как лучше? Я знаком с математическим путем, и я знаю, что я еще не полностью освоил его = / Мне интересно знать, как рассчитать два алгоритма с хорошей точностью в Windows. Какие API лучше всего использовать, надежно ли time () из stdio.h или мне нужно что-то лучше?

Пример тоже подойдет! Спасибо!

Answer 1

К сожалению, это не такая простая задача.

Как уже упоминалось ранее, QueryPerformanceCounter является жизнеспособным выбором.
Другие возможности:
- GetTickCount (не рекомендуется, посколькуего точность хуже 30 мс)
- timeGetTime : по умолчанию он имеет точность 15 мс.Это соответствует времени по умолчанию, выделенному планировщиком задач (15 мс на моем компьютере).Вы можете заставить timeGetTime быть более точным, изменив общесистемную настройку, которая управляет временем, выделенным планировщиком: вызов timeBeginPeriod может сделать это.Однако это следует использовать только как временный взлом системы!Пожалуйста, не используйте его в своем коде выпуска!
- Запрос счетчика меток времени процессора : это требует программирования на ассемблере, и я бы не рекомендовал его.

Что касается QueryPerformanceCounterВы можете найти простую в использовании обертку здесь: http://www.codeproject.com/KB/datetime/perftimer.aspx

Вы можете использовать ее следующим образом:

CPerfTimer t;
t.Start();     
CallExpensiveTask();
std::cout << "Time (ms) " << t.Elapsedms();

Несколько советов, однако:

• Как уже упоминалось, запускайте свою функцию много раз, чтобы получить надежную меру
• Остерегайтесь планировщика задач: на среднем компьютере каждому процессу дается 15 мс перед переключением на другой процесс.Если планировщик задач переключает задачу во время вызова измеряемой функции, вы можете измерить время, которое намного выше (примерно на 15 мс выше)
• Обратите внимание, что sleep (1) приводит к паузе в 15 мс (поскольку планировщик переключится надругой процесс)
• Помните, что QueryPerformanceCounter может (редко) давать неточные результаты: на многоядерных процессорах иногда может наблюдаться отрицательный промежуток времени (!).В этом случае вам следует повторить свою меру (см. http://www.virtualdub.org/blog/pivot/entry.php?id=106)
• Временные решения для противодействия эффекту планировщика: - Повысить приоритет процесса (вы можете сделать это через диспетчер задач) - Взломать планировщик: timeBeginPeriod (http://msdn.microsoft.com/en-us/library/dd757624(v=VS.85).aspx), предоставляемый Microsoft, может изменять время, выделяемое для каждой задачи, с 15 мс до более низких значений (не забудьте не включать этот код выпуска, поскольку это общесистемный параметр, который может снизить общую производительность ...)

Еще несколько замечаний о счетчике меток времени процессора

• Я сам не проверял его точность, но http://en.wikipedia.org/wiki/Time_Stamp_Counter является хорошим источником информации о нем,и об его ограничениях (особенно на многоядерных процессорах, а также на процессорах с переменными тактовыми частотами)
• AFAIK, рекомендуется использовать этот тип таймера в одном потоке, для которого вы устанавливаете привязку процессора
• Примерреализации (можно найти на http://developer.nvidia.com/object/timer_function_performance.html) может быть:

#pragma warning (disable : 4035)    // disable no return value warning

__forceinline  DWORD GetPentiumCounter()
{
__asm
{
    xor   eax,eax             // VC won't realize that eax is modified w/out this
                              //   instruction to modify the val.
                              //   Problem shows up in release mode builds
    _emit 0x0F                // Pentium high-freq counter to edx;eax
    _emit 0x31                // only care about low 32 bits in eax

    xor   edx,edx             // so VC gets that edx is modified
}
}

#pragma warning (pop)

Answer 2

То, что вы ищете, это QueryPerformanceCounter и QueryPerformanceFrequency.Это функции Windows API для доступа к таймерам высокого разрешения.Они должны дать лучшую точность, чем time или GetSystemTime.

LARGE_INTEGER time1;
QueryPerformanceCounter(&time1);

// Your code

LARGE_INTEGER time2;
QueryPerformanceCounter(&time2);

LARGE_INTEGER ticksPerSecond;
QueryPerformanceFrequency(&ticksPerSecond);
double seconds = (double)(time2.QuadPart - time1.QuadPart) / ticksPerSecond.QuadPart;

И здесь Я нашел реализацию класса CStopWatch, который можно использовать в качестве примера.

Answer 3

QueryPerformanceCounter / QueryPerformanceFrequency. AFAIK, они исправлены сейчас, и фактически измеряют циклы. Просто не забудьте повысить приоритет потока, чтобы он меньше влиял на другие потоки во время измерения.

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

Так что повышайте приоритет и повторяйте тесты несколько раз.