New hashtable power 2 rehash policy

[François Dumont]

Attached patch applied then.

I had to regorganize things a little now that some pieces have been 
integrated in 71181 patch.

2016-05-24  François Dumont  <fdumont@gcc.gnu.org>

     * include/bits/c++config (_GLIBCXX14_USE_CONSTEXPR): New.
     * include/bits/hashtable_policy.h
     (_Prime_rehash_policy::__has_load_factor): New. Mark rehash policy
     having load factor management.
     (_Mask_range_hashing): New.
     (__clp2): New.
     (_Power2_rehash_policy): New.
     (_Inserts<>): Remove last template parameter, _Unique_keys, so that
     partial specializations only depend on whether iterators are constant
     or not.
     * testsuite/23_containers/unordered_set/hash_policy/26132.cc: Adapt to
     test new hash policy.
     * testsuite/23_containers/unordered_set/hash_policy/load_factor.cc:
     Likewise.
     * testsuite/23_containers/unordered_set/hash_policy/rehash.cc:
     Likewise.
     * testsuite/23_containers/unordered_set/insert/hash_policy.cc:
     Likewise.
     * testsuite/23_containers/unordered_set/max_load_factor/robustness.cc:
     Likewise.
     * testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc:
     New.
     * testsuite/performance/23_containers/insert/54075.cc: Add benchmark
     using the new hash policy.
     * testsuite/performance/23_containers/insert_erase/41975.cc: Likewise.

François

On 23/05/2016 13:31, Jonathan Wakely wrote:
> On 17/05/16 22:28 +0200, François Dumont wrote:
>> On 14/05/2016 19:06, Daniel Krügler wrote:
>>> 1) The function __clp2 is declared using _GLIBCXX14_CONSTEXPR, which
>>> means that it is an inline function if and *only* if
>>> _GLIBCXX14_CONSTEXPR really expands to constexpr, otherwise it is
>>> *not* inline, which is probably not intended and could easily cause
>>> ODR problems. I suggest to mark it unconditionally as inline,
>>> regardless of _GLIBCXX14_CONSTEXPR.
>>
>> Maybe _GLIBCXX14_CONSTEXPR should take inline value previous to C++14 
>> mode.
>
> That's probably a good idea.
>
>> For the moment I simply added the inline as done in other situations.
>
> OK, thanks.
>
>>>
>>> 2) Furthermore I suggest to declare __clp2 as noexcept - this is
>>> (intentionally) *not* implied by constexpr.
>>>
>>> 3) Is there any reason, why _Power2_rehash_policy::_M_next_bkt
>>> shouldn't be noexcept?
>>>
>>> 4) Similar to (3) for _Power2_rehash_policy's member functions
>>> _M_bkt_for_elements, _M_need_rehash, _M_state, _M_reset
>> For noexcept I throught we were only adding it if necessary. We might 
>> have to go through a lot of code to find all places where noexcept 
>> could be added. Jonathan will give his feedback.
>
> I'm in favour of adding it anywhere that that definitely can't throw.
> We don't *need* to do that everywhere, but it doesn't hurt.
>
>> For the moment I have added it on all those methods.
>
> Great.
>
>> Thanks for feedback, updated and tested patch attached.
>
> OK for trunk - thanks!
>
>

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