[PATCH] libstdc++: Memoize {drop,drop_while,filter,reverse}_view::begin
Patrick Palka
ppalka@redhat.com
Wed Feb 12 04:43:00 GMT 2020
This patch adds memoization for these four views so that their begin() has the
required constant time amortized complexity.
In the general case we use std::optional to cache the result. When the
underlying range is a random_access_range then we store the cache as an offset
from the beginning of the range, which should be more compact. And when the
underlying iterator is not copyable, then we completely disable the cache.
Using std::optional in the cache is not ideal though because it means that the
cache can't be utilized during constexpr evaluation. If instead of
std::optional we store a separate flag to denote an empty cache then we'll be
able to use the cache during constexpr evaluation at the cost of a extra byte or
so. I am not sure which design to settle on.
libstdc++-v3/ChangeLog:
* include/std/ranges (__detail::_CachedPosition): New.
(views::filter_view::_S_needs_cached_begin): New member variable.
(views::filter_view::_M_cached_begin): New member variable.
(views::filter_view::begin): Use _M_cached_begin to cache its
result.
(views::drop_view::_S_needs_cached_begin): New static member variable.
(views::drop_view::_M_cached_begin): New member variable.
(views::drop_view::begin): Use _M_cached_begin to cache its result
when _S_needs_cached_begin.
(views::drop_while_view::_M_cached_begin): New member variable.
(views::drop_while_view::begin): Use _M_cached_begin to cache its
result.
(views::reverse_view::_S_needs_cached_begin): New static member
variable.
(views::reverse_view::_M_cached_begin): New member variable.
(views::reverse_view::begin): Use _M_cached_begin to cache its result
when _S_needs_cached_begin.
* testsuite/std/ranges/adaptors/drop.cc: Augment test to check that
drop_view::begin caches its result.
* testsuite/std/ranges/adaptors/drop_while.cc: Augment test to check
that drop_while_view::begin caches its result.
* testsuite/std/ranges/adaptors/filter.cc: Augment test to check that
filter_view::begin caches its result.
* testsuite/std/ranges/adaptors/reverse.cc: Augment test to check that
reverse_view::begin caches its result.
---
libstdc++-v3/include/std/ranges | 138 ++++++++++++++++--
.../testsuite/std/ranges/adaptors/drop.cc | 57 ++++++++
.../std/ranges/adaptors/drop_while.cc | 38 ++++-
.../testsuite/std/ranges/adaptors/filter.cc | 36 +++++
.../testsuite/std/ranges/adaptors/reverse.cc | 56 +++++++
5 files changed, 310 insertions(+), 15 deletions(-)
diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index ef613175b7c..485a073ad3a 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -1302,6 +1302,83 @@ namespace views
}
} // namespace __detail
+ namespace __detail
+ {
+ template<range _Range>
+ struct _CachedPosition
+ {
+ private:
+ std::optional<iterator_t<_Range>> _M_iter;
+
+ public:
+ constexpr bool
+ _M_has_value() const
+ { return _M_iter.has_value(); }
+
+ constexpr iterator_t<_Range>
+ _M_get(const _Range&) const
+ {
+ __glibcxx_assert(_M_has_value());
+ return *_M_iter;
+ }
+
+ constexpr void
+ _M_set(const _Range&, const iterator_t<_Range>& __it)
+ {
+ __glibcxx_assert(!_M_has_value());
+ if constexpr (copyable<iterator_t<_Range>>)
+ if (!is_constant_evaluated())
+ _M_iter.emplace(__it);
+ }
+ };
+
+ template<random_access_range _Range>
+ struct _CachedPosition<_Range>
+ {
+ private:
+ range_difference_t<_Range> _M_offset = -1;
+
+ public:
+ constexpr bool
+ _M_has_value() const
+ { return _M_offset >= 0; }
+
+ constexpr iterator_t<_Range>
+ _M_get(_Range& __r) const
+ {
+ __glibcxx_assert(_M_has_value());
+ return ranges::begin(__r) + _M_offset;
+ }
+
+ constexpr void
+ _M_set(_Range& __r, const iterator_t<_Range>& __it)
+ {
+ __glibcxx_assert(!_M_has_value());
+ _M_offset = __it - ranges::begin(__r);
+ }
+ };
+
+ template<range _Range>
+ requires (!copyable<iterator_t<_Range>>)
+ struct _CachedPosition<_Range>
+ {
+ constexpr bool
+ _M_has_value() const
+ { return false; }
+
+ constexpr iterator_t<_Range>
+ _M_get(const _Range&) const
+ {
+ __glibcxx_assert(false);
+ return {};
+ }
+
+ constexpr void
+ _M_set(const _Range&, const iterator_t<_Range>&) const
+ { }
+ };
+ } // namespace __detail
+
template<input_range _Vp,
indirect_unary_predicate<iterator_t<_Vp>> _Pred>
requires view<_Vp> && is_object_v<_Pred>
@@ -1457,6 +1534,7 @@ namespace views
_Vp _M_base = _Vp();
__detail::__box<_Pred> _M_pred;
+ [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
public:
filter_view() = default;
@@ -1488,11 +1566,15 @@ namespace views
constexpr _Iterator
begin()
{
- // XXX: we need to cache the result here as per [range.filter.view]
+ if (_M_cached_begin._M_has_value())
+ return {*this, _M_cached_begin._M_get(_M_base)};
+
__glibcxx_assert(_M_pred.has_value());
- return {*this, __detail::find_if(ranges::begin(_M_base),
- ranges::end(_M_base),
- std::ref(*_M_pred))};
+ auto __it = __detail::find_if(ranges::begin(_M_base),
+ ranges::end(_M_base),
+ std::ref(*_M_pred));
+ _M_cached_begin._M_set(_M_base, __it);
+ return {*this, std::move(__it)};
}
constexpr auto
@@ -2104,6 +2186,12 @@ namespace views
_Vp _M_base;
range_difference_t<_Vp> _M_count;
+ static constexpr bool _S_needs_cached_begin = !random_access_range<_Vp>;
+ [[no_unique_address]]
+ conditional_t<_S_needs_cached_begin,
+ __detail::_CachedPosition<_Vp>,
+ __detail::_Empty> _M_cached_begin;
+
public:
drop_view() = default;
@@ -2124,9 +2212,15 @@ namespace views
begin() requires (!(__detail::__simple_view<_Vp>
&& random_access_range<_Vp>))
{
- // XXX: we need to cache the result here as per [range.drop.view]
- return ranges::next(ranges::begin(_M_base), _M_count,
- ranges::end(_M_base));
+ if constexpr (_S_needs_cached_begin)
+ if (_M_cached_begin._M_has_value())
+ return _M_cached_begin._M_get(_M_base);
+
+ auto __it = ranges::next(ranges::begin(_M_base),
+ _M_count, ranges::end(_M_base));
+ if constexpr (_S_needs_cached_begin)
+ _M_cached_begin._M_set(_M_base, __it);
+ return __it;
}
constexpr auto
@@ -2182,6 +2276,7 @@ namespace views
private:
_Vp _M_base;
__detail::__box<_Pred> _M_pred;
+ [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
public:
drop_while_view() = default;
@@ -2206,10 +2301,14 @@ namespace views
constexpr auto
begin()
{
- // XXX: we need to cache the result here as per [range.drop.while.view]
- return __detail::find_if_not(ranges::begin(_M_base),
- ranges::end(_M_base),
- std::cref(*_M_pred));
+ if (_M_cached_begin._M_has_value())
+ return _M_cached_begin._M_get(_M_base);
+
+ auto __it = __detail::find_if_not(ranges::begin(_M_base),
+ ranges::end(_M_base),
+ std::cref(*_M_pred));
+ _M_cached_begin._M_set(_M_base, __it);
+ return __it;
}
constexpr auto
@@ -3071,6 +3170,12 @@ namespace views
private:
_Vp _M_base = _Vp();
+ static constexpr bool _S_needs_cached_begin = !random_access_range<_Vp>;
+ [[no_unique_address]]
+ conditional_t<_S_needs_cached_begin,
+ __detail::_CachedPosition<_Vp>,
+ __detail::_Empty> _M_cached_begin;
+
public:
reverse_view() = default;
@@ -3099,9 +3204,14 @@ namespace views
constexpr reverse_iterator<iterator_t<_Vp>>
begin()
{
- // XXX: we need to cache the result here as per [range.reverse.view]
- return make_reverse_iterator(ranges::next(ranges::begin(_M_base),
- ranges::end(_M_base)));
+ if constexpr (_S_needs_cached_begin)
+ if (_M_cached_begin._M_has_value())
+ return make_reverse_iterator(_M_cached_begin._M_get(_M_base));
+
+ auto __it = ranges::next(ranges::begin(_M_base), ranges::end(_M_base));
+ if constexpr (_S_needs_cached_begin)
+ _M_cached_begin._M_set(_M_base, __it);
+ return make_reverse_iterator(std::move(__it));
}
constexpr auto
diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc
index 93fbafcf5a3..2db275fb28b 100644
--- a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc
@@ -24,6 +24,7 @@
#include <testsuite_iterators.h>
using __gnu_test::test_range;
+using __gnu_test::forward_iterator_wrapper;
using __gnu_test::bidirectional_iterator_wrapper;
namespace ranges = std::ranges;
@@ -95,6 +96,61 @@ test06()
VERIFY( ranges::empty(x | views::drop(10)) );
}
+// The following tests that drop_view::begin caches its result.
+
+template<typename T>
+struct test_wrapper : forward_iterator_wrapper<T>
+{
+ static inline int increment_count = 0;
+
+ using forward_iterator_wrapper<T>::forward_iterator_wrapper;
+
+ test_wrapper() : forward_iterator_wrapper<T>(nullptr, nullptr)
+ { }
+
+ test_wrapper
+ operator++(int)
+ {
+ auto tmp = *this;
+ ++*this;
+ return tmp;
+ }
+
+ test_wrapper&
+ operator++()
+ {
+ ++increment_count;
+ forward_iterator_wrapper<T>::operator++();
+ return *this;
+ }
+
+ test_wrapper
+ operator--(int)
+ {
+ auto tmp = *this;
+ --*this;
+ return tmp;
+ }
+
+ test_wrapper&
+ operator--()
+ {
+ forward_iterator_wrapper<T>::operator--();
+ return *this;
+ }
+};
+
+void
+test07()
+{
+ int x[] = {1,2,3,4,5};
+ test_range<int, test_wrapper> rx(x);
+ auto v = rx | views::drop(3);
+ VERIFY( ranges::equal(v, (int[]){4,5}) );
+ VERIFY( ranges::equal(v, (int[]){4,5}) );
+ VERIFY( test_wrapper<int>::increment_count == 7 );
+}
+
int
main()
{
@@ -104,4 +160,5 @@ main()
test04();
test05();
test06();
+ test07();
}
diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc
index be47551563d..4d8bb109fae 100644
--- a/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc
@@ -25,6 +25,8 @@
using __gnu_test::test_range;
using __gnu_test::bidirectional_iterator_wrapper;
+using __gnu_test::forward_iterator_wrapper;
+using __gnu_test::random_access_iterator_wrapper;
namespace ranges = std::ranges;
namespace views = std::ranges::views;
@@ -54,10 +56,44 @@ test02()
static_assert(ranges::bidirectional_range<R>);
}
+// The following tests that drop_while_view::begin caches its result.
+
+template<template<typename> typename wrapper>
+struct test_view : ranges::view_base
+{
+ bool begin_already_called = false;
+ static inline int x[] = {1,2,3,4,5};
+ test_range<int, wrapper> rx{x};
+
+ auto
+ begin()
+ {
+ if (begin_already_called)
+ x[0] = 10;
+ begin_already_called = true;
+ return rx.begin();
+ }
+
+ auto
+ end()
+ { return rx.end(); }
+};
+
+template<template<typename> typename wrapper>
+void
+test03()
+{
+ auto v
+ = test_view<wrapper>{} | views::drop_while([] (int i) { return i<3; });
+ VERIFY( ranges::equal(v, (int[]){3,4,5}) );
+ VERIFY( ranges::equal(v, (int[]){3,4,5}) );
+}
+
int
main()
{
test01();
test02();
+ test03<forward_iterator_wrapper>();
+ test03<random_access_iterator_wrapper>();
}
-
diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc
index 83d52967a0f..834d10f7f91 100644
--- a/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc
@@ -25,6 +25,8 @@
using __gnu_test::test_range;
using __gnu_test::bidirectional_iterator_wrapper;
+using __gnu_test::forward_iterator_wrapper;
+using __gnu_test::random_access_iterator_wrapper;
namespace ranges = std::ranges;
namespace views = std::ranges::views;
@@ -87,6 +89,38 @@ test04()
(int[]){0}) );
}
+// The following tests that filter_view::begin caches its result.
+
+template<template<typename> typename wrapper>
+struct test_view : ranges::view_base
+{
+ bool begin_already_called = false;
+ static inline int x[] = {1,2,3,4,5};
+ test_range<int, wrapper> rx{x};
+
+ auto
+ begin()
+ {
+ if (begin_already_called)
+ x[0] = 10;
+ begin_already_called = true;
+ return rx.begin();
+ }
+
+ auto
+ end()
+ { return rx.end(); }
+};
+
+template<template<typename> typename wrapper>
+void
+test05()
+{
+ auto v = test_view<wrapper>{} | views::filter([] (int i) { return i%2 == 0; });
+ VERIFY( ranges::equal(v, (int[]){2,4}) );
+ VERIFY( ranges::equal(v, (int[]){2,4}) );
+}
+
int
main()
{
@@ -94,4 +128,6 @@ main()
test02();
test03();
test04();
+ test05<forward_iterator_wrapper>();
+ test05<random_access_iterator_wrapper>();
}
diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc
index 0c6aceabbed..db85c57dd43 100644
--- a/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc
@@ -76,6 +76,61 @@ test04()
(int[]){5,4,3,2,1}) );
}
+// The following tests that reverse_view::begin caches its result.
+
+template<typename T>
+struct test_wrapper : bidirectional_iterator_wrapper<T>
+{
+ static inline int increment_count = 0;
+
+ using bidirectional_iterator_wrapper<T>::bidirectional_iterator_wrapper;
+
+ test_wrapper() : bidirectional_iterator_wrapper<T>(nullptr, nullptr)
+ { }
+
+ test_wrapper
+ operator++(int)
+ {
+ auto tmp = *this;
+ ++*this;
+ return tmp;
+ }
+
+ test_wrapper&
+ operator++()
+ {
+ ++increment_count;
+ bidirectional_iterator_wrapper<T>::operator++();
+ return *this;
+ }
+
+ test_wrapper
+ operator--(int)
+ {
+ auto tmp = *this;
+ --*this;
+ return tmp;
+ }
+
+ test_wrapper&
+ operator--()
+ {
+ bidirectional_iterator_wrapper<T>::operator--();
+ return *this;
+ }
+};
+
+void
+test05()
+{
+ int x[] = {1,2,3,4,5};
+ test_range<int, test_wrapper> rx(x);
+ auto v = rx | views::reverse;
+ VERIFY( ranges::equal(v, (int[]){5,4,3,2,1}) );
+ VERIFY( ranges::equal(v, (int[]){5,4,3,2,1}) );
+ VERIFY( test_wrapper<int>::increment_count == 5 );
+}
+
int
main()
{
@@ -83,4 +138,5 @@ main()
test02();
test03();
test04();
+ test05();
}
--
2.25.0.191.gde93cc14ab
More information about the Gcc-patches
mailing list