Сравнение производительности параллельной сортировки: std::sort, std::execution::par и OpenMP ⇐ C++

[Anonymous]

Я экспериментировал с различными методами параллельной сортировки в C++ и провел сравнение производительности между:

• обычным std::sort< /li>
  Параллельная std::sort с использованием std::execution::par
• Пользовательская параллельная сортировка с использованием OpenMP >

Я провел тесты на наборе данных из 20 миллионов целых чисел. Вот затраченное время для каждого метода сортировки:

Код: Выделить всё

$ g++ -std=c++20 -fopenmp -pthread sort.cpp -o sort && ./sort
Building a vector of random integers...
Sorting with std::sort...
Elapsed time: 6.1555 s
Sorting with std::sort and std::execution::par...
Elapsed time: 6.45905 s
Sorting with OpenMP...
Elapsed time: 1.05043 s

$ g++ -std=c++20 -fopenmp -pthread sort.cpp -O3 -o sort
Building a vector of random integers...
Sorting with std::sort...
Elapsed time: 1.1355 s
Sorting with std::sort and std::execution::par...
Elapsed time: 1.14028 s
Sorting with OpenMP...
Elapsed time: 0.224919 s

g++ -v 2>&1 | tail -n1
gcc version 11.4.0 (Ubuntu 11.4.0-1ubuntu1~22.04)

Реализация OpenMP существенно обогнала остальные, что было удивительно, особенно если учесть, что параллельная обработка std::sort с std::execution::par заняла даже длиннее обычного std::sort. Мне интересно понять основные причины таких результатов производительности.
Вот код, который я использовал для теста:

Код: Выделить всё

#include 
#include 
#include 
#include 
#include 
#include 
#include  // Include the OpenMP header

#define N 20'000'000

bool is_sorted(std::vector &v) {
for (int i = 0; i < v.size() - 1; i++)
if (v[i] > v[i + 1]) return false;
return true;
}

// Fixed solution from https://stackoverflow.com/a/56079287/2612235
void omp_sort(std::vector &v) {
const int data_count = v.size();
auto get_block_edge = [data_count](int i, int n) {
return data_count * i / n;
};

int blocks = 0;
#pragma omp parallel
{
blocks = omp_get_num_threads();
int block = omp_get_thread_num();
int start = get_block_edge(block, blocks);
int finish = get_block_edge(block + 1, blocks);
std::sort(std::begin(v) + start, std::begin(v) + finish);
}

for (int merge_step = 1; merge_step < blocks; merge_step *= 2) {
#pragma omp parallel for
for (int i = 0; i < blocks; i += 2 * merge_step) {
int start = get_block_edge(i, blocks);
int mid = std::min(get_block_edge(i + merge_step, blocks), data_count);
int finish = std::min(get_block_edge(i + 2 * merge_step, blocks), data_count);
if (mid < finish)
std::inplace_merge(std::begin(v) + start, std::begin(v) + mid, std::begin(v) + finish);
}
}
}

int main()
{
std::cout 

Подробнее здесь: [url]https://stackoverflow.com/questions/77848856/comparing-performance-of-parallel-sorting-stdsort-vs-stdexecutionpar-vs-o[/url]