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.
commit b8d42cfa84fb31e592411e6cea41bdde980c51d7
Author: Jonathan Wakely <jwak...@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
