This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] Improve _Safe_iterator _M_distance_to

    Here is the patch to improve _Safe_iterator<>::_M_get_distance_to implementation.
I introduced a new _Distance_precision  __sp_sign_max_size for occasions where we can't find out the exact size of a range but still get the max size of it. Thanks to this the performance tests are much better when dealing with list iterators: 

Normal mode:
copy_backward_deque_iterators.cc    deque 2 list 5616r 5616u    0s         0mem    0pf copy_backward_deque_iterators.cc    list 2 deque 1586r 1586u    0s         0mem    0pf copy_deque_iterators.cc      deque 2 list                 5495r 5495u    0s         0mem    0pf copy_deque_iterators.cc      list 2 deque                 2400r 2400u    0s         0mem    0pf 

Debug mode:
copy_backward_deque_iterators.cc    deque 2 list 5789r 5785u    1s         0mem    0pf copy_backward_deque_iterators.cc    list 2 deque 1656r 1655u    0s         0mem    0pf copy_deque_iterators.cc      deque 2 list                 5792r 5793u    0s         0mem    0pf copy_deque_iterators.cc      list 2 deque                 2636r 2636u    0s         0mem    0pf 

Tested under Linux x86_64.

I'll commit once other patches are in.


    * include/debug/forward_list
(_Sequence_traits<__debug::forward_list<>>::_S_size): Returns __dp_sign
    distance when not empty.
    * include/debug/list
    (_Sequence_traits<__debug::list<>>::_S_size): Likewise.
    * include/debug/helper_functions.h (__dp_sign_max_size): New
    _Distance_precision enum entry.
    * include/debug/safe_iterator.h
    (__copy_move_a(_II, _II, const _Safe_iterator<>&)): Check for output
    iterator _M_can_advance as soon as input range distance precision is
    strictly higher than __dp_size.
    (__copy_move_a(const _Safe_iterator<>&, const _Safe_iterator<>&,
    const _Safe_iterator<>&)): Likewise.
    (__copy_move_backward_a(_II, _II, const _Safe_iterator<>&)): Likewise.
    (__copy_move_backward_a(const _Safe_iterator<>&,
    const _Safe_iterator<>&, const _Safe_iterator<>&)): Likewise.
    (__equal_aux(_II, _II, const _Safe_iterator<>&)): Likewise.
    (__equal_aux(const _Safe_iterator<>&,
    const _Safe_iterator<>&, const _Safe_iterator<>&)): Likewise.

François


diff --git a/libstdc++-v3/include/debug/forward_list b/libstdc++-v3/include/debug/forward_list
index e30b000009e..f1756ddec9d 100644
--- a/libstdc++-v3/include/debug/forward_list
+++ b/libstdc++-v3/include/debug/forward_list
@@ -911,7 +911,7 @@ namespace __gnu_debug
       _S_size(const std::__debug::forward_list<_Tp, _Alloc>& __seq)
       {
 	return __seq.empty()
-	  ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_equality);
+	  ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_sign);
       }
     };
 
diff --git a/libstdc++-v3/include/debug/helper_functions.h b/libstdc++-v3/include/debug/helper_functions.h
index b7aeafef12a..9429bb90a55 100644
--- a/libstdc++-v3/include/debug/helper_functions.h
+++ b/libstdc++-v3/include/debug/helper_functions.h
@@ -50,10 +50,11 @@ namespace __gnu_debug
    */
   enum _Distance_precision
     {
-      __dp_none,	// Not even an iterator type
-      __dp_equality,	//< Can compare iterator equality, only
-      __dp_sign,	//< Can determine equality and ordering
-      __dp_exact	//< Can determine distance precisely
+      __dp_none,		// Not even an iterator type
+      __dp_equality,		//< Can compare iterator equality, only
+      __dp_sign,		//< Can determine equality and ordering
+      __dp_sign_max_size,	//< __dp_sign and gives max range size
+      __dp_exact		//< Can determine distance precisely
     };
 
   template<typename _Iterator,
@@ -141,6 +142,7 @@ namespace __gnu_debug
 	    return true;
 	  break;
 	case __dp_sign:
+	case __dp_sign_max_size:
 	case __dp_exact:
 	  return __dist.first >= 0;
 	}
diff --git a/libstdc++-v3/include/debug/list b/libstdc++-v3/include/debug/list
index 5eb9a6094e3..140546a633e 100644
--- a/libstdc++-v3/include/debug/list
+++ b/libstdc++-v3/include/debug/list
@@ -916,7 +916,7 @@ namespace __gnu_debug
       _S_size(const std::__debug::list<_Tp, _Alloc>& __seq)
       {
 	return __seq.empty()
-	  ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_equality);
+	  ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_sign);
       }
     };
 #endif
diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h
index 1665c95f5df..584f8eec5b0 100644
--- a/libstdc++-v3/include/debug/safe_iterator.h
+++ b/libstdc++-v3/include/debug/safe_iterator.h
@@ -984,7 +984,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_check_valid_range2(__first, __last, __dist);
       __glibcxx_check_can_increment(__result, __dist.first);
 
-      if (__dist.second == ::__gnu_debug::__dp_exact
+      if (__dist.second > ::__gnu_debug::__dp_sign
 	  && __result._M_can_advance(__dist.first, true))
 	return ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>(
 		std::__copy_move_a<_IsMove>(__first, __last, __result.base()),
@@ -1008,7 +1008,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       if (__dist.second > ::__gnu_debug::__dp_equality)
 	{
-	  if (__dist.second == ::__gnu_debug::__dp_exact
+	  if (__dist.second > ::__gnu_debug::__dp_sign
 	      && __result._M_can_advance(__dist.first, true))
 	    return ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>(
 	      std::__copy_move_a<_IsMove>(__first.base(), __last.base(),
@@ -1051,7 +1051,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_check_valid_range2(__first, __last, __dist);
       __glibcxx_check_can_increment(__result, -__dist.first);
 
-      if (__dist.second == ::__gnu_debug::__dp_exact
+      if (__dist.second > ::__gnu_debug::__dp_sign
 	  && __result._M_can_advance(-__dist.first, true))
 	return ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>(
 		std::__copy_move_backward_a<_IsMove>(__first, __last,
@@ -1076,7 +1076,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       if (__dist.second > ::__gnu_debug::__dp_equality)
 	{
-	  if (__dist.second == ::__gnu_debug::__dp_exact
+	  if (__dist.second > ::__gnu_debug::__dp_sign
 	      && __result._M_can_advance(-__dist.first, true))
 	    return ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>(
 	      std::__copy_move_backward_a<_IsMove>(__first.base(), __last.base(),
@@ -1154,7 +1154,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_check_valid_range2(__first1, __last1, __dist);
       __glibcxx_check_can_increment(__first2, __dist.first);
 
-      if (__dist.second == ::__gnu_debug::__dp_exact
+      if (__dist.second > ::__gnu_debug::__dp_sign
 	  && __first2._M_can_advance(__dist.first, true))
 	return std::__equal_aux(__first1, __last1, __first2.base());
 
@@ -1175,7 +1175,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       if (__dist.second > ::__gnu_debug::__dp_equality)
 	{
-	  if (__dist.second == ::__gnu_debug::__dp_exact &&
+	  if (__dist.second > ::__gnu_debug::__dp_sign &&
 	      __first2._M_can_advance(__dist.first, true))
 	    return std::__equal_aux(__first1.base(), __last1.base(),
 				    __first2.base());
diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
index 3d30029dd25..99757f58269 100644
--- a/libstdc++-v3/include/debug/safe_iterator.tcc
+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
@@ -113,18 +113,22 @@ namespace __gnu_debug
     _Safe_iterator<_Iterator, _Sequence, _Category>::
     _M_get_distance_to(const _Safe_iterator& __rhs) const
     {
-      typedef typename _Distance_traits<_Iterator>::__type _Diff;
+      typedef typename _Distance_traits<_Iterator>::__type _Dist;
       typedef _Sequence_traits<_Sequence> _SeqTraits;
 
-      if (this->base() == __rhs.base())
-	return std::make_pair(0, __dp_exact);
+      _Dist __base_dist = __get_distance(this->base(), __rhs.base());
+      if (__base_dist.second == __dp_exact)
+	return __base_dist;
 
+      _Dist __seq_dist = _SeqTraits::_S_size(*this->_M_get_sequence());
       if (this->_M_is_before_begin())
 	{
 	  if (__rhs._M_is_begin())
 	    return std::make_pair(1, __dp_exact);
 
-	  return std::make_pair(1, __dp_sign);
+	  return __seq_dist.second == __dp_exact
+	    ? std::make_pair(__seq_dist.first + 1, __dp_exact)
+	    : __seq_dist;
 	}
 
       if (this->_M_is_begin())
@@ -133,30 +137,42 @@ namespace __gnu_debug
 	    return std::make_pair(-1, __dp_exact);
 
 	  if (__rhs._M_is_end())
-	    return _SeqTraits::_S_size(*this->_M_get_sequence());
+	    return __seq_dist;
 
-	  return std::make_pair(1, __dp_sign);
+	  return std::make_pair(__seq_dist.first,
+				__seq_dist.second == __dp_exact
+				? __dp_sign_max_size : __seq_dist.second);
 	}
 
       if (this->_M_is_end())
 	{
 	  if (__rhs._M_is_before_begin())
-	    return std::make_pair(-1, __dp_exact);
+	    return __seq_dist.second == __dp_exact
+	      ? std::make_pair(-__seq_dist.first - 1, __dp_exact)
+	      : std::make_pair(-__seq_dist.first, __dp_sign);
 
 	  if (__rhs._M_is_begin())
-	    {
-	      _Diff __diff = _SeqTraits::_S_size(*this->_M_get_sequence());
-	      return std::make_pair(-__diff.first, __diff.second);
-	    }
+	    return std::make_pair(-__seq_dist.first, __seq_dist.second);
 
-	  return std::make_pair(-1, __dp_sign);
+	  return std::make_pair(-__seq_dist.first,
+				__seq_dist.second == __dp_exact
+				? __dp_sign_max_size : __seq_dist.second);
 	}
 
-      if (__rhs._M_is_before_begin() || __rhs._M_is_begin())
-	return std::make_pair(-1, __dp_sign);
+      if (__rhs._M_is_before_begin())
+	return __seq_dist.second == __dp_exact
+	  ? std::make_pair(__seq_dist.first - 1, __dp_exact)
+	  : std::make_pair(-__seq_dist.first, __dp_sign);
+
+      if (__rhs._M_is_begin())
+	return std::make_pair(-__seq_dist.first,
+			      __seq_dist.second == __dp_exact
+			      ? __dp_sign_max_size : __seq_dist.second);
 
       if (__rhs._M_is_end())
-	return std::make_pair(1, __dp_sign);
+	return std::make_pair(__seq_dist.first,
+			      __seq_dist.second == __dp_exact
+			      ? __dp_sign_max_size : __seq_dist.second);
 
       return std::make_pair(1, __dp_equality);
     }
Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]