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

[DeepFlake]

В сообщении "Сравнение языков на массивах. Часть 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.

----------

Массив в стеке выделяется в 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 дольше происходит разыменование указателя и скрытая проверка индекса начинает тормозить.

-------
Продолжение в следующем сообщении

[DeepFlake]

В 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.

[p51x]

Сообщение от DeepFlake

и в C

VLA

[p51x]

Сообщение от DeepFlake

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

Они порождают зависимости по коду. И тут все очень зависит от алгоритма, предсказателя переходов проца и компилятора.

Сообщение от DeepFlake

При помощи оператора new нельзя создать массив

Можно

Сообщение от DeepFlake

потому что в язые C и С++ указатель на массив это то же самое, что указатель на первый элемент массива

Нет. Причина в вызове конструкторов/десрукторов, а не в указателях. Тем более для примитивных типов не совсем правильно, но работать будет.

Сообщение от DeepFlake

В Ada дольше происходит разыменование указателя и скрытая проверка индекса начинает тормозить.

Так вы же говорил, что влияние минимальное... Вы можете подтвердить это? Вы раскрытили цикл, чтобы уменьшить кол-во проверок и время изменилось?

Сообщение от DeepFlake

1. Если массив небольшой и фиксированной длины, то можно разместить его в стеке.

А для других языков это не так?

Сообщение от DeepFlake

Версия компилятора GNAT, которая в ALT, производит медленный код при работе с типами-контейнерами, я подозреваю что это из чисто маркетинговых соображений, ведь GNAT - это демо-версия коммерческого продукта GNAT Pro.

И кроме ваших думок есть основания? Вы дизасмнули код? Вы сравниливерсии?

[DeepFlake]

Сейчас посмотрим как быстро работают с массивами программы на Free Pascal. Free Pascal - язык, используемый в визуальном RAD-инструменте Lazarus. Хотя на Lazarus'е можно сделать любую программу, но ускорение разработки происходит, в основном, только для GUI-программ (с графическим интерфейсом). Не совсем корректно сравнивать Free Pascal и С++, Ada, Java, потому что у них разные области применения, более правильно сравнивать Lazarus со своими конкурентами, тоже визуальными RAD-инструментами, например, с Gambas, KBasic, MonoDevelop.

Lazarus и Free Pascal производят неоднозначное впечатление. С одной стороны, вроде бы, это простые и удобные инструменты, позволяющие быстро создать программу, а с другой стороны, не всё в них удобно, программы получаются не слишком надёжные и медленно работающие.

Например, при разработке GUI-программ самое важное - так расположить оконные элементы, чтобы они сами подстраивались под размер окна. Обычно это достигается использованием менеджеров раскладки (layout manager, arrangement), однако менеджеры раскладки удобно когда GUI пишешь в виде кода, и неудобно их использовать в визуальном редакторе окон, потому что приходится делать менеджер в менеджере и специальные настройки для некоторых ячеек. Поэтому в Lazarus'е в редакторе окон используются другие способы автоматической раскладки, которые гораздо удобнее для визуального создания GUI: первый на основе выравнивания (align), второй - на основе якорей (anchor). На практике приходится применять комбинацию из этих методов. Но проблема в том, что эти способы не так-то легко изучить, зато легко забыть, если не программировать в Lazarus'е постоянно.

Free Pascal - странная смесь языков С и Java с паскалевским синтаксисом.
По-умолчанию компилятор не создаёт в коде никаких run-time проверок (индекса, переполнения, стека), поэтому я их включил опциями для честного сравнения с другими языками.
В Debian Free Pascal версии 3.0.4, в ALT Linux 10 - 3.2.2.

-------

Я не смог найти способ разместить массив произвольного размера в стеке на Free Pascal'е, поэтому статический массив фиксированного размера сделал как глобальную переменную.

var
    set1 : array [ 0 .. 500000-1 ] of longint;
    set2 : array [ 0 .. 50000-1 ] of longint;
    set1_len, set2_len : longint;
    found, isSubSet: boolean;
    el_1, el_2: longint;
begin
    isSubSet := true;
    if set1_len >= set2_len
    then // первый массив больше
        begin
        for el_1 in set2
        do  // проход по второму массиву
            begin
            found := false;
            for el_2 in set1
            do  // проход по первому массиву
                begin
                if el_2 = el_1
                then // нашли совпадение элементов
                    begin 
                    found := true;
                    break;
                    end
                end;
            if not found
            then // не все элементы set2 принадлежат set1
                begin
                isSubSet := false;
                    // не является подмножеством
                break;
                end
            end;
        end
    else // второй массив больше
        begin
        for el_1 in set1
        do // проход по первому массиву
            begin
            found := false;
            for el_2 in set2
            do // проход по второму массиву
                begin
                if el_2 = el_1
                then // нашли совпадение элементов
                    begin 
                    found := true;
                    break;
                    end
                end;
            if not found
            then // не все элементы set1 принадлежат set2
                begin
                isSubSet := false;
                    // не является подмножеством
                break;
                end
            end;
        end;

Текст - в fp/subset_stat.
Результаты замеров в секундах:
Free Pascal - 49.4955
Free Pascal (alt) - 51.361

-------

Динамический массив создавать при помощи функции new можно только фиксированного размера:

type
    tArr1 = array [ 0 .. 500000-1 ] of longint;
    tArr2 = array [ 0 .. 50000-1 ] of longint;
var
    set1 : ^ tArr1;
    set2 : ^ tArr2;
    set1_len, set2_len : longint;
    found, isSubSet: boolean;
    el_1, el_2: longint;
begin
// создание
    new( set1 );
    new( set2 );

// заполнение через set1^[ индекс ] := число;

    isSubSet := true;
    if set1_len >= set2_len
    then // первый массив больше
        begin
        for el_1 in set2^
        do  // проход по второму массиву
            begin
            found := false;
            for el_2 in set1^
            do  // проход по первому массиву
                begin
                if el_2 = el_1
                then // нашли совпадение элементов
                    begin 
                    found := true;
                    break;
                    end
                end;
            if not found
            then // не все элементы set2 принадлежат set1
                begin
                isSubSet := false;
                    // не является подмножеством
                break;
                end
            end;
        end
    else // второй массив больше
        begin
        for el_1 in set1^
        do // проход по первому массиву
            begin
            found := false;
            for el_2 in set2^
            do // проход по второму массиву
                begin
                if el_2 = el_1
                then // нашли совпадение элементов
                    begin 
                    found := true;
                    break;
                    end
                end;
            if not found
            then // не все элементы set1 принадлежат set2
                begin
                isSubSet := false;
                    // не является подмножеством
                break;
                end
            end;
        end;

    dispose( set1 );
    dispose( set2 );

Текст в fp/subset_dyn.
Результаты:
Free Pascal - 51.9165
Free Pascal (alt) - 64.342

[DeepFlake]

Если надо создать динамический массив произвольного размера, то следует использовать функции GetMem, FreeMem, ReallocMem, однако в этом случае не производится run-time проверка индекса массива на диапазон.

var
    set1, set2 : ^ longint;
    set1_len, set2_len : longint;
    found, isSubSet: boolean;
    ind_1, ind_2: longint;
begin
    // создание массива
    getmem( set1, set1_len * sizeof( longint ) );
    getmem( set2, set2_len * sizeof( longint ) );

    // заполнение через set1[ индекс ] := число;

    isSubSet := true;
    if set1_len >= set2_len
    then // первый массив больше
        begin
        for ind_1:=0 to set2_len-1
        do  // проход по второму массиву
            begin
            found := false;
            for ind_2:=0 to set1_len-1
            do  // проход по первому массиву
                begin
                if set1[ ind_2 ] = set2[ ind_1 ]
                then // нашли совпадение элементов
                    begin 
                    found := true;
                    break;
                    end
                end;
            if not found
            then // не все элементы set2 принадлежат set1
                begin
                isSubSet := false;
                    // не является подмножеством
                break;
                end
            end;
        end
    else // второй массив больше
        begin
        for ind_1:=0 to set1_len-1
        do // проход по первому массиву
            begin
            found := false;
            for ind_2:=0 to set2_len-1
            do // проход по второму массиву
                begin
                if set2[ ind_2 ] = set1[ ind_1 ]
                then // нашли совпадение элементов
                    begin 
                    found := true;
                    break;
                    end
                end;
            if not found
            then // не все элементы set1 принадлежат set2
                begin
                isSubSet := false;
                    // не является подмножеством
                break;
                end
            end;
        end;

    freemem( set1 );
    freemem( set2 );

Текст - в fp/subset_dyn2.
Результаты:
Free Pascal - 36.8815
Free Pascal (alt) - 38.438

Почему в этом случае скорость не как у С, ведь проверка индекса на диапазон не производится? Оказывается производится проверка индекса на переполнение.

------

Free Pascal похож на Java ещё тем, что в язык встроен объект-массив. Он является управляемым объектом (managed), то есть память освобождается автоматически. Объект-массив может в процессе работы программы менять размер и быть неровным.

var
    set1, set2 : array of longint;
    set1_len, set2_len : longint;
    found, isSubSet: boolean;
    el_1, el_2: longint;
begin
    // выделение памяти
    setlength( set1, set1_len);
    setlength( set2, set2_len);

    // заполнение через set1[ индекс ] := число;

    isSubSet := true;
    if set1_len >= set2_len
    then // первый массив больше
        begin
        for el_1 in set2
        do  // проход по второму массиву
            begin
            found := false;
            for el_2 in set1
            do  // проход по первому массиву
                begin
                if el_2 = el_1
                then // нашли совпадение элементов
                    begin 
                    found := true;
                    break;
                    end
                end;
            if not found
            then // не все элементы set2 принадлежат set1
                begin
                isSubSet := false;
                    // не является подмножеством
                break;
                end
            end;
        end
    else // второй массив больше
        begin
        for el_1 in set1
        do // проход по первому массиву
            begin
            found := false;
            for el_2 in set2
            do // проход по второму массиву
                begin
                if el_2 = el_1
                then // нашли совпадение элементов
                    begin 
                    found := true;
                    break;
                    end
                end;
            if not found
            then // не все элементы set1 принадлежат set2
                begin
                isSubSet := false;
                    // не является подмножеством
                break;
                end
            end;
        end;

Текст - в fp/subset_obj.
Результаты:
Free Pascal - 89.4925
Free Pascal (alt) - 93.3365
Free Pascal (без проверки индекса) - 31.464
Free Pascal (alt) (без проверки индекса) - 32.849

Проверка индекса на вхождение в диапазон производится во Free Pascal'е неэффективно.

-------

А что если в процессе работы программы необходимо добавлять/удалять/вставлять элеиенты в массиве по определённой позиции? Для этого есть класс-список, для которого произведена специализация. В пакете lazutils есть модуль IntegerList, а в нём готовые специализированные классы-списки для целых чисел:

type
  TByteList = class(specialize TFPGList<Byte>)
  public
    procedure Sort; overload;
  end;

  TWordList = class(specialize TFPGList<Word>)
  public
    procedure Sort; overload;
  end;

  TCardinalList = class(specialize TFPGList<Cardinal>)
  public
    procedure Sort; overload;
  end;

  TIntegerList = class(specialize TFPGList<Integer>)
  public
    procedure Sort; overload;
  end;

  TInt64List = class(specialize TFPGList<Int64>)
  public
    procedure Sort; overload;
  end;

Эти классы по функциям похожи на std::vector из C++.

uses sysutils,
    IntegerList 
        // in lazutils package
    ;

var
    set1, set2 : TInt64List;
    set1_len, set2_len : longint;
    found, isSubSet: boolean;
    el_1, el_2: int64;
begin
    // Создание объектов
    set1 := TInt64List.Create;
    set2 := TInt64List.Create;

    // заполнение через set1.Add( число );

    isSubSet := true;
    if set1_len >= set2_len
    then // первый массив больше
        begin
        for el_1 in set2
        do  // проход по второму массиву
            begin
            found := false;
            for el_2 in set1
            do  // проход по первому массиву
                begin
                if el_2 = el_1
                then // нашли совпадение элементов
                    begin 
                    found := true;
                    break;
                    end
                end;
            if not found
            then // не все элементы set2 принадлежат set1
                begin
                isSubSet := false;
                    // не является подмножеством
                break;
                end
            end;
        end
    else // второй массив больше
        begin
        for el_1 in set1
        do // проход по первому массиву
            begin
            found := false;
            for el_2 in set2
            do // проход по второму массиву
                begin
                if el_2 = el_1
                then // нашли совпадение элементов
                    begin 
                    found := true;
                    break;
                    end
                end;
            if not found
            then // не все элементы set1 принадлежат set2
                begin
                isSubSet := false;
                    // не является подмножеством
                break;
                end
            end;
        end;

    // уничтожение объектов
    FreeAndNil( set1 );
    FreeAndNil( set2 );

Текст - в fp/subset_intlist.
Результаты:
Free Pascal - 166.3015
Free Pascal (alt) - 174.285

--------

[DeepFlake]

Соберём все результаты для Free Pascal вместе:

Статический массив (фиксир.) - 49.4955
Динамический массив (фиксир.) - 51.9165
Динамический массив (произв., без проверки индекса) - 36.8815
Объект-массив - 89.4925
IntegerList - 166.3015

Что можно сказать здесь? Проверка индекса на диапазон производится неэффективно, а сам компилятор - туповатый. Но Free Pascal никогда и не позиционировали как инструмент для высокопроизводительных расчётов.
Впрочем, если кому-то необходимо быстрые вычисления с 2-х, 3-х, 4-х мерными матрицами и векторами во Free Pascal, то в нём для этого есть модуль matrix. Также есть отдельные модули для работы с векторами и матрицами из чисел произвольной точности.