Rb_tree constructor optimization

François Dumont frs.dumont@gmail.com
Tue May 15 05:31:00 GMT 2018 

On 11/05/2018 14:16, Jonathan Wakely wrote:
> On 06/05/18 16:06 +0200, François Dumont wrote:
>> Here is the rework of this patch.
>>
>>
>> On 02/05/2018 13:49, Jonathan Wakely wrote:
>>> There's no changelog entry with the patch, so to recap, the changes
>>> are:
>>>
>>> - noexcept specifications are automatically deduced instead of being
>>>  stated explicitly.
>>
>> I simplified this part, it is not deduced anymore except for Debug 
>> mode relying on Normal mode qualifications.
>>
>>>
>>> - The allocator-extended move constructors get correct exception
>>>  specifications in Debug Mode (consistent with normal mode). This
>>>  should be done anyway, independent of any other changes.
>> I kept this untouch.
>>>
>>> - We avoid a `if (__x._M_root() != nullptr)` branch in the case where
>>>  the allocator-extended move constructor is used with an always-equal
>>>  allocator, right?
>> Kept too.
>>>
>>> Compilation time for containers is already **much** slower since the
>>> allocator-extended constructors were added for GCC 5.x, despite very
>>> few people ever using those constructors. This patch seems to require
>>> even more work from the compiler to parse constructors nobody uses.
>> I restore direct qualifications.
>>
>>> diff --git a/libstdc++-v3/include/bits/stl_map.h 
>>> b/libstdc++-v3/include/bits/stl_map.h
>>>> index a4a026e..2b8fd27 100644
>>>> --- a/libstdc++-v3/include/bits/stl_map.h
>>>> +++ b/libstdc++-v3/include/bits/stl_map.h
>>>> @@ -240,8 +240,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>>>>
>>>>       /// Allocator-extended move constructor.
>>>>       map(map&& __m, const allocator_type& __a)
>>>> - noexcept(is_nothrow_copy_constructible<_Compare>::value
>>>> -           && _Alloc_traits::_S_always_equal())
>>>> +      noexcept( noexcept(
>>>> +    _Rep_type(std::move(__m._M_t), declval<_Pair_alloc_type>())) )
>>>
>>> All these calls to declval need to be qualified to avoid ADL.
>>>
>>> It seems strange to have a mix of real values and declval expressions,
>>> rather than:
>>>
>>>     _Rep_type(std::declval<_Rep_type>(), 
>>> std::declval<_Pair_alloc_type>())) )
>> I add std:: qualitification and generalized usage.
>>>
>>>>
>>>> -      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
>>>> +    private:
>>>> +      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type)
>>>> + 
>>>> noexcept(is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>::value)
>>>
>>> This is wrong.
>>
>> As stated previously I removed this but based on this remark I also 
>> change the _Rb_tree_impl() qualification so that it doesn't depend 
>> anymore on allocator default constructor qualification.
>>
>> I've added a test for that too.
>>> This can use std::is_nothrow_constructible
>>>
>> Indeed.
>>>> +           "noexcept move constructor with allocator" );
>>>> +
>>>> +struct ExceptLess
>>>
>>> Please name this "ThrowingLess" instead of "ExceptLess", I think
>>> that's more descriptive.
>> I prefered "not_noexcept" prefix cause those operators are not 
>> throwing anything neither.
>>
>> Tested under Linux x86_64, ok to commit ?
>>
>>     * include/bits/stl_tree.h
>>     (_Rb_tree_impl()):
>>     Remove is_nothrow_default_constructible<_Node_allocator> from 
>> noexcept
>>     qualification.
>>     (_Rb_tree_impl(_Rb_tree_impl&&, _Node_allocator&&)): New.
>>     (_Rb_tree(_Rb_tree&&, _Node_allocator&&, std::true_type)): New, 
>> use latter.
>>     (_Rb_tree(_Rb_tree&&, _Node_allocator&&, std::false_type)): New.
>>     (_Rb_tree(_Rb_tree&&, _Node_allocator&&)): Adapt, use latters.
>>     * include/debug/map.h
>>     (map(map&&, const_allocator_type&)): Add noexcept qualitication.
>>     * include/debug/multimap.h
>>     (multimap(multimap&&, const_allocator_type&)): Add noexcept 
>> qualification.
>>     * include/debug/set.h
>>     (set(set&&, const_allocator_type&)): Add noexcept qualitication.
>>     * include/debug/multiset.h
>>     (multiset(multiset&&, const_allocator_type&)): Add noexcept 
>> qualification.
>>     * testsuite/23_containers/map/cons/noexcept_default_construct.cc:
>>     Add checks.
>>     * testsuite/23_containers/map/cons/noexcept_move_construct.cc:
>>     Add checks.
>>     * 
>> testsuite/23_containers/multimap/cons/noexcept_default_construct.cc:
>>     Add checks.
>>     * testsuite/23_containers/multimap/cons/noexcept_move_construct.cc:
>>     Add checks.
>>     * 
>> testsuite/23_containers/multiset/cons/noexcept_default_construct.cc:
>>     Add checks.
>>     * testsuite/23_containers/multiset/cons/noexcept_move_construct.cc:
>>     Add checks.
>>     * testsuite/23_containers/set/cons/noexcept_default_construct.cc:
>>     Add checks.
>>     * testsuite/23_containers/set/cons/noexcept_move_construct.cc:
>>     Add checks.
>>
>> François
>>
>
>> diff --git a/libstdc++-v3/include/bits/stl_tree.h 
>> b/libstdc++-v3/include/bits/stl_tree.h
>> index d0a8448..9e59259 100644
>> --- a/libstdc++-v3/include/bits/stl_tree.h
>> +++ b/libstdc++-v3/include/bits/stl_tree.h
>> @@ -698,8 +698,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>
>>       _Rb_tree_impl()
>>            _GLIBCXX_NOEXCEPT_IF(
>> - is_nothrow_default_constructible<_Node_allocator>::value
>> -        && is_nothrow_default_constructible<_Base_key_compare>::value )
>> +        // is_nothrow_default_constructible<_Node_allocator>::value &&
>> + is_nothrow_default_constructible<_Base_key_compare>::value )
>>       : _Node_allocator()
>>       { }
>
> This part wasn't in the previous patch and seems wrong:
> https://cplusplus.github.io/LWG/issue2455
>
Yes, I must have been tired when I decided to do such a thing.

Here it is again even more simplified. Should I backport the Debug mode 
fix to 8 branch ?

     * include/bits/stl_tree.h
     (_Rb_tree_impl(_Rb_tree_impl&&, _Node_allocator&&)): New.
     (_Rb_tree(_Rb_tree&&, _Node_allocator&&, true_type)): New, use latter.
     (_Rb_tree(_Rb_tree&&, _Node_allocator&&, false_type)): New.
     (_Rb_tree(_Rb_tree&&, _Node_allocator&&)): Adapt, use latters.
     * include/debug/map.h
     (map(map&&, const_allocator_type&)): Add noexcept qualitication.
     * include/debug/multimap.h
     (multimap(multimap&&, const_allocator_type&)): Add noexcept 
qualification.
     * include/debug/set.h
     (set(set&&, const_allocator_type&)): Add noexcept qualitication.
     * include/debug/multiset.h
     (multiset(multiset&&, const_allocator_type&)): Add noexcept 
qualification.
     * testsuite/23_containers/map/cons/noexcept_default_construct.cc:
     Add checks.
     * testsuite/23_containers/map/cons/noexcept_move_construct.cc:
     Add checks.
     * testsuite/23_containers/multimap/cons/noexcept_default_construct.cc:
     Add checks.
     * testsuite/23_containers/multimap/cons/noexcept_move_construct.cc:
     Add checks.
     * testsuite/23_containers/multiset/cons/noexcept_default_construct.cc:
     Add checks.
     * testsuite/23_containers/multiset/cons/noexcept_move_construct.cc:
     Add checks.
     * testsuite/23_containers/set/cons/noexcept_default_construct.cc:
     Add checks.
     * testsuite/23_containers/set/cons/noexcept_move_construct.cc:
     Add checks.

Ok to commit ?

François

-------------- next part --------------
A non-text attachment was scrubbed...
Name: rb_tree.patch
Type: text/x-patch
Size: 14488 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20180515/a9ea78b9/attachment.bin>

More information about the Libstdc++ mailing list