Модули Measure
Модуль Measure
Модуль Measure 2
Модуль Measure 3
Модули Measure 0
Скачать
Предыстория
В конце первого курса одним из заданий по дисциплине "Структуры данных и алгоритмы" было практическое исследование алгоритмов поиска. В частности, в большинстве вариантов необходимо было измерять время работы алгоритмов при конкретном числе элементов в таблице. В документе, описывающем стандартный ход исследования, условия исследования и форму отчёта, было рекомендовано измерять промежутки времени с помощью модуля Measure Антона Куранова (студента одного из предыдущих курсов прикладной математики). Метод применения этого модуля был очень прост: надо было всего лишь импортировать этот модуль, перед исследуемым местом алгоритма поставить оператор StаrtTimer, после исследуемого места оператор StopTimer, и когда необходимо получить время работы в секундах с помощью функции GetTime. Кроме простоты использования, у Measure было ещё одно преимущество перед вычислением времени вручную с помощью модуля DOS: он давал точность не 55мс (1 тик системного таймера), а 1мс.
Недостатки Measure
Модуль Measure достигал такой точности благодаря перепрограммированию системного таймера и в связи с этим обладал некоторыми не очень хорошими свойствами: в неотлаженной программе, которая могла закончиться ошибкой и "вылететь", Measure не исполнял своего завершающего кода, и уже в DOS системные часы шли в несколько раз быстрее. У одного моего одноклассника благодаря модулю Measure часы компьютера ушли на сутки вперёд.
Measure 2
Увидев содержимое модуля Measure, я подумал, что можно измерять время с не худшей точностью совсем не перепрограммируя системный таймер. И в апреле 1999 я написал модуль Measure2, который на 486 компьютере давал точность 50 мкс и был совместим с Measure по набору процедур. Идея Measure 2 очень проста: при инициализации модуля считаем количество пустых циклов до смены тика, при вызове StartTimer исполнение задерживается до начала нового тика, а при вызове StopTimer считается число пустых циклов до смены тика. Тогда время, выдаваемое GetTime вычисляется как время одного тика, умноженное на количество полных тиков плюс один и минус отношение числа циклов в StopTimer к числу циклов в инициализации.
Недостатки Measure 2
Однако осенью 1999 выяснилось, что на широко распространившихся в то время процессорах Pentium II алгоритм Measure 2 не давал приличной точности, погрешность приближалась ко времени тика системного таймера (55мс), так что все решения, заложенные в него, обесценивались. Вызвано это было, скорее всего, такими особенностями архитектуры Pentium 2, как конвейер и исполнение по предположению. Видимо, от того, насколько правдоподобным посчитает Pentium 2 переход в начало пустого цикла в очередной раз, зависит то, сколько времени будет исполняться этот цикл.
Measure 3
Осенью 1999 мой учитель программирования дал мне ксерокопию статьи из журнала "Монитор" (№6, 1995), содержание которой, по его мнению, соответствовало интересовавшей меня теме точного измерения времени выполнения частей программ. Там содержались некоторые сведения об интерфейсе микросхемы системного таймера. Оказалось, что из неё можно получить не только число полных тиков по 55мс, но и число "миллитиков" - в 65536 раз меньших тактов. Таким образом, с помощью этой микросхемы можно было мерить время с точностью 1 мкс. И на основе этой информации я сделал модуль Measure 3, конечно же совместимый с Measure 2 и Measure по набору процедур.
Недостатки Measure 3
Ещё в ходе разработки Measure 3 оказалось, что сведения, изложенные в статье, не совпадают с тем, что наблюдается в реальном компьютере. Оказалось, что тот порт, который должен был выдавать число "миллитиков", выдавал в 2 раза большие значения, а так как они не помещались в слово, то их по модулю 65536. Попытки найти специальную литературу, в которой был бы описан интерфейс этой микросхемы, успехом не увенчались. Пришлось предположить, что такое поведение одного реального компьютера характерно для всех остальных. В этом предположении и был написан Measure 3. На практике и все остальные компьютеры под DOS работали так же. Однако проблемы не заставили себя ждать. Сначала выяснилось, что под Windows NT порт, выдющий "миллитики" вообще никак не связан с границами тика, и, следовательно, Measure 3 в NT работать принципиально не может, потом выяснилось, что и под DOS с сетью NetWare иногда таймер изменяет своё поведение. Таким образом оказалось, что Measure 3 может быть использован только в исследовании, когда программы сразу пишутся, и тут же запускаются - если Measure 3 вообще работать будет, то будет работать точно. Но для использования в программах для распространения Measure 3 оказался неприменим - на каком-нибудь компьютере такая программа может вообще не заработать.
Итог
Итак, оказалось, что у каждого ухищрения в измерении времени есть своя обратная сторона. У Measure - возможность некорректного завершения, у Measure 2 - потеря точности на некоторых типах архитектур, у Measure 3 - отсутствие переносимости. Причём ни один модуль так и не дошёл до возможности измерить время одного поиска. Единственным преимуществом этих модулей следует признать удобный интерфейс из трёх процедур. Поэтому отныне я использую и буду писать только модули Measure0, которые используют функции операционной системы для определения текущего времени. Пусть они имеют маленькую точность, но эта точность не будет зависеть ни от архитектуры процессора, ни даже от архитектуры машины (в случае языков высокого уровня, например, Java).
Здесь Вы можете скачать доступные модули (распространяются свободно, безо всяких гарантий работоспособности и безо всякой ответственности со стороны автора за результаты работы):
- Measure0.java (695b) - класс Java. Погрешность определяется архитектурой машины, для IBM PC совместимых составляет 55мс. Ограничений на применимость не обнаружено.
- Measure0.asm (ещё не готов) - модуль Ассемблера 8086 для MS-DOS. Погрешность 55мс. Ограничений на применимость не обнаружено.
- Measure0.pas (ещё не готов) - модуль Турбо Паскаля (компилятор Турбо Паскаля существует, как известно, только для MS-DOS). Погрешность 55мс. Ограничений на применимость не обнаружено.
- Measure2.pas (5 745b) - модуль Турбо Паскаля. Минимальная достигнутая погрешность (на 486 и Pentium) - 50мкс. Погрешность очень большая на Pentium II (следует также полагать, что ситуация с этим не улучшилось на Pentium III и Pentium IV).
- Measure3.pas (8 000b) - модуль Турбо Паскаля. Если модуль будет работать, то погрешность составит 2мкс. Однако может и отказаться работать (почти наверняка откажется под Windows NT).
|