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

2330

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

2328

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

2328

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

2328

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

#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};
+    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;

 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)
         __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 {
+        // On first allocation SSO -> long, do not apply a minimum doubling
+        // of capacity/ This results in a minimum allocation size of 48 and we
+        // only need to guarantee amortized growth on subsequent growth.
+        __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 {
+        // On first allocation SSO -> long, do not apply a minimum doubling
+        // of capacity/ This results in a minimum allocation size of 48 and we
+        // only need to guarantee amortized growth on subsequent growth.
+        __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

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // <string>
 
 // This test ensures that the correct max_size() is returned depending on the platform.
 
 #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;