From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2181) id B0F25384BC3A; Thu, 7 Jul 2022 23:32:39 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B0F25384BC3A MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Jonathan Wakely To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org Subject: [gcc r11-10123] libstdc++: Replace try-catch in std::list::merge to avoid O(N) size X-Act-Checkin: gcc X-Git-Author: Jonathan Wakely X-Git-Refname: refs/heads/releases/gcc-11 X-Git-Oldrev: 43d10cce34281e420fa6bdeb9765e83ba79b1aad X-Git-Newrev: 7189d425b3dd84395a3d9573eb0ee5cd8f0fcc6f Message-Id: <20220707233239.B0F25384BC3A@sourceware.org> Date: Thu, 7 Jul 2022 23:32:39 +0000 (GMT) X-BeenThere: libstdc++-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 07 Jul 2022 23:32:39 -0000 https://gcc.gnu.org/g:7189d425b3dd84395a3d9573eb0ee5cd8f0fcc6f commit r11-10123-g7189d425b3dd84395a3d9573eb0ee5cd8f0fcc6f Author: Jonathan Wakely Date: Wed Sep 29 20:46:55 2021 +0100 libstdc++: Replace try-catch in std::list::merge to avoid O(N) size The current std::list::merge code calls size() before starting to merge any elements, so that the _M_size members can be updated after the merge finishes. The work is done in a try-block so that the sizes can still be updated in an exception handler if any element comparison throws. The _M_size members only exist for the cxx11 ABI, so the initial call to size() and the try-catch are only needed for that ABI. For the old ABI the size() call performs an O(N) list traversal to get a value that isn't even used, and catching exceptions just to rethrow them isn't needed either. This refactors the merge functions to remove the try-catch block and use an RAII type instead. For the cxx11 ABI that type's destructor updates the list sizes, and for the old ABI it's a no-op. libstdc++-v3/ChangeLog: * include/bits/list.tcc (list::merge): Remove call to size() and try-catch block. Use _Finalize_merge instead. * include/bits/stl_list.h (list::_Finalize_merge): New scope guard type to update _M_size members after a merge. (cherry picked from commit b8d42cfa84fb31e592411e6cea41bdde980c51d7) Diff: --- libstdc++-v3/include/bits/list.tcc | 73 ++++++++++++++---------------------- libstdc++-v3/include/bits/stl_list.h | 35 +++++++++++++++++ 2 files changed, 64 insertions(+), 44 deletions(-) diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc index 0ce4c47a90e..62b0ba1063a 100644 --- a/libstdc++-v3/include/bits/list.tcc +++ b/libstdc++-v3/include/bits/list.tcc @@ -416,29 +416,22 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER iterator __last1 = end(); iterator __first2 = __x.begin(); iterator __last2 = __x.end(); - const size_t __orig_size = __x.size(); - __try { - while (__first1 != __last1 && __first2 != __last2) - if (*__first2 < *__first1) - { - iterator __next = __first2; - _M_transfer(__first1, __first2, ++__next); - __first2 = __next; - } - else - ++__first1; - if (__first2 != __last2) - _M_transfer(__last1, __first2, __last2); - this->_M_inc_size(__x._M_get_size()); - __x._M_set_size(0); - } - __catch(...) + const _Finalize_merge __fin(*this, __x, __first2); + + while (__first1 != __last1 && __first2 != __last2) + if (*__first2 < *__first1) + { + iterator __next = __first2; + _M_transfer(__first1, __first2, ++__next); + __first2 = __next; + } + else + ++__first1; + if (__first2 != __last2) { - const size_t __dist = std::distance(__first2, __last2); - this->_M_inc_size(__orig_size - __dist); - __x._M_set_size(__dist); - __throw_exception_again; + _M_transfer(__last1, __first2, __last2); + __first2 = __last2; } } } @@ -463,30 +456,22 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER iterator __last1 = end(); iterator __first2 = __x.begin(); iterator __last2 = __x.end(); - const size_t __orig_size = __x.size(); - __try - { - while (__first1 != __last1 && __first2 != __last2) - if (__comp(*__first2, *__first1)) - { - iterator __next = __first2; - _M_transfer(__first1, __first2, ++__next); - __first2 = __next; - } - else - ++__first1; - if (__first2 != __last2) - _M_transfer(__last1, __first2, __last2); - - this->_M_inc_size(__x._M_get_size()); - __x._M_set_size(0); - } - __catch(...) + + const _Finalize_merge __fin(*this, __x, __first2); + + while (__first1 != __last1 && __first2 != __last2) + if (__comp(*__first2, *__first1)) + { + iterator __next = __first2; + _M_transfer(__first1, __first2, ++__next); + __first2 = __next; + } + else + ++__first1; + if (__first2 != __last2) { - const size_t __dist = std::distance(__first2, __last2); - this->_M_inc_size(__orig_size - __dist); - __x._M_set_size(__dist); - __throw_exception_again; + _M_transfer(__last1, __first2, __last2); + __first2 = __last2; } } } diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h index dbe05a9834b..2c70adf2b93 100644 --- a/libstdc++-v3/include/bits/stl_list.h +++ b/libstdc++-v3/include/bits/stl_list.h @@ -1,6 +1,7 @@ // List implementation -*- C++ -*- // Copyright (C) 2001-2021 Free Software Foundation, Inc. +// Copyright The GNU Toolchain Authors. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the @@ -1966,6 +1967,40 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 __false_type{}); } #endif + +#if _GLIBCXX_USE_CXX11_ABI + // Update _M_size members after merging (some of) __src into __dest. + struct _Finalize_merge + { + explicit + _Finalize_merge(list& __dest, list& __src, const iterator& __src_next) + : _M_dest(__dest), _M_src(__src), _M_next(__src_next) + { } + + ~_Finalize_merge() + { + // For the common case, _M_next == _M_sec.end() and the std::distance + // call is fast. But if any *iter1 < *iter2 comparison throws then we + // have to count how many elements remain in _M_src. + const size_t __num_unmerged = std::distance(_M_next, _M_src.end()); + const size_t __orig_size = _M_src._M_get_size(); + _M_dest._M_inc_size(__orig_size - __num_unmerged); + _M_src._M_set_size(__num_unmerged); + } + + list& _M_dest; + list& _M_src; + const iterator& _M_next; + +#if __cplusplus >= 201103L + _Finalize_merge(const _Finalize_merge&) = delete; +#endif + }; +#else + struct _Finalize_merge + { explicit _Finalize_merge(list&, list&, const iterator&) { } }; +#endif + }; #if __cpp_deduction_guides >= 201606