std::list optimizations

[François Dumont]

On 18/08/2017 22:04, Jonathan Wakely wrote:
> On 28/07/17 18:42 +0200, François Dumont wrote:
>> Hi
>>
>>    Completing execution of the testsuite revealed a bug. So here is 
>> the correct version of this patch.
>>
>> François
>>
>> On 21/07/2017 19:14, François Dumont wrote:
>>> Hi
>>>
>>>    Here is a proposal for 2 optimizations in the std::list 
>>> implementation.
>>>
>>>    Optimization on the move constructor taking an allocator for 
>>> always equal allocators. Compare to the version in my previous 
>>> std::list patch I am now doing it at std::list level rather than at 
>>> _List_base level. This way we won't instantiate the insert call and 
>>> we won't check for empty list when the allocator always compare equal.
>>>
>>>    2nd optimization, I replace the _S_distance method by the 
>>> std::distance algo which benefit from the nice [begin(), end()) 
>>> range optimization when cxx11 abi is being used.
>>>
>>>    Note that I am proposing the 2 change in 1 patch to save some 
>>> review time but I can commit those separately.
>>>
>>> Tested under x86_64 Linux normal mode.
>>>
>>>
>>>    * include/bits/stl_list.h
>>>    (_List_base<>::_S_distance): Remove.
>>>    (_List_impl(_List_impl&&, _Node_alloc_type&&)): New.
>>>    (_List_base(_List_base&&, _Node_alloc_type&&)): Use latter.
>>>    (_List_base(_Node_alloc_type&&)): New.
>>>    (_List_base<>::_M_distance, _List_base<>::_M_node_count): Move...
>>>    (list<>::_M_distance, list<>::_M_node_count): ...here. Replace 
>>> calls to
>>>    _S_distance with calls to std::distance.
>>>    (list(list&&, const allocator_type&, true_type)): New.
>>>    (list(list&&, const allocator_type&, false_type)): New.
>>>    (list(list&&, const allocator_type&)): Adapt to call latters.
>>>
>>> Ok to commit ?
>>>
>>> François
>>>
>>
>
>>       _List_base(_List_base&&) = default;
>>
>>       _List_base(_List_base&& __x, _Node_alloc_type&& __a)
>> +      : _M_impl(std::move(__x._M_impl), std::move(__a))
>> +      { }
>> +
>> +      _List_base(_Node_alloc_type&& __a)
>>       : _M_impl(std::move(__a))
>> -      {
>> -    if (__x._M_get_Node_allocator() == _M_get_Node_allocator())
>> -      _M_move_nodes(std::move(__x));
>> -    // else caller must move individual elements.
>> -      }
>> +      { }
>>
>
> I like this change in principle, but it alters the behaviour of an
> existing constructor. Existing code might use the constructor and get
> broken by this.
>
> You can avoid that by leaving the existing constructor alone and
> adding two new ones for new code to use. Reordering the parameters
> will make the new one distinct from the old one:
>
>      // Used when is_always_equal
>      _List_base(_Node_alloc_type&& __a, _List_base&& __x))
>      : _M_impl(std::move(__x._M_impl), std::move(__a))
>      { }

I have chosen this approach and also adapt the _List_impl class to have 
same signature which moreover correspond to order of members so maybe 
not so bad.

>
> _M_distance could be static though, neither version uses the 'this'
> pointer, so it would be called _S_distance.

Applied.

>
> Do those suggestions make sense? The idea is to ensure that a given
> function signature continues to have the same effects. To introduce
> new effects, use a new signature.
>
Sure, I didn't consider the explicit instantiation use case, makes sens.

So here is a new version. I propose to "mark" code kept for backward abi 
compatibility with the _GLIBCXX_INLINE_VERSION. Next time we decide to 
break abi we will just need to look for this macro to know what code can 
be removed.

  Ok to commit if tests are successful ?

François


-------------- next part --------------
A non-text attachment was scrubbed...
Name: list.patch
Type: text/x-patch
Size: 5469 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20170821/5aae2272/attachment.bin>