Сравнение языков на массивах. Часть 2

Posted by obzor under Заметки

В сообщении «Сравнение языков на массивах. Часть 1» в этом разделе описывались программы на языке C++, а в этом сообщении будут рассматриваться программы на языке Ada. Язык Ada по возможностям и стилю программирования очень похож на C++, но более надёжный. Он применяется там, где цена ошибки высока. Так же как для С++, программы будут компилироваться и запускаться в двух операционных системах на основе Linux — Debian 10 и ALT Linux 10. Компилятор языка Ada — GNAT от компании AdaCore. В Debian GNAT версии 8.3, а в ALT — 10.3 .

Все программы компилировались с опцией оптимизации -O2 или -O3, а иначе скорость их работы становится позорно низкой. Если в результатах замеров времени никаких пометок — значит в Debian, если пометка (alt) — значит в ALT.

В отличие от C++ в Ada есть run-time проверки, в том числе проверка индекса массива на выход из допустимого диапазона. Однако они реализованы достаточно эффективно и не сильно снижают производительность программ.

В Ada так же будем проверять скорость работы со статическим массивом, динамическим массивом и массивом в типе-контейнере Vector.
Тестовые массивы те же, один на 500000 элементов, второй на 50000.

DeepFlake

Массив в стеке выделяется в Ada несколько необычно, такого нет ни в одном языке. Во всех языках длина статического массива должна быть известна заранее, на этапе компиляции, то есть в Pascal’е нельзя так написать (и в C ):

procedure P1( n: integer )
var
    a1: array[ 1 .. n ] of real;
begin
  ...

а в Ada — можно.

procedure P1( n: integer )
is
    a1: array( 1 .. n ) of real;
begin
  ...

Здесь память для массива a1 выделяется из стека, причём длина массива заранее неизвестна.

Код сравнения двух множеств на предмет вхождения одного множества в другое, когда множества представлены в виде статических массивов:

found : boolean;
set1_len, set2_len : long_integer;
isSubSet : boolean;
set1 : array( 1 .. set1_len) of long_integer;
set2 : array( 1 .. set2_len) of long_integer;

isSubSet := true;
if set1_len >= set2_len
then -- первый массив больше
    for ind1 in set2'Range
    loop
        found := false;
        for ind2 in set1'Range
        loop
            if set1( ind2 ) = set2( ind1 )
            then
                -- нашли совпадение элементов
                found := true;
                exit;
            end if;
        end loop;
        if not found
        then  -- не все элементы set2 принадлежат set1
            isSubSet := false;
            exit;
        end if;
    end loop;
else -- второй массив больше
    for ind1 in set1'Range
    loop -- проход по первому массиву
        found := false;
        for ind2 in set2'Range
        loop -- проход по второму массиву
            if set1( ind1 ) = set2( ind2 )
            then -- нашли совпадение элементов
                found := true;
                exit;
            end if;
        end loop;
        if not found
        then -- не все элементы set1 принадлежат set2
            isSubSet := false;
                -- не является подмножеством
            exit;
        end if;
    end loop;
end if;

Текст программы — в прикреплении к сообщению в ada/subset_stack.

Результаты замеров времени работы программы в секундах (среднее значение):

GNAT — 13.66483
GNAT (alt) — 14.77729

В ALT почему-то все программы работают медленнее, хоть на каком языке написанные. Это система виновата, не компиляторы.
Сравним эти данные с результатами замеров для языка C++ из моего предыдущего сообщения:
Clang C++ — 14.02215
Clang C++ (alt) — 14.62863
GNU C++ (alt) — 14.6694

То есть Ada в Debian обогнал C++ несмотря на то, что в Ada run-time проверки. По крайней мере Ada не медленнее C++. Это очень хороший результат.

——

Динамический массив в языке Ada создаётся как в C++ и Pascal — вызывается оператор new, а уничтожается вызовом специальной функции. Отличие от C++ такое: в C++ для одиночных объектов память выделяется при помощи new, а для массивов — new []. При помощи оператора new нельзя создать массив потому что в язые C и С++ указатель на массив это то же самое, что указатель на первый элемент массива. То есть new создаст не массив, а только один элемент массива. А в Ada всё по-нормальному, оператор new может создавать как одиночные объекты, так и массивы.

type tLongIntArray
is
    array ( long_integer range <> ) of long_integer;

type tptrLongIntArray
is
    access tLongIntArray;

set1, set2 : tptrLongIntArray;

Здесь объявляется тип-массив произвольной длины из целых чисел, потом тип-указатель на такой массив, потом set1 и set2 — указатели на массив произвольной длины.
Выделение памяти под массивы из хипа:

set1 := new tLongIntArray ( 1 .. set1_len );
set2 := new tLongIntArray ( 1 .. set2_len );

Здесь мы конкретизируем длину массивов.
Освобождение динамической памяти производится функцией unchecked_deallocation, правда это функция с шаблоном типа, который надо освободить.

Код проверки множеств для динамических массивов ничем не отличается от кода для статических массивов:

isSubSet := true;
if set1_len >= set2_len
then -- первый массив больше
    for ind1 in set2'Range
    loop
        found := false;
        for ind2 in set1'Range
        loop
            if set1( ind2 ) = set2( ind1 )
            then
                -- нашли совпадение элементов
                found := true;
                exit;
            end if;
        end loop;
        if not found
        then  -- не все элементы set2 принадлежат set1
            isSubSet := false;
            exit;
        end if;
    end loop;
else -- второй массив больше
    for ind1 in set1'Range
    loop -- проход по первому массиву
        found := false;
        for ind2 in set2'Range
        loop -- проход по второму массиву
            if set1( ind1 ) = set2( ind2 )
            then -- нашли совпадение элементов
                found := true;
                exit;
            end if;
        end loop;
        if not found
        then -- не все элементы set1 принадлежат set2
            isSubSet := false;
                -- не является подмножеством
            exit;
        end if;
    end loop;
end if;

Исходный текст — в ada/subset_dyn.

Результаты замеров времени запуска в секундах:
GNAT — 19.703419
GNAT (alt) — 20.8893

Видно, что для Ada замедление работы с динамическими массивами по сравнению со статическими гораздо больше чем для C++. Для Ada замедление на 46%, для С++ — на 7%. В Ada дольше происходит разыменование указателя и скрытая проверка индекса начинает тормозить.

В Ada, так же как в C++, есть разнообразные типы-контейнеры и функции для работы с ними. Но функции называются непривычно, все привыкли к iter, map, filter, take, drop, enumerate и т.д., а в Ada нет таких названий. Сами функции есть, но называются по-другому.
В Ada отсутствуют замыкания и функциональные объекты, но вместо них используют внутренние функции (функция внутри функции). Внутренняя функция имеет доступ к внешним переменным, как и замыкание. Дело в том, что замыкание может спровоцировать неправильную работу программы, если она захватит объект и будет работать с ним, а он через какое-то время уничтожится, замыкание это не заметит и будет ошибка. С внутренними функциями такого не будет.

Типы-контейнеры являются настраиваемыми типами, то есть надо указывать тип элементов. Конкретизация вектора происходит так:

package LongInteger_Vectors
is 
    new ada.containers.vectors( Index_Type => natural,
        Element_Type => long_integer );

set1, set2 : LongInteger_Vectors.Vector;

Здесь объявляется новый модуль LongInteger_Vectors с векторами из целых чисел, то же самое что на C++
typedef std::vector<long int> LongInteger_Vector;

Заполняется вектор функцией set1.append() — это добавляет в конец.
Поиск нужного элемента производится функцией set1.Find( el1 ).

Вот код программы для векторов:

isSubSet := true;
if set1_len >= set2_len
then -- первый массив больше
    for el1 of set2
    loop
        found := set1.Find( el1 ) /= LongInteger_Vectors.No_Element;
        if not found
        then  -- не все элементы set2 принадлежат set1
            isSubSet := false;
            exit;
        end if;
    end loop;
else -- второй массив больше
    for el1 of set1
    loop -- проход по первому массиву
        found := set2.Find( el1 ) /= LongInteger_Vectors.No_Element;
        if not found
        then -- не все элементы set1 принадлежат set2
            isSubSet := false;
                -- не является подмножеством
            exit;
        end if;
    end loop;
end if;

Текст программы — в ada/subset_vec_find.

Результаты запусков для векторов в секундах:
GNAT — 13.6729
GNAT (alt) — 21.3264

В Debian программа на Ada отработала с той же скоростью, что и со статическим массивом (13 секунд), это хороший результат. В ALT версия GNAT более новая, но скорость работы как с динамическим массивом (20 секунд).
Программа на С++ работает с векторами быстрее (10 секунд).

——-

Работа с вектром в стиле for each:

isSubSet := true;
if set1_len >= set2_len
then -- первый массив больше
    for el1 of set2
    loop
        found := false;
        for el2 of set1
        loop
            if el1 = el2
            then
                -- нашли совпадение элементов
                found := true;
                exit;
            end if;
        end loop;
        if not found
        then  -- не все элементы set2 принадлежат set1
            isSubSet := false;
            exit;
        end if;
    end loop;
else -- второй массив больше
    for el1 of set1
    loop -- проход по первому массиву
        found := false;
        for el2 of set2
        loop -- проход по второму массиву
            if el1 = el2
            then -- нашли совпадение элементов
                found := true;
                exit;
            end if;
        end loop;
        if not found
        then -- не все элементы set1 принадлежат set2
            isSubSet := false;
                -- не является подмножеством
            exit;
        end if;
    end loop;
end if;

Текст в ada/subset_vec.

Результаты:

GNAT — 24.12821
GNAT (alt) — 38.6873

Очень медленно.

———

Соединим все результаты замеров для языка Ada вместе:
Статический массив — 13.664
Динамический массив — 19.703
Вектор с алгоритмом — 13.6729
Вектор с for each — 24.12821

Напомню результаты для языка C++:
Вектор (алгоритм STL) — 10-11 сек.
Статический массив — 14 сек.
Вектор ( for each ) — 14 сек.
Динамический массив — 15 сек.

Выводы можно такие сделать для языка Ada:
1. Если массив небольшой и фиксированной длины, то можно разместить его в стеке.
2. Если массив большой или его длина может меняться в процессе работы, то размещать в Vector и работать с ним через встроенные функции (не через for).
3. Версия компилятора GNAT, которая в ALT, производит медленный код при работе с типами-контейнерами, я подозреваю что это из чисто маркетинговых соображений, ведь GNAT — это демо-версия коммерческого продукта GNAT Pro.

тема на форуме

Похожие статьи

• Сравнение языков по скорости
• Разность двух полей Memo
• Заполнение ListView из XAML
• В какой момент происходит чтение app.config ?
• С чего начать изучение и переход с++ из Delphi
• Просмотрщик фотографий на C#
• Число в кубе
• Программа поиска анаграмм
• Программа для создания кроссвордов
• Какие бывают компиляторы на С++?