13G图边列表转vector<vector<int>>邻接表的性能优化及并行push_back实现咨询

Great question—handling large graph edge lists efficiently is all about taming random memory access and squeezing every bit of throughput from your system. Let's walk through why your current optimizations only gave a small boost, then dive into better strategies that should cut your runtime drastically.

Why Your Cache Optimization Only Helped a Little #

Your vector-of-vectors (vector<vector<int>>) structure does have overhead: accessing adj[u] requires two pointer dereferences, and each sub-vector lives in scattered memory blocks. While your cache buffer reduces the number of push_back calls, it doesn't fix the core issue: you're still performing random writes to memory locations all over the place. This kills CPU cache hit rates, which is the main bottleneck here. Plus, your cache[N][threshold] array takes up ~1.3GB of memory (3.3M × 100 × 4 bytes), which might be competing with other data for cache space.

Top Optimization Strategies #

1. Ditch fscanf for Memory-Mapped IO + Fast Integer Parsing

fscanf is surprisingly slow for large text files—it does a lot of extra work (like locale checks) that you don't need. Memory-mapping the file directly into your process's address space eliminates kernel-user space copy overhead, and manual integer parsing skips the bloat of standard library functions.

Here's how to implement this:

#include <sys/mman.h>
#include <fcntl.h>
#include <unistd.h>
#include <vector>
#include <cstdlib>

const int N = 3328557;

int main() {
    // Memory-map the edge list file
    int fd = open("path/to/edge/list", O_RDONLY);
    off_t file_size = lseek(fd, 0, SEEK_END);
    char* file_data = (char*)mmap(nullptr, file_size, PROT_READ, MAP_PRIVATE, fd, 0);
    close(fd);

    // Use this pointer to traverse the mapped data
    char* ptr = file_data;

    // Rest of your processing goes here...

    munmap(file_data, file_size); // Cleanup
    return 0;
}

For integer parsing, replace fscanf with strtol (or a custom faster parser) to skip whitespace and convert bytes to integers directly from the mapped buffer.

2. Reorganize Memory to Eliminate Random Access

The biggest win comes from switching to a single contiguous memory block + offset array instead of vector<vector<int>>. This turns random writes into sequential ones, which the CPU cache handles perfectly. Here's the step-by-step approach:

1. First pass: Count node degrees
   Scan the file once to track how many edges each node has. This lets you pre-allocate exactly the right amount of memory.
2. Compute prefix offsets
   Create an array where offset[u] is the starting index of node u's adjacency list in the contiguous block.
3. Second pass: Fill the contiguous adjacency list
   Write edges directly to their pre-computed positions in the block—no random access, no push_back overhead.

Full code example:

// ... (mmap setup from above)

// Step 1: Count degrees
std::vector<int> deg(N, 0);
char* ptr = file_data;
while (ptr < file_data + file_size) {
    // Skip whitespace
    while (ptr < file_data + file_size && (*ptr == ' ' || *ptr == '\n' || *ptr == '\r')) ptr++;
    if (ptr >= file_data + file_size) break;
    int u = strtol(ptr, &ptr, 10);
    while (ptr < file_data + file_size && (*ptr == ' ' || *ptr == '\n' || *ptr == '\r')) ptr++;
    int v = strtol(ptr, &ptr, 10);
    deg[u]++;
    deg[v]++;
}

// Step 2: Compute prefix offsets
std::vector<int> offset(N + 1, 0);
for (int i = 1; i <= N; ++i) {
    offset[i] = offset[i-1] + deg[i-1];
}
std::vector<int> adj_data(offset[N]); // Contiguous block for all edges

// Step 3: Fill adjacency list
ptr = file_data;
std::vector<int> current_offset = offset; // Track current write position
while (ptr < file_data + file_size) {
    while (ptr < file_data + file_size && (*ptr == ' ' || *ptr == '\n' || *ptr == '\r')) ptr++;
    if (ptr >= file_data + file_size) break;
    int u = strtol(ptr, &ptr, 10);
    while (ptr < file_data + file_size && (*ptr == ' ' || *ptr == '\n' || *ptr == '\r')) ptr++;
    int v = strtol(ptr, &ptr, 10);
    adj_data[current_offset[u]++] = v;
    adj_data[current_offset[v]++] = u;
}

// Optional: Convert back to vector<vector<int>> if needed
std::vector<std::vector<int>> adj(N);
for (int u = 0; u < N; ++u) {
    adj[u].resize(deg[u]);
    std::copy(adj_data.begin() + offset[u], adj_data.begin() + offset[u+1], adj[u].begin());
}

This approach will drastically reduce runtime—expect to go from minutes to tens of seconds, since all memory operations are sequential and cache-friendly.

3. Parallelize the Right Way (No Random Write Parallelism!)

Parallelizing push_back calls directly is a bad idea: random memory writes cause massive cache contention between threads, which will slow things down instead of speeding them up. Instead, use parallel file processing with local buffers:

1. Split the mapped file into chunks, one per thread.
2. Each thread processes its chunk, maintaining a local degree count and local adjacency buffer.
3. Merge all local degree counts to compute the global offset array.
4. Each thread writes its local adjacency data to the correct position in the global contiguous block.

Example of parallel degree counting with OpenMP:

std::vector<int> deg(N, 0);

#pragma omp parallel
{
    std::vector<int> local_deg(N, 0);
    off_t chunk_size = file_size / omp_get_num_threads();
    off_t start = omp_get_thread_num() * chunk_size;
    off_t end = (omp_get_thread_num() == omp_get_num_threads()-1) ? file_size : start + chunk_size;
    char* local_ptr = file_data + start;

    // Align start to the beginning of an integer
    if (start > 0) {
        while (local_ptr > file_data && *(local_ptr-1) != ' ' && *(local_ptr-1) != '\n') {
            local_ptr--;
        }
    }

    // Process chunk
    while (local_ptr < file_data + end) {
        while (local_ptr < file_data + end && (*local_ptr == ' ' || *local_ptr == '\n')) local_ptr++;
        if (local_ptr >= file_data + end) break;
        int u = strtol(local_ptr, &local_ptr, 10);
        while (local_ptr < file_data + end && (*local_ptr == ' ' || *local_ptr == '\n')) local_ptr++;
        if (local_ptr >= file_data + end) break;
        int v = strtol(local_ptr, &local_ptr, 10);
        local_deg[u]++;
        local_deg[v]++;
    }

    // Merge local counts to global
    #pragma omp critical
    {
        for (int i = 0; i < N; ++i) {
            deg[i] += local_deg[i];
        }
    }
}

This avoids contention during processing and only merges results once, making parallelism effective.

4. Quick Wins: Small Tweaks That Add Up

• Pre-reserve vector space: If you stick with vector<vector<int>>, call adj[u].reserve(deg[u]) after counting degrees—this eliminates expensive reallocations during push_back.
• Adjust cache threshold: If you keep your buffer approach, try increasing threshold (e.g., to 1000) to reduce the number of write2vec calls, but don't make it so large that the cache array eats up all available memory.
• Disable C++ IO sync: If you ever switch to cin/cout, add std::ios::sync_with_stdio(false); std::cin.tie(nullptr); to speed up input.

Final Notes #

The contiguous memory + memory-mapped IO approach will give you the biggest performance jump. Parallelism can then push it even further, but only if you avoid random write contention. With these changes, your 13G edge list should process in a fraction of the current time.

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