[gcc r10-6917] libstdc++: Memoize {drop, drop_while, filter, reverse}_view::begin
Patrick Palka
ppalka@gcc.gnu.org
Fri Feb 28 14:47:00 GMT 2020
https://gcc.gnu.org/g:a15350157862db3631772b4ae69a9c9e3b0fab6e
commit r10-6917-ga15350157862db3631772b4ae69a9c9e3b0fab6e
Author: Patrick Palka <ppalka@redhat.com>
Date: Tue Feb 11 17:14:22 2020 -0500
libstdc++: Memoize {drop,drop_while,filter,reverse}_view::begin
This patch adds memoization to these four views so that their begin() has the
required amortized constant time complexity.
The cache is enabled only for forward_ranges and above because we need the
underlying iterator to be copyable and multi-pass in order for the cache to be
usable. In the general case we represent the cached result of begin() as a bare
iterator. This takes advantage of the fact that value-initialized forward
iterators can be compared to as per N3644, so we can use a value-initialized
iterator to denote the "empty" state of the cache.
As a special case, when the underlying range models random_access_range and when
it's profitable size-wise, then we cache the offset of the iterator from the
beginning of the range instead of caching the iterator itself.
Additionally, in drop_view and reverse_view we disable the cache when the
underlying range models random_access_range, because in these cases recomputing
begin() takes O(1) time anyway.
libstdc++-v3/ChangeLog:
* include/std/ranges (__detail::_CachedPosition): New struct.
(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.
Diff:
---
libstdc++-v3/ChangeLog | 28 +++++
libstdc++-v3/include/std/ranges | 136 ++++++++++++++++++---
libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc | 57 +++++++++
.../testsuite/std/ranges/adaptors/drop_while.cc | 38 +++++-
.../testsuite/std/ranges/adaptors/filter.cc | 36 ++++++
.../testsuite/std/ranges/adaptors/reverse.cc | 56 +++++++++
6 files changed, 336 insertions(+), 15 deletions(-)
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 9fe2fd2..89e1f5b 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,31 @@
+2020-02-28 Patrick Palka <ppalka@redhat.com>
+
+ * include/std/ranges (__detail::_CachedPosition): New struct.
+ (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.
+
2020-02-28 Jonathan Wakely <jwakely@redhat.com>
* testsuite/27_io/filesystem/operations/last_write_time.cc: Fixes for
diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index 38d497e..2f77313 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -1334,6 +1334,83 @@ namespace views
}
} // namespace __detail
+ namespace __detail
+ {
+ template<range _Range>
+ struct _CachedPosition
+ {
+ 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
+ { }
+ };
+
+ template<forward_range _Range>
+ struct _CachedPosition<_Range>
+ {
+ private:
+ iterator_t<_Range> _M_iter{};
+
+ public:
+ constexpr bool
+ _M_has_value() const
+ { return _M_iter != iterator_t<_Range>{}; }
+
+ 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());
+ _M_iter = __it;
+ }
+ };
+
+ template<random_access_range _Range>
+ requires (sizeof(range_difference_t<_Range>)
+ <= sizeof(iterator_t<_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);
+ }
+ };
+
+ } // namespace __detail
+
template<input_range _Vp,
indirect_unary_predicate<iterator_t<_Vp>> _Pred>
requires view<_Vp> && is_object_v<_Pred>
@@ -1491,6 +1568,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;
@@ -1515,11 +1593,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
@@ -2127,6 +2209,11 @@ namespace views
_Vp _M_base = _Vp();
range_difference_t<_Vp> _M_count = 0;
+ static constexpr bool _S_needs_cached_begin = !random_access_range<_Vp>;
+ [[no_unique_address]]
+ __detail::__maybe_empty_t<_S_needs_cached_begin,
+ __detail::_CachedPosition<_Vp>> _M_cached_begin;
+
public:
drop_view() = default;
@@ -2147,9 +2234,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
@@ -2205,6 +2298,7 @@ namespace views
private:
_Vp _M_base = _Vp();
__detail::__box<_Pred> _M_pred;
+ [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
public:
drop_while_view() = default;
@@ -2229,10 +2323,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
@@ -3079,6 +3177,11 @@ namespace views
private:
_Vp _M_base = _Vp();
+ static constexpr bool _S_needs_cached_begin = !random_access_range<_Vp>;
+ [[no_unique_address]]
+ __detail::__maybe_empty_t<_S_needs_cached_begin,
+ __detail::_CachedPosition<_Vp>> _M_cached_begin;
+
public:
reverse_view() = default;
@@ -3098,9 +3201,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 93fbafc..3c82cae 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>()
+ { }
+
+ 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 be47551..4d8bb10 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 4e41232..58d898f 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;
@@ -89,6 +91,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()
{
@@ -96,4 +130,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 0c6acea..ceaaf3e 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>()
+ { }
+
+ 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();
}
More information about the Libstdc++-cvs
mailing list