diff mbox series

libstdc++: Fix complexity of drop_view::begin const [PR112641]

Message ID 20241025152414.1780304-1-ppalka@redhat.com
State Committed
Commit 7f622ee83fbbcf4a4ca70e020db8a0ce4b556b61
Headers
Series libstdc++: Fix complexity of drop_view::begin const [PR112641] |

Checks

Context Check Description
linaro-tcwg-bot/tcwg_gcc_build--master-aarch64 success Build passed
linaro-tcwg-bot/tcwg_gcc_check--master-aarch64 success Test passed
linaro-tcwg-bot/tcwg_gcc_build--master-arm success Build passed
linaro-tcwg-bot/tcwg_gcc_check--master-arm success Test passed

Commit Message

Patrick Palka Oct. 25, 2024, 3:24 p.m. UTC 
  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(-)

Comments

Jonathan Wakely Oct. 28, 2024, 3:37 p.m. UTC | #1 
On Fri, 25 Oct 2024 at 16:24, Patrick Palka <ppalka@redhat.com> wrote:
>
> Tested on x86_64-pc-linux-gnu, does this look OK for trunk/backports?

OK for all (also approved on the forge).

> 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<const _Vp> && sized_range<const _Vp>
>        {
> -       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());
>  }
> --
> 2.47.0.118.gfd3785337b
>
diff mbox series

Patch

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<const _Vp> && sized_range<const _Vp>
       {
-	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());
 }