std::unordered_map and the % operator

[François Dumont]

     That sounds like a very promizing enhancement because since we 
adopt this data structure a couple of versions ago the cost of the 
modulus became even more important.

   i will try to help, I will see if I can isolate the modulus part so 
that it can be easily replaced by the usage of libdivide.

François


On 16/03/2014 20:31, Ryan Lewis wrote:
> 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).