New hashtable power 2 rehash policy

[François Dumont]

Hi

     Here is a patch to introduce a new power of 2 based rehash policy. 
It enhances performance as it avoids modulo float operations. I have 
updated performance benches and here is the result:

54075.cc                        tr1 benches 455r  446u    8s        
0mem    0pf
54075.cc                        std benches 466r  460u    6s        
0mem    0pf
54075.cc                        std2 benches 375r  369u    6s        
0mem    0pf

std2 benches is the one using power of 2 bucket count.

     Note that I made use of __detected_or_t to avoid duplicating all 
the code of _Rehash_base<>.

     It brings a simplification of _Insert<>, it doesn't take a 
_Unique_keys template parameter anymore. It allowed to remove a 
specialization.

     It also improve behavior when we reach maximum number of buckets, 
we won't keep on trying to increase the number as it is impossible.

     Last it fixes a small problem in 54075.cc bench. We were using 
__uset_traits rather than __umset_traits in definition of __umset. 
Results were not the expected ones.

2016-04-22  François Dumont <fdumont@gcc.gnu.org>

     * include/bits/hashtable_policy.h
     (_Prime_rehash_policy::__has_load_factor): New. Mark rehash policy
     having load factor management.
     (_Mask_range_hashing): New.
     (_NextPower2<size_t>): New.
     (_Power2_rehash_policy): New.
     (_Inserts<>): Remove last template parameter _Unique_keys. Use the same
     implementation when keys are unique no matter if iterators are constant
     or not.
     * src/c++11/hashable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
     Consider when last prime number has been reach.
     * testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc:
     New.
     * testsuite/performance/23_containers/insert/54075.cc: Add bench using
     the new hash policy.
     * testsuite/performance/23_containers/insert_erase/41975.cc: Likewise.

Tested under linux x64_86, ok to commit ?

François


-------------- next part --------------
A non-text attachment was scrubbed...
Name: hashtable.patch
Type: text/x-patch
Size: 17473 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20160423/9faed653/attachment.bin>