martinus / robin-hood-hashing

Fast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20
https://gitter.im/martinus/robin-hood-hashing
MIT License
1.5k stars 142 forks source link

robin_hood.h: Change hash val shifts for `info` and `idx` generation #148

Open goldsteinn opened 2 years ago

goldsteinn commented 2 years ago

Instead of generating the info hash bits with a mask + shift, we can just use an unsigned shift from the end as that will bring in zeros.

With that change the idx hash bits can start from the begining so we no longer need to shift out the info hash bits.

Saves 2x instructions. Only ALU but this function is in the critical path.

There does not appear to be any issue with false hits changing the tag bits used.

False Tag Match Rates:

                  :   New,   Cur

Insert Seq Ints: 2^10 : 2.539, 2.832 2^12 : 3.076, 3.003 2^14 : 2.960, 3.497 2^16 : 4.048, 4.306 2^18 : 4.543, 4.732 2^20 : 5.182, 5.553 2^22 : 5.579, 5.557 2^24 : 6.237, 6.017 2^26 : 6.599, 6.432

Insert Rand Ints (seed = 0): 2^10 : 2.637, 4.199 2^12 : 2.979, 3.613 2^14 : 3.662, 3.955 2^16 : 4.309, 4.849 2^18 : 4.626, 4.564 2^20 : 4.849, 5.044 2^22 : 6.050, 5.279 2^24 : 5.664, 6.350 2^26 : 6.640, 6.771

Insert Strings: All Words(0) : 4.974, 5.231 10k Words(1) : 3.550, 4.000 URLS(2) : 5.548, 5.683 URLS(2) w/ "http://" : 5.466, 5.831 URLS(2) w/ "https://" : 5.569, 5.761