Prev: Parsing binary wfstream file
Next: const is an overrated concept that is a source of extra typing and maintenance
From: Goran on 1 Apr 2010 20:45
On Mar 31, 6:43 pm, "gast...(a)hotmail.com" <gast...(a)hotmail.com> wrote:
> Hello all,
>
> I am not sure if this is the correct newsgroup, but the information
> might be helpful.
>
> The (stdext::) hash_map in combination with strings (used on VStudio
> 2003 / vc7.1) does not have a good performance. It's actual slower
> than std::map<string, ...>. I noticed however that changing the hash
> function (with boost::hash_value for example) does make it fast again.
> Perhaps there is an issue with the hash function? A small test with
> random strings (up to the a length of 2000) gave the following
> results:
>
> stdext::hash_value with string:
> Mean: 3.73593e+009
> Sum: 373592873859453
> Min: 3735928607
> Max: 3735928779
> Var: 919.648
>
> boost::hash_value with string:
> Mean: 2.67717e+009
> Sum: 267716741970601
> Min: 1230214564
> Max: 4217158627
> Var: 2.11744e+018
>
> It seems that stdext::hash_value has a very narrow distribution, which
> may the root of the bad performance.
>
> note: I am aware of the tr1 / boost unordered_map which will superceed
> it. However this still may be an important issue for developpers who
> dropped hash containers due to bad experience with above combination
> (like myself).

Well, what is your use-case? If it's slower than std::map as it is,
why are you even bothering using a hash map (that is, what, if
anything, do you gain over a lowly map for your use-case with the
boost's hash)?

Also, a reminder for others who might be reading this:

1. any algo is fast for a small value of n (related empirical fact:
optimization is the root of all evil)
2. hardware likes linear searching due to better locality of
references
2. think about your data first. Do you want/will want it ordered? If
so, use an ordered container (set or map).
3. did you verify that hashing really is significantly more performant
than an ordered container?

Goran.


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 | 
Pages: 1
Prev: Parsing binary wfstream file
Next: const is an overrated concept that is a source of extra typing and maintenance