对于循环中的 emplace_back 向量，使用 openmp 无法加速

Question

我正在尝试 emplace_back 使用 openmp 循环中的向量。我的灵感来自这个 post : C++ OpenMP Parallel For Loop - Alternatives to std::vector。所以我写了一个测试代码：

// Example program
#include <iostream>
#include <string>
#include <vector>
#include <random>
#include <chrono>

#include <omp.h>

int main()
{
  std::cout << "Numbers of thread available : " << omp_get_max_threads() << std::endl;

  std::random_device dev;
  std::mt19937 gen(dev());
  std::uniform_int_distribution<unsigned> distrib(1, 5);

  {
    std::chrono::time_point<std::chrono::system_clock> start, end;
    start = std::chrono::system_clock::now();
    std::vector<std::pair<uint32_t, uint32_t> > result;

#pragma omp declare reduction (merge : std::vector<std::pair<uint32_t, uint32_t> > : omp_out.insert(omp_out.end(), std::make_move_iterator(omp_in.begin()), std::make_move_iterator(omp_in.end())))

#pragma omp parallel for reduction(merge: result)
    for(int i=0; i<100000000; ++i)
      {
        if(distrib(gen) == 1)
          {
            result.emplace_back(std::make_pair(distrib(gen),distrib(gen)));
          }
      }
    end = std::chrono::system_clock::now();                               \
    auto elapsed_seconds = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count(); \
    std::cout << "With openmp " << " : " << elapsed_seconds << "ms\n";
  }

  {
    std::chrono::time_point<std::chrono::system_clock> start, end;
    start = std::chrono::system_clock::now();
    std::vector<std::pair<uint32_t, uint32_t> > result;


    for(int i=0; i<100000000; ++i)
      {
        if(distrib(gen) == 1)
          {
            result.emplace_back(std::make_pair(distrib(gen),distrib(gen)));
          }
      }
    end = std::chrono::system_clock::now();                               \
    auto elapsed_seconds = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count(); \
    std::cout << "Without openmp " << " : " << elapsed_seconds << "ms\n";
  }
}

我用

编译这段代码

g++ -o main -std=c++17 -fopenmp main.cpp

输出为：

Numbers of thread available : 12
With openmp  : 3982ms
Without openmp  : 3887ms

显然，我的 openmp 实现没有任何加速。为什么？

Answer 1

关于文档，当前代码格式错误（因为并行代码主要包含-隐式依赖项）。因此，OpenMP 实现可以自由生成快速但完全“错误”的程序或缓慢的“正确”程序。

为了使用 OpenMP 获得正确的实现和不太差的加速，一种解决方案是 在每个 worker 中复制 generator/distribution（通过移动变量#pragma omp parallel 部分中的声明）并为（顺序）emplace_back.

添加 关键部分 （使用 #pragma omp critical）

由于可能的错误共享和锁争用，由此产生的并行实现可能扩展性不佳。最好生成 thread-private 数组，然后最终将子数组合并到一个大的共享数组中，而不是使用简单的临界区（但是请注意，这仍然不理想，因为计算可能会受到共享内存速度的限制。

请注意，当需要使用特定种子时，结果可能与顺序实现不同（这里没有问题，因为种子是从 random_device 中提取的）。

对于循环中的 emplace_back 向量，使用 openmp 无法加速

No speed up with openmp for emplace_back a vector in a loop

c++

openmp