OpenMP并行填充vector of vectors性能问题求助

你的问题根源很明确：全局互斥锁导致了严重的线程竞争——每个线程在循环的每一次迭代都要抢锁，大部分时间都花在等待锁释放上，完全抵消了并行的优势，甚至比单线程还慢。

针对vector of vectors的并发填充，最有效的方案是让每个线程先维护自己的局部容器，处理完分配的任务后再一次性合并到全局容器，彻底避免频繁的锁竞争。下面是具体的优化思路和代码实现：

优化思路：局部容器+延迟合并 #

1. 每个线程创建独立的local_output（和全局output结构一致的vector of vectors），线程内部处理任务时直接往自己的局部容器里添加元素，完全不需要锁。
2. 所有线程完成任务后，再将各自的局部容器合并到全局output中，此时只需要一次线程安全的合并操作，锁的开销可以忽略不计。
3. 可选优化：提前统计每个网格的元素数量，预分配内存，减少push_back时的内存分配开销。

修改后的完整代码 #

#include <cmath>
#include <chrono>
#include <iostream>
#include <mutex>
#include <vector>
#include <algorithm>
#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;
    points.reserve(num); // 提前预分配输入空间
    for (size_t i = 0; i < num; ++i) {
        Vector2d point;
        point.x = generate(0, w);
        point.y = generate(0, h);
        points.push_back(point);
    }

    // 初始化全局输出容器
    std::vector<std::vector<Vector2d>> output(w * h);

    // 可选：提前统计每个网格的元素数量，预分配内存
    std::vector<size_t> counts(w * h, 0);
    #pragma omp parallel for reduction(+:counts[:w*h]) // OpenMP 4.5+支持数组reduction
    for (size_t i = 0; i < num; ++i) {
        const Vector2d& point = points[i];
        size_t x = static_cast<size_t>(std::floor(point.x));
        size_t y = static_cast<size_t>(std::floor(point.y));
        size_t id = y * w + x;
        counts[id]++;
    }
    // 预分配每个vector的空间
    for (size_t id = 0; id < w * h; ++id) {
        output[id].reserve(counts[id]);
    }

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

    #pragma omp parallel
    {
        // 每个线程创建局部输出容器
        std::vector<std::vector<Vector2d>> local_output(w * h);

        // 分配任务到当前线程，无需等待其他线程（nowait）
        #pragma omp for nowait
        for (size_t i = 0; i < num; ++i) {
            const Vector2d& point = points[i];
            size_t x = static_cast<size_t>(std::floor(point.x));
            size_t y = static_cast<size_t>(std::floor(point.y));
            size_t id = y * w + x;
            // 直接往局部容器添加，无锁竞争
            local_output[id].push_back(point);
        }

        // 合并局部容器到全局输出，critical区保证线程安全
        #pragma omp critical
        {
            for (size_t id = 0; id < w * h; ++id) {
                // 使用std::move避免拷贝，提升效率
                std::move(local_output[id].begin(), local_output[id].end(), 
                          std::back_inserter(output[id]));
            }
        }
    }

    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;
}

关键优化点说明 #

• 无锁局部处理：每个线程独立操作自己的local_output，完全消除了循环内的锁竞争，这是性能提升的核心。
• 高效合并：合并时用std::move转移元素所有权，避免了昂贵的深拷贝；critical区只进入一次，锁的开销微乎其微。
• 预分配内存：提前统计每个网格的元素数量并reserve空间，减少了push_back过程中的内存重分配次数，进一步提升速度。

为什么不直接用OpenMP的reduction？因为reduction需要定义明确的二元合并操作，对于vector of vectors这种嵌套结构，自定义reduction的复杂度远高于局部容器+合并的方案，而且性能优势不明显，所以前者是更务实的选择。

内容的提问来源于stack exchange，提问作者areslp