hash_map problems

That could indicate a problem with the hash function, causing it to hash everything into the same bucket (in effect, making it into a linked list). What is the key-type of the hashtable, and what hashing function are you using?

EDIT: oh, you're just iterating through all the elements of the hash_map? Huh.... not sure.

---

"Sneftel is correct, if rather vulgar." --Flarelocke

[edited by - sneftel on January 29, 2004 3:31:03 PM]

IIRC, STLPort''s hash_map uses an internal linked list to represent the buckets, and thus hash_map::iterator works a lot like a linked list iteration. Iterating through a linked list is slower than iterating through a vector. I''m not sure if that will account for the massive drop you''re seeing, but it should explain part of it.

It is quite strange, and I can''t find any info on the web about it, I have a few ideas, but I can''t try them out until later on. If I find anything useful, I shall post it.

Thanks for your help.

Also, if you posted the actual iteration code (both versions) we might be able to give more insightful comments.

I can give you that now, it is just:

hash_map::iterator nodeIter = mChildNodes.begin();

Node *childNode;
for (; nodeIter != mChildNodes.end(); nodeIter++ )
{
childNode = nodeIter->second;
childNode->recursivefunctionbacktohere();
}

There are never more than 4 nodes in a child ( its a quadtree )

Use ++nodeIter instead of nodeIter++, just in case that iterator class is so complex that your compiler can''t optimise away the difference. (Unlikely, but it''s best not to tempt fate.)

Before I ask anything else: is this a debug build? Also, are you using the STLPort "safe" mode?

Yep it is debug and i have stl_debug on aswell.
Good point about ++nodeIter, i keep trying to remind myself to put it in like that initially, but I always seem to post ++ instead of pre .

I can''t see why there must be such a speed loss, I must have a problem with my recursion, I know a map can sometimes be costly to increment because it is a red-black tree ( I am correct on this I hope? ). And you were saying that a hash_map is effectively a list when it comes to iterating? Must be something I have done :/

quote:

---

Original post by Anonymous Poster
Also do this:

hash_map::iterator nodeIter = mChildNodes.begin();
hash_map::iterator endIter = mChildNodes.end();

Node *childNode;
for (; nodeIter != endIter; ++nodeIter )
{
childNode = nodeIter->second;
childNode->recursivefunctionbacktohere();
}
  

It may help.

---

This is probably winning - note the key change is that the end iterator is cached. Since it comes from a function call your compiler may not be able to make the optimization - and finding the end *might* be O(n) if the hash_map implementation in turn is not smart enough to cache.

... childNode is a pointer to an array of (up to 4) child nodes I take it? And then you recurse on each one? You might consider marking each node after you process it... and you''re not recalling this iteration function when you recurse on the children are you? o__O

quote:

---

Original post by RobertC
Yep it is debug and i have stl_debug on aswell.
...
I can't see why there must be such a speed loss, I must have a problem with my recursion, I know a map can sometimes be costly to increment because it is a red-black tree ( I am correct on this I hope? ). And you were saying that a hash_map is effectively a list when it comes to iterating? Must be something I have done :/

---

The STLPort safe mode produces a lot of extra checks to make sure you're using it correctly, and those checks slow things down. Relatively speaking the vector iterator is much simpler than the hash_map iterator, and produces both fewer extra checks and the checks that it does produce are faster. This complexity difference is exacerbated in debug builds because of the lack of compiler optimization combined with the actual embedded debug information.

A std::map is usually implemented as a red-black tree, but that's unrelated to a hash_map implementation. And yes, IIRC, the STLPort hash_map is the equivalent to linked list when iterating.

edit: bad spelling

[edited by - SiCrane on January 30, 2004 5:53:20 PM]

It appears to be a combination of having stl_port debug mode on and using the hash_map and all the nodes that I had. I had turend on debug mode in stl_port becuase I was needing to track down a problem I had, and all the extra predicate testing helped me track it down first go . I left it on, not thinking it would hit too much ( around 5% ).

quote:

---

and you''re not recalling this iteration function when you recurse on the children are you?

---

I''m not too sure what you mean here? Each node calls the recursive function on its children until it hits the bottom?

The reason I mentioned the map was that i had the same problem with map as i did with hash_map. A hash map iterator is ''slow'' because it has to go through each node of the RB tree I think?

Looks like it was the fact of having the debug mode going I guess.

Thanks heaps for all your guys help

quote:

---

Original post by RobertC

quote:

---

and you''re not recalling this iteration function when you recurse on the children are you?

---

I''m not too sure what you mean here? Each node calls the recursive function on its children until it hits the bottom?

---

What I mean is, what is "the recursive function"? Is it the one you posted, or something else? If you''re coming back to that same point, then something seems to be seriously messed with your logic, because you''re combining iteration and recursion in a strange way.

quote:

---

The reason I mentioned the map was that i had the same problem with map as i did with hash_map. A hash map iterator is ''slow'' because it has to go through each node of the RB tree I think?

---

Like the other poster said, it has nothing to do with RB trees, those are std::maps. There''s a reason it''s called a hash map

Ok there is confusion with what i meant on map, I was just pointing it out as another structure that gave me problems. I didn''t mean that they were related or anything .

The recursive function calls the same function on each child node, so that it iterates through each child node.

So yes it is the same one that i posted, but on the child node.

If each node has only 4 child nodes, don''t you think a hash_map is a bit of overkill?

That is just because of my scene node, I set it up so that other types of nodes could have n sub child nodes, and also wanted to be able to search them by name efficiently.