[gcc r11-10123] libstdc++: Replace try-catch in std::list::merge to avoid O(N) size

[gcc r11-10123] libstdc++: Replace try-catch in std::list::merge to avoid O(N) size

[Jonathan Wakely]

https://gcc.gnu.org/g:7189d425b3dd84395a3d9573eb0ee5cd8f0fcc6f

commit r11-10123-g7189d425b3dd84395a3d9573eb0ee5cd8f0fcc6f
Author: Jonathan Wakely <jwakely@redhat.com>
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