# Very slow graph walking

My code is very very slow. Could you give me hints on how I can make it much faster?

for (stdext::hash_map<unsigned __int32, CVertex*>::iterator it1 = graph.begin(); it1 != graph.end(); it1++)
{
for (std::vector<CVertex*>::iterator it2 = it1->second->getNeighbors().begin(); it2 != it1->second->getNeighbors().end(); it2++)
{
if ((*it2)->isEqualTo(it1->second)) continue;
for (std::vector<CVertex*>::iterator it3 = (*it2)->getNeighbors().begin(); it3 != (*it2)->getNeighbors().end(); it3++)
{
if ((*it3)->isEqualTo(*it2) || (*it3)->isEqualTo(it1->second)) continue;
for (std::vector<CVertex*>::iterator it4 = (*it3)->getNeighbors().begin(); it4 != (*it3)->getNeighbors().end(); it4++)
{
if ((*it4)->isEqualTo(*it3) || (*it4)->isEqualTo(*it2) || (*it4)->isEqualTo(it1->second)) continue;
for (std::vector<CVertex*>::iterator it5 = (*it4)->getNeighbors().begin(); it5 != (*it4)->getNeighbors().end(); it5++)
{
if ((*it5)->isEqualTo(*it4) || (*it5)->isEqualTo(*it3) || (*it5)->isEqualTo(*it2) || (*it5)->isEqualTo(it1->second)) continue;
for (std::vector<CVertex*>::iterator it6 = (*it5)->getNeighbors().begin(); it6 != (*it5)->getNeighbors().end(); it6++)
{
if (it1->second->isEqualTo(*it6))
{
unsigned __int32 *circle = new unsigned __int32[5];

circle[0] = it1->second->getWord();
circle[1] = (*it2)->getWord();
circle[2] = (*it3)->getWord();
circle[3] = (*it4)->getWord();
circle[4] = (*it5)->getWord();

m_results.push_back(circle);
}
}
}
}
}
}
}


I think this question is not subjective because I've found many good things on the Internet yet:

1. I use only vectors which is much faster (the not reserved too) because of the cache.
2. You cannot see here, but I use only inline function in vertex class.
3. I tried to reduce the numbers into uint 32 bit.

But I still miss good trick because its time is lifetime. For example, do you think I can make better compiler settings?

Or it's also very useful if you say I cannot make it much faster because in that case I don't waste more energy into finding a better solution.

• We need to see the definition of getNeighbors(). But you have O(N^6) loop. Its not surprising it is slow. You could remove a lot of push_back() if the order of circle[0..4] id not important. – Martin York Jan 1 '15 at 2:19
• thanks. its implementation is the following: inline std::vector<CVertex*>& CVertex::getNeighbors() { return m_neighbors; }; The CVertex is a simple id and link to the neighbors and nothing else. The problem is that one of my friends can achive much faster running (in another computer but the difference is so big I really doubt it is the reason) – Tamas Jan 1 '15 at 21:51
• No that looks correct. Note the inline does not help in any way to speed up the code. – Martin York Jan 1 '15 at 22:58
• To help speed up things. You can use m_results.reserve(<the number of items you will push>); Also using a vector<unsigned __int32> rather than an new unsigned __int32[5] may help in speding things up (as you can move it into the array rather than copying it in. – Martin York Jan 1 '15 at 23:02
• Other than that there is little we can do to help because you have not provided any real information that will help us solve the problem. – Martin York Jan 1 '15 at 23:02

• Google suggests that the performance of stdext::hash_map might be improved by adding #define _SECURE_SCL 0. See this MSDN article for background.
• Your if's look like they might become victim to branch misprediction. This StackOverflow answer explains that better than I ever could.
• If you haven't done so already, take care to allocate your vertices (and their internal data) contiguously. The simplest way to do that is usually to shove everything into a vector.