From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [216.205.24.124]) by sourceware.org (Postfix) with ESMTP id 748523988885 for ; Wed, 5 May 2021 09:46:44 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 748523988885 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-401-R1mTOZlqPuSrOyekq5CpYg-1; Wed, 05 May 2021 05:46:42 -0400 X-MC-Unique: R1mTOZlqPuSrOyekq5CpYg-1 Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.phx2.redhat.com [10.5.11.16]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 7CB3B1006C81; Wed, 5 May 2021 09:46:41 +0000 (UTC) Received: from localhost (unknown [10.33.36.164]) by smtp.corp.redhat.com (Postfix) with ESMTP id F09035C582; Wed, 5 May 2021 09:46:39 +0000 (UTC) Date: Wed, 5 May 2021 10:46:38 +0100 From: Jonathan Wakely To: Patrick Palka Cc: gcc-patches@gcc.gnu.org, libstdc++@gcc.gnu.org Subject: Re: [PATCH] libstdc++: Reduce ranges::minmax/minmax_element comparison complexity Message-ID: <20210505094638.GS3008@redhat.com> References: <20210505014220.1216746-1-ppalka@redhat.com> <20210505093931.GP3008@redhat.com> MIME-Version: 1.0 In-Reply-To: <20210505093931.GP3008@redhat.com> X-Clacks-Overhead: GNU Terry Pratchett X-Scanned-By: MIMEDefang 2.79 on 10.5.11.16 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=us-ascii; format=flowed Content-Disposition: inline X-Spam-Status: No, score=-14.3 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 05 May 2021 09:46:45 -0000 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> __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>)