From patchwork Fri Sep 12 17:36:52 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Palka X-Patchwork-Id: 120167 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 4D12E3857C67 for ; Fri, 12 Sep 2025 17:38:00 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 4D12E3857C67 Authentication-Results: sourceware.org; dkim=pass (1024-bit key, unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=JwA79pci 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 6F4713857C5F for ; Fri, 12 Sep 2025 17:36:57 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 6F4713857C5F Authentication-Results: sourceware.org; dmarc=pass (p=quarantine 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 6F4713857C5F 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=1757698617; cv=none; b=PI7tLwqXPhalvRNo7v3GnRRZKP/EdYAJzt4kaZLU4JC8HeacsHL/IFIDosQglCzzxLUDKT9TN6eB5NWIP+Cu6ZNHu8sdq9JVd57gPgu1Nyeb+G+yZ95YaUEXepey4StPIU3mlIRXfHFi3DLxCSRHJpmnrDMadBiE5AxJK8B/KBM= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1757698617; c=relaxed/simple; bh=fOoksJeFU9dYlLra91BnQKecDv1QVmbV2Xgvcc2schM=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=kw1XUF0eMguuGbfKtdMQjo30XaBj2Ct4avWmrWhgH5aUd24qP1Rsjg+vcWrUWhm096FXABU+oqwbR3K/ai/88AaEMgdv/OJC5rUaLl5B3fc3OCvaXu8wvwfDCdNKnlZFb1obEU9CBCuoueNPW7uGnsmtk7JOTC+wsgTKbuv9b/A= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 6F4713857C5F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1757698617; 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=nvUcTptsItSACKYk2J3ZupSJa5IBDvGQbW50NEITu9A=; b=JwA79pcirv1u7FJpkRDId9Z3ou1p+Tukv+TGOqdZQTvi1fpnrZqLih/e99qyBWdbnHaxmx MJv9toO2H+qCazt1mYxLMha6zdmsCgkx0jE+FNqHHg0hpeBmd0ZASRYoG+JY5UHut188eu jgKBwD1VvdENVPZvSTZsZ/JsJsHHQEo= Received: from mail-qk1-f198.google.com (mail-qk1-f198.google.com [209.85.222.198]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-151-gIumB-INO7y_MjzRdowCVg-1; Fri, 12 Sep 2025 13:36:56 -0400 X-MC-Unique: gIumB-INO7y_MjzRdowCVg-1 X-Mimecast-MFC-AGG-ID: gIumB-INO7y_MjzRdowCVg_1757698615 Received: by mail-qk1-f198.google.com with SMTP id af79cd13be357-820357763f6so75746685a.2 for ; Fri, 12 Sep 2025 10:36:56 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1757698615; x=1758303415; 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=nvUcTptsItSACKYk2J3ZupSJa5IBDvGQbW50NEITu9A=; b=ATCvWDE+gY1G1nTz01wK4f5YCKau2r4ZIDS5+R7PylTYwC9TEXoWuzHpwrpm89hnyp wleN6sSgMQ+Zyt6FuuxQzwDklc/ri7nPriePxpZoTG/mXSlCFmmQlnQ8HNyWmXkqp0o7 +thLbCAv0JkJX48fDegv06WSQucaMXHCYAPA2zcQUAcJTCNYxCTvYeoL3wfp3bC5Rctb QdXXvRcameAECgrWMrjz/nOjXUch/3F26S9tkGg+iJ7Be7KNIhws6G0uEM6u9BToHxc3 k45ZA1lALqQ8LljcLyG3YSU4uZDY2brzJ+f4/SSfI1+ThCm2sPCuglLi1EvsTBD8n8RL QCYw== X-Gm-Message-State: AOJu0Yy6RjilCb+/CaJ19fXNmnSaKJIBJXSMVsL6QhhJlZ9QimG86EQW l41m2QghyRIUavFo9q6pTtiU2q9NyQmqxZe0O34DhjaOq3XZbH0VGURX+B5XWYjNmwCE66vDKJQ CHkfOZ6fLVEriiLwTBrzaVxVqLLb2hNS4LqxM7kigoX9fBpIXPyJTb0Qk71JHt4R11yCpIkIwp3 8AzKvuh3S9q/pTIKCaj35lAY5m4vprZ1pLQ498tzrH X-Gm-Gg: ASbGncu1sY4DZLg0g1GJbuekqU+je7aw0sOeF1m+ry8jy8mIRdh6RXB7LIYXbLp8KqM +G3eZE3rQOVPTWj3ioPYuIyCul4ThEyMJZ3xaNsDsqkyDbhC6dxEeBlPYyQrhoksuwkabclRUt7 hQnPhsC6SkEe07TuZvvv+6wkooNwN/RlXbhSFZR3hxVH6DkM6ciRedKlEiYu3ILf5h1o+xpYW5/ xwX5YBeR64wJ5vysI5f3DuRff1PsDTisviY0n8NBAS+v8TiOLjsUZOxmLUk1jcoO57A8+Et7gKa CJdIm5pjweuE/ihPdQv5tMw2/lLYng== X-Received: by 2002:a05:620a:4001:b0:811:cf4:a1fb with SMTP id af79cd13be357-823fe385b17mr347061485a.7.1757698614814; Fri, 12 Sep 2025 10:36:54 -0700 (PDT) X-Google-Smtp-Source: AGHT+IG+UivEg/3yqObx/zNN5TmtC1m0all6G1WZDD63v01NdxoAXRuFVsT4Moc8KU4EGDLTGRjuTA== X-Received: by 2002:a05:620a:4001:b0:811:cf4:a1fb with SMTP id af79cd13be357-823fe385b17mr347057185a.7.1757698614124; Fri, 12 Sep 2025 10:36:54 -0700 (PDT) Received: from idea ([2600:4040:aa68:6000:9e8e:99ff:fed1:71f]) by smtp.gmail.com with ESMTPSA id af79cd13be357-820c974dbbbsm302406185a.21.2025.09.12.10.36.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 12 Sep 2025 10:36:53 -0700 (PDT) From: Patrick Palka To: gcc-patches@gcc.gnu.org Cc: libstdc++@gcc.gnu.org, Patrick Palka Subject: [PATCH] libstdc++: Fix ranges::shuffle for non-sized range [PR121917] Date: Fri, 12 Sep 2025 13:36:52 -0400 Message-ID: <20250912173652.3807567-1-ppalka@redhat.com> X-Mailer: git-send-email 2.51.0.193.g4975ec3473 MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-MFC-PROC-ID: JHOo3MRvea5mKaAlL2geRigDQVjVjP6zKaWNW-EWCr0_1757698615 X-Mimecast-Originator: redhat.com content-type: text/plain; charset="US-ASCII"; x-default=true X-Spam-Status: No, score=-14.8 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_HOSTKARMA_W, RCVD_IN_MSPIKE_H5, RCVD_IN_MSPIKE_WL, RCVD_IN_VALIDITY_RPBL_BLOCKED, RCVD_IN_VALIDITY_SAFE_BLOCKED, SPF_HELO_PASS, SPF_NONE, TXREP autolearn=ham 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? Patch generated with -w due to otherwise noisy whitespace changes. -- >8 -- The ranges::shuffle optimization, copied from std::shuffle, has a two-at-a-time PRNG optimization that considers the range of the PRNG vs the size of the range. But in C++20 a sentinel is not necessarily sized so we can't unconditionally do __last - __first. We could instead use ranges::size, but that'd take linear time for a non-sized sentinel which makes the optimization less clear of a win. So this patch instead makes us only consider this optimization for arguments that model sized_sentinel_for or sized_range. PR libstdc++/121917 libstdc++-v3/ChangeLog: * include/bits/ranges_algo.h (__shuffle_fn::_S_impl): Factor out from main operator() overload. Add optional size parameter, and only consider the two-at-a-time PRNG optimization if the size is given. (__shuffle_fn::operator()): Adjust to call _S_impl directly, computing the range size for sized_sentinel_for or sized_range arguments. * testsuite/25_algorithms/shuffle/constrained.cc: --- libstdc++-v3/include/bits/ranges_algo.h | 35 ++++++++++++++----- .../25_algorithms/shuffle/constrained.cc | 18 ++++++++++ 2 files changed, 44 insertions(+), 9 deletions(-) diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index 6e1e06cb2d0f..855ab1395149 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -1945,12 +1945,10 @@ namespace ranges struct __shuffle_fn { - template _Sent, - typename _Gen> - requires permutable<_Iter> - && uniform_random_bit_generator> - _Iter - operator()(_Iter __first, _Sent __last, _Gen&& __g) const + template + static _Iter + _S_impl(_Iter __first, _Sent __last, _Gen&& __g, + iter_difference_t<_Iter> __n) { // FIXME: Correctly handle integer-class difference types. if (__first == __last) @@ -1964,8 +1962,10 @@ namespace ranges using __uc_type = common_type_t::result_type, __ud_type>; + if (__n != -1) + { const __uc_type __urngrange = __g.max() - __g.min(); - const __uc_type __urange = __uc_type(__last - __first); + const __uc_type __urange = __uc_type(__n); if (__urngrange / __urange >= __urange) // I.e. (__urngrange >= __urange * __urange) but without wrap issues. @@ -1999,6 +1999,7 @@ namespace ranges return __i; } + } __distr_type __d; @@ -2009,14 +2010,30 @@ namespace ranges return __i; } + template _Sent, + typename _Gen> + requires permutable<_Iter> + && uniform_random_bit_generator> + _Iter + operator()(_Iter __first, _Sent __last, _Gen&& __g) const + { + iter_difference_t<_Iter> __n = -1; + if constexpr (sized_sentinel_for<_Sent, _Iter>) + __n = __last - __first; + return _S_impl(__first, __last, std::forward<_Gen>(__g), __n); + } + template requires permutable> && uniform_random_bit_generator> borrowed_iterator_t<_Range> operator()(_Range&& __r, _Gen&& __g) const { - return (*this)(ranges::begin(__r), ranges::end(__r), - std::forward<_Gen>(__g)); + range_difference_t<_Range> __n = -1; + if constexpr (sized_range<_Range>) + __n = ranges::size(__r); + return _S_impl(ranges::begin(__r), ranges::end(__r), + std::forward<_Gen>(__g), __n); } }; diff --git a/libstdc++-v3/testsuite/25_algorithms/shuffle/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/shuffle/constrained.cc index 70c6bdfc3d9e..4d633561508b 100644 --- a/libstdc++-v3/testsuite/25_algorithms/shuffle/constrained.cc +++ b/libstdc++-v3/testsuite/25_algorithms/shuffle/constrained.cc @@ -86,9 +86,27 @@ test02() ranges::shuffle(w, g); } +struct non_default_sentinel_t { }; + +template +bool operator==(const I& i, non_default_sentinel_t) +{ return i == std::default_sentinel; } + +void +test03() +{ + // PR libstdc++/121917 - ranges::shuffle incorrectly requires its arguments + // to model sized_sentinel_for + int a[2]{}; + std::counted_iterator iter(a, 2); + std::default_random_engine e; + std::ranges::shuffle(iter, non_default_sentinel_t{}, e); +} + int main() { test01(); test02(); + test03(); }