OpenMP C++并行构建邻接表前清理unordered_map触发访问违例问题

我正在开发一个基准测试程序，用于测量使用不同线程数的OpenMP从边列表构建图的邻接表所需的时间。为保证每次测试独立性，需在构建前清理旧邻接表，但尝试的四种清理方式（代码中注释的4种）均触发异常：An exception was thrown: read access violation. _Val was 0xFFFFFFFFFFFFFFFF。若跳过清理步骤，程序可正常运行，但邻接表会重复添加相同顶点导致数据错误。

核心问题代码（GetAdjacentList函数） #

template<typename EdgeList, typename AdjacentList>
inline void UndirectedGraph<EdgeList, AdjacentList>::GetAdjacentList(const int num_threads)
{
    // ALL OPTIONS THROWN THE SAME EXCEPTION
    //1- this->adjacent_list.clear();
    //2- AdjacentList(this->n_vertices).swap(this->adjacent_list);
    //3- this->adjacent_list = AdjacentList(this->n_vertices);
    //4- AdjacentList temp = AdjacentList(this->n_vertices);
    //   this->adjacent_list.swap(temp);

    if (num_threads > 1) {
        #pragma omp for
        for(int i = 0; i < this->n_vertices; ++i)
            omp_init_lock(&this->writelock[i]);
    }
    
    auto start = now();

    #pragma omp parallel for if(num_threads > 1) num_threads(num_threads)
    for (int i = 0; i < this->n_edges; i++) {

        int v1 = this->edge_list[i].first;
        int v2 = this->edge_list[i].second;

        if (num_threads > 1) omp_set_lock(&this->writelock[v1]);
        auto it1 = upper_bound(this->adjacent_list[v1].begin(), this->adjacent_list[v1].end(), v2);
        this->adjacent_list[v1].insert(it1, v2);
        if (num_threads > 1) omp_unset_lock(&this->writelock[v1]);

        
        if (num_threads > 1) omp_set_lock(&this->writelock[v2]);
        auto it2 = upper_bound(this->adjacent_list[v2].begin(), this->adjacent_list[v2].end(), v1);
        this->adjacent_list[v2].insert(it2, v1);
        if (num_threads > 1) omp_unset_lock(&this->writelock[v2]);

    }

    auto end = now();

    if (num_threads > 1) {
        #pragma omp for
        for (int i = 0; i < this->n_vertices; ++i)
            omp_destroy_lock(&this->writelock[i]);
    }

    this->elp_adj[num_threads - 1] = (end - start);

    this->density = static_cast<double>((2 * this->n_edges) / (this->n_vertices * (this->n_vertices - 1)));
    
}

完整类定义及补充代码 #

UndirectedGraph类实现 #

template<typename EdgeList, typename AdjacentList>
class UndirectedGraph {
private:
    string name = "";
    int n_edges = 0;
    int n_vertices = 0;
    double density = .0;
    unordered_map<int, Duration> elp_adj;
    vector<omp_lock_t> writelock;


public:
    EdgeList edge_list;
    AdjacentList adjacent_list;

    void printProprieties();
    void TriangleCounter(const int num_threads); // not implemented
    void GetResultByThread(int thread);
    void WriteResultsCsv(string results_path);
    void GetAdjacentList(const int num_threads);

    UndirectedGraph() { }

    UndirectedGraph(filesystem::directory_entry entry) {
        if (entry.is_regular_file()) {

            vector<string> row;
            string line, word;
            vector<int> temp_vertices;

            this->name = entry.path().generic_string();
            this->name.erase(this->name.begin(), this->name.begin() + 11);

            cout << "Reading file: " << this->name << " ...";

            ifstream file(entry.path(), ios::in);

            // Reading the edges file

            if (file.is_open()) {
                while (getline(file, line)) {
                    int first, second;

                    row.clear();

                    stringstream str(line);

                    while (getline(str, word, ','))
                        row.push_back(word);
                    this->n_edges += 1;

                    first = stoi(row[0]);
                    second = stoi(row[1]);

                    this->edge_list.push_back(make_pair(first, second));

                    if (find(temp_vertices.begin(), temp_vertices.end(), first) == temp_vertices.end()) temp_vertices.push_back(first);
                    if (find(temp_vertices.begin(), temp_vertices.end(), second) == temp_vertices.end()) temp_vertices.push_back(second);

                }
            }
            file.close();

            this->n_vertices = static_cast<int>(temp_vertices.size());
            this->writelock = vector<omp_lock_t>(this->n_vertices);

            cout << "  DONE\n";
        }
    }
};



template<typename EdgeList, typename AdjacentList>
inline void UndirectedGraph<EdgeList, AdjacentList>::printProprieties()
{
    cout << "Name: " << this->name << " - Number of Edges: " << this->n_edges << " - Number of vertices: " << this->n_vertices << endl << endl;
}




template<typename EdgeList, typename AdjacentList>
inline void UndirectedGraph<EdgeList, AdjacentList>::GetAdjacentList(const int num_threads)
{

    // ----------------- ALL THROWN AN EXCEPTION -----------------
    //1- this->adjacent_list.clear();
    //2- AdjacentList(this->n_vertices).swap(this->adjacent_list);
    //3- this->adjacent_list = AdjacentList(this->n_vertices);
    //4- AdjacentList temp = AdjacentList(this->n_vertices);
    //   this->adjacent_list.swap(temp);;

    if (num_threads > 1) {
    #pragma omp for
        for (int i = 0; i < this->n_vertices; ++i)
            omp_init_lock(&this->writelock[i]);
    }

    auto start = now();

    #pragma omp parallel for if(num_threads > 1) num_threads(num_threads)
    for (int i = 0; i < this->n_edges; i++) {

        int v1 = this->edge_list[i].first;
        int v2 = this->edge_list[i].second;

        if (num_threads > 1) omp_set_lock(&this->writelock[v1]);
        auto it1 = upper_bound(this->adjacent_list[v1].begin(), this->adjacent_list[v1].end(), v2);
        this->adjacent_list[v1].insert(it1, v2);
        if (num_threads > 1) omp_unset_lock(&this->writelock[v1]);


        if (num_threads > 1) omp_set_lock(&this->writelock[v2]);
        auto it2 = upper_bound(this->adjacent_list[v2].begin(), this->adjacent_list[v2].end(), v1);
        this->adjacent_list[v2].insert(it2, v1);
        if (num_threads > 1) omp_unset_lock(&this->writelock[v2]);

    }

    auto end = now();

    if (num_threads > 1) {
        #pragma omp for
        for (int i = 0; i < this->n_vertices; ++i)
            omp_destroy_lock(&this->writelock[i]);
    }

    this->elp_adj[num_threads - 1] = (end - start);

    this->density = static_cast<double>((2 * this->n_edges) / (this->n_vertices * (this->n_vertices - 1)));

}


vector<UndirectedGraph<EdgeList, AdjacentList>> ReadFromDirectory(string path) {
    vector<UndirectedGraph<EdgeList, AdjacentList>> graphs_list;

    for (const auto& entry : filesystem::directory_iterator(path))
        graphs_list.push_back(UndirectedGraph<EdgeList, AdjacentList>(entry));

    return graphs_list;

}

主函数代码 #

string ReturnResultPath() {

    stringstream results_path;

    time_t result = time(NULL);
    char timestamp[26];
    ctime_s(timestamp, sizeof timestamp, &result);
    string ts = string(timestamp);

    ts.erase(remove(ts.begin(), ts.end(), '\n'), ts.cend());

    replace(ts.begin(), ts.end(), ' ', '_');
    replace(ts.begin(), ts.end(), ':', '.');

    results_path << "./results/results_" << ts << ".csv";
    return results_path.str();
}

void RunTriangleCounter(vector<UndirectedGraph<EdgeList, AdjacentList>> graphs_vector, string results_path) {
    for (auto& graph : graphs_vector) {
        cout << "\n";
        graph.printProprieties();

        cout << "Number of available cores: " << thread::hardware_concurrency() << "\n\n";

        for (int threads = 0; threads < MAX_THREADS; threads++) { // untill 20 threads

            if (threads == 0)
                cout << "SEQUENTIAL EXECUTION ...\n";
            else 
                cout << "PARALLEL EXECUTION WITH " << threads + 1 << " THREADS ...\n";
            graph.GetAdjacentList(threads + 1);
            graph.TriangleCounter(threads + 1); // not implemented
            graph.GetResultByThread(threads);
        }

        cout << "\n\n";
    }
}


int main() {
    string standford_datasets_path = "./datasets/standford";
    string results_path = ReturnResultPath();

    RunTriangleCounter(ReadFromDirectory(standford_datasets_path), results_path);
    return 0;
}

头文件包含 #

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <fstream>
#include <unordered_map>
#include <map>
#include <thread>
#include <random>
#include <ctime>
#include <string>
#include <sstream>
#include <filesystem>
#include <cstdio>
#include <unordered_map>
#include <omp.h>
#include <mutex>

问题根源 #

触发内存访问异常的核心原因有两点：

1. 邻接表未正确初始化：构造函数仅初始化了writelock向量，但adjacent_list未被初始化为包含n_vertices个元素的容器。调用清理操作后，容器大小变为0，后续访问adjacent_list[v1]会直接越界访问非法内存。
2. 顶点ID与容器索引不匹配：从文件读取的顶点ID可能是非连续的（比如ID为100、200这类值），但代码直接用顶点ID作为adjacent_list的索引，导致访问超出容器范围的内存。
3. OpenMP锁使用错误：#pragma omp for没有包裹在parallel区域内，锁初始化时会出现线程执行异常。

修复步骤 #

1. 正确初始化与清理邻接表 #

• 在UndirectedGraph构造函数末尾添加邻接表初始化代码：

  // 构造函数末尾添加
  this->adjacent_list = AdjacentList(this->n_vertices);
  

• 替换GetAdjacentList中的清理方式，保持容器大小不变，仅清空每个顶点的邻接列表：

  // 替换原注释的清理代码
  for (auto& list : this->adjacent_list) {
      list.clear();
  }
  

2. 处理非连续顶点ID #

添加顶点ID到容器索引的映射，避免直接用原始ID访问邻接表：

• 在UndirectedGraph类中添加私有成员：

  unordered_map<int, int> vertex_id_to_index;
  

• 修改构造函数中读取顶点的逻辑：

  // 替换原temp_vertices相关代码
  int index = 0;
  while (getline(file, line)) {
      // ... 读取first和second的代码 ...
      if (vertex_id_to_index.find(first) == vertex_id_to_index.end()) {
          vertex_id_to_index[first] = index++;
      }
      if (vertex_id_to_index.find(second) == vertex_id_to_index.end()) {
          vertex_id_to_index[second] = index++;
      }
      // 存储映射后的索引
      this->edge_list.push_back(make_pair(vertex_id_to_index[first], vertex_id_to_index[second]));
  }
  this->n_vertices = index;
  this->writelock = vector<omp_lock_t>(this->n_vertices);
  this->adjacent_list = AdjacentList(this->n_vertices);
  

3. 修复OpenMP锁的使用 #

将锁的初始化和销毁代码包裹在parallel区域内：

// 锁初始化
if (num_threads > 1) {
    #pragma omp parallel num_threads(num_threads)
    {
        #pragma omp for
        for(int i = 0; i < this->n_vertices; ++i)
            omp_init_lock(&this->writelock[i]);
    }
}

// 锁销毁
if (num_threads > 1) {
    #pragma omp parallel num_threads(num_threads)
    {
        #pragma omp for
        for (int i = 0; i < this->n_vertices; ++i)
            omp_destroy_lock(&this->writelock[i]);
    }
}

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