是否可以使用复杂度为 O(1) 的 openMP 初始化向量？ (C++)

Question

我正在尝试使用 openMP 并行化结构中的一些向量函数。虽然它适用于我的大多数实现，但我发现由于 std::vector<> 的构造函数具有线性复杂性，我无法获得更好的性能，反而得到比顺序执行初始化更糟糕的东西。

这是初始化程序之一

         /**
         * @brief Construct a new constant parallel Vector object with a given value constantEntry
         * 
         * @param dim 
         * @param constantEntry 
         */
        parallelVector(const int dim, const double constantEntry){
            dimension = dim;
            values = std::vector<double>(dimension);

            #pragma omp parallel for schedule(static)
            for (int i=0 ; i<dimension; i++){
                values[i] = constantEntry;
            }
        }

std::vector<> 文档说我可以使用分配器获得 O(1) 的复杂度，但由于我对它们不太熟悉，我想知道是否可以使用具有唯一指针的东西？

Answer 1

template<class T>
struct uninitialized_allocator:std::allocator<T> {
  template<class...Us>
  void construct( T* p, Us&&... us ){
    ::new((void*)p) T(std::forward<Us>(us)...);
  }
  // don't construct when passed 0 arguments
  void construct( T* p ) {};
};

然后：

    int dimension = 0;
    std::vector<double, uninitialized_allocator<double>> values;
    parallelVector(const int dim, const double constantEntry):
      dimension(dim),
      values(dim)
    {
        #pragma omp parallel for schedule(static)
        for (int i=0 ; i<dimension; i++){
            values[i] = constantEntry;
        }
    }

但是请注意，您负责在调用 resize 以及使用 0 个参数的 emplace_back() 时初始化新向量元素。

理论上，std::vector 仍然会在每个元素上调用 construct(T*)，但这是一个 noop，编译器擅长消除死代码。因此，在重要的优化设置下，这应该可以满足您的需求。

请注意，我将 operator= 的用法更改为构造；它们不相同，并且vector在这两种情况下可以自由地表现出非常不同的行为。

是否可以使用复杂度为 O(1) 的 openMP 初始化向量？ (C++)

Is it possible to initialize a vector with openMP with O(1) complexity? (C++)

c++

struct

vector

openmp