Re: hash_multimap

[Gabe Foster <gabe at sgrail dot com>]

SEGV wrote:
> 
> I'm using (on Linux):
> 
>     gcc version egcs-2.90.29 980515 (egcs-1.0.3 release)
> 
> I'm animating some stuff that goes through STL containers, specifically a
> multimap. It has to do this 30 frames per second, and I can tell if it lags.
> 
> I thought I'd use a hash_multimap, even though it isn't Standard C++, to speed
> things up with more items. I found the hashed associative containers in my C++
> headers, as supplied by SGI.
> 
> However, I found things quite slower with the hashed containers, which is not
> what I would have expected. Below are four measurements, with 50 then 100 items.
> 
> items multimap hash_multimap
> ----------------------------
> 50:     0ms+ vs  -35ms
> 100:  -75ms  vs -245ms
> 
> You can see at 50 items, the multimap does not lag, and at 100 items it lags
> 75ms per frame. However, at 50 items the hash_multimap already lags 35ms, and a
> whopping 245ms at 100 items.
> 
Sounds like you've got a bad hash function to me.  If you don't have a
good one, hash_multimap can go from O(1) to O(N).  This is noted in the
STL documentation:

http://www.sgi.com/Technology/STL/HashedAssociativeContainer.html

I did not see a way to get hashing statistics from the container, but
you might try your hashing function on some sample data and see if it
tends to produce the same numbers.

-- 
 * J. Gabriel Foster         Silicon Grail       gabe@sgrail.com *
 *                   Cashing in on being a nerd.                 *