From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTP id 402D83857803 for ; Fri, 1 Oct 2021 14:04:49 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 402D83857803 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-74-gdUGH-47NN2iA_E93ClztA-1; Fri, 01 Oct 2021 10:04:45 -0400 X-MC-Unique: gdUGH-47NN2iA_E93ClztA-1 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id D228691277; Fri, 1 Oct 2021 14:04:44 +0000 (UTC) Received: from localhost (unknown [10.33.36.47]) by smtp.corp.redhat.com (Postfix) with ESMTP id 81BF518B5E; Fri, 1 Oct 2021 14:04:44 +0000 (UTC) Date: Fri, 1 Oct 2021 15:04:43 +0100 From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [committed] libstdc++: Replace try-catch in std::list::merge to avoid O(N) size Message-ID: MIME-Version: 1.0 X-Clacks-Overhead: GNU Terry Pratchett X-Scanned-By: MIMEDefang 2.79 on 10.5.11.11 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: multipart/mixed; boundary="hV1CIWdgkhmLgtPz" Content-Disposition: inline X-Spam-Status: No, score=-13.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=unavailable autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 01 Oct 2021 14:04:50 -0000 --hV1CIWdgkhmLgtPz Content-Type: text/plain; charset=us-ascii Content-Disposition: inline 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. Tested x86_64-linux. Committed to trunk. --hV1CIWdgkhmLgtPz Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="patch.txt" commit b8d42cfa84fb31e592411e6cea41bdde980c51d7 Author: Jonathan Wakely Date: Wed Sep 29 20:46:55 2021 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. 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 9ae640ee692..e11603c0157 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 @@ -1992,6 +1993,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 --hV1CIWdgkhmLgtPz--