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

Posted by obzor under c/c++

Сейчас буду сравнивать языки программирования на работе с одномерными массивами в операционной системе Linux. Начну с C++.

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

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

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

DeepFlake

Код для генерации тестового массива выглядит так (на языке 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. Освобождать не надо.

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

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-инструкции не генерировались.

Если массив размещять в типе-контейнере 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:par

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

std::execution:par_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.

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

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

• Склонение ФИО
• Удалить все слова из строки
• Как из строки получить время?
• Как из строки удалить определенное слово?
• Кнопка «Удаление» не срабатывает
• Найти и удалить всю cтроку, в которой нет заданной подстроки
• Удаление тегов из строки
• Скопировать html код из текстового файла
• Передать вектор в StrinGrid
• Удаление подстрок из строки за один проход