Re: [boost] [hash] regular behaviour of hash function for double values

Subject: Re: [boost] [hash] regular behaviour of hash function for double values
From: Topher Cooper (topher_at_[hidden])
Date: 2012-02-01 17:03:14

On 2/1/2012 12:59 PM, Stephan T. Lavavej wrote:
> Integer divisions are surprisingly expensive, relatively speaking. While changing deque, we introduced integer divisions that noticeably harmed performance. We got rid of them (restoring the perf and then some) by introducing a power-of-2 guarantee that let us use bitwise operations instead.
>
> Of course, this will only matter in very high performance code, like the fundamental operations performed by a container.
>
> STL
>    
Ah, good.  Something non-contentious that I can contribute.

There is a standard technique used in hashing and some other situations, 
that allows a divide/mod to reduce a value to an arbitrary range with a 
multiply and shift (frequently, in practice, multiplying into a wider 
width location, then indexing).  For this to work well, however, higher 
order bits/digits/oits/hits/... must be well distributed.  If this 
cannot be relied upon, techniques like bit rotates, swapping halves, 
xor-oring low bytes onto the high ones or doing a multiply by a constant 
ignoring overflow, before applying the algorithm can fix things.

The technique is to multiply the original value by the range and just 
use the overflow.  Just think of the value to be hashed as the numerator 
of a rational with one plus the maximum value as the denominator.

Topher