std::unordered_map and the % operator

[David Kastrup]

Ryan Lewis <me@ryanlewis.net> writes:

> Hi,
>
> Firstly, thanks to all the developers out there for providing a
> wonderful library.
>
> I am curious about the present implementation of the hash table in
> std::unordered_map.
>
> Clearly we need to ensure that the key is in the range [0,
> bucket_count) however, it seems to be that
> a simple modulus is a huge trouble. In particular, profiling my code,
> I can see that the processor stalls for quite some time on the
> modulus. Of 20 second algorithm, five seconds is spent in calls to
> find(). While at this juncture I am not particularly sure, my profile
> report suggests that the vast majority of this time is spent waiting
> on the modulus. On some machines a divide my take up to 24 cycles,
> versus only 1 or 2 for a multiplication.
>
> I am wondering if you maintainers would accept a specialization of
> this type which supports replacing the modulus with a multiplication
> by a so called magic number (e.g. the multiplicative inverse of the
> bucket_size in Z_n for appropriate n).

Huh?  Why would you pick the multiplicative inverse of the bucket_size
in some Z_n?  For one thing, almost all Z_n require division for
multiplication anyway.  Exceptions are n = 2^k, n = 2^k±1 and, with some
complications, n = 2^k±d for d represented by considerably fewer than k
bits.  However, for anything but size n=2^k, you'd want access to mixed
precision multiplication.  So that's basically feasible mostly in
assembly language.

A multiplicative inverse of the bucket size when n=2^k exists only for
odd bucket sizes.

The main problem is that the multiplicative inverse of the bucket size
does not at all help you figuring out the _modulus_ of a number
regarding the bucket size.  It allows you to do a fast division by the
bucket size when you _know_ in advance that the number you are starting
with is _divisable_ by the bucket size in Z.  But when you know that,
the modulus is trivially 0.

> In particular, this number can be recomputed whenever the bucket_size
> changes and cached. It seems to me that this will be a performance win
> in almost all cases.

I suggest that you try your explanation again.  It may very well be that
you have a feasible idea about what the code should be doing, but the
math you use to explain it does not appear to map usefully to code.

-- 
David Kastrup