[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