std::unordered_map and the % operator

[Jonathan Wakely]

On 16 March 2014 06:24, Ryan Lewis wrote:
> 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

We're not going to consider changing something like that without
benchmarks, so your first step should be to demonstrate there's a
problem with the existing code.

Storing the extra struct will increase the size of the containers,
which isn't a big deal, but would also increase the size of the
local_iterator type, which might have a performance impact.

Libstdc++'s hash containers are tweakable in a number of ways. It
would be possible to implement an alternative "range hashing" type
that works as you suggest so that can be used optionally, but doesn't
have to replace the default. That would require a few changes to pass
the bucket count to the range hasher so it could update its divisor
(where the default range hasher would ignore the count).