This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ 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]

Re: Limit Debug mode impact: overload __niter_base


    Here is a new proposal between yours and mine.

    It is still adding a function to wrap what __niter_base unwrap, I called it __nwrap_iter for this reason. But it takes advantage of knowing that __niter_base will only unwrap random access iterator to use an expression to that will do the right thing, no matter the original iterator type.

    I eventually found no issue in the testsuite, despite the std::equal change. I might have had a local invalid test.

    Ok to commit ?

François


On 27/06/2018 22:02, Jonathan Wakely wrote:
On 27/06/18 21:25 +0200, François Dumont wrote:
On 27/06/2018 02:13, Jonathan Wakely wrote:
On 26/06/18 17:03 +0100, Jonathan Wakely wrote:
On 18/06/18 23:01 +0200, François Dumont wrote:
Hi

    I abandon the idea of providing Debug algos, it would be too much code to add and maintain. However I haven't quit on reducing Debug mode performance impact.

    So this patch make use of the existing std::__niter_base to get rid of the debug layer around __gnu_debug::vector<>::iterator so that __builtin_memmove replacement can take place.

    As _Safe_iterator<> do not have a constructor taking a pointer I change algos implementation so that we do not try to instantiate the iterator type ourselves but rather rely on its operators + or -.

    The small drawback is that for std::equal algo where we can't use the __glibcxx_can_increment we need to keep the debug layer to make sure we don't reach past-the-end iterator. So I had to remove usage of __niter_base when in Debug mode, doing so it also disable potential usage of __builtin_memcmp when calling std::equal on std::__cxx1998::vector<> iterators. A rather rare situation I think.

We don't need to give up all checks in std::equal, we can do this:

@@ -1044,7 +1085,13 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
           typename iterator_traits<_II1>::value_type,
           typename iterator_traits<_II2>::value_type>)
      __glibcxx_requires_valid_range(__first1, __last1);
-
+#ifdef _GLIBCXX_DEBUG
+      typedef typename iterator_traits<_II1>::iterator_category _Cat1;
+      typedef typename iterator_traits<_II2>::iterator_category _Cat2;
+      if (!__are_same<_Cat1, input_iterator_tag>::__value
+         && __are_same<_Cat2, random_access_iterator_tag>::__value)
+       __glibcxx_requires_can_increment_range(__first1, __last1, __first2);
+#endif
      return std::__equal_aux(std::__niter_base(__first1),
                             std::__niter_base(__last1),
                             std::__niter_base(__first2));

We don't give up any check.

We do for my version of the patch, because with the new __niter_base
overload the debug layer gets removed. Your patch kept the checking by
not removing the debug layer, but loses the memcmp optimization.

My suggestion above removes the debug layer so uses the optimization,
but adds a separate range check, so we still get checking as well.

We only give up on using the __builtin_memcmp when std::equal is being used while Debug mode is active and std::equal is called directly with std::__cxx1998::vector.

Moreover this check is wrong and will introduce regression when running testsuite in Debug mode (this is why I know). It will assert in the following case:
vector<int> v1 { 0, 0, 0 };
vector<int> v2 { 0, 1 };
equal(v1.begin(), v1.end(), v2.begin());

We should assert for that test, it's undefined behaviour.






    Note that I don't know how to test that __builtin_memmove has been indeed used. So I've been through some debug sessions to check that.

The attached patch (not fully tested) seems to be a much simpler way
to achieve the same thing. Instead of modifying all the helper
structs, just define a new function to re-wrap the result into the
desired iterator type.


diff --git a/libstdc++-v3/include/debug/stl_iterator.h b/libstdc++-v3/include/debug/stl_iterator.h
index a6a2a76..eca7203 100644
--- a/libstdc++-v3/include/debug/stl_iterator.h
+++ b/libstdc++-v3/include/debug/stl_iterator.h
@@ -120,4 +120,19 @@ namespace __gnu_debug
#endif
}

+#if __cplusplus >= 201103L
+namespace std
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+template<typename _Iterator, typename _Container, typename _Sequence>
+    _Iterator
+    __niter_base(const __gnu_debug::_Safe_iterator<
+         __gnu_cxx::__normal_iterator<_Iterator, _Container>,
+         _Sequence>&);
+
+_GLIBCXX_END_NAMESPACE_VERSION
+}
+#endif

Why is this overload only defined for C++11 and later? I defined it
unconditionally in the attached patch.

What do you think?

Here's a complete patch that passes all tests in normal mode and
causes no regressions in debug mode (we already have some debug test
failing).

I wondered whether we need another overload of __wrap_iter for
handling move_iterator, but I think the first overload works OK.


I don't think we need it neither. Algos that handle move iterator are already doing it.

OK great.




diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index d429943..003ae8d 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -277,6 +277,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     __niter_base(_Iterator __it)
     { return __it; }
 
+  // Convert an iterator of type _From to an iterator of type _To.
+  // e.g. from int* to __normal_iterator<int*, Seq>.
+  template<typename _Iterator>
+    inline _Iterator
+    __nwrap_iter(_Iterator, _Iterator, _Iterator __res)
+    { return __res; }
+
+  template<typename _From, typename _To>
+    inline _From
+    __nwrap_iter(_From __from, _To __to, _To __res)
+    { return __from + (__res - __to); }
+
   // All of these auxiliary structs serve two purposes.  (1) Replace
   // calls to copy with memmove whenever possible.  (Memmove, not memcpy,
   // because the input and output ranges are permitted to overlap.)
@@ -419,9 +431,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     inline _OI
     __copy_move_a2(_II __first, _II __last, _OI __result)
     {
-      return _OI(std::__copy_move_a<_IsMove>(std::__niter_base(__first),
-					     std::__niter_base(__last),
-					     std::__niter_base(__result)));
+      return std::__nwrap_iter(__result,
+		std::__niter_base(__result),
+		std::__copy_move_a<_IsMove>(std::__niter_base(__first),
+					    std::__niter_base(__last),
+					    std::__niter_base(__result)));
     }
 
   /**
@@ -593,7 +607,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     inline _BI2
     __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
     {
-      return _BI2(std::__copy_move_backward_a<_IsMove>
+      return std::__nwrap_iter(__result,
+		std::__niter_base(__result),
+		std::__copy_move_backward_a<_IsMove>
 		  (std::__niter_base(__first), std::__niter_base(__last),
 		   std::__niter_base(__result)));
     }
@@ -804,7 +820,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>)
       __glibcxx_requires_can_increment(__first, __n);
 
-      return _OI(std::__fill_n_a(std::__niter_base(__first), __n, __value));
+      return std::__nwrap_iter(__first,
+		std::__niter_base(__first),
+		std::__fill_n_a(std::__niter_base(__first), __n, __value));
     }
 
   template<bool _BoolType>
@@ -1062,7 +1080,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       __glibcxx_function_requires(_EqualOpConcept<
 	    typename iterator_traits<_II1>::value_type,
 	    typename iterator_traits<_II2>::value_type>)
-      __glibcxx_requires_valid_range(__first1, __last1);
+	__glibcxx_requires_can_increment_range(__first1, __last1, __first2);
 
       return std::__equal_aux(std::__niter_base(__first1),
 			      std::__niter_base(__last1),
diff --git a/libstdc++-v3/include/debug/stl_iterator.h b/libstdc++-v3/include/debug/stl_iterator.h
index a6a2a76..f20b000 100644
--- a/libstdc++-v3/include/debug/stl_iterator.h
+++ b/libstdc++-v3/include/debug/stl_iterator.h
@@ -120,4 +120,17 @@ namespace __gnu_debug
 #endif
 }
 
+namespace std
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+  template<typename _Iterator, typename _Container, typename _Sequence>
+    _Iterator
+    __niter_base(const __gnu_debug::_Safe_iterator<
+		 __gnu_cxx::__normal_iterator<_Iterator, _Container>,
+		 _Sequence>&);
+
+_GLIBCXX_END_NAMESPACE_VERSION
+}
+
 #endif
diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector
index 802f4fd..ced5520 100644
--- a/libstdc++-v3/include/debug/vector
+++ b/libstdc++-v3/include/debug/vector
@@ -785,6 +785,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()(__b); }
     };
 
+ template<typename _Iterator, typename _Container, typename _Sequence>
+    _Iterator
+    __niter_base(const __gnu_debug::_Safe_iterator<
+		 __gnu_cxx::__normal_iterator<_Iterator, _Container>,
+		 _Sequence>& __it)
+    { return std::__niter_base(__it.base()); }
+
 _GLIBCXX_END_NAMESPACE_VERSION
 #endif
 

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]