суббота, 4 августа 2012 г.

ICFP 2012

Подготовка.

В этом году наша команда ShallowEndians пополнилась новыми людьми. Как и в прошлом году участвовали Джей, Пол, Кирилл Т., Кирилл М. и я. Но к нам ещё присоединились Гена и Млош. Также было решено работать в офисе, но в этом году не было свободных офисов и мы поселились в небольшом конференц зале.

Кирилл Т. создал образ дебиана, а Кирилл М. настроил меркуриал на своем амазоновском сервере. В этом году решили попробовать писать на одном языке. И им должен был стать C++.

До этого самого события мы ещё просто встретились что бы познакомится и просто обсудить предстоящее событие. На встречу я тоже опоздал;)

В пятницу мы договорились собраться в 5 утра в офисе и обсудить задачу. Среди нас только Джей был готов взять отгул на пятницу, что бы посвятить время icfp. Так что по плану мы должны были собраться после работы в 5 вечера.

В этом году я подошел к icfp не совсем в форме. Хоть и приехал с отпуска за две недели до, но ха это время эффект отпуска как рукой сняло. К тому же в четверг меня подняли в 5 утра - у нас были проблемы в одном из кластеров. Хоть фронтэнд и переключился на запасной кластер, но это надо было расследовать. В итоге весь четверг убил на это. А в пятницу в 3 утра опять подняли. На этот раз - это было ложное срабатывание вызванное инцидентом в четверг.

День первый.

По вышеизложенным причинам я не смог присоединится к комрадам в 5 утра. Но я успел прочесть задачу и отослать несколько идей которые появились:

  • важно сохранять текущий лучший результат и по SIGINT выводить его в консоль и выходить. Лучше не ждать ещё 10 секунд, так можно схлопотать SIGKILL.
  • большие карты решить будет сложно, надо собрать все лямбды локально идти к следующей далекой лямбде.
  • A* кажется хорошим строительным блоком для других стратегий.
  • интерактивная тулза будет очень важна для анализа решений и отладки алгоритма
  • Что бы определить регионы которые надо посещать надо воспользоваться алгоритмом кластеризации

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

Я присоединился к команде в 5 вечера. Милоша не было, а остальные уже были в зале. Работа кипела и по началу я даже не знал чем заняться. Скачал репу и скомпилил проект. Почитал уже написанный код. Почитал ещё раз задание. В общем все были в работе. И особо отрываться не хотели.

В данный этап в основном кодили Кирил М. и Джей. Кирил работал над BFS, Джей над симулятором. Остальные обдумывали задачу. Придумывали разные сложные карты, пытались определить алгоритмы которые могут пригодится.

Над идеями типа нейронных сетей мы посмеялись, но не приняли всерьёз. Камрады сказали что отказались от A* потому что, по описанию, он плохо работает на динамических картах. Была хорошая идея заключавшаяся в том, что бы разбить алгоритм на множество простых решений - набор предикат-решение опрашивался бы на каждом ходу. Если бы предикат возвращал true, выполнялось бы решение. В этом случае мы могли бы иметь общий алгоритм, который работал бы в большинстве случаев и набор захардкоженых решений для очень сложных случаев.

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

Про молниеносный раунд никто даже и не заикался. Участие в нем не представлялось возможным.

В общем помозговали немного. Идей было море, но вот времени на их реализацию не очень. Я был уже готов писать код. Не хотел пересекаться с тем что уже идет в разработке. Я задал вопрос комрадам - "что делать то?". На что получил ответ, что когда будет готов BFS, надо будет как то ходить от региона к региону. Вот этим я и занялся.

Я ещё раз прочитал статьи про BFS и A* в википедии. Все же верил, что на динамических картах A* должен работать. И я решил его реализовать. Основная идея была в том, что бы хранить в каждой ячейке карты саму карту, которая бы предоставляла состояние которое будет после того как мы туда доберемся. Эвристика была простой - расстояние + прохождение по земле - пенальти +1, иначе - пенальти 0.

В общем около 11 вечера у меня уже был алгоритм почти готов - путь находился, но в бектрекинге у меня был баг. Кирилл М. решил пойти домой, ну и я тоже пошел спать. Правда придя домой решил добить A*. Нашел багу и за минут 10 сделал dummysolver, программу которая берет лямбды, сортирует по удалению, пытается пройти к одной лямбде (сперва ближней, потом далее по расстоянию), дальше повторяется. В общем я обрадовался. До конца молниеносного раунда оставалось 4 часа и был шанс засабмитить. Но потом я нашел баг, что робот не умерает если по нему шарахнет камень. С таким багом алгоритм поиска пути выдавал фатальный вариант и робот умерал. Я огорчился и лег спать.

День второй.

Утро субботы началось не очень приятно. Оказалось что мой код не компилируется у большинства людей. Я использовал gcc 4.6, а некоторые - gcc 4.4 в котором не было поддержки auto, некоторые Visual Studio, в которой не было поддержки новому for (for(auto & i : container) {}), у некоторых были проблемы с std::unique_ptr. Немного подумали и самым простым было выпилить новый стандарт со всего кода. На это ушло около часа. Неблагодарная работа. Код стал менее читабельным.

Я объяснил как сделал A*. Рассказал, что хочу ввести более сложные эвристики. Например пенальти за сдвиг камня. Гена проявил сомнения что он будет работать с эвристиками отличными от расстояния. Мы немного подискутировали на эту тему и я сел и написал новые эвристики. Теперь за проходжение сквозь лямбду не было пенальти, пустая ячейка - +1, земля - +3, земля, которая находится под камнем, давала +7 пенальти. И оно заработало. Причем очень даже неплохо.

Дальше я попросил Джея сделать статистику по падению камней. Каждый раз, когда один камень падал, она увеличивалась на 1. Я интегрировал в A* и он стал ещё лучше. Теперь к примеру если был короткий путь, но который сдвинет камень и он упадет на 10 клеточек вниз, получал более низкий приоритет, чем обходной путь, который не тронет камни. Но если выхода не было, то камни двигались.

У Кирилла уже почти был готов BFS, он работал над тем что бы вырезать куски карты и перебирать варианты на меньшем участке. Джею организаторы не давали скучать своими обновлениями - водой, трамплинами и подобными пакостями. Милош работал над редактором, а Пол, Кирилл и Гена над исследованием алгоритмов. Они нашли статьи по сокобану и прочие алгоритмы и анализировали как их можно применить.

Я нашел проблему в моем алгоритме, робот загонял себя в тупик. Если над ним был камень, а по бокам стены - то он не мог продолжать двигаться. Я по началу начал запрещать двигаться к таким лямбдам, но это не дало ожидаемого результата. Алгоритм стал работать медленно, хотя и работал лучше.

Мне пришла идея использовать симуляцию отжига. Алгоритм был таков - находим первое решение. Запоминаем его. Дальше отрезаем 80% пути и делаем рандомное движение к любой лямбде. Дальше включаем алгоритм найти решение до конца. Получив несколько решений - выбираем лучшие. От них отрезаем 60% пути и продолжаем. Дойдя до 20%-го отрезания - возвращаемся к 80%. В общем этот алгоритм реализовывал некое подобие бектрекинга. Не настоящей бектрекинг, который мы хотели сделать, но первая быстрая версия. Стыдно говорить, но в начале я реализовал неправильно алгоритм. Делал по памяти. В начале отрезал 20%, потом 60%, потом 80%. То есть делал наоборот. Но быстро исправился.

Гена начал работать над высокоуровневыми стратегиями. А у Кирила был готов алгоритм и мы его начали комбинировать с моим. Идея была такова - если в округе есть лямбда - включать BFS, если нету - выбирать ближайшую лямбду и двигаться к ней, а дальше повторить. К тому же в качестве рандомного действия в симуляции отжига - мог включится BFS.

С одной стороны BFS давал хорошие результаты, но как и любой полный перебор - он был не очень быстр - что замедляло симуляцию отжига и уменьшало число популяций алгоритмов которые прорабатывались. Я немного уменьшил размер популяции что бы компенсировать. Результат был уже очень даже ничего.

Кирилл Т. нашел народные карты. Аж 1000 штук. И залил их в репозиторий. На очень больших картах наш dummysolver не очень шустро работал. На самой огромной я не дождался результата за одну минуту. Было над чем поработать.

Но мяньячить не стали, разошлись по домам часа в 4 утра. Джей все же остался, как мы выяснили по ночным коммитам. Он отрефакторил написанный код, что бы было легче продолжать разработку.

День третий.

Гена занялся реализацией кластеризации карты. Нашел библиотеку с кодом для Lin–Kernighan, и прикручевал её. Пол, хотя он и не знает C++, помогал реализовывать последние изменения от организаторов. Джей допилил интерфейс карты и оказалось, что мой A* не надо менять для поддержки трамплинов. Я надеялся на это, но все же было приятным сюрпризом. Кирилл Т. начал работу над тестами.

Кирилл М. оптимизировал BFS. Он придумал способ ускорить его получая лучший результат. На этапе когда память подходила к лимиту он отбрасывал часть решений. В итоге обрабатывалось больше хороших цепочек и получался лучше результат.

Я нашел проблему с тем, что A* не умеет двигаться назад. То есть ему не под силу подойти под камень убрав землю, отойти и подождать пока он упадет, а потом пойти дальше. Хотел решить эту проблему. Даже почти придумали как - убрать все камни, пройти к желаемой лямбде, дальше найти последний камень который мешает, предположить, что мы туда дойдем и включить там BFS, что бы найти путь сквозь камень. Дальше найти предыдущий камень и тд. Но к сожалению я так и не успел реализовать это.

Нам надо было ещё реализовать финальную программу, которую будем отсылать организаторам. Я начал с того, что заменил все std::cout на std::cerr, что бы если мы забудем закомментировать какой то логгинг, это не испортило нам решение. Также сделал хранитель решений, который бы обновлялся последний лучшим решением, а по SIGINT выводил его на экран и завершал программу. Также поддержал SIGABRT и SIGSEGV, на случай если произойдет ошибка, которую не сможем обработать. В этом случае тоже выводился лучший результат и завершалась программа.

Часам к 5 вечера и Пол и Милош нас покинули. А мы остались допиливать решение, исправлять краши, тестировать на разных картах.

Я также внес ещё рандомности в симуляцию отжига отрезая не 80%, а от 80 до 100, а потом не 60%, а от 60 до 80 и тд. Это тоже улучшило результаты.

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

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

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

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

А Кирилл, Гена и я остались до победного конца. Я занялся регистрацией и созданием финального бинарника. Кирилл скачал образ с сайта организаторов, а я установил его в Virtual Box и отработал создание архива с исходниками и финальным исполнительным файлом.

Кирилл успел сделать механихм отталкивания камня от лифта и мы игтегрировали его в финальное решение. Часа в 2 ночи, Гена был начал интеграцию кластеризации и приоретизации кластеров в осноной алгоритм. Я все ещё хотел сделать решение с проходом сквозь камни, но руки не дошли. Ещё пришлось повозится с Кириллом над интеграцией LKH библиотеки. Гена писал на виндовсе и хотя библиотека и была на C, у нас ушло достаточно времени что бы её скомпилить и слинковать с нашим решением на C++. К тому же там было много printf-ов. Я то думал что вычистил все std::cout, а про printf не подумал. Пришлось их комментировать или перенаправлять в STDERR. А дальше мы с Кириллом продолжили текстировать и исправлять баги.

Хоть Гена и старался успеть к 5 утра, но если бы и успел, было бы очень рискованно выкладывать не протестированное решение. Так что к сожалению не успели. А последний час шел очень быстро.

В 4:30 мы уже почти были готовы к заливке финальной версии. Где то в 4:45 я начал финальный билд. Кирилл ещё хотел включить небольшое изменение - включать BFS на всей карте если она не очень большая, а не на окне. Но получить билд уже было нереально. К тому же мы заметили регресию на одной из карте, где камень должен был быть отодвинут роботом, но этого не происходило. Но решено было заливать как есть.

Но я был на мобильном интернете. Остальные подключились к корпоративному интернету, но я не стал заморачиваться - для разработки хватало. Но тут интернет начал тупить. Было уже где то 4:55. Я плюнул - скинул билд на телефон и понес к Кириллу. Но почему то его ubunta не хотела монтировать телефон. Гена побежал на свой этаж за флешкой. Пришел где то в 4:58. Я быстро скинул файл. Кирилл открыл флешку, залил в google docs. Все вздохнули с облегчением. Но там надо было ещё нажать разшарить. Кирилл добавил организаторов, но не нажал на финальную кнопку. Мы это заметили - он нажал, все - файл ушел. За последние 5 минут получил не маленькую дозу адреналина;)

Послесловие.

Мне этот год понравился. Может даже больше чем предыдущий. Мы смогли писать на одном языке. И очень продуктивно взаимодействовали. Кирилл М. к примеру считает, что прошлый год был лучше. Но они немного разные были. В ICFP 2012 нам надо было именно реализовывать алгоритмы, а в прошлом году - придумывать их, а сама программа не была очень сложной.

Некоторые проблем мы решили с прошлого года, но все же было много и ошибок. К примеру вот несколько. Джей потратил много времени на мержи кода. У него не было нормальной утилиты как у других - KDiff3. По началу он использовал vimdiff, пока не перелез на винду. Нам надо было больше времени потратить на тесты и использовать их для нахождения оптимального алгоритма. Мы делали это на глазок. Так же мы не успели сделать много что хотели. Некоторые алгоритмы возможно были бы очень кстати, но руки не дошли до них.

Не смотря на проблемы, я все же считаю что мы молодцы. И неважно какое место мы получим. Мы уже получили массу удовольствия. Хотя это немного извращенное удовольствие. После окончания мы были изнеможены полностью. А в понедельник я ещё и пошел на работу, так как не мог пропустить этот день.

Всего было 270 команд. После первого раунда должно остаться 135. Я надеялся что мы попадем в 80, а может и в 60-ку. Кирилл М. дал прогноз, что мы все же пройдем в 2-й раунд, но еле-еле. После мы прочитали, что команда _adept_-а набрала свыше 6 миллионов на народных картах. Уже после окончания мы протестировали наш алгоритм, он набрал всего 1.3M.

К нашему удивлению в первом раунде мы, ShallowEndians, заняли 19-е место набрав 9877 очков. Я крайне обрадовался этому результату. Я все таки верил в нас. Но на 19 место даже не рассчитывал. Но посмотрим на 2-й раунд. Может это была случайности и среди 135 команд мы не попадем и в первые пол сотни. Кто знает.

понедельник, 27 июня 2011 г.

ICFP 2011 результаты

Объявили результаты первого рауна ICFP 2011. Мы с треском провалились заняв 74-е место из 199 комманд, которые засабмитили результат.

понедельник, 20 июня 2011 г.

ICFP 2011

День нулевой - начало

В четверг в пять часов вечера мы собрались прочитать и обсудить условия задачи. Нас было пятеро: Пол, Ждей, Кирил, Кирил и я. Вася должен был подключиться удаленно попоже, у него в Киеве была ещё ночь. Нашли свободный офис с четырьмя досками и начали разбираться. За первый час мы только успели немного понять условия задачи. Каждый читал и потом обсуждали правильно ли поняли какие то условия. Обсуждение вели на английском языке, что было не совсем просто. Но учитывая что только трое из нас разговаривали на русском - выхода не было.

Из языков мы планировали использовать C++ и возможно C#. Ещё подумывали о Python-е если понадобится. Забегая вперед скажу, что получилось совсем не так как ожидали. Мы ещё успели до этого установить виртуальные машины с Debian, создать репозиторий на Bitbucket и создать сайт на amazon, с которого сабмитили результат. Как бы мы не любили git, но бесплатного сервиса с закрытым доступом мы не нашли. А bitbucket.org предоставляет возможность использовать Mercurial для закрытыех проектов.

Что бы разобраться с задачей я решил написать прототип эмулятора логики LTG на lua. Этот язык я знаю хорошо и за счет своей простоты и динамической типизации позволяет писать код очень быстро. Через час у меня уже работала большая часть комманд и можно было прогнать тесты указаные в примере к задаче. Появилось более полное понимание задачи. В четверг решили долго не засиживаться и пойти по домам - так что разошлись около 8-9 часов.

Мы с Кирилом ещё пошли дернуть пивка и пообсуждать задачу. Были идеи что функции в условии - слишком нискоуровневые, А надо придумать высокоуровневый язык который уже преобразовывать в нужные компоненты. Что то типа асемблера против С++. Ещё Кирил предложил использовать генетический алгоритм, что бы создавать стратегии. Долго не сидели и пошли домой. И до двух ночи я читал википедию и другие сайты по лямбда и SKI исчеслению. Лаг спать когда прочитал про Y-комбинатор и ничего не понял, прочитал и опять ничего не понял;)

День первый

В пятницу у меня было важное совещание в 10:30, но после него я решил взять отгул, что бы потратить все время на контест. Утром когда проснулся меня осенило как можно создавать любые числа путем инкрамента и умножения на 2. Я быстро написал генератор представлений в SKI исчислении указаном в задаче. Сделал я это канечно же тоже на lua, так как быстрее было. Понял, что для больших чисел надо много операций. Пытался понять можно ли как то сложить два числа собранных в разных ячейках, но это оказалось невозможным. Пошел в офис.

Кирил, Пол и Джей обсуждали стратегии и саму задачу. Джей начал писать интерпретатор, который бы мы смогли использовать на C# (mono) в финальной программе. Пол делал саму программу которая бы взаимодействовала с тестером. В это время я и Кирил пытались разобраться с математикой, он уже реализовал интерпретатор игры на python. Ему было проще работать с питоном как мне с lua.

Мы не могли понять как передавать второй аргумент функции. Как имея в ячейке x(y), где x уже сложная функция, применить к у функцию z, что бы получилось x(z(y)). В этом была загвоздка. Я написал на луа брутафорсер, который бы переберал всевозможные варианты операций и смотрел получили ли мы нужную функцию. Пришлось даже перейти на luajit что бы оно работало быстрее. Но в общем почти весь день ушел в пустую - мы никак не продвинулись на 8 часов вечера.

И тут Кирил нашел в сети способ как можно изменить второй аргумент. Для этого надо было бы просто создать его в нулевой ячейке и применить слева K, потом S, а потом справа get и справа zero. Это был прорыв.

К этому моменту Пол сделал тупого бота, который повторяет действия оппонента и засабмитил его на тестовый сервер. Вел себя он не очень, но это было только начало. Потом пошли модификации бота в сторону использования dec много раз что бы убить ячейку оппонента.

Но что бы убивать ячейку быстро надо было что то придумать получше. Мы с Кирилом обсуждали много вариантов иногда даже срывались на мат русский язык в объяснениях. Кирил нашел в сети программу на haskel для преобразований лямбда выражений - но она не особо помогла нам.

Списался с Васей, он был на работе и обещал присоеденится в суботу с утра, когда прийдет домой.

Появыилось мнение, что нас спасет Y-комбинатор. Было уже очень поздно и все разошлись по домам, но мы с Кирилом остались и продолжили мозговой штурм. К трем часам ночи у нас появился вариант как использовать Y-комбинатор, что бы наносить много урона за раз. Прийнялись его переводить в комманды к тестовой программе руками. Исписали всю доску, вбили в интерпретатор Кирила, но оно не работало. То что было в википедии - Y-комбинатор в SKI - выдавало ошибку. Мы не могли понять почему. Кирил реализовал факториал в python-е при его помощи. Все было ок, но если взять и использовать Y взятый с вики - не получалось. Внесли в код новую карту Y - которая реализовывала Y-комбинатор и карту F - факториал. Запустили - все было ок. Но SKI функция не работала.

В общем в 4 часа ночи пошли по домам. Но на этом ещё не закончился день. Мы с Кирилом списались в google talk и продолжили работу. Попытались преобразовать лямбда выражение Y-комбинатора в SKI вручную, но было очень тяжело - получалось очень большое выражение. И я где-то доспустил ошибку. Кирил сделал тоже самое при помощи haskel программы - но тоже безрезультатно. Я подумал что надо автоматизировать преобразование лямбды в SKI и прогнать через Y-комбинатор. Начал реализацию, но довел только до половины. 20 часов на ногах. 18 из них программирования и мозгового шторма были очень утомляющими. Пошел спать.

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

День второй

Поспав 4 часа я проснулся, принял душ и пошел в офис. Мне надо было в 12 часов уехать на два часа в сервисный центр на плановый техосмотр машины. Поэтому терять время было нельзя.

Я почти доделал преобразователь λ в SKI и поехал в сервисный центр. Пока ждал - дописал, создал Y-комбинатор, который работает. Но он оказался очень большим. Преобразовать его в комманды к игровому серверу было нереально. Поэтому решил написать компилятор SKI в последовательность комманд. По началу казалось легкой задачей, но на создание нормального плана выполнения с оптимизациями типа - реюза уже просчитаных подвыражений у меня ушло около 6 часов. Но эта штука должна была быть очень полезной.

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

В то же время Кирил очень неплохо продвинулся. После того как научились делать атаку и безконечного цикла (который прерывался по лимиту действий, но урон оставался), стало возможным сделать продвинутые типы атак, которые выносят ячейки противника намного быстрее. В поединках мы видели, что у многих людей результаты лучше. До этого выигрывали порядка 20-30% матчей, после реализации рекурсивной атаки - около 40%. Тратили на это все 100000 ходов, ни разу не выигрывали досрочно.

Мы были шокированы когда нас оппонент убил за 123 хода. У нас только что бы собрать первую функцию атаки уходило около 200 ходов. А тут все 256 ячеек были убиты за это число ходов. Мы канечно понимали в чем дело - только оружие массового поражения могло такое сделать;) Это канечно была карта zombie, но мы не умели ещё ею пользоваться. Наверняка мы не знали, но были уверены что это zombie.

К тому же Кирил придумал хитрый ход - убивать 0-ю ячейку противника в самом нечале. Это позволяло выиграть у противников, которые не умеют воскрешать ячейки. Эта ячейка самая важная, она нужна почти во всех операциях. Если вынести её раньше того как вынесут нашу ячейку - есть шанс выиграть у не очень умных ботов.

Когда я дописал компилятор SKI - то увидел, что Y-комбинатор в нем занимает 892 хода. Это слишком много, хотя это уже было понятно раньше. За время работы над компилятором я немного отстал от алгоритмов которые обсуждались и пришлось вникать во все что придумали за это время.

Кирил создал очень крутое оружие - rollingAttack - это аттака которая собиралась за 127 ходов и выносила 0-ю ячейку противника на следующем ходу. Она использовала функцию attack - нанося урон и нам, но использовались не очень важные 50 ячеек. И если он не умел воскрешать ячейки - мы оставляли его безоружным и довивали peckingAttack - просто заклевывали обычным dec-ом.

Дела уже были получше - у нас хотя бы был полноценный бот, который хоть и был туповатым, но выигрывал у ещё более тупых ботов. Было немного досадно, что дела идут не очень. И было уже понятно что сверх-умного бота со всякими стратегиями - мы уже не сделаем.

Но мы знали, что для успеха надо научится использовать zombie, который вызывает heal. И если бы мы его сделали - то могли бы даже попасть куда то ближе к первым 50 участникам.

Опять уже было поздно, но как и в прошлый день мы с Кирилом остались и продолжили обсуждать проблему с зомби.

Для решения перешли к λ виду выражений и написали функцию, которая должна была бы быть один раз созданой и вставлена в мертвую ячейку. Потом она бы убивала соседнюю ячейку и копировала бы себя туда. Идея была отличная. Тут нам пригодился преобразователь с λ в SKI. Дальше скомпилировали в последовательность команд и запустили в интерпретаторе кирила - все заработало. Но в эмуляторе от судьей - ожидаемого результата не было. Немного подумали и пошли спать - уже было около 3-4 часов утра.

Кстати у Васи появились внеплановые проблемы и он к нам не смог присоедениться. Так что нас было только пятеро.

День третий - финальный

Вставать было очень тяжело. Хоть конкурс и завершался в 5 часов вечера и надо было идти в офис - но я просто физически не мог проснуться. Пришел где то около часа дня. Камрады оптимизировали существующие типы атак. Решили не тратить время на зомби, а сконцентрироваться на уже сделаном и довести до ума.

Но тут оказалось, что интерпретатор Пола отваливается по лимиту CPU на тестовом сервере. Где ошибка найти он не мог.

У нас было ещё две реализации интерпретаторов на lua и python, но доводить их до ума за оставшееся время было нереально. Да ещё и чревато ошибками. Было принято решение воевать в слепую. Имея четкую последовательность ходов - просто применяем её и надеемся что сработает. Тоесть мы вообще в финальной программе не будем знать что происходит на поле.

А это значило, что мы не сможем воскрешать наши мертвые ячейки. Что ж печально. Мы были уверены что оно будет работать, но толи C# был не очень подходящим вариантом, толи реализация. К тому же C# реализация интерпретировала функции, а lua и python - использовали функциональщину для реализации логики.

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

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

Тут кирил попросил попросил посмотреть ещё раз можно ли соптимизировать клюющую атаку. Я построил λ выражение с новой идеей, перевел в SKI и скомпилировал, но получилось что мой вариант убивает одну ячейку за 400 ходов, а все ячейки противника за 123000 ходов. Что не особо лучше предидущей реализации.

Но я не здался и соптимизировал одну инструкцию. Получил при этом убийство ячейки за 123 хода, противника за 94288 ходов. Отлично, но до конца контеста - 30 минут. А у меня формула и комманды к интерпретатору в текстовом файле.

Я быстренько интегрировал в C# код и Пол залил на тестовый сервер. 15 минут до конца. А мы не уверены стоит ли перезаливать финальную ферсию новой. Потестили локально, выиграли два поединка и решили - включать. Было стремно, но получилось все таки намного лучше предидущего результата. Он выигрывает в 55% случаев.

Итоги

В общем это была отличная встряска. Получил неймоверное удовольствие от контеста. Я узнал много про функцилнальщину. Да и просто отлично провел время.

Жаль канечно, что не сделали зомби и что в финальной версии мы отключили интерпретатор логики.

Посмотрел на наш репозиторий, а там: C#, C++, Python, Haskel, Lua, Shell. Вот такой вот зоопарк.

UPD: Наша комманда называется ShallowEndians. Почитал я блоги других комманд. Многие додумались до рекурсивного зомби используя copy, а потом get. Черт, гениально и просто. А пока за ночь наш бот нарубил 50 противников из 85 дуэлей;)

среда, 8 июня 2011 г.

Powershell cheatsheet

Useful powershell commands. Will update that list if i find something interesting.

tail -n 10 {filename}
get-content {filename} | select -last 10
gc {filename} | select -last 10
tail -f {filename}
get-content {filename} -wait
gc {filename} -wait
hostname
[System.Net.Dns]::GetHostName()

вторник, 14 сентября 2010 г.

MySQL в tmpfs

Хотелось бы поделиться опытом по использованию MySQL с хранением данных в памяти а не на диске. Это позволило нам сократить load average сервера, который из-за операций с диском стал сильно расти.



В одном проекте мы используем MySQL с движком MyISAM под Debian Lenny. Общие данные загружаются в оперативку демона на С++, а пользовательские данные один раз загружаются при логине и переодически сохраняются во время работы пользователя. Также сохраняются при логауте (либо по таймауту). Ввиду описаной схемы select-ов намного меньше, чем update-ов (select: 24%, delete: 4%, update: 61%, insert: 11%).

В принципе данная проблема - не админская, а вызвана не совсем удачным выбором инструмента. Скорее всего, нам бы подошел InnoDB, который использует row-level locking (блокировка по записям), а не table-level locking (блокировка всей таблицы при записи) как у MyISAM. Хотя объем данных записываемых на диск это врядли сократило бы. С другой стороны, нам SQL особо не нужен и мы склоняемся к портированию проекта на NoSQL (к некоторым из представителей мы давно приглядываемся (Сassandra), а некоторые (tokyo tyrant, Berkeley DB) мы активно используем для логирования пользовательских действий). Но выделить время на перевод хранилища данных на другой движок/базу не было, по этому решили использовать админ. ресурс.

С ростом количества пользователей и введением нового контента мы столкнулись с проблемой роста load average на сервере базы данных (2-3 la на 8-ми ядерном сервере наблюдалось всего при 400 запросах в секунду). При чем память была недогружена, как и процессор. Проблема была в большом большим объемом записи данных на диск (увеличение iowait). В некоторые моменты система начинала заикаться и некоторые примитивные запросы занимали 2 секунды, а то и больше. В нормальном режиме такие запросы выполняются за милисекунды.

Мы немного соптимизировали конфиги MySQL (используя как автоматические скрипты типа mysqltuner, так и ручную настройку), но это дало лишь небольшое снижение нагрузки (процентов на 10-15). По большей части параметры, отвечающие за кеширование данных, нам не подходят, так как у нас основная нагрузка - обновление данных, а не чтение. База находится на SAS диске, но скорости все равно не хватает. Бинарные логи находятся на другом диске (используются для бекапа базы со слейва).

Ускорить работу дисковой системы купив полноценный RAID нам не подходит из-за его большой цены. Но сам сервер почти простаивает, если не учитывать диски. Возможности сжатия данных в памяти до записи на диск в MyISAM нет, но и переходить на другой движек нету пока возможности (Falcon это должен был уметь, но его забросил Oracle после покупки MySQL)

База у нас занимает около 2-2.5 Gb (в tar.gz 700mb) и мы уже давно пробовали использовать MySQL в tmpfs (методом основаном на mylvmbackup), что позволяло не нагружать диск и упростить создание бекапа. К счастью мы недавно провели очистку базы, путем добавления крона, который удаляет старых пользователей, которые почти не пользовались проектом и ни разу не заплатили. Кроме этого мы очистили старые данные, которые собирали для статистики и поставили им срок жизни порядка двух месяцев.

В качестве быстрого решения даной проблемы возникла идея перевести главную базу на tmpfs. Что у нас получилось:

И так мы имели 3 сервера:
1. сервер А (боевая база куда стучатся демоны (у нас на нем 8Г оперативки ))
2. сервер Б (любой сервер на той же площадке со свободной оперативной (у нас 8Г из них 5Г свободно))
3. сервер В (на другой площадке заточен под бекапы всех проектов с максимум оперативки (у нас 16Г))

И так на Сервере А поднимаем tmpfs для файлов базы
mount -t tmpfs -o size=5G tmpfs /var/lib/mysql (с запасом в 2 раза больше чем весит база)
Так же не забываем в конфигах базы написать чтоб бин логи писались на оддельный свободный диск (мастер без них не работает), а под нагрузкой база может писать в эти логи до 1М в сек. Мы храним эти файлы не более 7 дней (более и не надо т.к. для востановления базы если что есть слайвы)

Соответсвено стартуем базу как мастер. Сервер под самими жескими нагрузками не выходит из 1ЛА и по памяти не более 6Г. Средняя скорость выполнения запроса вызросла в десятки раз, если раньше было 0,1-0,3 сек то стало 0.1-3 мсек
Далее на сервере Б так же поднимаем первый слейв тоже в tmpfs тут не стоит забывать о настройках relay-log т.к. если в слайве будет ошибка, а мастер будет доступен в эти логи он будет писать запросы которые были на мастере.. В итоге это может измерятся десятками гигобайт за ночь, прежде чем вы почините слайв, у нас это около 8-10 гигабайт в час. Бекапим эту базу снапшотами ночью 1-2 раза в день когда нагрузка на демоны минимальна. Такой слейв жрет максимум 0.2-0.3 ЛА и чуть более того что весит база.

Также на сервере В у нас подняты сразу несколько слайвов на tmpfs под наши проекты, споконо живут вместе особо не нагружая сервер при этом бекапятся снапшотом раз в 10 минут (если это время разложить то снапшот делается около 3 сек (базы вес которой 2,5 гига) ну и зжатие в архив около 6-7 минут) и да же при этом на сервере ЛА не привышает 2, даже когда бекапы пересикаются по времени. Судя по всему кол-во бекап слейвов на одном сервере определяется размером баз и кол-вом оперативки. Бекапы храним по 10 минут - последние 24 часа, каждые 6 часов - храним 30 дней, каждые 30 дней - вечно.

Далее если вдруг падает слайв Б или В поднять его с любым из бекапов с другово слайва не трогая мастер без проблем ели даже оба падают поднять не трогая мастер 10 минут - скорость переписывания бекапов.
Если падает мастер то есть на это два слейва с отстованием максимум 1-2 апдейта от мастера (не разу ни видели чтоб Slave Delay(отстование от мастера) превышал 0 сек) , при этом срочное решение проблемы это втечении 5 минут из слейва Б сделать мастер .. и перестроить демоны, при тестах они спокойно живут на одном сервере и не мешая друг другу.

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

Обязательно настраиваем оповещалки (munin, nagios, zabix - кому что больше по душе) на 2 площадках с измерением отстования слайва, можно по смс или по мылу, у нас нагиос следит за этим и при этом мунин его страхует и при этом рисует графики по которым все очень наглядно виодно что и как и кого.

Load average на серверах снижается осень сильно, теперь основную нагрузку берет на себя процессор и память, а не диск. Вот графики которые мы сняли при ещё одного переводе сервера сегодня:






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

В общем единственная потенциальная проблема — это рост базы. Но сейчас память в серваках достаточно дешевая и увеличить её не составит проблем (на части машин у нас 16Gb, на части 8Gb, но, насколько мне известно, можно поставить в потолке 128Gb). В любом случае кластеризацию базы никто не отменял и мы сможем разпределить базу на несколько серверов с схожей конфигурацией.

InnoDB - http://dev.mysql.com/doc/refman/5.1/en/innodb.html
MyISAM - http://dev.mysql.com/doc/refman/5.1/en/myisam-storage-engine.html
Сassandra - http://cassandra.apache.org/
tokyo tyrant - http://fallabs.com/tokyotyrant/
Berkeley DB - http://www.oracle.com/technetwork/database/berkeleydb/overview/index-085366.html
mysqltuner - http://mysqltuner.com/mysqltuner.pl
Falcon - http://en.wikipedia.org/wiki/Falcon_(storage_engine)
tmpfs - http://en.wikipedia.org/wiki/Tmpfs
mylvmbackup - http://www.lenzg.net/mylvmbackup/

понедельник, 29 марта 2010 г.

128-bit

Понадобилось на днях умножать и считать остаток от деления для 128 битных чисел на плюсах: (a * b) % c, где все числа 64 битные, а это значит что надо оперировать именно с 128 битами.
Нашел класс uint128_t, который использует два 64 битных числа. и в нем куча функционала. так как boost использовать нельзя было.
Быстро отпилил его, написав вручную недостоющие операторы. Отлично! Даже работает быстро. Но когда запустил на машине для которой создавался код все оказалось медленне раз в 10.
Немного покопав узнал, что дело в 32 битной системе (у меня на ноуте 64 бита). Очень огорчился и уж было думал что всё пропало и ничего сделать нельзя, но потом решил переписать вручную.
Сложить два 128 битных числа можно так:


inline void a_add_b_inplace(uint64_t& a0, uint64_t& a1, const uint64_t b0, const uint64_t b1)
{
 if(a1 >= 0xffffffffffffffffULL - b1)
 {
  ++a0;
 }
 a1 += b1;
 a0 += b0;
}


Умножение двух 64 битных чисел можно эфективно сделать используя три 32 битных числа и сохранить это все в 2 64 битных числа (получится 128 бит информации). Что то типа:


inline void a_mul_b(const uint64_t& a, const uint64_t& b, uint64_t& d0, uint64_t& d1)
{
 uint32_t a0 = (a >> 32) & 0x00ffffffffU;
 uint32_t a1 = a & 0x00ffffffffU;
 uint32_t b0 = (b >> 32);
 uint32_t b1 = b & 0x00ffffffffU;
 uint64_t c0 = ((uint64_t)a0) * b0; // << 64
 uint64_t c1 = ((uint64_t)a0) * b1 + ((uint64_t)a1) * b0; // << 32
 uint64_t c2 = ((uint64_t)a1) * b1;
 d0 = c0; // << 64
 d1 = c2;
 uint64_t c10 = (c1 >> 32) & 0x00ffffffffU;
 uint64_t c11 = c1 & 0x00ffffffffU;
 a_add_b_inplace(d0, d1, c10, c11<<32);
}
Остаток от деления можно получить уже не так просто. Для этого необходимо реализовать ещё несколько операций. Но удивил сам результат - на 32 битной платформе этот код работал в 5 раз бытрее чем класс uint128_t. А ещё на 64 битке эта реализация по скорости почти не отличается от 32-ной. Ура. В итоге я смог реализовать алгоритм Miller-Rabin-а для 64 битных чисел, который работал бы всего в несколько раз меленне на 32-х битной системе, чем на 64-х битной.

суббота, 20 марта 2010 г.

Планирование задач в сервере при помощи boost.task

Недавно на профильном ресурсе один программист задал вопрос: "Что использовать в сервере ММО для работы с потоками?". Программист склонялся к Intel TBB, но даже не к базовым примитивам, а к кастомному планированию задач (task scheduling). Ну нравится TBB - ну и ладно. А немного позже я увидел исходники сервера ММО другого программиста, который недавно начал переписываться его с нуля для улучшения архитектуры. И там было очень много велосипедов, которые писались самим программистом вместо того что бы использовать сторонние компоненты такие как boost (к примеру класы обертки над pthread-ом, и это в 2010 году, когда boost.thread уже почти в стандарте). Была там реализована и поддержка пула потоков с планировщиком задач. Тема эта мне очень интересна и я начал копать информацию о готовых решениях планировки задач (как в TBB) и нашел boost.task, про что и решил написать.

Определение

Задача (task) - это логически объедененный набор действий. Планировщик задач (task scheduler) асинхронино выполняет задачи руководствуясь определенными стратегиями по выбору кто должен выполняться в данный момент в каком потоке.

Задачи позволяют абстрагировться от обычных потоков и оперировать на более высоком уровне.

Зачем нужен планировщик задач?

Как работает сферический сервер в вакууме? Очень просто:
  1. Приходит запрос от клиента
  2. Он обрабатывается!
  3. Отсылается ответ

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

Сейчас загвоздка именно в том, как обрабатывается запрос. Надо разобраться как его обрабатывать.

Возьмем к примеру memcached-подобный сервер: у нас есть hash_map с данными, есть запросы чтения, есть запросы записи, которые делают простой лукап по хеш-мапе и возвращают данные либо записывают их в хеш-мап. Пока всё происходит в одном потоке, но что делать, если нам надо задействовать все процессоры системы?

Создаем столько потоков, сколько ядер. В каждом потоке обрабатываем пользователей, которых при создании соеденения раскидываем по принципу round-robin. При обращении к контейнеру используем rwlock-и (boost::shared_mutex). Отлично. А как нам быть с удалением элементов из контейнера? Создаем поток, который раз в N секунд просыпается и чистит контейнер.

Это был простой пример, а теперь более сложный пример: сервис, который может в зависимости от запроса пользователя сделать запрос в базу данных, сделать http запрос на какой то сайт. Что будет если сделать серрвер по предидущей модели (все запросы к другим компонентам будут выполняться синхронно)? Ну база данных находится на той же площадке, что и сервер, ответ будет в приделах пары миллисекунд. Отослать email - тоже не проблема - ставим sendmail на ту же машину, отдаём ему данные, а он сам разберется как отослать письмо.

Отлично. Хотя не совсем. А что делать с http-запросом? Он же может занять очень долго - всё зависит от сайта который находится где то далеко и не известно сколько будет обрабатывать запрос. В таком случае поток будет бездействовать, хотя в очереди есть много запросов, которые могут выполниться, но они ждут пока освободится этот поток.

Такой запрос необходимо выполнять асинхронно. Реализовать можно так:

class LongRequestHandler
{
public:
        void Handle()
        {
                // read client request parameters
                // mysql request 1
                // mysql request 2
                HttpRequestExecutor::GetInstance()->Execute(
                        "example.com?x=1",
                        boost::bind(this, &LongRequestHandler::HandleStage2)
                );
        }
        void HandleStage2(const std::string & http_request_result)
        {
                // mysql request 3
                // write response to client
        }
};

HttpRequestExecutor принемает url запроса и колбек, который надо вызвать по завершению запроса (тип колбека - boost::function).

И такой подход в работает, правда не слишком красиво.

В блоге Thinking Asynchronously in C++ показана интерестная реализация выполнения асинхронных задач. Выглядит результат следующим образом:

template void async_echo(
  tcp::socket& socket,
  mutable_buffer working_buffer,
  Handler handler,
  // coroutine state:
  coroutine coro = coroutine(),
  error_code ec = error_code(),
  size_t length = 0)
{
  reenter (coro)
  {
  entry:
    while (!ec)
    {
      yield socket.async_read_some(
          buffer(working_buffer),
          bind(&async_echo,
            ref(socket), working_buffer,
            box(handler), coro, _1, _2));
      if (ec) break;
      yield async_write(socket,
          buffer(working_buffer, length),
          bind(&async_echo,
            ref(socket), working_buffer,
            box(handler), coro, _1, _2));
    }
    handler(ec);
  }
}

Coroutine и yield в С++ смотрятся необычно;) Реализовано это на дефайнах, в блоге можно почитать как это удалось автору.

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

mysql request 1
mysql request 2
http request 1
mysql request 3
http request 2
mysql request 4
mysql request 5

И выполняя её последовательно с остановками в http запросах мы видим,что запросы

mysql request 2
http request 1

и

mysql request 3
http request 2
mysql request 4

можно выполнять паралельно и если мы захотим это сделать, то прийдется ещё сильнее усложнять логику. А хотелось бы написать простой код, например:

mysql request 1
x = run(func1)
y = run(func2)
wait(x, y)
mysql request 5

func1:
  mysql request 2
  http request 1

func2:
  mysql request 3
  http request 2
  mysql request 4

Вот тут и пригодиться планировщик задач.

Реализации

Про поддержку планировщика задач в новом стандарте 0x можно почитать тут.
  • just::thread - реализация библиотеки потоков стандарта C++0x от отца boost::thread
  • Parallel Patterns Library (PPL) - реализцаия от Microsoft
  • Asynchronous Agents Library - и ещё одна от Microsoft
  • Intel Threading Building Blocks - очень мощная библиотека для паралельного программирования от Intel. Включает в себя и планировщик задач.
  • boost::task - - реализация от Oliver Kowalke, не принятая ещё в boost

Мне наиболее понравился boost.task. Дальше его детальное рассмотрение.

Описание boost.task

boost.task - реализация предложения в стандарт C++0x. Она поддерживает задание стратегий выполнения задач, создание под-задач, прерывание задач.

Библиотека зависит от:

boost.task и boost.fiber компилируемые библиотеки (boost.atomic и boost.move - header-only) - так что прийдется их собирать. Что бы было удобнее эксперементировать собрал все зависимости в одном месте, приправил cmake-ом и залил поект на github. Работает на linux-е, для сборки под windows - потребуется 2-3 строчки добавить в cmake файлы.

Пример использования

API библиотеки достаточно простой, реализовать обработчик запроса, который описывался выше не совтавит труда. Приведу его ещё раз:

mysql request 1

  mysql request 2
  http request 1

  mysql request 3
  http request 2
  mysql request 4

mysql request 5

В качестве эмуляции запроса к mysql будет использован обычный sleep на случайное время:

boost::this_thread::sleep(boost::posix_time::milliseconds(rand()%100 + 10));

В качестве внешнего http-запроса будет использован асинхронный таймер из boost::asio.

Итак:

Request - класс запроса.

class Request
{
public:
    Request(const std::string & data);
    const std::string & Read() const;
    void Write(const std::string & answer);
};

А RequestHandler - класс обработчика запроса.

class RequestHandler
{
public:
    RequestHandler(boost::asio::io_service & io_service, const RequestPtr & request);
    void Process() const;
};

io_service - передается для того, что бы можно было выполнить внешний вызов (использовать таймер boost::asio::deadline_timer).

Итак начнем. Определяем пул потоков, для обработки наших задач:

boost::tasks::static_pool< boost::tasks::unbounded_fifo > pool( boost::tasks::poolsize( 5) );

boost.task поддерживает два основных вида стратегий планировки задач:

  • ограниченные (bounded) - имеют порог количества выполняемых задач, при достижении которого добавление новой задачи блокирует поток, который выполняет это действие. Основная задача - избежать исчерпания ресурсов (resource exhaustion) когда скорость добавления задач превышает скорость их выполнения
  • неограниченные (unbounded) - позволяют добавлять бесконечное число задач в очередь

Также есть возможность задания стратегии обработки задач внутри очереди:

  • fifo - первая добавленная задача выполняется первой
  • priority - у задачи есть приоритет, для выполнения выбираются задачи с высшим приоритетом
  • smart - очередь такого типа возможно сильно кастомизировать передавая параметры в шаблон. по умолчанию есть возможность индексировать задачи по любому ключу и заменять старую задачу на новую, если она сущесвует

Соответственно описанная строчка кода создает пул из 5 потоков с неограниченной очередью типа fifo.

Теперь нам понадобится создать io_service и пул из 3-х потоков для обработки внешних запросов.

boost::asio::io_service io_service;

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

boost::asio::deadline_timer dummy_timer(io_service);
dummy_timer.expires_from_now(boost::posix_time::seconds(10));
// void dummy_handler(const boost::system::error_code&) {}
dummy_timer.async_wait(&dummy_handler);

После этого можно создать пул потоков:

boost::thread_group io_service_thread_pool;
for(int i = 0; i < 3; ++i)
    io_service_thread_pool.create_thread(
        boost::bind(&boost::asio::io_service::run, &io_service)
    );

Далее создаём запрос:

RequestPtr request(new Request("some data"));
RequestHandlerPtr handler(new RequestHandler(io_service, request));

Все готово, можно выполнять задачу:

boost::tasks::handle< void > request_processing(
    boost::tasks::async(
        boost::tasks::make_task( &RequestHandler::Process, handler ),
        pool));

boost::tasks::make_task( &RequestHandler::Process, handler ) - создает задачу вызова Process у объекта handler, которую можно будет выполнить. boost::tasks::async инициирует асинхронное выполнение задачи. boost::tasks::handle объект, по которому можно отслеживать статус завершения задачи, получить результат если он есть.

boost::tasks::async поддерживает 4 алгоритма выполнения задачи:

  • own_thread - синхронное выполнение в том же потоке
  • new_thread - для задачи создается поток, в котором она будет выполнена, после чего поток будет завершен
  • as_sub_task - если текущая задача выполняется в пуле - добавляет новую задачу в него, иначе создает новый поток, как new_thread. Это поведение по умолчанию
  • static_pool - выполнить задачу в пуле потоков

Далее подождем пока задача выполнится:

request_processing.wait();

И остановим io_service:

io_service.stop();
io_service_thread_pool.join_all();

Функция Process получилась на удивление очень простой

void Subtask1() const
{
    Request("query2");
    ExternalRequest("extquery1");
}

void Subtask2() const
{
    Request("query3");
    ExternalRequest("extquery2");
    Request("query4");
}

void Process() const
{
    std::string data = request_->Read();

    Request("query1");

    boost::tasks::handle< void > subtask1(
        boost::tasks::async(
            boost::tasks::make_task( &RequestHandler::Subtask1, this )));
    boost::tasks::handle< void > subtask2(
        boost::tasks::async(
            boost::tasks::make_task( &RequestHandler::Subtask2, this )));

    boost::tasks::waitfor_all( subtask1, subtask2);

    Request("query5");

    request_->Write("some answer");
}

Подзадачи выполняются при помощи boost::tasks::async без указания policy на запуск и автоматически выбирается as_sub_task алгоритм, который выполнит задачи в том же пуле потоков, что и родительская задача. Реализация функций подзадач тоже тривиальная.

RequestHandler::Request - вызывает boost::this_thread::sleep, а с ExternalRequest все немного сложнее:

void ExternalRequest(const std::string & what) const
{
    ExternalRequestHandler external_handler(io_service_);
    boost::tasks::spin::auto_reset_event ev;
    external_handler.PerformExternalReqeust(what, &ev);
    ev.wait();
}

Создается хендлер, а так же событие с автоматическим сбросом - boost::tasks::spin::auto_reset_event. Это событие передается обработчику внешнего запроса и по его завершению будет вызвано ev.set(), а до тех пор ev.wait() блокирует задачу.

В противовес обычным потокам и примитивам синхронизации (boost::condition) ev.wait() не блокирует поток, а блокирует задачу (вызывает в цикле this_task::yield()). А это значит, что ресурсы процессора будут использованы другими задачами.

Файл целиком может быть найден тут.

Выводы

boost.task вполне удобная библиотека для планирования задач. Она позволяет посмотреть как будет выглядить поддержка асинхронного выполнения кода в новом стандарте C++0x, и её можно использовать уже прямо сейчас не дожидаясь пока будет выпущен стандарт.

Код с использованием boost.task становится меньше и намного понятнее, чем при обычном использовании потоков.

Есть канечно и недостатки: код ещё не оптимизирован, что может вызвать проблемы в редких случаях; библиотека ещё не принята в boost (вместе с её зависимостями).

Что почитать по теме?