Блог Романа Елизарова

Первым делом, мне хочется поздравить команду СПбГУ в составе Игоря Пышкина, Станислава Ершова и Алексея Гордеева с победой в 40-м Ежегодном Финале Командного Чемпионата Мира по Программированию (ACM ICPC). Для тренера команды Андрея Лопатина, это уже 4-ая победа в этом престижном международном соревновании — два раза он побеждал как участник и два раза как тренер.

В этом году борьба была особенно напряженной, без явных фаворитов. Официальная таблица результатов лежит здесь. СПбГУ опередил Шанхай всего на 7 штрафных минут.

Благодаря победе ребят, вузы из Санкт-Петербурга (СПбГУ и Университет ИТМО) уже пять (!) лет подряд становятся Чемпионами Мира. И вообще, команды из России показали отличные результаты — пять из первых десяти мест в этом году наши (СПбГУ, МФТИ, Университет ИТМО, УрФУ, ННГУ).

В этом году нашей группе волонтеров снова предложили продолжить заниматься организацией ICPC Live — трансляцией Чемпионата в прямом эфире для аудитории в интернете.

А тем временем Финал проходил на острове Пхукет в Тайланде. Мы уже намучились в прошлом году с "трудностями перевода" на Финале в Марокко, и было решено не полагаться на силы местных подрядчиков для съемки видео-картинки, а всё сделать силами группы ICPC News, обычно занимающейся видео и фотосъемкой соревнований, силами группы ICPC Analytics, следящей за кодом, который пишут участники, и силами нашей группы ICPC Live, которая обеспечивает всю инфографику, комментарии и техническое обеспечение трансляции в интернет.

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

Все волонтеры группы ICPC Live прошлого года согласились участвовать и в этом году, а с изменением формата трансляции нашу группу пришлось даже расширить.

Большая благодарность за всю проделанную работу нашему главному сценаристу и генератору идей Лиде Перовской, умельцу на все руки Паше Маврину, мега-программистам инфографики и анимаций Виталику Аксенову и Анне Маловой, главному комментатору и аналитику Егору Куликову, мастеру по видео Павлу Кроткову, дизайнеру Мише Куцеву, видео-монтажеру Виктории Волочай, контент-продюсеру Ниязу Нигматулину, и корреспонденту Чарльзу Невилю. Это не их профессии, да и вообще, никто из нас не занимается профессионально ничем, связанным с видео-продюсерством, просто все они болели за общее дело и делали то, что было нужно, а так же всегда были готовы помочь. На самом деле, полностью перечислить, кто и что именно делал в ICPC Live, просто невозможно. Работы было дикое количество, и на сон времени практически не оставалось.

В студии нам помогали Елена Андреева и Рита Саблина, в комментаторской Егору помогал глава ICPC Analytics Фредрик Хайнс, а в процессе подготовки данных по командам — Олег Христенко. Более того, Паше Маврину удалось запустить экспериментальную студию с русским комментарием от Анны-Вероники Дорогуш и Михаила Левина, правда русская трансляция регулярно отваливалась, так как следить за ней в этом году свободных рук уже не было. Зато мы теперь знаем, что еще нужно автоматизировать и запрограммировать, чтобы в следующем году всё организовать на еще большем количестве языков.

Кто хочет узнать подробней о том, как оно всё было устроено с технической точки зрения — читайте классную статью Лиды Перовской на Хабре. Виталик Аксенов писал анонс наших усилий на портале CodeForces.

В этом году у нас было вагон технических проблем, решение которых отнимало массу времени и не позволило реализовать все задумки. Пришлось применить все заготовленные костыли. Однако, благодаря общим усилиям трансляция получилась отличная. Я бы даже сказал — эпическая. В этом году мы начали трансляцию задолго до начала соревнований и вели её вплоть до конца церемонии закрытия. Результат нашего труда можно увидеть на нашем канале на YouTube. К нам пришло признание и от профессионального ТВ — кадры из нашей трансляции были использованы в новостном сюжете на телеканале Вести 24.

У нас родилось еще больше идей на финал следующего года, который пройдет в Рапид-Сити, Южная Дакота, США. Любые предложения и конструктивные замечания всячески приветствуются.

Большое спасибо организаторам конференции JPoint 2016. Конференция получилась отличная, хорошая подборка докладов. Слайды моего доклада "Wait for your fortune without blocking" я уже выложил здесь.

JPoint Student Day тоже получился ничего, хотя и народу было не очень много. Cлайды с доклада "Многопоточное Программирование — Теория и Практика" выложены здесь.

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

После продолжительного перерыва я снова появлюсь на публике. Больше года я не выступал ни на каких технических конференциях. Этому была вполне уважительная причина, ибо я занимался изучением Финансовой Математики (aka Quantitative Finance). Более подробно эта тема раскрыта в моем недавнем интервью JUG.RU в цикле "Без Слайдов". Теперь всё это позади. Знания получены, экзамены сданы, я получил официально право "to use the CQF designation letters after my name". Но бросать программирование и идти управлять рисками в какой-нибудь банк я пока не планирую. Теперь я снова буду нести свет знаний многопоточного программирования в массы.

В этом году на конференции JPoint 2016, которая пройдет в Москве 22-23 апреля, я сделаю не "научно-популярный" доклад, а наоборот. Это будет узко-специализированный доклад про мало известную, но порой очень полезную штуку из области синхронизации без блокировок. А именно, как совместить необходимость "усыплять" потоки до наступления какого-либо события с синхронизацией без блокировки, который мы частенько занимаемся ради пресловутой производительности. Но ведь ожидание чего-либо это и есть блокировка? Так? А вот и не так! Более подробно об этой я и расскажу на 2-м дне конференции в докладе под кодовым названием "Жди своего счастья без блокировки!".

Будет и научно-популярный доклад "Многопоточное программирование — Теория и Практика", по мотивам моего доклада на JPoint 2-х летней давности (но с практическими примерами!). Я его сделаю в рамках JPoint Student Day. Это отдельный день (24 апреля), в который пройдет специальная конференция для студентов, еще лишь открывающих для себя дорогу в мир профессионального программированию. Эта как раз та аудитория, которой нужно не столько дать конкретные знанию про ту или иную технологию (ибо технологии поменяются десяток раз в процессе их будущей профессиональной деятельности), сколько рассказать фундаментальные вещи и факты, которые на всю жизнь. А еще, что более важно, их нужно заинтересовать учиться самим. Именно поэтому, в конце доклада я буду рекомендовать прочитать замечательную книгу M. Herlihy. The Art of Multiprocessor Programming. 2012, про которую я в своем время даже отдельно писал. Жаль, что перевода её на Русский так и нет (может кто-нибудь занимается издательской деятельностью и посодействует это исправить?).

В эти выходные, 5-6 декабря 2015 года, пройдут Юбилейные, 20-е, соревнования Северовосточного Европейского Региона Студенческого Командного Чемпионата Мира по Программированию (NEERC). Как обычно, мы ждем очень напряженной борьбы. Как показывает история последних лет именно победители нашего полуфинального соревнования в последнее время становятся Чемпионами Мира ACM ICPC — самого престижного соревнования программистов в мире. Например, первые два места прошлогодних региональных соревнований, о которых я писал здесь в точности заняли первое и второе места на Финале ACM ICPC, который проходил 20 Мая 2015 года в Марракеше, Марокко.

В этом году мы подготовили специальный, Юбилейный, пробный тур в субботу 5-го декабря чтобы вспомнить историю соревнований и развлечь всех участников. Подробности смотрите в расписании.

Обратите внимание на официальную новостную страницу NEERCNews. Там размещена информация о регистрации гостей, которые захотят посетить Юбилейные соревнования.

А вот историческое фото команды победителя соревнования 20 лет назад (слева на право): Марк Сандлер, Денис Кисловский, и я.

В среду, 20 мая, в 12:30 по московскому времени начнется Финал 39-го Командного Чемпионата Мира по Программированию ACM (Association for Computing Machinery) ICPC (International Collegiate Programming Contest). 38 тысяч студентов из 2534 университетов со всего мира участвовали в региональных соревнованиях за право попасть на Финал этого самого престижного в мире соревнования по программированию. 128 команд различных вузов, по 3 человека от каждого вуза, приехали в город Марракеш, Марокко, чтобы биться за право называться Чемпионами Мира по Программированию. В этом году Россия представлена 10-ю командами ведущих вузов из Санкт-Петербурга, Москвы, Саратова и Казани.

Начиная с 2008 года с соревнования ведется прямая видео трансляция. В этом году трансляцию для вас проводит команда волонтеров из Санкт-Петербургского ИТМО, включая меня . У нас есть веб-камера на рабочей станции каждой команды и возможность посмотреть на экран их монитора. У нас будет одна камера на потолке и два оператора с камерами на полу соревнования, которые позволят нам увидеть всё происходящее на полу и посмотреть на работу интересующих нас команд со стороны. Мы начнем трансляцию за 30 минут до начала соревнований (в 12:00 по Москве) и будем следить на тегом #ICPCLive в twitter. Мы будем отслеживать соревнования в реальном времени, принимать заявки от зрителей через twitter, показывать те команды, которые набирают больше всего упоминаний в twitter от наших зрителей. К нам в студию будут приходить гости, которые расскажут интересные факты из истории соревнования и поделятся своими секретах подготовки команд, закулисными организационными тайнами и веселыми историями.

Команда аналитиков будет следить за работой команд, отслеживать их активность. На блоге ICPCNews: http://icpcnews.tumblr.com/ можно заранее ознакомиться с информацией о командах-фаворитах, претендующих на звание Чемпиона Мира в этом году. За новостями соревнования можно следить через twitter @icpcnews. Во время соревнования на сайте http://myicpc.icpcnews.com/ можно будет следить за таблицей результатов, статистикой по командам, и т.п. Видео живой трансляции соревнования будет запущено на сайте http://icpclive.org/. В этом году у нас будет два экрана. Первый, основной экран, будет содержать основную трансляцию с текущий таблицей результатов, бегущей строкой новостей, дискуссией с гостями в зале, видео из зала и обсуждаемых команд. Второй, дополнительный экран, будет постоянно показывать работу 4-х команд по нашему выбору. К сожалению, у нас не технической возможности запустить в сеть видеопотоки всех команд, но мы будем стараться сделать вам интересно.

Очередные, 19-е, соревнования Северовосточного Европейского Региона Студенческого Командного Чемпионата Мира по Программированию (NEERC) завершились. В следующем году нас ждут юбилейные, 20-е соревнования. Таблица результатов доступна на сайте соревнования. Победителем стала команда Санкт-Петербургского Университета ИТМО (Короткевич, Минаев, Васильев). В этом году борьба было очень напряженная. Первая команда Московского Государственного Университета (Евстропов, Пядеркин, Омельяненко) дышала в спину победителям и даже обходила их в один из моментов соренования. Обе команды решили по 9 из 11 задач, оторвашись на 2 задачи от остальных команд.

В этом году 15 сильнейших вузов нашего региона получают право участвовать в Финале Чемпионата Мира по Программированию ACM ICPC — самом престижном соревновании среди программистов в мире. Финал Чемпионата пройдет 16-21 Мая 2015 года в г. Марракеш, Марокко, где соберутся более 120 команд сильнейших вузов мира, чтобы бороться за звание Чемпиона Мира. NEERC по праву считается сильшейшим региональным соревнованием планеты. Победители NEERC становились чемпионами мира 6 раз из последних 10 финалов, включая все три последине года. Очень надеюсь на продолжение этой замечательной традиции и в этом году.

Огромное спасибо всем организаторам, волонтерам и спонсорам соревнования. Особенно хочется отметить технический коммитет соревнования, уже многие многие годы возглавляемый Матвеем Казаковым, и обеспечивающий бесперебойное и слаженное проведение соревнований. Отдельное спасибо нашему члену жюри Петру Митричеву, благодаря усилиям которого, мы оживили церемонию награждения, показав анимацию стратегии команды ИТМО в задаче G. Побробности смотрите в блоге Петра.

Условия задач выложены на сайте соревнования здесь. В этом году, после 5-и доступных всем задач A, B, F, J, и K, сложность резко возрастала. Только 35 команд решили больше 5 задач, в основном за счет задачи I. Я очень разочорован тем фактом, что мало команд решили задачи C и D. Задача C, решенная только двумя командами-лидерами, была доступна абсолютно всем командам ибо не требовала каких-либо специальных знаний и уже её точно можно было спокойно написать за последний час соревнования. Более того, в отличие от задачи I, которую многие пытались решить не успешно, задачу C было очень легко отладить на приведенных примерах. Её просто было нельзя сделать неправильно. Большое разочарование вызвал и тот факт, что задача F оказалась для учатников наиболее сложной из 5 простых задач. Складывается ощущение, что сложность задачи просто пропорциональна суммарному объему условия и кода решения. Конечно есть и усключения, вроде задачи H, правильное решение которых просто очень сложно придумать, и, даже придумав, очень сложно реализовать правильно. Интересно, проводил ли кто-нибудь такой анализ?

Краткий разбор задач я выложил здесь. Медиа-центр ИТМО записал видео разбора и выложил его здесь.

Во вторник, 21 Октября, я буду выступать в Санкт-Петербурге с докладом на конференции Joker. И буквально на этой неделе я снова столкнулся с темой доклада напрямую. А тема такая. Очень часто проблемы производительности реальных Java приложений под нагрузкой происходят из-за слишком большого количества генерируемого при работе мусора в памяти. Доклад называется "Почему GC съедает все моё CPU?". На нем я как раз об этом и расскажу со всеми подробностями. Акцентирую вниманеие в чем отличие в этом плане Java от других языков типа С/C++. Вот вам спойлер: неэффективный код одинаково легко написать на любом языке, но методики поиска проблем имеют свои специфики. А на Java мы пишем очень, очень большие приложения и когда они начинают тормозить, то для поиска в них узких мест без специальных инструментов не обойтись. Вот, например, на открытии торгов в одном из компонентов системы более 30% CPU уходит на сборку мусора. Как найти виновника?

Львиная доля доклада как раз будет посвящена инструменту, который мы, в Devexperts, разработали для поиска проблем с излишним мусором — Aprof. Я его уже упоминал в других докладах: в DIY Java Profiling в 2011 году он явно упоминался, а в Миллионах котировок в секунду он проскакивал, так как без контроля за выделением памяти действительно высокопроизводительную систему просто не сделать. Наконец-то я раскрою эту тему в полной мере. Расскажу как пользоваться Aprof-ом и как интерпретировать полученные результаты. Объясню как он устроен, что же именно он замеряет, как он это делает, и какой эффект на производительность целевого приложения это оказывает. Не обойду вниманием и связанные со всей этой темой фишки HotSpot — его умение выделять объекты на стеке устранять выделение памяти под объекты.

В процессе подготовки доклада я навел порядок и в исходниках самого Aprof-а. Они получили место постоянной прописки на GitHub по адресу https://github.com/devexperts/aprof (безусловно, их копия живет и в нашем корпоративном git репозитории). Обновил используемую версию ASM до 5.0.3. Теперь поддерживается Java 8. Выпустил свежий релиз Aprof. Теперь последнюю версию можно скачать с Bintray:

UPDATE: Тут читатели меня правильно поправляют, что некорректно говорить о том, что HotSpot умеет выделять объекты на стеке. Он вообще устраняет выделение памяти под объекты, если есть такая возможность.

UPDATE2: Слайды с доклада ( Collapse )

В этом году 38-ой ежегодный Финал Чемпионата Мира по Программированию ACM ICPC принимает в Екатеринбурге Уральский Федеральный Университет. Так получилось, что финал проводится в России второй раз подряд, сразу после Финала 2013 года в Санкт-Петербурге. Это символ признания мировых позиций Российской школы образования программистов. Команды Российских вузов становились чемпионами мира уже 8 раз за последние 20 лет, начав участвовать в региональных соревнованиях только с 1994 года.

В далеком 1994 году, будучи студентом 1-го курса ИТМО, я собрал команду и отправился на региональные соревнования в Бухарест. Мы имели хорошие знания алгоритмов и умение программировать, успехи в личных соревнованиях. Однако, не имея опыта командной работы, мы предсказуемо провалились. На следующий год, уже подготовленными, мы заняли 1-ое место на региональных соревнования в Амстердаме и прошли в Финал. Со следующего, 1996 года, проходил уже первый финал наших собственных региональных соревнований NEERC в Санкт-Петербурге, который я возглавил с 1997 года. С тех пор команды ИТМО каждый год попадали в Финал, но пройдет еще почти десятилетие и сменится несколько поколений, бывшие участники будут становиться тренерами, прежде чем, в 2004 году, команда ИТМО, тренируемая Андреем Станкевичем, в составе Димы Павлова, Паши Маврина и Сергея Оршанского станет Чемпионом Мира по Программированию. Это время ушло на построение в ИТМО целой школы по привлечению и обучению одаренных ребят именно в области программирования. Работа с одаренными детьми начинается уже с 6-го класса в рамках ЛКШ, кружков и различных олимпиад для школьников. И работают с детьми все те же чемпионы мира и заслуженные тренеры.

Но первыми Чемпионами Мира от России в 2000 году стала команда СПбГУ, под руководством Натальи Вояковской и Максима Шафирова, в составе Николая Дурова, Андрея Лопатина и Олега Етеревского. Дуров и Лопатин повторили свой успех и в 2001 году. Это была уникальная по составу и силе команда, но, по правилам, больше двух раз в Финале участвовать нельзя. Такой двукратный успех был очень долго ни кем не повторен. Под руководством тренера Андрея Станкевича, ИТМО занимала призовые места два года подряд в 2008 и 2009 годах, но это были полностью разные по составу команды. Только в 2012 и 2013 годах Михаил Кевер и Нияз Нигматулин стали двукратными чемпионами мира подряд, при поддержке, в 2012 году, чемпиона 2009-го года, Евгения Капуна, но и этот успех нельзя на равных сравнить с достижением Дурова и Лопатина. В 2013 году к ним в команду присоединился 7-и кратный участник Международных олимпиад по информатике, обладающий 6-ю(!) Золотыми медалями с 2007 по 2012 год, первый в таблице славы участников школьных олимпиад, Гена Короткевич. Такая команда не могла не победить.

В этом году Гена, будучи еще студентом 2-го курса, делает перерыв. Не выступает, а тренируется. Поэтому определенного фаворита в соревнованиях не наблюдается. Тем увлекательней будет за ними наблюдать. Я в этом году ведущий видео-трансляции соревнований. Несмотря на то, что я был директором соревнований прошлого года и участвовал в виде-трансляции соревнований, которую организовала компания Yandex, как партнер ИТМО, это будет для меня новым опытом. Я благодарен за эту возможность партнеру УрФУ при проведении Финала 2014 года, компании СКБ Контур.

Следите за обновлениями на локальной странице Финала ICPC 2014 года. Видео-трансляция будет доступна по этой ссылке. На том же сайте можно зарегистрироваться гостем для личного присутствия. Дух предстоящих соревнований отлично показан во вводном видео ( Collapse )

Через неделю после предыдущего доклада в Москве я выступил с его расширенной версией в Санкт-Петербурге, на конференции BitByte 2014. В формате "мастер класс" у меня было полтора часа на выступление. Сильно больше материала представить у меня не получилось, но, в дополнение к основным теоритическим предпосылкам, я успел затронуть вопрос построения линеаризуемых алгоритмов и основы теории алгоритмов без блокировки.

Моей задачей было заинтересовать слушателей теорией параллельного программирования и, судя по некоторым отзывам, цель была достигнута. Несколько человек, подошедших ко мне после выступления, явно хотели знать больше, и, я надеюсь, займутся самообразованием в этой области. А для сотрудников Devexperts я прочитаю в этом году целый курс из 8 лекций, в котором будет весь этот материал и много, много еще всего. Большую часть материала я возьму из курса лекций, который я читаю в ИТМО, но будет и много нового. Я подготовлю отдельную лекцию исключительно про JMM, где я подробно разберу структуру JMM и научу коллег доказывать и анализировать корректность кода по JMM. Несколько лекций будет посвящено практическим алгоритмам. В плане стоит отдельная лекция только про очереди и отдельная лекция только про хеш-таблицы. Там я не только расскажу и объясню все фундаментальные "классические" многопоточные построения на списках, но и современные достижения в области алгоритмов на массивах которые, как известно и о чем я уже писал, существенно превосходят списочные структуры по производительности на практике.

( Collapse )

На доклады на конференции JPoint 2014 в Москве было выделено по 45 минут. Что можно рассказать за 45 минут из теоретического курса параллельного программирования, который, по-хорошему, занимает целый семестр? Цель моего доклада заключалась в том, чтобы дать слушателям минимально необходимую теоретическую базу, которая позволит прочитать и понять 17-у главу спецификации языка Java (JLS), которая четко регламентирует допустимое поведение многопоточных программ на Java на любой архитектуре CPU. Это значит, что программисту на Java не обязательно разбираться в подробностях и деталях реализации кэшей, протоколов когерентности, параллелизма на уровне инструкций, специальных инструкций и барьеров, как и других особенностей различных архитектур. Это задача для тех, кто пишет JVM или хочет написать самый быстрый код. Программист на Java может писать корректные многопоточные программы, если он четко понимает, какие исполнения его многопоточного кода допустимы с точки зрения спецификации языка Java.

В качестве основной идеи доклада я выбрал тот неочевидный факт, что, в общем случае, поведение многопоточных программы нельзя изучать путем анализа различных перестановок выполняемых операций. Я отобрал основные определения и объяснил суть последовательной согласованности и линеаризуемости, чтобы подвести к этому факту. Из-за технических накладок с трансляцией организаторы попросили задержать начало доклада, из-за чего на доклад осталось около получаса, и его кульминационная концовка была несколько смазана. В этой записи я еще раз развернуто объясню основную идею и дам ссылки для домашнего чтения тем, кому хочется в этом подробней разобраться. ( Collapse )