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));
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.
commit 8c22777c71589de7351b34ed4e94f3d3d2a216ee
Author: Jonathan Wakely <jwak...@redhat.com>
Date: Tue Jun 26 18:07:26 2018 +0100
Unwrap debug mode vector iterators to use optimized algorithms
By defining __niter_base for iterators from debug mode vectors more
algorithms can use the optimized implementations using memcpy or memset.
The new function __wrap_iter converts back to the original iterator
type, handling the case where it's a debug mode iterator and needs a
pointer to the container.
2018-06-27 Fran??ois Dumont <fdum...@gcc.gnu.org>
Jonathan Wakely <jwak...@redhat.com>
* include/bits/stl_algobase.h (__wrap_iter<_To, _From>): Define new
function to convert unwrapped iterator back to result type.
[_GLIBCXX_DEBUG] (__wrap_iter<_Iter,_Seq, _From>): Overload for
converting to _Safe_iterator.
[_GLIBCXX_DEBUG] (__wrap_iter<_Iter,_Seq>): Overload for converting
from reverse_iterator<I> to reverse_iterator<_Safe_iterator<I,S>>.
(__copy_move_a2, __copy_move_backward_a2, fill_n): Use __wrap_iter.
[_GLIBCXX_DEBUG] (equal<_II1, _II2>(_II1, _II1, _II2)): Use
__glibcxx_requires_can_increment_range to check for valid ranges.
* include/debug/stl_iterator.h (__niter_base): Declare overload for
iterators from debug mode vector.
* include/debug/vector (__niter_base): Define.
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 022a3f1598b..31b2801d749 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -415,13 +415,52 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,
istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
+ // Convert an iterator of type _From to an iterator of type _To.
+ // e.g. from int* to __normal_iterator<int*, Seq>.
+ template<typename _To, typename _From>
+ inline _To
+ __wrap_iter(_To, _From __from)
+ { return _To(__from); }
+
+#ifdef _GLIBCXX_DEBUG
+ // Convert an iterator of type _From to a safe iterator
+ // for the same sequence as __to.
+ template<typename _Iter, typename _Seq, typename _From>
+ inline __gnu_debug::_Safe_iterator<_Iter, _Seq>
+ __wrap_iter(__gnu_debug::_Safe_iterator<_Iter, _Seq> __to, _From __from)
+ {
+ return __gnu_debug::_Safe_iterator<_Iter, _Seq>(_Iter(__from),
+ __to._M_sequence);
+ }
+
+ // Conversion from reverse_iterator<> to reverse_iterator<_Safe_iterator<>>
+ template<typename _Iter, typename _Seq, typename _From>
+ inline reverse_iterator<__gnu_debug::_Safe_iterator<_Iter, _Seq> >
+ __wrap_iter(
+ reverse_iterator<__gnu_debug::_Safe_iterator<_Iter, _Seq> > __to,
+ reverse_iterator<_From> __from)
+ {
+ typedef __gnu_debug::_Safe_iterator<_Iter, _Seq> _Safe;
+ typedef reverse_iterator<_Safe> _RevIter;
+ return _RevIter(_Safe(_Iter(__from.base()), __to.base()._M_sequence));
+ }
+
+ // No conversion needed when already a safe iterator.
+ template<typename _Iter, typename _Seq>
+ inline __gnu_debug::_Safe_iterator<_Iter, _Seq>
+ __wrap_iter(__gnu_debug::_Safe_iterator<_Iter, _Seq>,
+ __gnu_debug::_Safe_iterator<_Iter, _Seq> __iter)
+ { return __iter; }
+#endif
+
template<bool _IsMove, typename _II, typename _OI>
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::__wrap_iter(__result,
+ std::__copy_move_a<_IsMove>(std::__niter_base(__first),
+ std::__niter_base(__last),
+ std::__niter_base(__result)));
}
/**
@@ -593,9 +632,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
inline _BI2
__copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
{
- return _BI2(std::__copy_move_backward_a<_IsMove>
- (std::__niter_base(__first), std::__niter_base(__last),
- std::__niter_base(__result)));
+ return std::__wrap_iter(__result,
+ std::__copy_move_backward_a<_IsMove>(std::__niter_base(__first),
+ std::__niter_base(__last),
+ std::__niter_base(__result)));
}
/**
@@ -785,7 +825,8 @@ _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::__wrap_iter(__first,
+ std::__fill_n_a(std::__niter_base(__first), __n, __value));
}
template<bool _BoolType>
@@ -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));
diff --git a/libstdc++-v3/include/debug/stl_iterator.h b/libstdc++-v3/include/debug/stl_iterator.h
index a6a2a762766..431293bdec9 100644
--- a/libstdc++-v3/include/debug/stl_iterator.h
+++ b/libstdc++-v3/include/debug/stl_iterator.h
@@ -118,6 +118,19 @@ namespace __gnu_debug
-> decltype(std::make_move_iterator(__base(__it.base())))
{ return std::make_move_iterator(__base(__it.base())); }
#endif
-}
+} // namespace __gnu_debug
+
+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
+} // namespace std
#endif
diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector
index 8d60da328e1..54697030974 100644
--- a/libstdc++-v3/include/debug/vector
+++ b/libstdc++-v3/include/debug/vector
@@ -784,7 +784,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
};
_GLIBCXX_END_NAMESPACE_VERSION
-#endif
+#endif // C++11
+
+ 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()); }
} // namespace std