Продолжаю щупать 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	O0	0.14	14.9
	O3	0.03	14.8
	zinc	0.41	51
	native	0.05	50.4
10 000 000	O0	1.42	89.7
	O3	0.27	89.7
	zinc	4.01	383.2
	native	0.55	382.7
100 000 000	O0	14.46	754.8
	O3	2.79	754.8
	zinc	39.11	3630.7
	native	5.86	3626.9
1 000 000 000	O0	157.45	6687.6
	O3	28.14	6687.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 пытается балансировать между функциональным и императивным языком. Но из-за этого не преуспевает ни там ни там. Как академический проект он очень интересен, но решать вычислительную задачу я бы на нём не стал.

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