суббота, 19 января 2013 г.

Продолжаю щупать OCaml

Теперь решил написать простенькую программу на OCaml, провести замеры и сравнить с аналогичной программой на плюсах.
В качестве примера был взят алгоритм "Решето Эратосфена", т.к. он простой как кирпич. Задача требует написать функцию, принимающую на вход число и возвращающую контейнер со всеми простыми числами меньше заданного. Использовать можно только стандартную библиотеку.

Общие впечатления от OCaml примерно такие:
  • отвратительный ocamldoc, который поддерживает всего несколько тегов doxygen
  • невнятные сообщения об ошибках. Например, если допустить синтаксическую ошибку, а такое бывает часто, компилятор скажет что-то вроде
    File "sieve_of_eratosthenes.ml", line 92, characters 1-3:
    Error: Syntax error

    Ни ожидаемого токена, ни какого-либо намёка о причине ошибке нет (подсказки есть только в некоторых случаях)
  • убогая стандартная библиотека. Это то, что шокировало меня больше всего. Большинство контейнеров нерасширяемо, нет поддержки отложенного копирования (например при конкатенации списков).
В общем сплошное разочарование. Сама функция поиска простых чисел без комментариев и пустых строк выглядит так:

let sieve_of_eratosthenes = fun x ->
    let sowing = fun a max ->
        let rec sowing_tail = fun a i step max ->
            if i < max then
                (Array.set a i false;
                sowing_tail a (i + step) step max)
        in
        let rec sowing_head = fun a i max ->
            if i * i < max then
                (if (Array.get a i) = true then
                    sowing_tail a (i + i) i max;
                sowing_head a (i + 1) max
                )
        in
        sowing_head a 2 max
    in
    let a = Array.make (x + 1) true;
    in
    (Array.set a 0 false;
    Array.set a 1 false;
    sowing a (Array.length a)
    );
    let rec filter_prime_numbers = fun a l i ->
        if i > 1 then
        (if (Array.get a i) = true then
            (filter_prime_numbers a (i :: l) (i - 1);
            )
        else
            (filter_prime_numbers a l (i - 1);
            )
        )
        else
         l
    in
    filter_prime_numbers a [] ((Array.length a) - 1);
;;


а так на C++:

typedef std::unique_ptr<std::list<int>> IntList;
IntList sieveOfEratosthenes(unsigned int max)
{
    std::vector<bool> numbers(++max, true);
    numbers[0] = false;
    numbers[1] = false;
    for(unsigned int i = 2; i * i < max; i++)
        if( numbers[i] )
            for( unsigned int j = i + i; j < max; j += i)
                numbers[j] = false;
    IntList res(new std::list<int>);
    for( unsigned int i = 2; i < max; i++)
        if( numbers[i] )
            res->push_back(i);
    return std::move(res);
}



36 строк OCaml'а против 16 C++. В оправдание OCaml'у можно сказать, что при использовании циклов вместо рекурсивных вложенных функций объём кода заметно сократился бы. Но использовать цикл в функциональном языке очень некрасиво.

А теперь самая интересная вещь. Я замерил параметры времени исполнения программ:
Максимальное числоРежим компиляцииВремя исполнения, с.Потребляемая память, Мб.
1 000 000 O00.1414.9
O30.0314.8
zinc0.4151
native0.0550.4
10 000 000 O01.4289.7
O30.2789.7
zinc4.01383.2
native0.55382.7
100 000 000 O014.46754.8
O32.79754.8
zinc39.113630.7
native5.863626.9
1 000 000 000 O0157.456687.6
O328.146687.6
zinc-Fatal error: exception Out_of_memory
native-Fatal error: exception Out_of_memory

Подробнее о способах компиляции.

C++ компилировалось строкой
g++ -std=c++0x -Wall -pedantic -Werror -O?
где -O? - соответствующий ключ оптимизации.

zinc означает, что программа на OCaml собиралась для виртуальной машины:
ocamlc -w "+A" -warn-error "+A"

а native - что в качестве исполняемого elf
ocamlopt -w "+A" -warn-error "+A"

Что удивило в компиляторе OCaml - это отсутствие выбора агрессивности оптимизаций.

Из таблицы видно, что с оптимизациями -O3 плюсовая программа быстрее OCaml'овской примерно в 1.9 раза а расход памяти меньше от ~3.4 до ~4.81 раз. Из-за слишком большого расхода памяти программа на OCaml не смогла обработать 1 000 000 000 чисел.

Вообще говоря, режим -O0 в C++ и  скорость работы zinc сравнивать не очень корректно, но целью было показать различие в скорости при работе с наименьшим числом оптимизаций. Разница в расходе памяти почти не различается, а вот скорость исполнения плюсов значительно выше (Чуть меньше чем в 4 раза).

Сравнивая режим native и -O0 видно, что нативная оптимизированная  программа на OCaml быстрее нативной неоптимизированной программы на C++ в среднем в ~2.6 раза

Теперь о качестве оптимизатора. В C++ программа ускорилась в среднем в 5.2 раза. И это не предел, т.к. помимо -O3 есть ещё ряд ключей, ускоряющих программу. Результат OCaml веселей. Тут программа ускорилась в 7.2 раза. Но если Вы подумали, что оптимизатор OCaml лучше, то это совсем не так. Такой результат объясняется тормозами виртуальной машины zinc.

Для себя я сделал следующие выводы: OCaml пытается балансировать между функциональным и императивным языком. Но из-за этого не преуспевает ни там ни там. Как академический проект он очень интересен, но решать вычислительную задачу я бы на нём не стал.

Исходники алгоритмов и тестов можно посмотреть здесь.

2 комментария:

  1. Валялось, не помню откуда.

    let count = 200000

    let primes =
    let primes = Array.create (max count 3) 0 in
    primes.(0) <- 2; primes.(1) <- 3; primes.(2) <- 5; primes

    let rec is_prime i prime bound =
    if primes.(i) > bd then true
    else if prime mod primes.(i) = 0 then false else is_prime (succ i) pr bd

    let rec prime_n psize nr tog =
    if psize < count then
    let psize' =
    if is_prime 2 nr (truncate (sqrt (float nr))) then begin
    primes.(psize) <- nr; succ psize end
    else psize in
    prime_n psize' (nr + tog) (6 - tog)

    let _ = prime_n 3 7 4; Printf.printf "prime %d: %d\n" count primes.(pred count)

    ОтветитьУдалить
    Ответы
    1. Ну, вообще, программа не компилируется - необъвленные переменные, но выглядит по прятнее, да.

      На самом деле, сейчас я уже понимаю, что подобный тест - ни о чём. Как минимум нужно иметь набор бенчмарков по типу SPEC и прогнать компилятор на нём. Тогда можно будет говорить о хоть каком-то сравнении. Но для двух разных языков это крайне сложно.

      Удалить