This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Improve _Safe_iterator _M_distance_to
- From: François Dumont <frs dot dumont at gmail dot com>
- To: Jonathan Wakely <jwakely at redhat dot com>
- Cc: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Fri, 4 Oct 2019 22:31:13 +0200
- Subject: Re: [PATCH] Improve _Safe_iterator _M_distance_to
- References: <2702eec9-a1fb-06fb-43ce-946d8785dbf4@gmail.com> <20190927114559.GW9487@redhat.com>
I eventually committed the attach patch.
The usage of __dp_sign_max_size will come later.
François
On 9/27/19 1:45 PM, Jonathan Wakely wrote:
On 16/09/19 22:31 +0200, François Dumont wrote:
Here is the patch to improve _Safe_iterator<>::_M_get_distance_to
implementation.
I introduced a new _Distance_precision __sp_sign_max_size for
occasions where we can't find out the exact size of a range but still
get the max size of it. Thanks to this the performance tests are much
better when dealing with list iterators:
Normal mode:
copy_backward_deque_iterators.cc deque 2 list 5616r 5616u
0s 0mem 0pf
copy_backward_deque_iterators.cc list 2 deque 1586r 1586u
0s 0mem 0pf
copy_deque_iterators.cc deque 2 list 5495r
5495u 0s 0mem 0pf
copy_deque_iterators.cc list 2 deque 2400r
2400u 0s 0mem 0pf
Debug mode:
copy_backward_deque_iterators.cc deque 2 list 5789r 5785u
1s 0mem 0pf
copy_backward_deque_iterators.cc list 2 deque 1656r 1655u
0s 0mem 0pf
copy_deque_iterators.cc deque 2 list 5792r
5793u 0s 0mem 0pf
copy_deque_iterators.cc list 2 deque 2636r
2636u 0s 0mem 0pf
Tested under Linux x86_64.
I'll commit once other patches are in.
* include/debug/forward_list
(_Sequence_traits<__debug::forward_list<>>::_S_size): Returns __dp_sign
distance when not empty.
* include/debug/list
(_Sequence_traits<__debug::list<>>::_S_size): Likewise.
* include/debug/helper_functions.h (__dp_sign_max_size): New
_Distance_precision enum entry.
* include/debug/safe_iterator.h
(__copy_move_a(_II, _II, const _Safe_iterator<>&)): Check for output
iterator _M_can_advance as soon as input range distance precision is
strictly higher than __dp_size.
(__copy_move_a(const _Safe_iterator<>&, const _Safe_iterator<>&,
const _Safe_iterator<>&)): Likewise.
(__copy_move_backward_a(_II, _II, const _Safe_iterator<>&)):
Likewise.
(__copy_move_backward_a(const _Safe_iterator<>&,
const _Safe_iterator<>&, const _Safe_iterator<>&)): Likewise.
(__equal_aux(_II, _II, const _Safe_iterator<>&)): Likewise.
(__equal_aux(const _Safe_iterator<>&,
const _Safe_iterator<>&, const _Safe_iterator<>&)): Likewise.
The patch looks OK, but the safe_iterator.tcc changes are not listed
in the changelog, and those are the most complex part of the patch.
Please add a changelog entry for the _M_get_distance_to changes. OK
for trunk after that, thanks.
diff --git a/libstdc++-v3/include/debug/forward_list b/libstdc++-v3/include/debug/forward_list
index e30b000009e..f1756ddec9d 100644
--- a/libstdc++-v3/include/debug/forward_list
+++ b/libstdc++-v3/include/debug/forward_list
@@ -911,7 +911,7 @@ namespace __gnu_debug
_S_size(const std::__debug::forward_list<_Tp, _Alloc>& __seq)
{
return __seq.empty()
- ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_equality);
+ ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_sign);
}
};
diff --git a/libstdc++-v3/include/debug/helper_functions.h b/libstdc++-v3/include/debug/helper_functions.h
index 475fdda1d7b..5a920bb9a6f 100644
--- a/libstdc++-v3/include/debug/helper_functions.h
+++ b/libstdc++-v3/include/debug/helper_functions.h
@@ -50,10 +50,11 @@ namespace __gnu_debug
*/
enum _Distance_precision
{
- __dp_none, // Not even an iterator type
- __dp_equality, //< Can compare iterator equality, only
- __dp_sign, //< Can determine equality and ordering
- __dp_exact //< Can determine distance precisely
+ __dp_none, // Not even an iterator type
+ __dp_equality, //< Can compare iterator equality, only
+ __dp_sign, //< Can determine equality and ordering
+ __dp_sign_max_size, //< __dp_sign and gives max range size
+ __dp_exact //< Can determine distance precisely
};
template<typename _Iterator,
@@ -176,6 +177,7 @@ namespace __gnu_debug
return true;
break;
case __dp_sign:
+ case __dp_sign_max_size:
case __dp_exact:
return __dist.first >= 0;
}
diff --git a/libstdc++-v3/include/debug/list b/libstdc++-v3/include/debug/list
index 5eb9a6094e3..140546a633e 100644
--- a/libstdc++-v3/include/debug/list
+++ b/libstdc++-v3/include/debug/list
@@ -916,7 +916,7 @@ namespace __gnu_debug
_S_size(const std::__debug::list<_Tp, _Alloc>& __seq)
{
return __seq.empty()
- ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_equality);
+ ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_sign);
}
};
#endif
diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
index 581c51c9607..1750bc473d2 100644
--- a/libstdc++-v3/include/debug/safe_iterator.tcc
+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
@@ -113,18 +113,22 @@ namespace __gnu_debug
_Safe_iterator<_Iterator, _Sequence, _Category>::
_M_get_distance_to(const _Safe_iterator& __rhs) const
{
- typedef typename _Distance_traits<_Iterator>::__type _Diff;
+ typedef typename _Distance_traits<_Iterator>::__type _Dist;
typedef _Sequence_traits<_Sequence> _SeqTraits;
- if (this->base() == __rhs.base())
- return std::make_pair(0, __dp_exact);
+ _Dist __base_dist = __get_distance(this->base(), __rhs.base());
+ if (__base_dist.second == __dp_exact)
+ return __base_dist;
+ _Dist __seq_dist = _SeqTraits::_S_size(*this->_M_get_sequence());
if (this->_M_is_before_begin())
{
if (__rhs._M_is_begin())
return std::make_pair(1, __dp_exact);
- return std::make_pair(1, __dp_sign);
+ return __seq_dist.second == __dp_exact
+ ? std::make_pair(__seq_dist.first + 1, __dp_exact)
+ : __seq_dist;
}
if (this->_M_is_begin())
@@ -133,30 +137,42 @@ namespace __gnu_debug
return std::make_pair(-1, __dp_exact);
if (__rhs._M_is_end())
- return _SeqTraits::_S_size(*this->_M_get_sequence());
+ return __seq_dist;
- return std::make_pair(1, __dp_sign);
+ return std::make_pair(__seq_dist.first,
+ __seq_dist.second == __dp_exact
+ ? __dp_sign_max_size : __seq_dist.second);
}
if (this->_M_is_end())
{
if (__rhs._M_is_before_begin())
- return std::make_pair(-1, __dp_exact);
+ return __seq_dist.second == __dp_exact
+ ? std::make_pair(-__seq_dist.first - 1, __dp_exact)
+ : std::make_pair(-__seq_dist.first, __dp_sign);
if (__rhs._M_is_begin())
- {
- _Diff __diff = _SeqTraits::_S_size(*this->_M_get_sequence());
- return std::make_pair(-__diff.first, __diff.second);
- }
+ return std::make_pair(-__seq_dist.first, __seq_dist.second);
- return std::make_pair(-1, __dp_sign);
+ return std::make_pair(-__seq_dist.first,
+ __seq_dist.second == __dp_exact
+ ? __dp_sign_max_size : __seq_dist.second);
}
- if (__rhs._M_is_before_begin() || __rhs._M_is_begin())
- return std::make_pair(-1, __dp_sign);
+ if (__rhs._M_is_before_begin())
+ return __seq_dist.second == __dp_exact
+ ? std::make_pair(__seq_dist.first - 1, __dp_exact)
+ : std::make_pair(-__seq_dist.first, __dp_sign);
+
+ if (__rhs._M_is_begin())
+ return std::make_pair(-__seq_dist.first,
+ __seq_dist.second == __dp_exact
+ ? __dp_sign_max_size : __seq_dist.second);
if (__rhs._M_is_end())
- return std::make_pair(1, __dp_sign);
+ return std::make_pair(__seq_dist.first,
+ __seq_dist.second == __dp_exact
+ ? __dp_sign_max_size : __seq_dist.second);
return std::make_pair(1, __dp_equality);
}