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