CODEWITHSUNDEEP
c++stdvector
user2883918
user2883918

Reputation: 103

vector<vector<int>> takes too long initialize

I have some codes written in c++, it is a simple program to find out pair-wise dmin for a graph which has 3000+ vertices. All edges have the same weight 1. So I do BFS over all pairs of vertices.

My program runs not fast enough, so I did a profiling on my codes using Xcode 4.2.1's product->profile. It calls a tool called "instruments". After a while, I figured out how to use it. But what I got is very confusing. How could the highlighted line use so much time? Any thought is highly appreciated.

I defined: vector visited; vector< vector > G;//adjacency list enter image description here

Upvotes: 0

Views: 237

Answers (2)

user2784234
user2784234

Reputation: 451

The vast majority of time taken in the statement: (visited[G[n][i]] == false) would be due to massive cache misses.

Note that G is a big 3k*3k matrix, taking a contiguous virtual memory space, and visited is another 3k array taking another contiguous memory at a different location in the virtual memory space. Accessing both the memory locations in the same statement will cause lots of cache misses depending on the capacity of your processor's cache.

To gain a speed-up, rewrite the program keeping in mind locality of reference.

Upvotes: 1

Goz
Goz

Reputation: 62323

The instruments run is telling you that the vast majority of the time visited[G[n][i]] is true.

Upvotes: 1

Related Questions