From: Jonathan Wakely <jwakely@redhat.com>
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
Date: Fri, 1 Oct 2021 15:04:43 +0100 [thread overview]
Message-ID: <YVcVe/ZPT83YJ8eX@redhat.com> (raw)
[-- Attachment #1: Type: text/plain, Size: 1072 bytes --]
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.
[-- Attachment #2: patch.txt --]
[-- Type: text/plain, Size: 5712 bytes --]
commit b8d42cfa84fb31e592411e6cea41bdde980c51d7
Author: Jonathan Wakely <jwakely@redhat.com>
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
reply other threads:[~2021-10-01 14:04 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=YVcVe/ZPT83YJ8eX@redhat.com \
--to=jwakely@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=libstdc++@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).