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

[DeepFlake]

Вижу что моё сообщение здесь про сравнение разных языков программирования на примере расчёта простых чисел набрало 765 просмотров, видимо эта тема интересует многих (или это всё боты?). Поэтому решил продолжить исследование на эту тему.
Сейчас буду сравнивать языки программирования на работе с одномерными массивами в операционной системе Linux. Начну с C++.

Задача, решение которой будет реализовано на нескольких языках, такая: даны два множества целых чисел, в каждом из множеств элементы не повторяются. Множества представляются в виде массивов, где элементы случайно перемешаны. Необходимо проверить, не является ли какое-либо из множеств подмножеством другого.

Проверку будем проводить простым перебором. А что тут сравнивать, подумают некоторые. Цикл в цикле, а в нём проверка a[i]==b[j], и всё. Но доступ к элементам массивов может быть организован по-разному в разных языках. В разных языках по-разному реализована run-time проверка индекса массива. Кроме этого, для хранения массивов можно использовать различные средства: статическая память, динамическая память, тип-контейнер. Это тоже будем сравнивать - с каким массивом работа быстрее. Ещё интересно проверить ускорит ли работу применение SIMD-инструкций (MMX, SSE и т.д.) и применение параллельных функций обработки типов-контейнеров (политика исполнения std::execution:ar). Надо ещё учесть, что в операционной системе Linux наиболее часто используются два компилятора С++, это GNU C++ и Clang C++, поэтому надо сравнить их между собой, чей сгенерированный код лучше. И сравнить несколько версий компиляторов.

Для работы программ необходимо сначала подготовить файлы с тестовыми массивами. В первом массиве будет 500 тысяч элементов (целых чисел), а во-втором - 50 тысяч. Формат файла - текстовый, в каждой строке - по одному числу, в первой строке - длина массива, в дальнейших строках идут элементы друг за другом.

Код для генерации тестового массива выглядит так (на языке C++):

std::vector< long int >     set1;
std::random_device          randdev;
std::size_t                 set1_len;

set1.resize( set1_len );
std::iota( set1.begin(), set1.end(), 1 );
std::shuffle( set1.begin(), set1.end(), randdev );

set1 - контейнер для массива,
set1_len - длина массива,
resize - выделяем место для массива в контейнере,
iota - массив заполняется целыми числами от 1 до set1_len,
shuffle - элементы массива перемешиваются случайным образом.

Полный текст программы для создания тестовых массивов смотрите в прикреплённом архиве в каталоге cpp/genset.
------

Подсчёт времени работы программы ведётся при помощи функции std::chrono::system_clock::now() без учёта времени запуска программы операционной системой, то есть так:

auto start_time = std::chrono::system_clock::now();

// проверка массивов

std::chrono::duration<double> dur = std::chrono::system_clock::now() - start_time;
std::cout << "Продолжительность расчёта: " << dur.count() << " секунд." << std::endl;

------

Компиляцию и запуск делал на компьютере в Debian 10 и ALT Linux 10. В Debian компиляторы GCC 8.3, Clang 7, в ALT - GCC 10.3, Clang 17.
В результатах если никаких пометок, значит компилировал и запускал в Debian, если пометка alt - значит в ALT.
Все программы компилируются с опциями -O или -O3 (для оптимизации).

--------

Считается, что с данными в статической памяти программы работают быстрее всего, поэтому начнём тестирование с массивов в стэке. Выделить память в стэке функции можно вызовом alloca():

std::size_t     set1_len, set2_len;
long int*       set1;

set1 = (long int*) alloca( set1_len * sizeof( long int ) ) ;

Теперь set1 - массив чисел long int, работать с ним можно как set1[i]. Освобождать не надо.

Проверка множеств (в виде массивов) на вхождение друг в друга происходит так (хронометраж только для этого):

bool  isSubSet;
bool  found;

isSubSet = true;
if ( set1_len >= set2_len )
{ // первый массив больше
    for ( std::size_t ind1=0; ind1 < set2_len; ++ind1 )
    {
        found = false;
        for ( std::size_t ind2=0; ind2 < set1_len; ++ind2 )
        {
            if ( set1[ ind2 ] == set2[ ind1 ] )
            {
                // нашли совпадение элементов
                found = true;
                break;
            }
        }
        if ( not found )
        {  // не все элементы set2 принадлежат set1
            isSubSet = false;
            break;
        }
    }
}
else 
{  // второй массив больше
    for ( std::size_t ind1=0; ind1 < set1_len; ++ind1 )
    {  // проход по первому массиву
        found = false;
        for ( std::size_t ind2=0; ind2 < set2_len; ++ind2 )
        {  // проход по второму массиву
            if ( set1[ ind1 ] == set2[ ind2 ] )
            {  // нашли совпадение элементов
                found = true;
                break;
            }
        }
        if ( not found )
        {   // не все элементы set1 принадлежат set2
            isSubSet = false;
                //  не является подмножеством
            break;
        }
    }
}

Исходный текст программы с массивами в стэке смотрите в архиве в cpp/subset_stack.

Результаты запуска программы с массивами в стэке (обратите внимание: в C++ нет автоматической проверки индекса массива) - время вычисления в секундах, чем меньше тем лучше (вычисляется среднее значение по нескольким запускам):

Clang C++ - 14.02215
Clang C++ (alt) - 14.62863
GNU C++ (alt) - 14.6694
GNU C++ - 18.46837

Видно, что результаты почти одинаковые, а 18 секунд у GNU C++ в Debian'е потому что у него не включился оптимизатор (я задавал разные опции, но он не включился).
SIMD-инструкции не генерировались (я дизассемблировал), даже если задавать опции -mmmx и -msse.

--------

Для размещения массива в динамической памяти применяется оператор new:
set1 = new long int [ set1_len ] ;

Потом память надо освободить через delete [].
Сравнение динамических массивов происходит точно так же, как статических:

isSubSet = true;
if ( set1_len >= set2_len )
{ // первый массив больше
    for ( std::size_t ind1=0; ind1 < set2_len; ++ind1 )
    {
        found = false;
        for ( std::size_t ind2=0; ind2 < set1_len; ++ind2 )
        {
            if ( set1[ ind2 ] == set2[ ind1 ] )
            {
                // нашли совпадение элементов
                found = true;
                break;
            }
        }
        if ( not found )
        {  // не все элементы set2 принадлежат set1
            isSubSet = false;
            break;
        }
    }
}
else 
{  // второй массив больше
    for ( std::size_t ind1=0; ind1 < set1_len; ++ind1 )
    {  // проход по первому массиву
        found = false;
        for ( std::size_t ind2=0; ind2 < set2_len; ++ind2 )
        {  // проход по второму массиву
            if ( set1[ ind1 ] == set2[ ind2 ] )
            {  // нашли совпадение элементов
                found = true;
                break;
            }
        }
        if ( not found )
        {   // не все элементы set1 принадлежат set2
            isSubSet = false;
                //  не является подмножеством
            break;
        }
    }
}

Текст программы для массивов в динамической памяти смотрите в архиве в каталоге cpp/subset_dyn.

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

GNU C++ (alt) - 14.96082
Clang C++ (alt) - 15.06715
Clang C++ - 16.04735
GNU C++ - 18.43532

18 секунд у GNU C++ - потому что не включился оптимизатор.
SIMD-инструкции не генерировались.

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

[DeepFlake]

Если массив размещять в типе-контейнере std::vector, то работать с ним надо при помощи функций из <algorithm>, а иначе нет смысла использовать вектор.

std::vector< long int >     set1;
std::vector< long int >     set2;

isSubSet = true;
if ( set1_len >= set2_len )
{ // первый массив больше
    for ( long int el1 : set2 )
    {
        found = std::any_of( set1.begin(), set1.end(),
                    [ &el1 ] ( const long int& el ) { return el1 == el; } );

        if ( not found )
        {  // не все элементы set2 принадлежат set1
            isSubSet = false;
            break;
        }
    }
}
else 
{  // второй массив больше
    for ( long int el1 : set1 )
    {  // проход по первому массиву
        found = std::any_of( set2.begin(), set2.end(),
                    [ &el1 ] ( const long int& el ) { return el1 == el; } );
    
        if ( not found )
        {   // не все элементы set1 принадлежат set2
            isSubSet = false;
                //  не является подмножеством
            break;
        }
    }
}

Можно разрешить компилятору распараллелить обработку массива если использовать параметр std::execution:ar

found = std::any_of( std::execution::par, set2.begin(), set2.end(),
            [ &el1 ] ( const long int& el ) { return el1 == el; } );

std::execution:ar_unseq - разрешает распараллелить и использовать SIMD.
std::execution::unseq - разрешает в однопоточном коде использовать SIMD.
Проверим скорость работы программы со всеми этими параметрами в ALT (в Debian компиляторы это не поддерживают). В секундах:

GNU C++ - 10.44525
GNU C++ (alt) - 11.32513
GNU C++ (alt) паралел. - 11.10373
GNU C++ (alt) паралел.+SIMD - 28
GNU C++ (alt) SIMD - 20
Clang C++ - 10.27182
Clang C++ (alt) паралел. - 11.2052
Clang C++ (alt) паралел.+SIMD - 18

Видно, что параллельный код не генерируется, только однопоточный. SIMD значительно ухудшает производительность.

Текст программы в cpp/subset_par.

-------

Для сравнения проверим скорость работы с вектором когда доступ к его элементам осуществляется через конструкцию for (element : container ):

isSubSet = true;
if ( set1_len >= set2_len )
{ // первый массив больше
    for ( long int el1 : set2 )
    {
        found = false;
        for ( long int el2 : set1 )
        {
            if ( el1 == el2 )
            {
                // нашли совпадение элементов
                found = true;
                break;
            }
        }
        if ( not found )
        {  // не все элементы set2 принадлежат set1
            isSubSet = false;
            break;
        }
    }
}
else 
{  // второй массив больше
    for ( long int el1 : set1 )
    {  // проход по первому массиву
        found = false;
        for ( long int el2 : set2 )
        {  // проход по второму массиву
            if ( el1 == el2 )
            {  // нашли совпадение элементов
                found = true;
                break;
            }
        }
        if ( not found )
        {   // не все элементы set1 принадлежат set2
            isSubSet = false;
                //  не является подмножеством
            break;
        }
    }
}

Текст программы в cpp/subset_vec.

Результаты в секундах:
GNU C++ (alt) - 14.782
GNU C++ - 18.32765
Clang C++ - 18.3533
Clang C++ (alt) опция -O3 - 19.483
Clang C++ (alt) опция -O2 - 19.9807
Clang C++ (alt) опция -O или -O1 или без оптимиз. - завис.

В Debian'е оба компилятора не смогли произвести оптимизацию. В ALT GNU C++ хорошо соптимизировал на уровне скорости статического массива, а Clang C++ не смог, и даже сгенерировал ошибочный код при некоторых опциях.

--------

Соберём все результаты хронометража вместе:

Контейнер (итераторы и алгоритмы STL) - 10-11 сек.
Статический массив - 14 сек.
Контейнер ( for each ) - 14 сек.
Динамический массив - 15 сек.

Результаты для C++:
1. Получается что для работы с одномерными массивами в C++ надо использовать vector, так будет надёжнее и быстрее, причём обязательно в стиле функционального программирования (через итераторы, замыкания, предикаты).
2. Пытаться ускорить обработку при помощи параллельный алгоритмов из STL и SIMD не стоит, компиляторы пока не готовы генерировать оптимальный код.
3. В работе компилятора Clang C++ 17 в ALT Linux 10 обнаружены ошибки. Также ошибки обнаружены в отладчике lldb 17 и компоновщике GNU ld, библиотеке GTK+ 3.

[Vapaamies]

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

в C++ надо использовать vector, так будет надёжнее и быстрее, причём обязательно в стиле функционального программирования (через итераторы, замыкания, предикаты).

Спасибо за наводку. Буду теперь знать, что подмножество того, что я называю объектной алгеброй, реализовано не только в Java и JS, но и в C++.

Сообщения на форумах иногда бывают полезны не тем, что задумано автором, да.