std::unordered_map and the % operator

Ryan Lewis me@ryanlewis.net
Sun Mar 16 06:24:00 GMT 2014


Hi,

I think, it gets better, there is a zlib licensed, no attribution
necessary, existing library for the optimization I am speaking of:
http://libdivide.com/

Maybe the appropriate developer can do this:

One just needs to

- store a libdivide struct
- ensure that the libdivide struct has the right divisor in it (by
updating it within the rehash, and constructors)
- replace the % call in the hashtable_policy.h call

Best,
-rhl


On Thu, Mar 13, 2014 at 12:09 PM, Ryan Lewis <me@ryanlewis.net> wrote:
> Hi,
>
> My apologies I wrote this email late last night and it might not have
> been clear.
>
> My suggestion is that we make the process of modulus operator by the
> bucket size more efficient. Specifically by avoiding the division.
>
> ala:  - http://www.hackersdelight.org/magic.htm
> and/or http://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html
>
> To begin with your last concern that modulus is not division: we can
> clearly replace
>
> hash%(number of buckets) with (number of buckets) - hash/(number of buckets);
>
> now if we can replace the division with something faster that doesn't
> stall the pipeline we are in good shape. Also, it might be the case
> that in the process of computing a/b the modulus might show up. but
> for now lets ignore that.
>
> Luckily this is a well understood problem, see the notes above, but I
> summarize from the second link here:
>
> Suppose we are on a 32 bit bit machine and we wish to compute n/d:
> here n is the hash value and d is the number of buckets.
>
> Precompute these two numbers (e.g. once per rehash):
> -  p = ceil( log_2( d))
> -  m = ceil( 2^(32+p)/d) (this is a 33 bit number, keep only the
> lowest 32 bits).
>
> Now instead of the modulus, we do the division technique above, and
> replace the division with:
> - compute q = (m*n) >> 32 (this becomes one instruction on many processors)
> - compute t = ((n-q) >> 2) + q (this is an overflow safe way of
> compute (n+q) >> 1
> - compute t >> (p-1)
>
> There is even more efficient things to do depending on the specific
> number, as you are probably aware most compilers do this for
> constexpr's.
>
> Best,
> -rhl



More information about the Libstdc++ mailing list