🔒 Locked

Optimizing stdext::hash_map

Started by blaze02 Jun 13, 2007 at 9:25 PM 2 replies 3.3k views

Original Post

Jun 13, 2007 at 9:25 PM

I had this idea about optimizing our app. The first thing it does is load 40,000+ variables into a hash_map. The idea is to remember how much space is needed to load everything, and reserve that space before attempting to load all the variables. If I was working with a vector, this would be easy using .size to get the amount of memory and .reserve to allocate it. But with a hash_map, it is proving much harder. Is it possible to reserve space in a hash_map? Is it possible to determine how much space a hash_map currently has allocated? Thanks.

Driv3MeFar

107

Driv3MeFar

Jun 13, 2007 at 9:36 PM

There is a hash_map::size() function, which just returns the number of elements the map contains, but I suspect that's different from how much space the map has allocated.

I guess if it's a major concern, you could always write a custom allocator for it...

Edit: On second thought, hash_map::get_allocator().allocate() may work. I've never bothered with that stuff before, so I don't know exactly how it works, but it's worth a shot.

T1Oracle

Jun 13, 2007 at 10:02 PM

I think that stl style allocators are broken for associative types.

Quote:
Quoted from: Scott Meyers Effective STL
most standard containers never ask their associated allocated for memory. Never.

Although I believe it says that types which do not have nodes (ie: non-associative containers) use allocators.

I don't know if that applies to hash_map as well since it is not standard, but I wouldn't bet on stl allocators to help you.

*edit* As for reserving space, I am certain that you are out of luck on that one.

Look here

blaze02

Author

blaze02

Jun 14, 2007 at 4:31 AM

Hash maps usually grow at some threshold, so I would assume the amount of space to reserve would be something like:
map.size() * 1.25 //threshold = 80%

But that won't help if we can't tell it to reserve to a specific size.

As for the reserving the space, the container must be smart enough to optimize large inserts. It looks like the loading algorithm needs to load the hash_map entries into a vector with reserved size, then inserted into the hash_map all at once.

Quote:
Quoted from: Scott Meyers Effective STL
most standard containers never ask their associated allocated for memory. Never.

Where are the boost evangelists when you need them?

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.