parallel push_back for vector of vector

user_12883294 0
Viewed 119

I have a large text file around 13G which the content is an edge list of a graph. Each line has two integers uandv represent the endpoint of an edge. I want to read it to a vector of vector as an adjency vector of the graph.

Then It comes to folowing code.

const int N = 3328557;
vector<vector<int> >adj{N};

int main() {
    FILE * pFile;
    pFile = fopen("path/to/edge/list", "r");

    int u, v;
    while (fscanf(pFile, "%d%d", &u, &v) == 2) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    fclose(pFile);
}

It consumes about 7min. After some analysis, I find adj[u].push_back(v) and adj[v].push_back(u) consumes most time because of random address.

Then I use a two dimension array as cache. Once it's filled, I copy all the value to vector and clear it.

const int N = 3328557;
const int threshold = 100;

vector<vector<int> >adj{N};
int ln[N];
int cache[N][threshold];

void write2vec(int node) {
    for (int i = 0; i < ln[node]; i++)
        adj[node].push_back(cache[node][i]);
    ln[node] = 0;
}

int main() {
    FILE * pFile;
    pFile = fopen("path/to/edge/list", "r");

    int u, v;
    while (fscanf(pFile, "%d%d", &u, &v) == 2) {
        cache[u][ln[u]++] = v;
        if (ln[u] == threshold)
            write2vec(u);
        cache[v][ln[v]++] = u;
        if (ln[v] == threshold)
            write2vec(v);
    }

    for (int i = 1; i < N; i++)
        write2vec(i);
    
    fclose(pFile);
}

This time it consumes 5.5 min. It's still too long. Then I think the two push_back in the first code can be parallelized. But I don't know how to do. And does anyone has other idea?

Thanks.

Edit.

I think the reason why my second approach is faster is addressing on vector of vector is slower. The address of vector of vector is not contiguous, so accessing adj[u] needs two operation, first is adj then adj[u].

So I want to know if I can use multiprocessing to make addressing parallelized.

vector c++11 c++
1 Answers

"I think the two push_back in the first code can be parallelized."

It's likely that your CPU will agree. Given the data size, this is likely to hit a bottleneck from L3 cache to main memory. Modern CPU cores are capable of out-of-order execution, and this looks like the CPU will happily start with instructions that belong to the second push_back while the first one is waiting for main memory. That's exactly why out-of-order execution is a common feature.

The chief problem is reallocation - you didn't reserve capacity. And reallocation is not a simple CPU operation; it requires access to a global heap. I would suggest reserving 128/sizeof(int) elements per inner vector. That's one or two cache lines on comon CPU's, so you don't have vectors sharing cache lines.

MSalters_154160
Related