company_banner

Как заставить код выполняться за одинаковое время? Способы от Яндекс.Контеста

    Недавно мы объявили на Хабре, что начинаем принимать заявки на Яндекс.Алгоритм и другие треки чемпионата по программированию Yandex Cup. Уже много лет онлайн-соревнования Яндекса и других компаний проходят на платформе Контест. Меня зовут Павел Тыквин, я один из разработчиков Контеста. Основная задача нашей платформы — получить от участника чемпионата исходный код решения, скомпилировать и запустить этот код, прогнать тесты и вернуть результат. Звучит не очень сложно. Давайте попробуем.

    int main()
    {
    	int n = 500000000;
    	int *a = new int[n + 1];
    	for (int i = 0; i <= n; i++)
    		a[i] = i;
    	for (int i = 2; i * i <= n; i++)
    	{
    		if (a[i]) {
    			for (int j = i*i; j <= n; j += i) {
    				a[j] = 0;
    			}
    		}		
    	}
    	delete[] a;
    	return 0;
    }

    Это простенькое приложение специально для экспериментов, оно ищет простые числа методом решета Эратосфена. Запустим решение 20 раз и посчитаем user time каждого исполнения.

    Описание тестового стенда
    i7-8750H @ 2,20 ГГц
    32 ГБ RAM
    OС:
    Ubuntu 18.04.4
    5.3.0-53-generic

    Разброс времени исполнения до оптимизаций:


    Разница между самым быстрым и самым медленным исполнением — 2230 мс.

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

    Попробуем выравнять время исполнения.

    Изоляция ядер


    Начнем с очевидного. Процессы конкурируют за ядра, и нужно каким-то образом изолировать ядро под исполнение решения. Кроме того, с включенным Hyper Threading операционная система определяет одно физическое ядро процессора как два отдельных логических ядра. Для честной изоляции ядра нам нужно отключить Hyper Threading. Это можно сделать в настройках BIOS.

    Ядро Linux из коробки поддерживает флаг запуска для изоляции ядер isolcpus. Добавим этот флаг в GRUB_CMDLINE_LINUX_DEFAULT в настройках grub: /etc/default/grub. Например: GRUB_CMDLINE_LINUX_DEFAULT="... isolcpus=0,1"

    Выполним update-grub и перезапустим систему.

    Все выглядит как ожидалось — первые два ядра не используются системой:



    Запустимся на изолированном ядре. Конфигурация CPU Affinity позволяет привязать процесс к конкретному ядру. Есть несколько способов это сделать. Например, запустим решение в porto-контейнере (ядро выбирается с помощью аргумента cpu_set):

    portoctl exec test command='sudo stress.sh' cpu_set=0

    Офтоп: для запуска решений в продакшене мы используем QEMU-KVM. Porto-контейнер используется в статье, чтобы было проще показать.

    Запуск с ядром, выделенным под решение, без нагрузки на соседние ядра:


    Разница — 375 мс. Стало лучше, но это все равно слишком много.

    Тюним перфоманс


    Давайте попробуем провести наш тест под нагрузкой. Под какой именно? Наша задача — множеством потоков нагрузить все ядра. Это можно сделать несколькими способами:

    1. Написать простое приложение, которое создаст много потоков и начнет считать что-нибудь в каждом из них.
    2. Выполнить команду: cat /dev/zero | pbzip2 -c > /dev/null. pbzip2 здесь — это многопоточная реализация bzip2.
    3. Или можно установить утилиту stress и дать нагрузку командой stress --cpu 12.

    Запуск с ядром, выделенным под решение, с нагрузкой на соседние ядра:


    Разница — 1354 мс: на секунду больше, чем без нагрузки. Очевидно, нагрузка повлияла на время исполнения, несмотря на то, что мы запускались на изолированном ядре. Видно, что в определенный момент время исполнения уменьшилось. На первый взгляд это контринтуитивно: при растущей нагрузке производительность тоже увеличивается.

    В продакшене такое поведение (когда время исполнения начинает плыть под нагрузкой) может выстрелить очень болезненно. Что такое нагрузка в данном случае? Поток решений от участников, чаще всего на крупных соревнованиях и олимпиадах.

    Причина в том, что под нагрузкой включается Intel Turbo Boost — технология увеличения частоты. Отключим ее. Для своего cтенда я выключил еще и SpeedStep. Для процессора AMD нужно было бы выключить Turbo Core Cool'n'Quiet. Все перечисленное делается в BIOS, основная идея — отключить то, что автоматически управляет частотой процессора.

    Запуск на изолированном ядре с отключенным Turbo Boost и нагрузкой на соседние ядра:



    Выглядит неплохо, но разница все еще составляет 252 мс. И это все еще слишком много.

    Офтоп: заметьте, как просело среднее время исполнения — примерно на 25%. В повседневной жизни отключенные технологии — это добро.

    Мы избавились от конкуренции за ядра, стабилизировали частоту ядер — теперь на них ничто не влияет. Так откуда же разница?

    NUMA



    Non-Uniform Memory Access, «неравномерный доступ к памяти», или Non-Uniform Memory Architecture, «архитектура с неравномерной памятью». В NUMA-системах (то есть, условно, на любом современном многопроцессорном компьютере) у каждого процессора есть локальная память, которая рассматривается как часть общей. Каждый процессор может обратиться и к своей локальной памяти, и к локальной памяти остальных процессоров (удаленной памяти). Неравномерность в том, что доступ к локальной памяти происходит заметно быстрее.

    Время исполнения «гуляет» именно из-за такой неравномерности. Пофиксим ее, привязав наше исполнение к конкретной numa node. Для этого добавим numa node в конфигурацию porto-контейнера:

    portoctl exec test command='stress.sh' cpu_set="node 0" cpu_set=0

    Запуск на изолированном ядре с отключенным Turbo Boost, конфигурацией NUMA и нагрузкой на соседние ядра:


    Разница — 48 мс, а среднее время выполнения решения после того, как мы отключили процессорные оптимизаций, составляет 10 с. 48 мс в масштабе 10 с — равносильно погрешности в 0,5%, очень хорошо.

    Важный спойлер
    Спасибо vlanko за замечание.

    На обычном ноутбуке конфигурировать NUMA бесполезно т.к. процессор у нас один. Улучшение стабильности тестовых решений в данном случае NUMA-конфиг не объясняет.
    NUMA важна на серверах в проде. И для демонстрации этого на досуге проведу дополнительные замеры на сервере и приложу к статье


    Еще немного про isolcpus


    У флага isolcpus есть проблема: некоторые системные потоки все равно могут schedule'иться на изолированное ядро.

    Поэтому в продакшене мы используем пропатченное ядро с расширенной функциональностью этого флага. Тем самым мы выбираем ядро с учетом флага, когда происходит scheduling потоков.
    Патч самописный, сделан над ядром 3.18. В этом ядре есть макрос kthread_run, которым некоторые драйвера пользуются для запуска своих потоков. Во время запуска не производится проверка на доступные CPU, и потоки могут исполняться на любом ядре вне зависимости от настроек isolcpus.

    Поэтому мы и написали патч — в нем добавлен новый аргумент запуска slave_cpus и несколько макросов, которые выбирают ядро для запуска с учетом маски из этого флага.

    Планы на будущее


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

    Переезд в облако
    Новым вызовом для системы станет необходимость запускаться в Яндекс.Облаке. По нынешним меркам железные сервера — это ненадежно, переезд необходим, но важно сохранить консистентность выполнения посылок. Здесь технические возможности пока исследуются. Есть идея, что в крайних случаях на облачных машинах можно выполнять решения, не требующие строгого времени исполнения. Тем самым мы снизим нагрузку на железные машины и они будут заниматься только решениями, которые как раз требуют консистентности. Есть и другой вариант: сначала проверять посылку в облаке и, если она не уложилась в лимит времени, перепроверять на реальном железе.

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

    Выводы


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

    Комментарии 47

      +2
      Попытался поставить плюс и только тогда понял, что статья без ката) Думаю, стоит спрятать под кат.
      А информация интересная. Особенно тем, кто любит играться с бенчмарками различными
        0

        Кат поправили, да, спасибо.

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

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

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

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

                  Даже после всех ухищрений процессоры неизбежно будут троттлить

                  Попробуйте подключить к процессору нормальное электропитание и достаточное охлаждение. Или хотя бы воткнуть ноутбук, на котором вы делаете замеры, в розетку. С чего вдруг процессор неизбежно должен троттлить?
                    +1
                    На компе продолжали работать KDE, Chrome, Slack и куча другого софта.

                    Я конечно не большой спец по серверным нагрузкам и прочему, но что-то мне кажется, что не будет эта «куча другого софта» насиловать скедулер настолько чтобы это это было сколько-то заметно. Если вы не запускаете тест, какая у вас нагрузка на цпу? У меня тоже вот десяток приложений запущен, нагрузка на CPU ~0.01
                      0

                      У автора ноутбучный проц, о каких серверах речь?

                        0
                        Я еще немножко подумал и теперь вынужден с вами согласиться. Подозрительно.
                      0
                      В вашем стенде что-то фатально поломано.

                      Провел повторные замеры простым башем:
                      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 приложением или нагрузить ядра одним из способов из статьи.

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


                      Когда речь идет про тестовый стенд, то можно быть уверенным и в охлаждении, и в питании. Но вот контроллер стойки в ДЦ может в определенный момент решить, что пришло время ронять частоту и приложение на это уже никак повлиять не сможет.

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

                        –2
                        Можно во время теста попользоваться каким-нибудь жадным до CPU приложением или нагрузить ядра одним из способов из статьи.

                        Зачем? Я думал, цель — получить стабильное время выполнения, а не наоборот.

                          0
                          Зачем? Я думал, цель — получить стабильное время выполнения, а не наоборот.

                          Цель оптимизаций — добиться стабильного выполнения. А цель тестового стенда — проверка стабильности и поиск способа которым эту стабильность можно сломать)

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

                            В результате ваших оптимизаций время выполнения программы просело, на глазок, более чем на 40%. М.б. проще было не нагружать процессор свыше 2/3?


                            При условии стабильного времени выполнения без нагрузки (чего, как я уже сказал, вполне можно ожидать от процессора с нормальным питанием и охлаждением [нет, ноутбучный процессор под эти условия не подходит]), все дальнейшие пляски могут оказаться не нужны.

                              0

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

                                0

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

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

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

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

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

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


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

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

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

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

                                +1

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

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

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

                              +1

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

                              +1

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


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


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


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


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


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

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

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


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


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

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

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

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

                                          Насколько я знаю, в бенчмарках типа https://benchmarksgame-team.pages.debian.net/benchmarksgame смотрят на лучший результат, именно потому что более худшие могли оказаться подвержены влиянию фазы Луны и прочим неучтённым факторам.

                                        0

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

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

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

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

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

                                      +2

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


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

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

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

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

                                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                          Самое читаемое