Re: [boost] [unordered] request for ways to get more space efficient allocations

From: Daniel James (daniel_james_at_[hidden])
Date: 2008-04-21 10:50:40

On 21/04/2008, David Rodríguez Ibeas <dibeas_at_[hidden]> wrote:
>
> Anyway, Java's HashTable (at least
>  Sun's implementation) uses the opposite approach: hash tables are powers of
>  two. A power of two number of buckets implies that the container is more
>  sensitive to a bad hash function, but the 'modulo' operation can be
>  performed as a left-shift, which is much faster. To minimize the impact of a
>  bad hash function Java implements a second (fast, bitwise operations)
>  hashcode conversion after the user provided function.

Do you mean something like Thomas Wang's integer hash function? (or
maybe exactly like it).

http://www.concentric.net/~Ttwang/tech/inthash.htm

It's a possibility, although I'll probably have to provide a fallback
for when std::size_it isn't known to be 32 or 64 bit (is there anyone
using such a platform nowadays?).

The main appeal of using prime numbers is that they don't require any
assumptions about the platform. And since most STL implementations use
them, the hash function is likely to use them.

> (Note: Java VM modulo
>  an integer division operations are really slow, some real live testing
>  should be performed in C++)

At the moment I'm mostly concentrating on implementing the library
(move semantics, emplace, equality functions, getting it working on
different platforms etc.) and haven't done much work on performance.
I'll get round to it eventually, but if anyone fancies starting on
this now, it could be worked on independently.

Daniel