Optimize basic_string's memory usage

[ldionne]

Summary

• change __alignment from 16 to 8

The 16 value is likely inspired by the default glibc malloc() function returning 16 byte aligned memory. While this is true, this is not the underlying allocated capacity which for smaller allocs follows 8 + n * 16 which can be seen here: https://gcc.godbolt.org/z/WxeqWxqxY. Likewise, google's tcmalloc has finer grained allocations for all sizes from 64 - 128 bytes, meaning we also wast 8 bytes of allocation on every other allocation inside tcmalloc.

• change 'grow_by' to use precise size for the first SSO --> long allocation

The logic currently always at least doubles the capacity on growth. However, this causes any short or empty initialized string exceeding 22 bytes to be allocated to at least 48 bytes. (22 * 2 rounded up to 48). This is wasteful as there are likely plenty of strings that could be allocated into 40 (glibc) or 32 (tcmalloc) sized allocs.

[mvels]

Add grow_by without replace

[mvels]

Upload grow_by amended changes

[mvels]

Upload correct version this time

[mvels]

Fix headers removed by clang-format mess

[Mordante]

Thanks for working on this!

libcxx/include/string

2340

Can you add a bit more comment here why this is important. The text in the commit message contains a lot more information. When I read this message I was quite puzzled, after reading the commit message I understood what the reason for these changes are.

[mvels]

Added extra comments on string growth

[mvels]

BTW: I did not understand the Apple max_size.pass failure, I adjusted the test and they all pass (check-cxx) on my local git repo on x86.

[mvels]

Fix what I am sure is a bug in checking for max_size() in grow_by_....

[mvels]

Remove parenthesis from debugging

[Mordante]

In D155486#4532334, @mvels wrote:

BTW: I did not understand the Apple max_size.pass failure, I adjusted the test and they all pass (check-cxx) on my local git repo on x86.

On the backdeployment targets the new code uses the old version of the dylib. My suspicion is there is an ABI incompatibility. @philnik do you see an issue in this patch?

[philnik]

In D155486#4544305, @Mordante wrote:

In D155486#4532334, @mvels wrote:

BTW: I did not understand the Apple max_size.pass failure, I adjusted the test and they all pass (check-cxx) on my local git repo on x86.

On the backdeployment targets the new code uses the old version of the dylib. My suspicion is there is an ABI incompatibility. @philnik do you see an issue in this patch?

This is an ABI break, but I don't think that's the problem. max_size isn't instantiated. This look to me like there is an off-by-one error somewhere.

Could we split this into two patches? This is really seems like it has high potential for having subtile bugs.

libcxx/include/string

2338

Why do we want to change the growth specifically for the case when we go from short to long?

[mvels]

In D155486#4551579, @philnik wrote:

In D155486#4544305, @Mordante wrote:

In D155486#4532334, @mvels wrote:

BTW: I did not understand the Apple max_size.pass failure, I adjusted the test and they all pass (check-cxx) on my local git repo on x86.

On the backdeployment targets the new code uses the old version of the dylib. My suspicion is there is an ABI incompatibility. @philnik do you see an issue in this patch?

This is an ABI break, but I don't think that's the problem. max_size isn't instantiated. This look to me like there is an off-by-one error somewhere.

Could we split this into two patches? This is really seems like it has high potential for having subtile bugs.

Let me split the __alignment and growth changes in two separate patches

libcxx/include/string

2338

This is where most of the waste comes from, and we can also argue that the most common use case isn't actually 'Growing' the string, i.e., the doubling is to keep amortized growth on continued growth.

I.e., a common pattern is:

std::string s;
s = SomeValue();

In the above case assigning a value to s is not really "growing" the string, the fact that the size changes from 0 to n is a consequence of string not having a notion of "unassigned" (which is generally good).

But if you consider the above code, and SomeValue() returns a string of say, length 24, then the above algorithm would simply say we "grow from 0 to 24" and applies max(24, __min_cap * 2) = 44 bytes as minimum allocation size, which is wasteful.

Assigning values once to empty strings is a very common occurrence in practice, and there is no good reason to apply amortized growth to cases where a string goes from SSO to non SSO, and not doing so (precise sizing) saves memory,

[philnik]

libcxx/include/string

2338

My question was more meant as "why don't we just change the growth rate for everything?". That would save us a branch here, and AFAIK there is nothing preventing us from going that route.

[ldionne]

[Github PR transition] Commandeering to abandon since this landed in https://github.com/llvm/llvm-project/pull/68807 and another one I can't seem to find.

libcxx/include/string

_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type size() const _NOEXCEPT
         {return __is_long() ? __get_long_size() : __get_short_size();}
     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type length() const _NOEXCEPT {return size();}
 
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type max_size() const _NOEXCEPT {
     size_type __m = __alloc_traits::max_size(__alloc());
     if (__m <= std::numeric_limits<size_type>::max() / 2) {
       return __m - __alignment;
     } else {
       bool __uses_lsb = __endian_factor == 2;
       return __uses_lsb ? __m - __alignment : (__m / 2) - __alignment;
     }
   }
 
     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type capacity() const _NOEXCEPT {
         return (__is_long() ? __get_long_cap() : static_cast<size_type>(__min_cap)) - 1;
     }
 
#endif // _LIBCPP_STD_VER >= 20
     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
     const_pointer __get_pointer() const _NOEXCEPT
         {return __is_long() ? __get_long_pointer() : __get_short_pointer();}
 
     template <size_type __a> static
         _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
         size_type __align_it(size_type __s) _NOEXCEPT
             {return (__s + (__a-1)) & ~(__a-1);}
-    enum {__alignment = 16};
+    // Round up allocations to 8 bytes. Previous versions of std::string used a
+    // a value of 16 based on malloc() returning 16 byte aligned allocations.
+    // The motivation likely being that the requested size is as close as is
+    // possible to the 'perfect fit'. However, glibc's malloc() uses 8 bytes
+    // of overhead for small allocations, which results in a usable size of
+    // `N * 16 + 8`. Rounding to 16 bytes here thus results in extra waste.
+    // Likewise, other allocators such as tcmalloc() have fine grained 8 byte
+    // alignments for various size classes, which also results in waste.
+    // Once the `size returning new` features is in the standard (P0901), we
+    // can leave all this rounding to the `allocate_at_least` function.
+    enum {__alignment = 8};
     static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
     size_type __recommend(size_type __s) _NOEXCEPT
     {
         if (__s < __min_cap) {
             if (__libcpp_is_constant_evaluated())
                 return static_cast<size_type>(__min_cap);
             else
                 return static_cast<size_type>(__min_cap) - 1;

 template <class _CharT, class _Traits, class _Allocator>
 _LIBCPP_CONSTEXPR_SINCE_CXX20
 void
 basic_string<_CharT, _Traits, _Allocator>::__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)
 {
     size_type __ms = max_size();
-    if (__delta_cap > __ms - __old_cap - 1)
+    if (__delta_cap > __ms - __old_cap)
         __throw_length_error();
-    pointer __old_p = __get_pointer();
-    size_type __cap = __old_cap < __ms / 2 - __alignment ?
-                          __recommend(std::max(__old_cap + __delta_cap, 2 * __old_cap)) :
-                          __ms - 1;
+    pointer __old_p;
+    size_type __cap;
+    if (__is_long()) {
+        __old_p = __get_long_pointer();
+        __cap   = __old_cap < __ms / 2 - __alignment
+                    ? __recommend(std::max(__old_cap + __delta_cap, 2 * __old_cap))
+                    : __ms - 1;
+    } else {
+        // The current string is inlined (SSO). In this case we do not want to
+        // double the capacity for amortized growth as that can be wasteful.
+        // Consider the following code:
+        //   std::string s("");
+        //   s = "This is a string of 33 characters";
+        // Doubling the capacity here (to guarantee amortized growth) results in
+        // a min cap of 44, which including terminating zero rounds to 48 bytes.
+        // Allocating 48 bytes in standard glibc malloc results in an allocation
+        // of 64 bytes including 8 bytes overhead: glibc malloc (ptmalloc) small
+        // allocations align on 16 bytes with 8 bytes overhead. The effective
+        // size then being N * 16 + 8.
+        // If we had allocated the exact size required, we come to 34 bytes
+        // which rounds to 40 bytes, which in glibc results in an allocation of
+        // 48 including overhead. Shorter: for all string lengths 23 - 39, we
+        // would allocate 16 bytes more than required, which adds up, especially
+        // if we consider that strings are predominantly short.
+        // We only need to guarantee amortized growth on continuous growth, so
+        // we can simply request the exact size here, and only apply the minimum
+        // doubling on subsequent growth on 'long' string values.
+        __old_p = __get_short_pointer();
+        __cap   = __recommend(__old_cap + __delta_cap);
+    }
     auto __allocation = std::__allocate_at_least(__alloc(), __cap + 1);
     pointer __p = __allocation.ptr;
     __begin_lifetime(__p, __allocation.count);
     if (__n_copy != 0)
         traits_type::copy(std::__to_address(__p),
                           std::__to_address(__old_p), __n_copy);
     if (__n_add != 0)
         traits_type::copy(std::__to_address(__p) + __n_copy, __p_new_stuff, __n_add);

 #endif
     _LIBCPP_DEPRECATED_("use __grow_by_without_replace")
 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)
         __throw_length_error();
-    pointer __old_p = __get_pointer();
-    size_type __cap = __old_cap < __ms / 2 - __alignment ?
-                          __recommend(std::max(__old_cap + __delta_cap, 2 * __old_cap)) :
-                          __ms - 1;
+    pointer __old_p;
+    size_type __cap;
+    if (__is_long()) {
+        __old_p = __get_long_pointer();
+        __cap   = __old_cap < __ms / 2 - __alignment
+                    ? __recommend(std::max(__old_cap + __delta_cap, 2 * __old_cap))
+                    : __ms - 1;
+    } else {
+        // The current string is inlined (SSO). In this case we do not want to
+        // double the capacity for amortized growth as that can be wasteful.
+        // See the comments in `__grow_by_and_replace` for more information.
+        __old_p = __get_short_pointer();
+        __cap   = __recommend(__old_cap + __delta_cap);
+    }
     auto __allocation = std::__allocate_at_least(__alloc(), __cap + 1);
     pointer __p = __allocation.ptr;
     __begin_lifetime(__p, __allocation.count);
     if (__n_copy != 0)
         traits_type::copy(std::__to_address(__p),
                           std::__to_address(__old_p), __n_copy);
     size_type __sec_cp_sz = __old_sz - __n_del - __n_copy;
     if (__sec_cp_sz != 0)

libcxx/test/libcxx/strings/basic.string/string.capacity/max_size.pass.cpp

 
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <string>
 
 #include "test_macros.h"
 
-// alignment of the string heap buffer is hardcoded to 16
-static const std::size_t alignment = 16;
+// alignment of the string heap buffer is hard coded to 8.
+static const std::size_t alignment = 8;
 
 template <class = int>
 TEST_CONSTEXPR_CXX20 void full_size() {
   std::string str;
   assert(str.max_size() == std::numeric_limits<std::size_t>::max() - alignment);
 
 #ifndef TEST_HAS_NO_CHAR8_T
   std::u8string u8str;