[PATCH] libstdc++: Reduce ranges::minmax/minmax_element comparison complexity

Jonathan Wakely jwakely@redhat.com
Wed May 5 09:46:38 GMT 2021


On 05/05/21 10:39 +0100, Jonathan Wakely wrote:
>On 04/05/21 21:42 -0400, Patrick Palka via Libstdc++ wrote:
>>This rewrites ranges::minmax and ranges::minmax_element so that it
>>performs at most 3*N/2 many comparisons, as required by the standard.
>>In passing, this also fixes PR100387 by avoiding a premature std::move
>>in ranges::minmax and in std::shift_right.
>>
>>Tested on x86_64-pc-linux-gnu, does this look OK for trunk and perhaps
>>10/11?
>>
>>libstdc++-v3/ChangeLog:
>>
>>	PR libstdc++/100387
>>	* include/bits/ranges_algo.h (__minmax_fn::operator()): Rewrite
>>	to limit comparison complexity to 3*N/2.  Avoid premature std::move.
>>	(__minmax_element_fn::operator()): Likewise.
>>	(shift_right): Avoid premature std::move of __result.
>>	* testsuite/25_algorithms/minmax/constrained.cc (test04, test05):
>>	New tests.
>>	* testsuite/25_algorithms/minmax_element/constrained.cc (test02):
>>	Likewise.
>>---
>>libstdc++-v3/include/bits/ranges_algo.h       | 87 ++++++++++++++-----
>>.../25_algorithms/minmax/constrained.cc       | 31 +++++++
>>.../minmax_element/constrained.cc             | 19 ++++
>>3 files changed, 113 insertions(+), 24 deletions(-)
>>
>>diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
>>index cda3042c11f..bbd29127e89 100644
>>--- a/libstdc++-v3/include/bits/ranges_algo.h
>>+++ b/libstdc++-v3/include/bits/ranges_algo.h
>>@@ -3291,18 +3291,39 @@ namespace ranges
>>	auto __first = ranges::begin(__r);
>>	auto __last = ranges::end(__r);
>>	__glibcxx_assert(__first != __last);
>>+	auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
>>	minmax_result<range_value_t<_Range>> __result = {*__first, *__first};
>>	while (++__first != __last)
>>	  {
>>-	    auto __tmp = *__first;
>>-	    if (std::__invoke(__comp,
>>-			      std::__invoke(__proj, __tmp),
>>-			      std::__invoke(__proj, __result.min)))
>>-	      __result.min = std::move(__tmp);
>>-	    if (!(bool)std::__invoke(__comp,
>>-				     std::__invoke(__proj, __tmp),
>>-				     std::__invoke(__proj, __result.max)))
>>-	      __result.max = std::move(__tmp);
>>+	    // Process two elements at a time so that we perform at most
>>+	    // 3*N/2 many comparisons in total (each of the N/2 iterations
>
>Is "many" a typo here?
>
>>+	    // of this loop performs three comparisions).
>>+	    auto __val1 = *__first;
>
>Can we avoid making this copy if the range satisfies forward_range, by
>keeping copies of the min/max iterators, or just forwarding to
>ranges::minmax_element?

Hmm, on the other hand, for a forward range of ints we're probably
better off jsut making the copy here and not going through the
indirections done by minmax_element.

Maybe something like:

   if constexpr (forward_range<_Range> && is_scalar_v<range_value_t<_Range>>)




More information about the Libstdc++ mailing list