Комментарии 47
Попытался поставить плюс и только тогда понял, что статья без ката) Думаю, стоит спрятать под кат.
А информация интересная. Особенно тем, кто любит играться с бенчмарками различными
Боюсь, что запустить большинство наших компиляторов под QNX будет не простой задачей)
Я из текста вашей статьи понял, что у вас всё это нужно только для «олимпиады». Такие задачи, обычно, похожи на задачи из примера и вполне заработают и со штатными компиляторами Си++ в QNX.
А так — люди с linux пакеты портировали, помнится.
Это, конечно, немного не по теме, но, извините, очень уж режет глаза, зачем первые две строчки в коде?! У вас же нет никаких i/o операций, и этот «using namespace std;» тоже совершенно ни к чему!

Это еще цветочки в олимпиадном программировании, там в топовых решениях define на define, куча велосипедов, циклы с 10ю уровнями вложенности и т п. Переменные именуются не иначе как a, b, c, a1… и обычно их объявляют в начале файла побольше "про запас". Все эти соревнования имеют минимум общего с промышленной разработкой.

А не пробывали вместо патча ядра поиграть с настройками планировщика (chrt)?
Попробовать поиграть политиками скедулинга процесса и таким образом добиться изолированного исполнения? Интересная мысль в целом.
Тут правда есть особенность, что некоторые решения могут форкаться и создавать потоки. Но это не то чтобы блокер. Спасибо за идею — попробую на досуге)
Очень интересная статья, спасибо!

Такой вопрос:
В решении задачи ввод можно читать либо из файла «input.txt», либо из stdin.
Это как-то влияет на скорость выполнения в вашей системе? Были ли с этим проблемы и, если были, то как вы их обошли?
Пожалуйста!)
На самом деле не влияет, т.к. input.txt — это не файл, а UNIX domain socket.
Так что для передачи инпута в решение в любом случае используется не файловая система, а буферы памяти ядра
Разница между самым быстрым и самым медленным исполнением — 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 на каждом из серверов?

Так а в продакшене у вас тоже кластер на мобильных процах которые неизебжно тротлят?

Нет в продакшене xeon'ы
И они неизбежно скедулят процессы. Что приводит к разбросу времени выполнения решения
А про троттлинг я выше где-то в этой ветке писал

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

Тем, что это все равно не дает гарантий от просадки производительности из-за скедулнга. Можете во время выполнения башника, который вы скидывали во время ветки, запустить его еще раз (сэмулировать выполнение еще одногорешения на этой же железке). Время выполнения просядет.
Так что решение нужно приколачивать или к ядру или к всему серверу целиком. К ядру все-таки лучше
Довольно странно в олимпиадном программировании распределять места по скорости работы программы. Тогда джависты/питонисты точно пролетают и все, нацеленные на 1-е место, пишут на голом Си с ручными оптимизациями каждой строчки.

Обычно тесты бинарные: прошло/не прошло по времени, время даётся с запасом на предполагаемую асимптотику.

Сортировка — конечно же не по времени работы программы. Как правило она по сумме времени, потраченного на решение сданных задач, и штраф в 20 минут за каждую неверную попытку.


А запас по времени может быть достаточно маленьким — скажем, если нужно, чтобы решение с асимптотикой О(n) на "медленном" языке проходило, а с O(n*logn) на быстром — уже нет. И в таких ситуациях гарантированная скорость работы тестовых машин пригодится.

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

Разницу между O(n) и O(n*logn) нельзя ловить, т.к. логарифм для обозримых n по сути, константа. Между n, n^2, n^3 — можно и нужно.

Разницу между O(n) и O(n*logn) ловить можно и иногда нужно. Для этого приходится использовать n=1e6 или n=1e7, и в этом случае логарифм >20, уже вполне ловится.

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

Когда-то писал статью про измерение performance — habr.com/ru/post/171475. Если совсем кратко, то необходимо выделить метрику, которая будет постоянна и не зависеть от внешних условий (не только запущенных программ, os schedule, но и от скачков напряжения электросети). Очевидный ответ, надо построить распределение и найти mean распределения, но на практике требуется просто огромное количество запусков для более-менее достоверной выборки.

В итоге, лучше всего брать выборку на 10-50 запусков и использовать минимальное время на выполнение или медиану из 3-5 минимальных времен. Подробный разбор в статье.

Хм. Спасибо за статью — это пригодится.
Взял на заметку)

Не понимаю прикладной необходимости в этих "приседаниях". С одной стороны ответ очевиден — для того, что бы код выполнялся за равное время. Но зачем?


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


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


Более того, задача выглядит вредной, т.к. убивает принцип эффективной утилизации ресурсов. Т.е. люди придумывали всякие нужные технологии для этого и тут приходишь ты и отрубаешь все это нафик. Потому, что… — что?


Ну допустим нужно дать именно этой задаче максимум ресурсов. Ok. Выделяем под нее сервер и нагружаем его только этой задачей. Ресурсы будут распределяться только между равными задачами.


Если я что-то не вижу, поясните пожалуйста.

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

Я думаю, что тут важен стенд для проверки идентичный для всех. И методика оценки. Например, тот же запуск 1000 раз и средняя скорость. А для пущей релевантности — минимальное зафиксированное время за 1000 раз.


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


Погодите… в статье речь идет о самом стенде?

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

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

Вот именно, Речь как раз о том, что окно допуска слишком большое.

Запуск 1000 раз прямо противоречит цели "выдать результат побыстрее". А она есть)

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

Но выше я написал, что кажется не верно цель понимал. И речь идет о создании как раз стенда для проверки. Т.е. создании таких, идентичных условий. В этом случае задача видится разумной.

Хотя тут бы я смотрел в сторону ОС реального времени исполнения. Не стараясь изобрести велосипед на ОС заведомо предназначенной для разделения ресурсов.

они в статье не минимизированы, а выровнены. Это разные вещи, не?

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


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

В таких соревнованиях результат не зависит напрямую от скорости работы программы, то есть не важно сколько программа работала, если при этом уложилась в заранее определённый лимит. Лимит обычно даётся с запасом на фазу луны, медленный язык…

Идея интересная. Как отдельная олимпиада. Только инструкции х86 к реальным инструкциям железа имеют мало общего. Т.е надо эмулировать реальный проц, который запатентован :)

Реальные тесты же работали не на ноутбуке? Потому что не понимаю, как ему NUMA могла повлиять.
Хм. Действительно. Да это мой косяк.
Конфигурация NUMA используется в проде, поэтому и в статье ее упомянул. На ноуте она повлиять конечно не могла.
Проведу повторные измерения для статьи на серверном окружении и внесу правки. А пока сделаю приписку в разделе про NUMA. Спасибо
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.