[PATCH] Improve string::clear() performance

[PATCH] Improve string::clear() performance

[Cong Wang]

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

In !_GLIBCXX_USE_CXX11_ABI implementation, string::clear() calls
_M_mutate(), which could allocate memory as we do COW. This hurts
performance when string::clear() is on the hot path.

This patch improves it by using _S_empty_rep directly when
_GLIBCXX_FULLY_DYNAMIC_STRING is not enabled. And Linux distro like
Fedora doesn't enable this, this is why we caught it.

The copy-and-clear test shows it improves by 50%.

Ran all testsuites on Linux-x64.

2016-09-13  Cong Wang  <xiyou.wangcong@gmail.com>

    PR libstdc++/77582
    * libstdc++-v3/include/bits/basic_string.h: Change inline to a declaration.
    * libstdc++-v3/include/bits/basic_string.tcc: Inline the
implementation based on _M_mutate, and use _S_empty_rep when possible.
    * libstdc++-v3/testsuite/performance/21_strings/copy_and_clear.cc: New.

[-- Attachment #2: gcc.diff --]
[-- Type: text/plain, Size: 3171 bytes --]

diff --git a/libstdc++-v3/include/bits/basic_string.h b/libstdc++-v3/include/bits/basic_string.h
index e823f13..94d1df2 100644
--- a/libstdc++-v3/include/bits/basic_string.h
+++ b/libstdc++-v3/include/bits/basic_string.h
@@ -3686,8 +3686,7 @@ _GLIBCXX_END_NAMESPACE_CXX11
        */
       // PR 56166: this should not throw.
       void
-      clear()
-      { _M_mutate(0, this->size(), 0); }
+      clear();
 
       /**
        *  Returns true if the %string is empty.  Equivalent to 
diff --git a/libstdc++-v3/include/bits/basic_string.tcc b/libstdc++-v3/include/bits/basic_string.tcc
index 0080d2b..935932e 100644
--- a/libstdc++-v3/include/bits/basic_string.tcc
+++ b/libstdc++-v3/include/bits/basic_string.tcc
@@ -966,6 +966,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   template<typename _CharT, typename _Traits, typename _Alloc>
     void
     basic_string<_CharT, _Traits, _Alloc>::
+    clear()
+    {
+      if (_M_rep()->_M_is_shared())
+        {
+          const allocator_type __a = get_allocator();
+          _Rep* __r;
+
+#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
+	  __r = &_S_empty_rep();
+#else
+	  // Must reallocate.
+	  __r = _Rep::_S_create(0, this->capacity(), __a);
+#endif
+	  _M_rep()->_M_dispose(__a);
+	  _M_data(__r->_M_refdata());
+        }
+      _M_rep()->_M_set_length_and_sharable(0);
+    }
+
+  template<typename _CharT, typename _Traits, typename _Alloc>
+    void
+    basic_string<_CharT, _Traits, _Alloc>::
     swap(basic_string& __s)
     {
       if (_M_rep()->_M_is_leaked())
diff --git a/libstdc++-v3/testsuite/performance/21_strings/copy_and_clear.cc b/libstdc++-v3/testsuite/performance/21_strings/copy_and_clear.cc
new file mode 100644
index 0000000..708f053
--- /dev/null
+++ b/libstdc++-v3/testsuite/performance/21_strings/copy_and_clear.cc
@@ -0,0 +1,49 @@
+// Copyright (C) 2006-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
+// <http://www.gnu.org/licenses/>.
+
+
+#include <string>
+#include <testsuite_performance.h>
+
+void benchmark(long len)
+{
+  using namespace std;
+  using namespace __gnu_test;
+
+  time_counter time;
+  resource_counter resource;
+
+  start_counters(time, resource);
+  for (long i = 0; i < len; ++i)
+    {
+      string ss1("1");
+      string ss2(ss1);
+      ss1.clear();
+    }
+  stop_counters(time, resource);
+
+  report_performance(__FILE__, "", time, resource);
+  clear_counters(time, resource);
+}
+
+int main()
+{
+  benchmark(1000000);
+  benchmark(10000000);
+  benchmark(100000000);
+  return 0;
+}

Re: [PATCH] Improve string::clear() performance

[Jonathan Wakely]

On 13/09/16 11:02 -0700, Cong Wang wrote:
>In !_GLIBCXX_USE_CXX11_ABI implementation, string::clear() calls
>_M_mutate(), which could allocate memory as we do COW. This hurts
>performance when string::clear() is on the hot path.
>
>This patch improves it by using _S_empty_rep directly when
>_GLIBCXX_FULLY_DYNAMIC_STRING is not enabled. And Linux distro like
>Fedora doesn't enable this, this is why we caught it.
>
>The copy-and-clear test shows it improves by 50%.
>
>Ran all testsuites on Linux-x64.

Thank you for the patch (and changelog and test results!).

Do you have a GCC copyright assignment in place? See
https://gcc.gnu.org/contribute.html#legal for details.

If I understand the purpose of the change correctly, it's similar to
https://gcc.gnu.org/ml/gcc-patches/2014-06/msg00278.html - is that
right?

Re: [PATCH] Improve string::clear() performance

[Cong Wang]

On Wed, Sep 14, 2016 at 4:06 AM, Jonathan Wakely <jwakely@redhat.com> wrote:
> On 13/09/16 11:02 -0700, Cong Wang wrote:
>>
>> In !_GLIBCXX_USE_CXX11_ABI implementation, string::clear() calls
>> _M_mutate(), which could allocate memory as we do COW. This hurts
>> performance when string::clear() is on the hot path.
>>
>> This patch improves it by using _S_empty_rep directly when
>> _GLIBCXX_FULLY_DYNAMIC_STRING is not enabled. And Linux distro like
>> Fedora doesn't enable this, this is why we caught it.
>>
>> The copy-and-clear test shows it improves by 50%.
>>
>> Ran all testsuites on Linux-x64.
>
>
> Thank you for the patch (and changelog and test results!).
>
> Do you have a GCC copyright assignment in place? See
> https://gcc.gnu.org/contribute.html#legal for details.

Oh, didn't notice this, I thought gcc has something as quick
as the 'Signed-off-by' for Linux kernel (I am a Linux kernel developer).
I will do it.

>
> If I understand the purpose of the change correctly, it's similar to
> https://gcc.gnu.org/ml/gcc-patches/2014-06/msg00278.html - is that
> right?
>

Oh, yes, I didn't know your patch because I don't subscribe
gcc mailing list. I am wondering why your patch is not merged
after 2+ years?

Please let me know what you prefer: 1) You update your patch
and get it merged; 2) Use my patch if it looks good. I am fine with
either way. :)

Thanks.

Re: [PATCH] Improve string::clear() performance

[Jonathan Wakely]

On 14/09/16 09:09 -0700, Cong Wang wrote:
>On Wed, Sep 14, 2016 at 4:06 AM, Jonathan Wakely <jwakely@redhat.com> wrote:
>> On 13/09/16 11:02 -0700, Cong Wang wrote:
>>>
>>> In !_GLIBCXX_USE_CXX11_ABI implementation, string::clear() calls
>>> _M_mutate(), which could allocate memory as we do COW. This hurts
>>> performance when string::clear() is on the hot path.
>>>
>>> This patch improves it by using _S_empty_rep directly when
>>> _GLIBCXX_FULLY_DYNAMIC_STRING is not enabled. And Linux distro like
>>> Fedora doesn't enable this, this is why we caught it.
>>>
>>> The copy-and-clear test shows it improves by 50%.
>>>
>>> Ran all testsuites on Linux-x64.
>>
>>
>> Thank you for the patch (and changelog and test results!).
>>
>> Do you have a GCC copyright assignment in place? See
>> https://gcc.gnu.org/contribute.html#legal for details.
>
>Oh, didn't notice this, I thought gcc has something as quick
>as the 'Signed-off-by' for Linux kernel (I am a Linux kernel developer).
>I will do it.
>
>>
>> If I understand the purpose of the change correctly, it's similar to
>> https://gcc.gnu.org/ml/gcc-patches/2014-06/msg00278.html - is that
>> right?
>>
>
>Oh, yes, I didn't know your patch because I don't subscribe
>gcc mailing list. I am wondering why your patch is not merged
>after 2+ years?

As I said in the patch email, I'm not sure if it's conforming, due to
clearing the string's cpacity() as well as its size().

>Please let me know what you prefer: 1) You update your patch
>and get it merged; 2) Use my patch if it looks good. I am fine with
>either way. :)

I'll refresh my memory of the various issues and reconsider applying
my patch (that way we don't need to wait for your copyright
assignment). The performance benefits you measured make it more
compelling.

Re: [PATCH] Improve string::clear() performance

[Cong Wang]

On Wed, Sep 14, 2016 at 10:28 AM, Jonathan Wakely <jwakely@redhat.com> wrote:
> On 14/09/16 09:09 -0700, Cong Wang wrote:
>>
>> On Wed, Sep 14, 2016 at 4:06 AM, Jonathan Wakely <jwakely@redhat.com>
>> wrote:
>>>
>>> If I understand the purpose of the change correctly, it's similar to
>>> https://gcc.gnu.org/ml/gcc-patches/2014-06/msg00278.html - is that
>>> right?
>>>
>>
>> Oh, yes, I didn't know your patch because I don't subscribe
>> gcc mailing list. I am wondering why your patch is not merged
>> after 2+ years?
>
>
> As I said in the patch email, I'm not sure if it's conforming, due to
> clearing the string's cpacity() as well as its size().
>

OK. My patch keeps the original logic except the case for
_GLIBCXX_FULLY_DYNAMIC_STRING, should be at least
as correct as the current code. ;)


>> Please let me know what you prefer: 1) You update your patch
>> and get it merged; 2) Use my patch if it looks good. I am fine with
>> either way. :)
>
>
> I'll refresh my memory of the various issues and reconsider applying
> my patch (that way we don't need to wait for your copyright
> assignment). The performance benefits you measured make it more
> compelling.

Sure.

For long term, I think gcc should have something as simple as
'Signed-off-by' for Linux kernel, otherwise too much work for first-time
contributors like me. We all want to save time on this, don't we? ;)

Thanks.

Re: [PATCH] Improve string::clear() performance

[Jonathan Wakely]

On 14/09/16 10:41 -0700, Cong Wang wrote:
>For long term, I think gcc should have something as simple as
>'Signed-off-by' for Linux kernel, otherwise too much work for first-time
>contributors like me. We all want to save time on this, don't we? ;)

Signed-off-by wouldn't help. The copyright assignment is done so that
the FSF owns the copyright in the majority of the GCC code. If I add
a Signed-off-by to your patch that doesn't have any effect on your
copyright of the code.

It certainly does add a hurdle for contributors to GCC, but it's not a
policy that is likely to change.

Anyway, I'll fix this one way or another ASAP. Thanks again.

Re: [PATCH] Improve string::clear() performance

[Cong Wang]

On Thu, Sep 15, 2016 at 2:08 AM, Jonathan Wakely <jwakely@redhat.com> wrote:
> On 14/09/16 10:41 -0700, Cong Wang wrote:
>>
>> For long term, I think gcc should have something as simple as
>> 'Signed-off-by' for Linux kernel, otherwise too much work for first-time
>> contributors like me. We all want to save time on this, don't we? ;)
>
>
> Signed-off-by wouldn't help. The copyright assignment is done so that
> the FSF owns the copyright in the majority of the GCC code. If I add
> a Signed-off-by to your patch that doesn't have any effect on your
> copyright of the code.
>
> It certainly does add a hurdle for contributors to GCC, but it's not a
> policy that is likely to change.
>
> Anyway, I'll fix this one way or another ASAP. Thanks again.

Thanks for your kind explanation.

I think I already finish the copyright thing after exchanging emails with
assign@gnu.org. So copyright is not a blocker for consideration of
my patch any more.

Re: [PATCH] Improve string::clear() performance

[Jonathan Wakely]

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

On 14/09/16 18:28 +0100, Jonathan Wakely wrote:
>On 14/09/16 09:09 -0700, Cong Wang wrote:
>>On Wed, Sep 14, 2016 at 4:06 AM, Jonathan Wakely <jwakely@redhat.com> wrote:
>>>On 13/09/16 11:02 -0700, Cong Wang wrote:
>>>>
>>>>In !_GLIBCXX_USE_CXX11_ABI implementation, string::clear() calls
>>>>_M_mutate(), which could allocate memory as we do COW. This hurts
>>>>performance when string::clear() is on the hot path.
>>>>
>>>>This patch improves it by using _S_empty_rep directly when
>>>>_GLIBCXX_FULLY_DYNAMIC_STRING is not enabled. And Linux distro like
>>>>Fedora doesn't enable this, this is why we caught it.
>>>>
>>>>The copy-and-clear test shows it improves by 50%.
>>>>
>>>>Ran all testsuites on Linux-x64.
>>>
>>>
>>>Thank you for the patch (and changelog and test results!).
>>>
>>>Do you have a GCC copyright assignment in place? See
>>>https://gcc.gnu.org/contribute.html#legal for details.
>>
>>Oh, didn't notice this, I thought gcc has something as quick
>>as the 'Signed-off-by' for Linux kernel (I am a Linux kernel developer).
>>I will do it.
>>
>>>
>>>If I understand the purpose of the change correctly, it's similar to
>>>https://gcc.gnu.org/ml/gcc-patches/2014-06/msg00278.html - is that
>>>right?
>>>
>>
>>Oh, yes, I didn't know your patch because I don't subscribe
>>gcc mailing list. I am wondering why your patch is not merged
>>after 2+ years?
>
>As I said in the patch email, I'm not sure if it's conforming, due to
>clearing the string's cpacity() as well as its size().
>
>>Please let me know what you prefer: 1) You update your patch
>>and get it merged; 2) Use my patch if it looks good. I am fine with
>>either way. :)
>
>I'll refresh my memory of the various issues and reconsider applying
>my patch (that way we don't need to wait for your copyright
>assignment). The performance benefits you measured make it more
>compelling.

I'm applying this patch, which is my one from 2014 with a check for
whether the string is shared, so we just set the length to zero (and
don't throw away reusable capacity) when it's not shared.

Tested x86_64-linux, committed to trunk.



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

commit b9546ed53b169ffb809371231342eeb63595d8bc
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Fri Sep 23 18:01:25 2016 +0100

    Avoid reallocation for basic_string::clear()
    
    	PR libstdc++/56166
    	PR libstdc++/77582
    	* include/bits/basic_string.h (basic_string::clear()): Drop reference
    	and use empty rep.
    	* include/ext/rc_string_base.h (__rc_string_base::_M_clear()):
    	Likewise.
    	* testsuite/21_strings/basic_string/56166.cc: New.
    	* testsuite/ext/vstring/modifiers/clear/56166.cc: New.

diff --git a/libstdc++-v3/include/bits/basic_string.h b/libstdc++-v3/include/bits/basic_string.h
index 2708cbc..7a4204e 100644
--- a/libstdc++-v3/include/bits/basic_string.h
+++ b/libstdc++-v3/include/bits/basic_string.h
@@ -3690,10 +3690,24 @@ _GLIBCXX_END_NAMESPACE_CXX11
       /**
        *  Erases the string, making it empty.
        */
+#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
+      void
+      clear() _GLIBCXX_NOEXCEPT
+      {
+	if (_M_rep()->_M_is_shared())
+	  {
+	    _M_rep()->_M_dispose(this->get_allocator());
+	    _M_data(_S_empty_rep()._M_refdata());
+	  }
+	else
+	  _M_rep()->_M_set_length_and_sharable(0);
+      }
+#else
       // PR 56166: this should not throw.
       void
       clear()
       { _M_mutate(0, this->size(), 0); }
+#endif
 
       /**
        *  Returns true if the %string is empty.  Equivalent to 
diff --git a/libstdc++-v3/include/ext/rc_string_base.h b/libstdc++-v3/include/ext/rc_string_base.h
index 1c1ed87..eab3461 100644
--- a/libstdc++-v3/include/ext/rc_string_base.h
+++ b/libstdc++-v3/include/ext/rc_string_base.h
@@ -354,7 +354,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       void
       _M_clear()
-      { _M_erase(size_type(0), _M_length()); }
+      {
+	_M_dispose();
+	_M_data(_S_empty_rep._M_refcopy());
+      }
 
       bool
       _M_compare(const __rc_string_base&) const
diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/56166.cc b/libstdc++-v3/testsuite/21_strings/basic_string/56166.cc
new file mode 100644
index 0000000..3d4d876
--- /dev/null
+++ b/libstdc++-v3/testsuite/21_strings/basic_string/56166.cc
@@ -0,0 +1,93 @@
+// 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
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run { target c++11 } }
+
+// libstdc++/56166
+
+#ifndef _GLIBCXX_USE_CXX11_ABI
+# define _GLIBCXX_USE_CXX11_ABI 0
+#endif
+#include <string>
+#include <new>
+
+static int fail_after = -1;
+
+template<typename T>
+  struct Allocator
+  {
+    using value_type = T;
+
+    // Need these typedefs because COW string doesn't use allocator_traits.
+    using pointer = T*;
+    using const_pointer = const T*;
+    using reference = T&;
+    using const_reference = const T&;
+    using difference_type = long;
+    using size_type = unsigned long;
+    template<typename U>
+      struct rebind {
+        using other = Allocator<U>;
+      };
+
+    Allocator() { }
+
+    template<typename U>
+      Allocator(const Allocator<U>&) { }
+
+    T* allocate(size_type n)
+    {
+      if (fail_after >= 0) {
+        if (fail_after-- == 0) {
+          throw std::bad_alloc();
+        }
+      }
+      return (T*)new char[n * sizeof(T)];
+    }
+
+    void deallocate(T* p, size_type)
+    {
+      delete[] (char*)p;
+    }
+  };
+
+template<typename T, typename U>
+  bool operator==(const Allocator<T>&, const Allocator<U>&) { return true; }
+template<typename T, typename U>
+  bool operator!=(const Allocator<T>&, const Allocator<U>&) { return false; }
+
+using string = std::basic_string<char, std::char_traits<char>, Allocator<char>>;
+
+string f()
+{
+  string s1("xxxxxx");
+  string s2 = s1;
+  s1.clear();
+  return s2;
+}
+
+int main()
+{
+  for (int i = 0; i < 10; i++) {
+    try {
+      fail_after = i;
+      f();
+      break;
+    } catch (std::bad_alloc) {
+    }
+  }
+}
diff --git a/libstdc++-v3/testsuite/ext/vstring/modifiers/clear/56166.cc b/libstdc++-v3/testsuite/ext/vstring/modifiers/clear/56166.cc
new file mode 100644
index 0000000..109e622
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/vstring/modifiers/clear/56166.cc
@@ -0,0 +1,96 @@
+// 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
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run { target c++11 } }
+
+// libstdc++/56166
+
+#ifndef _GLIBCXX_USE_CXX11_ABI
+# define _GLIBCXX_USE_CXX11_ABI 0
+#endif
+#include <ext/vstring.h>
+#include <new>
+
+static int fail_after = -1;
+
+template<typename T>
+  struct Allocator
+  {
+    using value_type = T;
+
+    // Need these typedefs because COW string doesn't use allocator_traits.
+    using pointer = T*;
+    using const_pointer = const T*;
+    using reference = T&;
+    using const_reference = const T&;
+    using difference_type = long;
+    using size_type = unsigned long;
+    template<typename U>
+      struct rebind {
+        using other = Allocator<U>;
+      };
+
+    Allocator() { }
+
+    template<typename U>
+      Allocator(const Allocator<U>&) { }
+
+    T* allocate(size_type n)
+    {
+      if (fail_after >= 0) {
+        if (fail_after-- == 0) {
+          throw std::bad_alloc();
+        }
+      }
+      return (T*)new char[n * sizeof(T)];
+    }
+
+    void deallocate(T* p, size_type)
+    {
+      delete[] (char*)p;
+    }
+  };
+
+template<typename T, typename U>
+  bool operator==(const Allocator<T>&, const Allocator<U>&) { return true; }
+template<typename T, typename U>
+  bool operator!=(const Allocator<T>&, const Allocator<U>&) { return false; }
+
+
+using string = __gnu_cxx::__versa_string<char, std::char_traits<char>,
+                                         Allocator<char>,
+                                         __gnu_cxx::__rc_string_base>;
+
+string f()
+{
+  string s1("xxxxxx");
+  string s2 = s1;
+  s1.clear();
+  return s2;
+}
+
+int main()
+{
+  for (int i = 0; i < 10; i++) {
+    try {
+      fail_after = i;
+      f();
+      break;
+    } catch (std::bad_alloc) {
+    }
+  }
+}

Re: [PATCH] Improve string::clear() performance

[Cong Wang]

On Fri, Sep 23, 2016 at 10:25 AM, Jonathan Wakely <jwakely@redhat.com> wrote:
>
> I'm applying this patch, which is my one from 2014 with a check for
> whether the string is shared, so we just set the length to zero (and
> don't throw away reusable capacity) when it's not shared.
>
> Tested x86_64-linux, committed to trunk.

Great! Thanks for letting me know.