Комментарии 48
А информация интересная. Особенно тем, кто любит играться с бенчмарками различными
Это еще цветочки в олимпиадном программировании, там в топовых решениях define на define, куча велосипедов, циклы с 10ю уровнями вложенности и т п. Переменные именуются не иначе как a, b, c, a1… и обычно их объявляют в начале файла побольше "про запас". Все эти соревнования имеют минимум общего с промышленной разработкой.
Такой вопрос:
В решении задачи ввод можно читать либо из файла «input.txt», либо из stdin.
Это как-то влияет на скорость выполнения в вашей системе? Были ли с этим проблемы и, если были, то как вы их обошли?
Разница между самым быстрым и самым медленным исполнением — 2230 мс.
В вашем стенде что-то фатально поломано.
Запустил программу 20 раз с помощью вот такого нехитрого запускатора:
#!/bin/bash
for i in {1..20}
do
time ./a.out
done$ ./1.sh real 0m4,662s user 0m4,292s sys 0m0,370s real 0m4,619s user 0m4,229s sys 0m0,390s real 0m4,620s user 0m4,270s sys 0m0,350s real 0m4,631s user 0m4,261s sys 0m0,370s real 0m4,644s user 0m4,315s sys 0m0,330s real 0m4,609s user 0m4,209s sys 0m0,400s real 0m4,652s user 0m4,342s sys 0m0,310s real 0m4,619s user 0m4,279s sys 0m0,340s real 0m4,639s user 0m4,259s sys 0m0,380s real 0m4,665s user 0m4,325s sys 0m0,340s real 0m4,650s user 0m4,270s sys 0m0,380s real 0m4,644s user 0m4,264s sys 0m0,379s real 0m4,625s user 0m4,265s sys 0m0,360s real 0m4,606s user 0m4,227s sys 0m0,380s real 0m4,647s user 0m4,326s sys 0m0,320s real 0m4,638s user 0m4,258s sys 0m0,380s real 0m4,634s user 0m4,265s sys 0m0,370s real 0m4,623s user 0m4,232s sys 0m0,390s real 0m4,630s user 0m4,270s sys 0m0,360s real 0m4,633s user 0m4,263s sys 0m0,370s
Т.е. разброс порядка 1-1.5%. Только я не делал ничего для уменьшения разброса. На компе продолжали работать KDE, Chrome, Slack и куча другого софта.
Бонусом интересно было бы узнать почему компилятор не справляется всю эту программу нафиг выоптимизировать, оставив только
return 0;Даже после всех ухищрений процессоры неизбежно будут троттлить
Попробуйте подключить к процессору нормальное электропитание и достаточное охлаждение. Или хотя бы воткнуть ноутбук, на котором вы делаете замеры, в розетку. С чего вдруг процессор неизбежно должен троттлить?
На компе продолжали работать KDE, Chrome, Slack и куча другого софта.
Я конечно не большой спец по серверным нагрузкам и прочему, но что-то мне кажется, что не будет эта «куча другого софта» насиловать скедулер настолько чтобы это это было сколько-то заметно. Если вы не запускаете тест, какая у вас нагрузка на цпу? У меня тоже вот десяток приложений запущен, нагрузка на CPU ~0.01
В вашем стенде что-то фатально поломано.
Провел повторные замеры простым башем:
real 0m8.280s
user 0m7.828s
sys 0m0.452s
real 0m7.282s
user 0m6.750s
sys 0m0.532s
real 0m7.605s
user 0m7.127s
sys 0m0.456s
real 0m7.338s
user 0m6.877s
sys 0m0.460s
real 0m9.004s
user 0m8.435s <- вот тут я запустил среду разработки
sys 0m0.568s
real 0m10.179s
user 0m9.571s
sys 0m0.592s
Можно во время теста попользоваться каким-нибудь жадным до CPU приложением или нагрузить ядра одним из способов из статьи.
Попробуйте подключить к процессору нормальное электропитание и достаточное охлаждение. Или хотя бы воткнуть ноутбук, на котором вы делаете замеры, в розетку. С чего вдруг процессор неизбежно должен троттлить?
Когда речь идет про тестовый стенд, то можно быть уверенным и в охлаждении, и в питании. Но вот контроллер стойки в ДЦ может в определенный момент решить, что пришло время ронять частоту и приложение на это уже никак повлиять не сможет.
Так что во время крупного соревнования лучше считать, что троттлинг не только возможен, но и неизбежен, чем потом разбираться с последствиями)
Можно во время теста попользоваться каким-нибудь жадным до CPU приложением или нагрузить ядра одним из способов из статьи.
Зачем? Я думал, цель — получить стабильное время выполнения, а не наоборот.
Зачем? Я думал, цель — получить стабильное время выполнения, а не наоборот.
Цель оптимизаций — добиться стабильного выполнения. А цель тестового стенда — проверка стабильности и поиск способа которым эту стабильность можно сломать)
Время выполнения должно быть стабильным и под нагрузкой и без нее.
В результате ваших оптимизаций время выполнения программы просело, на глазок, более чем на 40%. М.б. проще было не нагружать процессор свыше 2/3?
При условии стабильного времени выполнения без нагрузки (чего, как я уже сказал, вполне можно ожидать от процессора с нормальным питанием и охлаждением [нет, ноутбучный процессор под эти условия не подходит]), все дальнейшие пляски могут оказаться не нужны.
Сейчас кластер серверов, которые занимаются проверкой решений, использует 720 ядер. Вы предлагаете не использовать их больше чем на 2/3? И при этом гарантировать что нагрузка не будет превышать 2/3 на каждом из серверов?
Так а в продакшене у вас тоже кластер на мобильных процах которые неизебжно тротлят?
Ну да. Не вижу чем это хуже выключения на всём кластере турбо-буста, раскатки на весь кластер кастомного ядра со специальными опциями загрузки и прибивания процессов к конкретным ядрам.
Так что решение нужно приколачивать или к ядру или к всему серверу целиком. К ядру все-таки лучше
Бонусом интересно было бы узнать почему компилятор не справляется всю эту программу нафиг выоптимизировать, оставив только `return 0;`
Я таки не поленился и отправил в GCC багрепорт. GCC починили и теперь на нём от тестовой программы действительно ничего не остаётся.
Обычно тесты бинарные: прошло/не прошло по времени, время даётся с запасом на предполагаемую асимптотику.
Сортировка — конечно же не по времени работы программы. Как правило она по сумме времени, потраченного на решение сданных задач, и штраф в 20 минут за каждую неверную попытку.
А запас по времени может быть достаточно маленьким — скажем, если нужно, чтобы решение с асимптотикой О(n) на "медленном" языке проходило, а с O(n*logn) на быстром — уже нет. И в таких ситуациях гарантированная скорость работы тестовых машин пригодится.
Разницу между O(n) и O(n*logn) нельзя ловить, т.к. логарифм для обозримых n по сути, константа. Между n, n^2, n^3 — можно и нужно.
Разницу между O(n) и O(n*logn) ловить можно и иногда нужно. Для этого приходится использовать n=1e6 или n=1e7, и в этом случае логарифм >20, уже вполне ловится.
Если закладываться на тормознутость питона то это может дать возможность пропихнуть решение на си с худшей асимптотикой. Так что по моему скромному давнему опыту все топовые решения били на С++
В итоге, лучше всего брать выборку на 10-50 запусков и использовать минимальное время на выполнение или медиану из 3-5 минимальных времен. Подробный разбор в статье.
Не понимаю прикладной необходимости в этих "приседаниях". С одной стороны ответ очевиден — для того, что бы код выполнялся за равное время. Но зачем?
Если брать спецификации где тайминги важны, то для этого есть либо прерывания, либо хардварные решения.
Если требуется оптимизация производительности, то это не равно стабильности времени выполнения. Оптимизировать нужно код или архитектуру в целом.
Более того, задача выглядит вредной, т.к. убивает принцип эффективной утилизации ресурсов. Т.е. люди придумывали всякие нужные технологии для этого и тут приходишь ты и отрубаешь все это нафик. Потому, что… — что?
Ну допустим нужно дать именно этой задаче максимум ресурсов. Ok. Выделяем под нее сервер и нагружаем его только этой задачей. Ресурсы будут распределяться только между равными задачами.
Если я что-то не вижу, поясните пожалуйста.
Я думаю, что тут важен стенд для проверки идентичный для всех. И методика оценки. Например, тот же запуск 1000 раз и средняя скорость. А для пущей релевантности — минимальное зафиксированное время за 1000 раз.
В противном случае, мы говорим даже не о качестве кода, а о способности претендентом завладеть ресурсами системы. Это странно. Как по мне.
Погодите… в статье речь идет о самом стенде?
Но все же, что-то мне начало казаться, что речь идет не про конкретное решение претендента, а о создании стенда для проведения такого сравнения. Это уже имеет смысл. Но из статьи я явно это не понял.
Статистика как раз и работает в допусках.
Вот именно, Речь как раз о том, что окно допуска слишком большое.
Насколько я знаю, в бенчмарках типа https://benchmarksgame-team.pages.debian.net/benchmarksgame смотрят на лучший результат, именно потому что более худшие могли оказаться подвержены влиянию фазы Луны и прочим неучтённым факторам.
Запуск 1000 раз прямо противоречит цели "выдать результат побыстрее". А она есть)
Но выше я написал, что кажется не верно цель понимал. И речь идет о создании как раз стенда для проверки. Т.е. создании таких, идентичных условий. В этом случае задача видится разумной.
Хотя тут бы я смотрел в сторону ОС реального времени исполнения. Не стараясь изобрести велосипед на ОС заведомо предназначенной для разделения ресурсов.
они в статье не минимизированы, а выровнены. Это разные вещи, не?
Скорость работы процессора может зависеть от его температуры, влажности воздуха, фонового электромагнитного излучения, фаз луны или вибрации стойки. Какой патч может гарантировать учет всех факторов?
Думаю, справедливой и точной методикой было бы запускать программы в эмуляторе, который подсчитывает, сколько каких команд процессора программа выполнила. Каждая инструкция имеет свой вес. Умножить, сложить — у кого меньше итоговая сумма, тот и победил. Веса инструкций заранее должны быть известны участникам.
Идея интересная. Как отдельная олимпиада. Только инструкции х86 к реальным инструкциям железа имеют мало общего. Т.е надо эмулировать реальный проц, который запатентован :)
Как заставить код выполняться за одинаковое время? Способы от Яндекс.Контеста