[PATCH] D41976: Low-hanging fruit optimization in string::__move_assign().
tvanslyke added a comment. 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. https://reviews.llvm.org/D41976 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D41976: Low-hanging fruit optimization in string::__move_assign().
tvanslyke created this revision.
tvanslyke added a reviewer: howard.hinnant.
Herald added a subscriber: cfe-commits.
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!
Repository:
rCXX libc++
https://reviews.llvm.org/D41976
Files:
string
Index: string
===
--- string
+++ string
@@ -2103,7 +2103,15 @@
#endif
{
clear();
-shrink_to_fit();
+
+size_type __cap = capacity();
+// check if we need to deallocate anything
+if(__recommend(0) != __cap)
+{
+pointer __old_data = __get_long_pointer();
+__alloc_traits::deallocate(__alloc(), __old_data, __cap + 1);
+__set_short_size(0);
+}
__r_.first() = __str.__r_.first();
__move_assign_alloc(__str);
__str.__zero();
Index: string
===
--- string
+++ string
@@ -2103,7 +2103,15 @@
#endif
{
clear();
-shrink_to_fit();
+
+size_type __cap = capacity();
+// check if we need to deallocate anything
+if(__recommend(0) != __cap)
+{
+pointer __old_data = __get_long_pointer();
+__alloc_traits::deallocate(__alloc(), __old_data, __cap + 1);
+__set_short_size(0);
+}
__r_.first() = __str.__r_.first();
__move_assign_alloc(__str);
__str.__zero();
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D41976: Low-hanging fruit optimization in string::__move_assign().
tvanslyke updated this revision to Diff 129685.
tvanslyke added a comment.
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.
https://reviews.llvm.org/D41976
Files:
string
Index: string
===
--- string
+++ string
@@ -1407,24 +1407,30 @@
__alloc_traits::propagate_on_container_copy_assignment::value>());}
_LIBCPP_INLINE_VISIBILITY
+void __clear_and_shrink()
+{
+clear();
+if(__is_long())
+__alloc_traits::deallocate(__alloc(), __get_long_pointer(),
capacity() + 1);
+}
+
+_LIBCPP_INLINE_VISIBILITY
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());
@@ -2102,8 +2108,7 @@
_NOEXCEPT_(is_nothrow_move_assignable::value)
#endif
{
-clear();
-shrink_to_fit();
+__clear_and_shrink();
__r_.first() = __str.__r_.first();
__move_assign_alloc(__str);
__str.__zero();
Index: string
===
--- string
+++ string
@@ -1407,24 +1407,30 @@
__alloc_traits::propagate_on_container_copy_assignment::value>());}
_LIBCPP_INLINE_VISIBILITY
+void __clear_and_shrink()
+{
+clear();
+if(__is_long())
+__alloc_traits::deallocate(__alloc(), __get_long_pointer(), capacity() + 1);
+}
+
+_LIBCPP_INLINE_VISIBILITY
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());
@@ -2102,8 +2108,7 @@
_NOEXCEPT_(is_nothrow_move_assignable::value)
#endif
{
-clear();
-shrink_to_fit();
+__clear_and_shrink();
__r_.first() = __str.__r_.first();
__move_assign_alloc(__str);
__str.__zero();
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D41976: Low-hanging fruit optimization in string::__move_assign().
tvanslyke added a comment. Here are the results: Comparing old-copymove.json to new-copymove.json BenchmarkTime CPU Time Old Time New CPU Old CPU New - BM_string_move_SSO-0.5833 -0.583312 512 5 BM_string_copy_SSO+0. +0.23 232323 BM_string_move_no_SSO -0.6250 -0.6250 8 3 8 3 BM_string_copy_no_SSO +0. +0.11 111111 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 https://reviews.llvm.org/D41976 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D41976: Low-hanging fruit optimization in string::__move_assign().
tvanslyke added a comment. 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. https://reviews.llvm.org/D41976 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D41976: Low-hanging fruit optimization in string::__move_assign().
tvanslyke added a comment. I can adapt it to the style guide if it is decided that it should be added. https://reviews.llvm.org/D41976 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D41976: Low-hanging fruit optimization in string::__move_assign().
tvanslyke added a comment. 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. https://reviews.llvm.org/D41976 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D41976: Low-hanging fruit optimization in string::__move_assign().
tvanslyke added a comment. 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()`). https://reviews.llvm.org/D41976 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D41976: Low-hanging fruit optimization in string::__move_assign().
tvanslyke added a comment. 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(0);` should should be unconditionally calling `__set_long_cap(0);` immediately after deallocating? I could be missing something obvious though. https://reviews.llvm.org/D41976 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D41976: Low-hanging fruit optimization in string::__move_assign().
tvanslyke updated this revision to Diff 129969.
tvanslyke added a comment.
Implemented changes to ensure string state is valid after calling
`__clear_and_shrink()`. Benchmark results are identical.
https://reviews.llvm.org/D41976
Files:
string
Index: string
===
--- string
+++ string
@@ -1407,24 +1407,34 @@
__alloc_traits::propagate_on_container_copy_assignment::value>());}
_LIBCPP_INLINE_VISIBILITY
+void __clear_and_shrink()
+{
+clear();
+if(__is_long())
+{
+__alloc_traits::deallocate(__alloc(), __get_long_pointer(),
capacity() + 1);
+__set_long_cap(0);
+__set_short_size(0);
+}
+}
+
+_LIBCPP_INLINE_VISIBILITY
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());
@@ -2102,8 +2112,7 @@
_NOEXCEPT_(is_nothrow_move_assignable::value)
#endif
{
-clear();
-shrink_to_fit();
+__clear_and_shrink();
__r_.first() = __str.__r_.first();
__move_assign_alloc(__str);
__str.__zero();
Index: string
===
--- string
+++ string
@@ -1407,24 +1407,34 @@
__alloc_traits::propagate_on_container_copy_assignment::value>());}
_LIBCPP_INLINE_VISIBILITY
+void __clear_and_shrink()
+{
+clear();
+if(__is_long())
+{
+__alloc_traits::deallocate(__alloc(), __get_long_pointer(), capacity() + 1);
+__set_long_cap(0);
+__set_short_size(0);
+}
+}
+
+_LIBCPP_INLINE_VISIBILITY
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());
@@ -2102,8 +2112,7 @@
_NOEXCEPT_(is_nothrow_move_assignable::value)
#endif
{
-clear();
-shrink_to_fit();
+__clear_and_shrink();
__r_.first() = __str.__r_.first();
__move_assign_alloc(__str);
__str.__zero();
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D41976: Low-hanging fruit optimization in string::__move_assign().
tvanslyke updated this revision to Diff 130775.
tvanslyke added a comment.
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.
https://reviews.llvm.org/D41976
Files:
include/string
test/libcxx/strings/basic.string/string.modifiers/copy_assign_move_assign_db1.pass.cpp
Index: test/libcxx/strings/basic.string/string.modifiers/copy_assign_move_assign_db1.pass.cpp
===
--- test/libcxx/strings/basic.string/string.modifiers/copy_assign_move_assign_db1.pass.cpp
+++ test/libcxx/strings/basic.string/string.modifiers/copy_assign_move_assign_db1.pass.cpp
@@ -0,0 +1,66 @@
+//===--===//
+//
+// 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.
+//
+//===--===//
+
+//
+
+// 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
+#include
+
+int main()
+{
+std::string l = "Long string so that allocation definitely, for sure, absolutely happens. Probably.";
+std::string l2 = l;
+std::string s = "short";
+std::string s2 = s;
+std::string empty = "";
+
+assert(l.__invariants());
+assert(s.__invariants());
+assert(l2.__invariants());
+assert(s2.__invariants());
+assert(empty.__invariants());
+
+
+s2 = empty;
+assert(s2.__invariants());
+assert(s2.size() == 0);
+assert(empty.__invariants());
+s2 = empty;
+assert(s2.__invariants());
+assert(s2.size() == 0);
+assert(empty.__invariants());
+
+{
+std::string::size_type cap = l.capacity();
+l = empty;
+assert(l.__invariants());
+assert(l.size() == 0);
+assert(empty.__invariants());
+cap = l2.capacity();
+l2 = std::move(empty);
+assert(l2.capacity() < cap);
+assert(l2.__invariants());
+assert(l2.size() == 0);
+assert(empty.__invariants());
+}
+}
+
+#else
+
+int main()
+{
+}
+
+#endif
Index: include/string
===
--- include/string
+++ include/string
@@ -1407,24 +1407,34 @@
__alloc_traits::propagate_on_container_copy_assignment::value>());}
_LIBCPP_INLINE_VISIBILITY
+void __clear_and_shrink()
+{
+clear();
+if(__is_long())
+{
+__alloc_traits::deallocate(__alloc(), __get_long_pointer(), capacity() + 1);
+__set_long_cap(0);
+__set_short_size(0);
+}
+}
+
+_LIBCPP_INLINE_VISIBILITY
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());
@@ -2102,8 +2112,7 @@
_NOEXCEPT_(is_nothrow_move_assignable::value)
#endif
{
-clear();
-shrink_to_fit();
+__clear_and_shrink();
__r_.first() = __str.__r_.first();
__move_assign_alloc(__str);
__str.__zero();
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D41976: Low-hanging fruit optimization in string::__move_assign().
tvanslyke updated this revision to Diff 130819.
tvanslyke added a comment.
Moved `__clear_and_shrink()` to live with the other public dunder methods and
adapted the associated test accordingly.
https://reviews.llvm.org/D41976
Files:
include/string
test/libcxx/strings/basic.string/string.modifiers/clear_and_shrink_db1.pass.cpp
Index: test/libcxx/strings/basic.string/string.modifiers/clear_and_shrink_db1.pass.cpp
===
--- test/libcxx/strings/basic.string/string.modifiers/clear_and_shrink_db1.pass.cpp
+++ test/libcxx/strings/basic.string/string.modifiers/clear_and_shrink_db1.pass.cpp
@@ -0,0 +1,48 @@
+//===--===//
+//
+// 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.
+//
+//===--===//
+
+//
+
+// 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
+#include
+
+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
Index: include/string
===
--- include/string
+++ include/string
@@ -1250,6 +1250,8 @@
_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);}
@@ -1415,16 +1417,14 @@
{
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());
@@ -2102,8 +2102,7 @@
_NOEXCEPT_(is_nothrow_move_assignable::value)
#endif
{
-clear();
-shrink_to_fit();
+__clear_and_shrink();
__r_.first() = __str.__r_.first();
__move_assign_alloc(__str);
__str.__zero();
@@ -3556,6 +3555,22 @@
return true;
}
+// __clear_and_shrink
+
+template
+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
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
