Improve insert/emplace robustness to self insertion

[François Dumont]

On 29/06/2016 23:30, Jonathan Wakely wrote:
> On 29/06/16 21:36 +0100, Jonathan Wakely wrote:
>> On 29/06/16 21:43 +0200, François Dumont wrote:
>>> As asked here is now a patch to only fix the robustness issue. The 
>>> consequence is that it is reverting the latest optimization as, 
>>> without smart algo, we always need to do a copy to protect against 
>>> insertion of values contained in the vector as shown by new tests.
>>
>> I don't understand. There is no problem with insert(), only with
>> emplace(), so why do both get worse?
>>
>> Also, the problem is with emplacing from an lvalue, so why do the
>> number of operations change for test02 and test03, which are for
>> xvalues and rvalues?
>>
>> I haven't analyzed your patch, but the results seem wrong. We should
>> not have to do any more work to insert rvalues.
>>
>> What am I missing?
>
> It seems to me that the minimal fix would be:
>
> --- a/libstdc++-v3/include/bits/vector.tcc
> +++ b/libstdc++-v3/include/bits/vector.tcc
> @@ -312,7 +312,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>          }
>        else
>          _M_insert_aux(begin() + (__position - cbegin()),
> -                       std::forward<_Args>(__args)...);
> + _Tp(std::forward<_Args>(__args)...));
>        return iterator(this->_M_impl._M_start + __n);
>       }
>
> This causes regressions in the insert_vs_emplace.cc test because we
> insert rvalues using emplace:

This is also why my patch is impacting insert from xvalue or rvalue.

>
>      iterator
>      insert(const_iterator __position, value_type&& __x)
>      { return emplace(__position, std::move(__x)); }
>
> That's suboptimal, since in the general case we need an extra
> construction for emplacing, but we know that we don't need to do that
> when inserting rvalues.

     Why not ? I realized with your remarks that I was missing some 
tests in the new self_insert.cc. The ones to insert an rvalue coming 
from the vector itself. In the attached patch there is those 2 tests, do 
you agree with expected behavior ? For the moment it doesn't check that 
the source value has been indeed moved cause it doesn't, I will update 
it once it does.

     My patch also reorganize a little bit code to avoid redundant 
checks to find out if reallocation is necessary or not. I was also 
thinking about reusing _M_realloc_insert_aux within _M_fill_insert when 
reallocation is needed.

>
> So the correct fix would be to implement inserting rvalues without
> using emplace.
>
> The attached patch is a smaller change, and doesn't change the number
> of operations for insertions, only for emplacing lvalues.
>
>
Ok, go ahead, I will try to rebase mine from yours.

François

-------------- next part --------------
A non-text attachment was scrubbed...
Name: vector_self_insert.patch
Type: text/x-patch
Size: 15767 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20160630/8071f59b/attachment.bin>