Optimize / partially inline basic_string copy constructor

[mvels]

Summary

Splits copy constructor up inlining short initialization, outlining long initialization into __init_long() which is the externally instantiated slow path initialization.

Subsequently changing the copy ctor to be inlined (not externally instantiated) provides significant speed ups for short string initialization.

Generated code given:

void StringCopyCtor(void* mem, const std::string& s) {

std::string*p = new(mem) std::string{s};

}

asm:

cmp     byte ptr [rsi + 23], 0
js      .LBB0_2
mov     rax, qword ptr [rsi + 16]
mov     qword ptr [rdi + 16], rax
movups  xmm0, xmmword ptr [rsi]
movups  xmmword ptr [rdi], xmm0
ret

.LBB0_2:

jmp     std::basic_string::__init_long # TAILCALL

Benchmark:
BM_StringCopy_Empty 5.19ns ± 6% 1.50ns ± 8% -71.02% (p=0.000 n=10+10)
BM_StringCopy_Small 5.14ns ± 8% 1.53ns ± 7% -70.17% (p=0.000 n=10+10)
BM_StringCopy_Large 18.9ns ± 0% 19.3ns ± 0% +1.92% (p=0.000 n=10+10)
BM_StringCopy_Huge 309ns ± 1% 316ns ± 5% ~ (p=0.633 n=8+10)

[mvels]

• Optimize / partially inline basic_string assignment operator

Changed init_long to accept [s,n] following discussion with EricWF

[EricWF]

There are a couple of places that now duplicate the body of __init_long. Would it make sense to deduplicate that code in some way?

Also, the plan is to make the __init_long function externally instantiated. But that will be done in a follow-up change since it involves the ABI.

Otherwise, this LGTM.

libcxx/include/string

799

This comment is a weird place. It's probably better suited on __init_long itself.

802

Numbers never age well in comments. I would put them in the commit message instead.

1550

The name of this function should express the intention that it's out-of-line and explicitly instantiated.

Historically not much attention was paid to how std::string handled inlining and explicit instantiation, and now that we're fixing that I want to make it a clear part of any change.

How about __init_long_out_of_line, __init_long_external, or __init_long_slow?

[mvels]

Rename __init_long

[mvels]

libcxx/include/string

802

Removed reference, it will pop in the commit once we do the inlining :)

[EricWF]

LGTM

[EricWF]

Committed as a8a9c8e0a11abc9ed4ed78fed528334371fedf87.

[mgorny]

I'm afraid this breaks stuff. TableGen built against libc++ after this change misbehaves:

[18/31] Building ARMGenSystemRegister.inc...
FAILED: lib/Target/ARM/ARMGenSystemRegister.inc 
cd /home/motus/netbsd8/netbsd8/build-stage2 && /home/motus/netbsd8/netbsd8/build-stage2/bin/llvm-tblgen -gen-searchable-tables -I /home/motus/netbsd8/netbsd8/llvm-project/llvm/lib/Target/ARM -I /home/motus/netbsd8/netbsd8/llvm-project/llvm/include -I /home/motus/netbsd8/netbsd8/llvm-project/llvm/lib/Target /home/motus/netbsd8/netbsd8/llvm-project/llvm/lib/Target/ARM/ARM.td --write-if-changed -o lib/Target/ARM/ARMGenSystemRegister.inc -d lib/Target/ARM/ARMGenSystemRegister.inc.d
/home/motus/netbsd8/netbsd8/llvm-project/llvm/lib/Target/ARM/ARM.td:1269:1: error: Reached EOF without matching #endif

^
#0 0x000000000049b032 llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/home/motus/netbsd8/netbsd8/build-stage2/bin/llvm-tblgen+0x49b032)
#1 0x000000000049905c llvm::sys::RunSignalHandlers() (/home/motus/netbsd8/netbsd8/build-stage2/bin/llvm-tblgen+0x49905c)
#2 0x000000000049b5e0 SignalHandler(int) (/home/motus/netbsd8/netbsd8/build-stage2/bin/llvm-tblgen+0x49b5e0)
Stack dump:
0.      Program arguments: /home/motus/netbsd8/netbsd8/build-stage2/bin/llvm-tblgen -gen-searchable-tables -I /home/motus/netbsd8/netbsd8/llvm-project/llvm/lib/Target/ARM -I /home/motus/netbsd8/netbsd8/llvm-project/llvm/include -I /home/motus/netbsd8/netbsd8/llvm-project/llvm/lib/Target /home/motus/netbsd8/netbsd8/llvm-project/llvm/lib/Target/ARM/ARM.td --write-if-changed -o lib/Target/ARM/ARMGenSystemRegister.inc -d lib/Target/ARM/ARMGenSystemRegister.inc.d 
ninja: build stopped: subcommand failed.

http://lab.llvm.org:8014/builders/netbsd-amd64/builds/834/steps/ninja%20build%20local/logs/stdio

libcxx/include/string

public:
 
     _LIBCPP_INLINE_VISIBILITY explicit basic_string(const allocator_type& __a)
 #if _LIBCPP_STD_VER <= 14
         _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value);
 #else
         _NOEXCEPT;
 #endif
 
+    // Optimization opportunity: do not externally instantiate the copy
+    // constructor, which inlines short string initialization. Long string
+    // initialization is delegated to the (external) __init_long()method,
+    // which results in a 3X-4X speed up for SSO initialization.
     basic_string(const basic_string& __str);
     basic_string(const basic_string& __str, const allocator_type& __a);
 
 #ifndef _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     basic_string(basic_string&& __str)
 #if _LIBCPP_STD_VER <= 14
         _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
#endif  // _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
 
     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);
 
+    void __init_long(const basic_string& __str);
+
     template <class _InputIterator>
     inline
     typename enable_if
     <
         __is_exactly_cpp17_input_iterator<_InputIterator>::value,
         void
     >::type
     __init(_InputIterator __first, _InputIterator __last);
else
         __set_long_cap(__cap+1);
         __set_long_size(__sz);
     }
     traits_type::copy(_VSTD::__to_address(__p), __s, __sz);
     traits_type::assign(__p[__sz], value_type());
 }
 
 template <class _CharT, class _Traits, class _Allocator>
+void basic_string<_CharT, _Traits, _Allocator>::__init_long(
+    const basic_string& __str) {
+  const value_type* __s = _VSTD::__to_address(__str.__get_long_pointer());
+  size_type __sz = __str.__get_long_size();
+  size_type __cap = __recommend(__sz);
+  pointer __p = __alloc_traits::allocate(__alloc(), __cap + 1);
+  __set_long_pointer(__p);
+  __set_long_cap(__cap + 1);
+  __set_long_size(__sz);
+  traits_type::copy(_VSTD::__to_address(__p), __s, __sz);
+  traits_type::assign(__p[__sz], value_type());
+}
+
+template <class _CharT, class _Traits, class _Allocator>
 template <class>
 basic_string<_CharT, _Traits, _Allocator>::basic_string(const _CharT* __s, const _Allocator& __a)
     : __r_(__default_init_tag(), __a)
 {
     _LIBCPP_ASSERT(__s != nullptr, "basic_string(const char*, allocator) detected nullptr");
     __init(__s, traits_type::length(__s));
 #if _LIBCPP_DEBUG_LEVEL >= 2
     __get_db()->__insert_c(this);

 
 template <class _CharT, class _Traits, class _Allocator>
 basic_string<_CharT, _Traits, _Allocator>::basic_string(const basic_string& __str)
     : __r_(__default_init_tag(), __alloc_traits::select_on_container_copy_construction(__str.__alloc()))
 {
     if (!__str.__is_long())
         __r_.first().__r = __str.__r_.first().__r;
     else
-        __init(_VSTD::__to_address(__str.__get_long_pointer()), __str.__get_long_size());
+        __init_long(__str);
 #if _LIBCPP_DEBUG_LEVEL >= 2
     __get_db()->__insert_c(this);
 #endif
 }
 
 template <class _CharT, class _Traits, class _Allocator>
 basic_string<_CharT, _Traits, _Allocator>::basic_string(
     const basic_string& __str, const allocator_type& __a)
     : __r_(__default_init_tag(), __a)
 {
     if (!__str.__is_long())
         __r_.first().__r = __str.__r_.first().__r;
     else
-        __init(_VSTD::__to_address(__str.__get_long_pointer()), __str.__get_long_size());
+        __init_long(__str);
 #if _LIBCPP_DEBUG_LEVEL >= 2
     __get_db()->__insert_c(this);
 #endif
 }
 
 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _CharT, class _Traits, class _Allocator>