Haskell и Java — сравнение на реальной задаче (спутники, ICFP Contest)

    Сегодня на хабре проходила статья про 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 выглядит так (значащий фрагмент):

    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 задание), код не оптимизирован (красоты для).

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

    Спасибо за внимание.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 5

      –1
      поставьте пожалуйста хабракат)
        +2
        а можно добавить еще вариант на C/C++?
          0
          это сделать можно, но пока я сделаю это сам, заинтересованные читатели могут меня опередить.
            0
            Заинтересованные читатели меня не опередили. Поэтому я сделал С++ тест сам.
            Производилось всё на другом компе, поэтому дам сравнительные скорости на нем.
            Делалось 15 итераций по 45000 тиков.

            Haskell (ghc -O2): в среднем 6400 мсек = 105К итераций/сек
            C++ (g++ -O3): в среднем 1700 мсек = 400К итераций/сек.

            Я варьировал всякие опции для ghc, но оно особо не улучшило.
            Затем, я запускал «time ./BenchVM». И смотрел на цифру, и снова запускал.
            Время работы бинарника иногда подымалось до 7500 секунд, но потом опускалось до 6300-6500.

            Вот примерный вывод (Хаскельный вариант):
            
            93401980065e8, o39 = 0.0, o100 = 5.219733041393699e7, o101 = 3.800730001674274e8}
               4,168,385,896 bytes allocated in the heap
                   6,053,464 bytes copied during GC
                      48,272 bytes maximum residency (2 sample(s))
                      36,384 bytes maximum slop
                           2 MB total memory in use (0 MB lost due to fragmentation)
            
              Generation 0:  7954 collections,     0 parallel,  0.09s,  0.08s elapsed
              Generation 1:     2 collections,     0 parallel,  0.00s,  0.00s elapsed
            
              INIT  time    0.00s  (  0.00s elapsed)
              MUT   time    6.13s  (  6.18s elapsed)
              GC    time    0.09s  (  0.08s elapsed)
              EXIT  time    0.00s  (  0.00s elapsed)
              Total time    6.22s  (  6.25s elapsed)
            
              %GC time       1.5%  (1.2% elapsed)
            
              Alloc rate    680,041,962 bytes per MUT second
            
              Productivity  98.5% of total user, 98.0% of total elapsed
            
            
            real	0m6.256s
            user	0m6.223s
            sys	0m0.023s
            
            


            Вот примерный вывод (С++ вариант):

            $ time ./vm 
            done1
            done1
            done1
            done1
            done1
            done1
            done1
            done1
            done1
            done1
            done1
            done1
            done1
            done1
            done1
            
            real	0m1.847s
            user	0m1.833s
            sys	0m0.000s
            
        • НЛО прилетело и опубликовало эту надпись здесь

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

          Самое читаемое