如何优化C++向量并行过滤性能？解决并行开销过大慢于串行问题

问题根源 #

你当前的实现中，每个符合条件的元素都通过#pragma omp critical调用push_back，这会导致大量线程阻塞等待临界区，并行的收益完全被锁开销抵消，甚至比串行更慢。

最优解决方案：线程本地存储后合并 #

每个线程先独立收集自己的结果，最后一次性合并到全局向量，仅在合并时进入一次临界区，大幅降低锁开销：

#pragma omp parallel
{
    // 每个线程维护自己的本地结果容器
    std::vector<std::vector<int>> local_b;

    #pragma omp for collapse(2)
    for(int i = 0 ; i < a.size() ; i++){
        for(int j = 0 ; j < a.size() ; j++){
            if(meetsConditions(a[i], a[j])){
                local_b.push_back({i, j});
            }
        }
    }

    // 仅在合并时进入临界区，避免频繁锁竞争
    #pragma omp critical
    b.insert(b.end(), local_b.begin(), local_b.end());
}

预分配向量+原子变量的正确实现 #

如果想预分配空间避免动态扩容，需要用原子变量安全地分配索引位置，确保每个线程写入的位置唯一：

#include <atomic>

// 初始化原子计数器，从0开始
std::atomic<int> current_idx = 0;
const int max_pairs = a.size() * a.size();

// 预分配足够的空间
b.resize(max_pairs);

#pragma omp parallel for collapse(2)
for(int i = 0 ; i < a.size() ; i++){
    for(int j = 0 ; j < a.size() ; j++){
        if(meetsConditions(a[i], a[j])){
            // 原子递增获取唯一的写入位置，无数据竞争
            int pos = current_idx++;
            b[pos] = {i, j};
        }
    }
}

// 截断向量到实际有效元素数量
b.resize(current_idx);

注意：必须使用std::atomic<int>而非普通int，current_idx++是原子操作，能保证多个线程不会同时获取同一个位置，避免数据竞争。

关于列表和指针的疑问 #

• 列表（std::list）：并不推荐。列表的插入操作同样需要锁保护，和原来的push_back加临界区一样会有频繁锁竞争，开销比线程本地向量合并大得多。
• 存储指针：没必要。存储索引比指针更安全（不会因为向量a的内存重新分配失效），且索引是轻量的int类型，占用空间更小，完全满足需求。

额外优化：直接并行执行doSmth（如果允许） #

如果doSmth函数是线程安全的，或者可以通过局部临界区保护，甚至可以跳过收集索引的步骤，直接在并行循环中执行：

#pragma omp parallel for collapse(2)
for(int i = 0 ; i < a.size() ; i++){
    for(int j = 0 ; j < a.size() ; j++){
        if(meetsConditions(a[i], a[j])){
            // 仅当doSmth非线程安全时需要加临界区，否则可移除
            #pragma omp critical
            doSmth(a[i], a[j]);
        }
    }
}

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