minor optimization bug in basic_string move assignment

minor optimization bug in basic_string move assignment

[waffl3x]

[-- Attachment #1: Type: text/plain, Size: 1051 bytes --]

Example: https://godbolt.org/z/sKhGqG1qK
https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=libstdc%2B%2B-v3/include/bits/basic_string.h;hb=HEAD#l880
When move assigning to a basic_string, the allocated memory of the moved into string is stored into the source string instead of deallocating it, a good optimization when everything is compatible. However in the case of a stateful allocator (is_always_true() evaluating as false) this optimization is never taken. Unless there is some reason I can't think of that makes equal stateful allocators incompatible here, I believe the if statement on line 880 of basic_string.h should also compare the equality of each strings allocator. The first condition in the function seems to indicate to me that this scenario was being considered and just forgotten about, as the memory doesn't get deallocated immediately if the two allocators are equal. I'll note that because of how everything is handled, this doesn't result in a leak so this bug is still only a minor missed optimization.

mailto:libstdc++@gcc.gnu.org

Re: minor optimization bug in basic_string move assignment

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 1592 bytes --]

On 04/01/23 00:11, waffl3x via Libstdc++ wrote:
> Example: https://godbolt.org/z/sKhGqG1qK
> https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=libstdc%2B%2B-v3/include/bits/basic_string.h;hb=HEAD#l880
> When move assigning to a basic_string, the allocated memory of the moved into string is stored into the source string instead of deallocating it, a good optimization when everything is compatible. However in the case of a stateful allocator (is_always_true() evaluating as false) this optimization is never taken. Unless there is some reason I can't think of that makes equal stateful allocators incompatible here, I believe the if statement on line 880 of basic_string.h should also compare the equality of each strings allocator. The first condition in the function seems to indicate to me that this scenario was being considered and just forgotten about, as the memory doesn't get deallocated immediately if the two allocators are equal. I'll note that because of how everything is handled, this doesn't result in a leak so this bug is still only a minor missed optimization.
>
> mailto:libstdc++@gcc.gnu.org

Hmmm, I don't know, at least it is not as simple as you present it.

You cannot add a check on allocator equality as you are proposing 
because it is too late. __str allocator might have already been 
propagated to *this on the previous call to std::__alloc_on_move. Note 
that current check is done only if 
!_Alloc_traits::_S_propagate_on_move_assign().

This patch might do the job but I wonder if equal allocators can become 
un-equal after the propagate-on-move-assignment ?



[-- Attachment #2: basic_string.h.patch --]
[-- Type: text/x-patch, Size: 1450 bytes --]

diff --git a/libstdc++-v3/include/bits/basic_string.h b/libstdc++-v3/include/bits/basic_string.h
index 109915653af..2627631e102 100644
--- a/libstdc++-v3/include/bits/basic_string.h
+++ b/libstdc++-v3/include/bits/basic_string.h
@@ -844,9 +844,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       operator=(basic_string&& __str)
       noexcept(_Alloc_traits::_S_nothrow_move())
       {
+	const bool __equal_allocs = _Alloc_traits::_S_always_equal()
+	    || _M_get_allocator() == __str._M_get_allocator()
 	if (!_M_is_local() && _Alloc_traits::_S_propagate_on_move_assign()
-	    && !_Alloc_traits::_S_always_equal()
-	    && _M_get_allocator() != __str._M_get_allocator())
+	    && !__equal_allocs)
 	  {
 	    // Destroy existing storage before replacing allocator.
 	    _M_destroy(_M_allocated_capacity);
@@ -868,16 +869,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
 		_M_set_length(__str.size());
 	      }
 	  }
-	else if (_Alloc_traits::_S_propagate_on_move_assign()
-	    || _Alloc_traits::_S_always_equal()
-	    || _M_get_allocator() == __str._M_get_allocator())
+	else if (_Alloc_traits::_S_propagate_on_move_assign() || __equal_allocs)
 	  {
 	    // Just move the allocated pointer, our allocator can free it.
 	    pointer __data = nullptr;
 	    size_type __capacity;
 	    if (!_M_is_local())
 	      {
-		if (_Alloc_traits::_S_always_equal())
+		if (__equal_allocs)
 		  {
 		    // __str can reuse our existing storage.
 		    __data = _M_data();

Re: minor optimization bug in basic_string move assignment

[Jonathan Wakely]

On Wed, 4 Jan 2023 at 18:21, François Dumont via Libstdc++
<libstdc++@gcc.gnu.org> wrote:
>
> On 04/01/23 00:11, waffl3x via Libstdc++ wrote:
> > Example: https://godbolt.org/z/sKhGqG1qK
> > https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=libstdc%2B%2B-v3/include/bits/basic_string.h;hb=HEAD#l880
> > When move assigning to a basic_string, the allocated memory of the moved into string is stored into the source string instead of deallocating it, a good optimization when everything is compatible. However in the case of a stateful allocator (is_always_true() evaluating as false) this optimization is never taken. Unless there is some reason I can't think of that makes equal stateful allocators incompatible here, I believe the if statement on line 880 of basic_string.h should also compare the equality of each strings allocator. The first condition in the function seems to indicate to me that this scenario was being considered and just forgotten about, as the memory doesn't get deallocated immediately if the two allocators are equal. I'll note that because of how everything is handled, this doesn't result in a leak so this bug is still only a minor missed optimization.
> >
> > mailto:libstdc++@gcc.gnu.org
>
> Hmmm, I don't know, at least it is not as simple as you present it.
>
> You cannot add a check on allocator equality as you are proposing
> because it is too late. __str allocator might have already been
> propagated to *this on the previous call to std::__alloc_on_move. Note
> that current check is done only if
> !_Alloc_traits::_S_propagate_on_move_assign().
>
> This patch might do the job but I wonder if equal allocators can become
> un-equal after the propagate-on-move-assignment ?

Since https://cplusplus.github.io/LWG/issue2593 they can't. But I
think when I wrote that code, they could do, which is probably why the
optimization wasn't done.

[PATCH] minor optimization bug in basic_string move assignment

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 3117 bytes --]

Let's submit a proper patch proposal then.

The occasion for me to ask if there is any reason for cow string not 
being C++11 allocator compliant ? Just lack of interest ?

I wanted to consider it to get rid of the __gnu_debug::_Safe_container 
_IsCxx11AllocatorAware template parameter.

     libstdc++: Optimize basic_string move assignment

     Since resolution of Issue 2593 [1] we can consider that equal 
allocators
     before the propagate-on-move-assignment operations will still be equal
     afterward.

     So we can extend the optimization of transfering the storage of the 
move-to
     instance to the move-from one that is currently limited to always equal
     allocators.

     [1] https://cplusplus.github.io/LWG/issue2593

     libstdc++-v3/ChangeLog:

             * include/bits/basic_string.h (operator=(basic_string&&)): 
Transfer move-to
             storage to the move-from instance when allocators are equal.
             * 
testsuite/21_strings/basic_string/allocator/char/move_assign.cc (test04):
             New test case.

Tested under linux x86_64, ok to commit ?

François


On 17/01/23 20:18, Jonathan Wakely wrote:
> On Wed, 4 Jan 2023 at 18:21, François Dumont via Libstdc++
> <libstdc++@gcc.gnu.org> wrote:
>> On 04/01/23 00:11, waffl3x via Libstdc++ wrote:
>>> Example: https://godbolt.org/z/sKhGqG1qK
>>> https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=libstdc%2B%2B-v3/include/bits/basic_string.h;hb=HEAD#l880
>>> When move assigning to a basic_string, the allocated memory of the moved into string is stored into the source string instead of deallocating it, a good optimization when everything is compatible. However in the case of a stateful allocator (is_always_true() evaluating as false) this optimization is never taken. Unless there is some reason I can't think of that makes equal stateful allocators incompatible here, I believe the if statement on line 880 of basic_string.h should also compare the equality of each strings allocator. The first condition in the function seems to indicate to me that this scenario was being considered and just forgotten about, as the memory doesn't get deallocated immediately if the two allocators are equal. I'll note that because of how everything is handled, this doesn't result in a leak so this bug is still only a minor missed optimization.
>>>
>>> mailto:libstdc++@gcc.gnu.org
>> Hmmm, I don't know, at least it is not as simple as you present it.
>>
>> You cannot add a check on allocator equality as you are proposing
>> because it is too late. __str allocator might have already been
>> propagated to *this on the previous call to std::__alloc_on_move. Note
>> that current check is done only if
>> !_Alloc_traits::_S_propagate_on_move_assign().
>>
>> This patch might do the job but I wonder if equal allocators can become
>> un-equal after the propagate-on-move-assignment ?
> Since https://cplusplus.github.io/LWG/issue2593 they can't. But I
> think when I wrote that code, they could do, which is probably why the
> optimization wasn't done.
>

[-- Attachment #2: string_move_assign_optim.patch --]
[-- Type: text/x-patch, Size: 3917 bytes --]

diff --git a/libstdc++-v3/include/bits/basic_string.h b/libstdc++-v3/include/bits/basic_string.h
index aa018262c98..c81dc0d425a 100644
--- a/libstdc++-v3/include/bits/basic_string.h
+++ b/libstdc++-v3/include/bits/basic_string.h
@@ -844,9 +844,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       operator=(basic_string&& __str)
       noexcept(_Alloc_traits::_S_nothrow_move())
       {
+	const bool __equal_allocs = _Alloc_traits::_S_always_equal()
+	  || _M_get_allocator() == __str._M_get_allocator();
 	if (!_M_is_local() && _Alloc_traits::_S_propagate_on_move_assign()
-	    && !_Alloc_traits::_S_always_equal()
-	    && _M_get_allocator() != __str._M_get_allocator())
+	    && !__equal_allocs)
 	  {
 	    // Destroy existing storage before replacing allocator.
 	    _M_destroy(_M_allocated_capacity);
@@ -868,16 +869,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
 		_M_set_length(__str.size());
 	      }
 	  }
-	else if (_Alloc_traits::_S_propagate_on_move_assign()
-	    || _Alloc_traits::_S_always_equal()
-	    || _M_get_allocator() == __str._M_get_allocator())
+	else if (_Alloc_traits::_S_propagate_on_move_assign() || __equal_allocs)
 	  {
 	    // Just move the allocated pointer, our allocator can free it.
 	    pointer __data = nullptr;
 	    size_type __capacity;
 	    if (!_M_is_local())
 	      {
-		if (_Alloc_traits::_S_always_equal())
+		if (__equal_allocs)
 		  {
 		    // __str can reuse our existing storage.
 		    __data = _M_data();
diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/allocator/char/move_assign.cc b/libstdc++-v3/testsuite/21_strings/basic_string/allocator/char/move_assign.cc
index cc58348e116..21e0b1cb4f4 100644
--- a/libstdc++-v3/testsuite/21_strings/basic_string/allocator/char/move_assign.cc
+++ b/libstdc++-v3/testsuite/21_strings/basic_string/allocator/char/move_assign.cc
@@ -28,6 +28,8 @@ const C c = 'a';
 using traits = std::char_traits<C>;
 
 using __gnu_test::propagating_allocator;
+using __gnu_test::tracker_allocator_counter;
+using __gnu_test::tracker_allocator;
 
 void test01()
 {
@@ -146,10 +148,60 @@ void test03()
   VERIFY(7 == v8.get_allocator().get_personality());
 }
 
+void test04()
+{
+  typedef propagating_allocator<C, true, tracker_allocator<C>> alloc_type;
+  typedef std::basic_string<C, traits, alloc_type> test_type;
+
+  {
+    tracker_allocator_counter::reset();
+    test_type v1(alloc_type(1));
+    v1 = "abcdefghijklmnopqr10";
+    auto ref_alloc_count = tracker_allocator_counter::get_allocation_count();
+
+    test_type v2(alloc_type(2));
+    v2 = "abcdefghijklmnopqr20";
+    v2 = std::move(v1);
+    VERIFY(1 == v1.get_allocator().get_personality());
+    VERIFY(1 == v2.get_allocator().get_personality());
+
+    VERIFY( tracker_allocator_counter::get_allocation_count() == 2 * ref_alloc_count );
+    VERIFY( tracker_allocator_counter::get_deallocation_count() == ref_alloc_count );
+
+    v1 = "abcdefghijklmnopqr11";
+
+    VERIFY( tracker_allocator_counter::get_allocation_count() == 3 * ref_alloc_count );
+  }
+
+  {
+    tracker_allocator_counter::reset();
+    test_type v1(alloc_type(1));
+    v1 = "abcdefghijklmnopqr10";
+    auto ref_alloc_count = tracker_allocator_counter::get_allocation_count();
+
+    test_type v2(alloc_type(1));
+    v2 = "abcdefghijklmnopqr20";
+    v2 = std::move(v1);
+    VERIFY(1 == v1.get_allocator().get_personality());
+    VERIFY(1 == v2.get_allocator().get_personality());
+
+    VERIFY( tracker_allocator_counter::get_allocation_count() == 2 * ref_alloc_count );
+    VERIFY( tracker_allocator_counter::get_deallocation_count() == 0 );
+
+    v1 = "abcdefghijklmnopqr11";
+
+    VERIFY( tracker_allocator_counter::get_allocation_count() == 2 * ref_alloc_count );
+  }
+
+  VERIFY( tracker_allocator_counter::get_allocation_count() ==
+	  tracker_allocator_counter::get_deallocation_count() );
+}
+
 int main()
 {
   test01();
   test02();
   test03();
+  test04();
   return 0;
 }

Re: [PATCH] minor optimization bug in basic_string move assignment

[Jonathan Wakely]

On Wed, 25 Jan 2023 at 18:38, François Dumont <frs.dumont@gmail.com> wrote:
>
> Let's submit a proper patch proposal then.
>
> The occasion for me to ask if there is any reason for cow string not
> being C++11 allocator compliant ? Just lack of interest ?

Mostly lack of interest, but also I don't really want to "encourage"
the use of the old string by investing lots of maintenance effort into
it. If you want new features like C++11 Allocators and
resize_and_overwrite etc then you should use the new type.

I don't remember if there were any actual blockers that made it
difficult to support stateful allocators in the COW string. I might
have written something about it in mails to the list when I was adding
the SSO string, but I don't remember now.

Anyway, for this patch ...

>
> I wanted to consider it to get rid of the __gnu_debug::_Safe_container
> _IsCxx11AllocatorAware template parameter.
>
>      libstdc++: Optimize basic_string move assignment
>
>      Since resolution of Issue 2593 [1] we can consider that equal
> allocators
>      before the propagate-on-move-assignment operations will still be equal
>      afterward.
>
>      So we can extend the optimization of transfering the storage of the
> move-to
>      instance to the move-from one that is currently limited to always equal
>      allocators.
>
>      [1] https://cplusplus.github.io/LWG/issue2593
>
>      libstdc++-v3/ChangeLog:
>
>              * include/bits/basic_string.h (operator=(basic_string&&)):
> Transfer move-to
>              storage to the move-from instance when allocators are equal.
>              *
> testsuite/21_strings/basic_string/allocator/char/move_assign.cc (test04):
>              New test case.
>
> Tested under linux x86_64, ok to commit ?

OK for trunk, thanks!

+Reviewed-by: Jonathan Wakely <jwakely@redhat.com>


> > On Wed, 4 Jan 2023 at 18:21, François Dumont via Libstdc++
> > <libstdc++@gcc.gnu.org> wrote:
> >> On 04/01/23 00:11, waffl3x via Libstdc++ wrote:
> >>> Example: https://godbolt.org/z/sKhGqG1qK
> >>> https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=libstdc%2B%2B-v3/include/bits/basic_string.h;hb=HEAD#l880
> >>> When move assigning to a basic_string, the allocated memory of the moved into string is stored into the source string instead of deallocating it, a good optimization when everything is compatible. However in the case of a stateful allocator (is_always_true() evaluating as false) this optimization is never taken. Unless there is some reason I can't think of that makes equal stateful allocators incompatible here, I believe the if statement on line 880 of basic_string.h should also compare the equality of each strings allocator. The first condition in the function seems to indicate to me that this scenario was being considered and just forgotten about, as the memory doesn't get deallocated immediately if the two allocators are equal. I'll note that because of how everything is handled, this doesn't result in a leak so this bug is still only a minor missed optimization.
> >>>
> >>> mailto:libstdc++@gcc.gnu.org
> >> Hmmm, I don't know, at least it is not as simple as you present it.
> >>
> >> You cannot add a check on allocator equality as you are proposing
> >> because it is too late. __str allocator might have already been
> >> propagated to *this on the previous call to std::__alloc_on_move. Note
> >> that current check is done only if
> >> !_Alloc_traits::_S_propagate_on_move_assign().
> >>
> >> This patch might do the job but I wonder if equal allocators can become
> >> un-equal after the propagate-on-move-assignment ?
> > Since https://cplusplus.github.io/LWG/issue2593 they can't. But I
> > think when I wrote that code, they could do, which is probably why the
> > optimization wasn't done.
> >

Re: [PATCH] minor optimization bug in basic_string move assignment

[François Dumont]

On 03/02/23 15:50, Jonathan Wakely wrote:
> On Wed, 25 Jan 2023 at 18:38, François Dumont <frs.dumont@gmail.com> wrote:
>> Let's submit a proper patch proposal then.
>>
>> The occasion for me to ask if there is any reason for cow string not
>> being C++11 allocator compliant ? Just lack of interest ?
> Mostly lack of interest, but also I don't really want to "encourage"
> the use of the old string by investing lots of maintenance effort into
> it. If you want new features like C++11 Allocators and
> resize_and_overwrite etc then you should use the new type.
>
> I don't remember if there were any actual blockers that made it
> difficult to support stateful allocators in the COW string. I might
> have written something about it in mails to the list when I was adding
> the SSO string, but I don't remember now.

Ok, thanks for feedback. I won't bother then.

>
> Anyway, for this patch ...
>
>> I wanted to consider it to get rid of the __gnu_debug::_Safe_container
>> _IsCxx11AllocatorAware template parameter.
>>
>>       libstdc++: Optimize basic_string move assignment
>>
>>       Since resolution of Issue 2593 [1] we can consider that equal
>> allocators
>>       before the propagate-on-move-assignment operations will still be equal
>>       afterward.
>>
>>       So we can extend the optimization of transfering the storage of the
>> move-to
>>       instance to the move-from one that is currently limited to always equal
>>       allocators.
>>
>>       [1] https://cplusplus.github.io/LWG/issue2593
>>
>>       libstdc++-v3/ChangeLog:
>>
>>               * include/bits/basic_string.h (operator=(basic_string&&)):
>> Transfer move-to
>>               storage to the move-from instance when allocators are equal.
>>               *
>> testsuite/21_strings/basic_string/allocator/char/move_assign.cc (test04):
>>               New test case.
>>
>> Tested under linux x86_64, ok to commit ?
> OK for trunk, thanks!
>
> +Reviewed-by: Jonathan Wakely <jwakely@redhat.com>

Should I have added this to the commit ?

If so sorry, I haven't.

Re: [PATCH] minor optimization bug in basic_string move assignment

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 2721 bytes --]

On Sat, 4 Feb 2023, 13:12 François Dumont via Libstdc++, <
libstdc++@gcc.gnu.org> wrote:

> On 03/02/23 15:50, Jonathan Wakely wrote:
> > On Wed, 25 Jan 2023 at 18:38, François Dumont <frs.dumont@gmail.com>
> wrote:
> >> Let's submit a proper patch proposal then.
> >>
> >> The occasion for me to ask if there is any reason for cow string not
> >> being C++11 allocator compliant ? Just lack of interest ?
> > Mostly lack of interest, but also I don't really want to "encourage"
> > the use of the old string by investing lots of maintenance effort into
> > it. If you want new features like C++11 Allocators and
> > resize_and_overwrite etc then you should use the new type.
> >
> > I don't remember if there were any actual blockers that made it
> > difficult to support stateful allocators in the COW string. I might
> > have written something about it in mails to the list when I was adding
> > the SSO string, but I don't remember now.
>
> Ok, thanks for feedback. I won't bother then.
>
> >
> > Anyway, for this patch ...
> >
> >> I wanted to consider it to get rid of the __gnu_debug::_Safe_container
> >> _IsCxx11AllocatorAware template parameter.
> >>
> >>       libstdc++: Optimize basic_string move assignment
> >>
> >>       Since resolution of Issue 2593 [1] we can consider that equal
> >> allocators
> >>       before the propagate-on-move-assignment operations will still be
> equal
> >>       afterward.
> >>
> >>       So we can extend the optimization of transfering the storage of
> the
> >> move-to
> >>       instance to the move-from one that is currently limited to always
> equal
> >>       allocators.
> >>
> >>       [1] https://cplusplus.github.io/LWG/issue2593
> >>
> >>       libstdc++-v3/ChangeLog:
> >>
> >>               * include/bits/basic_string.h (operator=(basic_string&&)):
> >> Transfer move-to
> >>               storage to the move-from instance when allocators are
> equal.
> >>               *
> >> testsuite/21_strings/basic_string/allocator/char/move_assign.cc
> (test04):
> >>               New test case.
> >>
> >> Tested under linux x86_64, ok to commit ?
> > OK for trunk, thanks!
> >
> > +Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
>
> Should I have added this to the commit ?
>
> If so sorry, I haven't.
>


No problem!

I think it would be a good habit for us to all start doing that (copying
the glibc project), to thank people who take the time to do a review. I
don't really mind if my name gets recorded as reviewer, but I'm going to
try to remember to add Reviewed-by: when I review something. And that might
encourage others to do the same, and to do more reviewing :-)



>