This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] PR67085 move comparison functions in heap operations
On 19/01/17 20:24 +0000, Jonathan Wakely wrote:
On 19/01/17 18:50 +0000, Jonathan Wakely wrote:
On 19/01/17 18:28 +0000, Jonathan Wakely wrote:
@@ -397,7 +401,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
while (__last - __first > 1)
{
--__last;
- std::__pop_heap(__first, __last, __last, __comp);
+ std::__pop_heap(__first, __last, __last, _GLIBCXX_MOVE(__comp));
Oops, we can't move from the functor in a loop, it might be invalid
after the first move. Fix coming asap.
Unfortunately this adds some more copies to my testcase. I have
another idea how to avoid that though.
This also adds an extra (safe) move in __is_heap.
I hope this is the last change needed for this bug. This avoids the
__iter_xxx_iter() generator functions and constructs the function
objects directly as local variables (to avoid copies in the arguments
and return values of the generators), and then passes them as lvalues
to the internal heap algos (to avoid copies in the algo argument
lists).
We can probably do more in <bits/predefined_ops.h> to avoid passing
things by value, at least for C++11 and later. We can probably also
avoid the generator functions in stl_algo.h and stl_algobase.h but I'm
not going to try to do that now.
I also tried passing the heap algos' _Tp arguments by reference, as
suggested by PR 51965, but that caused some regressions. I'll revisit
that another time.
Tested powerpc64le-linux, committed to trunk.
commit 6a5a08c54f2f62ac5dad94979df03686de6ad290
Author: Jonathan Wakely <jwakely@redhat.com>
Date: Thu Jan 19 21:09:36 2017 +0000
PR67085 pass comparison functions by reference in heap algorithms
PR libstdc++/67085
* include/bits/predefined_ops.h (_Iter_less_val, _Val_less_iter): Add
converting constructors from _Iter_less_iter.
(_Iter_comp_val, _Val_comp_iter): Add converting constructors from
_Iter_comp_iter.
(__iter_comp_val(_Iter_comp_iter<C>): Use converting constructor.
(__val_comp_iter(_Iter_comp_iter<C>): Likewise.
* include/bits/stl_heap.h (__is_heap_until, __push_heap, __pop_heap)
(__make_heap, __sort_heap): Change _Compare parameters to references.
(__is_heap, push_heap, __adjust_heap, __pop_heap, pop_heap)
(__make_heap, make_heap, sort_heap, is_heap_until): Pass comparison
functions as lvalues.
(is_heap): Call __is_heap_until directly to avoid copying __comp.
* testsuite/23_containers/priority_queue/67085.cc: Adjust test to
count copies during construction with empty sequence.
diff --git a/libstdc++-v3/include/bits/predefined_ops.h b/libstdc++-v3/include/bits/predefined_ops.h
index 2742984..a5a7694 100644
--- a/libstdc++-v3/include/bits/predefined_ops.h
+++ b/libstdc++-v3/include/bits/predefined_ops.h
@@ -50,6 +50,15 @@ namespace __ops
struct _Iter_less_val
{
+#if __cplusplus >= 201103L
+ constexpr _Iter_less_val() = default;
+#else
+ _Iter_less_val() { }
+#endif
+
+ explicit
+ _Iter_less_val(_Iter_less_iter) { }
+
template<typename _Iterator, typename _Value>
bool
operator()(_Iterator __it, _Value& __val) const
@@ -66,6 +75,15 @@ namespace __ops
struct _Val_less_iter
{
+#if __cplusplus >= 201103L
+ constexpr _Val_less_iter() = default;
+#else
+ _Val_less_iter() { }
+#endif
+
+ explicit
+ _Val_less_iter(_Iter_less_iter) { }
+
template<typename _Value, typename _Iterator>
bool
operator()(_Value& __val, _Iterator __it) const
@@ -141,6 +159,18 @@ namespace __ops
: _M_comp(_GLIBCXX_MOVE(__comp))
{ }
+ explicit
+ _Iter_comp_val(const _Iter_comp_iter<_Compare>& __comp)
+ : _M_comp(__comp._M_comp)
+ { }
+
+#if __cplusplus >= 201103L
+ explicit
+ _Iter_comp_val(_Iter_comp_iter<_Compare>&& __comp)
+ : _M_comp(std::move(__comp._M_comp))
+ { }
+#endif
+
template<typename _Iterator, typename _Value>
bool
operator()(_Iterator __it, _Value& __val)
@@ -155,7 +185,7 @@ namespace __ops
template<typename _Compare>
inline _Iter_comp_val<_Compare>
__iter_comp_val(_Iter_comp_iter<_Compare> __comp)
- { return _Iter_comp_val<_Compare>(_GLIBCXX_MOVE(__comp._M_comp)); }
+ { return _Iter_comp_val<_Compare>(_GLIBCXX_MOVE(__comp)); }
template<typename _Compare>
struct _Val_comp_iter
@@ -167,6 +197,18 @@ namespace __ops
: _M_comp(_GLIBCXX_MOVE(__comp))
{ }
+ explicit
+ _Val_comp_iter(const _Iter_comp_iter<_Compare>& __comp)
+ : _M_comp(__comp._M_comp)
+ { }
+
+#if __cplusplus >= 201103L
+ explicit
+ _Val_comp_iter(_Iter_comp_iter<_Compare>&& __comp)
+ : _M_comp(std::move(__comp._M_comp))
+ { }
+#endif
+
template<typename _Value, typename _Iterator>
bool
operator()(_Value& __val, _Iterator __it)
@@ -181,7 +223,7 @@ namespace __ops
template<typename _Compare>
inline _Val_comp_iter<_Compare>
__val_comp_iter(_Iter_comp_iter<_Compare> __comp)
- { return _Val_comp_iter<_Compare>(_GLIBCXX_MOVE(__comp._M_comp)); }
+ { return _Val_comp_iter<_Compare>(_GLIBCXX_MOVE(__comp)); }
template<typename _Value>
struct _Iter_equals_val
diff --git a/libstdc++-v3/include/bits/stl_heap.h b/libstdc++-v3/include/bits/stl_heap.h
index b19c9f4..3c102f1 100644
--- a/libstdc++-v3/include/bits/stl_heap.h
+++ b/libstdc++-v3/include/bits/stl_heap.h
@@ -72,7 +72,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _Compare>
_Distance
__is_heap_until(_RandomAccessIterator __first, _Distance __n,
- _Compare __comp)
+ _Compare& __comp)
{
_Distance __parent = 0;
for (_Distance __child = 1; __child < __n; ++__child)
@@ -91,8 +91,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
inline bool
__is_heap(_RandomAccessIterator __first, _Distance __n)
{
- return std::__is_heap_until(__first, __n,
- __gnu_cxx::__ops::__iter_less_iter()) == __n;
+ __gnu_cxx::__ops::_Iter_less_iter __comp;
+ return std::__is_heap_until(__first, __n, __comp) == __n;
}
template<typename _RandomAccessIterator, typename _Compare,
@@ -100,8 +100,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
inline bool
__is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
{
- return std::__is_heap_until(__first, __n,
- __gnu_cxx::__ops::__iter_comp_iter(__comp)) == __n;
+ __gnu_cxx::__ops::_Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
+ return std::__is_heap_until(__first, __n, __cmp) == __n;
}
template<typename _RandomAccessIterator>
@@ -126,7 +126,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
void
__push_heap(_RandomAccessIterator __first,
_Distance __holeIndex, _Distance __topIndex, _Tp __value,
- _Compare __comp)
+ _Compare& __comp)
{
_Distance __parent = (__holeIndex - 1) / 2;
while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
@@ -165,10 +165,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_irreflexive(__first, __last);
__glibcxx_requires_heap(__first, __last - 1);
+ __gnu_cxx::__ops::_Iter_less_val __comp;
_ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
std::__push_heap(__first, _DistanceType((__last - __first) - 1),
- _DistanceType(0), _GLIBCXX_MOVE(__value),
- __gnu_cxx::__ops::__iter_less_val());
+ _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
}
/**
@@ -200,11 +200,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
__glibcxx_requires_heap_pred(__first, __last - 1, __comp);
+ __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
+ __cmp(_GLIBCXX_MOVE(__comp));
_ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
std::__push_heap(__first, _DistanceType((__last - __first) - 1),
- _DistanceType(0), _GLIBCXX_MOVE(__value),
- __gnu_cxx::__ops::
- __iter_comp_val(_GLIBCXX_MOVE(__comp)));
+ _DistanceType(0), _GLIBCXX_MOVE(__value), __cmp);
}
template<typename _RandomAccessIterator, typename _Distance,
@@ -231,16 +231,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
+ (__secondChild - 1)));
__holeIndex = __secondChild - 1;
}
- std::__push_heap(__first, __holeIndex, __topIndex,
- _GLIBCXX_MOVE(__value),
- __gnu_cxx::__ops::
- __iter_comp_val(_GLIBCXX_MOVE(__comp)));
+ __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
+ __cmp(_GLIBCXX_MOVE(__comp));
+ std::__push_heap(__first, __holeIndex, __topIndex,
+ _GLIBCXX_MOVE(__value), __cmp);
}
template<typename _RandomAccessIterator, typename _Compare>
inline void
__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
- _RandomAccessIterator __result, _Compare __comp)
+ _RandomAccessIterator __result, _Compare& __comp)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
@@ -251,7 +251,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
*__result = _GLIBCXX_MOVE(*__first);
std::__adjust_heap(__first, _DistanceType(0),
_DistanceType(__last - __first),
- _GLIBCXX_MOVE(__value), _GLIBCXX_MOVE(__comp));
+ _GLIBCXX_MOVE(__value), __comp);
}
/**
@@ -282,8 +282,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__last - __first > 1)
{
--__last;
- std::__pop_heap(__first, __last, __last,
- __gnu_cxx::__ops::__iter_less_iter());
+ __gnu_cxx::__ops::_Iter_less_iter __comp;
+ std::__pop_heap(__first, __last, __last, __comp);
}
}
@@ -313,17 +313,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__last - __first > 1)
{
+ using __gnu_cxx::__ops::_Iter_comp_iter;
+ _Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
--__last;
- std::__pop_heap(__first, __last, __last,
- __gnu_cxx::__ops::
- __iter_comp_iter(_GLIBCXX_MOVE(__comp)));
+ std::__pop_heap(__first, __last, __last, __cmp);
}
}
template<typename _RandomAccessIterator, typename _Compare>
void
__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
- _Compare __comp)
+ _Compare& __comp)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
@@ -366,8 +366,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_irreflexive(__first, __last);
- std::__make_heap(__first, __last,
- __gnu_cxx::__ops::__iter_less_iter());
+ __gnu_cxx::__ops::_Iter_less_iter __comp;
+ std::__make_heap(__first, __last, __comp);
}
/**
@@ -391,15 +391,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
- std::__make_heap(__first, __last,
- __gnu_cxx::__ops::
- __iter_comp_iter(_GLIBCXX_MOVE(__comp)));
+ __gnu_cxx::__ops::_Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
+ std::__make_heap(__first, __last, __cmp);
}
template<typename _RandomAccessIterator, typename _Compare>
void
__sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
- _Compare __comp)
+ _Compare& __comp)
{
while (__last - __first > 1)
{
@@ -429,8 +428,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_irreflexive(__first, __last);
__glibcxx_requires_heap(__first, __last);
- std::__sort_heap(__first, __last,
- __gnu_cxx::__ops::__iter_less_iter());
+ __gnu_cxx::__ops::_Iter_less_iter __comp;
+ std::__sort_heap(__first, __last, __comp);
}
/**
@@ -455,9 +454,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
__glibcxx_requires_heap_pred(__first, __last, __comp);
- std::__sort_heap(__first, __last,
- __gnu_cxx::__ops::
- __iter_comp_iter(_GLIBCXX_MOVE(__comp)));
+ __gnu_cxx::__ops::_Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
+ std::__sort_heap(__first, __last, __cmp);
}
#if __cplusplus >= 201103L
@@ -483,9 +481,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_irreflexive(__first, __last);
+ __gnu_cxx::__ops::_Iter_less_iter __comp;
return __first +
- std::__is_heap_until(__first, std::distance(__first, __last),
- __gnu_cxx::__ops::__iter_less_iter());
+ std::__is_heap_until(__first, std::distance(__first, __last), __comp);
}
/**
@@ -510,10 +508,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
+ __gnu_cxx::__ops::_Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
return __first
- + std::__is_heap_until(__first, std::distance(__first, __last),
- __gnu_cxx::__ops::
- __iter_comp_iter(std::move(__comp)));
+ + std::__is_heap_until(__first, std::distance(__first, __last), __cmp);
}
/**
@@ -541,8 +538,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
- return std::is_heap_until(__first, __last, std::move(__comp))
- == __last;
+ // concept requirements
+ __glibcxx_function_requires(_RandomAccessIteratorConcept<
+ _RandomAccessIterator>)
+ __glibcxx_requires_valid_range(__first, __last);
+ __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
+
+ const auto __dist = std::distance(__first, __last);
+ __gnu_cxx::__ops::_Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
+ return std::__is_heap_until(__first, __dist, __cmp) == __dist;
}
#endif
diff --git a/libstdc++-v3/testsuite/23_containers/priority_queue/67085.cc b/libstdc++-v3/testsuite/23_containers/priority_queue/67085.cc
index 4ccea30..9f4da58 100644
--- a/libstdc++-v3/testsuite/23_containers/priority_queue/67085.cc
+++ b/libstdc++-v3/testsuite/23_containers/priority_queue/67085.cc
@@ -32,11 +32,11 @@ struct CopyCounter : std::less<int>
void
test01()
{
- int v[] = {1, 2, 3, 4};
- std::priority_queue<int, std::vector<int>, CopyCounter> q{v, v+4};
- VERIFY(count == 4);
+ int i;
+ std::priority_queue<int, std::vector<int>, CopyCounter> q{&i, &i};
+ VERIFY(count == 2);
q.push(1);
- VERIFY(count == 5);
+ VERIFY(count == 3);
}
int