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.
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk