benchmarking

[stas]

Допустим, у меня есть процедура, вычисляющая некую функцию f(x). Есть модификация, который позволяет эту процедуру ускорить, и надо проверить, насколько именно. Процедура довольно быстрая - скажем, порядка десятков миллисекунд (все цифры условные для примера). Т.е. чтобы ее мерять достаточно уверенно, надо написать бенчмарк, который ее запускает, скажем, 1000 раз и меряет, сколько времени заняло. Тут начинается интересное - бенчмарк дает разброс между, скажем, 10.8 секунды и 10.1 секунды. Какое значение использовать? Можно посчитать среднее, но с другой стороны - если некоторые бенчмарки выполняются за 10.1 секунды, не значит ли это, что именно настолько быстрая эта функция и есть, а значения выше этого - это мусор, вызванный каким-то другими эффектами в системе?
Имеет ли смысл удлинять тест, тестировать не 1000, а 10000, скажем? С одной стороны, относительный разброс становится меньше, с другой - больше вероятности, что во время теста случится что-нибудь, что повлияет на результаты (к сожалению, в современной ОС без значительных усилий трудно знать, не решит ли какой-нибудь процесс прямо сейчас что-нибудь поделать)?
Теперь дальше - меряем улучшеную функцию, получаем разброс, скажем, от 8.9 до 8.2. Можно ли утверждать, что мы ускорили функцию с 10.1 до 8.2 - т.е. практически на 20% - или же надо опять считать средние и сравнивать их?
Я знаю, что обычно принято считать среднее, но не очень понятно, почему именно в этом случае это будет лучше (для ясности - мне надо знать не насколько быстрая сама функция, а насколько конкретная модификация ее ускоряет).

Comments

[stas]

Ну мне абсолютно точно не надо, но хорошо бы 10% от 20% отличать :)
Однако я все-таки не совсем понимаю, почему нельзя просто сравнить минимумы в достаточно длинной серии - отрицательных ошибок ведь в данном случае быть не может, т.е. случайные события могут только замедлить.

[toyvo.livejournal.com]

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