On Fri, 12 Sep 2025, Patrick Palka wrote:
> On Fri, 12 Sep 2025, Jonathan Wakely wrote:
>
> > On Fri, 12 Sept 2025 at 18:39, Patrick Palka <[email protected]> wrote:
> > >
> > > 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<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
> > > - typename _Gen>
> > > - requires permutable<_Iter>
> > > - && uniform_random_bit_generator<remove_reference_t<_Gen>>
> > > - _Iter
> > > - operator()(_Iter __first, _Sent __last, _Gen&& __g) const
> > > + template<typename _Iter, typename _Sent, typename _Gen>
> > > + static _Iter
> > > + _S_impl(_Iter __first, _Sent __last, _Gen&& __g,
> > > + iter_difference_t<_Iter> __n)
> >
> > This _S_impl should be private, however ...
> >
> > > {
> > > // FIXME: Correctly handle integer-class difference types.
> > > if (__first == __last)
> > > @@ -1964,8 +1962,10 @@ namespace ranges
> > > using __uc_type
> > > = common_type_t<typename remove_reference_t<_Gen>::result_type,
> > > __ud_type>;
> > >
> > > + if (__n != -1)
> >
> > Having this as a runtime check for != 1 seems a little inelegant when
> > we've already determined statically whether we want to consider the
> > optimization.
> >
> > We could leave the main implementation in the operator()(Iter, Sent,
> > Gen&&) overload and just add:
> >
> > if constexpr (sized_sentinel_for<Sent, Iter>)
> >
> > here instead of 'if ( n != 1)'
> >
> > Then in the operator()(R&&, Gen&&) overload do:
> >
> > if constexpr (sized_range<_Range>)
> > {
> > auto __first = ranges::begin(__r);
> > return (*this)(__first, __first + ranges::size(__r),
> > std::forward<_Gen>(__g));
> > }
> > else
> > return (*this)(ranges::begin(__r), ranges::end(__r),
> > std::forward<_Gen>(__g));
> >
> > This way we don't need to pass n to _S_impl, we just ensure that we
> > pass a sized sentinel instead, and that enables the optimization.
>
> Sounds good, like so?
>
> -- >8 --
>
> Subject: [PATCH] libstdc++: Fix ranges::shuffle for non-sized range [PR121917]
>
> 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
> sized ranges.
>
> PR libstdc++/121917
>
> libstdc++-v3/ChangeLog:
>
> * include/bits/ranges_algo.h (__shuffle_fn::operator()): Only
> consider the two-at-a-time PRNG optimization if the range is
> sized.
> * testsuite/25_algorithms/shuffle/constrained.cc (test03): New
> test.
Whoops, forgot to --amend the commit. This is the correct diff:
-- >8 --
Subject: [PATCH] libstdc++: Fix ranges::shuffle for non-sized range [PR121917]
---
libstdc++-v3/include/bits/ranges_algo.h | 11 ++++++++++-
.../25_algorithms/shuffle/constrained.cc | 18 ++++++++++++++++++
2 files changed, 28 insertions(+), 1 deletion(-)
diff --git a/libstdc++-v3/include/bits/ranges_algo.h
b/libstdc++-v3/include/bits/ranges_algo.h
index 6e1e06cb2d0f..f886edbb952c 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -1964,9 +1964,10 @@ namespace ranges
using __uc_type
= common_type_t<typename remove_reference_t<_Gen>::result_type,
__ud_type>;
+ if constexpr (sized_sentinel_for<_Sent, _Iter>)
+ {
const __uc_type __urngrange = __g.max() - __g.min();
const __uc_type __urange = __uc_type(__last - __first);
-
if (__urngrange / __urange >= __urange)
// I.e. (__urngrange >= __urange * __urange) but without wrap
issues.
{
@@ -1999,6 +2000,7 @@ namespace ranges
return __i;
}
+ }
__distr_type __d;
@@ -2015,6 +2017,13 @@ namespace ranges
borrowed_iterator_t<_Range>
operator()(_Range&& __r, _Gen&& __g) const
{
+ if constexpr (sized_range<_Range>
+ && !sized_sentinel_for<sentinel_t<_Range>,
+ iterator_t<_Range>>)
+ return (*this)(ranges::begin(__r),
+ ranges::begin(__r) + ranges::size(__r),
+ std::forward<_Gen>(__g));
+ else
return (*this)(ranges::begin(__r), ranges::end(__r),
std::forward<_Gen>(__g));
}
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<std::input_or_output_iterator I>
+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();
}
--
2.51.0.193.g4975ec3473
