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

[Jonathan Wakely <jwakely@redhat.com>]

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?


>+	    if (++__first == __last)
>+	      {
>+		// N is odd; in this final iteration, we perform a just one

s/perform a just one/perform just one/

>+		// comparison, for a total of 3*(N-1)/2 + 1 < 3*N/2 comparisons.

I find this a bit hard to parse with the inequality there.

>+		if (__comp_proj(__val1, __result.min))
>+		  __result.min = std::move(__val1);
>+		else if (!__comp_proj(__val1, __result.max))
>+		  __result.max = std::move(__val1);

This can be two comparisons, can't it? Would this be better...

   // N is odd; in this final iteration, we perform at most two
   // comparisons, for a total of 3*(N-1)/2 + 2 comparisons,
   // which is not more than 3*N/2, as required.

?

>+		break;
>+	      }
>+	    auto __val2 = *__first;
>+	    if (!__comp_proj(__val2, __val1))
>+	      {
>+		if (__comp_proj(__val1, __result.min))
>+		  __result.min = std::move(__val1);
>+		if (!__comp_proj(__val2, __result.max))
>+		  __result.max = std::move(__val2);
>+	      }
>+	    else
>+	      {
>+		if (__comp_proj(__val2, __result.min))
>+		  __result.min = std::move(__val2);
>+		if (!__comp_proj(__val1, __result.max))
>+		  __result.max = std::move(__val1);
>+	      }

I thought we might be able to simplify this to something like:

     auto __val2 = *__first;
     auto&& [__min, __max] = (*this)(__val1, __val2, __comp, __proj);
     if (__comp_proj(__min, __result.min))
       __result.min = __min;
     if (__comp_proj(__result.max, __max))
       __result.max = __max;

But it doesn't work because we need to move from __min and __max, but
the (*this)(...) returns minmax_result<const T&> and can't be moved
from.

We could get around that but it's not much of a simplification:

     range_value_t<Range> __val2 = *__first;
     auto [__min, __max] = (*this)(std::addressof(__val1),
                                   std::addressof(__val2),
                                   __comp,
                                   [](auto __p) -> const auto& {
                                     return *__p;
                                   });
     if (__comp_proj(*__min, __result.min))
       __result.min = std::move(*__min);
     if (__comp_proj(__result.max, *__max))
       __result.max = std::move(*__max);

> 	  }
> 	return __result;
>       }
>@@ -3408,21 +3429,40 @@ namespace ranges
>       operator()(_Iter __first, _Sent __last,
> 		 _Comp __comp = {}, _Proj __proj = {}) const
>       {
>-	if (__first == __last)
>-	  return {__first, __first};
>-
>+	auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
> 	minmax_element_result<_Iter> __result = {__first, __first};
>-	auto __i = __first;
>-	while (++__i != __last)
>+	if (__first == __last)
>+	  return __result;
>+	while (++__first != __last)
> 	  {
>-	    if (std::__invoke(__comp,
>-			      std::__invoke(__proj, *__i),
>-			      std::__invoke(__proj, *__result.min)))
>-	      __result.min = __i;
>-	    if (!(bool)std::__invoke(__comp,
>-				     std::__invoke(__proj, *__i),
>-				     std::__invoke(__proj, *__result.max)))
>-	      __result.max = __i;
>+	    // 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
>+	    // of this loop performs three comparisions).
>+	    auto __prev = __first;
>+	    if (++__first == __last)
>+	      {
>+		// N is odd; in this final iteration, we perform a just one
>+		// comparison, for a total of 3*(N-1)/2 + 1 < 3*N/2 comparisons.

Same comments on the comments as above.

>+		if (__comp_proj(*__prev, *__result.min))
>+		  __result.min = __prev;
>+		else if (!__comp_proj(*__prev, *__result.max))
>+		  __result.max = __prev;
>+		break;
>+	      }
>+	    if (!__comp_proj(*__first, *__prev))
>+	      {
>+		if (__comp_proj(*__prev, *__result.min))
>+		  __result.min = __prev;
>+		if (!__comp_proj(*__first, *__result.max))
>+		  __result.max = __first;
>+	      }
>+	    else
>+	      {
>+		if (__comp_proj(*__first, *__result.min))
>+		  __result.min = __first;
>+		if (!__comp_proj(*__prev, *__result.max))
>+		  __result.max = __prev;
>+	      }

We don't need to move anything here, so this could be written using
ranges::minmax. I'm not sure it is an improvement though (except for
being slightly fewer lines of code):

     auto __mm = minmax(__prev, __first, __comp,
                        [](auto&& __it) -> auto&& { return *__it; });

     if (__comp_proj(*__mm.min, *__result.min))
       __result.min = __mm.min;
     if (__comp_proj(*__result.max, *__mm.max))
       __result.max = __mm.max;