c++ - OpenMP parallel for with vector of vectors

Question

我有一个大小为 W x H 的固定大小的二维矩阵，矩阵中的每个元素都是一个 std::vector。数据存储在具有线性化索引的 vector vector 中。我试图找到一种方法来同时填充输出 vector 。这是一些代码来指示我正在尝试做什么。

#include <cmath>
#include <chrono>
#include <iostream>
#include <mutex>
#include <vector>
#include <omp.h>

struct Vector2d
{
    double x;
    double y;
};

double generate(double range_min, double range_max)
{
    double val = (double)rand() / RAND_MAX;
    return range_min + val * (range_max - range_min);
}

int main(int argc, char** argv)
{
    (void)argc;
    (void)argv;

    // generate input data
    std::vector<Vector2d> points;
    size_t num = 10000000;
    size_t w = 100;
    size_t h = 100;

    for (size_t i = 0; i < num; ++i)
    {
        Vector2d point;
        point.x = generate(0, w);
        point.y = generate(0, h);
        points.push_back(point);
    }

    // output
    std::vector<std::vector<Vector2d> > output(num, std::vector<Vector2d>());
    std::mutex mutex;

    auto start = std::chrono::system_clock::now();

    #pragma omp parallel for
    for (size_t i = 0; i < num; ++i)
    {
        const Vector2d point = points[i];
        size_t x = std::floor(point.x);
        size_t y = std::floor(point.y);
        size_t id = y * w + x;
        mutex.lock();
        output[id].push_back(point);
        mutex.unlock();
    }

    auto end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed_seconds = end - start;
    std::cout << "elapsed time: " << elapsed_seconds.count() << "s\n";

    return 0;
}

问题是代码在启用 openmp 的情况下要慢得多。我找到了一些使用缩减填充 std::vector 的示例，但我不知道如何使其适应 vector 的 vector 。任何帮助表示赞赏，谢谢!

Answer 1

您可以采取一些措施来提高性能:

我会预先分配第二个包含 Vector2d 的 vector 上课，因为每次你push_back一个新的Vector2d和 capacity的 std::vector超过了，就会重新分配。所以如果你不关心初始化 Vector2d在你的std::vector我会简单地使用:

std::vector<std::vector<Vector2d> > output(num, 
               std::vector<Vector2d>(num, Vector2d(/*whatever goes in here*/)));

然后在您的 for 循环中，您可以通过 operator[] 访问第二个 vector 中的元素，这使您可以摆脱锁定。

#pragma omp parallel for
for (size_t i = 0; i < num; ++i)
{
    const Vector2d point = points[i];
    size_t x = std::floor(point(0));
    size_t y = std::floor(point(1));
    size_t id = y * w + x;
    output[id][i] = num;
}

虽然我不确定，但前面提到的方法适用于您想要执行的操作。否则你可以 reserve每个 std::vector<Vector2d> 的存储，这将留下您的初始循环:

std::vector<std::vector<Vector2d> > output(num, std::vector<Vector2d>());
for(int i = 0; i < num; ++i) {
    output[i].reserve(num);
}

#pragma omp parallel for
for (size_t i = 0; i < num; ++i)
{
    const Vector2d point = points[i];
    size_t x = std::floor(point(0));
    size_t y = std::floor(point(1));
    size_t id = y * w + x;
    mutex.lock();
    output[id].push_back(point);
    mutex.unlock();
}

这意味着你摆脱了 vector 重新分配，但你仍然有互斥...