Add optimization to basic_string::assign for compile-time known constant values.
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)
```
Reviewers: EricWF, #libc!
Subscribers: jfb, libcxx-commits
Tags: #libc
Differential Revision: https://reviews.llvm.org/D82221
Cr-Mirrored-From: https://chromium.googlesource.com/external/github.com/llvm/llvm-project
Cr-Mirrored-Commit: 2bad2226801f32362036b471d35a40dc5f343632
diff --git a/include/__string b/include/__string
index 2c038ce..9060bf9 100644
--- a/include/__string
+++ b/include/__string
@@ -152,7 +152,8 @@
_Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, value_type const*, size_type)) \
_Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::size_type basic_string<_CharType>::find_first_of(value_type const*, size_type, size_type) const) \
_Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, size_type, value_type)) \
- _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(value_type const*, size_type)) \
+ _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::__assign_external(value_type const*, size_type)) \
+ _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::__assign_external(value_type const*)) \
_Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::reserve(size_type)) \
_Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(value_type const*, size_type)) \
_Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::assign(basic_string const&, size_type, size_type)) \
@@ -176,7 +177,6 @@
_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) \
diff --git a/include/string b/include/string
index 7fc4280..2f846ed 100644
--- a/include/string
+++ b/include/string
@@ -1659,6 +1659,19 @@
_NOEXCEPT
{}
+ basic_string& __assign_external(const value_type* __s);
+ basic_string& __assign_external(const value_type* __s, size_type __n);
+
+ // 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 *this;
+ }
+
_LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
_LIBCPP_INLINE_VISIBILITY void __invalidate_iterators_past(size_type);
@@ -2269,24 +2282,30 @@
template <class _CharT, class _Traits, class _Allocator>
basic_string<_CharT, _Traits, _Allocator>&
+basic_string<_CharT, _Traits, _Allocator>::__assign_external(
+ const value_type* __s, size_type __n) {
+ size_type __cap = capacity();
+ if (__cap >= __n) {
+ value_type* __p = _VSTD::__to_address(__get_pointer());
+ traits_type::move(__p, __s, __n);
+ traits_type::assign(__p[__n], value_type());
+ __set_size(__n);
+ __invalidate_iterators_past(__n);
+ } else {
+ size_type __sz = size();
+ __grow_by_and_replace(__cap, __n - __cap, __sz, 0, __sz, __n, __s);
+ }
+ 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");
- size_type __cap = capacity();
- if (__cap >= __n)
- {
- value_type* __p = _VSTD::__to_address(__get_pointer());
- traits_type::move(__p, __s, __n);
- traits_type::assign(__p[__n], value_type());
- __set_size(__n);
- __invalidate_iterators_past(__n);
- }
- else
- {
- size_type __sz = size();
- __grow_by_and_replace(__cap, __n - __cap, __sz, 0, __sz, __n, __s);
- }
- return *this;
+ return (_LIBCPP_BUILTIN_CONSTANT_P(__n) && __n < __min_cap)
+ ? __assign_short(__s, __n)
+ : __assign_external(__s, __n);
}
template <class _CharT, class _Traits, class _Allocator>
@@ -2473,12 +2492,21 @@
template <class _CharT, class _Traits, class _Allocator>
basic_string<_CharT, _Traits, _Allocator>&
+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 assign(__s, traits_type::length(__s));
+ return _LIBCPP_BUILTIN_CONSTANT_P(*__s)
+ ? (traits_type::length(__s) < __min_cap
+ ? __assign_short(__s, traits_type::length(__s))
+ : __assign_external(__s, traits_type::length(__s)))
+ : __assign_external(__s);
}
-
// append
template <class _CharT, class _Traits, class _Allocator>