Subject: Re: [boost] unordered_map 32bit VS 64bit
From: Andrey Semashev (andrey.semashev_at_[hidden])
Date: 2012-01-26 02:51:50
On Thu, Jan 26, 2012 at 11:29 AM, Daniel James <dnljms_at_[hidden]> wrote:
> On 26 January 2012 07:11, Andrey Semashev <andrey.semashev_at_[hidden]> wrote:
>> Is it possible to always use power-of-2 number of buckets and bitwise
>> operations instead of modulus division?
> Since the container can use arbitrary hash functions, and the
> standard's quality requirements for hash functions aren't very high,
> it's problematic. It might be possible to use a mix function on the
> hash value and then use a power of 2, although that adds to the
> platform specific issues, which I've been trying to avoid - I've had
> enough problems dealing with varying compilers. I'll have to look into
> how much faster it is (if at all). I originally developed this on 32
> bit machines and it didn't seem worth it there.
I think, the problem of insufficient quality of a hash function should
not be solved by the container itself. Those users who provide good
hash functions will just waste CPU cycles if additional hash values
mixing is done within the container.
IMHO, the best way to address this problem is to provide a set of
"good" hash functions for common types (I believe functional/hash
already does this) and possibly a wrapper function that just does bit
mixing in a user-provided hash function. Boost.Unordered docs should
mention these tools and advise to use them to get better performance.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk