Limit includes in hashtable_policy.h

Message ID 974461f2-a3ff-1623-9bae-786d188a8630@gmail.com
State New
Headers show
Series
  • Limit includes in hashtable_policy.h
Related show

Commit Message

François Dumont Feb. 27, 2020, 6:30 p.m.
When I use std::is_permutation in hashtable_policy.h I included 
stl_algo.h which is a large header. No other header in include/bits does 
this, I would prefer not being the first to do such a thing.

As it is a recent change I prefer to submit this patch now.

Git commit message:

     libstdc++ Hashtable: Move std::is_permutation to limit includes

     * include/bits/stl_algo.h (__find_if, __count_if, 
std::is_permutation): Move...
     * include/bits/stl_algobase.h: ...here.
     * include/bits/hashtable_policy.h: Remove <bits/stl_algo.h> include.

testsuite/23_containers/unordered* tested under Linux x86_64, I'll run 
full before any commit.

Ok to commit now ?

Ok to commit once back in stage 1 ?

François

Comments

Jonathan Wakely Feb. 28, 2020, 2:09 p.m. | #1
On 27/02/20 19:30 +0100, François Dumont wrote:
>When I use std::is_permutation in hashtable_policy.h I included 

>stl_algo.h which is a large header. No other header in include/bits 

>does this, I would prefer not being the first to do such a thing.

>

>As it is a recent change I prefer to submit this patch now.

>

>Git commit message:

>

>    libstdc++ Hashtable: Move std::is_permutation to limit includes

>

>    * include/bits/stl_algo.h (__find_if, __count_if, 

>std::is_permutation): Move...

>    * include/bits/stl_algobase.h: ...here.

>    * include/bits/hashtable_policy.h: Remove <bits/stl_algo.h> include.

>

>testsuite/23_containers/unordered* tested under Linux x86_64, I'll run 

>full before any commit.

>

>Ok to commit now ?

>

>Ok to commit once back in stage 1 ?


I was already thinking of doing something like this in stage 1. But
you're right that this is a recent regression on master. Before
<bits/stl_algo.h> got added the preprocessed size of <unordered_map>
had got much smaller due to <array> no longer including <stdexcept>.
But including <bits/stl_algo.h> made it almost the same size as in
gcc-9 again.

With your patch we remove 7kloc from <unordered_map> again.

OK for master now, thanks.

Patch

diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 22bc4472e32..ef120134914 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -33,8 +33,7 @@ 
 
 #include <tuple>		// for std::tuple, std::forward_as_tuple
 #include <limits>		// for std::numeric_limits
-#include <bits/stl_algobase.h>	// for std::min.
-#include <bits/stl_algo.h>	// for std::is_permutation.
+#include <bits/stl_algobase.h>	// for std::min, std::is_permutation.
 
 namespace std _GLIBCXX_VISIBILITY(default)
 {
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 6503d1518d3..932ece55529 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -96,76 +96,6 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	std::iter_swap(__result, __b);
     }
 
-  /// This is an overload used by find algos for the Input Iterator case.
-  template<typename _InputIterator, typename _Predicate>
-    _GLIBCXX20_CONSTEXPR
-    inline _InputIterator
-    __find_if(_InputIterator __first, _InputIterator __last,
-	      _Predicate __pred, input_iterator_tag)
-    {
-      while (__first != __last && !__pred(__first))
-	++__first;
-      return __first;
-    }
-
-  /// This is an overload used by find algos for the RAI case.
-  template<typename _RandomAccessIterator, typename _Predicate>
-    _GLIBCXX20_CONSTEXPR
-    _RandomAccessIterator
-    __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
-	      _Predicate __pred, random_access_iterator_tag)
-    {
-      typename iterator_traits<_RandomAccessIterator>::difference_type
-	__trip_count = (__last - __first) >> 2;
-
-      for (; __trip_count > 0; --__trip_count)
-	{
-	  if (__pred(__first))
-	    return __first;
-	  ++__first;
-
-	  if (__pred(__first))
-	    return __first;
-	  ++__first;
-
-	  if (__pred(__first))
-	    return __first;
-	  ++__first;
-
-	  if (__pred(__first))
-	    return __first;
-	  ++__first;
-	}
-
-      switch (__last - __first)
-	{
-	case 3:
-	  if (__pred(__first))
-	    return __first;
-	  ++__first;
-	case 2:
-	  if (__pred(__first))
-	    return __first;
-	  ++__first;
-	case 1:
-	  if (__pred(__first))
-	    return __first;
-	  ++__first;
-	case 0:
-	default:
-	  return __last;
-	}
-    }
-
-  template<typename _Iterator, typename _Predicate>
-    _GLIBCXX20_CONSTEXPR
-    inline _Iterator
-    __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
-    {
-      return __find_if(__first, __last, __pred,
-		       std::__iterator_category(__first));
-    }
-
   /// Provided for stable_partition to use.
   template<typename _InputIterator, typename _Predicate>
     _GLIBCXX20_CONSTEXPR
@@ -3279,18 +3209,6 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 					      __new_value);
     }
 
-  template<typename _InputIterator, typename _Predicate>
-    _GLIBCXX20_CONSTEXPR
-    typename iterator_traits<_InputIterator>::difference_type
-    __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
-    {
-      typename iterator_traits<_InputIterator>::difference_type __n = 0;
-      for (; __first != __last; ++__first)
-	if (__pred(__first))
-	  ++__n;
-      return __n;
-    }
-
 #if __cplusplus >= 201103L
   /**
    *  @brief  Determines whether the elements of a sequence are sorted.
@@ -3588,74 +3506,6 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return std::make_pair(*__p.first, *__p.second);
     }
 
-  template<typename _ForwardIterator1, typename _ForwardIterator2,
-	   typename _BinaryPredicate>
-    _GLIBCXX20_CONSTEXPR
-    bool
-    __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
-		     _ForwardIterator2 __first2, _BinaryPredicate __pred)
-    {
-      // Efficiently compare identical prefixes:  O(N) if sequences
-      // have the same elements in the same order.
-      for (; __first1 != __last1; ++__first1, (void)++__first2)
-	if (!__pred(__first1, __first2))
-	  break;
-
-      if (__first1 == __last1)
-	return true;
-
-      // Establish __last2 assuming equal ranges by iterating over the
-      // rest of the list.
-      _ForwardIterator2 __last2 = __first2;
-      std::advance(__last2, std::distance(__first1, __last1));
-      for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
-	{
-	  if (__scan != std::__find_if(__first1, __scan,
-			  __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
-	    continue; // We've seen this one before.
-	  
-	  auto __matches
-	    = std::__count_if(__first2, __last2,
-			__gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
-	  if (0 == __matches ||
-	      std::__count_if(__scan, __last1,
-			__gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
-	      != __matches)
-	    return false;
-	}
-      return true;
-    }
-
-  /**
-   *  @brief  Checks whether a permutation of the second sequence is equal
-   *          to the first sequence.
-   *  @ingroup non_mutating_algorithms
-   *  @param  __first1  Start of first range.
-   *  @param  __last1   End of first range.
-   *  @param  __first2  Start of second range.
-   *  @return true if there exists a permutation of the elements in the range
-   *          [__first2, __first2 + (__last1 - __first1)), beginning with 
-   *          ForwardIterator2 begin, such that equal(__first1, __last1, begin)
-   *          returns true; otherwise, returns false.
-  */
-  template<typename _ForwardIterator1, typename _ForwardIterator2>
-    _GLIBCXX20_CONSTEXPR
-    inline bool
-    is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
-		   _ForwardIterator2 __first2)
-    {
-      // concept requirements
-      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
-      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
-      __glibcxx_function_requires(_EqualOpConcept<
-		typename iterator_traits<_ForwardIterator1>::value_type,
-		typename iterator_traits<_ForwardIterator2>::value_type>)
-      __glibcxx_requires_valid_range(__first1, __last1);
-
-      return std::__is_permutation(__first1, __last1, __first2,
-				   __gnu_cxx::__ops::__iter_equal_to_iter());
-    }
-
   /**
    *  @brief  Checks whether a permutation of the second sequence is equal
    *          to the first sequence.
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 268569336b0..ef6277abf11 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -1904,6 +1904,159 @@  _GLIBCXX_BEGIN_NAMESPACE_ALGO
 #endif
 
 _GLIBCXX_END_NAMESPACE_ALGO
+
+  /// This is an overload used by find algos for the Input Iterator case.
+  template<typename _InputIterator, typename _Predicate>
+    _GLIBCXX20_CONSTEXPR
+    inline _InputIterator
+    __find_if(_InputIterator __first, _InputIterator __last,
+	      _Predicate __pred, input_iterator_tag)
+    {
+      while (__first != __last && !__pred(__first))
+	++__first;
+      return __first;
+    }
+
+  /// This is an overload used by find algos for the RAI case.
+  template<typename _RandomAccessIterator, typename _Predicate>
+    _GLIBCXX20_CONSTEXPR
+    _RandomAccessIterator
+    __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
+	      _Predicate __pred, random_access_iterator_tag)
+    {
+      typename iterator_traits<_RandomAccessIterator>::difference_type
+	__trip_count = (__last - __first) >> 2;
+
+      for (; __trip_count > 0; --__trip_count)
+	{
+	  if (__pred(__first))
+	    return __first;
+	  ++__first;
+
+	  if (__pred(__first))
+	    return __first;
+	  ++__first;
+
+	  if (__pred(__first))
+	    return __first;
+	  ++__first;
+
+	  if (__pred(__first))
+	    return __first;
+	  ++__first;
+	}
+
+      switch (__last - __first)
+	{
+	case 3:
+	  if (__pred(__first))
+	    return __first;
+	  ++__first;
+	case 2:
+	  if (__pred(__first))
+	    return __first;
+	  ++__first;
+	case 1:
+	  if (__pred(__first))
+	    return __first;
+	  ++__first;
+	case 0:
+	default:
+	  return __last;
+	}
+    }
+
+  template<typename _Iterator, typename _Predicate>
+    _GLIBCXX20_CONSTEXPR
+    inline _Iterator
+    __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
+    {
+      return __find_if(__first, __last, __pred,
+		       std::__iterator_category(__first));
+    }
+
+  template<typename _InputIterator, typename _Predicate>
+    _GLIBCXX20_CONSTEXPR
+    typename iterator_traits<_InputIterator>::difference_type
+    __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
+    {
+      typename iterator_traits<_InputIterator>::difference_type __n = 0;
+      for (; __first != __last; ++__first)
+	if (__pred(__first))
+	  ++__n;
+      return __n;
+    }
+
+#if __cplusplus >= 201103L
+  template<typename _ForwardIterator1, typename _ForwardIterator2,
+	   typename _BinaryPredicate>
+    _GLIBCXX20_CONSTEXPR
+    bool
+    __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
+		     _ForwardIterator2 __first2, _BinaryPredicate __pred)
+    {
+      // Efficiently compare identical prefixes:  O(N) if sequences
+      // have the same elements in the same order.
+      for (; __first1 != __last1; ++__first1, (void)++__first2)
+	if (!__pred(__first1, __first2))
+	  break;
+
+      if (__first1 == __last1)
+	return true;
+
+      // Establish __last2 assuming equal ranges by iterating over the
+      // rest of the list.
+      _ForwardIterator2 __last2 = __first2;
+      std::advance(__last2, std::distance(__first1, __last1));
+      for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
+	{
+	  if (__scan != std::__find_if(__first1, __scan,
+			  __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
+	    continue; // We've seen this one before.
+
+	  auto __matches
+	    = std::__count_if(__first2, __last2,
+			__gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
+	  if (0 == __matches ||
+	      std::__count_if(__scan, __last1,
+			__gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
+	      != __matches)
+	    return false;
+	}
+      return true;
+    }
+
+  /**
+   *  @brief  Checks whether a permutation of the second sequence is equal
+   *          to the first sequence.
+   *  @ingroup non_mutating_algorithms
+   *  @param  __first1  Start of first range.
+   *  @param  __last1   End of first range.
+   *  @param  __first2  Start of second range.
+   *  @return true if there exists a permutation of the elements in the range
+   *          [__first2, __first2 + (__last1 - __first1)), beginning with
+   *          ForwardIterator2 begin, such that equal(__first1, __last1, begin)
+   *          returns true; otherwise, returns false.
+  */
+  template<typename _ForwardIterator1, typename _ForwardIterator2>
+    _GLIBCXX20_CONSTEXPR
+    inline bool
+    is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
+		   _ForwardIterator2 __first2)
+    {
+      // concept requirements
+      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
+      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
+      __glibcxx_function_requires(_EqualOpConcept<
+		typename iterator_traits<_ForwardIterator1>::value_type,
+		typename iterator_traits<_ForwardIterator2>::value_type>)
+      __glibcxx_requires_valid_range(__first1, __last1);
+
+      return std::__is_permutation(__first1, __last1, __first2,
+				   __gnu_cxx::__ops::__iter_equal_to_iter());
+    }
+#endif // C++11
+
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace std