Сегодня на хабре проходила статья про Nemerle и ICFP 2009. Я хотел бы поделиться собственными изысканиями на эту тему, которые сделал недавно. Моей задачей было написать идеальный компилятор VM из задания, сделать это на Хаскеле, а главное, сравнить скорости результирующего кода на Java и на Haskell. Здесь не приводится полное решение задачи для ICFP, потому что задача эта переборная, и VM в ней — самое внутреннее место, от которого зависит производительность переборного решения, этим она и интересна.
Введение в задачу: организаторами дается некая программа в виде байт-кода, к которому дается спецификация. Байт код не содержит в себе кодов перехода, а содержит только инструкции вида m1 < — m2 + m3 и им подобные, в том числе инструкция условного выбора из двух ячеек. Существует три адресуемых типа памяти, каждая из которых имеет тип «массив double»: память входных параметров, которая read only, память рабочая: read/write, и память выходных параметров — write only. Один проход программы дает на выходе координаты небесных тел в следующую точку времени, память должна сохраняться между проходами, потому что в ней лежит состояние мира. Используя данный «симулятор мира», необходимо подавать на вход программе управляющее воздействие на некий спутник, который должен по этому миру летать и что-то делать. Все координаты внутри вычисляются по известным формулам, приближенным к реальным, и всё получается очень красиво. Эти-то формулы и закодированы в VM. Используя данную VM, необходимо, в конечном итоге, оптимально управлять спутником, а эти управляющие последовательности являются тем, за что в конечном итоге дадут приз, а может и не дадут.
Прежде чем сравнивать Haskell и Java, я хотел бы уточнить про сравнение скоростей программ на OCaml и С/C++, о котором шла речь в комментах. В оригинальной статье сравнивался интерпретатор на С++ с JIT-компилятором на Ocaml, оттуда и превосходство OCaml-а в скорости. В нашем же варианте, мы будем сравнивать идентичные оптимальные виртуальные машины, сгенерированные компилятором — ahead of time.
Что я могу сказать по поводу скорости? Хаскель на данной задаче оказывается более чем 2 раза производительней, чем Java. Известное дело, если сгенерировать код на C, то производительность будет выше еще раз в 5-10: мы пробовали c неидеальным кодом еще в процессе соревнования.
Итак, задача: задание 4001 целиком, то есть все объекты: 12 пассивных спутников + луна + наш спутник. Необходимо посчитать итерации/сек.
Оборудование: Intel Q6600 неразогнанный, Arch Linux 64bit, GHC 6.10.3, JDK 1.6u14, все без использования многопоточности: для измерения качества Haskell как компилятора. Измерения в Java уже после того, как Hotspot прогрелся, а произошло это на чуть ли не на первых секундах, после чего результат не менялся)
Результат (итерации в секунду, весь просчитанный мир целиком в задачах 4001..4004 = 1 итерация):
* Java version (as sent to contest, простая компиляция): 22K iter/sec
* Java version (идеальная компиляция): 44K iter/src
* Java version (идеальная компиляция, 32bit JDK): 32K iter/src
* Haskell version (с ленивыми данными в VMState): 1.73K iter/sec, up to 8.1K iter/sec ==> незачёт.
* Haskell version (c strict данными в VMState): 96K iter/sec.
Идеальная VM на Java выглядит так (значащий фрагмент):
Что мы здесь имеем? Все временное в пределах итерации вынесено в локальные переменные, постоянное в members, выражения приведены в скобках (кроме повторно использующихся, которые пошли в локальные переменные). Константы сделаны константами. Порты сделаны массивом, можно было дать им персональные имена, но их мало, и поэтому на производительность это не влияет. Один вызов функции переводит объект в новое состояние (тик +1). Приятной особенностью задания является отсутствие ссылок вперед на временные переменные.
Напротив, неидеально откомпилированная виртуальная машина выглядит так: вместо временных переменных — members. Вместо вложенных скобок — сохранение результата в members на каждом шаге. То есть, практически один к одному по спецификации, выданной в PDF к заданию:
Теперь смотрим, как это сделано на Хаскеле. Здесь не принято модифицировать объект, и не имеется простых средств для этого. Вместо этого мы описываем объект (algebraic data type), затем функцию, которая создает первоначальный экземпляр, и еще пишем функцию, которая создает из одного экземпляра другой, отстоящий от него на 1 тик. Код получается похожий на Java, но временные переменные отсутствуют, вместо них let- bindings. Тестирование состояло в выводе на экран всего состояния (чтобы вычислить все ленивые цепочки), после 45000 итераций.
В типе VMState параметры конструктора (поля структуры) сделаны ленивыми. Если экземпляр VMState был порожден от предыдущего экземпляра через nextState, то он содержит ленивые заглушки (thunks, не знаю как сказать), которые находятся в куче. А если у нас 45000 тиков просчитать надо, то это надо пройти через 45000 экземпляров, у каждого из которых изрядно (сотня) параметров, и все ленивые. Короче, этот код дает нам 1.73К итераций в секунду, и это ужасно. Но стоит только заменить их на strict,
как тут же всё начинает шустро бегать. (96К iter/sec). В профайлере смотрим, что выделения лишней памяти практически нет (только экземпляры VMState), и нагрузка на GC крайне мала…
В принципе, этих изысканий уже может быть и достаточно, но, возможно, промежуточные варианты дадут нам какую-то надежду на то, что lazy может дать приемлемые скорости?
Для этого мы позволим себе взять подзадачу: в большинстве случаев в задачах 4001-4004 нужна только наша собственная пространственная позиция в ответ на наш импульс, а координаты спутников могут быть просчитаны раз и навсегда (заранее). Попробуем требовать от VM только позицию, а не всю структуру с координатами планет и т.д. Нашей позиции соответствуют поля o2, o3 (output ports 0×2, 0×3 из спецификации). Так как Haskell — ленивый язык, то мы можем ту же функцию (nextState, ленивый вариант) использовать в наших узких целях. В этом случае скорость расчета получается 4.5К iter/sec, что в два раза быстрее, потому что прочие значения не рассчитываются!
Теперь попробуем сделать эти два поля строгими (strict), а все остальные поля оставить lazy! Скорость получается 8.1K iter/sec! Это наверное оттого, что garbage collector-у надо делать чуть меньше работы, потому что после присвоения strict-полю цепочка ленивых вычислений может быть освобождена сразу же, а не только после вывода результата в конце всех итераций. Она становится быстрее и легче доступной для сборки.
Почему Хаскель быстрее чем Java на нашей задаче? Наверное потому что он компилирует в бинарник (executable), даже принимая во внимание, что сгенерированный в нем ассемблерный код ужасен по сравнению с тем, который выдает C/C++. И, наверное, здесь таки качественнее работает компилятор, который может быть уверен, что одинаковые куски в выражениях (например, в условиях “m12345 x == 0″) достаточно вычислять только один раз. Это роскошь, которую не может себе позволить Java. Для Java нам пришлось бы писать дополнительный код, который детализирует эти нюансы, а для Хаскеля вот, не надо, умный компилятор.
Комментарии по коду компилятора (который лежит тут) :
1. он генерит full lazy variant (strictness annotations добавлялись руками поверх результата компиляции в исследовательских целях)
2. константы вставлены в user-friendly формате, а не побитово (надо побитово)
3. там внутри код который генерирует также и Java, он неактивен, но есть.
4. код компилятора с комментариями и пустыми строками, и веткой для Java — 238 строк.
5. компилятор достаточно производителен для bin4.obf (4 задание), код не оптимизирован (красоты для).
Улучшения и замечания к компилятору приветствуются. Если необходимо, могу написать аналогичную статью про сам компилятор, а именно про перевод из плоских выражений в выражения со скобками итд, насколько просто это делается.
Спасибо за внимание.
Введение в задачу: организаторами дается некая программа в виде байт-кода, к которому дается спецификация. Байт код не содержит в себе кодов перехода, а содержит только инструкции вида m1 < — m2 + m3 и им подобные, в том числе инструкция условного выбора из двух ячеек. Существует три адресуемых типа памяти, каждая из которых имеет тип «массив double»: память входных параметров, которая read only, память рабочая: read/write, и память выходных параметров — write only. Один проход программы дает на выходе координаты небесных тел в следующую точку времени, память должна сохраняться между проходами, потому что в ней лежит состояние мира. Используя данный «симулятор мира», необходимо подавать на вход программе управляющее воздействие на некий спутник, который должен по этому миру летать и что-то делать. Все координаты внутри вычисляются по известным формулам, приближенным к реальным, и всё получается очень красиво. Эти-то формулы и закодированы в VM. Используя данную VM, необходимо, в конечном итоге, оптимально управлять спутником, а эти управляющие последовательности являются тем, за что в конечном итоге дадут приз, а может и не дадут.
Прежде чем сравнивать Haskell и Java, я хотел бы уточнить про сравнение скоростей программ на OCaml и С/C++, о котором шла речь в комментах. В оригинальной статье сравнивался интерпретатор на С++ с JIT-компилятором на Ocaml, оттуда и превосходство OCaml-а в скорости. В нашем же варианте, мы будем сравнивать идентичные оптимальные виртуальные машины, сгенерированные компилятором — ahead of time.
Что я могу сказать по поводу скорости? Хаскель на данной задаче оказывается более чем 2 раза производительней, чем Java. Известное дело, если сгенерировать код на C, то производительность будет выше еще раз в 5-10: мы пробовали c неидеальным кодом еще в процессе соревнования.
Итак, задача: задание 4001 целиком, то есть все объекты: 12 пассивных спутников + луна + наш спутник. Необходимо посчитать итерации/сек.
Оборудование: Intel Q6600 неразогнанный, Arch Linux 64bit, GHC 6.10.3, JDK 1.6u14, все без использования многопоточности: для измерения качества Haskell как компилятора. Измерения в Java уже после того, как Hotspot прогрелся, а произошло это на чуть ли не на первых секундах, после чего результат не менялся)
Результат (итерации в секунду, весь просчитанный мир целиком в задачах 4001..4004 = 1 итерация):
* Java version (as sent to contest, простая компиляция): 22K iter/sec
* Java version (идеальная компиляция): 44K iter/src
* Java version (идеальная компиляция, 32bit JDK): 32K iter/src
* Haskell version (с ленивыми данными в VMState): 1.73K iter/sec, up to 8.1K iter/sec ==> незачёт.
* Haskell version (c strict данными в VMState): 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+t41))
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;
Теперь смотрим, как это сделано на Хаскеле. Здесь не принято модифицировать объект, и не имеется простых средств для этого. Вместо этого мы описываем объект (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, но с некоторыми новыми значениями"
x { m2039= .... , o39=(if (t1699-(t12+t14*2))==0 then 0.0 else 1.0) }
В типе VMState параметры конструктора (поля структуры) сделаны ленивыми. Если экземпляр VMState был порожден от предыдущего экземпляра через nextState, то он содержит ленивые заглушки (thunks, не знаю как сказать), которые находятся в куче. А если у нас 45000 тиков просчитать надо, то это надо пройти через 45000 экземпляров, у каждого из которых изрядно (сотня) параметров, и все ленивые. Короче, этот код дает нам 1.73К итераций в секунду, и это ужасно. Но стоит только заменить их на strict,
data VMState = VMState { m2039,...,o101:: !Double } -- замечаем воскл. знак перед Double
как тут же всё начинает шустро бегать. (96К iter/sec). В профайлере смотрим, что выделения лишней памяти практически нет (только экземпляры VMState), и нагрузка на GC крайне мала…
В принципе, этих изысканий уже может быть и достаточно, но, возможно, промежуточные варианты дадут нам какую-то надежду на то, что lazy может дать приемлемые скорости?
Для этого мы позволим себе взять подзадачу: в большинстве случаев в задачах 4001-4004 нужна только наша собственная пространственная позиция в ответ на наш импульс, а координаты спутников могут быть просчитаны раз и навсегда (заранее). Попробуем требовать от VM только позицию, а не всю структуру с координатами планет и т.д. Нашей позиции соответствуют поля o2, o3 (output ports 0×2, 0×3 из спецификации). Так как Haskell — ленивый язык, то мы можем ту же функцию (nextState, ленивый вариант) использовать в наших узких целях. В этом случае скорость расчета получается 4.5К iter/sec, что в два раза быстрее, потому что прочие значения не рассчитываются!
Теперь попробуем сделать эти два поля строгими (strict), а все остальные поля оставить lazy! Скорость получается 8.1K iter/sec! Это наверное оттого, что garbage collector-у надо делать чуть меньше работы, потому что после присвоения strict-полю цепочка ленивых вычислений может быть освобождена сразу же, а не только после вывода результата в конце всех итераций. Она становится быстрее и легче доступной для сборки.
Почему Хаскель быстрее чем Java на нашей задаче? Наверное потому что он компилирует в бинарник (executable), даже принимая во внимание, что сгенерированный в нем ассемблерный код ужасен по сравнению с тем, который выдает C/C++. И, наверное, здесь таки качественнее работает компилятор, который может быть уверен, что одинаковые куски в выражениях (например, в условиях “m12345 x == 0″) достаточно вычислять только один раз. Это роскошь, которую не может себе позволить Java. Для Java нам пришлось бы писать дополнительный код, который детализирует эти нюансы, а для Хаскеля вот, не надо, умный компилятор.
Комментарии по коду компилятора (который лежит тут) :
1. он генерит full lazy variant (strictness annotations добавлялись руками поверх результата компиляции в исследовательских целях)
2. константы вставлены в user-friendly формате, а не побитово (надо побитово)
3. там внутри код который генерирует также и Java, он неактивен, но есть.
4. код компилятора с комментариями и пустыми строками, и веткой для Java — 238 строк.
5. компилятор достаточно производителен для bin4.obf (4 задание), код не оптимизирован (красоты для).
Улучшения и замечания к компилятору приветствуются. Если необходимо, могу написать аналогичную статью про сам компилятор, а именно про перевод из плоских выражений в выражения со скобками итд, насколько просто это делается.
Спасибо за внимание.