optimize basic_string

Jonathan Wakely jwakely@redhat.com
Mon Nov 25 17:25:02 GMT 2024


On 24/11/24 01:42 +0100, Jan Hubicka wrote:
>Hi,
>another common source of unnecesary throw_bad_alloc calls is basic_string::_M_create.
>    basic_string<_CharT, _Traits, _Alloc>::
>    _M_create(size_type& __capacity, size_type __old_capacity)
>    {
>      // _GLIBCXX_RESOLVE_LIB_DEFECTS
>      // 83.  String::npos vs. string::max_size()
>      if (__capacity > max_size())
>	std::__throw_length_error(__N("basic_string::_M_create"));
>
>      // The below implements an exponential growth policy, necessary to
>      // meet amortized linear time requirements of the library: see
>      // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
>      if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
>	{
>	  __capacity = 2 * __old_capacity;
>	  // Never allocate a string bigger than max_size.
>	  if (__capacity > max_size())
>	    __capacity = max_size();
>	}
>
>      // NB: Need an array of char_type[__capacity], plus a terminating
>      // null char_type() element.
>      return _S_allocate(_M_get_allocator(), __capacity + 1);
>    }
>
>The code makes it visible that string is never bigger then max_size, however + 1
>makes it one byte bigger than maximal size allowed by allocator.  I believe
>this is by miscounting the 0 at the end of string in max_size function:
>
>-      { return (_Alloc_traits::max_size(_M_get_allocator()) - 1) / 2; }
>+      { return _Alloc_traits::max_size(_M_get_allocator()) / 2 - 1; }

Ah yes, good catch. That code was copied from ext/sso_string_base.h
where it has been present since r0-76546-g3ad7074772808f in 2006!

>Path also adds __builtin_unreachable to express value ranges of capacity and length.
>This makes it possible to optimize out throw when copying strings as in the testcase.
>
>std::string
>test (std::string &a)
>{
>	return a;
>}
>
>This now yields the following:
>
>struct string test (struct string & a)
>{
>  size_type __siz;
>  struct string & _2(D);
>  char[16] * _4;
>  char * _5;
>  char * _7;
>  char * prephitmp_10;
>  char * pretmp_11;
>  char _15;
>  char * _18;
>  char * _27;
>  long unsigned int _32;
>
>  <bb 2> [local count: 1073741824]:
>  _4 = &MEM[(struct basic_string *)_2(D)].D.32970._M_local_buf;
>  MEM[(struct _Alloc_hider *)_2(D)]._M_p = _4;
>  _5 = MEM[(const struct basic_string *)a_3(D)]._M_dataplus._M_p;
>  __siz_6 = MEM[(const struct basic_string *)a_3(D)]._M_string_length;
>  if (__siz_6 > 15)
>    goto <bb 3>; [33.00%]
>  else
>    goto <bb 4>; [67.00%]
>
>  <bb 3> [local count: 354334800]:
>  _32 = __siz_6 + 1;
>  _27 = operator new (_32);
>  MEM[(struct basic_string *)_2(D)]._M_dataplus._M_p = _27;
>  MEM[(struct basic_string *)_2(D)].D.32970._M_allocated_capacity = __siz_6;
>  goto <bb 8>; [100.00%]
>
>  <bb 4> [local count: 719407024]:
>  if (__siz_6 == 1)
>    goto <bb 5>; [34.00%]
>  else
>    goto <bb 7>; [66.00%]
>
>  <bb 5> [local count: 353024841]:
>  _15 = MEM[(const char_type &)_5];
>  MEM[(char_type &)_2(D) + 16] = _15;
>
>  <bb 6> [local count: 350316931]:
>  goto <bb 9>; [100.00%]
>
>  <bb 7> [local count: 474808633]:
>  if (__siz_6 == 0)
>    goto <bb 6>; [73.78%]
>  else
>    goto <bb 8>; [26.22%]
>
>  <bb 8> [local count: 334966574]:
>  # _7 = PHI <_4(7), _27(3)>
>  __builtin_memcpy (_7, _5, __siz_6);
>  pretmp_11 = MEM[(const struct basic_string *)_2(D)]._M_dataplus._M_p;
>
>  <bb 9> [local count: 1038308344]:
>  # prephitmp_10 = PHI <_4(6), pretmp_11(8)>
>  MEM[(struct basic_string *)_2(D)]._M_string_length = __siz_6;
>  _18 = prephitmp_10 + __siz_6;
>  MEM[(char_type &)_18] = 0;
>  return _2(D);
>
>}
>
>.text segment is reduced from 213 bytes to 192 (saving 2 conditionals
>and 2 calls to throw)
>
>I find it funny that the code special cases a.size () == 1 to copy single byte
>and a.size () == 0 to bypass memcpy call.  I would say it is job of middle-end
>to optimize memcpy reasonably even for small blocks.  Was this based on some data
>showing that many strings have size of 0 and 1 which is not visible to
>compiler?

That was added as _M_copy in 2004 by r0-62838-gec61e852bc917b and when
I implemented the new std::__cxx11::basic_string I copied it, only
renaming it to _S_copy because that's our convention for static member
functions.

There's no explanation in the ChangeLog (obviously, because ChangeLog
files are useless at telling you *why* something happened), but this
comment was added:

+      // When __n = 1 way faster than the general multichar
+      // traits_type::copy/move/assign.

Back in 2004 char_traits<char>::copy called memcpy (not
__builtin_memcpy) and maybe it was badly optimized.

I think we can probably drop that "optimization" for __n == 1.

>regtested x86_64-linux, OK?
>
>Honza
>
>libstdc++-v3/ChangeLog:
>
>	* include/bits/basic_string.h:
>
>gcc/testsuite/ChangeLog:
>
>	* g++.dg/tree-ssa/string-1.C: New test.
>
>diff --git a/gcc/testsuite/g++.dg/tree-ssa/string-1.C b/gcc/testsuite/g++.dg/tree-ssa/string-1.C
>new file mode 100644
>index 00000000000..d38c23a7628
>--- /dev/null
>+++ b/gcc/testsuite/g++.dg/tree-ssa/string-1.C
>@@ -0,0 +1,9 @@
>+/* { dg-do compile } */
>+/* { dg-options "-O3 -std=c++20 -fdump-tree-optimized" } */
>+#include <string>
>+std::string
>+test (std::string &a)
>+{
>+	return a;
>+}
>+/* { dg-final { scan-tree-dump-not "throw" "optimized" } } */
>diff --git a/libstdc++-v3/include/bits/basic_string.h b/libstdc++-v3/include/bits/basic_string.h
>index f5b320099b1..d754deb28ed 100644
>--- a/libstdc++-v3/include/bits/basic_string.h
>+++ b/libstdc++-v3/include/bits/basic_string.h
>@@ -1079,20 +1079,30 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
>       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
>       size_type
>       size() const _GLIBCXX_NOEXCEPT
>-      { return _M_string_length; }
>+      {
>+	size_type __siz = _M_string_length;

Please use __sz for these variables, as that's consistent with names
used elsewhere.

>+	if (__siz > max_size ())
>+	  __builtin_unreachable ();
>+	return __siz;
>+      }
>
>       ///  Returns the number of characters in the string, not including any
>       ///  null-termination.
>       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
>       size_type
>       length() const _GLIBCXX_NOEXCEPT
>-      { return _M_string_length; }
>+      {
>+	size_type __siz = _M_string_length;
>+	if (__siz > max_size ())
>+	  __builtin_unreachable ();
>+	return __siz;

Should this just call size() instead of repeating the definition?

>+      }
>
>       ///  Returns the size() of the largest possible %string.
>       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
>       size_type
>       max_size() const _GLIBCXX_NOEXCEPT
>-      { return (_Alloc_traits::max_size(_M_get_allocator()) - 1) / 2; }
>+      { return _Alloc_traits::max_size(_M_get_allocator()) / 2 - 1; }
>
>       /**
>        *  @brief  Resizes the %string to the specified number of characters.
>@@ -1184,8 +1194,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
>       size_type
>       capacity() const _GLIBCXX_NOEXCEPT
>       {
>-	return _M_is_local() ? size_type(_S_local_capacity)
>-	                     : _M_allocated_capacity;
>+	size_t __siz = _M_is_local() ? size_type(_S_local_capacity)

size_type __sz = ...

>+				     : _M_allocated_capacity;
>+	if (__siz < _S_local_capacity || __siz > max_size () + 1)

Is this +1 correct?

I think it should be simply `__siz > max_size()`

The largest allocation allowed is max_size()+1 but the value stored in
_M_allocated_capacity will be just max_size() without the +1.


>+	  __builtin_unreachable ();
>+	return __siz;
>       }
>
>       /**



More information about the Libstdc++ mailing list