std::unordered_map and the % operator

[François Dumont]

     I took some time to run a bench for the usage of libdivide (or 
equivalent) into std unordered containers.

     To do so I had to patch the _Hashtable type so that I could inject 
in the implementation a libdivide based denominator used for modulus 
computation. The denominator type you will find in the patch can be 
constructed or assigned from a std::size_t and is also convertible to a 
std::size_t so that it doesn't change anything for the _Hashtable type.

     The results are indeed interesting, in main.cc you will find the 
code I have run to produce following figures:

main.cc                      set<int> libdivide 50000000 insertions    
  594r  451u  142s -2102431760mem    0pf
main.cc                      std::unordered_set<int> 50000000 
insertions     619r  565u   53s -2102431728mem    0pf

     First number is real time which is better, it is the total of 
second number, the user time, which is much better and third time, the 
system time, which is worst. I guess modulo operation was done in user 
time and libdivide operation is done in system time. I hope Ryan will be 
able to elaborate on it, I will assist him to reproduce it on his side.

     I discovered that this technique is already used in gcc, within the 
compiler hashtable itself. In src/gcc/hash-table.c there is a list of 
prime numbers associated with numbers needed to compute the modulo fast. 
If we were to adopt this technique we could do the same and pre-compute 
what we need.

François


On 16/03/2014 20:40, Jonathan Wakely wrote:
> On 16 March 2014 19:31, Ryan Lewis wrote:
>> 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.
> Because the local_iterator contains the hash function. If you want to
> add data to the hash function, you increase its size, and the size of
> anything that contains it.
>
> You can easily verify that by adding a member to the
> _Mod_range_hashing struct, which is the one that would need to be
> replaced to avoid the modulus operation, and checking
> sizeof(unordered_map<int,int>::local_iterator).
>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: hashtable.patch
Type: text/x-patch
Size: 10093 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20140324/28e97e19/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: main.cc
Type: text/x-c++src
Size: 2159 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20140324/28e97e19/attachment-0001.bin>