Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

On 08/07/16 17:38 +0100, Jonathan Wakely wrote:

On 06/07/16 21:46 +0200, François Dumont wrote:

Don't you plan to add it to the testsuite ?


Done with the attached aptch.


Just for completeness, I'm also adding the example from LWG 2164,
which is related.

Tested x86_64, committed to trunk.


commit 23cb1117d3b5073097ab15fcf9c0245aa98de067
Author: redi 
Date:   Tue Jul 12 14:00:11 2016 +

Add std::vector::emplace() testcase from LWG 2164

	* testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc:
	Add testcase from LWG 2164.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@238243 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
index d452b5b..8712216 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
@@ -135,6 +135,20 @@ test04()
   VERIFY( va[0]._i == 1 );
 }
 
+void
+test05()
+{
+  // LWG DR 2164
+  std::vector v;
+  v.reserve(4);
+  v = { 1, 2, 3 };
+  v.emplace(v.begin(), v.back());
+  VERIFY( v[0] == 3 );
+  VERIFY( v[1] == 1 );
+  VERIFY( v[2] == 2 );
+  VERIFY( v[3] == 3 );
+}
+
 int main()
 {
   test01();

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

On 09/07/16 20:29 -0400, David Edelsohn wrote:

On Sat, Jul 9, 2016 at 7:59 PM, Jonathan Wakely  wrote:

On 09/07/16 13:47 -0400, David Edelsohn wrote:


This patch has caused some new libstdc++ testsuite failures on AIX.



Which patch?

My last patch only added a new test, that can't have caused failures
in unrelated tests.

https://gcc.gnu.org/ml/libstdc++-cvs/2016-q3/msg00021.html


I thought that there were a recent set of libstdc++ patches related to
"insert'.


There was one July 4, but nothing since then has been committed, only
discussed. That touched vector::insert, so is highly unlikely to have
changed codegen for __gnu_debug::deque or __gnu_debug::list.


What else could have caused these regressions?  Recent
patches to C++ front-end?


Possibly, I've no idea, I haven't been watching the FE commits.


Thanks, David







FAIL: 23_containers/list/debug/insert4_neg.cc (test for excess errors)

Excess errors:


/tmp/20160708/powerpc-ibm-aix7.1.0.0/libstdc++-v3/include/debug/formatter.h:387:7:
error: __gnu_debug::_Error_formatter&
__gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
char*) [with _Iterator = __gnu_debug::_Safe_iterator
] causes a
section type conflict with __gnu_debug::_Error_formatter&
__gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
char*) [with _Iterator =
__gnu_debug::_Safe_iterator]

FAIL: 23_containers/deque/debug/insert4_neg.cc (test for excess errors)

Excess errors:


/tmp/20160708/powerpc-ibm-aix7.1.0.0/libstdc++-v3/include/debug/formatter.h:387:7:
error: __gnu_debug::_Error_formatter&
__gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
char*) [with _Iterator = __gnu_debug::_Safe_iterator
, std::__debug::deque >]
causes a section type conflict with __gnu_debug::_Error_formatter&
__gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
char*) [with _Iterator =
__gnu_debug::_Safe_iterator, std::__debug::deque >]

Thanks, David

Re: Improve insert/emplace robustness to self insertion

[David Edelsohn]

On Sat, Jul 9, 2016 at 7:59 PM, Jonathan Wakely  wrote:
> On 09/07/16 13:47 -0400, David Edelsohn wrote:
>>
>> This patch has caused some new libstdc++ testsuite failures on AIX.
>
>
> Which patch?
>
> My last patch only added a new test, that can't have caused failures
> in unrelated tests.
>
> https://gcc.gnu.org/ml/libstdc++-cvs/2016-q3/msg00021.html

I thought that there were a recent set of libstdc++ patches related to
"insert'.  What else could have caused these regressions?  Recent
patches to C++ front-end?

Thanks, David

>
>
>
>
>> FAIL: 23_containers/list/debug/insert4_neg.cc (test for excess errors)
>>
>> Excess errors:
>>
>>
>> /tmp/20160708/powerpc-ibm-aix7.1.0.0/libstdc++-v3/include/debug/formatter.h:387:7:
>> error: __gnu_debug::_Error_formatter&
>> __gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
>> char*) [with _Iterator = __gnu_debug::_Safe_iterator
>> ] causes a
>> section type conflict with __gnu_debug::_Error_formatter&
>> __gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
>> char*) [with _Iterator =
>> __gnu_debug::_Safe_iterator> std::__debug::list >]
>>
>> FAIL: 23_containers/deque/debug/insert4_neg.cc (test for excess errors)
>>
>> Excess errors:
>>
>>
>> /tmp/20160708/powerpc-ibm-aix7.1.0.0/libstdc++-v3/include/debug/formatter.h:387:7:
>> error: __gnu_debug::_Error_formatter&
>> __gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
>> char*) [with _Iterator = __gnu_debug::_Safe_iterator
>> , std::__debug::deque >]
>> causes a section type conflict with __gnu_debug::_Error_formatter&
>> __gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
>> char*) [with _Iterator =
>> __gnu_debug::_Safe_iterator> const int*>, std::__debug::deque >]
>>
>> Thanks, David

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

On 09/07/16 13:47 -0400, David Edelsohn wrote:

This patch has caused some new libstdc++ testsuite failures on AIX.


Which patch?

My last patch only added a new test, that can't have caused failures
in unrelated tests.

https://gcc.gnu.org/ml/libstdc++-cvs/2016-q3/msg00021.html




FAIL: 23_containers/list/debug/insert4_neg.cc (test for excess errors)

Excess errors:

/tmp/20160708/powerpc-ibm-aix7.1.0.0/libstdc++-v3/include/debug/formatter.h:387:7:
error: __gnu_debug::_Error_formatter&
__gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
char*) [with _Iterator = __gnu_debug::_Safe_iterator
] causes a
section type conflict with __gnu_debug::_Error_formatter&
__gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
char*) [with _Iterator =
__gnu_debug::_Safe_iterator]

FAIL: 23_containers/deque/debug/insert4_neg.cc (test for excess errors)

Excess errors:

/tmp/20160708/powerpc-ibm-aix7.1.0.0/libstdc++-v3/include/debug/formatter.h:387:7:
error: __gnu_debug::_Error_formatter&
__gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
char*) [with _Iterator = __gnu_debug::_Safe_iterator
, std::__debug::deque >]
causes a section type conflict with __gnu_debug::_Error_formatter&
__gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
char*) [with _Iterator =
__gnu_debug::_Safe_iterator, std::__debug::deque >]

Thanks, David

Re: Improve insert/emplace robustness to self insertion

[David Edelsohn]

This patch has caused some new libstdc++ testsuite failures on AIX.

FAIL: 23_containers/list/debug/insert4_neg.cc (test for excess errors)

Excess errors:

/tmp/20160708/powerpc-ibm-aix7.1.0.0/libstdc++-v3/include/debug/formatter.h:387:7:
error: __gnu_debug::_Error_formatter&
__gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
char*) [with _Iterator = __gnu_debug::_Safe_iterator
] causes a
section type conflict with __gnu_debug::_Error_formatter&
__gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
char*) [with _Iterator =
__gnu_debug::_Safe_iterator]

FAIL: 23_containers/deque/debug/insert4_neg.cc (test for excess errors)

Excess errors:

/tmp/20160708/powerpc-ibm-aix7.1.0.0/libstdc++-v3/include/debug/formatter.h:387:7:
error: __gnu_debug::_Error_formatter&
__gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
char*) [with _Iterator = __gnu_debug::_Safe_iterator
, std::__debug::deque >]
causes a section type conflict with __gnu_debug::_Error_formatter&
__gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
char*) [with _Iterator =
__gnu_debug::_Safe_iterator, std::__debug::deque >]

Thanks, David

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

On 06/07/16 21:46 +0200, François Dumont wrote:

Don't you plan to add it to the testsuite ?


Done with the attached aptch.

On my side I rebase part of my patch to reorganize a little bit code. 
I reintroduced _M_realloc_insert which isolates the code of 
_M_insert_aux used when we need to reallocate memory. So _M_insert_aux 
is used only when insertion can be done in place. It is a nice 
replacement for _M_emplace_back_aux that have been removed. In most of 
vector modifiers we start checking if we need to reallocate or not. 
With this reorganization we don't check it several times. Moreover, as 
soon as we reallocate we know that we don't need to do any temporary 
copy so insert_vs_emplace.cc test04 has been adapted and we now have 
no situation where emplace and insert are not equivalent.


   * include/bits/stl_vector.h (push_back(const value_type&)): Forward
   to _M_realloc_insert.
   (insert(const_iterator, value_type&&)): Forward to _M_insert_rval.
   (_M_realloc_insert): Declare new function.
   (_M_emplace_back_aux): Remove definition.
   * include/bits/vector.tcc (emplace_back(_Args...)):
   Use _M_realloc_insert.
   (insert(const_iterator, const value_type&)): Likewise.
   (_M_insert_rval, _M_emplace_aux): Likewise.
   (_M_emplace_back_aux): Remove declaration.
   (_M_realloc_insert): Define.
   * testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc:
   Adjust expected results for emplacing an lvalue with reallocation.

Tested under Linux x86_64.

Ok to commit ?


This is excellent work, thanks for doing it.

OK for trunk.


commit dd91c89f43bb79bc4e206824341536a234542c64
Author: redi 
Date:   Fri Jul 8 16:35:10 2016 +

	* testsuite/23_containers/vector/modifiers/insert/aliasing.cc: New.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@238169 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/aliasing.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/aliasing.cc
new file mode 100644
index 000..2ef13b4
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/aliasing.cc
@@ -0,0 +1,79 @@
+// Copyright (C) 2016 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// .
+
+// { dg-options "-std=gnu++14" }
+
+#include 
+#include 
+#include 
+
+// See https://gcc.gnu.org/ml/libstdc++/2016-07/msg8.html for background.
+
+struct T
+{
+ T(int v = 0) : value(v) { }
+ T(const T& t);
+ T& operator=(const T& t);
+ void make_child() { child = std::make_unique(value + 10); }
+ std::unique_ptr child;
+ int value;
+};
+
+T::T(const T& t) : value(t.value)
+{
+ if (t.child)
+   child.reset(new T(*t.child));
+}
+
+T& T::operator=(const T& t)
+{
+ value = t.value;
+ if (t.child)
+ {
+   if (child)
+ *child = *t.child;
+   else
+ child.reset(new T(*t.child));
+ }
+ else
+   child.reset();
+ return *this;
+}
+
+void
+test01()
+{
+ std::vector v;
+ v.reserve(3);
+ v.push_back(T(1));
+ v.back().make_child();
+ v.push_back(T(2));
+ v.back().make_child();
+
+ VERIFY(v[1].child->value == 12);
+ VERIFY(v[1].child->child == nullptr);
+
+ v.insert(v.begin(), *v[1].child);
+
+ VERIFY(v[0].value == 12);
+ VERIFY(v[0].child == nullptr);
+}
+
+int main()
+{
+  test01();
+}

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

On 06/07/16 21:46 +0200, François Dumont wrote:

On 05/07/2016 12:47, Jonathan Wakely wrote:

On 04/07/16 15:55 +0100, Jonathan Wakely wrote:

I'm getting nervous about the smart insertion trick to avoid making a
copy, I have a devious testcase in mind which will break with that
change. I'll share the testcase later today.


Here's a testcase which passes with libstdc++ but fails with libc++
because libc++ doesn't make a copy when inserting a T lvalue into
std::vector:

#include 
#include 
#include 

struct T
{
T(int v = 0) : value(v) { }
T(const T& t);
T& operator=(const T& t);
void make_child() { child = std::make_unique(value + 10); }
std::unique_ptr child;
int value;
};

T::T(const T& t) : value(t.value)
{
if (t.child)
  child.reset(new T(*t.child));
}

T& T::operator=(const T& t)
{
value = t.value;
if (t.child)
{
  if (child)
*child = *t.child;
  else
child.reset(new T(*t.child));
}
else
  child.reset();
return *this;
}

int main()
{
std::vector v;
v.reserve(3);
v.push_back(T(1));
v.back().make_child();
v.push_back(T(2));
v.back().make_child();

assert(v[1].child->value == 12);
assert(v[1].child->child == nullptr);

v.insert(v.begin(), *v[1].child);

assert(v[0].value == 12);
assert(v[0].child == nullptr);
}

The problem is that the object being inserted (*v[1].child) is not an
element of the vector, so the optimization assumes it is unchanged by
shuffling the existing elements. That assumption is wrong.

As far as I can see, this program is perfectly valid. It's slightly
contrived to prove a point, but it's not entirely unrealistic code.



Don't you plan to add it to the testsuite ?


Yes, I'm just very busy with other things, I've only been doing
anything on std::vector so you're not waiting too long for responses
:-)

On my side I rebase part of my patch to reorganize a little bit code. 
I reintroduced _M_realloc_insert which isolates the code of 
_M_insert_aux used when we need to reallocate memory. So _M_insert_aux 
is used only when insertion can be done in place. It is a nice 
replacement for _M_emplace_back_aux that have been removed. In most of 
vector modifiers we start checking if we need to reallocate or not. 


Great, I was thinking of doing that kind of refactoring.

I'll review it ASAP.

Re: Improve insert/emplace robustness to self insertion

[François Dumont]

On 05/07/2016 12:47, Jonathan Wakely wrote:

On 04/07/16 15:55 +0100, Jonathan Wakely wrote:

I'm getting nervous about the smart insertion trick to avoid making a
copy, I have a devious testcase in mind which will break with that
change. I'll share the testcase later today.


Here's a testcase which passes with libstdc++ but fails with libc++
because libc++ doesn't make a copy when inserting a T lvalue into
std::vector:

#include 
#include 
#include 

struct T
{
 T(int v = 0) : value(v) { }
 T(const T& t);
 T& operator=(const T& t);
 void make_child() { child = std::make_unique(value + 10); }
 std::unique_ptr child;
 int value;
};

T::T(const T& t) : value(t.value)
{
 if (t.child)
   child.reset(new T(*t.child));
}

T& T::operator=(const T& t)
{
 value = t.value;
 if (t.child)
 {
   if (child)
 *child = *t.child;
   else
 child.reset(new T(*t.child));
 }
 else
   child.reset();
 return *this;
}

int main()
{
 std::vector v;
 v.reserve(3);
 v.push_back(T(1));
 v.back().make_child();
 v.push_back(T(2));
 v.back().make_child();

 assert(v[1].child->value == 12);
 assert(v[1].child->child == nullptr);

 v.insert(v.begin(), *v[1].child);

 assert(v[0].value == 12);
 assert(v[0].child == nullptr);
}

The problem is that the object being inserted (*v[1].child) is not an
element of the vector, so the optimization assumes it is unchanged by
shuffling the existing elements. That assumption is wrong.

As far as I can see, this program is perfectly valid. It's slightly
contrived to prove a point, but it's not entirely unrealistic code.



Don't you plan to add it to the testsuite ?

On my side I rebase part of my patch to reorganize a little bit code. I 
reintroduced _M_realloc_insert which isolates the code of _M_insert_aux 
used when we need to reallocate memory. So _M_insert_aux is used only 
when insertion can be done in place. It is a nice replacement for 
_M_emplace_back_aux that have been removed. In most of vector modifiers 
we start checking if we need to reallocate or not. With this 
reorganization we don't check it several times. Moreover, as soon as we 
reallocate we know that we don't need to do any temporary copy so 
insert_vs_emplace.cc test04 has been adapted and we now have no 
situation where emplace and insert are not equivalent.


* include/bits/stl_vector.h (push_back(const value_type&)): Forward
to _M_realloc_insert.
(insert(const_iterator, value_type&&)): Forward to _M_insert_rval.
(_M_realloc_insert): Declare new function.
(_M_emplace_back_aux): Remove definition.
* include/bits/vector.tcc (emplace_back(_Args...)):
Use _M_realloc_insert.
(insert(const_iterator, const value_type&)): Likewise.
(_M_insert_rval, _M_emplace_aux): Likewise.
(_M_emplace_back_aux): Remove declaration.
(_M_realloc_insert): Define.
* testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc:
Adjust expected results for emplacing an lvalue with reallocation.

Tested under Linux x86_64.

Ok to commit ?

François
diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index 8e8aa7c..85abf4a 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -946,11 +946,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	++this->_M_impl._M_finish;
 	  }
 	else
-#if __cplusplus >= 201103L
-	  _M_emplace_back_aux(__x);
-#else
-	  _M_insert_aux(end(), __x);
-#endif
+	  _M_realloc_insert(end(), __x);
   }
 
 #if __cplusplus >= 201103L
@@ -1436,6 +1432,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
   // Called by insert(p,x)
   void
   _M_insert_aux(iterator __position, const value_type& __x);
+
+  void
+  _M_realloc_insert(iterator __position, const value_type& __x);
 #else
   // A value_type object constructed with _Alloc_traits::construct()
   // and destroyed with _Alloc_traits::destroy().
@@ -1469,16 +1468,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	void
 	_M_insert_aux(iterator __position, _Arg&& __arg);
 
+  template
+	void
+	_M_realloc_insert(iterator __position, _Args&&... __args);
+
   // Either move-construct at the end, or forward to _M_insert_aux.
   iterator
   _M_insert_rval(const_iterator __position, value_type&& __v);
 
-  // Called by push_back(x) and emplace_back(args) when they need to
-  // reallocate.
-  template
-	void
-	_M_emplace_back_aux(_Args&&... __args);
-
   // Try to emplace at the end, otherwise forward to _M_insert_aux.
   template
 	iterator
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 6e9be7f..b291e95 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -98,7 +98,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	++this->_M_impl._M_finish;
 	  }
 	else
-	  _M_emplace_back_aux(std::forward<_Args>(__args)...);
+	  _M_realloc_insert(end(), std::forward<_Args>(__args)...);
   }
 #endif
 
@@ -112,29 +112,32 @@ 

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

On 02/07/16 08:37 +0200, François Dumont wrote:
I haven't consider in this patch your remark about using allocator to 
build instance so don't hesitate to commit what you want and I will 
rebase.


Here's what I've committed to trunk.

I'm getting nervous about the smart insertion trick to avoid making a
copy, I have a devious testcase in mind which will break with that
change. I'll share the testcase later today.


commit 6aa6fa55a89c34c51366ed432bd942e09f691a0b
Author: redi 
Date:   Mon Jul 4 14:52:54 2016 +

Add tests for inserting aliased objects into std::vector

2016-07-04  Fran??ois Dumont  

	* testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc:
	New test.
	* testsuite/23_containers/vector/modifiers/insert/self_insert.cc: New
	test.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@237986 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
new file mode 100644
index 000..d452b5b
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
@@ -0,0 +1,144 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2016 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// .
+
+#include 
+#include "testsuite_hooks.h"
+
+bool test __attribute__((unused)) = true;
+
+void
+test01()
+{
+  std::vector vv =
+{
+  { 2, 3 },
+  { 4, 5 },
+  { 0, 1 }
+};
+
+  // Make sure emplace will imply reallocation.
+  VERIFY( vv.capacity() == 3 );
+
+  vv.emplace(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+void
+test02()
+{
+  std::vector vv =
+{
+  { 2, 3 },
+  { 4, 5 },
+  { 0, 1 }
+};
+
+  // Make sure emplace won't reallocate.
+  vv.reserve(4);
+  vv.emplace(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+struct A
+{
+  A(int i) : _i(i)
+  { }
+
+  A(const A& other) : _i(other._i)
+  {
+VERIFY( other._i >= 0 );
+  }
+
+  A(A&& other) : _i(other._i)
+  {
+VERIFY( other._i >= 0 );
+
+other._i = -1;
+  }
+
+  A(std::vector::iterator it) : _i(it->_i)
+  {
+VERIFY( it->_i >= 0 );
+  }
+
+  A& operator=(const A&) = default;
+  A& operator=(A&& other)
+  {
+VERIFY(other._i >= 0 );
+
+_i = other._i;
+other._i = -1;
+return *this;
+  }
+
+  int _i;
+};
+
+void
+test03()
+{
+  std::vector va =
+{
+  { A(1) },
+  { A(2) },
+  { A(3) }
+};
+
+  // Make sure emplace will imply reallocation.
+  VERIFY( va.capacity() == 3 );
+
+  va.emplace(va.begin(), va.begin());
+
+  VERIFY( va.size() == 4 );
+  VERIFY( va[0]._i == 1 );
+}
+
+void
+test04()
+{
+  std::vector va =
+{
+  { A(1) },
+  { A(2) },
+  { A(3) }
+};
+
+  // Make sure emplace won't reallocate.
+  va.reserve(4);
+  va.emplace(va.begin(), va.begin());
+
+  VERIFY( va.size() == 4 );
+  VERIFY( va[0]._i == 1 );
+}
+
+int main()
+{
+  test01();
+  test02();
+  test03();
+  test04();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc
new file mode 100644
index 000..9944cbb
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc
@@ -0,0 +1,70 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2016 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have 

Re: Improve insert/emplace robustness to self insertion

[François Dumont]

On 01/07/2016 11:54, Jonathan Wakely wrote:

On 30/06/16 21:51 +0200, François Dumont wrote:

On 29/06/2016 23:30, Jonathan Wakely wrote:


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.


No, I don't agree, because this is undefined behaviour:

  vv.insert(vv.begin(), std::move(vv[0]));

We don't need to support that case.


Ok but management of this kind of code is a nice consequence of using 
the smart insertion trick.




17.6.4.9 [res.on.arguments] says:

— If a function argument binds to an rvalue reference parameter, the
 implementation may assume that this parameter is a unique reference
 to this argument.

i.e. when passed an rvalue we can assume it is not a reference to
something in the container.

That's why we should not perform any more operations when inserting
rvalues than we do now. Any increase in copies/moves for inserting
rvalues is a regression, and should be avoided


Agree so in attached patch I have implemented the smart insertion trick 
to come back to optimal copies/moves. We don't need to do much to do 
better than Standard requirement and especially not additional copies/moves.


I haven't consider in this patch your remark about using allocator to 
build instance so don't hesitate to commit what you want and I will rebase.


François

diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index c37880a..d7435cc 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -1432,17 +1432,33 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #endif
 
   // Called by insert(p,x)
+  void
+  _M_insert_aux(iterator __position, const value_type& __x)
+  { _M_insert_value_aux(__position, __x); }
+
 #if __cplusplus < 201103L
   void
-  _M_insert_aux(iterator __position, const value_type& __x);
+  _M_insert_value_aux(iterator __position, const value_type& __x);
 
   void
   _M_realloc_insert_aux(iterator __position, const value_type& __x);
 #else
+  template
+void
+_M_insert_value_aux(iterator __position, _Val&& __x);
+
   template
 	void
 	_M_insert_aux(iterator __position, _Args&&... __args);
 
+  void
+  _M_insert_aux(iterator __position, value_type& __x)
+  { _M_insert_value_aux(__position, __x); }
+
+  void
+  _M_insert_aux(iterator __position, value_type&& __x)
+  { _M_insert_value_aux(__position, std::move(__x)); }
+
   template
 void
 _M_realloc_insert_aux(iterator __position, _Args&&... __args);
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 9061593..fe57db2 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -56,6 +56,8 @@
 #ifndef _VECTOR_TCC
 #define _VECTOR_TCC 1
 
+#include  // For std::less.
+
 namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
@@ -120,9 +122,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  }
 	else
 #if __cplusplus >= 201103L
-	  _M_insert_aux(begin() + (__position - cbegin()), __x);
+	  _M_insert_value_aux(begin() + (__position - cbegin()), __x);
 #else
-	  _M_insert_aux(__position, __x);
+	  _M_insert_value_aux(__position, __x);
 #endif
   else
 #if __cplusplus >= 201103L
@@ -323,28 +325,46 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
   void
   vector<_Tp, _Alloc>::
   _M_insert_aux(iterator __position, _Args&&... __args)
+  {
+	_Tp __x_copy(std::forward<_Args>(__args)...);
+	_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+ std::move(*(this->_M_impl._M_finish - 1)));
+	std::move_backward(__position.base(), this->_M_impl._M_finish - 1,
+			   this->_M_impl._M_finish);
+
+	++this->_M_impl._M_finish;
+
+	*__position = std::move(__x_copy);
+  }
+
+  template
+template
+  void
+  vector<_Tp, _Alloc>::
+  _M_insert_value_aux(iterator __position, _Val&& __x)
 #else
   template
 void
 vector<_Tp, _Alloc>::
-_M_insert_aux(iterator __position, const _Tp& __x)
+_M_insert_value_aux(iterator __position, const _Tp& __x)
 #endif
-  {
-#if __cplusplus >= 201103L
-	_Tp __x_copy(std::forward<_Args>(__args)...);
-#else
-	_Tp __x_copy(__x);
-#endif
-	_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
- _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1)));
-	++this->_M_impl._M_finish;
+{
+  

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

On 01/07/16 10:54 +0100, Jonathan Wakely wrote:

On 30/06/16 21:51 +0200, François Dumont wrote:

On 29/06/2016 23:30, Jonathan Wakely wrote:


   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.


No, I don't agree, because this is undefined behaviour:

 vv.insert(vv.begin(), std::move(vv[0]));

We don't need to support that case.

17.6.4.9 [res.on.arguments] says:

— If a function argument binds to an rvalue reference parameter, the
implementation may assume that this parameter is a unique reference
to this argument.

i.e. when passed an rvalue we can assume it is not a reference to
something in the container.

That's why we should not perform any more operations when inserting
rvalues than we do now. Any increase in copies/moves for inserting
rvalues is a regression, and should be avoided.



Here's what I'm planning to commit soon. This also fixes a problem
where the temporaries we create are not constructed+destroyed with the
allocator, which they must be.


commit 6012a80b33eab6501cd620fb710f9805d21cc4b3
Author: Jonathan Wakely 
Date:   Fri Jul 1 16:49:15 2016 +0100

Add tests for inserting aliased objects into std::vector

2016-07-01  Fran??ois Dumont  

	* testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc:
	New test.
	* testsuite/23_containers/vector/modifiers/insert/self_insert.cc: New
	test.

diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
new file mode 100644
index 000..d452b5b
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
@@ -0,0 +1,144 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2016 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// .
+
+#include 
+#include "testsuite_hooks.h"
+
+bool test __attribute__((unused)) = true;
+
+void
+test01()
+{
+  std::vector vv =
+{
+  { 2, 3 },
+  { 4, 5 },
+  { 0, 1 }
+};
+
+  // Make sure emplace will imply reallocation.
+  VERIFY( vv.capacity() == 3 );
+
+  vv.emplace(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+void
+test02()
+{
+  std::vector vv =
+{
+  { 2, 3 },
+  { 4, 5 },
+  { 0, 1 }
+};
+
+  // Make sure emplace won't reallocate.
+  vv.reserve(4);
+  vv.emplace(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+struct A
+{
+  A(int i) : _i(i)
+  { }
+
+  A(const A& other) : _i(other._i)
+  {
+VERIFY( other._i >= 0 );
+  }
+
+  A(A&& other) : _i(other._i)
+  {
+VERIFY( other._i >= 0 );
+
+other._i = -1;
+  }
+
+  A(std::vector::iterator it) : _i(it->_i)
+  {
+VERIFY( it->_i >= 0 );
+  }
+
+  A& operator=(const A&) = default;
+  A& operator=(A&& other)
+  {
+VERIFY(other._i >= 0 );
+
+_i = other._i;
+other._i = -1;
+return *this;
+  }
+
+  int _i;
+};
+
+void
+test03()
+{
+  std::vector va =
+{
+  { A(1) },
+  { A(2) },
+  { A(3) }
+};
+
+  // Make sure emplace will imply reallocation.
+  VERIFY( va.capacity() == 3 );
+
+  va.emplace(va.begin(), va.begin());
+
+  VERIFY( va.size() == 4 );
+  VERIFY( va[0]._i == 1 );
+}
+
+void
+test04()
+{
+  std::vector va =
+{
+  { A(1) },
+  { A(2) },
+  { A(3) }
+};
+
+  // Make sure emplace won't reallocate.
+  va.reserve(4);
+  va.emplace(va.begin(), va.begin());
+
+  VERIFY( va.size() == 4 );
+  VERIFY( va[0]._i == 1 );
+}
+
+int main()
+{

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

On 30/06/16 21:51 +0200, François Dumont wrote:

On 29/06/2016 23:30, Jonathan Wakely wrote:


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.


No, I don't agree, because this is undefined behaviour:

  vv.insert(vv.begin(), std::move(vv[0]));

We don't need to support that case.

17.6.4.9 [res.on.arguments] says:

— If a function argument binds to an rvalue reference parameter, the
 implementation may assume that this parameter is a unique reference
 to this argument.

i.e. when passed an rvalue we can assume it is not a reference to
something in the container.

That's why we should not perform any more operations when inserting
rvalues than we do now. Any increase in copies/moves for inserting
rvalues is a regression, and should be avoided.

Re: 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

diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index eaafa22..c37880a 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -949,7 +949,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __cplusplus >= 201103L
 	  _M_emplace_back_aux(__x);
 #else
-	  _M_insert_aux(end(), __x);
+	  _M_realloc_insert_aux(end(), __x);
 #endif
   }
 
@@ -1435,21 +1435,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __cplusplus < 201103L
   void
   _M_insert_aux(iterator __position, const value_type& __x);
-#else
-  template
-	static void
-	_S_insert_aux_assign(iterator __pos, _Args&&... __args)
-	{ *__pos =  _Tp(std::forward<_Args>(__args)...); }
-
-  static void
-  _S_insert_aux_assign(iterator __pos, _Tp&& __arg)
-  { *__pos = std::move(__arg); }
 
+  void
+  _M_realloc_insert_aux(iterator __position, const value_type& __x);
+#else
   template
 	void
 	_M_insert_aux(iterator __position, _Args&&... __args);
 
   template
+void
+_M_realloc_insert_aux(iterator __position, _Args&&... __args);
+
+  template
 	void
 	_M_emplace_back_aux(_Args&&... __args);
 #endif
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 604be7b..9061593 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -112,27 +112,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #endif
 {
   const size_type __n = __position - begin();
-  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
-	  && __position == end())
-	{
-	  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
-	  ++this->_M_impl._M_finish;
-	}
+  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+	if (__position == end())
+	  {
+	_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
+	++this->_M_impl._M_finish;
+	  }
+	else
+#if __cplusplus >= 201103L
+	  _M_insert_aux(begin() + (__position - cbegin()), __x);
+#else
+	  _M_insert_aux(__position, __x);
+#endif
   else
-	{
 #if __cplusplus >= 201103L
-	  const auto __pos = begin() + (__position - cbegin());
-	  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
-	{
-	  _Tp __x_copy = __x;
-	  _M_insert_aux(__pos, std::move(__x_copy));
-	}
-	  else
-	_M_insert_aux(__pos, __x);
+	

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

On 29/06/16 21:43 +0200, François Dumont wrote:
I tried those changes too but started having failing tests in 
vector/ext_pointer so prefer to not touch that for the moment. I think 
the compilation error was coming from the change of begin() + 
(__position - cbegin()) into begin() + __n because of overloaded 
operator+. The 2 other changes should be fine for a future patch.


By the way, I fixed that in my patch too. The problem was that __n had
type size_type, but for adding to iterators it should really be
difference_type. Simply using auto makes it work :-)

Unless you see any problems in my patch I'll finish testing it
tomorrow and commit it with your new testcases.

Thanks for inspiring me to investigate what we were doing wrong! :-)

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

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:

 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.

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.


diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index eaafa22..4f43c8e 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -981,6 +981,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
   }
 
 #if __cplusplus >= 201103L
+private:
+  iterator
+  _M_emplace_aux(const_iterator __position, value_type&& __v)
+  { return insert(__position, std::move(__v)); }
+
+  template
+	iterator
+	_M_emplace_aux(const_iterator __position, _Args&&... __args)
+	{ return insert(__position, _Tp(std::forward<_Args>(__args)...)); }
+
+public:
   /**
*  @brief  Inserts an object in %vector before specified iterator.
*  @param  __position  A const_iterator into the %vector.
@@ -995,7 +1006,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
*/
   template
 	iterator
-	emplace(const_iterator __position, _Args&&... __args);
+	emplace(const_iterator __position, _Args&&... __args)
+	{ return _M_emplace_aux(__position, std::forward<_Args>(__args)...); }
 
   /**
*  @brief  Inserts given value into %vector before specified iterator.
@@ -1039,8 +1051,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
*  used the user should consider using std::list.
*/
   iterator
-  insert(const_iterator __position, value_type&& __x)
-  { return emplace(__position, std::move(__x)); }
+  insert(const_iterator __position, value_type&& __x);
 
   /**
*  @brief  Inserts an initializer_list into the %vector.
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 9cb5464..fbcab84 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -297,24 +297,22 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
 #if __cplusplus >= 201103L
   template
-template
-  typename vector<_Tp, _Alloc>::iterator
-  vector<_Tp, _Alloc>::
-  emplace(const_iterator __position, _Args&&... __args)
-  {
-	const size_type __n = __position - begin();
-	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
-	&& __position == end())
-	  {
-	_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
- std::forward<_Args>(__args)...);
-	++this->_M_impl._M_finish;
-	  }
-	else
-	  _M_insert_aux(begin() + (__position - cbegin()),
-			std::forward<_Args>(__args)...);
-	return iterator(this->_M_impl._M_start + __n);
-  }
+auto
+vector<_Tp, _Alloc>::
+insert(const_iterator __position, value_type&& __v) -> iterator
+{
+  const auto __n = __position - cbegin();
+  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
+	  && __position == cend())
+	{
+	  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+   std::move(__v));
+	  ++this->_M_impl._M_finish;
+	}
+  else
+	_M_insert_aux(begin() + __n, std::move(__v));
+  return iterator(this->_M_impl._M_start + __n);
+}
 
   template
 template
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
index 

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

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?



diff --git 
a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc 
b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
index 39a3f03..8bd72b7 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
@@ -149,7 +149,7 @@ test01()
void
test02()
{
-  const X::special expected{ 0, 0, 0, 0, 1, 3 };
+  const X::special expected{ 0, 1, 0, 0, 2, 3 };
  X::special ins, emp;
  {
std::vector v;
@@ -187,7 +187,7 @@ test02()
void
test03()
{
-  const X::special expected{ 1, 1, 0, 0, 1, 3 };
+  const X::special expected{ 1, 2, 0, 0, 2, 3 };
  X::special ins, emp;
  {
std::vector v;

Re: Improve insert/emplace robustness to self insertion

[François Dumont]

On 29/06/2016 11:10, Jonathan Wakely wrote:

On 28/06/16 21:59 +0200, François Dumont wrote:

@@ -303,16 +301,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
  emplace(const_iterator __position, _Args&&... __args)
  {
const size_type __n = __position - begin();


It looks like this should use __position - cbegin(), to avoid an
implicit conversion from iterator to const_iterator, and ...


-if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
-&& __position == end())
-  {
-_Alloc_traits::construct(this->_M_impl, 
this->_M_impl._M_finish,

- std::forward<_Args>(__args)...);
-++this->_M_impl._M_finish;
-  }
+if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+  if (__position == end())


This could be __position == cend(), and ...


+{
+  _Alloc_traits::construct(this->_M_impl, 
this->_M_impl._M_finish,

+   std::forward<_Args>(__args)...);
+  ++this->_M_impl._M_finish;
+}
+  else
+_M_insert_aux(begin() + (__position - cbegin()),


This could use __n, and ...


+ std::forward<_Args>(__args)...);
else
-  _M_insert_aux(begin() + (__position - cbegin()),
-std::forward<_Args>(__args)...);
+  _M_realloc_insert_aux(begin() + (__position - cbegin()),


This could also use __n.


+ std::forward<_Args>(__args)...);
+
return iterator(this->_M_impl._M_start + __n);
  }


.

I tried those changes too but started having failing tests in 
vector/ext_pointer so prefer to not touch that for the moment. I think 
the compilation error was coming from the change of begin() + 
(__position - cbegin()) into begin() + __n because of overloaded 
operator+. The 2 other changes should be fine for a future patch.


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.


François
diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index eaafa22..c37880a 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -949,7 +949,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __cplusplus >= 201103L
 	  _M_emplace_back_aux(__x);
 #else
-	  _M_insert_aux(end(), __x);
+	  _M_realloc_insert_aux(end(), __x);
 #endif
   }
 
@@ -1435,21 +1435,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __cplusplus < 201103L
   void
   _M_insert_aux(iterator __position, const value_type& __x);
-#else
-  template
-	static void
-	_S_insert_aux_assign(iterator __pos, _Args&&... __args)
-	{ *__pos =  _Tp(std::forward<_Args>(__args)...); }
-
-  static void
-  _S_insert_aux_assign(iterator __pos, _Tp&& __arg)
-  { *__pos = std::move(__arg); }
 
+  void
+  _M_realloc_insert_aux(iterator __position, const value_type& __x);
+#else
   template
 	void
 	_M_insert_aux(iterator __position, _Args&&... __args);
 
   template
+void
+_M_realloc_insert_aux(iterator __position, _Args&&... __args);
+
+  template
 	void
 	_M_emplace_back_aux(_Args&&... __args);
 #endif
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 604be7b..9061593 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -112,27 +112,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #endif
 {
   const size_type __n = __position - begin();
-  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
-	  && __position == end())
-	{
-	  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
-	  ++this->_M_impl._M_finish;
-	}
+  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+	if (__position == end())
+	  {
+	_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
+	++this->_M_impl._M_finish;
+	  }
+	else
+#if __cplusplus >= 201103L
+	  _M_insert_aux(begin() + (__position - cbegin()), __x);
+#else
+	  _M_insert_aux(__position, __x);
+#endif
   else
-	{
 #if __cplusplus >= 201103L
-	  const auto __pos = begin() + (__position - cbegin());
-	  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
-	{
-	  _Tp __x_copy = __x;
-	  _M_insert_aux(__pos, std::move(__x_copy));
-	}
-	  else
-	_M_insert_aux(__pos, __x);
+	_M_realloc_insert_aux(begin() + (__position - cbegin()), __x);
 #else
-	_M_insert_aux(__position, __x);
+	_M_realloc_insert_aux(__position, __x);
 #endif
-	}
+
   return iterator(this->_M_impl._M_start + __n);
 }
 
@@ -303,16 +301,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
   emplace(const_iterator __position, _Args&&... __args)
   {
 	const size_type __n = __position - begin();
-	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
-	&& __position == end())
-	  

Re: Improve insert/emplace robustness to self insertion

[Paolo Carlini]

Hi,

On 29/06/2016 12:07, Jonathan Wakely wrote:

On 29/06/16 11:35 +0200, Paolo Carlini wrote:

Hi,

On 29/06/2016 10:57, Jonathan Wakely wrote:

On 28/06/16 21:59 +0200, François Dumont wrote:

+  if (_M_data_ptr(__position.base()) <= __ptr
+  && __ptr < _M_data_ptr(this->_M_impl._M_finish - 1))


This is undefined behaviour. If the object is not contained in the
vector then you can't compare its address to addresses within the
vector.


Uhm, would that be true also if the code used std::less? Aren't we 
doing something like that in std::basic_string under the assumption 
(Nathan?) that it would not be the case? Or maybe I'm misreading the 
code (admittedly I didn't follow in detail the whole exchange)


Yes, it's OK if you use std::less. In general there's no guarantee
that std::less defines the same order as operator<(T*, T*), but in
our implementation it does.

Ah Ok, excellent.


I'd still prefer to keep a correctness fix and a potentially risky
optimisation in separate commits.


Definitely. Maybe with an additional comment too!

Paolo.

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

On 29/06/16 11:35 +0200, Paolo Carlini wrote:

Hi,

On 29/06/2016 10:57, Jonathan Wakely wrote:

On 28/06/16 21:59 +0200, François Dumont wrote:

+  if (_M_data_ptr(__position.base()) <= __ptr
+  && __ptr < _M_data_ptr(this->_M_impl._M_finish - 1))


This is undefined behaviour. If the object is not contained in the
vector then you can't compare its address to addresses within the
vector.


Uhm, would that be true also if the code used std::less? Aren't we 
doing something like that in std::basic_string under the assumption 
(Nathan?) that it would not be the case? Or maybe I'm misreading the 
code (admittedly I didn't follow in detail the whole exchange)


Yes, it's OK if you use std::less. In general there's no guarantee
that std::less defines the same order as operator<(T*, T*), but in
our implementation it does.

I'd still prefer to keep a correctness fix and a potentially risky
optimisation in separate commits.

Re: Improve insert/emplace robustness to self insertion

[Paolo Carlini]

Hi,

On 29/06/2016 10:57, Jonathan Wakely wrote:

On 28/06/16 21:59 +0200, François Dumont wrote:

+  if (_M_data_ptr(__position.base()) <= __ptr
+  && __ptr < _M_data_ptr(this->_M_impl._M_finish - 1))


This is undefined behaviour. If the object is not contained in the
vector then you can't compare its address to addresses within the
vector.


Uhm, would that be true also if the code used std::less? Aren't we doing 
something like that in std::basic_string under the assumption (Nathan?) 
that it would not be the case? Or maybe I'm misreading the code 
(admittedly I didn't follow in detail the whole exchange)


Paolo.

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

On 28/06/16 21:59 +0200, François Dumont wrote:

@@ -303,16 +301,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
  emplace(const_iterator __position, _Args&&... __args)
  {
const size_type __n = __position - begin();


It looks like this should use __position - cbegin(), to avoid an
implicit conversion from iterator to const_iterator, and ...


-   if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
-   && __position == end())
- {
-   _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
-std::forward<_Args>(__args)...);
-   ++this->_M_impl._M_finish;
- }
+   if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+ if (__position == end())


This could be __position == cend(), and ...


+   {
+ _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+  std::forward<_Args>(__args)...);
+ ++this->_M_impl._M_finish;
+   }
+ else
+   _M_insert_aux(begin() + (__position - cbegin()),


This could use __n, and ...


+ std::forward<_Args>(__args)...);
else
- _M_insert_aux(begin() + (__position - cbegin()),
-   std::forward<_Args>(__args)...);
+ _M_realloc_insert_aux(begin() + (__position - cbegin()),


This could also use __n.


+   std::forward<_Args>(__args)...);
+
return iterator(this->_M_impl._M_start + __n);
  }

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

On 28/06/16 21:59 +0200, François Dumont wrote:

  template
void
vector<_Tp, _Alloc>::
-_M_insert_aux(iterator __position, const _Tp& __x)
+_M_insert_value_aux(iterator __position, const _Tp& __x)
#endif
{
-  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+  const _Tp* __ptr = std::__addressof(__x);
+
+  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+  _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1)));
+  ++this->_M_impl._M_finish;
+
+  _GLIBCXX_MOVE_BACKWARD3(__position.base(),
+ this->_M_impl._M_finish - 2,
+ this->_M_impl._M_finish - 1);
+
+  if (_M_data_ptr(__position.base()) <= __ptr
+ && __ptr < _M_data_ptr(this->_M_impl._M_finish - 1))


This is undefined behaviour. If the object is not contained in the
vector then you can't compare its address to addresses within the
vector.

I suggest forgetting about this optimisation unless we get a guarantee
from the compiler that we can do it safely. It's orthogonal to fixing
the correctness bug with emplacing an existing element of the vector.
We can fix the correctness bug now and worry about this optimisation
separately.

Improve insert/emplace robustness to self insertion

[François Dumont]

Hi

Following below discussion here is a patch to make sure we 
correctly deal with insertion of instances stored into the vector itself.


When we don't need reallocation I have implemented the libc++ trick 
to avoid an intermediate copy. I did my best to detect when a value_type 
instance is being inserted, whatever how it is inserted, lvalue/rvalue 
or xvalue reference. I was thinking that taking address of an rvalue 
would fail but it didn't. I also reuse _M_data_ptr method even if when 
vector is empty it doesn't work but vector is not empty when used so it 
should be fine. In the _M_insert_aux taking variadic number of 
parameters I always create a copy cause we can't know if one of those 
parameter has a link to vector values.


We could also implement libc++ trick in _M_fill_insert but not sure 
it worth it, what do you think ?


All vector tests run so far.

François

On 20/06/2016 09:42, Jonathan Wakely wrote:

On 19/06/16 10:21 +0200, François Dumont wrote:

On 16/06/2016 22:21, Jonathan Wakely wrote:

On 16/06/16 21:27 +0200, François Dumont wrote:
Very nice improvement. Could also benefit to other containers, 
especially std::deque. Do you plan to take care of it ?


Good point - I'd only looked at it for std::vector, because that's
what Howard's experiment tested. I haven't looked at the other
containers at all, and wasn't planning to do so. If you have time to
look at them that would be great, otherwise I'll add it to my TODO
list for something to look at later.


I started considering it and so came to the question of 
insert/emplace of the container self values. Is the following program 
ill-formed ?


int main()
{
 std::vector vv =
   {
 { 2, 3 },
 { 4, 5 },
 { 0, 1 }
   };

 vv.reserve(4);
 vv.emplace(vv.begin(), vv[0]);

 assert( vv[0].size() == 2 );
}

The assert fails because we end-up assigning a moved vector instance 
to vv first entry. This is not a regression of this patch, we were 
already not creating any copy before moving all vector values. If 
this program is ill-formed why does libc++ consider this kind of 
situation in its insert implementation ?


I think this should work correctly, for both insert and emplace.

Note that it gave me the idear of adding a DEBUG check detecting when 
a moved instance is being used. A moved instance shall only be 
destroyed or assigned, no ?


That's not true in general, but is true for these members of vector.





diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index eaafa22..d7435cc 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -949,7 +949,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __cplusplus >= 201103L
 	  _M_emplace_back_aux(__x);
 #else
-	  _M_insert_aux(end(), __x);
+	  _M_realloc_insert_aux(end(), __x);
 #endif
   }
 
@@ -1432,23 +1432,37 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #endif
 
   // Called by insert(p,x)
+  void
+  _M_insert_aux(iterator __position, const value_type& __x)
+  { _M_insert_value_aux(__position, __x); }
+
 #if __cplusplus < 201103L
   void
-  _M_insert_aux(iterator __position, const value_type& __x);
-#else
-  template
-	static void
-	_S_insert_aux_assign(iterator __pos, _Args&&... __args)
-	{ *__pos =  _Tp(std::forward<_Args>(__args)...); }
+  _M_insert_value_aux(iterator __position, const value_type& __x);
 
-  static void
-  _S_insert_aux_assign(iterator __pos, _Tp&& __arg)
-  { *__pos = std::move(__arg); }
+  void
+  _M_realloc_insert_aux(iterator __position, const value_type& __x);
+#else
+  template
+void
+_M_insert_value_aux(iterator __position, _Val&& __x);
 
   template
 	void
 	_M_insert_aux(iterator __position, _Args&&... __args);
 
+  void
+  _M_insert_aux(iterator __position, value_type& __x)
+  { _M_insert_value_aux(__position, __x); }
+
+  void
+  _M_insert_aux(iterator __position, value_type&& __x)
+  { _M_insert_value_aux(__position, std::move(__x)); }
+
+  template
+void
+_M_realloc_insert_aux(iterator __position, _Args&&... __args);
+
   template
 	void
 	_M_emplace_back_aux(_Args&&... __args);
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 604be7b..dab578e 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -112,27 +112,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #endif
 {
   const size_type __n = __position - begin();
-  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
-	  && __position == end())
-	{
-	  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
-	  ++this->_M_impl._M_finish;
-	}
+  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+	if (__position == end())
+	  {
+	_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
+