Андрей Власовских

Блог Андрея Власовских

Команда spb-archlinux на ICFPC 2009

13 комментариев

Никак не возьму в привычку чаще писать в блог. Но на этот раз повод действительно есть. Наша команда 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 на решение почти что не влияли. Мы же напрасно уделили этому внимание, в тактике нашей команды постепенно начала накапливаться ошибка подхода к заданию.

Интерфейс ctlsim

Почти с самого начала мы стали решать задачу в духе 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-интерфейсы рулят! Мы игрались с интерфейсом ctlsim, рисуя бешеные трассы, отлавливая баги во взаимодействии: всё было текстовым и простым
  • Мы выпили в ходе обсуждения в первую ночь кучу кофе и продержались где-то до 20 часов субботы
  • У нас были интересные обсуждения у доски. Было здорово подсказывать, ловить баги друг друга, придумывать новые подходы :)
  • Система управления версиями Mercurial всё время рулила
  • Мы хотели и продумывали (но так и не сделали) интерактивный контроллер в визуализаторе, чтобы играться в спутник с клавиатуры

Цифры

Ну и совсем под конец несколько цифр:

  • 219 ревизий в Mercurial
  • 11 исполняемых программ
  • 1701 строка на Python, 630 на C++, 475 на Java, 460 на Haskell, 171 на C, 111 на make, 67 на sh
  • На момент заморозки таблицы 84 место, 1654 очка (до отправки последних результатов)

Спасибо членам команды за классно проведённое время! :)

Реклама

Written by vlan

2009-07-02 в 01:41

Опубликовано в Uncategorized

Tagged with , , , , , ,

комментариев 13

Subscribe to comments with RSS.

  1. > Картинка concept map на доске в самом начале позволила быстро найти связи, которые ещё никто не понимал

    Э-э-э, можно этот пункт подробнее? А то в тексте ни слова не сказано об этом.

    > Мы выпили в ходе обсуждения в первую ночь кучу кофе и продержались где-то до 20 часов субботы

    По-моему это минус, а не плюс :)

  2. @Murkt Взяв свеженькую распечатку задания, мы стали рисовать на доске карту связи понятий, что позволило нам быстро понять, чего хотят от нас орги и какие взаимодействующие есть в задании. К сожалению, никаких фоток с конкурса у нас нет, но картинка давала хорошее представление.

    Про кофе: не спать и выбиваться из режима плохо, а вот выпить кучу вкусного кофе — хорошо :)

    vlasovskikh

    2009-07-02 at 13:13

  3. Здорово!

    У меня пара вопросов:
    1. Можешь ли дать пару ссылок на блоги/ресурсы по юникс-ориентированному программированию?
    2. Пробовал ли ты git и чем он лучше/хуже mercurial?
    3. А сколько человек должно было быть в такой команде и кто это контролировал? =)

    jetbird

    2009-07-03 at 12:10

  4. @jetbird Я могу порекомендовать книги. Одна из них в open source: это та самая “The Art of Unix Programming”, ссылка на которую в самой записи. Книга скорее о подходе, о традициях, не руководство. Зато местами весёлая :) Потом, конечно же, книги Кернигана и Пайка: «Unix. Программное окружение», «Практика программирования». Первую я ещё не читал, но зная авторов и слыша много отзывов, могу рекомендовать. А вот «Практика» отличнейшая вещь!

    Я пробовал git совсем немного. Мне не очень понравилось, что там такая куча команд, деление на низко- и высокоуровневые команды и пр. В hg очень легко составить себе чёткую концептуальную модель его работы, чтобы его поведение стало для тебя очень предсказуемым.

    В этом году не было ограничений на число участников. Но тут, видимо, не числом, а умением. Есть команды и из одного человека, которые занимают очень высокие места. Задача не распараллеливается на очень много мозгов.

    vlasovskikh

    2009-07-03 at 12:22

  5. Да, удалось ли победить буферизацию? У меня с этим также проблемы были: есть прибор, который раз в 10 мин. выдает в последовательный порт примерно 0,8 килобайт текста. Из него требуется выдирать определенные куски, записываемые в отдельные файлы. Было решено поступать следующим образом:

    $cat /dev/ttySx | ser2tlg | csplit (…)

    где ser2tlg — программа, написанная на flex + C. Проблема была в том, что размер буфера в пайпах составляет около 4 кб, и пока он не переполнится, ser2tlg входной информации не получает. В итоге, для того, чтобы получить первые данные приходилось ждать около часа. До сих пор не получилось это разрулить, переписал программу для вызова в таком виде:

    $./ser2files /dev/ttySx, которая напряую читает порт и напрямую же сохраняет файлы.

    jetbird

    2009-07-03 at 12:26

  6. @jetbird Если у тебя протокол с кадрами фиксированной длины (а не строками, как был у нас), то проблем вообще нет. Просто делаешь n = read(STDIN_FILENO, buf, sizeof(buf));. А поскольку read(2) может вернуть меньше данных, чем sizeof(buf), то надо написать свою readn, читающую n байтов. С другими форматами чуть сложнее, но тоже всегда есть решение. Просто строки нельзя буферизовать, если надо считать строго не более одной строки за раз.

    vlasovskikh

    2009-07-03 at 12:40

    • нет, там длина не фиксированная; раз в минуту приходят строки < 80 символов, раз в 10 минут — многострочные "абзацы". причем их длина также меняется.. нда, ну вот я пока что не знаю, что есть именованные пайпы, может быть, они могли бы помочь.

      jetbird

      2009-07-03 at 12:44

  7. @jetbird Не важно что это: сокет, файл или канал. Если данные неизвестного заранее размера с завершающим байтом, их нужно читать побайтово. Например, как описано у меня выше для Python.

    vlasovskikh

    2009-07-03 at 12:49

  8. @jetbird Про это можно почитать Снейдера «Эффективное программирование TCP/IP».

    vlasovskikh

    2009-07-03 at 12:51

  9. @incubos :)

    vlasovskikh

    2009-07-06 at 11:40


Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: