Partially inline basic_string::operator=(const basic_string&)

[mvels]

Summary

This change partially inlines operator=(const basic_string&) where both the input and current instance are short strings, making the assignment a fixed length inlined memcpy.

Assignments where either of the strings are long are delegate to assign_no_alias<is_short>(), which is templated for the long / short branch already observed in the caller.

Stable:

--------------------------------------------------------------------------------
Benchmark                                     Time             CPU   Iterations
--------------------------------------------------------------------------------
BM_StringAssignStr_Empty_Opaque            2.65 ns         2.66 ns    263745536
BM_StringAssignStr_Empty_Transparent       2.95 ns         2.96 ns    236494848
BM_StringAssignStr_Small_Opaque            2.93 ns         2.94 ns    237301760
BM_StringAssignStr_Small_Transparent       2.69 ns         2.69 ns    265809920
BM_StringAssignStr_Large_Opaque            19.6 ns         19.6 ns     35573760
BM_StringAssignStr_Large_Transparent       19.1 ns         19.1 ns     36716544
BM_StringAssignStr_Huge_Opaque             1901 ns         1901 ns       364544
BM_StringAssignStr_Huge_Transparent        1889 ns         1889 ns       360448

Unstable

--------------------------------------------------------------------------------
Benchmark                                     Time             CPU   Iterations
--------------------------------------------------------------------------------
BM_StringAssignStr_Empty_Opaque            1.29 ns         1.29 ns    540454912
BM_StringAssignStr_Empty_Transparent       1.11 ns         1.12 ns    628482048
BM_StringAssignStr_Small_Opaque            1.29 ns         1.29 ns    541216768
BM_StringAssignStr_Small_Transparent       1.11 ns         1.11 ns    629469184
BM_StringAssignStr_Large_Opaque            15.6 ns         15.6 ns     44945408
BM_StringAssignStr_Large_Transparent       14.9 ns         14.9 ns     46764032
BM_StringAssignStr_Huge_Opaque             1713 ns         1713 ns       401408
BM_StringAssignStr_Huge_Transparent        1704 ns         1704 ns       397312

[mvels]

Fix left behind comment

[EricWF]

@mvels Can you look over this diff?

There are two copies of each file in different locations.

Please update this review with a clean diff.

[mvels]

Removed duplicated files

[mvels]

In D75211#1894428, @EricWF wrote:

@mvels Can you look over this diff?

There are two copies of each file in different locations.

Please update this review with a clean diff.

Picked a new diff, looks good afaics

[ldionne]

Requesting changes so it shows up properly in my review queue (for question about assign). Otherwise this looks excellent.

libcxx/include/__string

168

Now I'm thinking that splitting stable an unstable was a *really* good decision. I don't even have to worry about the effects of this change on the stable ABI.

libcxx/include/string

2212

I love this

2292

Are there homologous changes we should make to the various assign methods?

[EricWF]

LGTM after addressing @ldionne's comment about other assign methods that might benefit from this.

Though I'm happy to see those changes in another patch.

[mvels]

libcxx/include/__string

168

Yes, I agree. BTW: we still need to make the ifdef under an ABI flag as Eric pointed out, but those sre mostly cosmetics.

Eric and I were discussing ideas Eric had about a future where we are not having to deal with all this ABI pain, and where we don't need these absolute splits. I do think we can get there (eventually), but until then, this is my preferred least worse solution :)

libcxx/include/string

2212

Thanks, yes, it's an easy way to avoid branches, but also some other ideas that are in the pipeline that Eric and I discussed.

For example, a 'grow' function that is overloaded for short / long. Our current growth pattern is a bit awkward as going from an SSO to a long string, we have 23 * 2 = 46 as a min cap, leading to an awkward first step up of 48 for length in range [23-47] (which also awkwardly doubles to 96, etc). Going from SSO to either 32 or 64 is a cleaner and cheaper step up and cache line friendly.

2292

Yes, although I plan to have all these in separate incremental reviews. There may be some shuffling small adjustments of these functions going forward, but this being unstable, nothing we can not tinker with incrementally.

I'd also like to have my document shared soon (a mid week / weekend of skiing currently is in the way). For the 'regular' assign, there are some additional factors, for example, for assign(const value_type*), if we know the length at compile time, there is no need to exercise traits::length in the external code, we can special case those in a partial inlineable part (i.e., the submitted builtin_constant_p) which calls __assign_no_alias (as constant strings never alias). Ditto, if the string is at compile time known to be short, we can directly inline the assign, and have all other code elided, etc.

Like Eric imo these are best done incrementally

libcxx/__string

#define _LIBCPP_STRING_UNSTABLE_EXTERN_TEMPLATE_LIST(_Func, _CharType) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::copy(value_type*, size_type, size_type) const) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::basic_string(basic_string const&, size_type, size_type, std::allocator<_CharType> const&)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find(value_type, size_type) const) \
   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init(size_type, value_type)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, value_type const*)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_last_of(value_type const*, size_type, size_type) const) \
   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__grow_by(size_type, size_type, size_type, size_type, size_type, size_type)) \
   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__grow_by_and_replace(size_type, size_type, size_type, size_type, size_type, size_type, value_type const*)) \
+  _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__assign_no_alias<false>(value_type const*, size_type)) \
+  _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__assign_no_alias<true>(value_type const*, size_type)) \
   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::push_back(value_type)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(size_type, value_type)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::rfind(value_type, size_type) const) \
   _Func(_LIBCPP_FUNC_VIS const basic_string<_CharType>::size_type basic_string<_CharType>::npos) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(size_type, value_type)) \
   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__erase_external_with_move(size_type, size_type)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(basic_string const&, size_type, size_type)) \
   _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(value_type const*) const) \
   _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, value_type const*) const) \
   _Func(_LIBCPP_FUNC_VIS _CharType& basic_string<_CharType>::at(size_type)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(value_type const*)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find(value_type const*, size_type, size_type) const) \
   _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, basic_string const&, size_type, size_type) const) \
   _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, value_type const*, size_type) const) \
-  _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::operator=(basic_string const&)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(value_type const*)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, basic_string const&, size_type, size_type)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::iterator basic_string<_CharType>::insert(basic_string::const_iterator, value_type)) \
   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::resize(size_type, value_type)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, basic_string const&, size_type, size_type))
 
 
 // char_traits

libcxx/include/__string

#define _LIBCPP_STRING_UNSTABLE_EXTERN_TEMPLATE_LIST(_Func, _CharType) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::copy(value_type*, size_type, size_type) const) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::basic_string(basic_string const&, size_type, size_type, std::allocator<_CharType> const&)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find(value_type, size_type) const) \
   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__init(size_type, value_type)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, value_type const*)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_last_of(value_type const*, size_type, size_type) const) \
   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__grow_by(size_type, size_type, size_type, size_type, size_type, size_type)) \
   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__grow_by_and_replace(size_type, size_type, size_type, size_type, size_type, size_type, value_type const*)) \
+  _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__assign_no_alias<false>(value_type const*, size_type)) \
+  _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__assign_no_alias<true>(value_type const*, size_type)) \
   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::push_back(value_type)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(size_type, value_type)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::rfind(value_type, size_type) const) \
   _Func(_LIBCPP_FUNC_VIS const basic_string<_CharType>::size_type basic_string<_CharType>::npos) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(size_type, value_type)) \
   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::__erase_external_with_move(size_type, size_type)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(basic_string const&, size_type, size_type)) \
   _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(value_type const*) const) \
   _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, value_type const*) const) \
   _Func(_LIBCPP_FUNC_VIS _CharType& basic_string<_CharType>::at(size_type)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(value_type const*)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find(value_type const*, size_type, size_type) const) \
   _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, basic_string const&, size_type, size_type) const) \
   _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, value_type const*, size_type) const) \
-  _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::operator=(basic_string const&)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(value_type const*)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, basic_string const&, size_type, size_type)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::iterator basic_string<_CharType>::insert(basic_string::const_iterator, value_type)) \
   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::resize(size_type, value_type)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, basic_string const&, size_type, size_type))
 
 
 // char_traits

libcxx/include/string

#endif  // _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
     __init(_ForwardIterator __first, _ForwardIterator __last);
 
     void __grow_by(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
                    size_type __n_copy,  size_type __n_del,     size_type __n_add = 0);
     void __grow_by_and_replace(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
                                size_type __n_copy,  size_type __n_del,
                                size_type __n_add, const value_type* __p_new_stuff);
 
+    // __assign_no_alias is invoked for assignment operations where we
+    // have proof that the input does not alias the current instance.
+    // For example, operator=(basic_string) performs a 'self' check.
+    template <bool __is_short>
+    void __assign_no_alias(const value_type* __s, size_type __n);
+
     _LIBCPP_INLINE_VISIBILITY
     void __erase_to_end(size_type __pos);
 
     // __erase_external_with_move is invoked for erase() invocations where
     // `n ~= npos`, likely requiring memory moves on the string data.
     void __erase_external_with_move(size_type __pos, size_type __n);
 
     _LIBCPP_INLINE_VISIBILITY
if (__old_cap+1 != __min_cap)
         __alloc_traits::deallocate(__alloc(), __old_p, __old_cap+1);
     __set_long_pointer(__p);
     __set_long_cap(__cap+1);
 }
 
 // assign
 
 template <class _CharT, class _Traits, class _Allocator>
+template <bool __is_short>
+void basic_string<_CharT, _Traits, _Allocator>::__assign_no_alias(
+    const value_type* __s, size_type __n) {
+  size_type __cap = __is_short ? __min_cap : __get_long_cap();
+  if (__n < __cap) {
+    pointer __p = __is_short ? __get_short_pointer() : __get_long_pointer();
+    __is_short ? __set_short_size(__n) : __set_long_size(__n);
+    traits_type::copy(_VSTD::__to_address(__p), __s, __n);
+    traits_type::assign(__p[__n], value_type());
+    __invalidate_iterators_past(__n);
+  } else {
+    size_type __sz = __is_short ? __get_short_size() : __get_long_size();
+    __grow_by_and_replace(__cap - 1, __n - __cap + 1, __sz, 0, __sz, __n, __s);
+  }
+}
+
+template <class _CharT, class _Traits, class _Allocator>
 basic_string<_CharT, _Traits, _Allocator>&
 basic_string<_CharT, _Traits, _Allocator>::assign(const value_type* __s, size_type __n)
 {
     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::assign received nullptr");
     size_type __cap = capacity();
     if (__cap >= __n)
     {
         value_type* __p = _VSTD::__to_address(__get_pointer());
basic_string<_CharT, _Traits, _Allocator>::operator=(value_type __c)
     traits_type::assign(*__p, __c);
     traits_type::assign(*++__p, value_type());
     __invalidate_iterators_past(1);
     return *this;
 }
 
 template <class _CharT, class _Traits, class _Allocator>
 basic_string<_CharT, _Traits, _Allocator>&
 basic_string<_CharT, _Traits, _Allocator>::operator=(const basic_string& __str)
 {
-    if (this != &__str)
-    {
-        __copy_assign_alloc(__str);
-        const bool __str_is_long = __str.__is_long(); // Force single branch
-        if (__is_long() || __str_is_long) {
-          return assign(__str.data(), __str.size());
-        }
+  if (this != &__str) {
+    if (!__is_long()) {
+      if (!__str.__is_long() /* !__str_is_long */) {
         __r_.first().__r = __str.__r_.first().__r;
-    }
-    return *this;
+      } else {
+        __assign_no_alias<true>(__str.data(), __str.size());
+      }
+    } else {
+      __assign_no_alias<false>(__str.data(), __str.size());
+    }
 }
 
 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _CharT, class _Traits, class _Allocator>
 inline
 void
 basic_string<_CharT, _Traits, _Allocator>::__move_assign(basic_string& __str, false_type)

libcxx/string

#endif  // _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
     __init(_ForwardIterator __first, _ForwardIterator __last);
 
     void __grow_by(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
                    size_type __n_copy,  size_type __n_del,     size_type __n_add = 0);
     void __grow_by_and_replace(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
                                size_type __n_copy,  size_type __n_del,
                                size_type __n_add, const value_type* __p_new_stuff);
 
+    // __assign_no_alias is invoked for assignment operations where we
+    // have proof that the input does not alias the current instance.
+    // For example, operator=(basic_string) performs a 'self' check.
+    template <bool __is_short>
+    void __assign_no_alias(const value_type* __s, size_type __n);
+
     _LIBCPP_INLINE_VISIBILITY
     void __erase_to_end(size_type __pos);
 
     // __erase_external_with_move is invoked for erase() invocations where
     // `n ~= npos`, likely requiring memory moves on the string data.
     void __erase_external_with_move(size_type __pos, size_type __n);
 
     _LIBCPP_INLINE_VISIBILITY
if (__old_cap+1 != __min_cap)
         __alloc_traits::deallocate(__alloc(), __old_p, __old_cap+1);
     __set_long_pointer(__p);
     __set_long_cap(__cap+1);
 }
 
 // assign
 
 template <class _CharT, class _Traits, class _Allocator>
+template <bool __is_short>
+void basic_string<_CharT, _Traits, _Allocator>::__assign_no_alias(
+    const value_type* __s, size_type __n) {
+  size_type __cap = __is_short ? __min_cap : __get_long_cap();
+  if (__n < __cap) {
+    pointer __p = __is_short ? __get_short_pointer() : __get_long_pointer();
+    __is_short ? __set_short_size(__n) : __set_long_size(__n);
+    traits_type::copy(_VSTD::__to_address(__p), __s, __n);
+    traits_type::assign(__p[__n], value_type());
+    __invalidate_iterators_past(__n);
+  } else {
+    size_type __sz = __is_short ? __get_short_size() : __get_long_size();
+    __grow_by_and_replace(__cap - 1, __n - __cap + 1, __sz, 0, __sz, __n, __s);
+  }
+}
+
+template <class _CharT, class _Traits, class _Allocator>
 basic_string<_CharT, _Traits, _Allocator>&
 basic_string<_CharT, _Traits, _Allocator>::assign(const value_type* __s, size_type __n)
 {
     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::assign received nullptr");
     size_type __cap = capacity();
     if (__cap >= __n)
     {
         value_type* __p = _VSTD::__to_address(__get_pointer());
basic_string<_CharT, _Traits, _Allocator>::operator=(value_type __c)
     __invalidate_iterators_past(1);
     return *this;
 }
 
 template <class _CharT, class _Traits, class _Allocator>
 basic_string<_CharT, _Traits, _Allocator>&
 basic_string<_CharT, _Traits, _Allocator>::operator=(const basic_string& __str)
 {
-    if (this != &__str)
-    {
-        __copy_assign_alloc(__str);
-        const bool __str_is_long = __str.__is_long(); // Force single branch
-        if (__is_long() || __str_is_long) {
-          return assign(__str.data(), __str.size());
-        }
+  if (this != &__str) {
+    if (!__is_long()) {
+      if (!__str.__is_long() /* !__str_is_long */) {
         __r_.first().__r = __str.__r_.first().__r;
-    }
-    return *this;
+      } else {
+        __assign_no_alias<true>(__str.data(), __str.size());
+      }
+    } else {
+      __assign_no_alias<false>(__str.data(), __str.size());
+    }
 }
 
 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _CharT, class _Traits, class _Allocator>
 inline
 void
 basic_string<_CharT, _Traits, _Allocator>::__move_assign(basic_string& __str, false_type)