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

Question

Осенью я прохожу курс по вычислительной геометрии, где мы будем реализовывать некоторые алгоритмы на C или C ++ и сравнивать их. Большинство студентов генерируют несколько наборов данных и измеряют свои программы с помощью команды time, но я бы хотел быть более внимательным.

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

Итак ... Как вы более точно измеряете время выполнения программы?

Что может иметь значение для измерения?

Какие гипотезы могут быть интересны для проверки (дисперсия, эффекты, вызванные кэшированием и т. Д.)?

Должен ли я проверить свой код на более чем одной машине? Чем эти машины должны отличаться?

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

Answer 1

Профилировщики великолепны. Вальгринд довольно популярен. Кроме того, я бы посоветовал опробовать ваш код на RISC-машинах, если вы сможете получить к ним доступ. Их эксплуатационные характеристики отличаются от таковых у машин cisc интересными способами.

Answer 2

Вы не указали свою платформу.Если вы работаете в системе POSIX (например, Linux), посмотрите clock_gettime.Это позволяет получить доступ к различным типам часов , например, время настенных часов или время процессора.Вы также можете узнать о точности часов.

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

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

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

Answer 3

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

Для получения дополнительной информации о метриках выполните поиск ввеб для метрик и профилирования .

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

Вы можете протестировать свою программу на разных машинах.Тактовые частоты процессора, размеры кеша L1 и L2, размеры оперативной памяти и скорости диска - все это факторы (а также количество других программ / задач, запущенных одновременно).Плавающая точка также может быть фактором.

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

Поскольку ваши данные обработки, обратите внимание на управляемый данными дизайн : http://www.gamearchitect.net/Articles/DataDrivenDesign.html

Answer 4

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

Что вам нужно сделать, это просто получитьпрофессиональный профилировщикВот для чего они.Однако, более реалистично.

Если вы сравниваете только алгоритмы, если ваша машина не работает в одной области (Pentium D, SSD), это не должно иметь большого значениясделать это только на одной машине.Если вы хотите посмотреть на эффекты кеша, попробуйте запустить алгоритм сразу после запуска машины (убедитесь, что у вас есть копия Windows 7, она должна быть бесплатной для студентов CS), а затем оставьте ее, делая что-то, что может потребовать много кешаКак обработка изображений, за 24 часа или что-то, чтобы убедить ОС кешировать ее.Затем запустите алгоритм снова.Сравните.

Answer 5

Вы можете использовать функцию синхронизации Windows API (не совсем так), и вы можете использовать команду встроенного ассемблера RDTSC с точностью до наносекунды (не забывайте, что команда и инструкции вокруг нее создают небольшие накладные расходы несколько сотен циклов, но это не большая проблема).