Re: std::unordered_map and the % operator

[Ryan Lewis <me at ryanlewis dot net>]

Hi,

I have my benchmarks that lead me to this conclusion and would happily
provide them.  I use the Zoom profiler by RotateRight, so i'm not sure
the best way to hand you the data, but, here are some screen captures:

http://imgur.com/a/ES44j

I'd be happy to provide the zoom profiles, but exporting them to txt
is not very useful. You'll need to get Zoom (there is   free trial) to
see them.

The summary is that of the nearly 5 seconds that my code spends in
this code path, about 3.5 of them are doing the mod, bucket access,
and search. The first two parts of this process, are together, just as
long as the search. The search itself, is never on more than 8
elements. That itself is suggests possibly poor cache access, but,
more experiments are warranted.

I'm not sure I see why a local_iterator would need to store the extra
struct, but, i'll take your word for it.

I was trying to provide an implementation of this by inheriting from
unordered_map and overloading the appropriate functions, but, I can't
seem to figure out how to convert a local_iterator an a normal
iterator to implement find correctly.

It would be create if someone could provide an experimental version of
this change just to see what happens with it. I'm sure the appropriate
developer could make the appropriate changes much faster that I would
be able it.

Best,
-rhl


On Sun, Mar 16, 2014 at 11:44 AM, Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
> 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).