Low-hanging fruit optimization in string::__move_assign().

[tvanslyke]

Summary

shrink_to_fit() ends up doing a lot work to get information that we already know since we just called clear(). This change seems concise enough to be worth the couple extra lines and my benchmarks show that it is indeed a pretty decent win. It looks like the same thing is going on twice in __copy_assign_alloc(), but I didn't want to go overboard since this is my first contribution to llvm/libc++. Go easy on me!

[tvanslyke]

I went ahead and just pulled it out to a small inline member function and added it to __copy_assign_alloc(). Removed some other redundancies.

[vsk]

Adding some folks who may be interested.

[mclow.lists]

Can you share your benchmark results, please?

[tvanslyke]

Here are the results:

Comparing old-copymove.json to new-copymove.json
Benchmark                        Time             CPU      Time Old      Time New       CPU Old       CPU New
-------------------------------------------------------------------------------------------------------------
BM_string_move_SSO            -0.5833         -0.5833            12             5            12             5
BM_string_copy_SSO            +0.0000         +0.0000            23            23            23            23
BM_string_move_no_SSO         -0.6250         -0.6250             8             3             8             3
BM_string_copy_no_SSO         +0.0000         +0.0000            11            11            11            11
BM_string_stable_sort         -0.0779         -0.0779       2772114       2556118       2772031       2556036

I put the benchmark on pastebin because it's a tad too long to paste here IMO: https://pastebin.com/mk1JXQme

[tvanslyke]

I'll add that the reason I felt compelled to submit this change was because perf was saying most of my program, that only ever moved strings, was spending a majority of it's time in string::reserve() calls. If for no other reason, I think it's confusing for people to see string::reserve getting called when all they wanted was a move assignment.

[lebedev.ri]

In D41976#975659, @tvanslyke wrote:

Here are the results:

Comparing old-copymove.json to new-copymove.json
Benchmark                        Time             CPU      Time Old      Time New       CPU Old       CPU New
-------------------------------------------------------------------------------------------------------------
BM_string_move_SSO            -0.5833         -0.5833            12             5            12             5
BM_string_copy_SSO            +0.0000         +0.0000            23            23            23            23
BM_string_move_no_SSO         -0.6250         -0.6250             8             3             8             3
BM_string_copy_no_SSO         +0.0000         +0.0000            11            11            11            11
BM_string_stable_sort         -0.0779         -0.0779       2772114       2556118       2772031       2556036

I put the benchmark on pastebin because it's a tad too long to paste here IMO: https://pastebin.com/mk1JXQme

Perhaps it should be added to the already-existing benchmarks/string.bench.cpp?
Not sure whether those are being used in test-suite/LNT.

[tvanslyke]

I can adapt it to the style guide if it is decided that it should be added.

[mclow.lists]

I'm a bit leery of this patch. Not because of what it's trying to do, but rather, the introduction of a method __clear_and_shrink that leaves the string in an invalid state. For all the uses that you put it to, I don't think that's a problem (though I'm still working through the failure possibilities), but I can see other people attempting to use this method - and not realizing that you have to "put the string back together" afterwards.

Maybe I'm just being paranoid.

[tvanslyke]

I think the only thing we need is a call to __set_long_cap(0) in the body of the if() to make the string be in a valid state, but if you follow the logic for a call to reserve(0) (after having called clear()) it doesn't even end up doing that (unless I'm missing something). I definitely have no problem adding the __set_long_cap(0) call to the diff.

[tvanslyke]

Just to elaborate, in reserve(0) after the deallocation there's a check if (__now_long) which takes the else branch and only ends up calling __set_short_size(__sz); // __sz = 0 here. So even without this diff the only thing reserve(0) does after deallocating is set the short size to zero, but it already is zero (because of the call to clear()).

[tvanslyke]

Sorry if I'm spamming too much. Just to be clear, I agree completely with your sentiment but I'm pretty sure that __clear_and_shrink() has exactly the same effects as clear(); shrink_to_fit();. Maybe reserve(); should should be unconditionally calling __set_long_cap(0); immediately after deallocating? I could be missing something obvious though.

[tvanslyke]

Implemented changes to ensure string state is valid after calling __clear_and_shrink(). Benchmark results are identical.

[mclow.lists]

This looks good to me.
Please add a test in test/libcxx/strings/string.modifiers and commit.

Something like this:

#include <string>
#include <cassert>

int main () {
    std::string l = "This makes this a long string, I hope; just rambling on and on...";
    std::string s = "short";
    assert(l.__invariants());
    assert(s.__invariants());

    s.__clear_and_shrink();
    assert(s.__invariants());
    assert(s.size() == 0);

    l.__clear_and_shrink();
    assert(l.__invariants());
    assert(l.size() == 0);
}

[tvanslyke]

Since __clear_and_shrink() is private the test covers copy and move assignment. I also ran the libcxx/strings/basic.string and std/strings tests with a hard-coded assert(__invariants()); at the end of __clear_and_shrink() and saw no failures.

I don't have commit access myself so I've added the test to the diff.

[mclow.lists]

In D41976#982978, @tvanslyke wrote:

I don't have commit access myself so I've added the test to the diff.

I'll commit it then.

[mclow.lists]

Since __clear_and_shrink() is private

There's no reason it has to be private.
People aren't supposed to call anything with a reserved name.

[tvanslyke]

Moved __clear_and_shrink() to live with the other public dunder methods and adapted the associated test accordingly.

[tvanslyke]

Hello. I would just like to follow up on the status of this patch. Is there anything else that is needed from me? I just want to make sure that nobody is waiting on me for anything; I'm still not 100% familiar with the process. Thanks in advance.

[vsk]

@mclow.lists is this still fine to commit? I can land it and watch the bots, if you'd like.

[mclow.lists]

In D41976#1031674, @vsk wrote:

@mclow.lists is this still fine to commit? I can land it and watch the bots, if you'd like.

Sure. Please do so.

[vsk]

Thanks @tvanslyke and @mclow.lists, landed as r327064.

[mclow.lists]

Howard just pointed out to me that __clear_and_shrink should be noexcept - otherwise we get the generation of an exception table and a call to terminate in string's move assignment operator. Fixed in revision 333435.

include/string

#if _LIBCPP_STD_VER > 17
 
     _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
     bool ends_with(const value_type* __s) const _NOEXCEPT
     { return ends_with(__self_view(__s)); }
 #endif
 
     _LIBCPP_INLINE_VISIBILITY bool __invariants() const;
 
+    _LIBCPP_INLINE_VISIBILITY void __clear_and_shrink();
+    
     _LIBCPP_INLINE_VISIBILITY
     bool __is_long() const _NOEXCEPT
         {return bool(__r_.first().__s.__size_ & __short_mask);}
 
 #if _LIBCPP_DEBUG_LEVEL >= 2
 
     bool __dereferenceable(const const_iterator* __i) const;
     bool __decrementable(const const_iterator* __i) const;
#endif  // _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
     void __copy_assign_alloc(const basic_string& __str, true_type)
         {
             if (__alloc() == __str.__alloc())
                 __alloc() = __str.__alloc();
             else
             {
                 if (!__str.__is_long())
                 {
-                    clear();
-                    shrink_to_fit();
+                    __clear_and_shrink();
                     __alloc() = __str.__alloc();
                 }
                 else
                 {
                     allocator_type __a = __str.__alloc();
                     pointer __p = __alloc_traits::allocate(__a, __str.__get_long_cap());
-                    clear();
-                    shrink_to_fit();
+                    __clear_and_shrink();
                     __alloc() = _VSTD::move(__a);
                     __set_long_pointer(__p);
                     __set_long_cap(__str.__get_long_cap());
                     __set_long_size(__str.size());
                 }
             }
         }
 

 void
 basic_string<_CharT, _Traits, _Allocator>::__move_assign(basic_string& __str, true_type)
 #if _LIBCPP_STD_VER > 14
     _NOEXCEPT
 #else
     _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
 #endif
 {
-    clear();
-    shrink_to_fit();
+    __clear_and_shrink();
     __r_.first() = __str.__r_.first();
     __move_assign_alloc(__str);
     __str.__zero();
 }
 
 template <class _CharT, class _Traits, class _Allocator>
 inline _LIBCPP_INLINE_VISIBILITY
 basic_string<_CharT, _Traits, _Allocator>&
if (capacity() < __min_cap - 1)
         return false;
     if (data() == 0)
         return false;
     if (data()[size()] != value_type(0))
         return false;
     return true;
 }
 
+// __clear_and_shrink
+
+template<class _CharT, class _Traits, class _Allocator>
+inline _LIBCPP_INLINE_VISIBILITY
+void 
+basic_string<_CharT, _Traits, _Allocator>::__clear_and_shrink()
+{
+    clear();
+    if(__is_long())
+    {
+        __alloc_traits::deallocate(__alloc(), __get_long_pointer(), capacity() + 1);
+        __set_long_cap(0);
+        __set_short_size(0);
+    }
+} 
+
 // operator==
 
 template<class _CharT, class _Traits, class _Allocator>
 inline _LIBCPP_INLINE_VISIBILITY
 bool
 operator==(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
            const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
 {

test/libcxx/strings/basic.string/string.modifiers/clear_and_shrink_db1.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <string>
+
+// Call __clear_and_shrink() and ensure string invariants hold
+
+#if _LIBCPP_DEBUG >= 1
+
+#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0))
+
+#include <string>
+#include <cassert>
+
+int main()
+{
+    std::string l = "Long string so that allocation definitely, for sure, absolutely happens. Probably.";
+    std::string s = "short";
+
+    assert(l.__invariants());
+    assert(s.__invariants());
+    
+    s.__clear_and_shrink();
+    assert(s.__invariants());
+    assert(s.size() == 0);
+
+    { 
+    std::string::size_type cap = l.capacity();
+    l.__clear_and_shrink();
+    assert(l.__invariants());
+    assert(l.size() == 0);
+    assert(l.capacity() < cap);
+    }
+}
+
+#else
+
+int main()
+{
+}
+
+#endif