dastapov: (Default)
[personal profile] dastapov
Продолжение рассказа про ICFPC-2007. Начало смотри тут, а окончание - тут.


Глава четвертая, в которой (в полном соответствии с классикой) наступает день Д, час Ч и полная Ж


Мы сразу договорились, что для хранения DNA будем использовать либо Data.Sequence (2-3 fingertree из "аминикислотных оснований"), либо Data.ByteString.Lazy (односвязный список из строк произвольной длины, который "снаружи" выглядит как одна неразрывная строка). Обе структуры данных обещали добавление и skip-ы за логарифмическое время. Мы с jethr0 решили использовать Sequence, а Lemmih стал писать свою версию с использованием ByteString. Нам бы подумать и пойти на шаг дальше, создав что-то вроде "class DNA a where append: a -> a-> a ; isPrefix a -> a -> Bool ; ..." и сделав ByteString и Sequence членами этого класса. Тогда бы мы могли с легкостью выбирать, какое из представлений DNA использовать в нашем коде.. Но тогда об этом никто не подумал ...

В 17:10 (EET), через четыре часа после начала соревнования, в нашем репозитории начал появляться первый код. В 18:00 у нас уже был "скелет" GUI, транслятор RNA в/из ImageOps, командно-строчный рендерер RNA->ImageOps->PNM, реализующий все простые ImageOps (кроме flood fill, clip и line) и начатки транслятора DNA->RNA.

Где-то в 18:30 мы с jethr0 стали спотыкаться о то, что спецификация давала алгоритм трансляции DNA в RNA в виде не очень аккуратно структурированой императивной программы, написанной в процедурном стиле. В частности, в деле фигурировала некая процедура "finish()", которую могли вызвать в любой момент и которая должна была немедленно прекратить весь процесс трансляции ДНК и выдать на-гора накопленное в процессе РНК. Фактически, процедура "finish()", в котором ее использовали организаторы, была прямым аналогом оператора goto. Кроме того, все циклы в спецификации были бесконечными, а выход из них бы по "return".

Лирическое отступление:


Jethr0 предлагал использовать Error monad для того, чтобы закодировать finish и return как исключения, а я предлагал для тех же самых целей использовать Maybe monad. Поскольку мы с jethr0 писали код в gobby(*), то к нашей дискусии подключился Cale и предложил нас помирить и сделать код в два раза короче и понятнее с помощью monad transformers. К этому моменту у нас уже было где-то 75% нужного кода (пока еще не тестированного).

*) gobby - это онлайновый многопользовательский редактор, чтобы проникнуться идеей - смотрите этот скринкаст

Мы с jethr0 уселись наблюдать за работой мастера, а Cale засучил рукава. К сожалению, что мой код, что код jethr0 был достаточно "грязным" и не-абстрактным, в расчете на дальнейший рефакторинг и наведение красоты. В результате Cale в нем заблудился, а все наши попытки ему помочь (параллельными исправлениями кода и полезными советами) только ухудшали дело. В результате, когда где-то между 19:30 и 20:00 компилятор выдал мне такую ошибку:

/home/adept/devel/icfpc2007/work/src/DNA.hs:62:36:
Couldn't match expected type `Either () a'
against inferred type `a' (a rigid variable)
`a' is bound by the type signature for `runDNA'
at /home/adept/devel/icfp2007/work/src/DNA.hs:53:19
Expected type: ErrorT () (ContT (Either () a) (State Global)) a1
Inferred type: ErrorT () (ContT a (State Global)) a
In the first argument of `runErrorT', namely `x'
In the first argument of `runContT', namely `(runErrorT x)'
Failed, modules loaded: Types, DNA.IO, DNA.Compiler.

, я понял, что дело пахнет керосином.

Cale и jethr0 были уверены, что "еще чуть-чуть - и всё", я уже ничего не правил и просто наблюдал за процессом, и к 20:30 мы благополучно "зарисовали себя в угол". А все потому, что некогда было остановится и "наточить пилу" - ведь "надо ж пилить!"

В 20:40 Lemmih коммитит первую версию своего кода, которая где-то глючит и не проходит self-check и и начинает обписывать ее тестами. Выясняется, что примеры, сопровождающие спецификацию, слишком простые и не подходят для адекватного тестирования, а других у нас пока нет. Vincenz и psykotic начинают объединять свой код, чтобы получить GUI, которое умеет рендерить RNA в картинку и показывать процесс "в динамике".

В 21:00 просыпается zeeeee и в 21:30 мы собираемся на первую "статусную встречу". Очень быстро выясняется, что самый удобный формат - это сразу писать в gobby протокол обсуждения. Ведущий пишет: "Текущий статус:", а все остальные начинают снизу дописывать информацию про свои куски. Затем ведущий пишет: "Проблемы и открытые вопросы:", и каждый вносит свою часть, причем иногда бывало так, что кто-то еще дописывает вопрос, а другие уже пишут под ним ответ на него и т.п. Наблюдать, как семь человек одновременно пишут текст примерно так же увлекательно, как смотреть на муравьев, которые тянут кусок сахара весом в несколько раз больше их.

Выясняется, что у нас уже есть цепочка RNA->ImageOp->PNG и RNA->ImageOp->GUI->PNG, в которой все работает, но безбожно тормозят flood fill и combine. Кроме того, у нас есть две неработающие реализации DNA->RNA: одна написана Lemmih-ом и глючит, вторая написана мной, jethr0 и Cale, и лежит на операционном столе кишками наружу.

Соответственно, мы планируем:
1)Довести до ума хотя бы одну версию DNA->RNA в ближайшие 2-3 часа и с ее помощью нагенерировать тестовых данных для отладки другой версии или вообще объединить их код
2)Добавить в GUI несколько опций пошаговой отрисовки RNA
3)Ускорить процесс отрисовки путем профилирования и оптимизации узких мест
4)Понять, как при помощи префиксов "исключать" или "добавлять" RNA в получающийся при обработки "просто ДНК" поток.

В 22:30 мы заканчиваем обсуждать все насущные проблемы и продолжаем кодить дальше. Поскольку Cale и jethr0 продолжают пытаться "оживить Франкенштейна", я дописываю пару мелких вещей к GUI, попутно знакомясь с gtk2hs.

В 23:30 Lemmih говорит, что его транслятор DNA->RNA похоже работает, но безумно тормозит и жрет невероятное кол-во памяти. Причина, судя по всему, фрагментация ByteString-а в процессе многочисленных "разрезаний" и append-ов. Почему никто не додумался до очевидного решения - периодического копирования фрагментированного ByteString-а в новый, состоящий из одной части - совершенно непонятно. Глядишь, могли бы в течении часа получить быстрый работающий DNA-to-RNA.

Cale и jethr0 бросают попытки оживить наш код. Jethr0, в принципе, считает, что еще можно откатится на код, который мы имели в 18:30 и довести его до ума, а Cale считает, что перспективнее разобраться с тем, что сделал Lemmih и дальше развить его в нужном направлении.

Lemmih берет тайм-аут, мы с Cale пытаемся зарефакторить его код так, чтобы он использовал ByteString, vincenz и psykotic дописывают GUI, jethr0 возится со второй версией DNA->RNA, а zeeeee читает код и логи, пытаясь наверстать то, что он "проспал".

В 01:00 код DNA-to-RNA, основаный на версии Lemmih-а и переделаный для использования Sequence, начинает запускаться. Он работает на порядок быстрее, чем с ByteString, но не проходит до конца self-check. Получается, что прошло уже 12 часов, а у нас еще нет работающего framework-а по трансляции DNA в картинку :( Zeeeee говорит, что он постарается с этим разобраться до наступления у нас утра, и я иду спать. Кажется, vincenz, Cale и jethr0 делают то же самое.

Глава пятая, в которой проходят сутки и заканчивается lightning division


21 июля, 8:15 EET (второй календарный день соревнований)

Я просыпаюсь, иду читать backlog и вытаскивать свежие commit-ы. В IRC тихо, спят все, кроме zeeeee. На вопрос о том, как у нас дела, я получаю достаточно обескураживающий ответ: понять, почему версия Lemmih-а не проходит self-check, не вышло. Поэтому zeeeee набросал свое решение DNA->RNA на питоне "с чистого листа", надеясь с его помощью получить отладочные данные для отлова багов в коде Lemmih-а (или наоборот).

Однако морская поговорка не зря гласит, что надо брать с собой либо один компас, либо сразу три - получилось, что обе версии - и написанная на haskell, и написанная на python - не проходят self-check, причем "валятся" в разных местах.

До утренней "статусной встречи" еще есть время и я трачу его на изучение кода GUI и свежевытянутых патчей.

21 июля, 10:00 EET, утренняя статусная встреча
В онлайне только я, zeeeee, vincenz и psykotic - остальные спят. Выясняется, что у нас уже есть навороченный GUI, который умеет загружать RNA из файла; сохранять RNA в файл; показывать ImageOps, из которых состоит RNA и давать их править; сохранять ImageOps в файл и загружать их; рисовать картинку пошагово или сразу всю; сохранять PNG в файл. Правда, flood fill периодически "залипает" на заливке больших зон, но при отрисовке стандартного source.png этот баг "не стреляет". Вот чего у нас нет - так это работающего DNA->RNA :( А ведь прошли уже почти полные сутки.

Становится понятно, что в lightning division (соревнование-в-соревновании, на основании результатов первых суток) нам ловить нечего, т.к. за ближайшие три часа мы врядли родим что-то достойное.

Vincenz и zeeeee отправляются ковырять DNA->RNA (обе версии), psykotic до-отлаживает рендерер, а я дописываю пару мелких фич в GUI ("step N instructions", "step to next `line' instruction" и т.п.) и экспериментирую с ними.

В процессе экспериментов я вижу, что куцый кусок RNA, которое нам пока что удалось получить, начинается с команд, рисующих линиями на экране текст, который затем заливается поверх черным цветом и на этом фоне уже рисуется "грустный Эндо". А текст этот подозрительно похож на кусок DNA: "IIPIFFCPICFPPICIICCIICIPPPFIIC". К сожалению, из-за отсутствия работающего транслятора DNA->RNA я не могу проверить, что получается в результате дописывания этого префикса к ДНК. Я пытаюсь послать этот префикс на сайт организаторов как наше решение, надеясь, что мне покажут получившуюся картинку, но увы :( Картинка показывается только для самого лучшего на данный момент префикса, а им является self-check prefix (взятый из спецификации), который мы заслали еще вчера.

Я создаю в "протоколе встречи" раздел "Conspiracy theory" и предлагаю команде обратить внимание на этот "скрытый" префикс и на пункт 4 из списка на второй странице спецификации: "ДНК пришельца создано разумными существами и может содержать в себе разнообразные послания". Возможно, нам стоит обратить на это внимание, тем более, что одно из таких посланий (рисуемый префикс) мы только что нашли?

Моя идея не находит поддержки. Все считают, что это - не более чем развешивание лапши на ушах доверчивых участников.

В результате какое-то время все продолжают заниматься тем, чем занимались раньше. Я понимаю, что в DNA->RNA и так копается слишком много народа, и пишу скрипт, сравнивающий два PNG и вычисляющий разницу между ними - по этой норме организаторы оценивали решение, чем твоя картинка ближе к target.png - тем лучше.

Затем я пишу мелкие haskel-скрипты для генерации ImageOps, на которых мы проверяем быстродействие GUI - например, зарисовка квадрата 600x600 линиями по спирали, или куча fill-ов и clip-ов, и т.д. и т.п. В результате где-то до 15:00 я занят возней с GUI, экспериментами с чужим кодом, отловом мелких багов в этом коде и вычисткой из репозитория мертвого кода и следов неудавшихся экспериментов в полной уверенности, что "еще чуть-чуть, и у нас будет DNA->RNA".

15:00 - DNA->RNA еще нет. Точнее, что-то есть, но оно работает со скоростью 200 итераций в секунду, так что завершения 1.8 млн итераций мы до окончания соревнования не дождемся. Vincenz форкает эту версию в отдельную ветку и начинает ее ковырять отдельно от всех. И в 16:00 нормального кода тоже еще нет. И в 17:00 - тоже нет (я за это время успеваю отловить, кажется, всех блох в имеющемся в репозитории коде). Cale, который в это время рассматривает endo.dna в hex-редакторе, говорит, что где-то в начале есть зона, в которой, кажется, ascii art-ом написано "Auchtung! Portable Network Graphics follows!". Ну, понятное дело - генерится-то в результате PNG ... Я пишу себе в todo "посмотреть на это своими глазами" и ... забываю.

А в это время на Scoreboard-е видно, что целая группа команд идет, похоже, по одному и тому же пути - все заслали префикс длиной в 28 символов и получили одинаковый результат. Что это? Читеры? Или они независимо нашли один и тот же кусок информации? Надо было остановиться и подумать над этим, но мы были слишком увлечены.

В 17:00 я иду проветриться с Юлькой и ребенком (как, я еще не писал, что прогулки по часу каждый день - рулят неимоверно?) и в процессе обсуждения с ней все больше уверяюсь в том, что мы идем по какому-то неправильному пути. По приходу домой я начинаю поднимать на IRC бучу по поводу того, что всем надо все бросать и срочно "всем колхозом" наваливаться на DNA->RNA, каким угодно образом доводить любую реализацию до ума, потом доводить ее до того, чтобы она была приемлемо быстрая, и уже потом заниматься всем остальным (а мы за это время успели нафигачить немерянно кода "про запас").

Развивается бурная дискуссия, и вся работа останавливается. Вечерняя статусная встреча срывается, т.к. мнения делятся примерно пополам - половина согласна со мной и считает, что не о чем совещаться, пока мы не получим DNA->RNA, а вторая половина считает, что можно двигаться дальше в прежнем стиле, и встречу провести все-таки надо и планы на будущее обсудить надо. Я продолжаю всячески настаивать, и, похоже, народ понимает, что мне "проще отдаться, чем объяснить, почему нельзя".

В результате исходники открываются в gobby, мы их читаем и правим минимум вчетвером, и к 23:00 у нас есть работающее решение, которое:
1)Достаточно быстрое. 20-30К итераций в секунду.
2)Ест приемлемо памяти (200-300 Мб на генерации selfcheck)
3)Проходит self-check

Ура! Не прошло и пол-соревнования, как мы реализовали необходимый минимум ... Мы вкручиваем полученный код в GUI и командно-строчную обвязку, и я ухожу спать "на самом интересном месте".


Читать начало или окончание.

(no subject)

Date: 2007-07-30 05:55 pm (UTC)
From: [identity profile] i-love-python.livejournal.com
я вот так и не догнал. что это за lightning division? это каждый год такое или только на этом соревновании?

(no subject)

Date: 2007-07-30 06:01 pm (UTC)
From: [identity profile] http://users.livejournal.com/_adept_/
Это стандартная тема, бывает каждый год. Идея в том, что функция оценки результата редко бывает бинарной: "решил/не решил". Как правило, есть четкий способ посчитать достижения любой команды в любой момент времени. Соответственно, lightning division - это отдельный приз тем, кто больше всего сделал за первые сутки.

Profile

dastapov: (Default)
Dmitry Astapov

July 2017

M T W T F S S
     12
3456789
1011 1213141516
17181920212223
24252627282930
31      

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags