thirteen

Algorithm used in submission, team THIRTEEN, ICFP Contest 2009 [eng]

There were several requests from english-speaking audience about the algorithm

which was used by our team. So, this article may give some description.

Full source code is in at the end of that post (subversion url).

Team Thirteen algorithm contains the following parts:
————————————————————

1) Lambert transfer: given the

• current coordinates
• motion vector
• exact desired transfer time T
• destination point,

calculates the impulse vector. This is done analytically (matlab+books), and very fast algorithm is implemented (10 iterations max). The results are not exact, but are used as a basis for

• estimating the travel costs to any satellite
• actual transfer setup (see “9)”)

2) Choose the right time to start. Given the

• current position
• destination satellite
• 2 time brackets

calculates the delay (t0) before Lambert transfer and duration T of the transfer, so that transfer has optimal parameters (speed or fuel usage).

3) Moon gravity - when some “earth/moon” point is passed, Earth gravity is not taken into the account when calculating Lambert, and moon-centered calculations are performed.  Otherwise, moon is excluded from the Lamber equations same way.

4) bin -> java compiler. Produces java class for fast calculations, for each task. Input/Output as per specification, 1 time tick is calculated. ”clone” method for previews of the future.

5) Simulator: given the initial impulse and delta T, calculate final state of the world (T iterations of VM).

6) For task 4001-4004, bin -> java compiler which does NOT calculate all satellites, only earth/moon/traveller coordinates. This is done by tracking data dependencies in bin file and excluding all non-relevant calculations which result in non-needed ports. 15-20x speedup is achieved.

7) caching of satellites position for the whole time range of problem, for faster lookup at any time point (done once per problem). Together with “6)” it gives fast “future preview” ability with regard to satellites.

8 ) Travelling salesman problem, reducing the use of fuel, without visiting fuel station. By the way, score was added for visiting it (later we discovered it). When choosing next satellite, we optimized t0, and T (see “2)”) and used search depth of 2 satellites (current, next, one after next), and criteria was to minimize sum of fuel spent.

9) Precise meeting. Given the satellite, using the Lamber transfer, get the initial impulse. Then, minimize the function distance_to_destination_with_initial_impilses(Ix, Iy) function is implemented as a simulation flight using fast java implementation of formulas from bin file (see “4)” and “6)”). Using gradient descent for optimization. Problem: when travelling towards earth, calculates very slowly due to unsophisticated algorithm.

9a) when optimization fails due to very long computations, travel anyway with best found impulse, then calculate new impulse in the middle of travel. Repeat if needed.

10) another algorithm of travelling salesman, where speed of travel was optimized, but fuel was refilled at the base station, was developed, but due to competition time constraints, was not polished, and used as backup algorithm. This helped to solve 1 problem, where main algorithm failed (!) during the separate top-10 competition in the aftertime.

Материалы по теме ICFP Contest 2009

http://vimeo.com/album/126865/video/6613815 - видео с ICFP Conference с разбором полетов

http://san13.habrahabr.ru/blog/68995/ - популяризаторская статья на ICFP тему

http://vidiowiki.com/watch/m844dyn/ - интервью с победителем этого года (японец).

http://shinhoge.blogspot.com/2009/09/icfp-programming-contest-2009.html - его блог (англ).

http://john.freml.in/icfp-contest-2009-debrief - человек подбил итоги по top10

THIRTEEN заняли второе место на ICFPC 2009

Пришла почта от организаторов, наше - второе место. Результаты еще не опубликовали в инете (кто в танке - сам контест был летом, про спутники вокруг земли).

Тем не менее, вчера в Эдинбурге на ICFP конференции было награждение первых мест (первое в блице, первое в основном зачете, и приз симпатий жюри).

Мы собрались туда поехать, но визы нынче делаются дольше, чем 2 недели, и даже сегодня еще не готовы. Поэтому поедем позже в Эдинбург просто погулять, если всё будет хорошо.

Первое место заняла команда shinh (C++) из Японии, которая заняла второе место в прошлом году. Первое место в прошлом году заняли гугловцы.

Первое место в этом году в блиц-раунде занял человек из Севастополя по имени Aleksey, и в прошлом году тоже он.  Он тоже не получил еще визу, и не смог вкусить лавров.

До следующих встреч!

ICFP Contest 2009, Java vs Haskell performance investigation

Джентельмены!

Я взял в руки Хаскель, и за один световой день (суммарно) написал компилятор бинарных файлов от ICFPC 2009. Он компилирует формулы из obf файлов в быстрый Haskell вычислитель. Ну, вместо интерпретатора.

Я преследовал следующие цели:

• вспомнить Хаскель (а то в последнее время я уже его позабыл), и написать идеальный компилятор. В нашем блоге существует ссылка на аналогичную разработку.
• замерять время, за которое я это напишу (тест провален - медленно. Но я делал это на мини-ноутбуке на коленках, и иногда отвлекался на детей и жену)
• написать программу для товарищей чтобы смотрели как это выглядит на Haskell.
• измерить lazy/strict имплементацию в Haskell по скорости
• сравнить производительность с нашей текущей VM (на java)
• сравнить производительность с идеальной VM, написанной на java.

Что я могу сказать по этим пунктам? Хаскель на данной задаче рвет Джаву на куски (Haskell в 2 раза быстрее чем Java).

Задача: задание 4001 целиком (все объекты), посчитать итерации/сек.

Environment: Intel Q6600, Arch Linux 64bit, GHC 6.10.3, JDK 1.6u14, all single-threaded

Результат:

• Java version (as sent to contest): 22K iter/sec
• Java version (ideal): 44K iter/src
• Java version (ideal, 32bit): 32K iter/src
• Haskell version (lazy): 1.73K iter/sec, up to 8.1K iter/sec ==> fail.
• Haskell version (strict): 96K iter/sec.

Идеальная VM на Java выглядит так:

public class Vm {
  double m2039;
  {m2039=0.0; }
  public void fw(double[] i, double[] o) {
      double t60=((6.67428e-11*t59));
      double t61=(((((t53*t53)*t53) != 0) ? t60/((t53*t53)*t53) : 0));
      m2039=(t12+1.0);
          o[0]=((((Math.sqrt (((t1989*t1989)+(t1987*t1987))))-6357000.0)<0) ? ...
  }
}

Что мы здесь имеем? Все временное в пределах итерации вынесено в локальные переменные, постоянное в members, выражения приведены в скобках (кроме повторно использующихся, которые пошли в локальные переменные). Константы сделаны константами. Порты сделаны массивом, можно было дать им персональные имена, но их мало, и на производительность это не влияет. Один вызов функции переводит объект в новое состояние (тик +1). Приятной особенностью задания (или решения?) является отсутствие ссылок вперед во временных переменных.

Неидеально откомпилированная виртуальная машина  выглядит так: вместо временных переменных - members. Вместо вложенных скобок - сохранение результата в members на каждом шаге. То есть, практически один к одному по спецификации, выданной в PDF к заданию:

d57 = d2042;
d59 = (d13 == 0.0 ? d56 : d57);
d60 = d34 * d59;
d61 = (d55 != 0.0 ? d60 / d55 : 0.0);
d62 = d45 * d61;
d63 = d62 + d41;
d64 = d63 * d4;
d65 = d2114;
d66 = d9 * d9;
d67 = d11 * d11;

Теперь смотрим Haskell. Здесь не принято модифицировать объект, и не имеется легких средств для этого. Вместо этого мы описываем объект (algebraic data type), затем функцию, которая создает первоначальный экземпляр, и еще пишем функцию, которая создает из одного экземпляра другой, отстоящий от него на 1 тик. Код получается похожий на Java, но временные переменные отсутствуют, вместо них let- bindings. Тестирование состояло в выводе на экран результатов после 45000 итераций, всего состояния (чтобы вычислить все ленивые цепочки).

data VMState = VMState { m2039,...,o101::Double }
initState = VMState {m2039=0.0....}
nextState x (i16000,i3,i2)=
  let ....
      t18=((if t13==0 then 3.84399e8 else m2051 x)) :: Double
    in 
     x { m2039= .... , o39=(if (t1699-0.0)==0 then 0.0 else 1.0) }

В типе VMState параметры конструктора сделаны ленивыми. Если экземпляр VMState был порожден от другого экземпляра указанным образом, то он содержит ленивые заглушки (thunks, не знаю как сказать), которые находятся в куче. А если у нас 50000 тиков просчитать надо, то это надо пройти через 50000 экземпляров, у каждого из которых порядком параметров, и все ленивые. Короче, этот код дает нам 1.73К итераций в секунду, и это ужасно. Но стоит только заменить их на strict,

data VMState = VMState { m2039,...,o101:: !Double }

как тут же всё начинает шустро бегать. (96К iter/sec). В профайлере смотрим, что выделения лишней памяти практически нет (только экземпляры VMState), и нагрузка на GC крайне мала..

В принципе, этого может быть и достаточно, но, возможно, промежуточные варианты дадут нам какую-то надежду на lazy. В большинстве случаев нам в задачах 4001-4004 нужна только наша собственные пространственная позиция в ответ на импульс. Попробуем требовать только позицию, а не всю структуру с координатами планет и т.д. Нашей позиции соответствуют поля o2, o3 (output ports 0×2, 0×3 из спецификации). Скорость расчета получается 4.5К iter/sec, что в два раза быстрее, потому что прочие значения не рассчитываются!

Теперь попробуем оставить эти два поля strict, а все остальные поля сделать lazy! Скорость получается 8.1K iter/sec! Это наверное оттого, что garbage collector-у надо делать чуть меньше работы, потому что после присвоения strict-полю цепочка ленивых вычислений может быть освобождена сразу же, а не только после вывода результата в конце всех итераций. Она становится быстрее и легче доступной для сборки.

Почему Хаскель быстрее чем Java на нашей задаче? Наверное потому что он компилирует в бинарник, даже притом, что сгенерированный в нем код ужасен по сравнению с тем, который выдает C/C++. И, наверное, здесь лучше работает компилятор, который может быть уверен, что  одинаковые куски в выражениях (например, “m12345 x == 0″) достаточно вычислять только один раз. Роскошь, которую себе не может позволить Java. Для Java пришлось бы писать дополнительный код, который детализирует эти нюансы, а для Haskell вот, не надо.

Комментарии по коду компилятора (который лежит тут) :

1. он генерит full lazy variant (strictness annotations были добавлены руками по результату)
2. константы вставлены в user-friendly формате, а не побитово (надо побитово)
3. там внутре код который генерирует Java, он неактивен, но есть.
4. код компилятора с комментариями и пустыми строками, и веткой на Java - 238 строк.
5. компилятор достаточно производителен для bin4.obf (4 задание), код не оптимизирован (красоты для).

Улучшения и замечания к компилятору приветствуются. Спасибо за внимание.

This article was slightly tuned for google translation from Russian, hence the language.

Youtube

Перезалили несколько штук на youtube еще (все старые).

http://www.youtube.com/watch?v=mFPd2xtcseI
http://www.youtube.com/watch?v=m5pyK4hYjrI
http://www.youtube.com/watch?v=1xipQH3PGog
http://www.youtube.com/watch?v=39ZtWqZoPUo

episode 4002, speedy algorithm, score 723

Это посчитано кодом, который ушел в сабмит, но не заенаблен, потому что он не считает все случаи хорошо. Точнее, оказалось, что он считает 4002 случай лучше чем официально заенабленный алгоритм, но это нашли токо сейчас.

Оригинал 3.5М

(brox) Don’t Panic

А чего это я распереживался? Оказывается, наши последние сорцы из svn прекрасно работают, и выдают на гора соответственно:
4001-613.653
4002-678.975
4003-563.734
4004-610.659
Просто надо было запускать с параметром false, а не 0.
Т.е. Problem4Solver 4001 false
Так что я тулчейн подпилю слегка, и готово дело.

(sas) Сумбурное

В этот раз все было куда как лучше. Я горжусь, что смог примазаться к таким людям.
Но я не удовлетворен. Уж очень мало сам сделал полезного. Мне бы поменьше болтать, да побольше кодить.
А вот команде в целом бы наоборот бы. Бы. San хорош. Очень. Может быть слишком. Я за полетом его мысле-рук не успеваю. Остановить и одумать его никак. А порой надо. Обидно иметь давно решенные задачи и не иметь рабочей проги в час Х.
А в целом, и впрочем, это - подробности. Которые враки.
Пошел писать все сначала, на хаскеле. Чего и вам.

ICFPC 2009 THIRTEEN testcase 4001 video

Здесь базу посетили _после_ Луны.

Оригинал 5М

ICFPC 2009 THIRTEEN testcase 4003 video

Здесь мы залетаем на базу перед полетом на луну.

Оригинал