From patchwork Fri Oct 25 15:24:14 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Palka X-Patchwork-Id: 99589 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 6400A3858D33 for ; Fri, 25 Oct 2024 15:25:01 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTP id EADC03858D29 for ; Fri, 25 Oct 2024 15:24:25 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org EADC03858D29 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org EADC03858D29 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.129.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729869871; cv=none; b=lFc/9kz+SAEu6H5khypqnBYV4/A+5y/4elnr4lv0ONkKn/TJHtnpGev6CaYXyj7E3EItDDUgsoI7+WFQHKl46crmKq+UnoE/gn8KEwbHhjD8gWfpySb6wtePgz7qzm/bEqMYNqfcm//8J0ihm8csvZmcRFS5r/RnDSNCrZE+16U= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729869871; c=relaxed/simple; bh=E2OR2x3Y2veBuU1BFWptYyFHa8bSAh/fPKIlC4pUGXo=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=keITTiwgpxJKRIpaEDAAIDrsYB4Dmec2lUPDTkDon4cwix/ldr8Xi3wle7ZmM+y6qYBBoVF91o8FU9lgf6FLikV5jmxXuJL4nPFuNZP02feqRTLe3Un33rYVLc23EhngBSAtSX9dyVwIVqGznEN9tX9vxSQsr6nS96V3KCULvOk= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1729869865; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=gO5LGPRHozc/qy24H+9gWYn1/HCfZCBra2hJTlQ12PI=; b=B3gRa2haees/mpMLVwHYu0pjcaRWKzeogoEPihOoFJ6hTAbKepDQAdgfg+Ol/4Pk3hXHJZ Azrnex+vSPULdBvESjmHCqlmKSXmI5V9sWADvwcHODlKhLi7+r+RDylDlk8RQ+SMyzrFLt 5hoOfvU3gOZRd9ckEV/YYTmayEFAXYU= Received: from mail-qk1-f199.google.com (mail-qk1-f199.google.com [209.85.222.199]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-139-9U_5DJ4BMnud3gGqJ9U9ZA-1; Fri, 25 Oct 2024 11:24:22 -0400 X-MC-Unique: 9U_5DJ4BMnud3gGqJ9U9ZA-1 Received: by mail-qk1-f199.google.com with SMTP id af79cd13be357-7ab38ef4c52so19943485a.0 for ; Fri, 25 Oct 2024 08:24:22 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729869860; x=1730474660; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=gO5LGPRHozc/qy24H+9gWYn1/HCfZCBra2hJTlQ12PI=; b=nNabLly/P6YWETo3yNAmgcivQVMVzxHIopS44/MXQUygCxuhlILiV0zOq1E8u6qkW7 6VxjwxGfOlf7kzd3lXDQ4gxK7GKYMdNaUX0Ly7QMU7vwYXBtJeD+Ttbbf60z7Xr6A7d4 +gBVCTkk/IANOWR0tjy35Ut/h13kStlWKPS7Uu/VBBKZ8nFS0hsTXwVlNH+ZEvxB9cyg iqleB8JqNFrQ3syo5bziu8MwLmRTyR2ORRpv56Fzl+wahTTqpUe0kSM86BAT/pur57lQ r/i6J4XID5h/p3IB3Kb/TmZPovYYa7IieZARLNOm2roElsNDqM2nounlCToCA+B678sZ W0oQ== X-Gm-Message-State: AOJu0YygaAmWOHke8glQguPQaPMVFmHsQv6JH7B6/d5TqMIpCej2kRDG 0A481ygy8C4r8m/NeJS3lylS3VE3OfJ7DPXhBkMltOH3E8UYOYjwPQ6fM2nHG7YkKMFcvzIhSt2 CDCjrRDEsKG2vKKsYqJ5NiytgMvNhRuZXlRiCIihec+sP7ucR/BFmCb4C9sJu02CjdfbdiUzXD3 YlyptpJ0la1QClAjK6Cu0UqXdl+cWx9HlYcNrC X-Received: by 2002:a05:620a:29d3:b0:7a9:bd93:ac0e with SMTP id af79cd13be357-7b18eaa65fdmr109283385a.8.1729869860581; Fri, 25 Oct 2024 08:24:20 -0700 (PDT) X-Google-Smtp-Source: AGHT+IH4CJlHiNdWBeoSuC2ICEcNL52KluSxy4m4qYFEWQUxh/YZuuTsN7b3NH4Esdyx/naeS+ss+Q== X-Received: by 2002:a05:620a:29d3:b0:7a9:bd93:ac0e with SMTP id af79cd13be357-7b18eaa65fdmr109281985a.8.1729869860121; Fri, 25 Oct 2024 08:24:20 -0700 (PDT) Received: from localhost.localdomain (ool-18bb2a2e.dyn.optonline.net. [24.187.42.46]) by smtp.gmail.com with ESMTPSA id af79cd13be357-7b18d294a2csm62888885a.46.2024.10.25.08.24.19 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 25 Oct 2024 08:24:19 -0700 (PDT) From: Patrick Palka To: gcc-patches@gcc.gnu.org Cc: libstdc++@gcc.gnu.org, Patrick Palka Subject: [PATCH] libstdc++: Fix complexity of drop_view::begin const [PR112641] Date: Fri, 25 Oct 2024 11:24:14 -0400 Message-ID: <20241025152414.1780304-1-ppalka@redhat.com> X-Mailer: git-send-email 2.47.0.118.gfd3785337b MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-14.5 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_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~patchwork=sourceware.org@gcc.gnu.org Tested on x86_64-pc-linux-gnu, does this look OK for trunk/backports? Also available in PR form at https://forge.sourceware.org/gcc/gcc-TEST/pulls/8 -- >8 -- Views are required to have a amortized O(1) begin(), but our drop_view's const begin overload is O(n) for non-common ranges. This patch reimplements it so that it's O(1) even in that case. See also LWG 4009. PR libstdc++/112641 libstdc++-v3/ChangeLog: * include/std/ranges (drop_view::begin const): Reimplement so that it's O(1) instead of O(n) even in the non-common range case. * testsuite/std/ranges/adaptors/drop.cc (test10): New test. --- libstdc++-v3/include/std/ranges | 4 ++-- libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc | 12 ++++++++++++ 2 files changed, 14 insertions(+), 2 deletions(-) diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index cebe10683f9..743429dbcea 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -2664,8 +2664,8 @@ namespace views::__adaptor begin() const requires random_access_range && sized_range { - return ranges::next(ranges::begin(_M_base), _M_count, - ranges::end(_M_base)); + return ranges::begin(_M_base) + ranges::min(ranges::distance(_M_base), + _M_count); } constexpr auto diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc index c9987c61e3c..0bd5bebb785 100644 --- a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc @@ -274,6 +274,17 @@ test09() static_assert(!requires { views::all | drop; }); } +constexpr bool +test10() +{ + // PR libstdc++/112641 - drop_view::begin const may have O(n) complexity + const auto s = ranges::subrange(views::iota(size_t(1)), size_t(-1)); + const auto r = ranges::drop_view(s, s.size() - 1); + const auto b = r.begin(); // time out + VERIFY( *b == size_t(-1) ); + return true; +} + int main() { @@ -286,4 +297,5 @@ main() test07(); test08(); test09(); + static_assert(test10()); }