benchmarking

[stas]

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

Comments

[ex-ex-zhuzh.livejournal.com]

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

[stas]

Вот тут мне не понятно - почему? Т.е. если бы я точно знал, что получаемый мной минимум - действительно минимально возможное время, то разве не разумно было бы сравнивать именно чистое время функции в обоих случаях? Ведь мне неинтересно, сколько будет бежать функция - мне интересно, насколько я ее улучшил. Разве не лучше в этом случае мерять по минимуму?
Конечно, точно знать я не могу, но если я сделаю достаточно много тестов, то разумное приближение к минимуму у меня будет - поскольку никакая случайная ошибка не может _уменьшить_ время функции.

[ex-ex-zhuzh.livejournal.com]

для того, чтобы улучшать что-нибудь, надо бы сначала понять, что именно мы улучшаем. по мне, так среднее время пробега (потому что минимальное, как и было сказано, недостижимо).

[toyvo.livejournal.com]

Я думаю, что проще всего сделать Т-тест (а можно наверно и Z) и сказать что с такой-то долей уверенности (по таблицам T-распределения) функция 2 лучше чем функция 1. Мне кажется, что численное выражение тут будет шаманством - слишком это зависит от работы ОС в это время. Ещё, возможно, я бы сравнивал не не обе выборки целиком а по два центральных квадраната выкинув марджины. Это сильно снизит шум.

[stas]

Что лучше, я и так знаю - разница между точками достаточно большая. Мне надо знать, стало лучше, скажем, на 5% или на 10% или на 20%.

[toyvo.livejournal.com]

Когда меряешь экспериментально и хочешь численного выражения, надо кучу всего делать для минимазации шума. Напрашивается:
1) Абсолютно пустой компъютер, облегченная до минимума операционная система
2) Рестарт после каждого сэмпла
3) Отрубить сеть
4) Отрубить все завязанные на scheduller таски.

И всё равно - фигово обычно получается:( В гугл-сколаре масса статей о том, как ставить подобные эксперименты, очень нетривиальная задача, ИМХО, если нужен корректный результат.

[stas]

Я так примерно и делаю, но отрубить сеть не могу - к тестовому компутеру доступ только по сети :)

[toyvo.livejournal.com]

:)
Ещё советуют после каждого рестарта выжидать минут по 10-15 чтоб все обязательные сервисы успели подняться. А ещё, в случае сетевого исполнение, надо следить чтоб траффик не прыгал сильно. У нас в лабе рассказывают байку как один длинный ночной эксперимент начал выдавать поразительно интересные результаты:
В воскресенье все работало офигенно, потом, замедлялось до пятницы, а субботу просто нафиг висло. И повторялось с воскресенья. Выяснилось - ночной сетевой бэкап:)

> выжидать минут по 10-15 чтоб все обязательные сервисы у

[poige.livejournal.com]

:) это актуальная рекомендация для платформы ZX-80?

Re: > выжидать минут по 10-15 чтоб все обязательные сервисы

[toyvo.livejournal.com]

Вероятнее всего - нет:) Но, подозреваю с ZX-80 вообще меньше проблем в плане шума:)))

[yury]

init 2
остаётся необходимый сетевой доступ, отрубается NFS и прочие потенциально неприятные вещи.

[toyvo.livejournal.com]

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

[stas]

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

[toyvo.livejournal.com]

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

[ivar.livejournal.com]

А почму просто профайлером не воспользоваться? он тебе все построчно распишет... или среда не та?

[stas]

А чем мне поможет профайлер? Меня интересует общее время выполнения и насколько оно стало лучше от моих модификаций. У профайлера, скорее всего, точность еще ниже - единичные события точно мерять в реальной программе почти невозможно.

[ivar.livejournal.com]

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

[mopexod.livejournal.com]

Пиши честно - ускорилось на 15-20%. Какой смысл в высокой точности, если налицо широкое распределение?

[stas]

Если б оно для маркетинга было - так бы и сделал :) Но это для себя, хочется знать точнее.

[unbe.livejournal.com]

если процедура без i/o, то можно брать CPU time конкретного процесса, будет точнее.

[yba.livejournal.com]

ИМХО, профайлер по идее точнее меряет

[pierre-denis.livejournal.com]

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

Так и есть. Запускаешь раз 10 - 20, берешь наименьший результат и всё.

///Теперь дальше - меряем улучшеную функцию, получаем разброс, скажем, от 8.9 до 8.2. Можно ли утверждать, что мы ускорили функцию с 10.1 до 8.2 - т.е. практически на 20% ///

Да, можно. Также прогоняешь тесть раз 10 - 20, берешь минимальный результат - это есть время работы функции. Всё остальное - мусор.