Почему сортировка вектора с помощью execute :: par занимает больше времени, чем обычная сортировка (g cc 10.1.0)? - PullRequest
Новая
       147

Почему сортировка вектора с помощью execute :: par занимает больше времени, чем обычная сортировка (g cc 10.1.0)?

2 голосов
/ 14 июля 2020

Рассмотрим этот код: 

#include <algorithm>
#include <chrono>
#include <cstdio>
#include <execution>
#include <functional>
#include <random>
#include <vector>
using namespace std;
using namespace std::chrono;

constexpr size_t NUM_OF_ELEMENTS = 30000000;

// execute lambda and print the execution time
void measure(function<void()> lambda)
{
    auto start = high_resolution_clock::now();
    lambda();
    auto end = high_resolution_clock::now();
    
    printf("%ld\n", duration_cast<microseconds>(end - start).count());
}

int main()
{
    random_device rd;
    mt19937_64 gen(rd());
    // range from INT_MIN to INT_MAX
    uniform_int_distribution<> distr(-2147483648, 2147483647);
    
    vector<int> original;
    original.reserve(NUM_OF_ELEMENTS);
    
    for(size_t i = 0; i < NUM_OF_ELEMENTS; i++)
        original.push_back(distr(gen));
    
    vector<int> the_copy(original.begin(), original.end());
    
    // sort with single thread
    measure([&]{ sort(original.begin(), original.end()); });
    
    // sort with execution::par
    measure([&]{ sort(execution::par, the_copy.begin(), the_copy.end()); });
    return 0;
}

Код можно суммировать в несколько пунктов:

  • создать генератор случайных чисел
  • создать вектор случайных чисел целые числа
  • создать копию этого вектора
  • отсортировать исходный вектор с помощью одного потока и измерить время выполнения
  • отсортировать копию с помощью std::execution::par и измерить время выполнения
  • распечатать время выполнения

Версия execution::par всегда занимает больше времени. Неважно, какое значение имеет NUM_OF_ELEMENTS. Я пробовал значения от 100 000 до 30 000 000, увеличиваясь на 100 000. Приведенный выше код дает похожие результаты (значения в микросекундах): 

9729406    // single thread
10834613   // execution::par

Я скомпилировал код на Windows 10 с помощью g cc с использованием кода VS: g++ -std=c++17 -g ${workspaceFolder}/main.cpp -o ${workspaceFolder}/main.exe

Для стандартной библиотеки C ++ я использую дистрибутив mingw, который можно найти здесь . Версии программы: GCC 10.1.0 + LLVM/Clang/LLD/LLDB 10.0.0 + MinGW-w64 7.0.0

У моего процессора 6 ядер, и во время выполнения я не запускал никаких основных программ или фоновых процессов.

Во-первых, я подумал, что ему есть чем заняться при размере вектора но 30 000 000 элементов наверняка хватит. Он уже работает в течение 10 секунд перед завершением одного теста.

  • Что происходит?
  • Разве execution::par предназначен для использования таким образом?
  • Сделать Мне нужно включить некоторые флаги компиляции или какой-то другой трюк, чтобы он работал должным образом?

1 Ответ

1 голос
/ 15 июля 2020

запускает perf в вашем коде, похоже, что он тратит немного больше времени на попытки разбить данные.

Это только один пример, но я запускал его несколько раз, и последовательно параллельная версия занимала больше времени для разделения данных на несколько уровней сортировки. Поскольку он рекурсивен, трудно получить точную картину того, сколько дополнительных накладных расходов он в итоге добавляет.

sort1 - это непараллельная сортировка. sort2 - это параллельная сортировка.

введите описание изображения здесь

Кроме того, ответ на основной вопрос заключается в том, что вам нужны строительные блоки Intel Thread, чтобы g cc мог использовать что-либо, кроме последовательных алгоритмов. Его можно быстро установить на linux с помощью sudo apt install libtbb-dev, а затем связать его с -ltbb

...