std::list optimizations

[Jonathan Wakely]

On 21/08/17 21:14 +0200, François Dumont wrote:
>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.

Great, thanks.

> Ok to commit if tests are successful ?

Yes, thanks.