使用OpenMP并行图遍历内存占用过高的原因排查

我正在实现并行图遍历，代码里只有一个可写共享变量。按我的理解，内存占用应该等于bfs函数局部变量大小×线程数+少量开销，但实际数值远超预期。

编译环境：gcc/9.2.0
编译命令：g++ demo.cpp -I . -o d -std=c++11 -O2 -fopenmp

代码中runBFS函数通过OpenMP并行调用bfs函数，每个线程处理一个src对应的目标列表，最终将各线程结果拼接为totalStr。请问我哪里处理错了？

完整代码如下：

#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#include <map>
#include <map>
#include <tuple>
#include <sstream>
#include <unordered_set>

#include "omp.h"

using namespace std;


static map<int,std::vector<int>> g_adjLst;
static map<int,std::vector<int>> g_pairLst;
static int g_vertex;

void setSize(int nodesLen) ;
void addEdge(const int src, const int dst);
void print();

int findShortestPath(int src,int dst);
string bfs(int src, const std::vector<int>& , int thread) ;

int getSize() ;
int getPairSize() ;
void clearPair () ;
void storePairForPathFinding(int src, int dst) ;
string runBFS();

void setSize(int nodesLen) {
    g_vertex = nodesLen;
}

string bfs( int src, const std::vector<int>& dst ,  int perc) {

    std::stringstream msg;

    if (g_adjLst.find(src) == g_adjLst.end()) {
        return  "";
    }

    std::vector<int>  dist (g_vertex,INT_MAX);
    std::vector<bool> visited(g_vertex,false);

    std::queue <int> q;
    q.push(src);
    visited.at(src) = true;
    dist.at(src)= 0;

    while (!q.empty()) {
        int size = q.size();
        while (size--) {
            int curr = q.front();
            q.pop();
            if (g_adjLst.find(curr) == g_adjLst.end()) {
                return "";
            }
            for (vector<int> ::const_iterator it = g_adjLst[curr].begin();  it != g_adjLst[curr].end(); ++it) {
                if (visited.at(*it)) {continue;}

                if (dist.at(*it)> dist.at(curr) +1) {
                    dist.at(*it)= dist.at(curr) + 1;
                    q.push(*it);
                }
                visited.at(*it) = 1;
            }
        }
    }

    stringstream s;
    for (std::vector<int> ::const_iterator it =  dst.begin() ; it != dst.end(); ++it) {
        s << " {" << src << "," << *it << "}" << dist[*it] ;
    }
    return s.str();
}

//
void storePairForPathFinding (int src, int dst) {
    g_pairLst[src].push_back(dst);
}

//
//
string runBFS() {

    int  i,tid=0,nthreads;

    vector<int> ::iterator ip ;
    for (std::map<int,std::vector<int>> ::iterator it = g_pairLst.begin(); it != g_pairLst.end() ;++it) {
        ip = std::unique(it->second.begin() , it->second.end());
        it->second.resize(std::distance(it->second.begin(),ip));
    }

    std::string totalStr  = "" ,partialStr = "";

    int total = g_pairLst.size();
    #pragma omp parallel for private(tid,nthreads,partialStr) shared (totalStr)
    for (i = 0 ; i < g_pairLst.size(); i++) {
        auto it = g_pairLst.begin();
        advance(it,i);
        tid = omp_get_thread_num();
        partialStr = bfs(it->first,it->second,int(i*100/total));

        // Create thread safe region.
        #pragma omp critical
        {
                //add each threads partial sum to the total sum
                totalStr += partialStr;
        }
    }
    return totalStr; 
}

//
//
void addEdge(int src, int dst) {
    g_adjLst[src].push_back(dst);
}
int main () {
  setSize(60000);


for(int i = 0; i < 60000;i++) {
    for (int j=0; j< 60000; j++) {
        addEdge(i,j);
        if (i==j) {
            storePairForPathFinding(0,i);
        }
    }
}

    string s = runBFS();

    cout << "Ans1 = " << s << endl;

    string e = runBFS();
    cout << "Ans2 = " << e << endl;  
}

问题根源分析 #

1. 图结构本身的内存爆炸 #

你在main函数里创建了一个60000×60000的完全图：每个节点都和其他60000个节点相连，g_adjLst作为邻接表，总共有60000个vector，每个vector包含60000个int。按每个int4字节计算，这部分内存就达到：
60000 × 60000 × 4字节 = 14,400,000,000字节 ≈ 13.4GB
这是内存远超预期的核心原因，和并行逻辑无关。

2. BFS局部变量的重复分配 #

每个bfs调用都会创建两个大小为60000的vector：

std::vector<int>  dist (g_vertex,INT_MAX); // 60000×4=240KB
std::vector<bool> visited(g_vertex,false); // 60000位≈7.5KB

如果OpenMP启用8个线程，这部分内存约为8×(240KB+7.5KB)≈2GB，属于次要但可优化的开销。

3. 其他隐性内存开销 #

• g_pairLst存储了60000个目标节点，即使去重后也占用一定内存；
• 字符串拼接totalStr += partialStr会频繁触发内存重分配，长字符串会产生大量内存碎片。

修复建议 #

1. 重构图结构：
   完全图不需要实际存储邻接表，直接通过逻辑判断就能得到结果（任意两点距离为1，自身到自身为0），可直接砍掉13GB的内存占用。

2. 复用BFS局部容器：
   将dist和visited改为线程私有变量，或通过对象池复用，避免每次调用bfs都重新分配大内存块。

3. 优化字符串拼接：
   预先计算结果字符串的大致长度并提前分配内存；或让每个线程先将结果存入独立的stringstream，最后一次性合并，减少内存重分配次数。

4. 优化并行循环：
   原循环中每次调用advance(it,i)遍历map的效率极低，map是有序容器，随机访问性能差。建议先将map的键值对转为vector再并行遍历：

   vector<pair<int, vector<int>>> pairs(g_pairLst.begin(), g_pairLst.end());
   #pragma omp parallel for private(partialStr) shared(totalStr)
   for (size_t i = 0; i < pairs.size(); ++i) {
       partialStr = bfs(pairs[i].first, pairs[i].second, int(i*100/pairs.size()));
       #pragma omp critical
       totalStr += partialStr;
   }
   

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