* libstdc++: Extend memcmp optimization in std::lexicographical_compare
@ 2020-06-05 20:24 François Dumont
2020-06-08 18:20 ` Jonathan Wakely
2020-06-08 20:07 ` Jonathan Wakely
0 siblings, 2 replies; 19+ messages in thread
From: François Dumont @ 2020-06-05 20:24 UTC (permalink / raw)
To: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 2525 bytes --]
Hi
Here is the last of my algo patches this time to extend the memcmp
optimization to std::deque iterators and _GLIBCXX_DEBUG mode.
To do so I had to return int in implementation details of
lexicographical_compare to make sure we can treat a deque iterator range
by chunk in a performant way.
Tested under Linux x86_64 normal and debug modes.
* include/bits/stl_algobase.h
(__lexicographical_compare_impl): Return int.
(__lexicographical_compare::__lc): Likewise.
(__lexicographical_compare_aux1(_II1, _II1, _II2, _II2)): New.
(__lexicographical_compare_aux1(_Deque_iterator<>, _Deque_iterator<>,
_II2, _II2)): Declare.
(__lexicographical_compare_aux1(_II1, _II1,
_Deque_iterator<>, _Deque_iterator<>)): Declare.
(__lexicographical_compare_aux1(_Deque_iterator<>, _Deque_iterator<>,
_Deque_iterator<>, _Deque_iterator<>)): Declare.
(__lexicographical_compare_aux): Adapt, call later.
(__lexicographical_compare_aux(_Safe_iterator<>,
_Safe_iterator<>,
_II2, _II2)): Declare.
(__lexicographical_compare_aux(_II1, _II1,
_Safe_iterator<>, _Safe_iterator<>)): Declare.
(__lexicographical_compare_aux(_Safe_iterator<>,
_Safe_iterator<>,
_Safe_iterator<>, _Safe_iterator<>)): Declare.
(std::lexicographical_compare): Adapt, call later without
__niter_base
usage.
* include/bits/deque.tcc (__lex_cmp_dit): New.
(__lexicographical_compare_aux1): New.
* include/debug/safe_iterator.tcc
(__lexicographical_compare_aux(const _Safe_iterator<>&,
const _Safe_iterator<>&, _II2, _II2)): New.
(__lexicographical_compare_aux(
const _Safe_iterator<>&, const_Safe_iterator<>&,
const _Safe_iterator<>&, const _Safe_iterator<>&)): New.
* testsuite/25_algorithms/lexicographical_compare/1.cc
(test6, test7):
New.
*
testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc:
New test.
Ok to commit ?
François
[-- Attachment #2: lexi_cmp_debug_deque.patch --]
[-- Type: text/x-patch, Size: 18916 bytes --]
diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
index 1d32a1691c7..d7dbe64f3e1 100644
--- a/libstdc++-v3/include/bits/deque.tcc
+++ b/libstdc++-v3/include/bits/deque.tcc
@@ -1261,6 +1261,98 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
return true;
}
+ template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
+ int
+ __lex_cmp_dit(
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __first1,
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __last1,
+ _II __first2, _II __last2)
+ {
+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
+ typedef typename _Iter::difference_type difference_type;
+
+ if (__first1._M_node != __last1._M_node)
+ {
+ difference_type __len = __last2 - __first2;
+ difference_type __flen
+ = std::min(__len, __first1._M_last - __first1._M_cur);
+ if (int __ret = std::__lexicographical_compare_aux1(
+ __first1._M_cur, __first1._M_last, __first2, __first2 + __flen))
+ return __ret;
+
+ __first2 += __flen;
+ __len -= __flen;
+ __flen = std::min<size_t>(__len, _Iter::_S_buffer_size());
+ for (typename _Iter::_Map_pointer __node = __first1._M_node + 1;
+ __node != __last1._M_node;
+ __first2 += __flen, __len -= __flen,
+ __flen = std::min<size_t>(__len, _Iter::_S_buffer_size()),
+ ++__node)
+ if (int __ret = std::__lexicographical_compare_aux1(
+ *__node, *__node + _Iter::_S_buffer_size(),
+ __first2, __first2 + __flen))
+ return __ret;
+
+ return std::__lexicographical_compare_aux1(
+ __last1._M_first, __last1._M_cur, __first2, __last2);
+ }
+
+ return std::__lexicographical_compare_aux1(
+ __first1._M_cur, __last1._M_cur, __first2, __last2);
+ }
+
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _II2>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II2>::__value, int>::__type
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
+ _II2 __first2, _II2 __last2)
+ { return std::__lex_cmp_dit(__first1, __last1, __first2, __last2); }
+
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ int
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
+ { return std::__lex_cmp_dit(__first1, __last1, __first2, __last2); }
+
+ template<typename _II1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II1>::__value, int>::__type
+ __lexicographical_compare_aux1(
+ _II1 __first1, _II1 __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
+ {
+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> _Iter;
+ typedef typename _Iter::difference_type difference_type;
+
+ difference_type __len = __last1 - __first1;
+ while (__len > 0)
+ {
+ const difference_type __flen = __first2._M_node == __last2._M_node
+ ? __last2._M_cur - __first2._M_cur
+ : __first2._M_last - __first2._M_cur;
+ const difference_type __clen = std::min(__len, __flen);
+ if (int __ret = std::__lexicographical_compare_aux1(
+ __first1, __first1 + __clen,
+ __first2._M_cur, __first2._M_cur + __flen))
+ return __ret;
+
+ __first1 += __clen;
+ __len -= __clen;
+ __first2 += __clen;
+ }
+
+ return __first1 == __last1 ? (__first2 != __last2 ? -1 : 0) : 1;
+ }
+
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 0163d8f902d..ecc50a10c9d 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -1279,7 +1279,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
template<typename _II1, typename _II2, typename _Compare>
_GLIBCXX20_CONSTEXPR
- bool
+ int
__lexicographical_compare_impl(_II1 __first1, _II1 __last1,
_II2 __first2, _II2 __last2,
_Compare __comp)
@@ -1288,16 +1288,18 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
typedef typename iterator_traits<_II2>::iterator_category _Category2;
typedef std::__lc_rai<_Category1, _Category2> __rai_type;
- __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
- for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
+ _II1 __new_last1
+ = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
+ for (; __first1 != __new_last1 && __rai_type::__cnd2(__first2, __last2);
++__first1, (void)++__first2)
{
if (__comp(__first1, __first2))
- return true;
+ return -1;
if (__comp(__first2, __first1))
- return false;
+ return 1;
}
- return __first1 == __last1 && __first2 != __last2;
+
+ return __first1 == __last1 ? (__first2 != __last2 ? -1 : 0) : 1;
}
template<bool _BoolType>
@@ -1305,7 +1307,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
{
template<typename _II1, typename _II2>
_GLIBCXX20_CONSTEXPR
- static bool
+ static int
__lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
{
using __gnu_cxx::__ops::__iter_less_iter;
@@ -1320,7 +1322,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
{
template<typename _Tp, typename _Up>
_GLIBCXX20_CONSTEXPR
- static bool
+ static int
__lc(const _Tp* __first1, const _Tp* __last1,
const _Up* __first2, const _Up* __last2)
{
@@ -1328,16 +1330,44 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
const size_t __len2 = __last2 - __first2;
if (const size_t __len = std::min(__len1, __len2))
if (int __result = std::__memcmp(__first1, __first2, __len))
- return __result < 0;
- return __len1 < __len2;
+ return __result;
+
+ return __len1 < __len2 ? -1 : (__len2 < __len1 ? 1 : 0);
}
};
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _II2>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II2>::__value, int>::__type
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _II2, _II2);
+
+ template<typename _II1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II1>::__value, int>::__type
+ __lexicographical_compare_aux1(
+ _II1, _II1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
+
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ int
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
+
template<typename _II1, typename _II2>
_GLIBCXX20_CONSTEXPR
- inline bool
- __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
- _II2 __first2, _II2 __last2)
+ inline int
+ __lexicographical_compare_aux1(_II1 __first1, _II1 __last1,
+ _II2 __first2, _II2 __last2)
{
typedef typename iterator_traits<_II1>::value_type _ValueType1;
typedef typename iterator_traits<_II2>::value_type _ValueType2;
@@ -1360,6 +1390,43 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
__first2, __last2);
}
+ template<typename _II1, typename _II2>
+ _GLIBCXX20_CONSTEXPR
+ inline int
+ __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
+ _II2 __first2, _II2 __last2)
+ {
+ return std::__lexicographical_compare_aux1(std::__niter_base(__first1),
+ std::__niter_base(__last1),
+ std::__niter_base(__first2),
+ std::__niter_base(__last2));
+ }
+
+ template<typename _Ite1, typename _Seq1, typename _Cat1,
+ typename _II2>
+ int
+ __lexicographical_compare_aux(
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
+ _II2, _II2);
+
+ template<typename _II1,
+ typename _Ite2, typename _Seq2, typename _Cat2>
+ int
+ __lexicographical_compare_aux(
+ _II1, _II1,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&);
+
+ template<typename _Ite1, typename _Seq1, typename _Cat1,
+ typename _Ite2, typename _Seq2, typename _Cat2>
+ int
+ __lexicographical_compare_aux(
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&);
+
template<typename _ForwardIterator, typename _Tp, typename _Compare>
_GLIBCXX20_CONSTEXPR
_ForwardIterator
@@ -1659,10 +1726,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
__glibcxx_requires_valid_range(__first1, __last1);
__glibcxx_requires_valid_range(__first2, __last2);
- return std::__lexicographical_compare_aux(std::__niter_base(__first1),
- std::__niter_base(__last1),
- std::__niter_base(__first2),
- std::__niter_base(__last2));
+ return std::__lexicographical_compare_aux(__first1, __last1,
+ __first2, __last2) < 0;
}
/**
@@ -1692,7 +1757,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
return std::__lexicographical_compare_impl
(__first1, __last1, __first2, __last2,
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_comp_iter(__comp)) < 0;
}
#if __cpp_lib_three_way_comparison
diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
index 888ac803ae5..ca4e2d52d1d 100644
--- a/libstdc++-v3/include/debug/safe_iterator.tcc
+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
@@ -470,6 +470,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return __equal_aux1(__first1, __last1, __first2);
}
+ template<typename _Ite1, typename _Seq1, typename _Cat1,
+ typename _II2>
+ int
+ __lexicographical_compare_aux(
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
+ _II2 __first2, _II2 __last2)
+ {
+ typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
+ __glibcxx_check_valid_range2(__first1, __last1, __dist1);
+ __glibcxx_check_valid_range(__first2, __last2);
+
+ if (__dist1.second > ::__gnu_debug::__dp_equality)
+ return std::__lexicographical_compare_aux(__first1.base(),
+ __last1.base(),
+ __first2, __last2);
+ return std::__lexicographical_compare_aux1(__first1, __last1,
+ __first2, __last2);
+ }
+
+ template<typename _II1,
+ typename _Ite2, typename _Seq2, typename _Cat2>
+ int
+ __lexicographical_compare_aux(
+ _II1 __first1, _II1 __last1,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
+ {
+ __glibcxx_check_valid_range(__first1, __last1);
+ typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist2;
+ __glibcxx_check_valid_range2(__first2, __last2, __dist2);
+
+ if (__dist2.second > ::__gnu_debug::__dp_equality)
+ return std::__lexicographical_compare_aux(__first1, __last1,
+ __first2.base(),
+ __last2.base());
+ return std::__lexicographical_compare_aux1(__first1, __last1,
+ __first2, __last2);
+ }
+
+ template<typename _Ite1, typename _Seq1, typename _Cat1,
+ typename _Ite2, typename _Seq2, typename _Cat2>
+ int
+ __lexicographical_compare_aux(
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
+ {
+ typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
+ __glibcxx_check_valid_range2(__first1, __last1, __dist1);
+ typename ::__gnu_debug::_Distance_traits<_Ite2>::__type __dist2;
+ __glibcxx_check_valid_range2(__first2, __last2, __dist2);
+
+ if (__dist1.second > ::__gnu_debug::__dp_equality)
+ {
+ if (__dist2.second > ::__gnu_debug::__dp_equality)
+ return std::__lexicographical_compare_aux(__first1.base(),
+ __last1.base(),
+ __first2.base(),
+ __last2.base());
+ return std::__lexicographical_compare_aux(__first1.base(),
+ __last1.base(),
+ __first2, __last2);
+ }
+
+ if (__dist2.second > ::__gnu_debug::__dp_equality)
+ return std::__lexicographical_compare_aux(__first1, __last1,
+ __first2.base(),
+ __last2.base());
+ return std::__lexicographical_compare_aux1(__first1, __last1,
+ __first2, __last2);
+ }
+
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
index 8c2f043f943..b8f92bacd85 100644
--- a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
@@ -74,6 +74,29 @@ test5()
con2.begin(), con2.end()) );
}
+void
+test6()
+{
+ VERIFY( std::lexicographical_compare(array2, array2 + 2,
+ array3, array3 + 3) );
+ VERIFY( !std::lexicographical_compare(array3, array3 + 3,
+ array2, array2 + 2) );
+}
+
+using __gnu_test::random_access_iterator_wrapper;
+typedef test_container<int, random_access_iterator_wrapper> RaiContainer;
+
+void
+test7()
+{
+ RaiContainer con2(array2, array2 + 2);
+ RaiContainer con3(array3, array3 + 3);
+ VERIFY( std::lexicographical_compare(con2.begin(), con2.end(),
+ con3.begin(), con3.end()) );
+ VERIFY( !std::lexicographical_compare(con3.begin(), con3.end(),
+ con2.begin(), con2.end()) );
+}
+
int
main()
{
@@ -82,4 +105,6 @@ main()
test3();
test4();
test5();
+ test6();
+ test7();
}
diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc
new file mode 100644
index 00000000000..c686ad5677d
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc
@@ -0,0 +1,134 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <algorithm>
+#include <vector>
+#include <deque>
+
+#include <ext/new_allocator.h>
+#include <ext/malloc_allocator.h>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i)
+ d.push_back(i);
+
+ const deque<int>& cd = d;
+
+ VERIFY( !lexicographical_compare(cd.begin(), cd.end(), cd.begin(), cd.end()) );
+ VERIFY( !lexicographical_compare(cd.begin(), cd.end(), d.begin(), d.end()) );
+ VERIFY( !lexicographical_compare(d.begin(), d.end(), d.begin(), d.end()) );
+ VERIFY( !lexicographical_compare(d.begin(), d.end(), cd.begin(), cd.end()) );
+}
+
+void test02()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != 1000; ++i)
+ d.push_back(i % 10);
+
+ VERIFY( !lexicographical_compare(d.begin(), d.begin() + 10,
+ d.begin() + 20, d.begin() + 30) );
+ VERIFY( lexicographical_compare(d.begin(), d.begin() + 10,
+ d.begin() + 20, d.begin() + 31) );
+ VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10,
+ d.begin(), d.end() - 20) );
+
+ const deque<int>& cd = d;
+
+ VERIFY( !lexicographical_compare(cd.begin(), cd.begin() + 10,
+ cd.begin() + 20, cd.begin() + 30) );
+ VERIFY( !lexicographical_compare(cd.begin() + 10, cd.end() - 10,
+ d.begin(), d.end() - 20) );
+ VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10,
+ cd.begin(), cd.end() - 20) );
+}
+
+void test03()
+{
+ using namespace std;
+
+ deque<int> d1;
+ for (int i = 0; i != 1000; ++i)
+ d1.push_back(i % 10);
+
+ deque<int> d2(d1);
+ for (int i = 0; i != 10; ++i)
+ d2.pop_front();
+
+ VERIFY( !lexicographical_compare(d1.begin(), d1.begin() + 10,
+ d2.begin(), d2.begin() + 10) );
+ VERIFY( !lexicographical_compare(d1.begin() + 10, d1.end() - 10,
+ d2.begin(), d2.end() - 10) );
+
+ const deque<int>& cd1 = d1;
+ const deque<int>& cd2 = d2;
+
+ VERIFY( !lexicographical_compare(cd1.begin(), cd1.begin() + 10,
+ cd2.begin() + 20, cd2.begin() + 30) );
+ VERIFY( !lexicographical_compare(cd1.begin() + 10, cd1.end() - 10,
+ d2.begin(), d2.end() - 10) );
+ VERIFY( lexicographical_compare(cd2.begin() + 10, cd2.end() - 10,
+ cd1.begin(), cd1.end() - 20) );
+}
+
+void test04()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ vector<int> v(d.begin(), d.end());
+
+ VERIFY( lexicographical_compare(d.begin() + 5, d.end() - 1, v.begin() + 5, v.end()) );
+ VERIFY( !lexicographical_compare(v.begin(), v.end(), d.begin(), d.end()) );
+
+ const deque<int>& cd = d;
+
+ VERIFY( !lexicographical_compare(cd.begin(), cd.end(), v.begin(), v.end()) );
+ VERIFY( !lexicographical_compare(v.begin(), v.end(), cd.begin(), cd.end()) );
+}
+
+void test05()
+{
+ using namespace std;
+
+ int a[] = { 0, 1, 2, 3, 4 };
+ deque<int, __gnu_cxx::new_allocator<int> > d1(a, a + 5);
+ deque<int, __gnu_cxx::malloc_allocator<int> > d2(a, a + 5);
+
+ VERIFY( !lexicographical_compare(d1.begin(), d1.end(), d2.begin(), d2.end()) );
+}
+
+int main()
+{
+ test01();
+ test02();
+ test03();
+ test04();
+ test05();
+ return 0;
+}
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: libstdc++: Extend memcmp optimization in std::lexicographical_compare
2020-06-05 20:24 libstdc++: Extend memcmp optimization in std::lexicographical_compare François Dumont
@ 2020-06-08 18:20 ` Jonathan Wakely
2020-06-08 21:08 ` Jonathan Wakely
` (2 more replies)
2020-06-08 20:07 ` Jonathan Wakely
1 sibling, 3 replies; 19+ messages in thread
From: Jonathan Wakely @ 2020-06-08 18:20 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On 05/06/20 22:24 +0200, François Dumont via Libstdc++ wrote:
>Hi
>
>Â Â Â Here is the last of my algo patches this time to extend the memcmp
>optimization to std::deque iterators and _GLIBCXX_DEBUG mode.
>
>Â Â Â To do so I had to return int in implementation details of
>lexicographical_compare to make sure we can treat a deque iterator
>range by chunk in a performant way.
>
>Tested under Linux x86_64 normal and debug modes.
>
>Â Â Â Â Â Â Â Â Â Â Â * include/bits/stl_algobase.h
>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_impl): Return int.
>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare::__lc): Likewise.
>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux1(_II1, _II1, _II2, _II2)): New.
>(__lexicographical_compare_aux1(_Deque_iterator<>, _Deque_iterator<>,
>Â Â Â Â Â Â Â Â Â Â Â _II2, _II2)): Declare.
>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux1(_II1, _II1,
>Â Â Â Â Â Â Â Â Â Â Â _Deque_iterator<>, _Deque_iterator<>)): Declare.
>(__lexicographical_compare_aux1(_Deque_iterator<>, _Deque_iterator<>,
>Â Â Â Â Â Â Â Â Â Â Â _Deque_iterator<>, _Deque_iterator<>)): Declare.
>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux): Adapt, call later.
Is this meant to say "latter"? That's still not correct grammar
though. I think it would be better to name the function it calls
explicitly: "Call __lexicographical_compare_aux1."
>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux(_Safe_iterator<>,
>_Safe_iterator<>,
>Â Â Â Â Â Â Â Â Â Â Â _II2, _II2)): Declare.
>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux(_II1, _II1,
>Â Â Â Â Â Â Â Â Â Â Â _Safe_iterator<>, _Safe_iterator<>)): Declare.
>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux(_Safe_iterator<>,
>_Safe_iterator<>,
>Â Â Â Â Â Â Â Â Â Â Â _Safe_iterator<>, _Safe_iterator<>)): Declare.
>Â Â Â Â Â Â Â Â Â Â Â (std::lexicographical_compare): Adapt, call later without
>__niter_base
>Â Â Â Â Â Â Â Â Â Â Â usage.
>Â Â Â Â Â Â Â Â Â Â Â * include/bits/deque.tcc (__lex_cmp_dit): New.
>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux1): New.
>Â Â Â Â Â Â Â Â Â Â Â * include/debug/safe_iterator.tcc
>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux(const _Safe_iterator<>&,
>Â Â Â Â Â Â Â Â Â Â Â const _Safe_iterator<>&, _II2, _II2)): New.
>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux(
>Â Â Â Â Â Â Â Â Â Â Â const _Safe_iterator<>&, const_Safe_iterator<>&,
>Â Â Â Â Â Â Â Â Â Â Â const _Safe_iterator<>&, const _Safe_iterator<>&)): New.
>Â Â Â Â Â Â Â Â Â Â Â * testsuite/25_algorithms/lexicographical_compare/1.cc
>(test6, test7):
>Â Â Â Â Â Â Â Â Â Â Â New.
>Â Â Â Â Â Â Â Â Â Â Â *
>testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc:
>Â Â Â Â Â Â Â Â Â Â Â New test.
>
>Ok to commit ?
>
>François
>
>
>diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
>index 1d32a1691c7..d7dbe64f3e1 100644
>--- a/libstdc++-v3/include/bits/deque.tcc
>+++ b/libstdc++-v3/include/bits/deque.tcc
>@@ -1261,6 +1261,98 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
> return true;
> }
>
>+ template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
_II is the wrong name here, it mean InputIterator. All callers of this
function are constrained for random access iterators. This cannot be
called with an input iterator. Please use _RAIter.
>+ int
>+ __lex_cmp_dit(
>+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __first1,
>+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __last1,
>+ _II __first2, _II __last2)
>+ {
>+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
>+ typedef typename _Iter::difference_type difference_type;
>+
>+ if (__first1._M_node != __last1._M_node)
>+ {
>+ difference_type __len = __last2 - __first2;
>+ difference_type __flen
What does "flen" mean? Why not use len2 for last2 - first2, as we do
elsewhere? And then use len for min(len1, len2)?
>+ = std::min(__len, __first1._M_last - __first1._M_cur);
>+ if (int __ret = std::__lexicographical_compare_aux1(
This call (and the three later in this function) will do overload
resolution again on the full set of __lexicographical_compare_aux1
overloads, which includes the ones for deque iterators. But we know
that __first1._M_cur and __first1._M_last are not deque iterators.
__first2 could be a deque iterator, but I'm not sure if we really want
one function that has to handle that case anyway.
>+ __first1._M_cur, __first1._M_last, __first2, __first2 + __flen))
>+ return __ret;
>+
>+ __first2 += __flen;
>+ __len -= __flen;
>+ __flen = std::min<size_t>(__len, _Iter::_S_buffer_size());
>+ for (typename _Iter::_Map_pointer __node = __first1._M_node + 1;
>+ __node != __last1._M_node;
>+ __first2 += __flen, __len -= __flen,
>+ __flen = std::min<size_t>(__len, _Iter::_S_buffer_size()),
>+ ++__node)
>+ if (int __ret = std::__lexicographical_compare_aux1(
>+ *__node, *__node + _Iter::_S_buffer_size(),
>+ __first2, __first2 + __flen))
>+ return __ret;
>+
>+ return std::__lexicographical_compare_aux1(
>+ __last1._M_first, __last1._M_cur, __first2, __last2);
>+ }
>+
>+ return std::__lexicographical_compare_aux1(
>+ __first1._M_cur, __last1._M_cur, __first2, __last2);
>+ }
>+
>+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
>+ typename _II2>
This is not an input iterator either.
>+ typename __gnu_cxx::__enable_if<
>+ __is_random_access_iter<_II2>::__value, int>::__type
This should be inline.
Also, I'm curious why these overloads use __enable_if rather than the
conventional approach of tag dispatching using iterator_category.
(The same question applies to th __equal_aux1 and __copy_move_a1
overloads for deque iterators as well). It doesn't really matter
though.
>+ __lexicographical_compare_aux1(
>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
>+ _II2 __first2, _II2 __last2)
>+ { return std::__lex_cmp_dit(__first1, __last1, __first2, __last2); }
>+
>+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
>+ typename _Tp2, typename _Ref2, typename _Ptr2>
>+ int
This should be inline.
>+ __lexicographical_compare_aux1(
>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
>+ { return std::__lex_cmp_dit(__first1, __last1, __first2, __last2); }
I'm not convinced it's useful for this function and the one above it
to share the same logic.
>+ template<typename _II1,
>+ typename _Tp2, typename _Ref2, typename _Ptr2>
>+ typename __gnu_cxx::__enable_if<
>+ __is_random_access_iter<_II1>::__value, int>::__type
>+ __lexicographical_compare_aux1(
>+ _II1 __first1, _II1 __last1,
>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
>+ {
>+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> _Iter;
>+ typedef typename _Iter::difference_type difference_type;
>+
>+ difference_type __len = __last1 - __first1;
>+ while (__len > 0)
>+ {
>+ const difference_type __flen = __first2._M_node == __last2._M_node
>+ ? __last2._M_cur - __first2._M_cur
>+ : __first2._M_last - __first2._M_cur;
>+ const difference_type __clen = std::min(__len, __flen);
"flen"? "clen"?
>+ if (int __ret = std::__lexicographical_compare_aux1(
>+ __first1, __first1 + __clen,
>+ __first2._M_cur, __first2._M_cur + __flen))
>+ return __ret;
>+
>+ __first1 += __clen;
>+ __len -= __clen;
>+ __first2 += __clen;
>+ }
>+
>+ return __first1 == __last1 ? (__first2 != __last2 ? -1 : 0) : 1;
Isn't this function doing basically the same as __lex_cmp_dit? Why
does it not use the same logic?
Can this whole function just negate the result of __lex_cmp_dit called
with the arguments switched?
return -std::__lex_cmp_dit(__first2, __last2, __first1, __last1);
That would also fix the bug that makes the following loop forever:
std::deque<int> d;
int i = 0;
std::lexicographical_compare(&i, &i + 1, d.begin(), d.end());
>+ }
>+
> _GLIBCXX_END_NAMESPACE_VERSION
> } // namespace std
>
>diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
>index 0163d8f902d..ecc50a10c9d 100644
>--- a/libstdc++-v3/include/bits/stl_algobase.h
>+++ b/libstdc++-v3/include/bits/stl_algobase.h
>@@ -1279,7 +1279,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>
> template<typename _II1, typename _II2, typename _Compare>
> _GLIBCXX20_CONSTEXPR
>- bool
>+ int
> __lexicographical_compare_impl(_II1 __first1, _II1 __last1,
> _II2 __first2, _II2 __last2,
> _Compare __comp)
>@@ -1288,16 +1288,18 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
> typedef typename iterator_traits<_II2>::iterator_category _Category2;
> typedef std::__lc_rai<_Category1, _Category2> __rai_type;
>
>- __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
>- for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
>+ _II1 __new_last1
>+ = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
>+ for (; __first1 != __new_last1 && __rai_type::__cnd2(__first2, __last2);
> ++__first1, (void)++__first2)
> {
> if (__comp(__first1, __first2))
>- return true;
>+ return -1;
> if (__comp(__first2, __first1))
>- return false;
>+ return 1;
> }
>- return __first1 == __last1 && __first2 != __last2;
>+
>+ return __first1 == __last1 ? (__first2 != __last2 ? -1 : 0) : 1;
This is going to produce worse code for the common (non-deque) case,
isn't it?
> }
>
> template<bool _BoolType>
>@@ -1305,7 +1307,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
> {
> template<typename _II1, typename _II2>
> _GLIBCXX20_CONSTEXPR
>- static bool
>+ static int
> __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
> {
> using __gnu_cxx::__ops::__iter_less_iter;
>@@ -1320,7 +1322,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
> {
> template<typename _Tp, typename _Up>
> _GLIBCXX20_CONSTEXPR
>- static bool
>+ static int
> __lc(const _Tp* __first1, const _Tp* __last1,
> const _Up* __first2, const _Up* __last2)
> {
>@@ -1328,16 +1330,44 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
> const size_t __len2 = __last2 - __first2;
> if (const size_t __len = std::min(__len1, __len2))
> if (int __result = std::__memcmp(__first1, __first2, __len))
>- return __result < 0;
>- return __len1 < __len2;
>+ return __result;
>+
>+ return __len1 < __len2 ? -1 : (__len2 < __len1 ? 1 : 0);
Again, this will produce worse code.
If you made it return ptrdiff_t instead of int you could just do:
return ptrdiff_t(__len1 - __len2);
But I think we should just not change these __lc helpers, and not try
to reuse them for deque iterators. We can define new helpers that
return the 3-way result that is needed for comparing deque iterators.
>+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
>+ typename _II2>
>+ typename __gnu_cxx::__enable_if<
>+ __is_random_access_iter<_II2>::__value, int>::__type
>+ __lexicographical_compare_aux1(
>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
>+ _II2, _II2);
>+
>+ template<typename _II1,
>+ typename _Tp2, typename _Ref2, typename _Ptr2>
>+ typename __gnu_cxx::__enable_if<
>+ __is_random_access_iter<_II1>::__value, int>::__type
>+ __lexicographical_compare_aux1(
>+ _II1, _II1,
>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
>+
>+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
>+ typename _Tp2, typename _Ref2, typename _Ptr2>
>+ int
>+ __lexicographical_compare_aux1(
>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
>+
> template<typename _II1, typename _II2>
> _GLIBCXX20_CONSTEXPR
>- inline bool
>- __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
>- _II2 __first2, _II2 __last2)
>+ inline int
>+ __lexicographical_compare_aux1(_II1 __first1, _II1 __last1,
>+ _II2 __first2, _II2 __last2)
If you rename this to __lexicographical_compare_aux2 instead and add
a one-line forwarding function called __lexicographical_compare_aux1,
then the code above for deque iterators can call the aux2 overload
directly, to avoid doing overload resolution on aux1 again.
> {
> typedef typename iterator_traits<_II1>::value_type _ValueType1;
> typedef typename iterator_traits<_II2>::value_type _ValueType2;
>@@ -1360,6 +1390,43 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
> __first2, __last2);
> }
>
>+ template<typename _II1, typename _II2>
>+ _GLIBCXX20_CONSTEXPR
>+ inline int
>+ __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
>+ _II2 __first2, _II2 __last2)
>+ {
>+ return std::__lexicographical_compare_aux1(std::__niter_base(__first1),
>+ std::__niter_base(__last1),
>+ std::__niter_base(__first2),
>+ std::__niter_base(__last2));
>+ }
>+
>+ template<typename _Ite1, typename _Seq1, typename _Cat1,
Please don't introduce any more "Ite" parameters, this should be _It1
or _Iter1.
>+ typename _II2>
>+ int
>+ __lexicographical_compare_aux(
>+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
>+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
>+ _II2, _II2);
>+
>+ template<typename _II1,
>+ typename _Ite2, typename _Seq2, typename _Cat2>
>+ int
>+ __lexicographical_compare_aux(
>+ _II1, _II1,
>+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&,
>+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&);
>+
>+ template<typename _Ite1, typename _Seq1, typename _Cat1,
>+ typename _Ite2, typename _Seq2, typename _Cat2>
>+ int
>+ __lexicographical_compare_aux(
>+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
>+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
>+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&,
>+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&);
>+
> template<typename _ForwardIterator, typename _Tp, typename _Compare>
> _GLIBCXX20_CONSTEXPR
> _ForwardIterator
>@@ -1659,10 +1726,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> __glibcxx_requires_valid_range(__first1, __last1);
> __glibcxx_requires_valid_range(__first2, __last2);
>
>- return std::__lexicographical_compare_aux(std::__niter_base(__first1),
>- std::__niter_base(__last1),
>- std::__niter_base(__first2),
>- std::__niter_base(__last2));
>+ return std::__lexicographical_compare_aux(__first1, __last1,
>+ __first2, __last2) < 0;
Why does __lexicographical_compare_aux need to change to return int?
It looks like only __lexicographical_compare_aux1 gets called
recursively for deque iterators, so only that needs to be able to
return -1/0/+1 values.
> }
>
> /**
>@@ -1692,7 +1757,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
>
> return std::__lexicographical_compare_impl
> (__first1, __last1, __first2, __last2,
>- __gnu_cxx::__ops::__iter_comp_iter(__comp));
>+ __gnu_cxx::__ops::__iter_comp_iter(__comp)) < 0;
> }
>
> #if __cpp_lib_three_way_comparison
>diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
>index 888ac803ae5..ca4e2d52d1d 100644
>--- a/libstdc++-v3/include/debug/safe_iterator.tcc
>+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
>@@ -470,6 +470,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> return __equal_aux1(__first1, __last1, __first2);
> }
>
>+ template<typename _Ite1, typename _Seq1, typename _Cat1,
>+ typename _II2>
>+ int
>+ __lexicographical_compare_aux(
>+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
>+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
>+ _II2 __first2, _II2 __last2)
>+ {
>+ typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
>+ __glibcxx_check_valid_range2(__first1, __last1, __dist1);
>+ __glibcxx_check_valid_range(__first2, __last2);
>+
>+ if (__dist1.second > ::__gnu_debug::__dp_equality)
>+ return std::__lexicographical_compare_aux(__first1.base(),
>+ __last1.base(),
>+ __first2, __last2);
>+ return std::__lexicographical_compare_aux1(__first1, __last1,
>+ __first2, __last2);
>+ }
>+
>+ template<typename _II1,
>+ typename _Ite2, typename _Seq2, typename _Cat2>
>+ int
>+ __lexicographical_compare_aux(
>+ _II1 __first1, _II1 __last1,
>+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2,
>+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
>+ {
>+ __glibcxx_check_valid_range(__first1, __last1);
>+ typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist2;
>+ __glibcxx_check_valid_range2(__first2, __last2, __dist2);
>+
>+ if (__dist2.second > ::__gnu_debug::__dp_equality)
>+ return std::__lexicographical_compare_aux(__first1, __last1,
>+ __first2.base(),
>+ __last2.base());
>+ return std::__lexicographical_compare_aux1(__first1, __last1,
>+ __first2, __last2);
>+ }
>+
>+ template<typename _Ite1, typename _Seq1, typename _Cat1,
>+ typename _Ite2, typename _Seq2, typename _Cat2>
>+ int
>+ __lexicographical_compare_aux(
>+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
>+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
>+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2,
>+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
>+ {
>+ typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
>+ __glibcxx_check_valid_range2(__first1, __last1, __dist1);
>+ typename ::__gnu_debug::_Distance_traits<_Ite2>::__type __dist2;
>+ __glibcxx_check_valid_range2(__first2, __last2, __dist2);
>+
>+ if (__dist1.second > ::__gnu_debug::__dp_equality)
>+ {
>+ if (__dist2.second > ::__gnu_debug::__dp_equality)
>+ return std::__lexicographical_compare_aux(__first1.base(),
>+ __last1.base(),
>+ __first2.base(),
>+ __last2.base());
>+ return std::__lexicographical_compare_aux(__first1.base(),
>+ __last1.base(),
>+ __first2, __last2);
>+ }
>+
>+ if (__dist2.second > ::__gnu_debug::__dp_equality)
>+ return std::__lexicographical_compare_aux(__first1, __last1,
>+ __first2.base(),
>+ __last2.base());
>+ return std::__lexicographical_compare_aux1(__first1, __last1,
>+ __first2, __last2);
>+ }
>+
> _GLIBCXX_END_NAMESPACE_VERSION
> } // namespace std
>
>diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
>index 8c2f043f943..b8f92bacd85 100644
>--- a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
>+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
>@@ -74,6 +74,29 @@ test5()
> con2.begin(), con2.end()) );
> }
>
>+void
>+test6()
>+{
>+ VERIFY( std::lexicographical_compare(array2, array2 + 2,
>+ array3, array3 + 3) );
>+ VERIFY( !std::lexicographical_compare(array3, array3 + 3,
>+ array2, array2 + 2) );
>+}
>+
>+using __gnu_test::random_access_iterator_wrapper;
>+typedef test_container<int, random_access_iterator_wrapper> RaiContainer;
Since last week you can use __gnu_test::random_access_container<int>
for this.
>+void
>+test7()
>+{
>+ RaiContainer con2(array2, array2 + 2);
>+ RaiContainer con3(array3, array3 + 3);
>+ VERIFY( std::lexicographical_compare(con2.begin(), con2.end(),
>+ con3.begin(), con3.end()) );
>+ VERIFY( !std::lexicographical_compare(con3.begin(), con3.end(),
>+ con2.begin(), con2.end()) );
>+}
>+
> int
> main()
> {
>@@ -82,4 +105,6 @@ main()
> test3();
> test4();
> test5();
>+ test6();
>+ test7();
> }
>diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc
>new file mode 100644
>index 00000000000..c686ad5677d
>--- /dev/null
>+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc
>@@ -0,0 +1,134 @@
>+// Copyright (C) 2020 Free Software Foundation, Inc.
>+//
>+// This file is part of the GNU ISO C++ Library. This library is free
>+// software; you can redistribute it and/or modify it under the
>+// terms of the GNU General Public License as published by the
>+// Free Software Foundation; either version 3, or (at your option)
>+// any later version.
>+
>+// This library is distributed in the hope that it will be useful,
>+// but WITHOUT ANY WARRANTY; without even the implied warranty of
>+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
>+// GNU General Public License for more details.
>+
>+// You should have received a copy of the GNU General Public License along
>+// with this library; see the file COPYING3. If not see
>+// <http://www.gnu.org/licenses/>.
>+
>+#include <algorithm>
>+#include <vector>
>+#include <deque>
>+
>+#include <ext/new_allocator.h>
>+#include <ext/malloc_allocator.h>
>+
>+#include <testsuite_hooks.h>
>+
>+void test01()
>+{
>+ using namespace std;
>+
>+ deque<int> d;
>+ for (int i = 0; i != _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i)
>+ d.push_back(i);
>+
>+ const deque<int>& cd = d;
>+
>+ VERIFY( !lexicographical_compare(cd.begin(), cd.end(), cd.begin(), cd.end()) );
>+ VERIFY( !lexicographical_compare(cd.begin(), cd.end(), d.begin(), d.end()) );
>+ VERIFY( !lexicographical_compare(d.begin(), d.end(), d.begin(), d.end()) );
>+ VERIFY( !lexicographical_compare(d.begin(), d.end(), cd.begin(), cd.end()) );
>+}
>+
>+void test02()
>+{
>+ using namespace std;
>+
>+ deque<int> d;
>+ for (int i = 0; i != 1000; ++i)
>+ d.push_back(i % 10);
>+
>+ VERIFY( !lexicographical_compare(d.begin(), d.begin() + 10,
>+ d.begin() + 20, d.begin() + 30) );
>+ VERIFY( lexicographical_compare(d.begin(), d.begin() + 10,
>+ d.begin() + 20, d.begin() + 31) );
>+ VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10,
>+ d.begin(), d.end() - 20) );
>+
>+ const deque<int>& cd = d;
>+
>+ VERIFY( !lexicographical_compare(cd.begin(), cd.begin() + 10,
>+ cd.begin() + 20, cd.begin() + 30) );
>+ VERIFY( !lexicographical_compare(cd.begin() + 10, cd.end() - 10,
>+ d.begin(), d.end() - 20) );
>+ VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10,
>+ cd.begin(), cd.end() - 20) );
>+}
>+
>+void test03()
>+{
>+ using namespace std;
>+
>+ deque<int> d1;
>+ for (int i = 0; i != 1000; ++i)
>+ d1.push_back(i % 10);
>+
>+ deque<int> d2(d1);
>+ for (int i = 0; i != 10; ++i)
>+ d2.pop_front();
>+
>+ VERIFY( !lexicographical_compare(d1.begin(), d1.begin() + 10,
>+ d2.begin(), d2.begin() + 10) );
>+ VERIFY( !lexicographical_compare(d1.begin() + 10, d1.end() - 10,
>+ d2.begin(), d2.end() - 10) );
>+
>+ const deque<int>& cd1 = d1;
>+ const deque<int>& cd2 = d2;
>+
>+ VERIFY( !lexicographical_compare(cd1.begin(), cd1.begin() + 10,
>+ cd2.begin() + 20, cd2.begin() + 30) );
>+ VERIFY( !lexicographical_compare(cd1.begin() + 10, cd1.end() - 10,
>+ d2.begin(), d2.end() - 10) );
>+ VERIFY( lexicographical_compare(cd2.begin() + 10, cd2.end() - 10,
>+ cd1.begin(), cd1.end() - 20) );
>+}
>+
>+void test04()
>+{
>+ using namespace std;
>+
>+ deque<int> d;
>+ for (int i = 0; i != 1024; ++i)
>+ d.push_back(i);
>+
>+ vector<int> v(d.begin(), d.end());
>+
>+ VERIFY( lexicographical_compare(d.begin() + 5, d.end() - 1, v.begin() + 5, v.end()) );
>+ VERIFY( !lexicographical_compare(v.begin(), v.end(), d.begin(), d.end()) );
>+
>+ const deque<int>& cd = d;
>+
>+ VERIFY( !lexicographical_compare(cd.begin(), cd.end(), v.begin(), v.end()) );
>+ VERIFY( !lexicographical_compare(v.begin(), v.end(), cd.begin(), cd.end()) );
>+}
>+
>+void test05()
>+{
>+ using namespace std;
>+
>+ int a[] = { 0, 1, 2, 3, 4 };
>+ deque<int, __gnu_cxx::new_allocator<int> > d1(a, a + 5);
>+ deque<int, __gnu_cxx::malloc_allocator<int> > d2(a, a + 5);
>+
>+ VERIFY( !lexicographical_compare(d1.begin(), d1.end(), d2.begin(), d2.end()) );
>+}
>+
>+int main()
>+{
>+ test01();
>+ test02();
>+ test03();
>+ test04();
>+ test05();
>+ return 0;
>+}
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: libstdc++: Extend memcmp optimization in std::lexicographical_compare
2020-06-05 20:24 libstdc++: Extend memcmp optimization in std::lexicographical_compare François Dumont
2020-06-08 18:20 ` Jonathan Wakely
@ 2020-06-08 20:07 ` Jonathan Wakely
2020-06-08 21:05 ` Jonathan Wakely
1 sibling, 1 reply; 19+ messages in thread
From: Jonathan Wakely @ 2020-06-08 20:07 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On 05/06/20 22:24 +0200, François Dumont via Libstdc++ wrote:
>diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
>index 888ac803ae5..ca4e2d52d1d 100644
>--- a/libstdc++-v3/include/debug/safe_iterator.tcc
>+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
>@@ -470,6 +470,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> return __equal_aux1(__first1, __last1, __first2);
> }
>
>+ template<typename _Ite1, typename _Seq1, typename _Cat1,
>+ typename _II2>
>+ int
>+ __lexicographical_compare_aux(
>+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
>+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
>+ _II2 __first2, _II2 __last2)
>+ {
>+ typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
>+ __glibcxx_check_valid_range2(__first1, __last1, __dist1);
>+ __glibcxx_check_valid_range(__first2, __last2);
>+
>+ if (__dist1.second > ::__gnu_debug::__dp_equality)
>+ return std::__lexicographical_compare_aux(__first1.base(),
>+ __last1.base(),
>+ __first2, __last2);
>+ return std::__lexicographical_compare_aux1(__first1, __last1,
>+ __first2, __last2);
What's the rationale for the choice of whether to call aux or aux1
here?
It seems to be that if we know [first1, last1) is a valid range, we
use aux with the unsafe iterators (which means we do overload
resolution again for all the overloads that include _Safe_iterator,
but we know we don't have safe iterators now). Otherwise, if we don't
know it's a valid range, we call aux1 with the safe iterators.
Why don't we use aux1 in both cases?
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: libstdc++: Extend memcmp optimization in std::lexicographical_compare
2020-06-08 20:07 ` Jonathan Wakely
@ 2020-06-08 21:05 ` Jonathan Wakely
0 siblings, 0 replies; 19+ messages in thread
From: Jonathan Wakely @ 2020-06-08 21:05 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On 08/06/20 21:07 +0100, Jonathan Wakely wrote:
>On 05/06/20 22:24 +0200, François Dumont via Libstdc++ wrote:
>>diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
>>index 888ac803ae5..ca4e2d52d1d 100644
>>--- a/libstdc++-v3/include/debug/safe_iterator.tcc
>>+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
>>@@ -470,6 +470,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>> return __equal_aux1(__first1, __last1, __first2);
>> }
>>
>>+ template<typename _Ite1, typename _Seq1, typename _Cat1,
>>+ typename _II2>
>>+ int
>>+ __lexicographical_compare_aux(
>>+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
>>+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
>>+ _II2 __first2, _II2 __last2)
>>+ {
>>+ typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
>>+ __glibcxx_check_valid_range2(__first1, __last1, __dist1);
>>+ __glibcxx_check_valid_range(__first2, __last2);
>>+
>>+ if (__dist1.second > ::__gnu_debug::__dp_equality)
>>+ return std::__lexicographical_compare_aux(__first1.base(),
>>+ __last1.base(),
>>+ __first2, __last2);
>>+ return std::__lexicographical_compare_aux1(__first1, __last1,
>>+ __first2, __last2);
>
>What's the rationale for the choice of whether to call aux or aux1
>here?
>
>It seems to be that if we know [first1, last1) is a valid range, we
>use aux with the unsafe iterators (which means we do overload
>resolution again for all the overloads that include _Safe_iterator,
>but we know we don't have safe iterators now). Otherwise, if we don't
>know it's a valid range, we call aux1 with the safe iterators.
>
>Why don't we use aux1 in both cases?
Oh, is it because aux will still use __niter_base and so turn
__normal_iterator arguments into pointers?
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: libstdc++: Extend memcmp optimization in std::lexicographical_compare
2020-06-08 18:20 ` Jonathan Wakely
@ 2020-06-08 21:08 ` Jonathan Wakely
2020-06-08 23:02 ` Jonathan Wakely
2020-06-09 10:24 ` Jonathan Wakely
2020-06-09 20:20 ` François Dumont
2 siblings, 1 reply; 19+ messages in thread
From: Jonathan Wakely @ 2020-06-08 21:08 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 667 bytes --]
On 08/06/20 19:20 +0100, Jonathan Wakely wrote:
>On 05/06/20 22:24 +0200, François Dumont via Libstdc++ wrote:
>>Hi
>>
>>Â Â Â Here is the last of my algo patches this time to extend the
>>memcmp optimization to std::deque iterators and _GLIBCXX_DEBUG mode.
>>
>>Â Â Â To do so I had to return int in implementation details of
>>lexicographical_compare to make sure we can treat a deque iterator
>>range by chunk in a performant way.
Here's a simpler version, which doesn't alter anything for the
existing code (i.e. all iterators that aren't deque iterators) and
also fixes the infinite loop bug.
This seems simpler and less invasive.
Please take a look.
[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 20609 bytes --]
commit b7c4d633e875ccd2b3141f1b74d062fea11ab2c0
Author: Fran??ois Dumont <fdumont@gcc.gnu.org>
Date: Mon Jun 8 21:58:14 2020 +0100
libstdc++: Extend memcmp optimization in std::lexicographical_compare
Make the memcmp optimization work for std::deque iterators and safe
iterators.
Co-authored-by: Jonathan Wakely <jwakely@redhat.com>
libstdc++-v3/ChangeLog:
2020-06-08 Fran??ois Dumont <fdumont@gcc.gnu.org>
Jonathan Wakely <jwakely@redhat.com>
* include/bits/deque.tcc (__lex_cmp_dit): New.
(__lexicographical_compare_aux1): Define overloads for deque
iterators.
* include/bits/stl_algobase.h (__lexicographical_compare::__3way):
New static member function.
(__lexicographical_compare<true>::__3way): Likewise.
(__lexicographical_compare<true>::__lc): Use __3way.
(__lexicographical_compare_aux): Rename to
__lexicographical_compare_aux1 and declare overloads for deque
iterators.
(__lexicographical_compare_aux): Define new forwarding function
that calls __lexicographical_compare_aux1 and declare new overloads
for safe iterators.
(lexicographical_compare): Do not use __niter_base on
parameters.
* include/debug/safe_iterator.tcc
(__lexicographical_compare_aux): Define overloads for safe
iterators.
* testsuite/25_algorithms/lexicographical_compare/1.cc: Add
checks with random access iterators.
* testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc:
New test.
diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
index 1d32a1691c7..ac7f281e04c 100644
--- a/libstdc++-v3/include/bits/deque.tcc
+++ b/libstdc++-v3/include/bits/deque.tcc
@@ -1261,6 +1261,107 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
return true;
}
+ template<typename _Tp1, typename _Ref, typename _Ptr, typename _Tp2>
+ int
+ __lex_cmp_dit(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __last1,
+ const _Tp2* __first2, const _Tp2* __last2)
+ {
+ const bool __simple =
+ (__is_byte<_Tp1>::__value && __is_byte<_Tp2>::__value
+ && !__gnu_cxx::__numeric_traits<_Tp1>::__is_signed
+ && !__gnu_cxx::__numeric_traits<_Tp2>::__is_signed
+ && __is_pointer<_Ptr>::__value
+#if __cplusplus > 201703L && __cpp_lib_concepts
+ // For C++20 iterator_traits<volatile T*>::value_type is non-volatile
+ // so __is_byte<T> could be true, but we can't use memcmp with
+ // volatile data.
+ && !is_volatile_v<_Tp1>
+ && !is_volatile_v<_Tp2>
+#endif
+ );
+ typedef std::__lexicographical_compare<__simple> _Lc;
+
+ while (__first1._M_node != __last1._M_node)
+ {
+ const ptrdiff_t __len1 = __first1._M_last - __first1._M_cur;
+ const ptrdiff_t __len2 = __last2 - __first2;
+ const ptrdiff_t __len = std::min(__len1, __len2);
+ // if __len1 > __len2 this will return a positive value:
+ if (int __ret = _Lc::__3way(__first1._M_cur, __first1._M_last,
+ __first2, __first2 + __len))
+ return __ret;
+
+ __first1 += __len;
+ __first2 += __len;
+ }
+ return _Lc::__3way(__first1._M_cur, __last1._M_cur,
+ __first2, __last2);
+ }
+
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2>
+ inline bool
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
+ _Tp2* __first2, _Tp2* __last2)
+ { return std::__lex_cmp_dit(__first1, __last1, __first2, __last2) < 0; }
+
+ template<typename _Tp1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ inline bool
+ __lexicographical_compare_aux1(_Tp1* __first1, _Tp1* __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
+ { return std::__lex_cmp_dit(__first2, __last2, __first1, __last1) > 0; }
+
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ inline bool
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
+ {
+ const bool __simple =
+ (__is_byte<_Tp1>::__value && __is_byte<_Tp2>::__value
+ && !__gnu_cxx::__numeric_traits<_Tp1>::__is_signed
+ && !__gnu_cxx::__numeric_traits<_Tp2>::__is_signed
+ && __is_pointer<_Ptr1>::__value
+ && __is_pointer<_Ptr2>::__value
+#if __cplusplus > 201703L && __cpp_lib_concepts
+ // For C++20 iterator_traits<volatile T*>::value_type is non-volatile
+ // so __is_byte<T> could be true, but we can't use memcmp with
+ // volatile data.
+ && !is_volatile_v<_Tp1>
+ && !is_volatile_v<_Tp2>
+#endif
+ );
+ typedef std::__lexicographical_compare<__simple> _Lc;
+
+ while (__first1 != __last1 && __first2 != __last2)
+ {
+ const ptrdiff_t __len1 = __first1._M_node == __last1._M_node
+ ? __last1._M_cur - __first1._M_cur
+ : __first1._M_last - __first1._M_cur;
+ const ptrdiff_t __len2 = __first2._M_node == __last2._M_node
+ ? __last2._M_cur - __first2._M_cur
+ : __first2._M_last - __first2._M_cur;
+ const ptrdiff_t __len = std::min(__len1, __len2);
+ if (int __ret = _Lc::__3way(__first1._M_cur, __first1._M_cur + __len,
+ __first2._M_cur, __first2._M_cur + __len))
+ return __ret;
+
+ __first1 += __len;
+ __first2 += __len;
+ }
+
+ return (__last1 - __first1) - (__last2 - __first2);
+ }
+
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 0163d8f902d..3bdfece0929 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -1313,6 +1313,25 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
__first2, __last2,
__iter_less_iter());
}
+
+ template<typename _II1, typename _II2>
+ _GLIBCXX20_CONSTEXPR
+ static int
+ __3way(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
+ {
+ while (__first1 != __last1)
+ {
+ if (__first2 == __last2)
+ return +1;
+ if (*__first1 < *__first2)
+ return -1;
+ if (*__first2 < *__first1)
+ return +1;
+ ++__first1;
+ ++__first2;
+ }
+ return int(__first2 == __last2) - 1;
+ }
};
template<>
@@ -1323,21 +1342,28 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
static bool
__lc(const _Tp* __first1, const _Tp* __last1,
const _Up* __first2, const _Up* __last2)
+ { return __3way(__first1, __last1, __first2, __last2) < 0; }
+
+ template<typename _Tp, typename _Up>
+ _GLIBCXX20_CONSTEXPR
+ static ptrdiff_t
+ __3way(const _Tp* __first1, const _Tp* __last1,
+ const _Up* __first2, const _Up* __last2)
{
const size_t __len1 = __last1 - __first1;
const size_t __len2 = __last2 - __first2;
if (const size_t __len = std::min(__len1, __len2))
if (int __result = std::__memcmp(__first1, __first2, __len))
- return __result < 0;
- return __len1 < __len2;
+ return __result;
+ return ptrdiff_t(__len1 - __len2);
}
};
template<typename _II1, typename _II2>
_GLIBCXX20_CONSTEXPR
inline bool
- __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
- _II2 __first2, _II2 __last2)
+ __lexicographical_compare_aux1(_II1 __first1, _II1 __last1,
+ _II2 __first2, _II2 __last2)
{
typedef typename iterator_traits<_II1>::value_type _ValueType1;
typedef typename iterator_traits<_II2>::value_type _ValueType2;
@@ -1360,6 +1386,67 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
__first2, __last2);
}
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2>
+ bool
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _Tp2*, _Tp2*);
+
+ template<typename _Tp1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ bool
+ __lexicographical_compare_aux1(_Tp1*, _Tp1*,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
+
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ bool
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
+
+ template<typename _II1, typename _II2>
+ _GLIBCXX20_CONSTEXPR
+ inline bool
+ __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
+ _II2 __first2, _II2 __last2)
+ {
+ return std::__lexicographical_compare_aux1(std::__niter_base(__first1),
+ std::__niter_base(__last1),
+ std::__niter_base(__first2),
+ std::__niter_base(__last2));
+ }
+
+ template<typename _Iter1, typename _Seq1, typename _Cat1,
+ typename _II2>
+ bool
+ __lexicographical_compare_aux(
+ const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
+ const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
+ _II2, _II2);
+
+ template<typename _II1,
+ typename _Iter2, typename _Seq2, typename _Cat2>
+ bool
+ __lexicographical_compare_aux(
+ _II1, _II1,
+ const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
+ const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
+
+ template<typename _Iter1, typename _Seq1, typename _Cat1,
+ typename _Iter2, typename _Seq2, typename _Cat2>
+ bool
+ __lexicographical_compare_aux(
+ const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
+ const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
+ const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
+ const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
+
template<typename _ForwardIterator, typename _Tp, typename _Compare>
_GLIBCXX20_CONSTEXPR
_ForwardIterator
@@ -1659,10 +1746,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
__glibcxx_requires_valid_range(__first1, __last1);
__glibcxx_requires_valid_range(__first2, __last2);
- return std::__lexicographical_compare_aux(std::__niter_base(__first1),
- std::__niter_base(__last1),
- std::__niter_base(__first2),
- std::__niter_base(__last2));
+ return std::__lexicographical_compare_aux(__first1, __last1,
+ __first2, __last2);
}
/**
diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
index 888ac803ae5..db6a301655f 100644
--- a/libstdc++-v3/include/debug/safe_iterator.tcc
+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
@@ -470,6 +470,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return __equal_aux1(__first1, __last1, __first2);
}
+ template<typename _Ite1, typename _Seq1, typename _Cat1,
+ typename _II2>
+ int
+ __lexicographical_compare_aux(
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
+ _II2 __first2, _II2 __last2)
+ {
+ typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
+ __glibcxx_check_valid_range2(__first1, __last1, __dist1);
+ __glibcxx_check_valid_range(__first2, __last2);
+
+ if (__dist1.second > ::__gnu_debug::__dp_equality)
+ return std::__lexicographical_compare_aux(__first1.base(),
+ __last1.base(),
+ __first2, __last2);
+ return std::__lexicographical_compare_aux1(__first1, __last1,
+ __first2, __last2);
+ }
+
+ template<typename _II1,
+ typename _Ite2, typename _Seq2, typename _Cat2>
+ int
+ __lexicographical_compare_aux(
+ _II1 __first1, _II1 __last1,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
+ {
+ __glibcxx_check_valid_range(__first1, __last1);
+ typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist2;
+ __glibcxx_check_valid_range2(__first2, __last2, __dist2);
+
+ if (__dist2.second > ::__gnu_debug::__dp_equality)
+ return std::__lexicographical_compare_aux(__first1, __last1,
+ __first2.base(),
+ __last2.base());
+ return std::__lexicographical_compare_aux1(__first1, __last1,
+ __first2, __last2);
+ }
+
+ template<typename _Ite1, typename _Seq1, typename _Cat1,
+ typename _Ite2, typename _Seq2, typename _Cat2>
+ int
+ __lexicographical_compare_aux(
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
+ {
+ typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
+ __glibcxx_check_valid_range2(__first1, __last1, __dist1);
+ typename ::__gnu_debug::_Distance_traits<_Ite2>::__type __dist2;
+ __glibcxx_check_valid_range2(__first2, __last2, __dist2);
+
+ if (__dist1.second > ::__gnu_debug::__dp_equality)
+ {
+ if (__dist2.second > ::__gnu_debug::__dp_equality)
+ return std::__lexicographical_compare_aux(__first1.base(),
+ __last1.base(),
+ __first2.base(),
+ __last2.base());
+ return std::__lexicographical_compare_aux(__first1.base(),
+ __last1.base(),
+ __first2, __last2);
+ }
+
+ if (__dist2.second > ::__gnu_debug::__dp_equality)
+ return std::__lexicographical_compare_aux(__first1, __last1,
+ __first2.base(),
+ __last2.base());
+ return std::__lexicographical_compare_aux1(__first1, __last1,
+ __first2, __last2);
+ }
+
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
index 8c2f043f943..9bbc83b7af0 100644
--- a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
@@ -74,7 +74,30 @@ test5()
con2.begin(), con2.end()) );
}
-int
+void
+test6()
+{
+ VERIFY( std::lexicographical_compare(array2, array2 + 2,
+ array3, array3 + 3) );
+ VERIFY( !std::lexicographical_compare(array3, array3 + 3,
+ array2, array2 + 2) );
+}
+
+using __gnu_test::random_access_iterator_wrapper;
+typedef test_container<int, random_access_iterator_wrapper> RaiContainer;
+
+void
+test7()
+{
+ RaiContainer con2(array2, array2 + 2);
+ RaiContainer con3(array3, array3 + 3);
+ VERIFY( std::lexicographical_compare(con2.begin(), con2.end(),
+ con3.begin(), con3.end()) );
+ VERIFY( !std::lexicographical_compare(con3.begin(), con3.end(),
+ con2.begin(), con2.end()) );
+}
+
+int
main()
{
test1();
@@ -82,4 +105,6 @@ main()
test3();
test4();
test5();
+ test6();
+ test7();
}
diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc
new file mode 100644
index 00000000000..a8fe4b70958
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc
@@ -0,0 +1,157 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <algorithm>
+#include <vector>
+#include <deque>
+
+#include <ext/new_allocator.h>
+#include <ext/malloc_allocator.h>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i)
+ d.push_back(i);
+
+ const deque<int>& cd = d;
+
+ VERIFY( !lexicographical_compare(cd.begin(), cd.end(), cd.begin(), cd.end()) );
+ VERIFY( !lexicographical_compare(cd.begin(), cd.end(), d.begin(), d.end()) );
+ VERIFY( !lexicographical_compare(d.begin(), d.end(), d.begin(), d.end()) );
+ VERIFY( !lexicographical_compare(d.begin(), d.end(), cd.begin(), cd.end()) );
+}
+
+void test02()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != 1000; ++i)
+ d.push_back(i % 10);
+
+ VERIFY( lexicographical_compare(d.begin(), d.begin() + 10,
+ d.begin() + 21, d.begin() + 31) );
+ VERIFY( lexicographical_compare(d.begin() + 1, d.begin() + 10,
+ d.begin() + 21, d.begin() + 32) );
+ VERIFY( !lexicographical_compare(d.begin(), d.begin() + 10,
+ d.begin() + 20, d.begin() + 30) );
+ VERIFY( !lexicographical_compare(d.begin() + 1, d.begin() + 10,
+ d.begin() + 1 + 20, d.begin() + 30) );
+ VERIFY( lexicographical_compare(d.begin(), d.begin() + 10,
+ d.begin() + 20, d.begin() + 31) );
+ VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10,
+ d.begin(), d.end() - 20) );
+
+ const deque<int>& cd = d;
+
+ VERIFY( lexicographical_compare(cd.begin(), cd.begin() + 10,
+ cd.begin() + 21, cd.begin() + 31) );
+ VERIFY( lexicographical_compare(cd.begin() + 1, cd.begin() + 10,
+ cd.begin() + 21, cd.begin() + 32) );
+ VERIFY( !lexicographical_compare(cd.begin(), cd.begin() + 10,
+ cd.begin() + 20, cd.begin() + 30) );
+ VERIFY( !lexicographical_compare(cd.begin() + 1, cd.begin() + 10,
+ cd.begin() + 21, cd.begin() + 30) );
+ VERIFY( !lexicographical_compare(cd.begin() + 10, cd.end() - 10,
+ d.begin(), d.end() - 20) );
+ VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10,
+ cd.begin(), cd.end() - 20) );
+}
+
+void test03()
+{
+ using namespace std;
+
+ deque<int> d1;
+ for (int i = 0; i != 1000; ++i)
+ d1.push_back(i % 10);
+
+ deque<int> d2(d1);
+ for (int i = 0; i != 10; ++i)
+ d2.pop_front();
+
+ VERIFY( !lexicographical_compare(d1.begin(), d1.begin() + 10,
+ d2.begin(), d2.begin() + 10) );
+ VERIFY( !lexicographical_compare(d1.begin() + 10, d1.end() - 10,
+ d2.begin(), d2.end() - 10) );
+
+ const deque<int>& cd1 = d1;
+ const deque<int>& cd2 = d2;
+
+ VERIFY( !lexicographical_compare(cd1.begin(), cd1.begin() + 10,
+ cd2.begin() + 20, cd2.begin() + 30) );
+ VERIFY( !lexicographical_compare(cd1.begin() + 10, cd1.end() - 10,
+ d2.begin(), d2.end() - 10) );
+ VERIFY( lexicographical_compare(cd2.begin() + 10, cd2.end() - 10,
+ cd1.begin(), cd1.end() - 20) );
+}
+
+void test04()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ vector<int> v(d.begin(), d.end());
+
+ VERIFY( lexicographical_compare(d.begin() + 5, d.end() - 1, v.begin() + 5, v.end()) );
+ VERIFY( !lexicographical_compare(v.begin(), v.end(), d.begin(), d.end()) );
+
+ const deque<int>& cd = d;
+
+ VERIFY( !lexicographical_compare(cd.begin(), cd.end(), v.begin(), v.end()) );
+ VERIFY( !lexicographical_compare(v.begin(), v.end(), cd.begin(), cd.end()) );
+}
+
+void test05()
+{
+ using namespace std;
+
+ int a[] = { 0, 1, 2, 3, 4 };
+ deque<int, __gnu_cxx::new_allocator<int> > d1(a, a + 5);
+ deque<int, __gnu_cxx::malloc_allocator<int> > d2(a, a + 5);
+
+ VERIFY( !lexicographical_compare(d1.begin(), d1.end(), d2.begin(), d2.end()) );
+}
+
+void
+test06()
+{
+ using namespace std;
+
+ deque<int> d;
+ int i = 0;
+ VERIFY( lexicographical_compare(d.begin(), d.end(), &i, &i + 1) );
+ VERIFY( !lexicographical_compare(&i, &i + 1, d.begin(), d.end()) );
+}
+
+int main()
+{
+ test01();
+ test02();
+ test03();
+ test04();
+ test05();
+ test06();
+}
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: libstdc++: Extend memcmp optimization in std::lexicographical_compare
2020-06-08 21:08 ` Jonathan Wakely
@ 2020-06-08 23:02 ` Jonathan Wakely
2020-06-09 16:11 ` Jonathan Wakely
0 siblings, 1 reply; 19+ messages in thread
From: Jonathan Wakely @ 2020-06-08 23:02 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On 08/06/20 22:08 +0100, Jonathan Wakely wrote:
>On 08/06/20 19:20 +0100, Jonathan Wakely wrote:
>>On 05/06/20 22:24 +0200, François Dumont via Libstdc++ wrote:
>>>Hi
>>>
>>>Â Â Â Here is the last of my algo patches this time to extend the
>>>memcmp optimization to std::deque iterators and _GLIBCXX_DEBUG
>>>mode.
>>>
>>>Â Â Â To do so I had to return int in implementation details of
>>>lexicographical_compare to make sure we can treat a deque iterator
>>>range by chunk in a performant way.
>
>Here's a simpler version, which doesn't alter anything for the
>existing code (i.e. all iterators that aren't deque iterators) and
>also fixes the infinite loop bug.
>
>This seems simpler and less invasive.
>
>Please take a look.
I've actually tested it in debug mode now, and ...
>diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
>index 888ac803ae5..db6a301655f 100644
>--- a/libstdc++-v3/include/debug/safe_iterator.tcc
>+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
>@@ -470,6 +470,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> return __equal_aux1(__first1, __last1, __first2);
> }
>
>+ template<typename _Ite1, typename _Seq1, typename _Cat1,
>+ typename _II2>
>+ int
This should return bool here.
>+ __lexicographical_compare_aux(
>+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
>+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
>+ _II2 __first2, _II2 __last2)
>+ {
>+ typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
>+ __glibcxx_check_valid_range2(__first1, __last1, __dist1);
>+ __glibcxx_check_valid_range(__first2, __last2);
>+
>+ if (__dist1.second > ::__gnu_debug::__dp_equality)
>+ return std::__lexicographical_compare_aux(__first1.base(),
>+ __last1.base(),
>+ __first2, __last2);
>+ return std::__lexicographical_compare_aux1(__first1, __last1,
>+ __first2, __last2);
>+ }
>+
>+ template<typename _II1,
>+ typename _Ite2, typename _Seq2, typename _Cat2>
>+ int
And here.
>+ __lexicographical_compare_aux(
>+ _II1 __first1, _II1 __last1,
>+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2,
>+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
>+ {
>+ __glibcxx_check_valid_range(__first1, __last1);
>+ typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist2;
>+ __glibcxx_check_valid_range2(__first2, __last2, __dist2);
>+
>+ if (__dist2.second > ::__gnu_debug::__dp_equality)
>+ return std::__lexicographical_compare_aux(__first1, __last1,
>+ __first2.base(),
>+ __last2.base());
>+ return std::__lexicographical_compare_aux1(__first1, __last1,
>+ __first2, __last2);
>+ }
>+
>+ template<typename _Ite1, typename _Seq1, typename _Cat1,
>+ typename _Ite2, typename _Seq2, typename _Cat2>
>+ int
And here.
>+ __lexicographical_compare_aux(
>+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
>+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
>+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2,
>+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
>+ {
>+ typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
>+ __glibcxx_check_valid_range2(__first1, __last1, __dist1);
>+ typename ::__gnu_debug::_Distance_traits<_Ite2>::__type __dist2;
>+ __glibcxx_check_valid_range2(__first2, __last2, __dist2);
>+
>+ if (__dist1.second > ::__gnu_debug::__dp_equality)
>+ {
>+ if (__dist2.second > ::__gnu_debug::__dp_equality)
>+ return std::__lexicographical_compare_aux(__first1.base(),
>+ __last1.base(),
>+ __first2.base(),
>+ __last2.base());
>+ return std::__lexicographical_compare_aux(__first1.base(),
>+ __last1.base(),
>+ __first2, __last2);
>+ }
>+
>+ if (__dist2.second > ::__gnu_debug::__dp_equality)
>+ return std::__lexicographical_compare_aux(__first1, __last1,
>+ __first2.base(),
>+ __last2.base());
>+ return std::__lexicographical_compare_aux1(__first1, __last1,
>+ __first2, __last2);
>+ }
>+
> _GLIBCXX_END_NAMESPACE_VERSION
> } // namespace std
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: libstdc++: Extend memcmp optimization in std::lexicographical_compare
2020-06-08 18:20 ` Jonathan Wakely
2020-06-08 21:08 ` Jonathan Wakely
@ 2020-06-09 10:24 ` Jonathan Wakely
2020-06-09 20:35 ` François Dumont
2020-06-09 20:20 ` François Dumont
2 siblings, 1 reply; 19+ messages in thread
From: Jonathan Wakely @ 2020-06-09 10:24 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On 08/06/20 19:20 +0100, Jonathan Wakely wrote:
>On 05/06/20 22:24 +0200, François Dumont via Libstdc++ wrote:
>>Hi
>>
>>Â Â Â Here is the last of my algo patches this time to extend the
>>memcmp optimization to std::deque iterators and _GLIBCXX_DEBUG mode.
>>
>>Â Â Â To do so I had to return int in implementation details of
>>lexicographical_compare to make sure we can treat a deque iterator
>>range by chunk in a performant way.
>>
>>Tested under Linux x86_64 normal and debug modes.
>>
>>Â Â Â Â Â Â Â Â Â Â Â * include/bits/stl_algobase.h
>>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_impl): Return int.
>>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare::__lc): Likewise.
>>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux1(_II1, _II1, _II2, _II2)): New.
>>(__lexicographical_compare_aux1(_Deque_iterator<>, _Deque_iterator<>,
>>Â Â Â Â Â Â Â Â Â Â Â _II2, _II2)): Declare.
>>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux1(_II1, _II1,
>>Â Â Â Â Â Â Â Â Â Â Â _Deque_iterator<>, _Deque_iterator<>)): Declare.
>>(__lexicographical_compare_aux1(_Deque_iterator<>, _Deque_iterator<>,
>>Â Â Â Â Â Â Â Â Â Â Â _Deque_iterator<>, _Deque_iterator<>)): Declare.
>>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux): Adapt, call later.
>
>Is this meant to say "latter"? That's still not correct grammar
>though. I think it would be better to name the function it calls
>explicitly: "Call __lexicographical_compare_aux1."
>
>>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux(_Safe_iterator<>,
>>_Safe_iterator<>,
>>Â Â Â Â Â Â Â Â Â Â Â _II2, _II2)): Declare.
>>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux(_II1, _II1,
>>Â Â Â Â Â Â Â Â Â Â Â _Safe_iterator<>, _Safe_iterator<>)): Declare.
>>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux(_Safe_iterator<>,
>>_Safe_iterator<>,
>>Â Â Â Â Â Â Â Â Â Â Â _Safe_iterator<>, _Safe_iterator<>)): Declare.
>>Â Â Â Â Â Â Â Â Â Â Â (std::lexicographical_compare): Adapt, call later
>>without __niter_base
>>Â Â Â Â Â Â Â Â Â Â Â usage.
>>Â Â Â Â Â Â Â Â Â Â Â * include/bits/deque.tcc (__lex_cmp_dit): New.
>>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux1): New.
>>Â Â Â Â Â Â Â Â Â Â Â * include/debug/safe_iterator.tcc
>>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux(const _Safe_iterator<>&,
>>Â Â Â Â Â Â Â Â Â Â Â const _Safe_iterator<>&, _II2, _II2)): New.
>>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux(
>>Â Â Â Â Â Â Â Â Â Â Â const _Safe_iterator<>&, const_Safe_iterator<>&,
>>Â Â Â Â Â Â Â Â Â Â Â const _Safe_iterator<>&, const _Safe_iterator<>&)): New.
>>Â Â Â Â Â Â Â Â Â Â Â * testsuite/25_algorithms/lexicographical_compare/1.cc
>>(test6, test7):
>>Â Â Â Â Â Â Â Â Â Â Â New.
>>Â Â Â Â Â Â Â Â Â Â Â *
>>testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc:
>>Â Â Â Â Â Â Â Â Â Â Â New test.
>>
>>Ok to commit ?
>>
>>François
>>
>>
>
>>diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
>>index 1d32a1691c7..d7dbe64f3e1 100644
>>--- a/libstdc++-v3/include/bits/deque.tcc
>>+++ b/libstdc++-v3/include/bits/deque.tcc
>>@@ -1261,6 +1261,98 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>> return true;
>> }
>>
>>+ template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
>
>_II is the wrong name here, it mean InputIterator. All callers of this
>function are constrained for random access iterators. This cannot be
>called with an input iterator. Please use _RAIter.
>
>>+ int
>>+ __lex_cmp_dit(
>>+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __first1,
>>+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __last1,
>>+ _II __first2, _II __last2)
>>+ {
>>+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
>>+ typedef typename _Iter::difference_type difference_type;
>>+
>>+ if (__first1._M_node != __last1._M_node)
>>+ {
>>+ difference_type __len = __last2 - __first2;
>>+ difference_type __flen
>
>What does "flen" mean? Why not use len2 for last2 - first2, as we do
>elsewhere? And then use len for min(len1, len2)?
>
>
>>+ = std::min(__len, __first1._M_last - __first1._M_cur);
>>+ if (int __ret = std::__lexicographical_compare_aux1(
>
>This call (and the three later in this function) will do overload
>resolution again on the full set of __lexicographical_compare_aux1
>overloads, which includes the ones for deque iterators. But we know
>that __first1._M_cur and __first1._M_last are not deque iterators.
>
>__first2 could be a deque iterator, but I'm not sure if we really want
>one function that has to handle that case anyway.
>
>>+ __first1._M_cur, __first1._M_last, __first2, __first2 + __flen))
>>+ return __ret;
>>+
>>+ __first2 += __flen;
>>+ __len -= __flen;
>>+ __flen = std::min<size_t>(__len, _Iter::_S_buffer_size());
>>+ for (typename _Iter::_Map_pointer __node = __first1._M_node + 1;
>>+ __node != __last1._M_node;
>>+ __first2 += __flen, __len -= __flen,
>>+ __flen = std::min<size_t>(__len, _Iter::_S_buffer_size()),
>>+ ++__node)
>>+ if (int __ret = std::__lexicographical_compare_aux1(
>>+ *__node, *__node + _Iter::_S_buffer_size(),
>>+ __first2, __first2 + __flen))
>>+ return __ret;
>>+
>>+ return std::__lexicographical_compare_aux1(
>>+ __last1._M_first, __last1._M_cur, __first2, __last2);
>>+ }
>>+
>>+ return std::__lexicographical_compare_aux1(
>>+ __first1._M_cur, __last1._M_cur, __first2, __last2);
>>+ }
>>+
>>+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
>>+ typename _II2>
>
>This is not an input iterator either.
>
>>+ typename __gnu_cxx::__enable_if<
>>+ __is_random_access_iter<_II2>::__value, int>::__type
>
>This should be inline.
>
>Also, I'm curious why these overloads use __enable_if rather than the
>conventional approach of tag dispatching using iterator_category.
>(The same question applies to th __equal_aux1 and __copy_move_a1
>overloads for deque iterators as well). It doesn't really matter
>though.
>
>>+ __lexicographical_compare_aux1(
>>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
>>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
>>+ _II2 __first2, _II2 __last2)
>>+ { return std::__lex_cmp_dit(__first1, __last1, __first2, __last2); }
>>+
>>+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
>>+ typename _Tp2, typename _Ref2, typename _Ptr2>
>>+ int
>
>This should be inline.
>
>>+ __lexicographical_compare_aux1(
>>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
>>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
>>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
>>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
>>+ { return std::__lex_cmp_dit(__first1, __last1, __first2, __last2); }
>
>I'm not convinced it's useful for this function and the one above it
>to share the same logic.
>
>>+ template<typename _II1,
>>+ typename _Tp2, typename _Ref2, typename _Ptr2>
>>+ typename __gnu_cxx::__enable_if<
>>+ __is_random_access_iter<_II1>::__value, int>::__type
>>+ __lexicographical_compare_aux1(
>>+ _II1 __first1, _II1 __last1,
>>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
>>+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
>>+ {
>>+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> _Iter;
>>+ typedef typename _Iter::difference_type difference_type;
>>+
>>+ difference_type __len = __last1 - __first1;
>>+ while (__len > 0)
>>+ {
>>+ const difference_type __flen = __first2._M_node == __last2._M_node
>>+ ? __last2._M_cur - __first2._M_cur
>>+ : __first2._M_last - __first2._M_cur;
>>+ const difference_type __clen = std::min(__len, __flen);
>
>"flen"? "clen"?
>
>>+ if (int __ret = std::__lexicographical_compare_aux1(
>>+ __first1, __first1 + __clen,
>>+ __first2._M_cur, __first2._M_cur + __flen))
>>+ return __ret;
>>+
>>+ __first1 += __clen;
>>+ __len -= __clen;
>>+ __first2 += __clen;
>>+ }
>>+
>>+ return __first1 == __last1 ? (__first2 != __last2 ? -1 : 0) : 1;
>
>Isn't this function doing basically the same as __lex_cmp_dit? Why
>does it not use the same logic?
>
>Can this whole function just negate the result of __lex_cmp_dit called
>with the arguments switched?
>
> return -std::__lex_cmp_dit(__first2, __last2, __first1, __last1);
>
>That would also fix the bug that makes the following loop forever:
>
> std::deque<int> d;
> int i = 0;
> std::lexicographical_compare(&i, &i + 1, d.begin(), d.end());
Same question for __equal_aux1, why is it implemented twice? Why
doesn't __equal_aux1(_II f1, _II l1, _Deque_iterator<> f2) just call
__equal_aux1(f2, f2 + (l1 - f1), f1) ?
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: libstdc++: Extend memcmp optimization in std::lexicographical_compare
2020-06-08 23:02 ` Jonathan Wakely
@ 2020-06-09 16:11 ` Jonathan Wakely
2020-06-09 16:12 ` Jonathan Wakely
2020-06-09 20:42 ` François Dumont
0 siblings, 2 replies; 19+ messages in thread
From: Jonathan Wakely @ 2020-06-09 16:11 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On 09/06/20 00:02 +0100, Jonathan Wakely wrote:
>On 08/06/20 22:08 +0100, Jonathan Wakely wrote:
>>On 08/06/20 19:20 +0100, Jonathan Wakely wrote:
>>>On 05/06/20 22:24 +0200, François Dumont via Libstdc++ wrote:
>>>>Hi
>>>>
>>>>Â Â Â Here is the last of my algo patches this time to extend the
>>>>memcmp optimization to std::deque iterators and _GLIBCXX_DEBUG
>>>>mode.
>>>>
>>>>Â Â Â To do so I had to return int in implementation details of
>>>>lexicographical_compare to make sure we can treat a deque
>>>>iterator range by chunk in a performant way.
>>
>>Here's a simpler version, which doesn't alter anything for the
>>existing code (i.e. all iterators that aren't deque iterators) and
>>also fixes the infinite loop bug.
>>
>>This seems simpler and less invasive.
>>
>>Please take a look.
>
>I've actually tested it in debug mode now, and ...
>
>>diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
>>index 888ac803ae5..db6a301655f 100644
>>--- a/libstdc++-v3/include/debug/safe_iterator.tcc
>>+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
>>@@ -470,6 +470,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>> return __equal_aux1(__first1, __last1, __first2);
>> }
>>
>>+ template<typename _Ite1, typename _Seq1, typename _Cat1,
>>+ typename _II2>
>>+ int
>
>This should return bool here.
>
>>+ __lexicographical_compare_aux(
>>+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
>>+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
>>+ _II2 __first2, _II2 __last2)
>>+ {
>>+ typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
>>+ __glibcxx_check_valid_range2(__first1, __last1, __dist1);
>>+ __glibcxx_check_valid_range(__first2, __last2);
>>+
>>+ if (__dist1.second > ::__gnu_debug::__dp_equality)
>>+ return std::__lexicographical_compare_aux(__first1.base(),
>>+ __last1.base(),
>>+ __first2, __last2);
>>+ return std::__lexicographical_compare_aux1(__first1, __last1,
>>+ __first2, __last2);
>>+ }
>>+
>>+ template<typename _II1,
>>+ typename _Ite2, typename _Seq2, typename _Cat2>
>>+ int
>
>And here.
>
>>+ __lexicographical_compare_aux(
>>+ _II1 __first1, _II1 __last1,
>>+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2,
>>+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
>>+ {
>>+ __glibcxx_check_valid_range(__first1, __last1);
>>+ typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist2;
>>+ __glibcxx_check_valid_range2(__first2, __last2, __dist2);
>>+
>>+ if (__dist2.second > ::__gnu_debug::__dp_equality)
>>+ return std::__lexicographical_compare_aux(__first1, __last1,
>>+ __first2.base(),
>>+ __last2.base());
>>+ return std::__lexicographical_compare_aux1(__first1, __last1,
>>+ __first2, __last2);
>>+ }
>>+
>>+ template<typename _Ite1, typename _Seq1, typename _Cat1,
>>+ typename _Ite2, typename _Seq2, typename _Cat2>
>>+ int
>
>And here.
And I've also enhanced the tests so they catch the bug I created where
the __lexicographical_compare_aux1 overload taking two ranges of deque
iterators was still trying to return a three-way result, rather than
bool.
Corrected patch attached.
But, the 25_algorithms/lexicographical_compare/deque_iterators/1.cc
test doesn't actually test the new code properly, because it only uses
deque<int> which means memcmp isn't even used. We need better tests.
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: libstdc++: Extend memcmp optimization in std::lexicographical_compare
2020-06-09 16:11 ` Jonathan Wakely
@ 2020-06-09 16:12 ` Jonathan Wakely
2020-06-09 20:42 ` François Dumont
1 sibling, 0 replies; 19+ messages in thread
From: Jonathan Wakely @ 2020-06-09 16:12 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 3686 bytes --]
On 09/06/20 17:11 +0100, Jonathan Wakely wrote:
>On 09/06/20 00:02 +0100, Jonathan Wakely wrote:
>>On 08/06/20 22:08 +0100, Jonathan Wakely wrote:
>>>On 08/06/20 19:20 +0100, Jonathan Wakely wrote:
>>>>On 05/06/20 22:24 +0200, François Dumont via Libstdc++ wrote:
>>>>>Hi
>>>>>
>>>>>Â Â Â Here is the last of my algo patches this time to extend
>>>>>the memcmp optimization to std::deque iterators and
>>>>>_GLIBCXX_DEBUG mode.
>>>>>
>>>>>Â Â Â To do so I had to return int in implementation details of
>>>>>lexicographical_compare to make sure we can treat a deque
>>>>>iterator range by chunk in a performant way.
>>>
>>>Here's a simpler version, which doesn't alter anything for the
>>>existing code (i.e. all iterators that aren't deque iterators) and
>>>also fixes the infinite loop bug.
>>>
>>>This seems simpler and less invasive.
>>>
>>>Please take a look.
>>
>>I've actually tested it in debug mode now, and ...
>>
>>>diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
>>>index 888ac803ae5..db6a301655f 100644
>>>--- a/libstdc++-v3/include/debug/safe_iterator.tcc
>>>+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
>>>@@ -470,6 +470,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>> return __equal_aux1(__first1, __last1, __first2);
>>> }
>>>
>>>+ template<typename _Ite1, typename _Seq1, typename _Cat1,
>>>+ typename _II2>
>>>+ int
>>
>>This should return bool here.
>>
>>>+ __lexicographical_compare_aux(
>>>+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
>>>+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
>>>+ _II2 __first2, _II2 __last2)
>>>+ {
>>>+ typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
>>>+ __glibcxx_check_valid_range2(__first1, __last1, __dist1);
>>>+ __glibcxx_check_valid_range(__first2, __last2);
>>>+
>>>+ if (__dist1.second > ::__gnu_debug::__dp_equality)
>>>+ return std::__lexicographical_compare_aux(__first1.base(),
>>>+ __last1.base(),
>>>+ __first2, __last2);
>>>+ return std::__lexicographical_compare_aux1(__first1, __last1,
>>>+ __first2, __last2);
>>>+ }
>>>+
>>>+ template<typename _II1,
>>>+ typename _Ite2, typename _Seq2, typename _Cat2>
>>>+ int
>>
>>And here.
>>
>>>+ __lexicographical_compare_aux(
>>>+ _II1 __first1, _II1 __last1,
>>>+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2,
>>>+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
>>>+ {
>>>+ __glibcxx_check_valid_range(__first1, __last1);
>>>+ typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist2;
>>>+ __glibcxx_check_valid_range2(__first2, __last2, __dist2);
>>>+
>>>+ if (__dist2.second > ::__gnu_debug::__dp_equality)
>>>+ return std::__lexicographical_compare_aux(__first1, __last1,
>>>+ __first2.base(),
>>>+ __last2.base());
>>>+ return std::__lexicographical_compare_aux1(__first1, __last1,
>>>+ __first2, __last2);
>>>+ }
>>>+
>>>+ template<typename _Ite1, typename _Seq1, typename _Cat1,
>>>+ typename _Ite2, typename _Seq2, typename _Cat2>
>>>+ int
>>
>>And here.
>
>And I've also enhanced the tests so they catch the bug I created where
>the __lexicographical_compare_aux1 overload taking two ranges of deque
>iterators was still trying to return a three-way result, rather than
>bool.
>
>Corrected patch attached.
*Really* attached this time.
>But, the 25_algorithms/lexicographical_compare/deque_iterators/1.cc
>test doesn't actually test the new code properly, because it only uses
>deque<int> which means memcmp isn't even used. We need better tests.
>
>
[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 22343 bytes --]
commit 4d501ba840194a28799cb83bcd8aaecd0eec5304
Author: Fran??ois Dumont <fdumont@gcc.gnu.org>
Date: Tue Jun 9 00:01:51 2020 +0100
libstdc++: Extend memcmp optimization in std::lexicographical_compare
Make the memcmp optimization work for std::deque iterators and safe
iterators.
Co-authored-by: Jonathan Wakely <jwakely@redhat.com>
libstdc++-v3/ChangeLog:
2020-06-08 Fran??ois Dumont <fdumont@gcc.gnu.org>
Jonathan Wakely <jwakely@redhat.com>
* include/bits/deque.tcc (__lex_cmp_dit): New.
(__lexicographical_compare_aux1): Define overloads for deque
iterators.
* include/bits/stl_algobase.h (__lexicographical_compare::__3way):
New static member function.
(__lexicographical_compare<true>::__3way): Likewise.
(__lexicographical_compare<true>::__lc): Use __3way.
(__lexicographical_compare_aux): Rename to
__lexicographical_compare_aux1 and declare overloads for deque
iterators.
(__lexicographical_compare_aux): Define new forwarding function
that calls __lexicographical_compare_aux1 and declare new overloads
for safe iterators.
(lexicographical_compare): Do not use __niter_base on
parameters.
* include/debug/safe_iterator.tcc
(__lexicographical_compare_aux): Define overloads for safe
iterators.
* testsuite/25_algorithms/lexicographical_compare/1.cc: Add
checks with random access iterators.
* testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc:
New test.
diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
index 1d32a1691c7..7d1ec86456a 100644
--- a/libstdc++-v3/include/bits/deque.tcc
+++ b/libstdc++-v3/include/bits/deque.tcc
@@ -1261,6 +1261,109 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
return true;
}
+ template<typename _Tp1, typename _Ref, typename _Ptr, typename _Tp2>
+ int
+ __lex_cmp_dit(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __last1,
+ const _Tp2* __first2, const _Tp2* __last2)
+ {
+ const bool __simple =
+ (__is_byte<_Tp1>::__value && __is_byte<_Tp2>::__value
+ && !__gnu_cxx::__numeric_traits<_Tp1>::__is_signed
+ && !__gnu_cxx::__numeric_traits<_Tp2>::__is_signed
+ && __is_pointer<_Ptr>::__value
+#if __cplusplus > 201703L && __cpp_lib_concepts
+ // For C++20 iterator_traits<volatile T*>::value_type is non-volatile
+ // so __is_byte<T> could be true, but we can't use memcmp with
+ // volatile data.
+ && !is_volatile_v<_Tp1>
+ && !is_volatile_v<_Tp2>
+#endif
+ );
+ typedef std::__lexicographical_compare<__simple> _Lc;
+
+ while (__first1._M_node != __last1._M_node)
+ {
+ const ptrdiff_t __len1 = __first1._M_last - __first1._M_cur;
+ const ptrdiff_t __len2 = __last2 - __first2;
+ const ptrdiff_t __len = std::min(__len1, __len2);
+ // if __len1 > __len2 this will return a positive value:
+ if (int __ret = _Lc::__3way(__first1._M_cur, __first1._M_last,
+ __first2, __first2 + __len))
+ return __ret;
+
+ __first1 += __len;
+ __first2 += __len;
+ }
+ return _Lc::__3way(__first1._M_cur, __last1._M_cur,
+ __first2, __last2);
+ }
+
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2>
+ inline bool
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
+ _Tp2* __first2, _Tp2* __last2)
+ { return std::__lex_cmp_dit(__first1, __last1, __first2, __last2) < 0; }
+
+ template<typename _Tp1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ inline bool
+ __lexicographical_compare_aux1(_Tp1* __first1, _Tp1* __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
+ { return std::__lex_cmp_dit(__first2, __last2, __first1, __last1) > 0; }
+
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ inline bool
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
+ {
+ const bool __simple =
+ (__is_byte<_Tp1>::__value && __is_byte<_Tp2>::__value
+ && !__gnu_cxx::__numeric_traits<_Tp1>::__is_signed
+ && !__gnu_cxx::__numeric_traits<_Tp2>::__is_signed
+ && __is_pointer<_Ptr1>::__value
+ && __is_pointer<_Ptr2>::__value
+#if __cplusplus > 201703L && __cpp_lib_concepts
+ // For C++20 iterator_traits<volatile T*>::value_type is non-volatile
+ // so __is_byte<T> could be true, but we can't use memcmp with
+ // volatile data.
+ && !is_volatile_v<_Tp1>
+ && !is_volatile_v<_Tp2>
+#endif
+ );
+ typedef std::__lexicographical_compare<__simple> _Lc;
+
+ while (__first1 != __last1)
+ {
+ const ptrdiff_t __len2 = __first2._M_node == __last2._M_node
+ ? __last2._M_cur - __first2._M_cur
+ : __first2._M_last - __first2._M_cur;
+ if (__len2 == 0)
+ return false;
+ const ptrdiff_t __len1 = __first1._M_node == __last1._M_node
+ ? __last1._M_cur - __first1._M_cur
+ : __first1._M_last - __first1._M_cur;
+ const ptrdiff_t __len = std::min(__len1, __len2);
+ if (int __ret = _Lc::__3way(__first1._M_cur, __first1._M_cur + __len,
+ __first2._M_cur, __first2._M_cur + __len))
+ return __ret < 0;
+
+ __first1 += __len;
+ __first2 += __len;
+ }
+
+ return __last2 != __first2;
+ }
+
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 0163d8f902d..41dd740d34a 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -1313,6 +1313,25 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
__first2, __last2,
__iter_less_iter());
}
+
+ template<typename _II1, typename _II2>
+ _GLIBCXX20_CONSTEXPR
+ static int
+ __3way(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
+ {
+ while (__first1 != __last1)
+ {
+ if (__first2 == __last2)
+ return +1;
+ if (*__first1 < *__first2)
+ return -1;
+ if (*__first2 < *__first1)
+ return +1;
+ ++__first1;
+ ++__first2;
+ }
+ return int(__first2 == __last2) - 1;
+ }
};
template<>
@@ -1323,21 +1342,28 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
static bool
__lc(const _Tp* __first1, const _Tp* __last1,
const _Up* __first2, const _Up* __last2)
+ { return __3way(__first1, __last1, __first2, __last2) < 0; }
+
+ template<typename _Tp, typename _Up>
+ _GLIBCXX20_CONSTEXPR
+ static ptrdiff_t
+ __3way(const _Tp* __first1, const _Tp* __last1,
+ const _Up* __first2, const _Up* __last2)
{
const size_t __len1 = __last1 - __first1;
const size_t __len2 = __last2 - __first2;
if (const size_t __len = std::min(__len1, __len2))
if (int __result = std::__memcmp(__first1, __first2, __len))
- return __result < 0;
- return __len1 < __len2;
+ return __result;
+ return ptrdiff_t(__len1 - __len2);
}
};
template<typename _II1, typename _II2>
_GLIBCXX20_CONSTEXPR
inline bool
- __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
- _II2 __first2, _II2 __last2)
+ __lexicographical_compare_aux1(_II1 __first1, _II1 __last1,
+ _II2 __first2, _II2 __last2)
{
typedef typename iterator_traits<_II1>::value_type _ValueType1;
typedef typename iterator_traits<_II2>::value_type _ValueType2;
@@ -1360,6 +1386,67 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
__first2, __last2);
}
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2>
+ bool
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _Tp2*, _Tp2*);
+
+ template<typename _Tp1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ bool
+ __lexicographical_compare_aux1(_Tp1*, _Tp1*,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
+
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ bool
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
+
+ template<typename _II1, typename _II2>
+ _GLIBCXX20_CONSTEXPR
+ inline bool
+ __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
+ _II2 __first2, _II2 __last2)
+ {
+ return std::__lexicographical_compare_aux1(std::__niter_base(__first1),
+ std::__niter_base(__last1),
+ std::__niter_base(__first2),
+ std::__niter_base(__last2));
+ }
+
+ template<typename _Iter1, typename _Seq1, typename _Cat1,
+ typename _II2>
+ bool
+ __lexicographical_compare_aux(
+ const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
+ const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
+ _II2, _II2);
+
+ template<typename _II1,
+ typename _Iter2, typename _Seq2, typename _Cat2>
+ bool
+ __lexicographical_compare_aux(
+ _II1, _II1,
+ const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
+ const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
+
+ template<typename _Iter1, typename _Seq1, typename _Cat1,
+ typename _Iter2, typename _Seq2, typename _Cat2>
+ bool
+ __lexicographical_compare_aux(
+ const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
+ const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
+ const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
+ const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
+
template<typename _ForwardIterator, typename _Tp, typename _Compare>
_GLIBCXX20_CONSTEXPR
_ForwardIterator
@@ -1659,10 +1746,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
__glibcxx_requires_valid_range(__first1, __last1);
__glibcxx_requires_valid_range(__first2, __last2);
- return std::__lexicographical_compare_aux(std::__niter_base(__first1),
- std::__niter_base(__last1),
- std::__niter_base(__first2),
- std::__niter_base(__last2));
+ return std::__lexicographical_compare_aux(__first1, __last1,
+ __first2, __last2);
}
/**
diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
index 888ac803ae5..f694e514239 100644
--- a/libstdc++-v3/include/debug/safe_iterator.tcc
+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
@@ -470,6 +470,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return __equal_aux1(__first1, __last1, __first2);
}
+ template<typename _Ite1, typename _Seq1, typename _Cat1,
+ typename _II2>
+ bool
+ __lexicographical_compare_aux(
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
+ _II2 __first2, _II2 __last2)
+ {
+ typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
+ __glibcxx_check_valid_range2(__first1, __last1, __dist1);
+ __glibcxx_check_valid_range(__first2, __last2);
+
+ if (__dist1.second > ::__gnu_debug::__dp_equality)
+ return std::__lexicographical_compare_aux(__first1.base(),
+ __last1.base(),
+ __first2, __last2);
+ return std::__lexicographical_compare_aux1(__first1, __last1,
+ __first2, __last2);
+ }
+
+ template<typename _II1,
+ typename _Ite2, typename _Seq2, typename _Cat2>
+ bool
+ __lexicographical_compare_aux(
+ _II1 __first1, _II1 __last1,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
+ {
+ __glibcxx_check_valid_range(__first1, __last1);
+ typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist2;
+ __glibcxx_check_valid_range2(__first2, __last2, __dist2);
+
+ if (__dist2.second > ::__gnu_debug::__dp_equality)
+ return std::__lexicographical_compare_aux(__first1, __last1,
+ __first2.base(),
+ __last2.base());
+ return std::__lexicographical_compare_aux1(__first1, __last1,
+ __first2, __last2);
+ }
+
+ template<typename _Ite1, typename _Seq1, typename _Cat1,
+ typename _Ite2, typename _Seq2, typename _Cat2>
+ bool
+ __lexicographical_compare_aux(
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
+ {
+ typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
+ __glibcxx_check_valid_range2(__first1, __last1, __dist1);
+ typename ::__gnu_debug::_Distance_traits<_Ite2>::__type __dist2;
+ __glibcxx_check_valid_range2(__first2, __last2, __dist2);
+
+ if (__dist1.second > ::__gnu_debug::__dp_equality)
+ {
+ if (__dist2.second > ::__gnu_debug::__dp_equality)
+ return std::__lexicographical_compare_aux(__first1.base(),
+ __last1.base(),
+ __first2.base(),
+ __last2.base());
+ return std::__lexicographical_compare_aux(__first1.base(),
+ __last1.base(),
+ __first2, __last2);
+ }
+
+ if (__dist2.second > ::__gnu_debug::__dp_equality)
+ return std::__lexicographical_compare_aux(__first1, __last1,
+ __first2.base(),
+ __last2.base());
+ return std::__lexicographical_compare_aux1(__first1, __last1,
+ __first2, __last2);
+ }
+
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
index 8c2f043f943..9bbc83b7af0 100644
--- a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
@@ -29,43 +29,43 @@ int array1[] = {0, 1};
int array2[] = {1, 0};
int array3[] = {1, 0, 1};
-void
+void
test1()
{
Container con1(array1, array1);
Container con2(array2, array2);
- VERIFY( !std::lexicographical_compare(con1.begin(), con1.end(),
+ VERIFY( !std::lexicographical_compare(con1.begin(), con1.end(),
con2.begin(), con2.end()) );
}
-void
+void
test2()
{
Container con1(array1, array1 + 2);
Container con2(array2, array2 + 2);
- VERIFY( std::lexicographical_compare(con1.begin(), con1.end(),
+ VERIFY( std::lexicographical_compare(con1.begin(), con1.end(),
con2.begin(), con2.end()) );
}
-void
+void
test3()
{
Container con1(array1, array1 + 2);
Container con2(array2, array2 + 2);
- VERIFY( !std::lexicographical_compare(con2.begin(), con2.end(),
+ VERIFY( !std::lexicographical_compare(con2.begin(), con2.end(),
con1.begin(), con1.end()) );
}
-void
+void
test4()
{
Container con3(array3, array3 + 3);
Container con2(array2, array2 + 2);
- VERIFY( std::lexicographical_compare(con2.begin(), con2.end(),
+ VERIFY( std::lexicographical_compare(con2.begin(), con2.end(),
con3.begin(), con3.end()) );
}
-void
+void
test5()
{
Container con3(array3, array3 + 3);
@@ -74,7 +74,30 @@ test5()
con2.begin(), con2.end()) );
}
-int
+void
+test6()
+{
+ VERIFY( std::lexicographical_compare(array2, array2 + 2,
+ array3, array3 + 3) );
+ VERIFY( !std::lexicographical_compare(array3, array3 + 3,
+ array2, array2 + 2) );
+}
+
+using __gnu_test::random_access_iterator_wrapper;
+typedef test_container<int, random_access_iterator_wrapper> RaiContainer;
+
+void
+test7()
+{
+ RaiContainer con2(array2, array2 + 2);
+ RaiContainer con3(array3, array3 + 3);
+ VERIFY( std::lexicographical_compare(con2.begin(), con2.end(),
+ con3.begin(), con3.end()) );
+ VERIFY( !std::lexicographical_compare(con3.begin(), con3.end(),
+ con2.begin(), con2.end()) );
+}
+
+int
main()
{
test1();
@@ -82,4 +105,6 @@ main()
test3();
test4();
test5();
+ test6();
+ test7();
}
diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc
new file mode 100644
index 00000000000..1d5c758fc61
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc
@@ -0,0 +1,165 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <algorithm>
+#include <vector>
+#include <deque>
+
+#include <ext/new_allocator.h>
+#include <ext/malloc_allocator.h>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i)
+ d.push_back(i);
+
+ const deque<int>& cd = d;
+
+ VERIFY( !lexicographical_compare(cd.begin(), cd.end(), cd.begin(), cd.end()) );
+ VERIFY( !lexicographical_compare(cd.begin(), cd.end(), d.begin(), d.end()) );
+ VERIFY( !lexicographical_compare(d.begin(), d.end(), d.begin(), d.end()) );
+ VERIFY( !lexicographical_compare(d.begin(), d.end(), cd.begin(), cd.end()) );
+
+ const deque<int>::iterator first = d.begin(), last = d.end();
+ VERIFY( lexicographical_compare(first, last - 1, first, last) );
+ VERIFY( !lexicographical_compare(first, last, first, last - 1) );
+ VERIFY( lexicographical_compare(first, last, first + 1, last) );
+ VERIFY( !lexicographical_compare(first + 1, last, first, last) );
+}
+
+void test02()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != 1000; ++i)
+ d.push_back(i % 10);
+
+ VERIFY( lexicographical_compare(d.begin(), d.begin() + 10,
+ d.begin() + 21, d.begin() + 31) );
+ VERIFY( lexicographical_compare(d.begin(), d.begin() + 10,
+ d.begin() + 20, d.begin() + 31) );
+ VERIFY( ! lexicographical_compare(d.begin() + 1, d.begin() + 10,
+ d.begin() + 21, d.begin() + 30) );
+ VERIFY( !lexicographical_compare(d.begin(), d.begin() + 10,
+ d.begin() + 20, d.begin() + 30) );
+ VERIFY( !lexicographical_compare(d.begin() + 1, d.begin() + 10,
+ d.begin() + 1 + 20, d.begin() + 30) );
+ VERIFY( lexicographical_compare(d.begin(), d.begin() + 10,
+ d.begin() + 20, d.begin() + 31) );
+ VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10,
+ d.begin(), d.end() - 20) );
+
+ const deque<int>& cd = d;
+
+ VERIFY( lexicographical_compare(cd.begin(), cd.begin() + 10,
+ cd.begin() + 21, cd.begin() + 31) );
+ VERIFY( lexicographical_compare(cd.begin() + 1, cd.begin() + 10,
+ cd.begin() + 21, cd.begin() + 32) );
+ VERIFY( !lexicographical_compare(cd.begin(), cd.begin() + 10,
+ cd.begin() + 20, cd.begin() + 30) );
+ VERIFY( !lexicographical_compare(cd.begin() + 1, cd.begin() + 10,
+ cd.begin() + 21, cd.begin() + 30) );
+ VERIFY( !lexicographical_compare(cd.begin() + 10, cd.end() - 10,
+ d.begin(), d.end() - 20) );
+ VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10,
+ cd.begin(), cd.end() - 20) );
+}
+
+void test03()
+{
+ using namespace std;
+
+ deque<int> d1;
+ for (int i = 0; i != 1000; ++i)
+ d1.push_back(i % 10);
+
+ deque<int> d2(d1);
+ for (int i = 0; i != 10; ++i)
+ d2.pop_front();
+
+ VERIFY( !lexicographical_compare(d1.begin(), d1.begin() + 10,
+ d2.begin(), d2.begin() + 10) );
+ VERIFY( !lexicographical_compare(d1.begin() + 10, d1.end() - 10,
+ d2.begin(), d2.end() - 10) );
+
+ const deque<int>& cd1 = d1;
+ const deque<int>& cd2 = d2;
+
+ VERIFY( !lexicographical_compare(cd1.begin(), cd1.begin() + 10,
+ cd2.begin() + 20, cd2.begin() + 30) );
+ VERIFY( !lexicographical_compare(cd1.begin() + 10, cd1.end() - 10,
+ d2.begin(), d2.end() - 10) );
+ VERIFY( lexicographical_compare(cd2.begin() + 10, cd2.end() - 10,
+ cd1.begin(), cd1.end() - 20) );
+}
+
+void test04()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ vector<int> v(d.begin(), d.end());
+
+ VERIFY( lexicographical_compare(d.begin() + 5, d.end() - 1, v.begin() + 5, v.end()) );
+ VERIFY( !lexicographical_compare(v.begin(), v.end(), d.begin(), d.end()) );
+
+ const deque<int>& cd = d;
+
+ VERIFY( !lexicographical_compare(cd.begin(), cd.end(), v.begin(), v.end()) );
+ VERIFY( !lexicographical_compare(v.begin(), v.end(), cd.begin(), cd.end()) );
+}
+
+void test05()
+{
+ using namespace std;
+
+ int a[] = { 0, 1, 2, 3, 4 };
+ deque<int, __gnu_cxx::new_allocator<int> > d1(a, a + 5);
+ deque<int, __gnu_cxx::malloc_allocator<int> > d2(a, a + 5);
+
+ VERIFY( !lexicographical_compare(d1.begin(), d1.end(), d2.begin(), d2.end()) );
+}
+
+void
+test06()
+{
+ using namespace std;
+
+ deque<int> d;
+ int i = 0;
+ VERIFY( lexicographical_compare(d.begin(), d.end(), &i, &i + 1) );
+ VERIFY( !lexicographical_compare(&i, &i + 1, d.begin(), d.end()) );
+}
+
+int main()
+{
+ test01();
+ test02();
+ test03();
+ test04();
+ test05();
+ test06();
+}
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: libstdc++: Extend memcmp optimization in std::lexicographical_compare
2020-06-08 18:20 ` Jonathan Wakely
2020-06-08 21:08 ` Jonathan Wakely
2020-06-09 10:24 ` Jonathan Wakely
@ 2020-06-09 20:20 ` François Dumont
2020-06-09 20:38 ` Jonathan Wakely
2 siblings, 1 reply; 19+ messages in thread
From: François Dumont @ 2020-06-09 20:20 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: libstdc++, gcc-patches
On 08/06/20 8:20 pm, Jonathan Wakely wrote:
> On 05/06/20 22:24 +0200, François Dumont via Libstdc++ wrote:
>> Hi
>>
>> Â Â Â Here is the last of my algo patches this time to extend the
>> memcmp optimization to std::deque iterators and _GLIBCXX_DEBUG mode.
>>
>> Â Â Â To do so I had to return int in implementation details of
>> lexicographical_compare to make sure we can treat a deque iterator
>> range by chunk in a performant way.
>>
>> Tested under Linux x86_64 normal and debug modes.
>>
>> Â Â Â Â Â Â Â Â Â Â Â * include/bits/stl_algobase.h
>> Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_impl): Return int.
>> Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare::__lc): Likewise.
>> Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux1(_II1, _II1,
>> _II2, _II2)): New.
>> (__lexicographical_compare_aux1(_Deque_iterator<>, _Deque_iterator<>,
>> Â Â Â Â Â Â Â Â Â Â Â _II2, _II2)): Declare.
>> Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux1(_II1, _II1,
>> Â Â Â Â Â Â Â Â Â Â Â _Deque_iterator<>, _Deque_iterator<>)): Declare.
>> (__lexicographical_compare_aux1(_Deque_iterator<>, _Deque_iterator<>,
>> Â Â Â Â Â Â Â Â Â Â Â _Deque_iterator<>, _Deque_iterator<>)): Declare.
>> Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux): Adapt, call
>> later.
>
> Is this meant to say "latter"? That's still not correct grammar
> though. I think it would be better to name the function it calls
> explicitly: "Call __lexicographical_compare_aux1."
Ok.
>
>> Â Â Â Â Â Â Â Â Â Â Â
>> (__lexicographical_compare_aux(_Safe_iterator<>, _Safe_iterator<>,
>> Â Â Â Â Â Â Â Â Â Â Â _II2, _II2)): Declare.
>> Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux(_II1, _II1,
>> Â Â Â Â Â Â Â Â Â Â Â _Safe_iterator<>, _Safe_iterator<>)): Declare.
>> Â Â Â Â Â Â Â Â Â Â Â
>> (__lexicographical_compare_aux(_Safe_iterator<>, _Safe_iterator<>,
>> Â Â Â Â Â Â Â Â Â Â Â _Safe_iterator<>, _Safe_iterator<>)): Declare.
>> Â Â Â Â Â Â Â Â Â Â Â (std::lexicographical_compare): Adapt, call
>> later without __niter_base
>> Â Â Â Â Â Â Â Â Â Â Â usage.
>> Â Â Â Â Â Â Â Â Â Â Â * include/bits/deque.tcc (__lex_cmp_dit): New.
>> Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux1): New.
>> Â Â Â Â Â Â Â Â Â Â Â * include/debug/safe_iterator.tcc
>> Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux(const
>> _Safe_iterator<>&,
>> Â Â Â Â Â Â Â Â Â Â Â const _Safe_iterator<>&, _II2, _II2)): New.
>> Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux(
>> Â Â Â Â Â Â Â Â Â Â Â const _Safe_iterator<>&, const_Safe_iterator<>&,
>> Â Â Â Â Â Â Â Â Â Â Â const _Safe_iterator<>&, const
>> _Safe_iterator<>&)): New.
>> Â Â Â Â Â Â Â Â Â Â Â *
>> testsuite/25_algorithms/lexicographical_compare/1.cc (test6, test7):
>> Â Â Â Â Â Â Â Â Â Â Â New.
>> Â Â Â Â Â Â Â Â Â Â Â *
>> testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc:
>> Â Â Â Â Â Â Â Â Â Â Â New test.
>>
>> Ok to commit ?
>>
>> François
>>
>>
>
>> diff --git a/libstdc++-v3/include/bits/deque.tcc
>> b/libstdc++-v3/include/bits/deque.tcc
>> index 1d32a1691c7..d7dbe64f3e1 100644
>> --- a/libstdc++-v3/include/bits/deque.tcc
>> +++ b/libstdc++-v3/include/bits/deque.tcc
>> @@ -1261,6 +1261,98 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>> return true;
>> }
>>
>> + template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
>
> _II is the wrong name here, it mean InputIterator. All callers of this
> function are constrained for random access iterators. This cannot be
> called with an input iterator. Please use _RAIter.
>
>> + int
>> + __lex_cmp_dit(
>> + const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __first1,
>> + const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __last1,
>> + _II __first2, _II __last2)
>> + {
>> + typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
>> + typedef typename _Iter::difference_type difference_type;
>> +
>> + if (__first1._M_node != __last1._M_node)
>> + {
>> + difference_type __len = __last2 - __first2;
>> + difference_type __flen
>
> What does "flen" mean? Why not use len2 for last2 - first2, as we do
> elsewhere? And then use len for min(len1, len2)?
short for 'first lenght' because it is the first iterator range.
len1/len2 is better of course.
>
>
>> + = std::min(__len, __first1._M_last - __first1._M_cur);
>> + if (int __ret = std::__lexicographical_compare_aux1(
>
> This call (and the three later in this function) will do overload
> resolution again on the full set of __lexicographical_compare_aux1
> overloads, which includes the ones for deque iterators. But we know
> that __first1._M_cur and __first1._M_last are not deque iterators.
>
> __first2 could be a deque iterator, but I'm not sure if we really want
> one function that has to handle that case anyway.
Considering the performance results on the std::copy algo it appeared to
me that just "unrolling" the deque iterator is already an enhancement.
Looping on pointers is better than looping on deque iterators.
Is it what you wonder ?
>
>> + __first1._M_cur, __first1._M_last, __first2, __first2 +
>> __flen))
>> + return __ret;
>> +
>> + __first2 += __flen;
>> + __len -= __flen;
>> + __flen = std::min<size_t>(__len, _Iter::_S_buffer_size());
>> + for (typename _Iter::_Map_pointer __node = __first1._M_node + 1;
>> + __node != __last1._M_node;
>> + __first2 += __flen, __len -= __flen,
>> + __flen = std::min<size_t>(__len, _Iter::_S_buffer_size()),
>> + ++__node)
>> + if (int __ret = std::__lexicographical_compare_aux1(
>> + *__node, *__node + _Iter::_S_buffer_size(),
>> + __first2, __first2 + __flen))
>> + return __ret;
>> +
>> + return std::__lexicographical_compare_aux1(
>> + __last1._M_first, __last1._M_cur, __first2, __last2);
>> + }
>> +
>> + return std::__lexicographical_compare_aux1(
>> + __first1._M_cur, __last1._M_cur, __first2, __last2);
>> + }
>> +
>> + template<typename _Tp1, typename _Ref1, typename _Ptr1,
>> + typename _II2>
>
> This is not an input iterator either.
>
>> + typename __gnu_cxx::__enable_if<
>> + __is_random_access_iter<_II2>::__value, int>::__type
>
> This should be inline.
>
> Also, I'm curious why these overloads use __enable_if rather than the
> conventional approach of tag dispatching using iterator_category.
> (The same question applies to th __equal_aux1 and __copy_move_a1
> overloads for deque iterators as well). It doesn't really matter
> though.
Those functions are using Rai operations like operator- so I thought
that they they should be enabled only on the right category of iterator.
Maybe overload would have been fine too.
Isn't it making overload resolution better ?
>
>> + __lexicographical_compare_aux1(
>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
>> + _II2 __first2, _II2 __last2)
>> + { return std::__lex_cmp_dit(__first1, __last1, __first2,
>> __last2); }
>> +
>> + template<typename _Tp1, typename _Ref1, typename _Ptr1,
>> + typename _Tp2, typename _Ref2, typename _Ptr2>
>> + int
>
> This should be inline.
>
>> + __lexicographical_compare_aux1(
>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
>> + { return std::__lex_cmp_dit(__first1, __last1, __first2,
>> __last2); }
>
> I'm not convinced it's useful for this function and the one above it
> to share the same logic.
This overload is here just to disambiguate a call with 4 deque iterators
cause in this case the compiler wouldn't know which of the 2 other
overloads to call. But I still want only 2 implementations, one when 1st
range are deque iterators and another when 2nd range are deque
iterators. I just chose that when I have 2 deque iterator ranges I'll
use the implementation where 1st range is such.
>
>> + template<typename _II1,
>> + typename _Tp2, typename _Ref2, typename _Ptr2>
>> + typename __gnu_cxx::__enable_if<
>> + __is_random_access_iter<_II1>::__value, int>::__type
>> + __lexicographical_compare_aux1(
>> + _II1 __first1, _II1 __last1,
>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
>> + {
>> + typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>
>> _Iter;
>> + typedef typename _Iter::difference_type difference_type;
>> +
>> + difference_type __len = __last1 - __first1;
>> + while (__len > 0)
>> + {
>> + const difference_type __flen = __first2._M_node ==
>> __last2._M_node
>> + ? __last2._M_cur - __first2._M_cur
>> + : __first2._M_last - __first2._M_cur;
>> + const difference_type __clen = std::min(__len, __flen);
>
> "flen"? "clen"?
just 'c' for const I think
>> + if (int __ret = std::__lexicographical_compare_aux1(
>> + __first1, __first1 + __clen,
>> + __first2._M_cur, __first2._M_cur + __flen))
>> + return __ret;
>> +
>> + __first1 += __clen;
>> + __len -= __clen;
>> + __first2 += __clen;
>> + }
>> +
>> + return __first1 == __last1 ? (__first2 != __last2 ? -1 : 0) : 1;
>
> Isn't this function doing basically the same as __lex_cmp_dit? Why
> does it not use the same logic?
>
> Can this whole function just negate the result of __lex_cmp_dit called
> with the arguments switched?
>
> return -std::__lex_cmp_dit(__first2, __last2, __first1, __last1);
>
> That would also fix the bug that makes the following loop forever:
>
> std::deque<int> d;
> int i = 0;
> std::lexicographical_compare(&i, &i + 1, d.begin(), d.end());
I have to consider this, I also wanted to cover comparison with raw
pointer ranges or vector iterators that could be replaced with memcmp.
>
>
>> + }
>> +
>> _GLIBCXX_END_NAMESPACE_VERSION
>> } // namespace std
>>
>> diff --git a/libstdc++-v3/include/bits/stl_algobase.h
>> b/libstdc++-v3/include/bits/stl_algobase.h
>> index 0163d8f902d..ecc50a10c9d 100644
>> --- a/libstdc++-v3/include/bits/stl_algobase.h
>> +++ b/libstdc++-v3/include/bits/stl_algobase.h
>> @@ -1279,7 +1279,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>>
>> template<typename _II1, typename _II2, typename _Compare>
>> _GLIBCXX20_CONSTEXPR
>> - bool
>> + int
>> __lexicographical_compare_impl(_II1 __first1, _II1 __last1,
>> _II2 __first2, _II2 __last2,
>> _Compare __comp)
>> @@ -1288,16 +1288,18 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>> typedef typename iterator_traits<_II2>::iterator_category
>> _Category2;
>> typedef std::__lc_rai<_Category1, _Category2> __rai_type;
>>
>> - __last1 = __rai_type::__newlast1(__first1, __last1, __first2,
>> __last2);
>> - for (; __first1 != __last1 && __rai_type::__cnd2(__first2,
>> __last2);
>> + _II1 __new_last1
>> + = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
>> + for (; __first1 != __new_last1 && __rai_type::__cnd2(__first2,
>> __last2);
>> ++__first1, (void)++__first2)
>> {
>> if (__comp(__first1, __first2))
>> - return true;
>> + return -1;
>> if (__comp(__first2, __first1))
>> - return false;
>> + return 1;
>> }
>> - return __first1 == __last1 && __first2 != __last2;
>> +
>> + return __first1 == __last1 ? (__first2 != __last2 ? -1 : 0) : 1;
>
> This is going to produce worse code for the common (non-deque) case,
> isn't it?
>
>
>> }
>>
>> template<bool _BoolType>
>> @@ -1305,7 +1307,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>> {
>> template<typename _II1, typename _II2>
>> _GLIBCXX20_CONSTEXPR
>> - static bool
>> + static int
>> __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
>> {
>> using __gnu_cxx::__ops::__iter_less_iter;
>> @@ -1320,7 +1322,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>> {
>> template<typename _Tp, typename _Up>
>> _GLIBCXX20_CONSTEXPR
>> - static bool
>> + static int
>> __lc(const _Tp* __first1, const _Tp* __last1,
>> const _Up* __first2, const _Up* __last2)
>> {
>> @@ -1328,16 +1330,44 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>> const size_t __len2 = __last2 - __first2;
>> if (const size_t __len = std::min(__len1, __len2))
>> if (int __result = std::__memcmp(__first1, __first2, __len))
>> - return __result < 0;
>> - return __len1 < __len2;
>> + return __result;
>> +
>> + return __len1 < __len2 ? -1 : (__len2 < __len1 ? 1 : 0);
>
> Again, this will produce worse code.
>
> If you made it return ptrdiff_t instead of int you could just do:
>
> return ptrdiff_t(__len1 - __len2);
>
> But I think we should just not change these __lc helpers, and not try
> to reuse them for deque iterators. We can define new helpers that
> return the 3-way result that is needed for comparing deque iterators.
>
Yes, it sounds promising.
>
>> + template<typename _Tp1, typename _Ref1, typename _Ptr1,
>> + typename _II2>
>> + typename __gnu_cxx::__enable_if<
>> + __is_random_access_iter<_II2>::__value, int>::__type
>> + __lexicographical_compare_aux1(
>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
>> + _II2, _II2);
>> +
>> + template<typename _II1,
>> + typename _Tp2, typename _Ref2, typename _Ptr2>
>> + typename __gnu_cxx::__enable_if<
>> + __is_random_access_iter<_II1>::__value, int>::__type
>> + __lexicographical_compare_aux1(
>> + _II1, _II1,
>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
>> +
>> + template<typename _Tp1, typename _Ref1, typename _Ptr1,
>> + typename _Tp2, typename _Ref2, typename _Ptr2>
>> + int
>> + __lexicographical_compare_aux1(
>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
>> +
>> template<typename _II1, typename _II2>
>> _GLIBCXX20_CONSTEXPR
>> - inline bool
>> - __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
>> - _II2 __first2, _II2 __last2)
>> + inline int
>> + __lexicographical_compare_aux1(_II1 __first1, _II1 __last1,
>> + _II2 __first2, _II2 __last2)
>
> If you rename this to __lexicographical_compare_aux2 instead and add
> a one-line forwarding function called __lexicographical_compare_aux1,
> then the code above for deque iterators can call the aux2 overload
> directly, to avoid doing overload resolution on aux1 again.
>
>> {
>> typedef typename iterator_traits<_II1>::value_type _ValueType1;
>> typedef typename iterator_traits<_II2>::value_type _ValueType2;
>> @@ -1360,6 +1390,43 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>> __first2, __last2);
>> }
>>
>> + template<typename _II1, typename _II2>
>> + _GLIBCXX20_CONSTEXPR
>> + inline int
>> + __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
>> + _II2 __first2, _II2 __last2)
>> + {
>> + return
>> std::__lexicographical_compare_aux1(std::__niter_base(__first1),
>> + std::__niter_base(__last1),
>> + std::__niter_base(__first2),
>> + std::__niter_base(__last2));
>> + }
>> +
>> + template<typename _Ite1, typename _Seq1, typename _Cat1,
>
> Please don't introduce any more "Ite" parameters, this should be _It1
> or _Iter1.
>
>> + typename _II2>
>> + int
>> + __lexicographical_compare_aux(
>> + const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
>> + const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
>> + _II2, _II2);
>> +
>> + template<typename _II1,
>> + typename _Ite2, typename _Seq2, typename _Cat2>
>> + int
>> + __lexicographical_compare_aux(
>> + _II1, _II1,
>> + const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&,
>> + const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&);
>> +
>> + template<typename _Ite1, typename _Seq1, typename _Cat1,
>> + typename _Ite2, typename _Seq2, typename _Cat2>
>> + int
>> + __lexicographical_compare_aux(
>> + const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
>> + const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
>> + const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&,
>> + const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&);
>> +
>> template<typename _ForwardIterator, typename _Tp, typename _Compare>
>> _GLIBCXX20_CONSTEXPR
>> _ForwardIterator
>> @@ -1659,10 +1726,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
>> __glibcxx_requires_valid_range(__first1, __last1);
>> __glibcxx_requires_valid_range(__first2, __last2);
>>
>> - return
>> std::__lexicographical_compare_aux(std::__niter_base(__first1),
>> - std::__niter_base(__last1),
>> - std::__niter_base(__first2),
>> - std::__niter_base(__last2));
>> + return std::__lexicographical_compare_aux(__first1, __last1,
>> + __first2, __last2) < 0;
>
> Why does __lexicographical_compare_aux need to change to return int?
>
> It looks like only __lexicographical_compare_aux1 gets called
> recursively for deque iterators, so only that needs to be able to
> return -1/0/+1 values.
>
Yes, I think I'll follow your idea based on your patch proposal.
>
>> }
>>
>> /**
>> @@ -1692,7 +1757,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
>>
>> return std::__lexicographical_compare_impl
>> (__first1, __last1, __first2, __last2,
>> - __gnu_cxx::__ops::__iter_comp_iter(__comp));
>> + __gnu_cxx::__ops::__iter_comp_iter(__comp)) < 0;
>> }
>>
>> #if __cpp_lib_three_way_comparison
>> diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc
>> b/libstdc++-v3/include/debug/safe_iterator.tcc
>> index 888ac803ae5..ca4e2d52d1d 100644
>> --- a/libstdc++-v3/include/debug/safe_iterator.tcc
>> +++ b/libstdc++-v3/include/debug/safe_iterator.tcc
>> @@ -470,6 +470,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>> return __equal_aux1(__first1, __last1, __first2);
>> }
>>
>> + template<typename _Ite1, typename _Seq1, typename _Cat1,
>> + typename _II2>
>> + int
>> + __lexicographical_compare_aux(
>> + const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
>> + const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
>> + _II2 __first2, _II2 __last2)
>> + {
>> + typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
>> + __glibcxx_check_valid_range2(__first1, __last1, __dist1);
>> + __glibcxx_check_valid_range(__first2, __last2);
>> +
>> + if (__dist1.second > ::__gnu_debug::__dp_equality)
>> + return std::__lexicographical_compare_aux(__first1.base(),
>> + __last1.base(),
>> + __first2, __last2);
>> + return std::__lexicographical_compare_aux1(__first1, __last1,
>> + __first2, __last2);
>> + }
>> +
>> + template<typename _II1,
>> + typename _Ite2, typename _Seq2, typename _Cat2>
>> + int
>> + __lexicographical_compare_aux(
>> + _II1 __first1, _II1 __last1,
>> + const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2,
>> + const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
>> + {
>> + __glibcxx_check_valid_range(__first1, __last1);
>> + typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist2;
>> + __glibcxx_check_valid_range2(__first2, __last2, __dist2);
>> +
>> + if (__dist2.second > ::__gnu_debug::__dp_equality)
>> + return std::__lexicographical_compare_aux(__first1, __last1,
>> + __first2.base(),
>> + __last2.base());
>> + return std::__lexicographical_compare_aux1(__first1, __last1,
>> + __first2, __last2);
>> + }
>> +
>> + template<typename _Ite1, typename _Seq1, typename _Cat1,
>> + typename _Ite2, typename _Seq2, typename _Cat2>
>> + int
>> + __lexicographical_compare_aux(
>> + const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
>> + const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
>> + const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2,
>> + const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
>> + {
>> + typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
>> + __glibcxx_check_valid_range2(__first1, __last1, __dist1);
>> + typename ::__gnu_debug::_Distance_traits<_Ite2>::__type __dist2;
>> + __glibcxx_check_valid_range2(__first2, __last2, __dist2);
>> +
>> + if (__dist1.second > ::__gnu_debug::__dp_equality)
>> + {
>> + if (__dist2.second > ::__gnu_debug::__dp_equality)
>> + return std::__lexicographical_compare_aux(__first1.base(),
>> + __last1.base(),
>> + __first2.base(),
>> + __last2.base());
>> + return std::__lexicographical_compare_aux(__first1.base(),
>> + __last1.base(),
>> + __first2, __last2);
>> + }
>> +
>> + if (__dist2.second > ::__gnu_debug::__dp_equality)
>> + return std::__lexicographical_compare_aux(__first1, __last1,
>> + __first2.base(),
>> + __last2.base());
>> + return std::__lexicographical_compare_aux1(__first1, __last1,
>> + __first2, __last2);
>> + }
>> +
>> _GLIBCXX_END_NAMESPACE_VERSION
>> } // namespace std
>>
>> diff --git
>> a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
>> b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
>> index 8c2f043f943..b8f92bacd85 100644
>> --- a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
>> +++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
>> @@ -74,6 +74,29 @@ test5()
>> con2.begin(), con2.end()) );
>> }
>>
>> +void
>> +test6()
>> +{
>> + VERIFY( std::lexicographical_compare(array2, array2 + 2,
>> + array3, array3 + 3) );
>> + VERIFY( !std::lexicographical_compare(array3, array3 + 3,
>> + array2, array2 + 2) );
>> +}
>> +
>> +using __gnu_test::random_access_iterator_wrapper;
>> +typedef test_container<int, random_access_iterator_wrapper>
>> RaiContainer;
>
> Since last week you can use __gnu_test::random_access_container<int>
> for this.
>
>> +void
>> +test7()
>> +{
>> + RaiContainer con2(array2, array2 + 2);
>> + RaiContainer con3(array3, array3 + 3);
>> + VERIFY( std::lexicographical_compare(con2.begin(), con2.end(),
>> + con3.begin(), con3.end()) );
>> + VERIFY( !std::lexicographical_compare(con3.begin(), con3.end(),
>> + con2.begin(), con2.end()) );
>> +}
>> +
>> int main()
>> {
>> @@ -82,4 +105,6 @@ main()
>> test3();
>> test4();
>> test5();
>> + test6();
>> + test7();
>> }
>> diff --git
>> a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc
>> b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc
>>
>> new file mode 100644
>> index 00000000000..c686ad5677d
>> --- /dev/null
>> +++
>> b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc
>> @@ -0,0 +1,134 @@
>> +// Copyright (C) 2020 Free Software Foundation, Inc.
>> +//
>> +// This file is part of the GNU ISO C++ Library. This library is free
>> +// software; you can redistribute it and/or modify it under the
>> +// terms of the GNU General Public License as published by the
>> +// Free Software Foundation; either version 3, or (at your option)
>> +// any later version.
>> +
>> +// This library is distributed in the hope that it will be useful,
>> +// but WITHOUT ANY WARRANTY; without even the implied warranty of
>> +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
>> +// GNU General Public License for more details.
>> +
>> +// You should have received a copy of the GNU General Public License
>> along
>> +// with this library; see the file COPYING3. If not see
>> +// <http://www.gnu.org/licenses/>.
>> +
>> +#include <algorithm>
>> +#include <vector>
>> +#include <deque>
>> +
>> +#include <ext/new_allocator.h>
>> +#include <ext/malloc_allocator.h>
>> +
>> +#include <testsuite_hooks.h>
>> +
>> +void test01()
>> +{
>> + using namespace std;
>> +
>> + deque<int> d;
>> + for (int i = 0; i !=
>> _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i)
>> + d.push_back(i);
>> +
>> + const deque<int>& cd = d;
>> +
>> + VERIFY( !lexicographical_compare(cd.begin(), cd.end(), cd.begin(),
>> cd.end()) );
>> + VERIFY( !lexicographical_compare(cd.begin(), cd.end(), d.begin(),
>> d.end()) );
>> + VERIFY( !lexicographical_compare(d.begin(), d.end(), d.begin(),
>> d.end()) );
>> + VERIFY( !lexicographical_compare(d.begin(), d.end(), cd.begin(),
>> cd.end()) );
>> +}
>> +
>> +void test02()
>> +{
>> + using namespace std;
>> +
>> + deque<int> d;
>> + for (int i = 0; i != 1000; ++i)
>> + d.push_back(i % 10);
>> +
>> + VERIFY( !lexicographical_compare(d.begin(), d.begin() + 10,
>> + d.begin() + 20, d.begin() + 30) );
>> + VERIFY( lexicographical_compare(d.begin(), d.begin() + 10,
>> + d.begin() + 20, d.begin() + 31) );
>> + VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10,
>> + d.begin(), d.end() - 20) );
>> +
>> + const deque<int>& cd = d;
>> +
>> + VERIFY( !lexicographical_compare(cd.begin(), cd.begin() + 10,
>> + cd.begin() + 20, cd.begin() + 30) );
>> + VERIFY( !lexicographical_compare(cd.begin() + 10, cd.end() - 10,
>> + d.begin(), d.end() - 20) );
>> + VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10,
>> + cd.begin(), cd.end() - 20) );
>> +}
>> +
>> +void test03()
>> +{
>> + using namespace std;
>> +
>> + deque<int> d1;
>> + for (int i = 0; i != 1000; ++i)
>> + d1.push_back(i % 10);
>> +
>> + deque<int> d2(d1);
>> + for (int i = 0; i != 10; ++i)
>> + d2.pop_front();
>> +
>> + VERIFY( !lexicographical_compare(d1.begin(), d1.begin() + 10,
>> + d2.begin(), d2.begin() + 10) );
>> + VERIFY( !lexicographical_compare(d1.begin() + 10, d1.end() - 10,
>> + d2.begin(), d2.end() - 10) );
>> +
>> + const deque<int>& cd1 = d1;
>> + const deque<int>& cd2 = d2;
>> +
>> + VERIFY( !lexicographical_compare(cd1.begin(), cd1.begin() + 10,
>> + cd2.begin() + 20, cd2.begin() + 30) );
>> + VERIFY( !lexicographical_compare(cd1.begin() + 10, cd1.end() - 10,
>> + d2.begin(), d2.end() - 10) );
>> + VERIFY( lexicographical_compare(cd2.begin() + 10, cd2.end() - 10,
>> + cd1.begin(), cd1.end() - 20) );
>> +}
>> +
>> +void test04()
>> +{
>> + using namespace std;
>> +
>> + deque<int> d;
>> + for (int i = 0; i != 1024; ++i)
>> + d.push_back(i);
>> +
>> + vector<int> v(d.begin(), d.end());
>> +
>> + VERIFY( lexicographical_compare(d.begin() + 5, d.end() - 1,
>> v.begin() + 5, v.end()) );
>> + VERIFY( !lexicographical_compare(v.begin(), v.end(), d.begin(),
>> d.end()) );
>> +
>> + const deque<int>& cd = d;
>> +
>> + VERIFY( !lexicographical_compare(cd.begin(), cd.end(), v.begin(),
>> v.end()) );
>> + VERIFY( !lexicographical_compare(v.begin(), v.end(), cd.begin(),
>> cd.end()) );
>> +}
>> +
>> +void test05()
>> +{
>> + using namespace std;
>> +
>> + int a[] = { 0, 1, 2, 3, 4 };
>> + deque<int, __gnu_cxx::new_allocator<int> > d1(a, a + 5);
>> + deque<int, __gnu_cxx::malloc_allocator<int> > d2(a, a + 5);
>> +
>> + VERIFY( !lexicographical_compare(d1.begin(), d1.end(), d2.begin(),
>> d2.end()) );
>> +}
>> +
>> +int main()
>> +{
>> + test01();
>> + test02();
>> + test03();
>> + test04();
>> + test05();
>> + return 0;
>> +}
>
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: libstdc++: Extend memcmp optimization in std::lexicographical_compare
2020-06-09 10:24 ` Jonathan Wakely
@ 2020-06-09 20:35 ` François Dumont
2020-06-09 20:50 ` Jonathan Wakely
0 siblings, 1 reply; 19+ messages in thread
From: François Dumont @ 2020-06-09 20:35 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: libstdc++, gcc-patches
On 09/06/20 12:24 pm, Jonathan Wakely wrote:
> On 08/06/20 19:20 +0100, Jonathan Wakely wrote:
>> On 05/06/20 22:24 +0200, François Dumont via Libstdc++ wrote:
>>> Hi
>>>
>>> Â Â Â Here is the last of my algo patches this time to extend the
>>> memcmp optimization to std::deque iterators and _GLIBCXX_DEBUG mode.
>>>
>>> Â Â Â To do so I had to return int in implementation details of
>>> lexicographical_compare to make sure we can treat a deque iterator
>>> range by chunk in a performant way.
>>>
>>> Tested under Linux x86_64 normal and debug modes.
>>>
>>> Â Â Â Â Â Â Â Â Â Â Â * include/bits/stl_algobase.h
>>> Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_impl): Return int.
>>> Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare::__lc): Likewise.
>>> Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux1(_II1, _II1,
>>> _II2, _II2)): New.
>>> (__lexicographical_compare_aux1(_Deque_iterator<>, _Deque_iterator<>,
>>> Â Â Â Â Â Â Â Â Â Â Â _II2, _II2)): Declare.
>>> Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux1(_II1, _II1,
>>> Â Â Â Â Â Â Â Â Â Â Â _Deque_iterator<>, _Deque_iterator<>)): Declare.
>>> (__lexicographical_compare_aux1(_Deque_iterator<>, _Deque_iterator<>,
>>> Â Â Â Â Â Â Â Â Â Â Â _Deque_iterator<>, _Deque_iterator<>)): Declare.
>>> Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux): Adapt, call
>>> later.
>>
>> Is this meant to say "latter"? That's still not correct grammar
>> though. I think it would be better to name the function it calls
>> explicitly: "Call __lexicographical_compare_aux1."
>>
>>> Â Â Â Â Â Â Â Â Â Â Â
>>> (__lexicographical_compare_aux(_Safe_iterator<>, _Safe_iterator<>,
>>> Â Â Â Â Â Â Â Â Â Â Â _II2, _II2)): Declare.
>>> Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux(_II1, _II1,
>>> Â Â Â Â Â Â Â Â Â Â Â _Safe_iterator<>, _Safe_iterator<>)): Declare.
>>> Â Â Â Â Â Â Â Â Â Â Â
>>> (__lexicographical_compare_aux(_Safe_iterator<>, _Safe_iterator<>,
>>> Â Â Â Â Â Â Â Â Â Â Â _Safe_iterator<>, _Safe_iterator<>)): Declare.
>>> Â Â Â Â Â Â Â Â Â Â Â (std::lexicographical_compare): Adapt, call
>>> later without __niter_base
>>> Â Â Â Â Â Â Â Â Â Â Â usage.
>>> Â Â Â Â Â Â Â Â Â Â Â * include/bits/deque.tcc (__lex_cmp_dit): New.
>>> Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux1): New.
>>> Â Â Â Â Â Â Â Â Â Â Â * include/debug/safe_iterator.tcc
>>> Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux(const
>>> _Safe_iterator<>&,
>>> Â Â Â Â Â Â Â Â Â Â Â const _Safe_iterator<>&, _II2, _II2)): New.
>>> Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux(
>>> Â Â Â Â Â Â Â Â Â Â Â const _Safe_iterator<>&, const_Safe_iterator<>&,
>>> Â Â Â Â Â Â Â Â Â Â Â const _Safe_iterator<>&, const
>>> _Safe_iterator<>&)): New.
>>> Â Â Â Â Â Â Â Â Â Â Â *
>>> testsuite/25_algorithms/lexicographical_compare/1.cc (test6, test7):
>>> Â Â Â Â Â Â Â Â Â Â Â New.
>>> Â Â Â Â Â Â Â Â Â Â Â *
>>> testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc:
>>> Â Â Â Â Â Â Â Â Â Â Â New test.
>>>
>>> Ok to commit ?
>>>
>>> François
>>>
>>>
>>
>>> diff --git a/libstdc++-v3/include/bits/deque.tcc
>>> b/libstdc++-v3/include/bits/deque.tcc
>>> index 1d32a1691c7..d7dbe64f3e1 100644
>>> --- a/libstdc++-v3/include/bits/deque.tcc
>>> +++ b/libstdc++-v3/include/bits/deque.tcc
>>> @@ -1261,6 +1261,98 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>>> return true;
>>> }
>>>
>>> + template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
>>
>> _II is the wrong name here, it mean InputIterator. All callers of this
>> function are constrained for random access iterators. This cannot be
>> called with an input iterator. Please use _RAIter.
>>
>>> + int
>>> + __lex_cmp_dit(
>>> + const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __first1,
>>> + const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __last1,
>>> + _II __first2, _II __last2)
>>> + {
>>> + typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
>>> + typedef typename _Iter::difference_type difference_type;
>>> +
>>> + if (__first1._M_node != __last1._M_node)
>>> + {
>>> + difference_type __len = __last2 - __first2;
>>> + difference_type __flen
>>
>> What does "flen" mean? Why not use len2 for last2 - first2, as we do
>> elsewhere? And then use len for min(len1, len2)?
>>
>>
>>> + = std::min(__len, __first1._M_last - __first1._M_cur);
>>> + if (int __ret = std::__lexicographical_compare_aux1(
>>
>> This call (and the three later in this function) will do overload
>> resolution again on the full set of __lexicographical_compare_aux1
>> overloads, which includes the ones for deque iterators. But we know
>> that __first1._M_cur and __first1._M_last are not deque iterators.
>>
>> __first2 could be a deque iterator, but I'm not sure if we really want
>> one function that has to handle that case anyway.
>>
>>> + __first1._M_cur, __first1._M_last, __first2, __first2 +
>>> __flen))
>>> + return __ret;
>>> +
>>> + __first2 += __flen;
>>> + __len -= __flen;
>>> + __flen = std::min<size_t>(__len, _Iter::_S_buffer_size());
>>> + for (typename _Iter::_Map_pointer __node = __first1._M_node + 1;
>>> + __node != __last1._M_node;
>>> + __first2 += __flen, __len -= __flen,
>>> + __flen = std::min<size_t>(__len, _Iter::_S_buffer_size()),
>>> + ++__node)
>>> + if (int __ret = std::__lexicographical_compare_aux1(
>>> + *__node, *__node + _Iter::_S_buffer_size(),
>>> + __first2, __first2 + __flen))
>>> + return __ret;
>>> +
>>> + return std::__lexicographical_compare_aux1(
>>> + __last1._M_first, __last1._M_cur, __first2, __last2);
>>> + }
>>> +
>>> + return std::__lexicographical_compare_aux1(
>>> + __first1._M_cur, __last1._M_cur, __first2, __last2);
>>> + }
>>> +
>>> + template<typename _Tp1, typename _Ref1, typename _Ptr1,
>>> + typename _II2>
>>
>> This is not an input iterator either.
>>
>>> + typename __gnu_cxx::__enable_if<
>>> + __is_random_access_iter<_II2>::__value, int>::__type
>>
>> This should be inline.
>>
>> Also, I'm curious why these overloads use __enable_if rather than the
>> conventional approach of tag dispatching using iterator_category.
>> (The same question applies to th __equal_aux1 and __copy_move_a1
>> overloads for deque iterators as well). It doesn't really matter
>> though.
>>
>>> + __lexicographical_compare_aux1(
>>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
>>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
>>> + _II2 __first2, _II2 __last2)
>>> + { return std::__lex_cmp_dit(__first1, __last1, __first2,
>>> __last2); }
>>> +
>>> + template<typename _Tp1, typename _Ref1, typename _Ptr1,
>>> + typename _Tp2, typename _Ref2, typename _Ptr2>
>>> + int
>>
>> This should be inline.
>>
>>> + __lexicographical_compare_aux1(
>>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
>>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
>>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
>>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
>>> + { return std::__lex_cmp_dit(__first1, __last1, __first2,
>>> __last2); }
>>
>> I'm not convinced it's useful for this function and the one above it
>> to share the same logic.
>>
>>> + template<typename _II1,
>>> + typename _Tp2, typename _Ref2, typename _Ptr2>
>>> + typename __gnu_cxx::__enable_if<
>>> + __is_random_access_iter<_II1>::__value, int>::__type
>>> + __lexicographical_compare_aux1(
>>> + _II1 __first1, _II1 __last1,
>>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
>>> + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
>>> + {
>>> + typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>
>>> _Iter;
>>> + typedef typename _Iter::difference_type difference_type;
>>> +
>>> + difference_type __len = __last1 - __first1;
>>> + while (__len > 0)
>>> + {
>>> + const difference_type __flen = __first2._M_node ==
>>> __last2._M_node
>>> + ? __last2._M_cur - __first2._M_cur
>>> + : __first2._M_last - __first2._M_cur;
>>> + const difference_type __clen = std::min(__len, __flen);
>>
>> "flen"? "clen"?
>>
>>> + if (int __ret = std::__lexicographical_compare_aux1(
>>> + __first1, __first1 + __clen,
>>> + __first2._M_cur, __first2._M_cur + __flen))
>>> + return __ret;
>>> +
>>> + __first1 += __clen;
>>> + __len -= __clen;
>>> + __first2 += __clen;
>>> + }
>>> +
>>> + return __first1 == __last1 ? (__first2 != __last2 ? -1 : 0) : 1;
>>
>> Isn't this function doing basically the same as __lex_cmp_dit? Why
>> does it not use the same logic?
>>
>> Can this whole function just negate the result of __lex_cmp_dit called
>> with the arguments switched?
>>
>> return -std::__lex_cmp_dit(__first2, __last2, __first1, __last1);
>>
>> That would also fix the bug that makes the following loop forever:
>>
>> std::deque<int> d;
>> int i = 0;
>> std::lexicographical_compare(&i, &i + 1, d.begin(), d.end());
>
> Same question for __equal_aux1, why is it implemented twice? Why
> doesn't __equal_aux1(_II f1, _II l1, _Deque_iterator<> f2) just call
> __equal_aux1(f2, f2 + (l1 - f1), f1) ?
>
Because I didn't thought about doing it this way. Yet another patch if
you don't do it yourself.
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: libstdc++: Extend memcmp optimization in std::lexicographical_compare
2020-06-09 20:20 ` François Dumont
@ 2020-06-09 20:38 ` Jonathan Wakely
0 siblings, 0 replies; 19+ messages in thread
From: Jonathan Wakely @ 2020-06-09 20:38 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On 09/06/20 22:20 +0200, François Dumont via Libstdc++ wrote:
>On 08/06/20 8:20 pm, Jonathan Wakely wrote:
>>On 05/06/20 22:24 +0200, François Dumont via Libstdc++ wrote:
>>>Hi
>>>
>>>   Here is the last of my algo patches this time to extend the
>>>memcmp optimization to std::deque iterators and _GLIBCXX_DEBUG
>>>mode.
>>>
>>>   To do so I had to return int in implementation details of
>>>lexicographical_compare to make sure we can treat a deque iterator
>>>range by chunk in a performant way.
>>>
>>>Tested under Linux x86_64 normal and debug modes.
>>>
>>>           * include/bits/stl_algobase.h
>>>           (__lexicographical_compare_impl): Return int.
>>>           (__lexicographical_compare::__lc): Likewise.
>>>           (__lexicographical_compare_aux1(_II1, _II1,
>>>_II2, _II2)): New.
>>>(__lexicographical_compare_aux1(_Deque_iterator<>, _Deque_iterator<>,
>>>           _II2, _II2)): Declare.
>>>           (__lexicographical_compare_aux1(_II1, _II1,
>>>           _Deque_iterator<>, _Deque_iterator<>)): Declare.
>>>(__lexicographical_compare_aux1(_Deque_iterator<>, _Deque_iterator<>,
>>>           _Deque_iterator<>, _Deque_iterator<>)): Declare.
>>>           (__lexicographical_compare_aux): Adapt,
>>>call later.
>>
>>Is this meant to say "latter"? That's still not correct grammar
>>though. I think it would be better to name the function it calls
>>explicitly: "Call __lexicographical_compare_aux1."
>
>Ok.
>
>
>>
>>>          Â
>>>(__lexicographical_compare_aux(_Safe_iterator<>, _Safe_iterator<>,
>>>           _II2, _II2)): Declare.
>>>           (__lexicographical_compare_aux(_II1, _II1,
>>>           _Safe_iterator<>, _Safe_iterator<>)): Declare.
>>>          Â
>>>(__lexicographical_compare_aux(_Safe_iterator<>, _Safe_iterator<>,
>>>           _Safe_iterator<>, _Safe_iterator<>)): Declare.
>>>           (std::lexicographical_compare): Adapt, call
>>>later without __niter_base
>>>           usage.
>>>           * include/bits/deque.tcc (__lex_cmp_dit): New.
>>>           (__lexicographical_compare_aux1): New.
>>>           * include/debug/safe_iterator.tcc
>>>           (__lexicographical_compare_aux(const
>>>_Safe_iterator<>&,
>>>           const _Safe_iterator<>&, _II2, _II2)): New.
>>>           (__lexicographical_compare_aux(
>>>           const _Safe_iterator<>&, const_Safe_iterator<>&,
>>>           const _Safe_iterator<>&, const
>>>_Safe_iterator<>&)): New.
>>>           *
>>>testsuite/25_algorithms/lexicographical_compare/1.cc (test6,
>>>test7):
>>>           New.
>>>           * testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc:
>>>           New test.
>>>
>>>Ok to commit ?
>>>
>>>François
>>>
>>>
>>
>>>diff --git a/libstdc++-v3/include/bits/deque.tcc
>>>b/libstdc++-v3/include/bits/deque.tcc
>>>index 1d32a1691c7..d7dbe64f3e1 100644
>>>--- a/libstdc++-v3/include/bits/deque.tcc
>>>+++ b/libstdc++-v3/include/bits/deque.tcc
>>>@@ -1261,6 +1261,98 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>>>Â Â Â Â Â return true;
>>>Â Â Â }
>>>
>>>+Â template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
>>
>>_II is the wrong name here, it mean InputIterator. All callers of this
>>function are constrained for random access iterators. This cannot be
>>called with an input iterator. Please use _RAIter.
>>
>>>+Â Â Â int
>>>+Â Â Â __lex_cmp_dit(
>>>+Â Â Â const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __first1,
>>>+Â Â Â const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __last1,
>>>+Â Â Â _II __first2, _II __last2)
>>>+Â Â Â {
>>>+Â Â Â Â Â typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
>>>+Â Â Â Â Â typedef typename _Iter::difference_type difference_type;
>>>+
>>>+Â Â Â Â Â if (__first1._M_node != __last1._M_node)
>>>+Â Â Â {
>>>+Â Â Â Â Â difference_type __len = __last2 - __first2;
>>>+Â Â Â Â Â difference_type __flen
>>
>>What does "flen" mean? Why not use len2 for last2 - first2, as we do
>>elsewhere? And then use len for min(len1, len2)?
>
>short for 'first lenght' because it is the first iterator range.
>len1/len2 is better of course.
>
>>
>>
>>>+Â Â Â Â Â Â Â = std::min(__len, __first1._M_last - __first1._M_cur);
>>>+Â Â Â Â Â if (int __ret = std::__lexicographical_compare_aux1(
>>
>>This call (and the three later in this function) will do overload
>>resolution again on the full set of __lexicographical_compare_aux1
>>overloads, which includes the ones for deque iterators. But we know
>>that __first1._M_cur and __first1._M_last are not deque iterators.
>>
>>__first2 could be a deque iterator, but I'm not sure if we really want
>>one function that has to handle that case anyway.
>
>Considering the performance results on the std::copy algo it appeared
>to me that just "unrolling" the deque iterator is already an
>enhancement. Looping on pointers is better than looping on deque
>iterators.
>
>Is it what you wonder ?
Well the question is redundant given my proposed patch, because it
doesn't use __lexicographical_compare_aux1 on the internal pointers. I
added a new function, so that __lexicographical_compare_aux1 doesn't
need to be changed.
>>
>>>+Â Â Â Â Â Â Â Â Â __first1._M_cur, __first1._M_last, __first2, __first2 +
>>>__flen))
>>>+Â Â Â Â Â Â Â return __ret;
>>>+
>>>+Â Â Â Â Â __first2 += __flen;
>>>+Â Â Â Â Â __len -= __flen;
>>>+Â Â Â Â Â __flen = std::min<size_t>(__len, _Iter::_S_buffer_size());
>>>+Â Â Â Â Â for (typename _Iter::_Map_pointer __node = __first1._M_node + 1;
>>>+Â Â Â Â Â Â Â Â Â Â __node != __last1._M_node;
>>>+Â Â Â Â Â Â Â Â Â Â __first2 += __flen, __len -= __flen,
>>>+Â Â Â Â Â Â Â Â Â Â __flen = std::min<size_t>(__len, _Iter::_S_buffer_size()),
>>>+Â Â Â Â Â Â Â Â Â Â ++__node)
>>>+Â Â Â Â Â Â Â if (int __ret = std::__lexicographical_compare_aux1(
>>>+Â Â Â Â Â Â Â Â Â *__node, *__node + _Iter::_S_buffer_size(),
>>>+Â Â Â Â Â Â Â Â Â __first2, __first2 + __flen))
>>>+Â Â Â Â Â Â Â Â Â return __ret;
>>>+
>>>+Â Â Â Â Â return std::__lexicographical_compare_aux1(
>>>+Â Â Â Â Â Â Â __last1._M_first, __last1._M_cur, __first2, __last2);
>>>+Â Â Â }
>>>+
>>>+Â Â Â Â Â return std::__lexicographical_compare_aux1(
>>>+Â Â Â Â Â Â Â Â Â __first1._M_cur, __last1._M_cur, __first2, __last2);
>>>+Â Â Â }
>>>+
>>>+Â template<typename _Tp1, typename _Ref1, typename _Ptr1,
>>>+Â Â Â Â Â Â typename _II2>
>>
>>This is not an input iterator either.
>>
>>>+Â Â Â typename __gnu_cxx::__enable_if<
>>>+Â Â Â Â Â __is_random_access_iter<_II2>::__value, int>::__type
>>
>>This should be inline.
>>
>>Also, I'm curious why these overloads use __enable_if rather than the
>>conventional approach of tag dispatching using iterator_category.
>>(The same question applies to th __equal_aux1 and __copy_move_a1
>>overloads for deque iterators as well). It doesn't really matter
>>though.
>
>Those functions are using Rai operations like operator- so I thought
>that they they should be enabled only on the right category of
>iterator. Maybe overload would have been fine too.
Yes, but tag dispatching also selects the right overload for the right
iterator category.
>Isn't it making overload resolution better ?
No, SFINAE makes overload resolution very expensive.
>>
>>>+Â Â Â __lexicographical_compare_aux1(
>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
>>>+Â Â Â Â Â Â Â _II2 __first2, _II2 __last2)
>>>+Â Â Â { return std::__lex_cmp_dit(__first1, __last1, __first2,
>>>__last2); }
>>>+
>>>+Â template<typename _Tp1, typename _Ref1, typename _Ptr1,
>>>+Â Â Â Â Â Â typename _Tp2, typename _Ref2, typename _Ptr2>
>>>+Â Â Â int
>>
>>This should be inline.
>>
>>>+Â Â Â __lexicographical_compare_aux1(
>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
>>>+Â Â Â { return std::__lex_cmp_dit(__first1, __last1, __first2,
>>>__last2); }
>>
>>I'm not convinced it's useful for this function and the one above it
>>to share the same logic.
>This overload is here just to disambiguate a call with 4 deque
>iterators cause in this case the compiler wouldn't know which of the 2
>other overloads to call.
Yes, I understand that part.
>But I still want only 2 implementations, one
>when 1st range are deque iterators and another when 2nd range are
>deque iterators.
But that's silly, the two cases are equivalent, you just need to flip
the result. You don't need two completely different implementations
for comparing deque+other and other+deque. And the two completely
different implementations are *completely* different, for no obvious
reason (one even has a bug that loops forever).
>I just chose that when I have 2 deque iterator ranges
>I'll use the implementation where 1st range is such.
The case where you have two deque iterators can be handled by a
specialized function that unwraps both sets of deque iterators, and
the other two cases can share the same logic.
>>
>>>+Â template<typename _II1,
>>>+Â Â Â Â Â Â typename _Tp2, typename _Ref2, typename _Ptr2>
>>>+Â Â Â typename __gnu_cxx::__enable_if<
>>>+Â Â Â Â Â __is_random_access_iter<_II1>::__value, int>::__type
>>>+Â Â Â __lexicographical_compare_aux1(
>>>+Â Â Â Â Â Â Â _II1 __first1, _II1 __last1,
>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
>>>+Â Â Â {
>>>+Â Â Â Â Â typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>
>>>_Iter;
>>>+Â Â Â Â Â typedef typename _Iter::difference_type difference_type;
>>>+
>>>+Â Â Â Â Â difference_type __len = __last1 - __first1;
>>>+Â Â Â Â Â while (__len > 0)
>>>+Â Â Â {
>>>+Â Â Â Â Â const difference_type __flen = __first2._M_node ==
>>>__last2._M_node
>>>+Â Â Â Â Â Â Â ? __last2._M_cur - __first2._M_cur
>>>+Â Â Â Â Â Â Â : __first2._M_last - __first2._M_cur;
>>>+Â Â Â Â Â const difference_type __clen = std::min(__len, __flen);
>>
>>"flen"? "clen"?
>just 'c' for const I think
>>>+Â Â Â Â Â if (int __ret = std::__lexicographical_compare_aux1(
>>>+Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â __first1, __first1 + __clen,
>>>+Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â __first2._M_cur, __first2._M_cur + __flen))
>>>+Â Â Â Â Â Â Â return __ret;
>>>+
>>>+Â Â Â Â Â __first1 += __clen;
>>>+Â Â Â Â Â __len -= __clen;
>>>+Â Â Â Â Â __first2 += __clen;
>>>+Â Â Â }
>>>+
>>>+Â Â Â Â Â return __first1 == __last1 ? (__first2 != __last2 ? -1 : 0) : 1;
>>
>>Isn't this function doing basically the same as __lex_cmp_dit? Why
>>does it not use the same logic?
>>
>>Can this whole function just negate the result of __lex_cmp_dit called
>>with the arguments switched?
>>
>>Â return -std::__lex_cmp_dit(__first2, __last2, __first1, __last1);
>>
>>That would also fix the bug that makes the following loop forever:
>>
>>Â std::deque<int> d;
>>Â int i = 0;
>>Â std::lexicographical_compare(&i, &i + 1, d.begin(), d.end());
>I have to consider this, I also wanted to cover comparison with raw
>pointer ranges or vector iterators that could be replaced with memcmp.
Which works fine with the patch I proposed.
>>
>>
>>>+Â Â Â }
>>>+
>>>_GLIBCXX_END_NAMESPACE_VERSION
>>>} // namespace std
>>>
>>>diff --git a/libstdc++-v3/include/bits/stl_algobase.h
>>>b/libstdc++-v3/include/bits/stl_algobase.h
>>>index 0163d8f902d..ecc50a10c9d 100644
>>>--- a/libstdc++-v3/include/bits/stl_algobase.h
>>>+++ b/libstdc++-v3/include/bits/stl_algobase.h
>>>@@ -1279,7 +1279,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>>>
>>>Â template<typename _II1, typename _II2, typename _Compare>
>>>Â Â Â _GLIBCXX20_CONSTEXPR
>>>-Â Â Â bool
>>>+Â Â Â int
>>>Â Â Â __lexicographical_compare_impl(_II1 __first1, _II1 __last1,
>>>Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â _II2 __first2, _II2 __last2,
>>>Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â _Compare __comp)
>>>@@ -1288,16 +1288,18 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>>>Â Â Â Â Â typedef typename iterator_traits<_II2>::iterator_category
>>>_Category2;
>>>Â Â Â Â Â typedef std::__lc_rai<_Category1, _Category2> __rai_type;
>>>
>>>-Â Â Â Â Â __last1 = __rai_type::__newlast1(__first1, __last1,
>>>__first2, __last2);
>>>-Â Â Â Â Â for (; __first1 != __last1 && __rai_type::__cnd2(__first2,
>>>__last2);
>>>+Â Â Â Â Â _II1 __new_last1
>>>+Â Â Â = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
>>>+Â Â Â Â Â for (; __first1 != __new_last1 &&
>>>__rai_type::__cnd2(__first2, __last2);
>>>Â Â Â Â Â Â ++__first1, (void)++__first2)
>>>Â Â Â Â {
>>>Â Â Â Â Â if (__comp(__first1, __first2))
>>>-Â Â Â Â Â Â Â return true;
>>>+Â Â Â Â Â Â Â return -1;
>>>Â Â Â Â Â if (__comp(__first2, __first1))
>>>-Â Â Â Â Â Â Â return false;
>>>+Â Â Â Â Â Â Â return 1;
>>>Â Â Â Â }
>>>-Â Â Â Â Â return __first1 == __last1 && __first2 != __last2;
>>>+
>>>+Â Â Â Â Â return __first1 == __last1 ? (__first2 != __last2 ? -1 : 0) : 1;
>>
>>This is going to produce worse code for the common (non-deque) case,
>>isn't it?
>>
>>
>>>Â Â Â }
>>>
>>>Â template<bool _BoolType>
>>>@@ -1305,7 +1307,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>>>Â Â Â {
>>>Â Â Â Â Â template<typename _II1, typename _II2>
>>>Â Â Â Â _GLIBCXX20_CONSTEXPR
>>>-Â Â Â static bool
>>>+Â Â Â static int
>>>Â Â Â Â __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
>>>Â Â Â Â {
>>>Â Â Â Â Â using __gnu_cxx::__ops::__iter_less_iter;
>>>@@ -1320,7 +1322,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>>>Â Â Â {
>>>Â Â Â Â Â template<typename _Tp, typename _Up>
>>>Â Â Â Â _GLIBCXX20_CONSTEXPR
>>>-Â Â Â static bool
>>>+Â Â Â static int
>>>Â Â Â Â __lc(const _Tp* __first1, const _Tp* __last1,
>>>Â Â Â Â Â Â Â Â const _Up* __first2, const _Up* __last2)
>>>Â Â Â Â {
>>>@@ -1328,16 +1330,44 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>>>Â Â Â Â Â const size_t __len2 = __last2 - __first2;
>>>Â Â Â Â Â if (const size_t __len = std::min(__len1, __len2))
>>>Â Â Â Â Â Â Â if (int __result = std::__memcmp(__first1, __first2, __len))
>>>-Â Â Â Â Â Â Â Â Â return __result < 0;
>>>-Â Â Â Â Â return __len1 < __len2;
>>>+Â Â Â Â Â Â Â Â Â return __result;
>>>+
>>>+Â Â Â Â Â return __len1 < __len2 ? -1 : (__len2 < __len1 ? 1 : 0);
>>
>>Again, this will produce worse code.
>>
>>If you made it return ptrdiff_t instead of int you could just do:
>>
>>Â return ptrdiff_t(__len1 - __len2);
>>
>>But I think we should just not change these __lc helpers, and not try
>>to reuse them for deque iterators. We can define new helpers that
>>return the 3-way result that is needed for comparing deque iterators.
>>
>Yes, it sounds promising.
>>
>>>+Â template<typename _Tp1, typename _Ref1, typename _Ptr1,
>>>+Â Â Â Â Â Â typename _II2>
>>>+Â Â Â typename __gnu_cxx::__enable_if<
>>>+Â Â Â Â Â __is_random_access_iter<_II2>::__value, int>::__type
>>>+Â Â Â __lexicographical_compare_aux1(
>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
>>>+Â Â Â Â Â Â Â _II2, _II2);
>>>+
>>>+Â template<typename _II1,
>>>+Â Â Â Â Â Â typename _Tp2, typename _Ref2, typename _Ptr2>
>>>+Â Â Â typename __gnu_cxx::__enable_if<
>>>+Â Â Â Â Â __is_random_access_iter<_II1>::__value, int>::__type
>>>+Â Â Â __lexicographical_compare_aux1(
>>>+Â Â Â Â Â Â Â _II1, _II1,
>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
>>>+
>>>+Â template<typename _Tp1, typename _Ref1, typename _Ptr1,
>>>+Â Â Â Â Â Â typename _Tp2, typename _Ref2, typename _Ptr2>
>>>+Â Â Â int
>>>+Â Â Â __lexicographical_compare_aux1(
>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
>>>+
>>>Â template<typename _II1, typename _II2>
>>>Â Â Â _GLIBCXX20_CONSTEXPR
>>>-Â Â Â inline bool
>>>-Â Â Â __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
>>>-Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â _II2 __first2, _II2 __last2)
>>>+Â Â Â inline int
>>>+Â Â Â __lexicographical_compare_aux1(_II1 __first1, _II1 __last1,
>>>+Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â _II2 __first2, _II2 __last2)
>>
>>If you rename this to __lexicographical_compare_aux2 instead and add
>>a one-line forwarding function called __lexicographical_compare_aux1,
>>then the code above for deque iterators can call the aux2 overload
>>directly, to avoid doing overload resolution on aux1 again.
>>
>>>Â Â Â {
>>>Â Â Â Â Â typedef typename iterator_traits<_II1>::value_type _ValueType1;
>>>Â Â Â Â Â typedef typename iterator_traits<_II2>::value_type _ValueType2;
>>>@@ -1360,6 +1390,43 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>>>Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â __first2, __last2);
>>>Â Â Â }
>>>
>>>+Â template<typename _II1, typename _II2>
>>>+Â Â Â _GLIBCXX20_CONSTEXPR
>>>+Â Â Â inline int
>>>+Â Â Â __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
>>>+Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â _II2 __first2, _II2 __last2)
>>>+Â Â Â {
>>>+Â Â Â Â Â return
>>>std::__lexicographical_compare_aux1(std::__niter_base(__first1),
>>>+Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â std::__niter_base(__last1),
>>>+Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â std::__niter_base(__first2),
>>>+Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â std::__niter_base(__last2));
>>>+Â Â Â }
>>>+
>>>+Â template<typename _Ite1, typename _Seq1, typename _Cat1,
>>
>>Please don't introduce any more "Ite" parameters, this should be _It1
>>or _Iter1.
>>
>>>+Â Â Â Â Â Â typename _II2>
>>>+Â Â Â int
>>>+Â Â Â __lexicographical_compare_aux(
>>>+Â Â Â Â Â Â Â const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
>>>+Â Â Â Â Â Â Â const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
>>>+Â Â Â Â Â Â Â _II2, _II2);
>>>+
>>>+Â template<typename _II1,
>>>+Â Â Â Â Â Â typename _Ite2, typename _Seq2, typename _Cat2>
>>>+Â Â Â int
>>>+Â Â Â __lexicographical_compare_aux(
>>>+Â Â Â Â Â Â Â _II1, _II1,
>>>+Â Â Â Â Â Â Â const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&,
>>>+Â Â Â Â Â Â Â const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&);
>>>+
>>>+Â template<typename _Ite1, typename _Seq1, typename _Cat1,
>>>+Â Â Â Â Â Â typename _Ite2, typename _Seq2, typename _Cat2>
>>>+Â Â Â int
>>>+Â Â Â __lexicographical_compare_aux(
>>>+Â Â Â Â Â Â Â const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
>>>+Â Â Â Â Â Â Â const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
>>>+Â Â Â Â Â Â Â const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&,
>>>+Â Â Â Â Â Â Â const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&);
>>>+
>>>Â template<typename _ForwardIterator, typename _Tp, typename _Compare>
>>>Â Â Â _GLIBCXX20_CONSTEXPR
>>>Â Â Â _ForwardIterator
>>>@@ -1659,10 +1726,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
>>>Â Â Â Â Â __glibcxx_requires_valid_range(__first1, __last1);
>>>Â Â Â Â Â __glibcxx_requires_valid_range(__first2, __last2);
>>>
>>>-Â Â Â Â Â return
>>>std::__lexicographical_compare_aux(std::__niter_base(__first1),
>>>-Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â std::__niter_base(__last1),
>>>-Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â std::__niter_base(__first2),
>>>-Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â std::__niter_base(__last2));
>>>+Â Â Â Â Â return std::__lexicographical_compare_aux(__first1, __last1,
>>>+Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â __first2, __last2) < 0;
>>
>>Why does __lexicographical_compare_aux need to change to return int?
>>
>>It looks like only __lexicographical_compare_aux1 gets called
>>recursively for deque iterators, so only that needs to be able to
>>return -1/0/+1 values.
>>
>Yes, I think I'll follow your idea based on your patch proposal.
I already sent a complete patch.
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: libstdc++: Extend memcmp optimization in std::lexicographical_compare
2020-06-09 16:11 ` Jonathan Wakely
2020-06-09 16:12 ` Jonathan Wakely
@ 2020-06-09 20:42 ` François Dumont
2020-06-09 20:53 ` Jonathan Wakely
1 sibling, 1 reply; 19+ messages in thread
From: François Dumont @ 2020-06-09 20:42 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: libstdc++, gcc-patches
On 09/06/20 6:11 pm, Jonathan Wakely wrote:
> On 09/06/20 00:02 +0100, Jonathan Wakely wrote:
>> On 08/06/20 22:08 +0100, Jonathan Wakely wrote:
>>> On 08/06/20 19:20 +0100, Jonathan Wakely wrote:
>>>> On 05/06/20 22:24 +0200, François Dumont via Libstdc++ wrote:
>>>>> Hi
>>>>>
>>>>> Â Â Â Here is the last of my algo patches this time to extend the
>>>>> memcmp optimization to std::deque iterators and _GLIBCXX_DEBUG mode.
>>>>>
>>>>> Â Â Â To do so I had to return int in implementation details of
>>>>> lexicographical_compare to make sure we can treat a deque iterator
>>>>> range by chunk in a performant way.
>>>
>>> Here's a simpler version, which doesn't alter anything for the
>>> existing code (i.e. all iterators that aren't deque iterators) and
>>> also fixes the infinite loop bug.
>>>
>>> This seems simpler and less invasive.
>>>
>>> Please take a look.
>>
>> I've actually tested it in debug mode now, and ...
>>
>>> diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc
>>> b/libstdc++-v3/include/debug/safe_iterator.tcc
>>> index 888ac803ae5..db6a301655f 100644
>>> --- a/libstdc++-v3/include/debug/safe_iterator.tcc
>>> +++ b/libstdc++-v3/include/debug/safe_iterator.tcc
>>> @@ -470,6 +470,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>> return __equal_aux1(__first1, __last1, __first2);
>>> }
>>>
>>> + template<typename _Ite1, typename _Seq1, typename _Cat1,
>>> + typename _II2>
>>> + int
>>
>> This should return bool here.
>>
>>> + __lexicographical_compare_aux(
>>> + const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&
>>> __first1,
>>> + const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
>>> + _II2 __first2, _II2 __last2)
>>> + {
>>> + typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
>>> + __glibcxx_check_valid_range2(__first1, __last1, __dist1);
>>> + __glibcxx_check_valid_range(__first2, __last2);
>>> +
>>> + if (__dist1.second > ::__gnu_debug::__dp_equality)
>>> + return std::__lexicographical_compare_aux(__first1.base(),
>>> + __last1.base(),
>>> + __first2, __last2);
>>> + return std::__lexicographical_compare_aux1(__first1, __last1,
>>> + __first2, __last2);
>>> + }
>>> +
>>> + template<typename _II1,
>>> + typename _Ite2, typename _Seq2, typename _Cat2>
>>> + int
>>
>> And here.
>>
>>> + __lexicographical_compare_aux(
>>> + _II1 __first1, _II1 __last1,
>>> + const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&
>>> __first2,
>>> + const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
>>> + {
>>> + __glibcxx_check_valid_range(__first1, __last1);
>>> + typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist2;
>>> + __glibcxx_check_valid_range2(__first2, __last2, __dist2);
>>> +
>>> + if (__dist2.second > ::__gnu_debug::__dp_equality)
>>> + return std::__lexicographical_compare_aux(__first1, __last1,
>>> + __first2.base(),
>>> + __last2.base());
>>> + return std::__lexicographical_compare_aux1(__first1, __last1,
>>> + __first2, __last2);
>>> + }
>>> +
>>> + template<typename _Ite1, typename _Seq1, typename _Cat1,
>>> + typename _Ite2, typename _Seq2, typename _Cat2>
>>> + int
>>
>> And here.
>
> And I've also enhanced the tests so they catch the bug I created where
> the __lexicographical_compare_aux1 overload taking two ranges of deque
> iterators was still trying to return a three-way result, rather than
> bool.
>
> Corrected patch attached.
>
> But, the 25_algorithms/lexicographical_compare/deque_iterators/1.cc
> test doesn't actually test the new code properly, because it only uses
> deque<int> which means memcmp isn't even used. We need better tests.
>
>
> .
I didn't consider adding one cause I didn't need it to challenge the new
code dedicated to deque iterators. I don't remember if I really check
but for me there are already checks involving memcmp.
Also I haven't found how to write a test checking that memcmp is indeed
call, I haven't try hard neither.
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: libstdc++: Extend memcmp optimization in std::lexicographical_compare
2020-06-09 20:35 ` François Dumont
@ 2020-06-09 20:50 ` Jonathan Wakely
0 siblings, 0 replies; 19+ messages in thread
From: Jonathan Wakely @ 2020-06-09 20:50 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On 09/06/20 22:35 +0200, François Dumont via Libstdc++ wrote:
>On 09/06/20 12:24 pm, Jonathan Wakely wrote:
>>On 08/06/20 19:20 +0100, Jonathan Wakely wrote:
>>>On 05/06/20 22:24 +0200, François Dumont via Libstdc++ wrote:
>>>>Hi
>>>>
>>>>   Here is the last of my algo patches this time to extend
>>>>the memcmp optimization to std::deque iterators and
>>>>_GLIBCXX_DEBUG mode.
>>>>
>>>>   To do so I had to return int in implementation details of
>>>>lexicographical_compare to make sure we can treat a deque
>>>>iterator range by chunk in a performant way.
>>>>
>>>>Tested under Linux x86_64 normal and debug modes.
>>>>
>>>>           * include/bits/stl_algobase.h
>>>>           (__lexicographical_compare_impl): Return int.
>>>>           (__lexicographical_compare::__lc): Likewise.
>>>>           (__lexicographical_compare_aux1(_II1,
>>>>_II1, _II2, _II2)): New.
>>>>(__lexicographical_compare_aux1(_Deque_iterator<>, _Deque_iterator<>,
>>>>           _II2, _II2)): Declare.
>>>>           (__lexicographical_compare_aux1(_II1, _II1,
>>>>           _Deque_iterator<>, _Deque_iterator<>)): Declare.
>>>>(__lexicographical_compare_aux1(_Deque_iterator<>, _Deque_iterator<>,
>>>>           _Deque_iterator<>, _Deque_iterator<>)): Declare.
>>>>           (__lexicographical_compare_aux): Adapt,
>>>>call later.
>>>
>>>Is this meant to say "latter"? That's still not correct grammar
>>>though. I think it would be better to name the function it calls
>>>explicitly: "Call __lexicographical_compare_aux1."
>>>
>>>>          Â
>>>>(__lexicographical_compare_aux(_Safe_iterator<>,
>>>>_Safe_iterator<>,
>>>>           _II2, _II2)): Declare.
>>>>           (__lexicographical_compare_aux(_II1, _II1,
>>>>           _Safe_iterator<>, _Safe_iterator<>)): Declare.
>>>>          Â
>>>>(__lexicographical_compare_aux(_Safe_iterator<>,
>>>>_Safe_iterator<>,
>>>>           _Safe_iterator<>, _Safe_iterator<>)): Declare.
>>>>           (std::lexicographical_compare): Adapt,
>>>>call later without __niter_base
>>>>           usage.
>>>>           * include/bits/deque.tcc (__lex_cmp_dit): New.
>>>>           (__lexicographical_compare_aux1): New.
>>>>           * include/debug/safe_iterator.tcc
>>>>           (__lexicographical_compare_aux(const
>>>>_Safe_iterator<>&,
>>>>           const _Safe_iterator<>&, _II2, _II2)): New.
>>>>           (__lexicographical_compare_aux(
>>>>           const _Safe_iterator<>&, const_Safe_iterator<>&,
>>>>           const _Safe_iterator<>&, const
>>>>_Safe_iterator<>&)): New.
>>>>           *
>>>>testsuite/25_algorithms/lexicographical_compare/1.cc (test6,
>>>>test7):
>>>>           New.
>>>>           * testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc:
>>>>           New test.
>>>>
>>>>Ok to commit ?
>>>>
>>>>François
>>>>
>>>>
>>>
>>>>diff --git a/libstdc++-v3/include/bits/deque.tcc
>>>>b/libstdc++-v3/include/bits/deque.tcc
>>>>index 1d32a1691c7..d7dbe64f3e1 100644
>>>>--- a/libstdc++-v3/include/bits/deque.tcc
>>>>+++ b/libstdc++-v3/include/bits/deque.tcc
>>>>@@ -1261,6 +1261,98 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>>>>Â Â Â Â return true;
>>>>Â Â }
>>>>
>>>>+Â template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
>>>
>>>_II is the wrong name here, it mean InputIterator. All callers of this
>>>function are constrained for random access iterators. This cannot be
>>>called with an input iterator. Please use _RAIter.
>>>
>>>>+Â Â Â int
>>>>+Â Â Â __lex_cmp_dit(
>>>>+Â Â Â const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __first1,
>>>>+Â Â Â const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __last1,
>>>>+Â Â Â _II __first2, _II __last2)
>>>>+Â Â Â {
>>>>+Â Â Â Â Â typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
>>>>+Â Â Â Â Â typedef typename _Iter::difference_type difference_type;
>>>>+
>>>>+Â Â Â Â Â if (__first1._M_node != __last1._M_node)
>>>>+Â Â Â {
>>>>+Â Â Â Â Â difference_type __len = __last2 - __first2;
>>>>+Â Â Â Â Â difference_type __flen
>>>
>>>What does "flen" mean? Why not use len2 for last2 - first2, as we do
>>>elsewhere? And then use len for min(len1, len2)?
>>>
>>>
>>>>+Â Â Â Â Â Â Â = std::min(__len, __first1._M_last - __first1._M_cur);
>>>>+Â Â Â Â Â if (int __ret = std::__lexicographical_compare_aux1(
>>>
>>>This call (and the three later in this function) will do overload
>>>resolution again on the full set of __lexicographical_compare_aux1
>>>overloads, which includes the ones for deque iterators. But we know
>>>that __first1._M_cur and __first1._M_last are not deque iterators.
>>>
>>>__first2 could be a deque iterator, but I'm not sure if we really want
>>>one function that has to handle that case anyway.
>>>
>>>>+Â Â Â Â Â Â Â Â Â __first1._M_cur, __first1._M_last, __first2, __first2
>>>>+ __flen))
>>>>+Â Â Â Â Â Â Â return __ret;
>>>>+
>>>>+Â Â Â Â Â __first2 += __flen;
>>>>+Â Â Â Â Â __len -= __flen;
>>>>+Â Â Â Â Â __flen = std::min<size_t>(__len, _Iter::_S_buffer_size());
>>>>+Â Â Â Â Â for (typename _Iter::_Map_pointer __node = __first1._M_node + 1;
>>>>+Â Â Â Â Â Â Â Â Â Â __node != __last1._M_node;
>>>>+Â Â Â Â Â Â Â Â Â Â __first2 += __flen, __len -= __flen,
>>>>+Â Â Â Â Â Â Â Â Â Â __flen = std::min<size_t>(__len, _Iter::_S_buffer_size()),
>>>>+Â Â Â Â Â Â Â Â Â Â ++__node)
>>>>+Â Â Â Â Â Â Â if (int __ret = std::__lexicographical_compare_aux1(
>>>>+Â Â Â Â Â Â Â Â Â *__node, *__node + _Iter::_S_buffer_size(),
>>>>+Â Â Â Â Â Â Â Â Â __first2, __first2 + __flen))
>>>>+Â Â Â Â Â Â Â Â Â return __ret;
>>>>+
>>>>+Â Â Â Â Â return std::__lexicographical_compare_aux1(
>>>>+Â Â Â Â Â Â Â __last1._M_first, __last1._M_cur, __first2, __last2);
>>>>+Â Â Â }
>>>>+
>>>>+Â Â Â Â Â return std::__lexicographical_compare_aux1(
>>>>+Â Â Â Â Â Â Â Â Â __first1._M_cur, __last1._M_cur, __first2, __last2);
>>>>+Â Â Â }
>>>>+
>>>>+Â template<typename _Tp1, typename _Ref1, typename _Ptr1,
>>>>+Â Â Â Â Â Â typename _II2>
>>>
>>>This is not an input iterator either.
>>>
>>>>+Â Â Â typename __gnu_cxx::__enable_if<
>>>>+Â Â Â Â Â __is_random_access_iter<_II2>::__value, int>::__type
>>>
>>>This should be inline.
>>>
>>>Also, I'm curious why these overloads use __enable_if rather than the
>>>conventional approach of tag dispatching using iterator_category.
>>>(The same question applies to th __equal_aux1 and __copy_move_a1
>>>overloads for deque iterators as well). It doesn't really matter
>>>though.
>>>
>>>>+Â Â Â __lexicographical_compare_aux1(
>>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
>>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
>>>>+Â Â Â Â Â Â Â _II2 __first2, _II2 __last2)
>>>>+Â Â Â { return std::__lex_cmp_dit(__first1, __last1, __first2,
>>>>__last2); }
>>>>+
>>>>+Â template<typename _Tp1, typename _Ref1, typename _Ptr1,
>>>>+Â Â Â Â Â Â typename _Tp2, typename _Ref2, typename _Ptr2>
>>>>+Â Â Â int
>>>
>>>This should be inline.
>>>
>>>>+Â Â Â __lexicographical_compare_aux1(
>>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
>>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
>>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
>>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
>>>>+Â Â Â { return std::__lex_cmp_dit(__first1, __last1, __first2,
>>>>__last2); }
>>>
>>>I'm not convinced it's useful for this function and the one above it
>>>to share the same logic.
>>>
>>>>+Â template<typename _II1,
>>>>+Â Â Â Â Â Â typename _Tp2, typename _Ref2, typename _Ptr2>
>>>>+Â Â Â typename __gnu_cxx::__enable_if<
>>>>+Â Â Â Â Â __is_random_access_iter<_II1>::__value, int>::__type
>>>>+Â Â Â __lexicographical_compare_aux1(
>>>>+Â Â Â Â Â Â Â _II1 __first1, _II1 __last1,
>>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
>>>>+Â Â Â Â Â Â Â _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
>>>>+Â Â Â {
>>>>+Â Â Â Â Â typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2,
>>>>_Ptr2> _Iter;
>>>>+Â Â Â Â Â typedef typename _Iter::difference_type difference_type;
>>>>+
>>>>+Â Â Â Â Â difference_type __len = __last1 - __first1;
>>>>+Â Â Â Â Â while (__len > 0)
>>>>+Â Â Â {
>>>>+Â Â Â Â Â const difference_type __flen = __first2._M_node ==
>>>>__last2._M_node
>>>>+Â Â Â Â Â Â Â ? __last2._M_cur - __first2._M_cur
>>>>+Â Â Â Â Â Â Â : __first2._M_last - __first2._M_cur;
>>>>+Â Â Â Â Â const difference_type __clen = std::min(__len, __flen);
>>>
>>>"flen"? "clen"?
>>>
>>>>+Â Â Â Â Â if (int __ret = std::__lexicographical_compare_aux1(
>>>>+Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â __first1, __first1 + __clen,
>>>>+Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â __first2._M_cur, __first2._M_cur + __flen))
>>>>+Â Â Â Â Â Â Â return __ret;
>>>>+
>>>>+Â Â Â Â Â __first1 += __clen;
>>>>+Â Â Â Â Â __len -= __clen;
>>>>+Â Â Â Â Â __first2 += __clen;
>>>>+Â Â Â }
>>>>+
>>>>+Â Â Â Â Â return __first1 == __last1 ? (__first2 != __last2 ? -1 : 0) : 1;
>>>
>>>Isn't this function doing basically the same as __lex_cmp_dit? Why
>>>does it not use the same logic?
>>>
>>>Can this whole function just negate the result of __lex_cmp_dit called
>>>with the arguments switched?
>>>
>>>Â return -std::__lex_cmp_dit(__first2, __last2, __first1, __last1);
>>>
>>>That would also fix the bug that makes the following loop forever:
>>>
>>>Â std::deque<int> d;
>>>Â int i = 0;
>>>Â std::lexicographical_compare(&i, &i + 1, d.begin(), d.end());
>>
>>Same question for __equal_aux1, why is it implemented twice? Why
>>doesn't __equal_aux1(_II f1, _II l1, _Deque_iterator<> f2) just call
>>__equal_aux1(f2, f2 + (l1 - f1), f1) ?
>>
>Because I didn't thought about doing it this way. Yet another patch if
>you don't do it yourself.
I've already started working on it, so I'll do it.
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: libstdc++: Extend memcmp optimization in std::lexicographical_compare
2020-06-09 20:42 ` François Dumont
@ 2020-06-09 20:53 ` Jonathan Wakely
2020-06-10 6:18 ` François Dumont
0 siblings, 1 reply; 19+ messages in thread
From: Jonathan Wakely @ 2020-06-09 20:53 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 5004 bytes --]
On 09/06/20 22:42 +0200, François Dumont via Libstdc++ wrote:
>On 09/06/20 6:11 pm, Jonathan Wakely wrote:
>>On 09/06/20 00:02 +0100, Jonathan Wakely wrote:
>>>On 08/06/20 22:08 +0100, Jonathan Wakely wrote:
>>>>On 08/06/20 19:20 +0100, Jonathan Wakely wrote:
>>>>>On 05/06/20 22:24 +0200, François Dumont via Libstdc++ wrote:
>>>>>>Hi
>>>>>>
>>>>>>   Here is the last of my algo patches this time to
>>>>>>extend the memcmp optimization to std::deque iterators and
>>>>>>_GLIBCXX_DEBUG mode.
>>>>>>
>>>>>>   To do so I had to return int in implementation
>>>>>>details of lexicographical_compare to make sure we can treat
>>>>>>a deque iterator range by chunk in a performant way.
>>>>
>>>>Here's a simpler version, which doesn't alter anything for the
>>>>existing code (i.e. all iterators that aren't deque iterators) and
>>>>also fixes the infinite loop bug.
>>>>
>>>>This seems simpler and less invasive.
>>>>
>>>>Please take a look.
>>>
>>>I've actually tested it in debug mode now, and ...
>>>
>>>>diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc
>>>>b/libstdc++-v3/include/debug/safe_iterator.tcc
>>>>index 888ac803ae5..db6a301655f 100644
>>>>--- a/libstdc++-v3/include/debug/safe_iterator.tcc
>>>>+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
>>>>@@ -470,6 +470,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>>>Â Â Â Â return __equal_aux1(__first1, __last1, __first2);
>>>>Â Â }
>>>>
>>>>+Â template<typename _Ite1, typename _Seq1, typename _Cat1,
>>>>+Â Â Â Â Â Â typename _II2>
>>>>+Â Â Â int
>>>
>>>This should return bool here.
>>>
>>>>+Â Â Â __lexicographical_compare_aux(
>>>>+Â Â Â const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&
>>>>__first1,
>>>>+Â Â Â const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
>>>>+Â Â Â _II2 __first2, _II2 __last2)
>>>>+Â Â Â {
>>>>+Â Â Â Â Â typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
>>>>+Â Â Â Â Â __glibcxx_check_valid_range2(__first1, __last1, __dist1);
>>>>+Â Â Â Â Â __glibcxx_check_valid_range(__first2, __last2);
>>>>+
>>>>+Â Â Â Â Â if (__dist1.second > ::__gnu_debug::__dp_equality)
>>>>+Â Â Â return std::__lexicographical_compare_aux(__first1.base(),
>>>>+Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â __last1.base(),
>>>>+Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â __first2, __last2);
>>>>+Â Â Â Â Â return std::__lexicographical_compare_aux1(__first1, __last1,
>>>>+Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â __first2, __last2);
>>>>+Â Â Â }
>>>>+
>>>>+Â template<typename _II1,
>>>>+Â Â Â Â Â Â typename _Ite2, typename _Seq2, typename _Cat2>
>>>>+Â Â Â int
>>>
>>>And here.
>>>
>>>>+Â Â Â __lexicographical_compare_aux(
>>>>+Â Â Â _II1 __first1, _II1 __last1,
>>>>+Â Â Â const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&
>>>>__first2,
>>>>+Â Â Â const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
>>>>+Â Â Â {
>>>>+Â Â Â Â Â __glibcxx_check_valid_range(__first1, __last1);
>>>>+Â Â Â Â Â typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist2;
>>>>+Â Â Â Â Â __glibcxx_check_valid_range2(__first2, __last2, __dist2);
>>>>+
>>>>+Â Â Â Â Â if (__dist2.second > ::__gnu_debug::__dp_equality)
>>>>+Â Â Â return std::__lexicographical_compare_aux(__first1, __last1,
>>>>+Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â __first2.base(),
>>>>+Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â __last2.base());
>>>>+Â Â Â Â Â return std::__lexicographical_compare_aux1(__first1, __last1,
>>>>+Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â __first2, __last2);
>>>>+Â Â Â }
>>>>+
>>>>+Â template<typename _Ite1, typename _Seq1, typename _Cat1,
>>>>+Â Â Â Â Â Â typename _Ite2, typename _Seq2, typename _Cat2>
>>>>+Â Â Â int
>>>
>>>And here.
>>
>>And I've also enhanced the tests so they catch the bug I created where
>>the __lexicographical_compare_aux1 overload taking two ranges of deque
>>iterators was still trying to return a three-way result, rather than
>>bool.
>>
>>Corrected patch attached.
>>
>>But, the 25_algorithms/lexicographical_compare/deque_iterators/1.cc
>>test doesn't actually test the new code properly, because it only uses
>>deque<int> which means memcmp isn't even used. We need better tests.
>>
>>
>>.
>
>I didn't consider adding one cause I didn't need it to challenge the
>new code dedicated to deque iterators. I don't remember if I really
>check but for me there are already checks involving memcmp.
>
>Also I haven't found how to write a test checking that memcmp is
>indeed call, I haven't try hard neither.
It doesn't need to check that memcmp is actually called. The point is
that a bug in the __lexicographical_compare<true>::__lc function won't
get noticed if we never call that function.
The attached patch adds tests for deque<unsigned char> which will use
the memcmp code.
This reminds me that I was going to extend the condition for using
memcmp to also apply to unsigned integers with sizeof(T) > 1 on big
endian targets.
[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 27195 bytes --]
commit 6b4a9d81d7e1999ced2c1b01df70b3f6047b7ebd
Author: Fran??ois Dumont <fdumont@gcc.gnu.org>
Date: Tue Jun 9 00:01:51 2020 +0100
libstdc++: Extend memcmp optimization in std::lexicographical_compare
Make the memcmp optimization work for std::deque iterators and safe
iterators.
Co-authored-by: Jonathan Wakely <jwakely@redhat.com>
libstdc++-v3/ChangeLog:
2020-06-08 Fran??ois Dumont <fdumont@gcc.gnu.org>
Jonathan Wakely <jwakely@redhat.com>
* include/bits/deque.tcc (__lex_cmp_dit): New.
(__lexicographical_compare_aux1): Define overloads for deque
iterators.
* include/bits/stl_algobase.h (__lexicographical_compare::__3way):
New static member function.
(__lexicographical_compare<true>::__3way): Likewise.
(__lexicographical_compare<true>::__lc): Use __3way.
(__lexicographical_compare_aux): Rename to
__lexicographical_compare_aux1 and declare overloads for deque
iterators.
(__lexicographical_compare_aux): Define new forwarding function
that calls __lexicographical_compare_aux1 and declare new overloads
for safe iterators.
(lexicographical_compare): Do not use __niter_base on
parameters.
* include/debug/safe_iterator.tcc
(__lexicographical_compare_aux): Define overloads for safe
iterators.
* testsuite/25_algorithms/lexicographical_compare/1.cc: Add
checks with random access iterators.
* testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc:
New test.
libstdc++-v3/ChangeLog:
* include/bits/deque.tcc:
* include/bits/stl_algobase.h:
* include/debug/safe_iterator.tcc:
* testsuite/25_algorithms/lexicographical_compare/1.cc:
* testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc: New test.
diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
index 1d32a1691c7..7d1ec86456a 100644
--- a/libstdc++-v3/include/bits/deque.tcc
+++ b/libstdc++-v3/include/bits/deque.tcc
@@ -1261,6 +1261,109 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
return true;
}
+ template<typename _Tp1, typename _Ref, typename _Ptr, typename _Tp2>
+ int
+ __lex_cmp_dit(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __last1,
+ const _Tp2* __first2, const _Tp2* __last2)
+ {
+ const bool __simple =
+ (__is_byte<_Tp1>::__value && __is_byte<_Tp2>::__value
+ && !__gnu_cxx::__numeric_traits<_Tp1>::__is_signed
+ && !__gnu_cxx::__numeric_traits<_Tp2>::__is_signed
+ && __is_pointer<_Ptr>::__value
+#if __cplusplus > 201703L && __cpp_lib_concepts
+ // For C++20 iterator_traits<volatile T*>::value_type is non-volatile
+ // so __is_byte<T> could be true, but we can't use memcmp with
+ // volatile data.
+ && !is_volatile_v<_Tp1>
+ && !is_volatile_v<_Tp2>
+#endif
+ );
+ typedef std::__lexicographical_compare<__simple> _Lc;
+
+ while (__first1._M_node != __last1._M_node)
+ {
+ const ptrdiff_t __len1 = __first1._M_last - __first1._M_cur;
+ const ptrdiff_t __len2 = __last2 - __first2;
+ const ptrdiff_t __len = std::min(__len1, __len2);
+ // if __len1 > __len2 this will return a positive value:
+ if (int __ret = _Lc::__3way(__first1._M_cur, __first1._M_last,
+ __first2, __first2 + __len))
+ return __ret;
+
+ __first1 += __len;
+ __first2 += __len;
+ }
+ return _Lc::__3way(__first1._M_cur, __last1._M_cur,
+ __first2, __last2);
+ }
+
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2>
+ inline bool
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
+ _Tp2* __first2, _Tp2* __last2)
+ { return std::__lex_cmp_dit(__first1, __last1, __first2, __last2) < 0; }
+
+ template<typename _Tp1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ inline bool
+ __lexicographical_compare_aux1(_Tp1* __first1, _Tp1* __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
+ { return std::__lex_cmp_dit(__first2, __last2, __first1, __last1) > 0; }
+
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ inline bool
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
+ {
+ const bool __simple =
+ (__is_byte<_Tp1>::__value && __is_byte<_Tp2>::__value
+ && !__gnu_cxx::__numeric_traits<_Tp1>::__is_signed
+ && !__gnu_cxx::__numeric_traits<_Tp2>::__is_signed
+ && __is_pointer<_Ptr1>::__value
+ && __is_pointer<_Ptr2>::__value
+#if __cplusplus > 201703L && __cpp_lib_concepts
+ // For C++20 iterator_traits<volatile T*>::value_type is non-volatile
+ // so __is_byte<T> could be true, but we can't use memcmp with
+ // volatile data.
+ && !is_volatile_v<_Tp1>
+ && !is_volatile_v<_Tp2>
+#endif
+ );
+ typedef std::__lexicographical_compare<__simple> _Lc;
+
+ while (__first1 != __last1)
+ {
+ const ptrdiff_t __len2 = __first2._M_node == __last2._M_node
+ ? __last2._M_cur - __first2._M_cur
+ : __first2._M_last - __first2._M_cur;
+ if (__len2 == 0)
+ return false;
+ const ptrdiff_t __len1 = __first1._M_node == __last1._M_node
+ ? __last1._M_cur - __first1._M_cur
+ : __first1._M_last - __first1._M_cur;
+ const ptrdiff_t __len = std::min(__len1, __len2);
+ if (int __ret = _Lc::__3way(__first1._M_cur, __first1._M_cur + __len,
+ __first2._M_cur, __first2._M_cur + __len))
+ return __ret < 0;
+
+ __first1 += __len;
+ __first2 += __len;
+ }
+
+ return __last2 != __first2;
+ }
+
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 0163d8f902d..41dd740d34a 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -1313,6 +1313,25 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
__first2, __last2,
__iter_less_iter());
}
+
+ template<typename _II1, typename _II2>
+ _GLIBCXX20_CONSTEXPR
+ static int
+ __3way(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
+ {
+ while (__first1 != __last1)
+ {
+ if (__first2 == __last2)
+ return +1;
+ if (*__first1 < *__first2)
+ return -1;
+ if (*__first2 < *__first1)
+ return +1;
+ ++__first1;
+ ++__first2;
+ }
+ return int(__first2 == __last2) - 1;
+ }
};
template<>
@@ -1323,21 +1342,28 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
static bool
__lc(const _Tp* __first1, const _Tp* __last1,
const _Up* __first2, const _Up* __last2)
+ { return __3way(__first1, __last1, __first2, __last2) < 0; }
+
+ template<typename _Tp, typename _Up>
+ _GLIBCXX20_CONSTEXPR
+ static ptrdiff_t
+ __3way(const _Tp* __first1, const _Tp* __last1,
+ const _Up* __first2, const _Up* __last2)
{
const size_t __len1 = __last1 - __first1;
const size_t __len2 = __last2 - __first2;
if (const size_t __len = std::min(__len1, __len2))
if (int __result = std::__memcmp(__first1, __first2, __len))
- return __result < 0;
- return __len1 < __len2;
+ return __result;
+ return ptrdiff_t(__len1 - __len2);
}
};
template<typename _II1, typename _II2>
_GLIBCXX20_CONSTEXPR
inline bool
- __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
- _II2 __first2, _II2 __last2)
+ __lexicographical_compare_aux1(_II1 __first1, _II1 __last1,
+ _II2 __first2, _II2 __last2)
{
typedef typename iterator_traits<_II1>::value_type _ValueType1;
typedef typename iterator_traits<_II2>::value_type _ValueType2;
@@ -1360,6 +1386,67 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
__first2, __last2);
}
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2>
+ bool
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _Tp2*, _Tp2*);
+
+ template<typename _Tp1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ bool
+ __lexicographical_compare_aux1(_Tp1*, _Tp1*,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
+
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ bool
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
+
+ template<typename _II1, typename _II2>
+ _GLIBCXX20_CONSTEXPR
+ inline bool
+ __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
+ _II2 __first2, _II2 __last2)
+ {
+ return std::__lexicographical_compare_aux1(std::__niter_base(__first1),
+ std::__niter_base(__last1),
+ std::__niter_base(__first2),
+ std::__niter_base(__last2));
+ }
+
+ template<typename _Iter1, typename _Seq1, typename _Cat1,
+ typename _II2>
+ bool
+ __lexicographical_compare_aux(
+ const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
+ const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
+ _II2, _II2);
+
+ template<typename _II1,
+ typename _Iter2, typename _Seq2, typename _Cat2>
+ bool
+ __lexicographical_compare_aux(
+ _II1, _II1,
+ const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
+ const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
+
+ template<typename _Iter1, typename _Seq1, typename _Cat1,
+ typename _Iter2, typename _Seq2, typename _Cat2>
+ bool
+ __lexicographical_compare_aux(
+ const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
+ const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
+ const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
+ const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
+
template<typename _ForwardIterator, typename _Tp, typename _Compare>
_GLIBCXX20_CONSTEXPR
_ForwardIterator
@@ -1659,10 +1746,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
__glibcxx_requires_valid_range(__first1, __last1);
__glibcxx_requires_valid_range(__first2, __last2);
- return std::__lexicographical_compare_aux(std::__niter_base(__first1),
- std::__niter_base(__last1),
- std::__niter_base(__first2),
- std::__niter_base(__last2));
+ return std::__lexicographical_compare_aux(__first1, __last1,
+ __first2, __last2);
}
/**
diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
index 888ac803ae5..f694e514239 100644
--- a/libstdc++-v3/include/debug/safe_iterator.tcc
+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
@@ -470,6 +470,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return __equal_aux1(__first1, __last1, __first2);
}
+ template<typename _Ite1, typename _Seq1, typename _Cat1,
+ typename _II2>
+ bool
+ __lexicographical_compare_aux(
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
+ _II2 __first2, _II2 __last2)
+ {
+ typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
+ __glibcxx_check_valid_range2(__first1, __last1, __dist1);
+ __glibcxx_check_valid_range(__first2, __last2);
+
+ if (__dist1.second > ::__gnu_debug::__dp_equality)
+ return std::__lexicographical_compare_aux(__first1.base(),
+ __last1.base(),
+ __first2, __last2);
+ return std::__lexicographical_compare_aux1(__first1, __last1,
+ __first2, __last2);
+ }
+
+ template<typename _II1,
+ typename _Ite2, typename _Seq2, typename _Cat2>
+ bool
+ __lexicographical_compare_aux(
+ _II1 __first1, _II1 __last1,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
+ {
+ __glibcxx_check_valid_range(__first1, __last1);
+ typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist2;
+ __glibcxx_check_valid_range2(__first2, __last2, __dist2);
+
+ if (__dist2.second > ::__gnu_debug::__dp_equality)
+ return std::__lexicographical_compare_aux(__first1, __last1,
+ __first2.base(),
+ __last2.base());
+ return std::__lexicographical_compare_aux1(__first1, __last1,
+ __first2, __last2);
+ }
+
+ template<typename _Ite1, typename _Seq1, typename _Cat1,
+ typename _Ite2, typename _Seq2, typename _Cat2>
+ bool
+ __lexicographical_compare_aux(
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
+ {
+ typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
+ __glibcxx_check_valid_range2(__first1, __last1, __dist1);
+ typename ::__gnu_debug::_Distance_traits<_Ite2>::__type __dist2;
+ __glibcxx_check_valid_range2(__first2, __last2, __dist2);
+
+ if (__dist1.second > ::__gnu_debug::__dp_equality)
+ {
+ if (__dist2.second > ::__gnu_debug::__dp_equality)
+ return std::__lexicographical_compare_aux(__first1.base(),
+ __last1.base(),
+ __first2.base(),
+ __last2.base());
+ return std::__lexicographical_compare_aux(__first1.base(),
+ __last1.base(),
+ __first2, __last2);
+ }
+
+ if (__dist2.second > ::__gnu_debug::__dp_equality)
+ return std::__lexicographical_compare_aux(__first1, __last1,
+ __first2.base(),
+ __last2.base());
+ return std::__lexicographical_compare_aux1(__first1, __last1,
+ __first2, __last2);
+ }
+
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
index 8c2f043f943..9bbc83b7af0 100644
--- a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
@@ -29,43 +29,43 @@ int array1[] = {0, 1};
int array2[] = {1, 0};
int array3[] = {1, 0, 1};
-void
+void
test1()
{
Container con1(array1, array1);
Container con2(array2, array2);
- VERIFY( !std::lexicographical_compare(con1.begin(), con1.end(),
+ VERIFY( !std::lexicographical_compare(con1.begin(), con1.end(),
con2.begin(), con2.end()) );
}
-void
+void
test2()
{
Container con1(array1, array1 + 2);
Container con2(array2, array2 + 2);
- VERIFY( std::lexicographical_compare(con1.begin(), con1.end(),
+ VERIFY( std::lexicographical_compare(con1.begin(), con1.end(),
con2.begin(), con2.end()) );
}
-void
+void
test3()
{
Container con1(array1, array1 + 2);
Container con2(array2, array2 + 2);
- VERIFY( !std::lexicographical_compare(con2.begin(), con2.end(),
+ VERIFY( !std::lexicographical_compare(con2.begin(), con2.end(),
con1.begin(), con1.end()) );
}
-void
+void
test4()
{
Container con3(array3, array3 + 3);
Container con2(array2, array2 + 2);
- VERIFY( std::lexicographical_compare(con2.begin(), con2.end(),
+ VERIFY( std::lexicographical_compare(con2.begin(), con2.end(),
con3.begin(), con3.end()) );
}
-void
+void
test5()
{
Container con3(array3, array3 + 3);
@@ -74,7 +74,30 @@ test5()
con2.begin(), con2.end()) );
}
-int
+void
+test6()
+{
+ VERIFY( std::lexicographical_compare(array2, array2 + 2,
+ array3, array3 + 3) );
+ VERIFY( !std::lexicographical_compare(array3, array3 + 3,
+ array2, array2 + 2) );
+}
+
+using __gnu_test::random_access_iterator_wrapper;
+typedef test_container<int, random_access_iterator_wrapper> RaiContainer;
+
+void
+test7()
+{
+ RaiContainer con2(array2, array2 + 2);
+ RaiContainer con3(array3, array3 + 3);
+ VERIFY( std::lexicographical_compare(con2.begin(), con2.end(),
+ con3.begin(), con3.end()) );
+ VERIFY( !std::lexicographical_compare(con3.begin(), con3.end(),
+ con2.begin(), con2.end()) );
+}
+
+int
main()
{
test1();
@@ -82,4 +105,6 @@ main()
test3();
test4();
test5();
+ test6();
+ test7();
}
diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc
new file mode 100644
index 00000000000..14a75358db4
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc
@@ -0,0 +1,301 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <algorithm>
+#include <vector>
+#include <deque>
+
+#include <ext/new_allocator.h>
+#include <ext/malloc_allocator.h>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i)
+ d.push_back(i);
+
+ const deque<int>& cd = d;
+
+ VERIFY( !lexicographical_compare(cd.begin(), cd.end(), cd.begin(), cd.end()) );
+ VERIFY( !lexicographical_compare(cd.begin(), cd.end(), d.begin(), d.end()) );
+ VERIFY( !lexicographical_compare(d.begin(), d.end(), d.begin(), d.end()) );
+ VERIFY( !lexicographical_compare(d.begin(), d.end(), cd.begin(), cd.end()) );
+
+ const deque<int>::iterator first = d.begin(), last = d.end();
+ VERIFY( lexicographical_compare(first, last - 1, first, last) );
+ VERIFY( !lexicographical_compare(first, last, first, last - 1) );
+ VERIFY( lexicographical_compare(first, last, first + 1, last) );
+ VERIFY( !lexicographical_compare(first + 1, last, first, last) );
+}
+
+void test02()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != 1000; ++i)
+ d.push_back(i % 10);
+
+ VERIFY( lexicographical_compare(d.begin(), d.begin() + 10,
+ d.begin() + 21, d.begin() + 31) );
+ VERIFY( lexicographical_compare(d.begin(), d.begin() + 10,
+ d.begin() + 20, d.begin() + 31) );
+ VERIFY( ! lexicographical_compare(d.begin() + 1, d.begin() + 10,
+ d.begin() + 21, d.begin() + 30) );
+ VERIFY( !lexicographical_compare(d.begin(), d.begin() + 10,
+ d.begin() + 20, d.begin() + 30) );
+ VERIFY( !lexicographical_compare(d.begin() + 1, d.begin() + 10,
+ d.begin() + 1 + 20, d.begin() + 30) );
+ VERIFY( lexicographical_compare(d.begin(), d.begin() + 10,
+ d.begin() + 20, d.begin() + 31) );
+ VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10,
+ d.begin(), d.end() - 20) );
+
+ const deque<int>& cd = d;
+
+ VERIFY( lexicographical_compare(cd.begin(), cd.begin() + 10,
+ cd.begin() + 21, cd.begin() + 31) );
+ VERIFY( lexicographical_compare(cd.begin() + 1, cd.begin() + 10,
+ cd.begin() + 21, cd.begin() + 32) );
+ VERIFY( !lexicographical_compare(cd.begin(), cd.begin() + 10,
+ cd.begin() + 20, cd.begin() + 30) );
+ VERIFY( !lexicographical_compare(cd.begin() + 1, cd.begin() + 10,
+ cd.begin() + 21, cd.begin() + 30) );
+ VERIFY( !lexicographical_compare(cd.begin() + 10, cd.end() - 10,
+ d.begin(), d.end() - 20) );
+ VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10,
+ cd.begin(), cd.end() - 20) );
+}
+
+void test03()
+{
+ using namespace std;
+
+ deque<int> d1;
+ for (int i = 0; i != 1000; ++i)
+ d1.push_back(i % 10);
+
+ deque<int> d2(d1);
+ for (int i = 0; i != 10; ++i)
+ d2.pop_front();
+
+ VERIFY( !lexicographical_compare(d1.begin(), d1.begin() + 10,
+ d2.begin(), d2.begin() + 10) );
+ VERIFY( !lexicographical_compare(d1.begin() + 10, d1.end() - 10,
+ d2.begin(), d2.end() - 10) );
+
+ const deque<int>& cd1 = d1;
+ const deque<int>& cd2 = d2;
+
+ VERIFY( !lexicographical_compare(cd1.begin(), cd1.begin() + 10,
+ cd2.begin() + 20, cd2.begin() + 30) );
+ VERIFY( !lexicographical_compare(cd1.begin() + 10, cd1.end() - 10,
+ d2.begin(), d2.end() - 10) );
+ VERIFY( lexicographical_compare(cd2.begin() + 10, cd2.end() - 10,
+ cd1.begin(), cd1.end() - 20) );
+}
+
+void test04()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ vector<int> v(d.begin(), d.end());
+
+ VERIFY( lexicographical_compare(d.begin() + 5, d.end() - 1, v.begin() + 5, v.end()) );
+ VERIFY( !lexicographical_compare(v.begin(), v.end(), d.begin(), d.end()) );
+
+ const deque<int>& cd = d;
+
+ VERIFY( !lexicographical_compare(cd.begin(), cd.end(), v.begin(), v.end()) );
+ VERIFY( !lexicographical_compare(v.begin(), v.end(), cd.begin(), cd.end()) );
+}
+
+void test05()
+{
+ using namespace std;
+
+ int a[] = { 0, 1, 2, 3, 4 };
+ deque<int, __gnu_cxx::new_allocator<int> > d1(a, a + 5);
+ deque<int, __gnu_cxx::malloc_allocator<int> > d2(a, a + 5);
+
+ VERIFY( !lexicographical_compare(d1.begin(), d1.end(), d2.begin(), d2.end()) );
+}
+
+void
+test06()
+{
+ using namespace std;
+
+ deque<int> d;
+ int i = 0;
+ VERIFY( lexicographical_compare(d.begin(), d.end(), &i, &i + 1) );
+ VERIFY( !lexicographical_compare(&i, &i + 1, d.begin(), d.end()) );
+}
+
+void test07()
+{
+ using namespace std;
+
+ deque<unsigned char> d;
+ for (int i = 0; i != _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i)
+ d.push_back(i);
+
+ const deque<unsigned char>& cd = d;
+
+ VERIFY( !lexicographical_compare(cd.begin(), cd.end(), cd.begin(), cd.end()) );
+ VERIFY( !lexicographical_compare(cd.begin(), cd.end(), d.begin(), d.end()) );
+ VERIFY( !lexicographical_compare(d.begin(), d.end(), d.begin(), d.end()) );
+ VERIFY( !lexicographical_compare(d.begin(), d.end(), cd.begin(), cd.end()) );
+
+ const deque<unsigned char>::iterator first = d.begin(), last = d.end();
+ VERIFY( lexicographical_compare(first, last - 1, first, last) );
+ VERIFY( !lexicographical_compare(first, last, first, last - 1) );
+ VERIFY( lexicographical_compare(first, last, first + 1, last) );
+ VERIFY( !lexicographical_compare(first + 1, last, first, last) );
+}
+
+void test08()
+{
+ using namespace std;
+
+ deque<unsigned char> d;
+ for (int i = 0; i != 1000; ++i)
+ d.push_back(i % 10);
+
+ VERIFY( lexicographical_compare(d.begin(), d.begin() + 10,
+ d.begin() + 21, d.begin() + 31) );
+ VERIFY( lexicographical_compare(d.begin(), d.begin() + 10,
+ d.begin() + 20, d.begin() + 31) );
+ VERIFY( ! lexicographical_compare(d.begin() + 1, d.begin() + 10,
+ d.begin() + 21, d.begin() + 30) );
+ VERIFY( !lexicographical_compare(d.begin(), d.begin() + 10,
+ d.begin() + 20, d.begin() + 30) );
+ VERIFY( !lexicographical_compare(d.begin() + 1, d.begin() + 10,
+ d.begin() + 1 + 20, d.begin() + 30) );
+ VERIFY( lexicographical_compare(d.begin(), d.begin() + 10,
+ d.begin() + 20, d.begin() + 31) );
+ VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10,
+ d.begin(), d.end() - 20) );
+
+ const deque<unsigned char>& cd = d;
+
+ VERIFY( lexicographical_compare(cd.begin(), cd.begin() + 10,
+ cd.begin() + 21, cd.begin() + 31) );
+ VERIFY( lexicographical_compare(cd.begin() + 1, cd.begin() + 10,
+ cd.begin() + 21, cd.begin() + 32) );
+ VERIFY( !lexicographical_compare(cd.begin(), cd.begin() + 10,
+ cd.begin() + 20, cd.begin() + 30) );
+ VERIFY( !lexicographical_compare(cd.begin() + 1, cd.begin() + 10,
+ cd.begin() + 21, cd.begin() + 30) );
+ VERIFY( !lexicographical_compare(cd.begin() + 10, cd.end() - 10,
+ d.begin(), d.end() - 20) );
+ VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10,
+ cd.begin(), cd.end() - 20) );
+}
+
+void test09()
+{
+ using namespace std;
+
+ deque<unsigned char> d1;
+ for (int i = 0; i != 1000; ++i)
+ d1.push_back(i % 10);
+
+ deque<unsigned char> d2(d1);
+ for (int i = 0; i != 10; ++i)
+ d2.pop_front();
+
+ VERIFY( !lexicographical_compare(d1.begin(), d1.begin() + 10,
+ d2.begin(), d2.begin() + 10) );
+ VERIFY( !lexicographical_compare(d1.begin() + 10, d1.end() - 10,
+ d2.begin(), d2.end() - 10) );
+
+ const deque<unsigned char>& cd1 = d1;
+ const deque<unsigned char>& cd2 = d2;
+
+ VERIFY( !lexicographical_compare(cd1.begin(), cd1.begin() + 10,
+ cd2.begin() + 20, cd2.begin() + 30) );
+ VERIFY( !lexicographical_compare(cd1.begin() + 10, cd1.end() - 10,
+ d2.begin(), d2.end() - 10) );
+ VERIFY( lexicographical_compare(cd2.begin() + 10, cd2.end() - 10,
+ cd1.begin(), cd1.end() - 20) );
+}
+
+void test10()
+{
+ using namespace std;
+
+ deque<unsigned char> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ vector<unsigned char> v(d.begin(), d.end());
+
+ VERIFY( lexicographical_compare(d.begin() + 5, d.end() - 1, v.begin() + 5, v.end()) );
+ VERIFY( !lexicographical_compare(v.begin(), v.end(), d.begin(), d.end()) );
+
+ const deque<unsigned char>& cd = d;
+
+ VERIFY( !lexicographical_compare(cd.begin(), cd.end(), v.begin(), v.end()) );
+ VERIFY( !lexicographical_compare(v.begin(), v.end(), cd.begin(), cd.end()) );
+}
+
+void test11()
+{
+ using namespace std;
+
+ int a[] = { 0, 1, 2, 3, 4 };
+ deque<unsigned char, __gnu_cxx::new_allocator<unsigned char> > d1(a, a + 5);
+ deque<unsigned char, __gnu_cxx::malloc_allocator<unsigned char> > d2(a, a + 5);
+
+ VERIFY( !lexicographical_compare(d1.begin(), d1.end(), d2.begin(), d2.end()) );
+}
+
+void
+test12()
+{
+ using namespace std;
+
+ deque<unsigned char> d;
+ int i = 0;
+ VERIFY( lexicographical_compare(d.begin(), d.end(), &i, &i + 1) );
+ VERIFY( !lexicographical_compare(&i, &i + 1, d.begin(), d.end()) );
+}
+
+int main()
+{
+ test01();
+ test02();
+ test03();
+ test04();
+ test05();
+ test06();
+ test07();
+ test08();
+ test09();
+ test10();
+ test11();
+ test12();
+}
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: libstdc++: Extend memcmp optimization in std::lexicographical_compare
2020-06-09 20:53 ` Jonathan Wakely
@ 2020-06-10 6:18 ` François Dumont
2020-06-10 14:49 ` Jonathan Wakely
0 siblings, 1 reply; 19+ messages in thread
From: François Dumont @ 2020-06-10 6:18 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: libstdc++, gcc-patches
On 09/06/20 10:53 pm, Jonathan Wakely wrote:
> On 09/06/20 22:42 +0200, François Dumont via Libstdc++ wrote:
>> On 09/06/20 6:11 pm, Jonathan Wakely wrote:
>>> On 09/06/20 00:02 +0100, Jonathan Wakely wrote:
>>>> On 08/06/20 22:08 +0100, Jonathan Wakely wrote:
>>>>> On 08/06/20 19:20 +0100, Jonathan Wakely wrote:
>>>>>> On 05/06/20 22:24 +0200, François Dumont via Libstdc++ wrote:
>>>>>>> Hi
>>>>>>>
>>>>>>>    Here is the last of my algo patches this time to
>>>>>>> extend the memcmp optimization to std::deque iterators and
>>>>>>> _GLIBCXX_DEBUG mode.
>>>>>>>
>>>>>>>    To do so I had to return int in implementation
>>>>>>> details of lexicographical_compare to make sure we can treat a
>>>>>>> deque iterator range by chunk in a performant way.
>>>>>
>>>>> Here's a simpler version, which doesn't alter anything for the
>>>>> existing code (i.e. all iterators that aren't deque iterators) and
>>>>> also fixes the infinite loop bug.
>>>>>
>>>>> This seems simpler and less invasive.
>>>>>
>>>>> Please take a look.
>>>>
>>>> I've actually tested it in debug mode now, and ...
>>>>
>>>>> diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc
>>>>> b/libstdc++-v3/include/debug/safe_iterator.tcc
>>>>> index 888ac803ae5..db6a301655f 100644
>>>>> --- a/libstdc++-v3/include/debug/safe_iterator.tcc
>>>>> +++ b/libstdc++-v3/include/debug/safe_iterator.tcc
>>>>> @@ -470,6 +470,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>>>> Â Â Â Â return __equal_aux1(__first1, __last1, __first2);
>>>>> Â Â }
>>>>>
>>>>> +Â template<typename _Ite1, typename _Seq1, typename _Cat1,
>>>>> +Â Â Â Â Â Â typename _II2>
>>>>> +Â Â Â int
>>>>
>>>> This should return bool here.
>>>>
>>>>> +Â Â Â __lexicographical_compare_aux(
>>>>> +Â Â Â const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&
>>>>> __first1,
>>>>> +Â Â Â const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&
>>>>> __last1,
>>>>> +Â Â Â _II2 __first2, _II2 __last2)
>>>>> +Â Â Â {
>>>>> +Â Â Â Â Â typename
>>>>> ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
>>>>> +Â Â Â Â Â __glibcxx_check_valid_range2(__first1, __last1, __dist1);
>>>>> +Â Â Â Â Â __glibcxx_check_valid_range(__first2, __last2);
>>>>> +
>>>>> +Â Â Â Â Â if (__dist1.second > ::__gnu_debug::__dp_equality)
>>>>> +Â Â Â return std::__lexicographical_compare_aux(__first1.base(),
>>>>> +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â __last1.base(),
>>>>> +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â __first2,
>>>>> __last2);
>>>>> +Â Â Â Â Â return std::__lexicographical_compare_aux1(__first1,
>>>>> __last1,
>>>>> +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â __first2, __last2);
>>>>> +Â Â Â }
>>>>> +
>>>>> +Â template<typename _II1,
>>>>> +Â Â Â Â Â Â typename _Ite2, typename _Seq2, typename _Cat2>
>>>>> +Â Â Â int
>>>>
>>>> And here.
>>>>
>>>>> +Â Â Â __lexicographical_compare_aux(
>>>>> +Â Â Â _II1 __first1, _II1 __last1,
>>>>> +Â Â Â const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&
>>>>> __first2,
>>>>> +Â Â Â const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&
>>>>> __last2)
>>>>> +Â Â Â {
>>>>> +Â Â Â Â Â __glibcxx_check_valid_range(__first1, __last1);
>>>>> +Â Â Â Â Â typename ::__gnu_debug::_Distance_traits<_II1>::__type
>>>>> __dist2;
>>>>> +Â Â Â Â Â __glibcxx_check_valid_range2(__first2, __last2, __dist2);
>>>>> +
>>>>> +Â Â Â Â Â if (__dist2.second > ::__gnu_debug::__dp_equality)
>>>>> +Â Â Â return std::__lexicographical_compare_aux(__first1, __last1,
>>>>> +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â __first2.base(),
>>>>> +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â __last2.base());
>>>>> +Â Â Â Â Â return std::__lexicographical_compare_aux1(__first1,
>>>>> __last1,
>>>>> +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â __first2, __last2);
>>>>> +Â Â Â }
>>>>> +
>>>>> +Â template<typename _Ite1, typename _Seq1, typename _Cat1,
>>>>> +Â Â Â Â Â Â typename _Ite2, typename _Seq2, typename _Cat2>
>>>>> +Â Â Â int
>>>>
>>>> And here.
>>>
>>> And I've also enhanced the tests so they catch the bug I created where
>>> the __lexicographical_compare_aux1 overload taking two ranges of deque
>>> iterators was still trying to return a three-way result, rather than
>>> bool.
>>>
>>> Corrected patch attached.
>>>
>>> But, the 25_algorithms/lexicographical_compare/deque_iterators/1.cc
>>> test doesn't actually test the new code properly, because it only uses
>>> deque<int> which means memcmp isn't even used. We need better tests.
>>>
>>>
>>> .
>>
>> I didn't consider adding one cause I didn't need it to challenge the
>> new code dedicated to deque iterators. I don't remember if I really
>> check but for me there are already checks involving memcmp.
>>
>> Also I haven't found how to write a test checking that memcmp is
>> indeed call, I haven't try hard neither.
>
> It doesn't need to check that memcmp is actually called. The point is
> that a bug in the __lexicographical_compare<true>::__lc function won't
> get noticed if we never call that function.
Sure, I just thought this call was already tested as it isn't new code
introduce by this patch.
>
> The attached patch adds tests for deque<unsigned char> which will use
> the memcmp code.
>
> This reminds me that I was going to extend the condition for using
> memcmp to also apply to unsigned integers with sizeof(T) > 1 on big
> endian targets.
>
This illustrates what I tried to avoid in my original patch, the code
duplication. I was calling __lexicographical_compare_aux1 because I
didn't want to duplicate the code to compute __simple.
Of course it can be expose as a template using.
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: libstdc++: Extend memcmp optimization in std::lexicographical_compare
2020-06-10 6:18 ` François Dumont
@ 2020-06-10 14:49 ` Jonathan Wakely
2020-06-10 16:40 ` François Dumont
0 siblings, 1 reply; 19+ messages in thread
From: Jonathan Wakely @ 2020-06-10 14:49 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On 10/06/20 08:18 +0200, François Dumont via Libstdc++ wrote:
>On 09/06/20 10:53 pm, Jonathan Wakely wrote:
>>This reminds me that I was going to extend the condition for using
>>memcmp to also apply to unsigned integers with sizeof(T) > 1 on big
>>endian targets.
>>
>This illustrates what I tried to avoid in my original patch, the code
>duplication. I was calling __lexicographical_compare_aux1 because I
>didn't want to duplicate the code to compute __simple.
>
>Of course it can be expose as a template using.
Not for C++98.
I'm not very concerned about duplicating the boolean condition. I
definitely prefer that to codegen changes that affect every user of
lexicographical_compare just to benefit the handful of people using
it with std::deque.
If __lexicographical_compare_aux1 could be reused without changes,
great, but it needed changes with consequences for more code than just
deque iterators.
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: libstdc++: Extend memcmp optimization in std::lexicographical_compare
2020-06-10 14:49 ` Jonathan Wakely
@ 2020-06-10 16:40 ` François Dumont
2020-06-10 17:14 ` Jonathan Wakely
0 siblings, 1 reply; 19+ messages in thread
From: François Dumont @ 2020-06-10 16:40 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: libstdc++, gcc-patches
On 10/06/20 4:49 pm, Jonathan Wakely wrote:
> On 10/06/20 08:18 +0200, François Dumont via Libstdc++ wrote:
>> On 09/06/20 10:53 pm, Jonathan Wakely wrote:
>>> This reminds me that I was going to extend the condition for using
>>> memcmp to also apply to unsigned integers with sizeof(T) > 1 on big
>>> endian targets.
>>>
>> This illustrates what I tried to avoid in my original patch, the code
>> duplication. I was calling __lexicographical_compare_aux1 because I
>> didn't want to duplicate the code to compute __simple.
>>
>> Of course it can be expose as a template using.
>
> Not for C++98.
>
> I'm not very concerned about duplicating the boolean condition. I
> definitely prefer that to codegen changes that affect every user of
> lexicographical_compare just to benefit the handful of people using
> it with std::deque.
>
> If __lexicographical_compare_aux1 could be reused without changes,
> great, but it needed changes with consequences for more code than just
> deque iterators.
>
>
That's fine with me, the patch looks good.
Do you want me to get rid of the enable_if usage before the commit ?
Otherwise I let you commit it ?
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: libstdc++: Extend memcmp optimization in std::lexicographical_compare
2020-06-10 16:40 ` François Dumont
@ 2020-06-10 17:14 ` Jonathan Wakely
0 siblings, 0 replies; 19+ messages in thread
From: Jonathan Wakely @ 2020-06-10 17:14 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On 10/06/20 18:40 +0200, François Dumont wrote:
>On 10/06/20 4:49 pm, Jonathan Wakely wrote:
>>On 10/06/20 08:18 +0200, François Dumont via Libstdc++ wrote:
>>>On 09/06/20 10:53 pm, Jonathan Wakely wrote:
>>>>This reminds me that I was going to extend the condition for using
>>>>memcmp to also apply to unsigned integers with sizeof(T) > 1 on big
>>>>endian targets.
>>>>
>>>This illustrates what I tried to avoid in my original patch, the
>>>code duplication. I was calling __lexicographical_compare_aux1
>>>because I didn't want to duplicate the code to compute __simple.
>>>
>>>Of course it can be expose as a template using.
>>
>>Not for C++98.
>>
>>I'm not very concerned about duplicating the boolean condition. I
>>definitely prefer that to codegen changes that affect every user of
>>lexicographical_compare just to benefit the handful of people using
>>it with std::deque.
>>
>>If __lexicographical_compare_aux1 could be reused without changes,
>>great, but it needed changes with consequences for more code than just
>>deque iterators.
>>
>>
>That's fine with me, the patch looks good.
>
>Do you want me to get rid of the enable_if usage before the commit ?
>
>Otherwise I let you commit it ?
I've pushed it to master now.
^ permalink raw reply [flat|nested] 19+ messages in thread
end of thread, other threads:[~2020-06-10 17:14 UTC | newest]
Thread overview: 19+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-06-05 20:24 libstdc++: Extend memcmp optimization in std::lexicographical_compare François Dumont
2020-06-08 18:20 ` Jonathan Wakely
2020-06-08 21:08 ` Jonathan Wakely
2020-06-08 23:02 ` Jonathan Wakely
2020-06-09 16:11 ` Jonathan Wakely
2020-06-09 16:12 ` Jonathan Wakely
2020-06-09 20:42 ` François Dumont
2020-06-09 20:53 ` Jonathan Wakely
2020-06-10 6:18 ` François Dumont
2020-06-10 14:49 ` Jonathan Wakely
2020-06-10 16:40 ` François Dumont
2020-06-10 17:14 ` Jonathan Wakely
2020-06-09 10:24 ` Jonathan Wakely
2020-06-09 20:35 ` François Dumont
2020-06-09 20:50 ` Jonathan Wakely
2020-06-09 20:20 ` François Dumont
2020-06-09 20:38 ` Jonathan Wakely
2020-06-08 20:07 ` Jonathan Wakely
2020-06-08 21:05 ` Jonathan Wakely
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).