Андрей Власовских
Команда spb-archlinux на ICFPC 2009
Никак не возьму в привычку чаще писать в блог. Но на этот раз повод действительно есть. Наша команда spb-archlinux принимала участие в программерском конкурсе ICFP Contest 2009 :)
Ниже рассказ об этом. Если вкратце, было весело! :)
Upd: В финальной таблице результатов мы заняли 95 место с 1826 очками.
Один из членов команды Jkff уже описал наше участие в своём отчёте, так что здесь я остановлюсь на частностях и личном впечатлении, а за общим описанием отсылаю вас в его блог.
Итак, описание Jkff вы уже прочитали. Я бы хотел рассказать про отдельные моменты конкурса. Мне наиболее интересно то, почему мы заняли относительно невысокое место (за 4 часа до окончания мы были 84-ые из 317). Поэтому ниже проводится «разбор полётов». Но я хочу сразу сказать, что мне лично было приятно участвовать с нашей командой! Мы хорошо сработались и я с удовольствием поучаствую в следующем году. Ниже я расскажу также о весёлых моментах в конкурсе :)
Задание
Итак, во время прочтения задания мы сразу и обрадовались, и обеспокоились :) Я, в общем-то, правильно предсказал то, что нас ждёт. До конкурса на каналах Jabber и IRC много говорилось об аэрокосмической теме и о времени 13:00:16. Окончательно раскусить оргов так и не смогли. Мне было ясно следующее: форматы времени и вообще точное время будут играть большую роль (про важность дискретного времени мы вспомнили, к сожалению, слишком поздно). Другой моей догадкой была очередная виртуальная машина (VM), которая обеспечит независимость от платформы: орги слишком уклончиво отвечали на вопрос о том, как надо было отправлять результаты.
В самом начале конкурса выяснилось, что 1995-06-29T13:00:16 (часовой пояс?) — это время первой стыковки шаттла и станции «Мир». Управлять спутниками — это звучало весело :) Но мы сразу стали опасаться сложностей с VM: Jkff вычитал что-то про машинные инструкции, записывающие результат в память по адресу инструкции, и мы стали думать про самомодифицирующийся код и пр. В реальности всё оказалось очень просто. VM была с гарвардской архитектурой: память команд и данных у неё была раздельная. К тому же позднее нам стало понятно, что платформонезависимость была единственной целью включения VM в задание. Способ и эффективность реализации VM на решение почти что не влияли. Мы же напрасно уделили этому внимание, в тактике нашей команды постепенно начала накапливаться ошибка подхода к заданию.
Интерфейс ctl-sim
Почти с самого начала мы стали решать задачу в духе Unix. Вырисовывалась пара взаимодействующих программ: sim — симулятор, выполняемый на VM, и ctl — контроллер, ведущий симулируемый спутник. В ходе небольшого обсуждения я изложил своё видение взаимодействия этой пары. ctl и sim будут обмениваться командами чтения/записи в порты IO через неименованные каналы ОС. Формат обмена FMT было решено сделать текстовым, что давало нам читаемый и отлаживаемый интерфейс в стиле Unix. Например, имея готовую трассу команд на вход симулятора, вывод можно было, в принципе, увидеть картинку полёта спутников следующим образом:
$ cat trace.fmt | sim | vis
В таком же стиле можно было вручную вести спутник (номеров портов было мало и мы помнили их наизусть):
$ sim
0 0x3e80=1002
0 0x0=0 0x1=10000 0x2=-6352278.930 0x3=6361717.566 0x4=21082000
1
1 0x0=0 0x1=10000 0x2=-6347554.360 0x3=6366431.626 0x4=21082000
2 0x2=5000
2 0x0=0 0x1=5000 0x2=-6345326.291 0x3=6371142.177 0x4=21082000
По общему мнению, интерфейс взаимодействия контроллеров и симуляторов получился хороший, он позволил нам писать их на разных языках: Python, Haskell, C++ и Java (на ней был написан визуализатор). Однако сразу же надо высказаться критически об этом интерфейсе. Он способствовал написанию контроллеров на разных языках, что уменьшало шансы совместной работы над кодом и повторного использования кода в следующих задачах. Мы обезопасили себя от проблем с отладкой VM, нашего физического эмулятора и разных контроллеров. Однако это дало начало ненужному в таком коротком конкурсе языковому разброду. К тому же отладка интерфейса обошлась нам в 4 человеко-часа. Но в целом, всё же, интерфейс был положительным моментом.
С упомянутой отладкой интерфейса отдельная история. Несмотря на то, что программы взаимодействовали через каналы (pipes), они были крайне сильно связаны. Контроллер ожидал ответа от симулятора после каждой своей команды. Фактически, это был протокол с обменом сообщениями «запрос-ответ». А для этого только каналов недостаточно, нужно организовать подчиенение процессов. Эта типичная схема описана у Реймонда в “The Art of Unix Programming”. Мы решили оставить всё на каналах и просто сделать программу-драйвер fmtdump, которая связывала каналы двух программ крест-на-крест и заодно писала логи их взаимодействия в общем формате FMT. Всё бы хорошо, да только мы не задумывались над обязательностью flush(2) после write(2) и над тем, что строки текствого протокола мы не имеем права буферизовать при чтении: строку неизвестной длины без блокировки можно читать только по одному байту за раз.
После того, как минут за 30 всё это было осознано, началась борьба по отключению буферизации ввода во всех языках, на которых писались контроллеры. В Python это оказалось сделать на удивление сложно. Способ, описанный в документации, не работал и одно время мне пришлось использовать свою функцию чтения строки по байту. Позже правильный способ всё-таки был найден: открыть файл в бинарном режиме, указать размер буфера 0 и читать строку через readline, а не итерироваться по строкам файла. В других вариантах буферизация всё равно происходит.
Вот с этими техническими деталями VM и интерфейса симулятора к контроллеру мы провозились до середины субботы. Сама VM получилась тоже интересно, см. блог Jkff. Напомню, что для получения симулятора использовалось взаимодействие языков байткода VM, Python, Haskell и C++.
Все пишут контроллеры
Закопавшись с VM, мы сели за саму задачу, т. е. за контроллеры, только к полудню субботы. До этого я писал транслятор байткода в Haskell-ассемблер VM, а также драйвер пары контроллер-симулятор fmtdump, Kerzum писал компилятор sim с Haskell-ассемблера в C++, Jkff писал визуализацию выходного лога в формате FMT, а Cfr и Incubos писали альтернативный sim, моделирующий мир по формулам из задания.
Cfr уже без Incubos (который пошёл спать) начал писать свой контроллер на Haskell, однако скоро от его кода ответвился Kerzum, который решил попробовать свою реализацию. Параллельно Jkff начал ещё один контроллер на Python. Я занимался скриптами сборки всех проектов и небольшими исправлениями к fmtdump. Не очень понятно, что мешало всем вместе вначале решить задачу математически и алгоритмически. Наверное, всем просто хотелось уже наконец попробовать подойти к задачам практически: симулятор и драйвер были как раз готовы. Начавшееся разделение хаскеловских и питоновских контроллеров в результате затормозит нас на довольно большое время, хотя и обезопасит от отдельных неудач с конкретными контроллерами. Как и в случае с интерфейсом контроллер-симулятор, мы опять подошли к проблеме слишком защищёно.
Вечером в субботу свой контроллер начал и Incubos, взяв за основу мои наброски (об этом речь ниже). Так что в воскресенье практически все работали над контроллерами, но своими, а не общим. Знания тоже локализовались в коде и обмен ими шёл не особо эффективно.
Эволюция контроллеров на Python
После того, как к полудню субботы я решил вопросы с драйвером, я взялся за контроллеры. Однако вместо того, чтобы познакомиться наконец детально с физикой задачи (а не только с VM и форматами), я решил придумать хороший интерфейс контроллеров на Python, чтобы их было легко писать и комбинировать.
Утром я написал для ребят простой парсер формата FMT на Python и дёрнул меня тогда чёрт сделать его интерфейс потоковым! Возможно, это была главная моя ошибка за весь конкурс. Контроллер представлялся в этом первом интерфейсе функцией типа Iterable(Ports) -> Iterable(Ports). Чуть позже, думая об универсальном интерфейсе, я написал вспомогательную функцию buffered :: ([Ports] -> Ports), int -> (Iterable(Ports) -> Iterable(Ports)), которая позволяла работать с одним шагом симуляции, но иметь буфер портов за предыдущие ходы. Тогда мне показалось, что такая потоковая обработка наряду с буферизацией будет удобной для решения всех задач. Но я почему-то забыл с самого начала подумать про суть обмена данными с симулятором и про композицию алгоритмов управления в контроллерах. С таким интерфейсом это получалось крайне неестественно.
Что же было естественным способом управления симулятором? Старое доброе ООП. Наша задача сводится к синхронному обмену сообщениями (message passing) между процессами с локальным изменяемым состоянием.
К сожалению, Jkff и Incubos уже вовсю писали свой код на потоковом интерфейсе (код Incubos особенно критично зависел от этого), а ОО-интерфейс я придумал только днём в воскресенье, после того, как, наконец, выспался после 36-часового бодрствования.
Новый интерфейс заключался вот в чём. Есть интерфейс ООП Sim с единственными методом: interact :: Ports -> Ports, который в ответ на управляющие сигналы в порты ввода выдаёт сигналы портов вывода. Всё очень банально! Зато сразу стало возможно делать следующие вещи: объединять контроллеры (процедуры аргумента Sim) последовательной композицией, организовывать внутри них конечные автоматы, вызывать внутри контроллеров другие контроллеры (вложенные конечные автоматы), делать классы-прокси для дампа логов взаимодействия, запускать альтернативный симулятор внутри процесса для предсказания физики и пр.
Посетила бы нас эта простая мысль раньше — наш код был бы повторно используемым, более выразительным и наверняка содержал бы меньше ошибок.
Последнее улучшение интерфейса контроллера состояло в том, что специальный прокси TraceSim добавлял поле trace :: [(Ports, Ports)] с историей команд ввода-вывода, что нужно почти всем алгоритмам.
Физика и геометрия
Отдельной темой стоят наши обсуждения физики и геометрии задачи. К сожалению, в субботу их было очень мало, но зато они были интересные :) и в воскресенье они позволили нам прийти, фактически, к решению задачи. Особенно эффективными мне показались обсуждения физики у доски, в которых участвовали я, Jkff и пару раз Cfr с Kerzum. На мой взгляд, примерно так и стоило бы решать задачу: обсуждать и вместе писать алгоритмы, а не распределять усилия на несвязанный код. Хоть в итоге именно распределение позволило набрать нам наши очки, но оно и помешало набрать нам больше.
Надо заметить, что ещё в субботу вечером у нас был код, выводящий спутники первых задач на нужную орбиту, но нам упорно не давали очков. Оказалось, мы невнимательно читали задание, допустили несколько опечаток в расчётах, выводили данные со значительной потерей точности, также совсем забыли, что мы летаем в дискретном времени с шагом 1 сек и скоростью порядка 10 км/сек. Это значит, что без учёта дискретизации (например, параллельным расчётом по непрерывной формуле и дискретной симуляцией с коррекцией после этого) мы не могли достичь нужной точности в орбитальных переходах.
В воскресенье часть этих проблем была решена и при помощи многих подхаков мы решили все задачи, кроме последней, главной. До неё мы, к сожалению, не успели дойти из-за нехватки времени и неизвестного бага в симуляторе, проявлявшегося только на этой задаче.
Причины неуспеха
По моему мнению, нам помешало следующее:
- Не пытались писать алгоритмы контроллеров вместе
- Не провели своевременный поиск доков по предметной области
- Долго не вспоминали о дискретном времени
- Писали код на разных языках, не думали о композиции алгоритмов
- Потеряли полдня на баг с выводом неточных чисел с плавающей точкой
- Плохо организовали математический код, допускали много опечаток
Что мне понравилось
Ну и после такого анализа хочу поделиться приятными впечатлениями :) Вот что было интересно:
- Мы запрограммили классный многоязыковой процесс получения симулятора
- Картинка concept map на доске в самом начале позволила быстро найти связи, которые ещё никто не понимал
- Unix-интерфейсы рулят! Мы игрались с интерфейсом
ctl-sim, рисуя бешеные трассы, отлавливая баги во взаимодействии: всё было текстовым и простым - Мы выпили в ходе обсуждения в первую ночь кучу кофе и продержались где-то до 20 часов субботы
- У нас были интересные обсуждения у доски. Было здорово подсказывать, ловить баги друг друга, придумывать новые подходы :)
- Система управления версиями Mercurial всё время рулила
- Мы хотели и продумывали (но так и не сделали) интерактивный контроллер в визуализаторе, чтобы играться в спутник с клавиатуры
Цифры
Ну и совсем под конец несколько цифр:
- 219 ревизий в Mercurial
- 11 исполняемых программ
- 1701 строка на Python, 630 на C++, 475 на Java, 460 на Haskell, 171 на C, 111 на make, 67 на sh
- На момент заморозки таблицы 84 место, 1654 очка (до отправки последних результатов)
Спасибо членам команды за классно проведённое время! :)
Tagged: 2009, c++, haskell, icfpc, java, python, spb-archlinux
- 01 Июл 22:41
