Add optimization to basic_string::assign for compile-time known constant values.

[mvels]

Summary

This change optimizes the assign() methods for string where either the contents or lengths are compile time known constants. For small strings (< min_cap) we can execute the assignment entirely inline. For strings up to 128 bytes we allow the compiler to efficiently inline the copy operation after we call the offline __resize<>() method. Short / long branches are taken at the call site for better branch prediction and allowing FDO optimizations.

Benchmarks (unstable / google perflab):

name                                                old time/op             new time/op             delta
BM_StringAssignAsciiz_Empty_Opaque                  5.69ns ± 7%             5.97ns ± 7%     ~             (p=0.056 n=5+5)
BM_StringAssignAsciiz_Empty_Transparent             5.39ns ± 7%             0.79ns ± 8%  -85.36%          (p=0.008 n=5+5)
BM_StringAssignAsciiz_Small_Opaque                  11.2ns ± 5%             11.0ns ± 6%     ~             (p=0.548 n=5+5)
BM_StringAssignAsciiz_Small_Transparent             10.1ns ± 7%              1.0ns ± 8%  -89.76%          (p=0.008 n=5+5)
BM_StringAssignAsciiz_Large_Opaque                  23.5ns ± 7%             23.8ns ± 7%     ~             (p=0.841 n=5+5)
BM_StringAssignAsciiz_Large_Transparent             21.4ns ± 7%             12.7ns ± 7%  -40.83%          (p=0.008 n=5+5)
BM_StringAssignAsciiz_Huge_Opaque                    336ns ± 4%              327ns ± 7%     ~             (p=0.421 n=5+5)
BM_StringAssignAsciiz_Huge_Transparent               331ns ± 5%              324ns ± 7%     ~             (p=0.548 n=5+5)
BM_StringAssignAsciizMix_Opaque                     13.6ns ±10%             13.7ns ± 9%     ~             (p=0.690 n=5+5)
BM_StringAssignAsciizMix_Transparent                12.9ns ± 8%              3.6ns ± 8%  -71.82%          (p=0.008 n=5+5)

[mvels]

Adjusted for sizeof(value_type)

[mvels]

Added proper constant for min short -> long promotion size

[ldionne]

Please make sure you update the ABI v2 abi list when you make these changes. It's currently broken (and this change will break it even more). You can run make check-cxx-abilist to see the failures.

Or, I guess we can also have a discussion to disable the abi list tests for unstable ABIs, since it's not that useful I guess.

[mvels]

Simplified change to inlined optimizations.

[mvels]

Fixed external instantiations for unstable (removed __resize)

[mvels]

In D78763#2001599, @ldionne wrote:

Please make sure you update the ABI v2 abi list when you make these changes. It's currently broken (and this change will break it even more). You can run make check-cxx-abilist to see the failures.

Or, I guess we can also have a discussion to disable the abi list tests for unstable ABIs, since it's not that useful I guess.

Thanks Luis, I noticed the ABI list checks are remove from unstable, thanks!

I will check with ericwf@ on further review, I scoped this change down to only the inlining part, optimizing capacity step ups and growth will follow in separate changes (our data indicates its a win)

[mvels]

Restricted assign to __min_cap

[ldionne]

In D78763#2049008, @mvels wrote:

In D78763#2001599, @ldionne wrote:

Please make sure you update the ABI v2 abi list when you make these changes. It's currently broken (and this change will break it even more). You can run make check-cxx-abilist to see the failures.

Or, I guess we can also have a discussion to disable the abi list tests for unstable ABIs, since it's not that useful I guess.

Thanks Luis, I noticed the ABI list checks are remove from unstable, thanks!

They are removed from the unstable ABI, but not from the ABI v2. Those are different things (and I guess it doesn't really make sense for them to be different). But we should either decide that we don't test abi lists for ABI v2, or fix it. I suggest we fix it for now in order to make progress on this. You just need to update the ABI list for v2, it shouldn't be difficult.

[mvels]

They are removed from the unstable ABI, but not from the ABI v2. Those are different things (and I guess it doesn't really make sense for them to be different). But we should either decide that we don't test abi lists for ABI v2, or fix it. I suggest we fix it for now in order to make progress on this. You just need to update the ABI list for v2, it shouldn't be difficult.

Ah, gotcha, I only tested V1 and unstable, I always forget there is this weird child called 'V2' :)

[ldionne]

In D78763#2049928, @mvels wrote:

They are removed from the unstable ABI, but not from the ABI v2. Those are different things (and I guess it doesn't really make sense for them to be different). But we should either decide that we don't test abi lists for ABI v2, or fix it. I suggest we fix it for now in order to make progress on this. You just need to update the ABI list for v2, it shouldn't be difficult.

Ah, gotcha, I only tested V1 and unstable, I always forget there is this weird child called 'V2' :)

Well, I think we should probably remove that notion, or merge it with the "unstable" ABI. It's not really a thing since V2 is basically unstable AFAICT.

Just fix it and we can improve the situation (i.e. probably remove it) later.

[mvels]

Well, I think we should probably remove that notion, or merge it with the "unstable" ABI. It's not really a thing since V2 is basically unstable AFAICT.

Just fix it and we can improve the situation (i.e. probably remove it) later.

I have no way to verify / test this (cross compiling apple darwin v2 looks to be impossible?), and guessing the mangled names from x86 compiles seems dubious as well given the diffs I see on apple v1 vs linux v1

Shall I simply remove the x86_64-apple-darwin.v2.abilist insteasd? (I noticed these are simple 'check if present' targets)

[ldionne]

In D78763#2057956, @mvels wrote:

Well, I think we should probably remove that notion, or merge it with the "unstable" ABI. It's not really a thing since V2 is basically unstable AFAICT.

Just fix it and we can improve the situation (i.e. probably remove it) later.

I have no way to verify / test this (cross compiling apple darwin v2 looks to be impossible?), and guessing the mangled names from x86 compiles seems dubious as well given the diffs I see on apple v1 vs linux v1

Shall I simply remove the x86_64-apple-darwin.v2.abilist insteasd? (I noticed these are simple 'check if present' targets)

Yeah, I guess that's fine. Nobody uses it anyway.

[mvels]

Removed Apple V2 abi list

[mvels]

Update diff after master pull

[ldionne]

libcxx/include/string

2306–2307

It used to be __n <= ..., now it's __n < ... -- what am I missing?

[mvels]

libcxx/include/string

2306–2307

The initial version was aimed at optimizing 2 things:

• short optimization, i.e., [n] chars < min_cap guaranteed to fit inside any SSO or heap allocated string
• small memcpy optimization, i.., n <= 128 which when inlined can be vectorized efficiently (i.e., a rough max memcpy inline)

For this change we should focus only on the former. The latter is better picked up as an FDO / LLVM compiler inlining opportunity.

[ldionne]

I think you answered all my questions. Feel free to wait for Eric if he wants to review it too, but by now you know our string better than I do :)

[mvels]

Optimed ternary op for ascizz string -> always evalutate length in inlined constant string.

[mvels]

Thanks for the reviews!

I am pretty confident about these changes, and the numbers held up well on our benchmarks. I'm running an internal global presubmit on our depot to double check for any weirdness before committing.

[mvels]

Uploading clean diff

[mvels]

Uploaded clean diff in case harbormaster is confused about diffs

[mvels]

I'm mystified why the build fails, it fails on applying the patch:

$ ./scripts/buildkite/apply_patch.sh
repository exist, will reuse
working dir /mnt/disks/ssd0/agent/llvm-project-fork
Syncing local, origin and upstream...
refresh of master branch completed
Getting dependencies of 271828
Base revision is cd2553de77f2c3206deaa261a15cc7520ff2ff56
git reset, git cleanup...
Analyzing D78763
Applying diff 271828 for revision D78763...
Traceback (most recent call last):
  File "scripts/phabtalk/apply_patch2.py", line 331, in <module>
    patcher.run()
  File "scripts/phabtalk/apply_patch2.py", line 124, in run
    self._apply_diff(self.diff_id, revision_id)
  File "scripts/phabtalk/apply_patch2.py", line 240, in _apply_diff
    raise Exception('Applying patch failed:\n{}'.format(proc.stdout + proc.stderr))
Exception: Applying patch failed:
error: patch failed: libcxx/include/string:1528
error: libcxx/include/string: patch does not apply
error: patch failed: libcxx/include/__string:184
error: libcxx/include/__string: patch does not apply

Which I have no clue .... why? I locally pulled, confirmed (and uploaded) the diff from "git diff origin", yet it fails... Not sure if I should dig into rev cd2553de77f2c3206deaa261a15cc7520ff2ff56 or the whys here?

[mvels]

Looks like harbormaster builds use arcanist, and arcanist has **magic ** making awful diffs?

For example, I cleanly pulled both my local master and local branch.
git diff against HEAD and origin both confirm the true diff

arc diff --preview gives ....... **magic*** (https://reviews.llvm.org/differential/diff/272089/)

I have no idea how this all works, or to have phabricator understand / build with a clean full diff against head.....

I'll likely ignore this, if this really breaks build we'll roll back, but does not look like I get any good signal here (and local builds all work fine for me)

[mvels]

Running arc diff --update D78763

[mvels]

arc diff with --head=HEAD 'HEAD~1'

[mvels]

I'm going to abandon this diff, seems arcanist, phabricator and I can't see each other eye to eye...... :\ which makes me sad,....

Create new diff (same as this) in https://reviews.llvm.org/D82220

[mvels]

In D78763#2104284, @mvels wrote:

I'm going to abandon this diff, seems arcanist, phabricator and I can't see each other eye to eye...... :\ which makes me sad,....

Create new diff (same as this) in https://reviews.llvm.org/D82220

And, another 'arcanist suprise' :\

From a clean local branch: https://reviews.llvm.org/D82221

Abandoning this change, sorry for all the noise, one day I am sure all this will be over and we all will be using plain git and all that

libcxx/include/__string

#define _LIBCPP_STRING_UNSTABLE_EXTERN_TEMPLATE_LIST(_Func, _CharType) \
   _Func(_LIBCPP_FUNC_VIS _CharType& basic_string<_CharType>::at(size_type)) \
   _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>::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 _CharType* basic_string<_CharType>::__resize<false>(size_type)) \
-  _Func(_LIBCPP_FUNC_VIS _CharType* basic_string<_CharType>::__resize<true>(size_type)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, basic_string const&, size_type, size_type))
 
 
 // char_traits
 
 template <class _CharT>
 struct _LIBCPP_TEMPLATE_VIS char_traits
 {

libcxx/include/string

void __zero() _NOEXCEPT
             for (unsigned __i = 0; __i < __n_words; ++__i)
                 __a[__i] = 0;
         }
 
     template <size_type __a> static
         _LIBCPP_INLINE_VISIBILITY
         size_type __align_it(size_type __s) _NOEXCEPT
             {return (__s + (__a-1)) & ~(__a-1);}
-    enum {__alignment = 16, __min_long_capacity = 32 };
+    enum {__alignment = 16};
     static _LIBCPP_INLINE_VISIBILITY
     size_type __recommend(size_type __s) _NOEXCEPT
         {
         if (__s < __min_cap) return static_cast<size_type>(__min_cap) - 1;
         size_type __guess = __align_it<sizeof(value_type) < __alignment ?
                      __alignment/sizeof(value_type) : 1 > (__s+1) - 1;
         if (__guess == __min_cap) ++__guess;
         return __guess;
         }
-    static _LIBCPP_INLINE_VISIBILITY size_type
-        __recommend_cap(size_type __cap) _NOEXCEPT {
-      return __align_it < sizeof(value_type) < __alignment
-          ? __alignment / sizeof(value_type)
-          : 1 > (__cap);
-    }
 
     inline
     void __init(const value_type* __s, size_type __sz, size_type __reserve);
     inline
     void __init(const value_type* __s, size_type __sz);
     inline
     void __init(size_type __n, value_type __c);
 
#endif
     _LIBCPP_INLINE_VISIBILITY
     void __move_assign_alloc(basic_string&, false_type)
         _NOEXCEPT
         {}
 
     basic_string& __assign_external(const value_type* __s);
     basic_string& __assign_external(const value_type* __s, size_type __n);
 
-    template <bool __is_short>
-    value_type* __resize(size_type __n);
-
-    inline value_type* __resize(size_type __n) {
-      return __is_long() ? __resize<false>(__n) : __resize<true>(__n);
-    }
-
-    inline value_type* __resize_small(size_type __n) _NOEXCEPT {
+    // Assigns the value in __s, guaranteed to be __n < __min_cap in length.
+    inline basic_string& __assign_short(const value_type* __s, size_type __n) {
       pointer __p = __is_long()
                         ? (__set_long_size(__n), __get_long_pointer())
                         : (__set_short_size(__n), __get_short_pointer());
+      traits_type::move(_VSTD::__to_address(__p), __s, __n);
       traits_type::assign(__p[__n], value_type());
-      return  _VSTD::__to_address(__p);
-    }
-
-    inline basic_string& __assign_small_length(const value_type* __s,
-                                               size_type __n) {
-      value_type* p = (__n < __min_cap) ? __resize_small(__n) : __resize(__n);
-      if (__builtin_constant_p(*__s)) {
-        traits_type::copy(p, __s, __n);
-      } else {
-        traits_type::move(p, __s, __n);
-      }
       return *this;
     }
 
     _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
     _LIBCPP_INLINE_VISIBILITY void __invalidate_iterators_past(size_type);
 
     friend basic_string operator+<>(const basic_string&, const basic_string&);
     friend basic_string operator+<>(const value_type*, const basic_string&);
basic_string<_CharT, _Traits, _Allocator>::__grow_by_and_replace
     __set_long_pointer(__p);
     __set_long_cap(__cap+1);
     __old_sz = __n_copy + __n_add + __sec_cp_sz;
     __set_long_size(__old_sz);
     traits_type::assign(__p[__old_sz], value_type());
 }
 
 template <class _CharT, class _Traits, class _Allocator>
-template <bool __is_short>
-_CharT* basic_string<_CharT, _Traits, _Allocator>::__resize(size_type __n) {
-  size_type __old_cap = __is_short ? __min_cap : __get_long_cap();
-  pointer __old_p = __is_short ? __get_short_pointer() : __get_long_pointer();
-  if (__n < __old_cap) {
-    __is_short ? __set_short_size(__n) : __set_long_size(__n);
-    return _VSTD::__to_address(__old_p);
-  }
-
-  const size_type __ms = max_size();
-  if (__n > __ms) this->__throw_length_error();
-
-  size_type __new_cap;
-  if (__is_short) {
-    __new_cap = __recommend_cap(_VSTD::max<size_type>(
-        __n + 1, __min_long_capacity / sizeof(value_type)));
-  } else {
-    __new_cap = (__old_cap < __ms / 2 - __alignment)
-                    ? __recommend_cap(_VSTD::max(__n + 1, 2 * __old_cap))
-                    : __ms;
-  }
-  pointer __p = __alloc_traits::allocate(__alloc(), __new_cap);
-  __invalidate_all_iterators();
-  __set_long_pointer(__p);
-  __is_short ? __set_short_size(__n) : __set_long_size(__n);
-  __set_long_cap(__new_cap);
-  if (!__is_short) {
-    __alloc_traits::deallocate(__alloc(), __old_p, __old_cap);
-  }
-  return __p;
-}
-
-template <class _CharT, class _Traits, class _Allocator>
 void
 basic_string<_CharT, _Traits, _Allocator>::__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)
 {
     size_type __ms = max_size();
     if (__delta_cap > __ms - __old_cap)
         this->__throw_length_error();
     pointer __old_p = __get_pointer();
basic_string<_CharT, _Traits, _Allocator>::__assign_external(
   return *this;
 }
 
 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");
-    return (__builtin_constant_p(__n) && __n <= 128 / sizeof(value_type))
-               ? __assign_small_length(__s, __n)
+    return (_LIBCPP_BUILTIN_CONSTANT_P(__n) && __n < __min_cap)
+               ? __assign_short(__s, __n)
                : __assign_external(__s, __n);
 }
 
 template <class _CharT, class _Traits, class _Allocator>
 basic_string<_CharT, _Traits, _Allocator>&
 basic_string<_CharT, _Traits, _Allocator>::assign(size_type __n, value_type __c)
 {
     size_type __cap = capacity();
basic_string<_CharT, _Traits, _Allocator>::__assign_external(const value_type* __s) {
   return __assign_external(__s, traits_type::length(__s));
 }
 
 template <class _CharT, class _Traits, class _Allocator>
 basic_string<_CharT, _Traits, _Allocator>&
 basic_string<_CharT, _Traits, _Allocator>::assign(const value_type* __s)
 {
     _LIBCPP_ASSERT(__s != nullptr, "string::assign received nullptr");
-    return (__builtin_constant_p(*__s) && traits_type::length(__s) <= 128)
-               ? __assign_small_length(__s, traits_type::length(__s))
+    return (_LIBCPP_BUILTIN_CONSTANT_P(*__s) && traits_type::length(__s) <= 128)
+               ? __assign_short(__s, traits_type::length(__s))
                : __assign_external(__s);
 }
 // append
 
 template <class _CharT, class _Traits, class _Allocator>
 basic_string<_CharT, _Traits, _Allocator>&
 basic_string<_CharT, _Traits, _Allocator>::append(const value_type* __s, size_type __n)
 {