Buderus-trade.ru

Теплотехника Будерус
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Измерение времени выполнения блока кода на C/С

Измерение времени выполнения блока кода на C/С++

Распространенный совет, который дают новичкам: подключить библиотеку time.h и, с помощью функции получения времени clock() , определить время перед выполнением блока кода и после него. Время выполнения блока будет разницей полученных времен. То есть, что-то вроде

Здесь clock_t — арифметический тип для представления времени; clock() возвращает время, фиксируемое процессором от начала выполнения программы, или -1 , если оно не известно. Для выражения этого времени в секундах применяется формула clock()/CLOCKS_PER_SEC .

Однако такой способ плохо подходит для измерения коротких интервалов времени. Рассмотрим следующий код

Он (взят отсюда) составлен по приведенной выше схеме и подсчитывает количество простых чисел на интервале от 0 до maxnum . Сущность вычислений сейчас не важна — они просто занимают некоторое время, которое мы пытаемся подсчитать. Выполнив, получим

Теперь уменьшим maxnum в 10 раз

Количество простых чисел сократилось даже менее, чем в 10 раз. Казалось бы, мы вправе ожидать ненулевого результата, но. Недаром пишут в руководстве по clock():

Видимо, все дело в этом «approximation».

Обращает на себя внимание то, что следующая за выводом программы строка

показывала ненулевое время. То есть системные средства считают все, что нужно, и пора ими воспользоваться.

Сначала приведем решения для Linux, хотя они работают и в Windows при использовании компилятора MinGW. Итак, альтернативами clock() являются gettimeofday() и clock_gettime() .

позволяет получить время в виде структуры timeval (вторая структура — timezone считается устаревшей и при вызове заменяется NULL’ом):

которая содержит число секунд и микросекунд, прошедших с 1-го января 1970 г. 00:00:00 Всемирного времени. Имеется в виду, что с начального момента прошло tv_sec секунд и еще tv_usec микросекунд.

Микросекунды представляются мне слишком кратким интервалом. Напишем функцию, возвращающую число миллисекунд с начального момента времени

Тестовую программу переделаем следующим образом:

В результате получим

Calculating. The number of primes lower than 100000 is: 9592 It took me 144 milliseconds.

Calculating. The number of primes lower than 10000 is: 1229 It took me 7 milliseconds.

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

Читайте так же:
Счетчик банкнот рекомендованные цб

Функция clock_gettime() из time.h обеспечивает доступ к нескольким видам системных таймеров и имеет наносекундное разрешение. Прототип функции имеет вид:

clk_id позволяет выбрать вид таймера, например (приведу фрагмент из руководства, там есть и другие таймеры):

  • CLOCK_REALTIME , a system-wide realtime clock.
  • CLOCK_PROCESS_CPUTIME_ID , high-resolution timer provided by the CPU for each process.
  • CLOCK_THREAD_CPUTIME_ID , high-resolution timer provided by the CPU for each of the threads.

Время сохраняется в структуре timespec

по тому же принципу, что и в timeval : с начального момента прошло tv_sec секунд и еще tv_nsec наносекунд.

Запишем функцию, возвращающую время в миллисекундах, основываясь на clock_gettime()

Теперь — Windows-решение, работающее в Visual Studio. Это функция GetTickCount() , возвращающая время в миллисекундах с момента старта операционной системы и в течение 49.7 дней:

DWORD WINAPI GetTickCount(void);

Поскольку GetTickCount() возвращает DWORD , счетчик времени сбрасывается в ноль через 49.7 дней. Эта проблема решается использованием GetTickCount64()

ULONGLONG WINAPI GetTickCount64(void);

переполнение в которой вряд ли возможно.

Тестовая программа с использованием GetTickCount() :

Читайте также

Комментарии

Дмитрий Храмов
Компьютерное моделирование и все, что с ним связано: сбор данных, их анализ, разработка математических моделей, софт для моделирования, визуализации и оформления публикаций. Ну и за жизнь немного.

Сортировка подсчётом

Сортировка подсчётом [1] (англ.  counting sort [2] ; сортировка посредством подсчёта [3] англ.  sorting by counting [4] ) — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000.

Содержание

Простой алгоритм [ править | править код ]

Это простейший вариант алгоритма. Создать вспомогательный массив C[0..k — 1] , состоящий из нулей, затем последовательно прочитать элементы входного массива A , для каждого A[i] увеличить C[A[i]] на единицу. Теперь достаточно пройти по массиву C , для каждого j ∈ < 0 , . . . , k − 1 >> в массив A последовательно записать число j C[j] раз.

Это же решение на C и C++.

Алгоритм со списком [ править | править код ]

Этот вариант (англ.  pigeonhole sorting, count sort ) используется, когда на вход подается массив структур данных, который следует отсортировать по ключам ( key ). Нужно создать вспомогательный массив C[0..k — 1] , каждый C[i] в дальнейшем будет содержать список элементов из входного массива. Затем последовательно прочитать элементы входного массива A , каждый A[i] добавить в список C[A[i].key] . В заключении пройти по массиву C , для каждого j ∈ < 0 , . . . , k − 1 >> в массив A последовательно записывать элементы списка C[j] . Алгоритм устойчив.

Читайте так же:
Счетчик зарегистрированных пользователей для сайта

Устойчивый алгоритм [ править | править код ]

Обобщение на произвольный целочисленный диапазон [ править | править код ]

Возникает несколько вопросов. Что делать, если диапазон значений (min и max) заранее не известен? Что делать, если минимальное значение больше нуля или в сортируемых данных присутствуют отрицательные числа? Первый вопрос можно решить линейным поиском min и max, что не повлияет на асимптотику алгоритма. Второй вопрос несколько сложнее. Если min больше нуля, то следует при работе с массивом C из A[i] вычитать min, а при обратной записи прибавлять. При наличии отрицательных чисел нужно при работе с массивом C к A[i] прибавлять |min| , а при обратной записи вычитать.

Анализ [ править | править код ]

Квадратичный алгоритм сортировки подсчётом [ править | править код ]

Также сортировкой подсчётом называют немного другой алгоритм. В нём используются входной массив A и вспомогательный массив B для отсортированного множества. В алгоритме следует для каждого элемента входного массива A[i] подсчитать количество элементов меньших него c 1 > и количество элементов, равных ему, но стоящих ранее c 2 > ( c = c 1 + c 2 +c_<2>> ). B[c] присвоить A[i] . Алгоритм устойчив.

Вечный вопрос измерения времени

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

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

Задача состоит в измерении времени работы участка пользовательского кода. Раньше для этой задачи я использовал класс следующего вида:

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

Читайте так же:
Коммерческое предложение поверка счетчиков

Измерять время работы можно используя такие инструментальные средства, как Intel Parallel Amplifier, но часто удобно измерять время изнутри программы. Например, это позволяет записать значения в лог. Поэтому мы все-таки попробуем создать класс для замера скорости.

Рассмотрим пример кода, вычисляющий некоторое число. Используем для измерения времени работы класс Timing.

В таком виде механизм измерения времени ведет себя как ожидалось и на моей рабочей машине выдает, скажем, 7 секунд. Результат корректен даже для многоядерной машины, так как неважно какие ядра будут использованы в процессе работы алгоритма (см. рисунок 1).
Работа одного потока на многоядерной машине
Рисунок 1 — Работа одного потока на многоядерной машине.

Теперь представим, что мы хотим использовать в нашей программе возможности многоядерных процессоров и хотим оценить, что нам дает распараллеливание алгоритма на основе технологии OpenMP. Распараллелим наш код, добавив одну строчку:

Теперь программа печатает на экран время работы 1.6 секунд. Поскольку используется машина с 4 ядрами, хочется сказать «Ура, мы получили ускорение в 4 раза и замер времени работы это подтверждает».

Огорчу. Мы измеряем не время работы алгоритма, а время работы главного потока. В данном случае измерение кажется достоверным, поскольку основной поток работал столько же, сколько и дополнительные. Поставим простой эксперимент. Явно укажем использовать 10 потоков, а не 4:

Логика подсказывает, что данный код должен работать приблизительно тоже время, что и код, распараллеливаемый на 4 потока. У нас четырех ядерный процессор, а следовательно от увеличения количества потоков можно ожидать только замедление. Однако на экране мы увидим значение порядка 0.7 секунд.

Это ожидаемый результат, хотя мы хотели получить совсем иное. Было создано 10 потоков. Каждый из которых отработал порядка 0.7 секунд. Именно это время работал и основной поток, время которого мы замеряем, используя класс Timing. Как видите, такой способ неприменим для измерения скорости программ с параллельными участками кода. Для наглядности отобразим это на рисунке 2.
Так может выглядеть работа 10 потоков, на машине с четырьмя ядрами
Рисунок 2 — Так может выглядеть работа 10 потоков, на машине с четырьмя ядрами.

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

Читайте так же:
Договор найма жилого помещения оплата по счетчику

Любимой функцией многих разработчиков для измерения скорости является QueryPerformanceCounter. Давайте построим измерение скорости с ее использованием. В простом виде класс для измерения будет выглядеть следующим образом:

К сожалению, на многоядерной машине, так делать больше нельзя. 🙂 Вот что сказано по поводу этой функции в MSDN:

On a multiprocessor computer, it should not matter which processor is called. However, you can get different results on different processors due to bugs in the basic input/output system (BIOS) or the hardware abstraction layer (HAL). To specify processor affinity for a thread, use the SetThreadAffinityMask function.

Произведем усовершенствования и привяжем главный поток к одному ядру:

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

Измерим, что покажут классы Timing и Timing2 на различном количестве потоков:

Сведем данные в таблицу, показанную на третьем рисунке.
Время работы алгоритма в секундах
Рисунок 3 — Время работы алгоритма в секундах измеренное с помощью функций GetThreadTimes и QueryPerformanceCounter на четырехядерной машине.

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

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

Документация

timeit функционируйте и функции секундомера, tic и toc , включите вы, чтобы измерить, сколько времени ваш код исполняетесь. Используйте timeit функция для строгого измерения функционального времени выполнения. Используйте tic и toc оценить время для меньших фрагментов кода, которые не являются полными функциями.

Для дополнительных деталей об эффективности вашего кода, таких как информация о вызове функции и время выполнения отдельных строк кода, используют MATLAB ® Профилировщик. Для получения дополнительной информации смотрите Профиль Ваш Код, чтобы Улучшать Производительность.

Функции времени

Чтобы измерить время, требуемое запускать функцию, используйте timeit функция. timeit вызовы функции заданная функция многократно, и возвращают медиану измерений. Это берет указатель на функцию, которая будет измерена, и возвращает типичное время выполнения в секундах. Предположим, что вы задали функцию, computeFunction , это берет два входных параметров, x и y , это задано в вашей рабочей области. Можно вычислить время, чтобы выполнить функцию с помощью timeit .

Читайте так же:
Яндекс метрика код счетчика установлен не всех страницах

Фрагменты времени кода

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

Иногда программы, запущенные слишком быстро для tic и toc обеспечить полезные данные. Если ваш код быстрее, чем 1/10 секунда, полагайте, что измерение его запускающийся в цикле, и затем среднем значении находит время для одного запуска.

Функция cputime по сравнению с tic/toc и timeit

Рекомендуется, чтобы вы использовали timeit или tic и toc измерять уровень вашего кода. Эти функции возвращают тактовое стеной время. В отличие от этого, tic и toc , timeit вызовы функции ваш код многократно, и, поэтому, рассматривают новые затраты.

cputime функционируйте измеряет общее процессорное время и суммы через все потоки. Это измерение отличается с тактового стеной времени когда timeit или tic / toc возвратитесь, и мог вводить в заблуждение. Например:

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

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

Советы для того, чтобы измерить уровень

Рассмотрите следующие советы, когда вы измерите уровень своего кода:

Время достаточно значительный фрагмент кода. Идеально, код, который вы синхронизируете, должен взять больше, чем 1/10 секунда, чтобы запуститься.

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

Если вы не пытаетесь измерить в первый раз стоимость, запустить ваш код многократно. Используйте timeit функция.

Избегайте clear all при измерении уровня. Для получения дополнительной информации смотрите clear функция.

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

голоса
Рейтинг статьи
Ссылка на основную публикацию
Adblock
detector