为什么使用 execution::par 对向量进行排序比正常排序 (gcc 10.1.0) 花费的时间更长？

Question

考虑这段代码：

#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

我使用 VS Code 使用 gcc 在 Windows 10 上编译了代码： g++ -std=c++17 -g ${workspaceFolder}/main.cpp -o ${workspaceFolder}/main.exe

对于 C++ 标准库，我使用可以找到的 mingw 发行版 here。程序版本：GCC 10.1.0 + LLVM/Clang/LLD/LLDB 10.0.0 + MinGW-w64 7.0.0

我的处理器有 6 个内核，在执行时我没有运行任何主要程序或后台进程。

首先，我认为这与向量的大小有关，但 30 000 000 个元素肯定足够了。在完成单个测试之前已经运行s 10 秒。

这是怎么回事？
execution::par是不是要这么用？
我是否必须启用一些编译标志或一些其他技巧才能使其按预期工作？

Answer 1

运行 perf 你的代码，看起来它在尝试分区数据时花费了一点点时间。

这只是一个示例，但我运行它多次出现，而且并行版本始终需要更长的时间才能在多个排序级别对数据进行分区。由于它是递归的，因此很难准确了解它最终增加了多少额外开销。

sort1 是非并行排序。
sort2 是并行排序。

除此之外，基本问题的答案是您需要安装英特尔线程构建块，以便 gcc 使用串行算法以外的任何算法。
这可以简单地在 linux 上用 sudo apt install libtbb-dev 安装，然后你 link 用 -ltbb

反对它

为什么使用 execution::par 对向量进行排序比正常排序 (gcc 10.1.0) 花费的时间更长？

Why does sorting a vector with execution::par take longer than normal sort (gcc 10.1.0)?

c++

sorting

multithreading

mingw-w64

c++17