Как сделать хороший бенчмаркинг сложных функций?

Сообщение о среднем и стандартном отклонении дает хорошее описание распределения, когда рассматриваемое распределение является приблизительно нормальным. Однако это редко относится к измерениям вычислительной производительности. Вместо этого измерения производительности, как правило, больше напоминают распределение Пуассона. Это имеет смысл, потому что не так много случайных событий на компьютере заставят программу работать быстрее; по сути, весь шум измерения заключается в том, сколько случайных событий происходит, что приводит к его замедлению. (Нормальное распределение, напротив, не имеет вообще никакого интуитивного смысла; оно требует веры в то, что программа имеет ненулевую вероятность завершения работы в отрицательное время).

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

«По 10 раз каждый» звучит как очень итерации для меня. Обычно я делаю что-то порядка тысячи (или больше, в зависимости от функции/системы) прогонов, если только это не является полностью невыполнимым. Как минимум, вам нужно убедиться, что вы используете синхронизацию достаточно долго, чтобы избавиться от любой зависимости от состояния системы, некоторые из которых могут меняться с довольно большой степенью детализации времени.

Еще одна вещь, о которой вы должны знать, это то, что практически в каждой системе есть таймер для конкретной платформы, который намного точнее, чем то, что доступно <time.h>. Узнайте, что это такое на вашей целевой платформе[ах], и используйте это вместо этого.

Я предполагаю, что вы смотрите на бенчмаркинг чисто алгоритмических вычислений в своей программе, и нет никакого пользовательского ввода или вывода, который может занять непредсказуемое время. Теперь, что касается чисто числовых программ, ваши результаты могут варьироваться в зависимости от времени фактического выполнения вашей программы, на которое будут влиять другие текущие действия в системе. Может быть другой фактор, который вы можете игнорировать в зависимости от желаемого уровня точности, например, влияние из-за промаха кеша, разного времени доступа через иерархию памяти. можно попробовать просмотреть ассемблерный код и посмотреть сгенерированные инструкции. А затем на основе процессора получить количество циклов для этих инструкций. Этот метод может быть непрактичным в зависимости от объема кода, который вы ищете для эталонного тестирования. Если вы особенно о влиянии иерархии памяти, то вы можете захотеть очень тщательно контролировать среду выполнения, то есть, где загружается программа, куда загружаются ее данные и т. д. Но, как я уже упоминал, в зависимости от желаемой точности, вы можете поглотить вариацию, вызванную иерархией памяти в вашей статистической вариация». Возможно, вам потребуется тщательно спроектировать тестовые входные данные для ваших функций, чтобы обеспечить охват пути, и вы можете опубликовать статистику производительности как функцию тестовых входных данных. Это покажет, как функция ведет себя в диапазоне входных данных.